蚁群算法

蚁群算法1.蚁群算法简述2.蚁群算法原理4.蚁群算法应用3.蚁群算法改进MacroDorigo蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。由MarcoDorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用自然界蚂蚁群体在寻找食物的过程中，通过一种被称为信息素（Pheromone）的物质实现相互的间接通信，从而能够合作发现从蚁穴到食物源的最短路径。通过对这种群体智能行为的抽象建模，研究者提出了蚁群优化算法（AntColonyOptimization,ACO），为最优化问题、尤其是组合优化问题的求解提供了一强有力的手段。1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用自然界蚂蚁觅食行为蚁群优化算法1.蚁群算法简述2.蚁群算法原理3.蚁群算法扩展4.蚁群算法应用自然界蚂蚁觅食行为蚁群优化算法蚁群搜索空间的一组有效解问题的搜索空间信息素浓度变量一个有效解问题的最优解觅食空间信息素蚁巢到食物的一条路径找到的最短路径对应关系启发式搜索蚂蚁间的通信食物该走那条路呢？我走我自己的路这条路好远，少产生信息素这条路好近，多产生点信息素跟着信息素多的准没错蚁群觅食行为图1.蚁群算法简述2.蚁群算法原理3.蚁群算法扩展4.蚁群算法应用蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。不难看出，有大量蚂蚁组成的群体的集体行为表现出了一种信息正反馈现象：某条路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁个体之间就是通过这种信息的交流来达到搜索食物的目的，由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。基本蚂蚁算法模型TSP问题旅行商问题，即TSP问题假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用蚁群优化的本质在于：选择机制：信息素越多的路径，被选择的概率越大。更新机制：路径上面的信息素会随蚂蚁的经过而增长，同时也随时间的推移逐渐挥发消失。协调机制：蚂蚁间通过环境中的信息素来协同工作。蚁群算法的寻优包含两个基本过程：蚂蚁构建解：通过使一群蚂蚁并行异步访问邻近点，逐步建立优化问题的解。更新信息素：依据蚂蚁所构建的解修改空间内的信息素浓度。1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用相关参数m：是群体中的蚂蚁总数𝑑(𝑖,𝑗)：表示城市𝑖和城市𝑗之间的距𝜏𝑖𝑗：表示在t时刻城市𝑖和𝑗之间的信息素.初始时刻各条路径上信息素相等，𝜏𝑖𝑗=𝐶(C为常数)。𝑝𝑖𝑗𝑡：在t时刻蚂蚁k由城市i转移到城市j的概率𝑎𝑙𝑙𝑜𝑤𝑑𝑘=0,1…𝑛−1−𝑡𝑎𝑏𝑢𝑘：表示蚂蚁k下一步允许走过的城市的集合。蚂蚁具有记忆功能，𝑡𝑎𝑏𝑢𝑘(k=1,2，…，m)用以记录蚂蚁k当前所走过的城市，随着进化过程作动态调整。𝛼：表示路径上的信息索对蚂蚁选择路径所起的相对作用大小。𝜂𝑖𝑗：为由城市𝑖转移到城市𝑗的期望程度。例如，可以取𝜂𝑖𝑗=1/𝑑𝑖𝑗𝛽：表示相对于𝜏𝑖𝑗的重要程度。当𝛼=0，算法就是传统的贪心算法当𝛽=0时，就成了纯粹的正反馈的启发式算法。1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用经过𝑛个时刻，蚂蚁可走完所有的城市，完成一次循环。每只蚂蚁所走过的路径就是一个解。此时，要根据下面的更新规则对各条路径上的信息素进行更新：信息素进行更新其中𝜌∈(0，1)为挥发因子，因为随着时间的推移，路径上以前留下的信息素会逐渐消失，用参数𝜌表示信息素𝜏𝑖𝑗随时间的推移而衰减的程度。信息素增量∆𝜏𝑖𝑗可表示为：∆𝜏𝑖𝑗𝑘表示蚂蚁k在本次循环中在城市𝑖和𝑗之间留下的信息素Q为常数，𝐿𝑘为蚂蚁k在本次循环中所走路径的长1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用算法流程1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用例给出用蚁群算法求解一个四城市的TSP问题的执行步骤，四个城市A、B、C、D之间的距离矩阵如下假设蚂蚁种群的规模m=3,参数a=1，b=2，r=0.5。312354152242ijWd1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用解：步骤1：初始化。首先使用贪心算法得到路径(ACDBA)，则Cnn=f(ACDBA)=1+2+4+3=10。求得0=m/Cnn=3/10=0.3。初始化所有边上的信息素ij=0。1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用步骤2.2：为每只蚂蚁选择下城市。我们仅以蚂蚁1为例，当前城市i=A,可访问城市集合J1(i)={B,C,D}。计算蚂蚁1选择B,C,D作为下一访问城市的概率：()0.075/(0.0330.30.075)0.18pD()0.033/(0.0330.30.075)0.081pB()0.3/(0.0330.30.075)0.74pC121212:0.3(1/3)0.033:0.3(1/1)0.3:0.3(1/2)0.075ABABACACADADBACDababab用轮盘赌法则选择下城市。假设产生的随机数q=random(0,1)=0.05，则蚂蚁1将会选择城市B。用同样的方法为蚂蚁2和3选择下一访问城市，假设蚂蚁2选择城市D，蚂蚁3选择城市A。步骤2.1：为每只蚂蚁随机选择出发城市，假设蚂蚁1选择城市A，蚂蚁2选择城市B，蚂蚁3选择城市D。1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用步骤2.3：当前蚂蚁1所在城市i=B,路径记忆向量R1=(AB)，可访问城市集合J1(i)={C,D}。计算蚂蚁1选择C,D作为下一城市的概率：1212:0.3(1/5)0.012:0.3(1/4)0.019BCBCBDBDCBDabab()0.012/(0.0120.019)0.39pC()0.019/(0.0120.019)0.61pD用轮盘赌法则选择下城市。假设产生的随机数q=random(0,1)=0.67，则蚂蚁1将会选择城市D。用同样的方法为蚂蚁2和3选择下一访问城市，假设蚂蚁2选择城市C，蚂蚁3选择城市C。1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用步骤2.4：实际上此时路径已经构造完毕，蚂蚁1构建的路径为(ABDCA)。蚂蚁2构建的路径为(BDCAB)。蚂蚁3构建的路径为(DACBD)。步骤3：信息素更新。计算每只蚂蚁构建的路径长度：C1=3+4+2+1=10，C2=4+2+1+3=10，C3=2+1+5+4=12。更新每条边上的信息素：31(1)0.50.3(1/101/10)0.35kABABABkr31(1)0.50.3(1/12)0.16kACACACkr……如此，根据公式(5.2)依次计算出问题空间内所有边更新后的信息素量。仿真结果1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用缺点：需要较长的计算时间，容易停滞所有路径的信息素增量，会导致错误的引导适用小规模的系统基本蚁群算法的特点1.蚂蚁算法是一种并行的优化算法。蚂蚁搜索食物的过程彼此独立，只通过信息素进行间接的交流。并行计算可以显著减少计算时间。2.蚂蚁算法是一种正反馈算法。一段路径上的信息素水平越高，就越能够吸引更多的蚂蚁沿着这条路径运动，这又使得其信息素水平增加。正反馈的存在使得搜索很快收敛。3.蚂蚁算法的鲁棒性性能较好。相对于其它算法，蚂蚁算法对初始路线的要求不高。也就是说，蚂蚁算法的搜索结果不依赖于初始路线的选择。4.蚂蚁算法的搜索过程不需要进行人工的调整。蚂蚁算法可以在不需要人工干预的情况下完成从初始化到得到整个结果的整个计算过程1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用蚁群算法改进随着规模的扩大比起其他启发式算法，AS算法的性能下降的十分严重。因此出现了很多改进的蚁群算法，精华蚁群算法、基于排列的蚂蚁系统𝐴𝑆𝑟𝑎𝑛𝑘和最大最小蚂蚁系统等1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用精华蚂蚁系统（EAS）思想：对算法从开始到目前为止找到的最优路径实施一种额外的强化手段1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用信息素更新规则𝑇𝑏𝑠:从开始到目前为止找到的最优路径针对𝑇𝑏𝑠的额外强化通过向𝑇𝑏𝑠中的每条边增加𝑒/𝐶𝑏𝑠大小的信息量，𝑒定义了路径权重的大小，𝐶𝑏𝑠代表了𝑇𝑏𝑠的长度𝜏𝑖𝑗←𝜏𝑖𝑗+∆𝜏𝑖𝑗𝑘+𝑒∆𝜏𝑖𝑗𝑏𝑠𝑚𝑘=1∆𝜏𝑖𝑗𝑏𝑠=1𝐶𝑏𝑠，如果边在路径𝑇𝑏𝑠上0，否则使用精华策略并选取适当的𝑒值可以得到更好的解题路径，也能在更少的迭代次数下得到更好的结果基于排列的蚂蚁系统𝐴𝑆𝑟𝑎𝑛𝑘𝐴𝑆𝑟𝑎𝑛𝑘算法中，蚂蚁释放的信息素大小随着蚂蚁在排列中的先后次序逐渐减少，与EAS算法类似，通常至今最优蚂蚁都会在每次迭代中释放更多的信息素。1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用信息素更新规则信息素更新前，蚂蚁的排列次序r由他们构建的路径的长度按递增的顺。而蚂蚁释放的信息素大小的权值有蚂蚁的排列次序r决定。只有排在最前面（𝑤−1）只蚂蚁和生成了至今最优蚂蚁的路径的蚂蚁才允许释放信息素。𝜏𝑖𝑗←𝜏𝑖𝑗+𝑤−𝑟∆𝜏𝑖𝑗𝑟+𝑤∆𝜏𝑖𝑗𝑏𝑠𝑤−1𝑟=1𝐴𝑆𝑟𝑎𝑛𝑘算法稍优于EAS算法类似，明显优于AS最大最小蚂蚁系统最大最小蚂蚁系统（MAX-MINAntSystem，MMAS）在基本AS算法的基础上进行了四项改进：1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用(1)只允许迭代最优蚂蚁（在本次迭代构建出最短路径的蚂蚁），或者至今最优蚂蚁释放信息素。（迭代最优更新规则和至今最优更新规则在MMAS中会被交替使用）如果只使用至今最优更新规则进行信息素的更新，搜索的导向性很强，算法会很快收敛到Tb附近；反之，如果只使用迭代最优更新规则，则算法的探索能力会得到增强，但收敛速度会下降。实验结果表明，对于小规模的TSP问题，仅仅使用迭代最优信息素更新方式即可。随着问题规模的增大，至今最优信息素规则的使用变得越来越重要。(2)信息素量大小的取值范围被限制在一个区间[𝜏𝑚𝑖𝑛,𝜏𝑚𝑎𝑥]内。当信息素浓度也被限制在一个范围内以后，位于城市i的蚂蚁k选择城市j作为下一城市的概率也将被限制在一个区间内。算法有效避免了陷入停滞状态（所有蚂蚁不断重复搜索同一条路径）的可能性。最大最小蚂蚁系统最大最小蚂蚁系统（MAX-MINAntSystem，MMAS）在基本AS算法的基础上进行了四项改进：1.蚁群算法简述2.蚁群算法原理3.蚁群算法改进4.蚁群算法应用(3)信息素初始值为信息素取值区间的上限，并伴随一个较小的信息素蒸发速率。增强算法在初始阶段的探索能力，有助于