蚁群算法

改进的蚁群算法及其应用SA07011068章宗长SA07011065石轲2008-6-23改进的蚁群算法MacroDorigoGambardella带精英策略的蚂蚁系统带精英策略的蚂蚁系统（AntSystemwithelitiststrategy,ASelite）是最早的改进蚂蚁系统遗传算法中的精英策略传统的遗传算法可能会导致最适应个体的遗传信息丢失精英策略的思想是保留住一代中的最适应个体蚂蚁系统中的精英策略每次循环之后给予最优解以额外的信息素量这样的解被称为全局最优解（global-bestsolution）找出这个解的蚂蚁被称为精英蚂蚁(elitistants)带精英策略的蚂蚁系统信息素根据下式进行更新*(1)()ijijijijtt1mkijijk其中,0,kkijQkL如果蚂蚁在本次循环中经过路径(i,j)否则**,0,ijQL如果边(i,j)是所找出的最优解的一部分否则带精英策略的蚂蚁系统上式中表示精英蚂蚁引起的路径(i,j)上的信息素量的增加**L特点：可以使蚂蚁系统找出更优的解找到这些解的时间更短精英蚂蚁过多会导致搜索早熟收敛是精英蚂蚁的个数是所找出的最优解的路径长度蚁群系统蚁群系统(AntColonySystem,ACS)是由Dorigo和Gambardella在1996年提出的蚁群系统做了三个方面的改进：状态转移规则为更好更合理地利用新路径和利用关于问题的先验知识提供了方法全局更新规则只应用于最优的蚂蚁路径上在建立问题解决方案的过程中，应用局部信息素更新规则蚁群系统状态转移规则一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市s0argmax{[(,)][(,)]},,kuallowedruruqqsS如果按先验知识选择路径否则其中，S根据下列公式得到()(),()()()0,kijijkkisisijsallowedttjallowedttPtotherwise蚁群系统状态转移规则q是在[0,1]区间均匀分布的随机数q0的大小决定了利用先验知识与探索新路径之间的相对重要性。上述状态转移规则被称为伪随机比例规则特点：倾向于选择短的且有着大量信息素的边作为移动方向蚁群系统全局更新规则只有全局最优的蚂蚁才被允许释放信息素目的：使蚂蚁的搜索主要集中在当前循环为止所找出的最好路径的领域内全局更新在所有蚂蚁都完成它们的路径之后执行，使用下式对所建立的路径进行更新(,)(1)(,)(,)rsrsrs1,(,)0,gbLrs如果(r,s)全局最优路径否则蚁群系统全局更新规则为信息素挥发参数，01为到目前为止找出的全局最优路径gbL全局更新规则的另一个类型称为迭代最优区别:使用代替，为当前迭代(循环)中的最优路径长度这两种类型对蚁群系统性能的影响差别很小，全局最优的性能要稍微好一些gbLibLibL蚁群系统局部更新规则类似于蚁密和蚁量模型中的更新规则蚂蚁应用下列局部更新规则对它们所经过的边进行激素更新(,)(1)(,)(,)01rsrsrs其中,为一个参数,01nnnL实验发现，可以产生好的结果，其中n是城市的数量，是由最近的邻域启发产生的一个路径长度nnL局部更新规则可以有效地避免蚂蚁收敛到同一路径最大-最小蚂蚁系统蚁群算法将蚂蚁的搜索行为集中到最优解的附近可以提高解的质量和收敛速度，从而改进算法的性能。但这种搜索方式会使早熟收敛行为更容易发生最大-最小蚂蚁系统(Max-MinAntSystem,MMAS)能将这种搜索方式和一种能够有效避免早熟收敛的机制结合在一起，从而使算法获得最优的性能最大-最小蚂蚁系统MMAS和AS主要有三个方面不同：为了充分利用循环最优解和到目前为止找出的最优解，在每次循环之后，只有一只蚂蚁进行信息素更新。这只蚂蚁可能是找出当前循环中最优解的蚂蚁，也可能是找出从实验开始以来最优解的蚂蚁为避免搜索的停滞，在每个解的元素上的的信息素轨迹量的值域范围被限制在区间内将信息素轨迹初始化为maxminmax[,]信息素轨迹更新在MMAS中，只有一只蚂蚁用于在每次循环后更新信息轨迹经修改的轨迹更新规则如下：(1)()ijbestijijtt1()ijbestbestfs表示迭代最优解或全局最优解的值在蚁群算法中主要使用全局最优解，而在MMAS中则主要使用迭代最优解()bestfs信息素轨迹的限制不管是选择迭代最优还是全局最优蚂蚁来进行信息素更新，都可能导致搜索的停滞。停滞现象发生的原因：在每个选择点上一个选择的信息素轨迹量明显高于其他的选择。避免停滞状态发生的方法：影响用来选择下一解元素的概率，它直接依赖于信息素轨迹和启发信息。通过限制信息素轨迹的影响，可以很容易地避免各信息素轨迹之间的差异过大。信息素轨迹的限制MMAS对信息素轨迹的最小值和最大值分别施加了和的限制，从而使得对所有信息素轨迹，有minmax()ijtminmax()ijtMMAS收敛：在每个选择点上，其中一个解元素上的轨迹量为，而所有其他可选择的解元素上的轨迹量为。minmax若MMAS收敛，通过始终选择信息素量最大的解元素所构造的解将与算法找出的最优解相一致信息素轨迹的限制的选取maxmax11()()ijttioptitfsopt其中,f(s)为对于一个具体问题的最优解gbopt渐进的最大值估计通过使用f(s)代替f(s)来实现的选取要基于两点假设最优解在搜索停滞发生之前不久被找出对解构造的主要影响是由信息素轨迹的上限与下限之间的相对差异决定min信息素轨迹的限制在一个选择点上选择相应解元素的概率Pdec直接取决于和minmax在每个选择点上蚂蚁需在avg=n/2个解元素中选择maxmaxmin(1)decPavg蚂蚁构造最优解，需作n次正确的决策decnbestPPmaxmaxmin(1)(1)(1)(1)nbestdecndecbestPPavgPavgP信息素轨迹的初始化在第一次循环后所有信息素轨迹与相一致max(1)通过选择对这种类型的轨迹初始化来增加在算法的第一次循环期间对新解的探索当将信息素轨迹初始化为时，选择概率将增加得更加缓慢实验表明，将初始值设为可以改善最大-最小蚂蚁系统的性能maxmax(1)信息素轨迹的平滑化基本思想：通过增加选择有着低强度信息素轨迹量解元素的概率以提高探索新解的能力*max()()(()())ijijijtttt*()()ijijtt其中,01,和分别为平滑化之前和之后的信息素轨迹量平滑机制有助于对搜索空间进行更有效的探索蚁群算法的应用混流装配线调度混流装配线(sequencingmixedmodelsonanassemblyline,SMMAL)是指一定时间内，在一条生产线上生产出多种不同型号的产品，产品的品种可以随顾客需求的变化而变化。SMMAL是车间作业调度问题(job-shopschedulingproblem,JSP)的具体应用之一。问题描述以汽车组装为例，即在组装所有车辆的过程中，所确定的组装顺序应使各零部件的使用速率均匀化。如果不同型号的汽车消耗零部件的种类大致相同，那么原问题可简化为单级SMMAL调度问题。21,111min()Dnmpipjpjijipjbx1,0,jiijx如果车型在调度中的位置否则iipipdbD问题描述i表示车型数的标号n表示需要装配的车型数m表示装配线上需要的零部件种类总数p表示生产调度中子装配的标号表示零部件p的理想使用速率j表示车型调度结果(即排序位置)的标号D表示在一个生产循环中需要组装的各种车型的总和p问题描述di表示在一个生产循环中车型i的数量bip表示生产每辆i车型需要零部件p的数量表示在组装线调度中前j-1台车消耗零部件p的数量和1,0,,0jpjpjiippxb且1,jp蚁群算法在SMMAL中的应用假设有3种车型A、B、C排序，每个生产循环需A型车3辆，B型车2辆，C型车1辆，则每个循环共需生产6辆车。采用下图的搜索空间定义，列表示6个排序阶段，行表示有3种车型可以选择。蚁群算法就是不断改变圆圈的大小，最终寻找到满意的可行解。搜索的初始状态简单SMMAL排序的搜索空间举例经过若干次迭代之后，搜索空间变化，此时最可能的可行解为B-A-C-A-B-A若干次迭代后的状态局部搜索()的计算ij21,1()ijmpipkppQjb局部搜索采用的是贪心策略ij基本思路：每一步均从当前可选择策略中选取，使目标函数值增加最少的策略，即在确定第j个位置组装的车型时，如果有多种车型可供选择，则从中选择一种车型i，使第j个位置组装车型i时各零部件的使用速率最为均匀。状态转移概率状态转移概率公式如下(1),(1)()0,kijijkkijijijjtabuitabupt若否则信息素更新规则LB表示目标函数的下限值表示当前目标函数的平均值Zcutr表示当前的目标函数值这种动态标记的方法可在搜索过程中加大可行解间信息素的差别，避免算法早熟Z0(1),0,cutrkijZLBijZLB如果车型在调度中的位置否则_1nantkijijk()(1)()ijijijtnt实验数据实验参数设置蚂蚁系统蚂蚁数量N_ant=5最大循环周期Ncmax=400=0.2Q=20000=0.9LB=0.0蚁群系统q0=0.5全局更新规则中的和局部更新规则中的均取0.1实验参数设置最大-最小蚂蚁系统选取全局最优解()bestfsmin0max00,1,LDL是利用贪心策略算得的目标函数值带有精英策略的蚂蚁系统精英蚂蚁数量:1只实验结果实验结果分析直接用贪心策略求解结果：3293.4375蚂蚁系统求解SMMAL问题的性能较差对于这个具体的问题，带精英策略的蚂蚁系统的求解性能并不好于蚂蚁系统蚁群系统的性能相对于前两者而言，有了很大幅度的提高最大-最小蚂蚁系统的性能最好，大多数情况下的求解结果已达到实际的最优解实验界面实验界面蚁群系统在TSP问题中的应用10城市TSP问题20城市TSP问题蚁群系统在TSP问题中的应用30城市TSP问题48城市TSP问题Questions?