网站建设开发方案,wordpress主题显示不完整,上海网站备案在哪里查询,自己建网站需要钱吗蚁群算法#xff08;密恐勿入#xff09; 蚁群算法--给你一个感性认识 蚁群算法#xff08;密恐勿入#xff09;1. 算法简介1.1 基本原理1.1.1 模拟蚂蚁在简单地形#xff0c;寻找食物1.1.2 模拟蚂蚁在复杂地形#xff0c;找到食物1.2 算法应用 2. 算法解析3.算法应用——…蚁群算法密恐勿入 蚁群算法--给你一个感性认识 蚁群算法密恐勿入1. 算法简介1.1 基本原理1.1.1 模拟蚂蚁在简单地形寻找食物1.1.2 模拟蚂蚁在复杂地形找到食物1.2 算法应用 2. 算法解析3.算法应用——TSP问题3.1 TSP旅行商介绍3.2 利用蚁群算法解决TSP问题总结一下 1. 算法简介
1.1 基本原理
蚁群算法是一种模拟蚂蚁觅食行为的启发式算法被广泛应用于优化问题的求解。蚁群算法的基本思想是将一群蚂蚁放在问题的解空间上让它们通过信息素的传递和挥发逐渐找到最优解。
1.1.1 模拟蚂蚁在简单地形寻找食物 阶段一在蚁群算法的初始阶段我们在地图上不放置任何食物因为蚂蚁需要在没有任何信息素的情况下开始摸索前进。一开始蚂蚁们在洞外随机移动试图找到食物的位置。每只蚂蚁的速度相同它们会按照随机的方向前进直到遇到障碍物或者到达了边界。此时它们会再次随机选择一个方向并继续前进。这个过程会持续进行 阶段二当蚂蚁们找到了食物后它们会将一些信息素沿着它们的路径释放出来并且在回到蚁巢的路上也会释放信息素。 蚁群之间的规则
蚂蚁发现食物并将其带回巢穴时通常会遵循已经标记的路径返回即原路返回。在返回过程中蚂蚁会释放归巢素和信息素这些化学物质可以吸引其他蚂蚁跟随它的路径前往食物源。如果路径上有较多的归巢素或信息素则越来越多的蚂蚁将会选择这条路径前往食物。 阶段三当蚂蚁们回到巢穴时它们会在原来的路径上释放更多信息素增强这条路径的吸引力并且尝试着寻找更短的路径。蚂蚁们会在路径上选择合适的地方停下来释放信息素然后返回巢穴。这个过程将持续进行直到蚂蚁们找到了最优路径。 根据以上规则随着时间的推移蚂蚁们终会可能找到的最优路径。 1.1.2 模拟蚂蚁在复杂地形找到食物 1.2 算法应用
蚁群算法已经应用于多种优化问题的求解比如
旅行商问题图着色问题网络路由问题调度问题生产计划问题
在这些问题中蚁群算法通常能够找到较优的解。此外蚁群算法还可以用于机器学习领域中的聚类和分类等问题。
2. 算法解析
想要理解算法需要去理解以下内容 蚁群是如何找到解的解的步骤是什么 蚂蚁在初始时随机选择一个起点并向前行走。当蚂蚁走到一个节点时它会选择一个下一个节点进行移动。蚂蚁选择下一个节点的概率与该节点上的信息素浓度成正比。信息素浓度越高的节点被选择的概率也越高。当蚂蚁移动到一个节点时它会在该节点上释放一定量的信息素。当蚂蚁找到解后它会回到起点并在路径上释放更多的信息素增强这条路径的吸引力。当其他蚂蚁在寻找解的过程中遇到已经被标记的路径时它们会更有可能选择这条路径。随着时间的推移信息素会挥发路径上信息素的浓度会逐渐降低。这样路径上的信息素浓度会经历一个上升和下降的过程。蚂蚁们会根据路径上的信息素浓度来选择下一个节点。当信息素浓度很高时它们更有可能选择这条路径。蚂蚁们持续寻找解直到找到最优解或者达到预设的迭代次数。 作者个人理解 蚂蚁个体之间就是通过这种间接的通信机制实现协同搜索最短路径的目标的。我们举例简单说明蚂蚁觅食行为 现阶段 蚂蚁有A→B→C 和 A→D→C两种较优路径 A→D→C的距离要大于A→B→C
因为大量蚂蚁的选择概率会不一样会将蚂蚁大致分为两批一批走A→B→C 另一批走A→D→C单位时间内A→B→C通过蚂蚁也要大于 A→D→C随着时间的推移A→B→C的信息素越来越多正反馈调节下走此条路径的蚂蚁也越来越多。所以越短路径的浓度会越来越大经过此短路径达到目的地的蚂蚁也会比其他路径多。这样大量的蚂蚁实践之后就找到了最短路径。所以这个过程本质可以概括为以下几点
路径概率选择机制信息素踪迹越浓的路径,被选中的概率越大信息素更新机制路径越短,路径上的信息素踪迹增长得越快协同工作机制蚂蚁个体通过信息素进行信息交流。 蚂蚁在蚁群算法中通过信息素的传递和挥发来进行交流。通过信息素的传递和挥发整个蚁群就会产生信息正反馈现象、种群分化等。 正反馈现象 由大量蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象。某一路径上走过的蚂蚁越多,则后来者选择该路径的可能性就越大。 在一个人流量比较大的商场人们往往会选择人流量比较大的走廊或者通道来走因为人流量越大越能够说明这个通道是正确的这样就会产生一种信息正反馈现象后来的人也会选择这条路线进一步增加这条路线的人流量。与蚁群算法类似人们会根据前人的经验来选择路线从而产生类似的正反馈现象。 种群分化 种群分化是蚁群算法中的一个现象当蚂蚁在搜索过程中遇到了局部最优解时会一直围绕这个局部最优解寻找并且释放信息素。这会导致其他蚂蚁也会被吸引过来导致整个蚁群陷入局部最优解而无法找到全局最优解的情况。这种现象在蚁群算法中是非常常见的需要特别注意。为了避免种群分化蚂蚁需要具有一定的随机性同时需要及时更新信息素以便发现全局最优解。 一个人在某个领域上有很高的专业技能但是如果他过于专注于这个领域就可能会失去对其他领域的了解和认识进而导致对问题的认识出现偏差甚至无法解决某些问题。 就比如图1. 我如果此刻将原有阻碍去掉一部分此时只靠信息素交流的蚁群会产生种群分化现象。陷入了局部最有解。 当蚁群算法陷入局部最优解时可以使用以下方法进行优化
增加蚂蚁的数量。增加蚂蚁的数量可以增加搜索的广度从而有更大的可能性找到全局最优解。调整信息素挥发速度。通过适当降低信息素挥发速度可以增加信息素在路径上的积累从而增加蚂蚁选择该路径的概率。引入随机因素。在蚁群算法中引入随机因素可以使蚂蚁更具有探索性从而有可能跳出局部最优解进而找到全局最优解。改变参数。通过改变蚁群算法中的参数如信息素浓度、信息素挥发速度、启发式因子等可以使算法更加灵活从而更容易找到全局最优解。使用局部搜索算法。在蚁群算法的基础上可以结合局部搜索算法如模拟退火算法、遗传算法等来寻找全局最优解。
上述的情况可以利用第三条和第四条解决。
3.算法应用——TSP问题
3.1 TSP旅行商介绍
首先我们先回顾一下什么是TSP旅行商问题 假设有一位邮递员他从初始城市任意一城市出发途径所有城市并回到初始城市那么他一共会有 ( n − 1 ) ! (n-1)! (n−1)!
条路径。从中找出那条最短路径这就是TSP旅行商问题。
如果我们遍历的去找那个最短路径那么随着城市的增加计算量大大增加。 3.2 利用蚁群算法解决TSP问题
在这里蚂蚁仅有信息素这一项能力是不够的。所以我们给与蚂蚁一些其他的能力
蚂蚁在一次旅行中不会重复访问相同的城市蚂蚁可以知晓城市之间的距离。蚂蚁在路上会释放信息素蚂蚁在选择下一个城市的概率依靠以下公式 p i j k ( τ i j α ) ( η i j β ) ∑ allowed k ( τ i j α ) ( η i j β ) p_{i j}^{k}\frac{\left(\tau_{i j}^{\alpha}\right)\left(\eta_{i j}^{\beta}\right)}{\sum_{\text {allowed}_k}\left(\tau_{i j}^{\alpha}\right)\left(\eta_{i j}^{\beta}\right)} pijk∑allowedk(τijα)(ηijβ)(τijα)(ηijβ)
参数名称参数意义参数设置过大参数设置过小信息素因子ɑ反映了蚂蚁运动过程中路径上积累的信息素的量在指导蚁群搜索中的相对重要程度。取值范围通常在[1, 4]之间。蚂蚁选择以前已经走过的路可能性较大容易使随机搜索性减弱蚁群易陷入纯粹的随机搜索使种群陷入局部最优启发函数因子反映了启发式信息在指导蚁群搜索中的相对重要程度蚁群寻优过程中先验性、确定性因素作用的强度取值范围在[0, 5]之间虽然收敛速度加快但是易陷入局部最优蚁群易陷入纯粹的随机搜索很难找到最优解 其实这个公式也很好理解蚂蚁选择城市的概率主要由 τ i j ( t ) \tau_{ij}(t) τij(t)和 η i j ( ) \eta_{ij}() ηij(t)有关分母为蚂蚁k可能访问的城市之和为常数这样才能使蚂蚁选择各个城市的概率之后为1符合概率的定义。 τ i j ( t ) \tau_{ij}(t) τij(t)和$\eta_{ij}()上的指数信息素因子ɑ和启发函数因子只决定了信息素浓度以及启发函数对蚂蚁k从i到j的可能性的贡献程度。
例下图为计算蚂蚁从起点城市2到可达城市的概率套公式很好理解: 图2. 此图和此节部分内容借鉴于秃头小苏蚁群算法(实例帮助理解)
OK,蚂蚁有了这些能力后我们只需要控制一下流程就可以解决TSP问题了下面是给出了此问题的一种常用的解决流程
蚁群算法解决TSP问题的算法流程
初始化信息素浓度矩阵 τ i j ( t ) \tau_{ij}(t) τij(t)启发式函数 η i j \eta_{ij} ηij以及蚂蚁的位置。每只蚂蚁按照信息素和启发式函数的概率选择下一个城市。记录蚂蚁的路径和距离。在所有蚂蚁走完所有城市之后根据蚂蚁走过的路径和距离更新信息素浓度矩阵 η i j ( t ) \eta_{ij}(t) ηij(t)。如果未达到停止条件则返回步骤2。
其中停止条件可以是迭代次数达到预设值或者最佳解不再改变。 起点的选择对最短路径是有影响的。不同的起点可能会导致不同的最短路径。在蚁群算法中通过随机选择起始点可以增加搜索的广度从而有更大的可能性找到全局最优解。 信息素更新的时机一般有两种方式
在每个迭代周期结束后进行更新即在所有蚂蚁完成当前迭代周期后根据其路径长度和信息素更新信息素浓度。在每只蚂蚁走遍所有城市之后立即更新信息素浓度。
信息素更新公式: τ i j ( t 1 ) ( 1 − ρ ) τ i j ( t ) ∑ k 1 m Δ τ i j k ( t ) \tau_{i j}(t1)(1-\rho) \tau_{i j}(t)\sum_{k1}^{m} \Delta \tau_{i j}^{k}(t) τij(t1)(1−ρ)τij(t)k1∑mΔτijk(t)
其中 ρ \rho ρ 是信息素挥发速度 Δ τ i j k ( t ) \Delta \tau_{i j}^{k}(t) Δτijk(t) 是蚂蚁 k 在迭代 t 中走过路径 i 到 j 所留下的信息素m 是蚂蚁的数量。
在每个迭代周期结束后进行更新或在每只蚂蚁走遍所有城市之后立即更新信息素浓度均可。
Delta tau 是蚂蚁 k 在迭代 t 中走过路径 i 到 j 所留下的信息素不同的 Delta tau 规则有以下几种
静态规则所有蚂蚁在搜索过程中释放的信息素量是相等的即 Δ τ i j k ( t ) Q / L k ( t ) \Delta \tau_{i j}^{k}(t)Q/L_{k}(t) Δτijk(t)Q/Lk(t)其中 Q 是常量L_k(t) 是蚂蚁 k 在迭代 t 中走过的路径长度。动态规则蚂蚁在搜索过程中释放的信息素量是动态变化的即 Δ τ i j k ( t ) Q / L k ( t ) ∑ k 1 m w k ⋅ L k ( t ) \Delta \tau_{i j}^{k}(t)Q/L_{k}(t)\sum_{k1}^{m} w_{k} \cdot L_{k}(t) Δτijk(t)Q/Lk(t)∑k1mwk⋅Lk(t)其中 ∑ k 1 m w k 1 \sum_{k1}^{m} w_{k}1 ∑k1mwk1w_k 是蚂蚁 k 对信息素的贡献系数L_k(t) 是蚂蚁 k 在迭代 t 中走过的路径长度。最大值规则每只蚂蚁在搜索过程中释放的信息素量最多为 Δ τ i j k ( t ) Q L b e s t \Delta \tau_{i j}^{k}(t)\frac{Q}{L_{best}} Δτijk(t)LbestQ其中 L_best 是迄今为止找到的最短路径长度。 以上规则中静态规则是最简单的但是可能会导致信息素的浓度过高或过低从而影响搜索效果。动态规则可以根据搜索的进展情况动态调整信息素的浓度适应性更强。最大值规则可以防止信息素浓度过高但可能会导致搜索无法跳出局部最优解。 例(静态规则)下图为信息素的更新过程假设初始时各路径信息素浓度为10。 总结一下
蚁群算法流程
初始化信息素浓度矩阵_{ij}(t)启发式函数_{ij}以及蚂蚁的位置。每只蚂蚁按照信息素和启发式函数的概率选择下一个城市。记录蚂蚁的路径和距离。在所有蚂蚁走完所有城市之后根据蚂蚁走过的路径和距离更新信息素浓度矩阵_{ij}(t)。如果未达到停止条件则返回步骤2。
其中停止条件可以是迭代次数达到预设值或者最佳解不再改变。
起点的选择对最短路径是有影响的。不同的起点可能会导致不同的最短路径。在蚁群算法中通过随机选择起始点可以增加搜索的广度从而有更大的可能性找到全局最优解。
信息素更新的时机一般有两种方式
在每个迭代周期结束后进行更新即在所有蚂蚁完成当前迭代周期后根据其路径长度和信息素更新信息素浓度。在每只蚂蚁走遍所有城市之后立即更新信息素浓度。
信息素更新公式: τ i j ( t 1 ) ( 1 − ρ ) τ i j ( t ) ∑ k 1 m Δ τ i j k ( t ) \tau_{i j}(t1)(1-\rho) \tau_{i j}(t)\sum_{k1}^{m} \Delta \tau_{i j}^{k}(t) τij(t1)(1−ρ)τij(t)k1∑mΔτijk(t)
其中 ρ \rho ρ 是信息素挥发速度 Δ τ i j k ( t ) \Delta \tau_{i j}^{k}(t) Δτijk(t) 是蚂蚁 k 在迭代 t 中走过路径 i 到 j 所留下的信息素m 是蚂蚁的数量。
在每个迭代周期结束后进行更新或在每只蚂蚁走遍所有城市之后立即更新信息素浓度均可。
Delta tau 是蚂蚁 k 在迭代 t 中走过路径 i 到 j 所留下的信息素不同的 Delta tau 规则有以下几种
静态规则所有蚂蚁在搜索过程中释放的信息素量是相等的即 Δ τ i j k ( t ) Q / L k ( t ) \Delta \tau_{i j}^{k}(t)Q/L_{k}(t) Δτijk(t)Q/Lk(t)其中 Q 是常量L_k(t) 是蚂蚁 k 在迭代 t 中走过的路径长度。动态规则蚂蚁在搜索过程中释放的信息素量是动态变化的即 Δ τ i j k ( t ) Q / L k ( t ) ∑ k 1 m w k ⋅ L k ( t ) \Delta \tau_{i j}^{k}(t)Q/L_{k}(t)\sum_{k1}^{m} w_{k} \cdot L_{k}(t) Δτijk(t)Q/Lk(t)∑k1mwk⋅Lk(t)其中 ∑ k 1 m w k 1 \sum_{k1}^{m} w_{k}1 ∑k1mwk1w_k 是蚂蚁 k 对信息素的贡献系数L_k(t) 是蚂蚁 k 在迭代 t 中走过的路径长度。最大值规则每只蚂蚁在搜索过程中释放的信息素量最多为 Δ τ i j k ( t ) Q L b e s t \Delta \tau_{i j}^{k}(t)\frac{Q}{L_{best}} Δτijk(t)LbestQ其中 L_best 是迄今为止找到的最短路径长度。
