蚁群算法及算例

蚁群优化算法（ACO算法）一、概述二、蚂蚁系统（AS）三、算例四、改进的ACO算法一、概述（一）算法背景——蚁群的自组织行为特征1、高度结构化的组织——虽然蚂蚁的个体行为极其简单，但由个体组成的蚁群却构成高度结构化的社会组织，蚂蚁社会的成员有分工，有相互的通信和信息传递。2、自然优化——蚁群在觅食过程中，在没有任何提示下总能找到从蚁巢到食物源之间的最短路径；当经过的路线上出现障碍物时，还能迅速找到新的最优路径。3、信息正反馈——蚂蚁在寻找食物时，在其经过的路径上释放信息素（外激素）。蚂蚁基本没有视觉，但能在小范围内察觉同类散发的信息素的轨迹，由此来决定何去何从，并倾向于朝着信息素强度高的方向移动。4、自催化行为——某条路径上走过的蚂蚁越多，留下的信息素也越多（随时间蒸发一部分），后来蚂蚁选择该路径的概率也越高。（二）算法的产生与发展1、产生——受蚁群觅食行为启发，意大利学者M.Dorigo于1991年在其博士论文中首次系统地提出一种基于蚂蚁种群的新型智能优化算法“蚂蚁系统（Antsystem,简称AS）”，并用该法求解旅行商问题，获得了较好的效果。2、发展——后来，提出者及许多研究者对该算法作了各种改进，将其应用于更为广泛的领域，如图着色问题、二次分配问题、工件排序问题、车辆路径问题、车间作业调度问题、网络路由问题、大规模集成电路设计等。近些年来，M.Dorigo等人把蚂蚁算法进一步发展成一种通用的优化技术“蚁群优化（AntColonyOptimization,简称ACO）”，并将所有符合ACO框架的算法称为“蚁群优化算法（ACOalgorithm）”。3、展望——初步的研究结果已显示出ACO算法在求解复杂优化问题，特别是离散优化问题方面的优越性。虽然严格的理论基础尚未奠定，但从当前的应用效果来看，此算法具有光明的发展前景。（三）特点◆是一种基于多主体的智能算法，不是单个蚂蚁行动，而是多个蚂蚁同时搜索，具有分布式的协同优化机制。◆本质上属于随机搜索算法（概率算法），具有概率搜索的特征。◆是一种全局搜索算法，能够有效地避免局部最优。（四）优点◆求解问题的快速性——由正反馈机制决定；◆全局优化性——由分布式计算决定，避免蚁群在寻优空间中过早收敛；◆有限时间内答案的合理性——由贪婪式搜索模式决定，使能在搜索过程的早期就找到可以接受的较好解。二、蚂蚁系统（AS算法）——最早的ACO算法（一）算法基本思想（以旅行商为例说明）1、根据具体问题设置多只蚂蚁，分头并行搜索。2、每只蚂蚁完成一次周游后，在行进的路上释放信息素，信息素量与解的质量成正比。3、蚂蚁路径的选择根据信息素强度大小（初始信息素量设为相等），同时考虑两点之间的距离，采用随机的局部搜索策略。这使得距离较短的边，其上的信息素量较大，后来的蚂蚁选择该边的概率也较大。4、每只蚂蚁只能走合法路线（经过每个城市1次且仅1次），为此设置禁忌表来控制。5、所有蚂蚁都搜索完一次就是迭代一次，每迭代一次就对所有的边做一次信息素更新，原来的蚂蚁死掉，新的蚂蚁进行新一轮搜索。6、更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。7、达到预定的迭代步数，或出现停滞现象（所有蚂蚁都选择同样的路径，解不再变化），则算法结束，以当前最优解作为问题的最优解。（二）参数含义及符号mktnijdji,——蚂蚁数量；——蚂蚁编号；——时刻；——城市数；——城市之间的距离；ijij——启发式因子（能见度），反映蚂蚁由城市转移到城市的启发程度；ij——边上的信息素量；ji,kijk——第只蚂蚁在本次迭代中留在边上的信息素量；ji,——信息素蒸发（或挥发）系数，110——持久性（或残留）系数，；)(tPkijtkij——时刻蚂蚁由城市转移到城市的概率（转移概率）；ij——本次迭代边上的信息素增量；ji,ktabuk——蚂蚁的禁忌表。（三）计算公式1、转移概率计算公式：tpkij否则如果,iJj,tηtτtηtτtpkiJsβisαisβijαijkijk0iJk——蚂蚁下一步允许选择的城市集合。——信息素的相对重要程度；——启发式因子的相对重要程度；kijijd12、启发式因子计算公式：3、信息素计算公式ijijijtnt)()1()(mkkijijΔτ1否则在本次周游中经过边若蚂蚁,0),(,jikLQkkijQ——正常数，kLk——蚂蚁在本次周游中所走路径的长度。当所有蚂蚁完成1次周游后，各路径上的信息素为：Cij0开始时，令（四）算法步骤Cij)0(0)0(ij1、初始化参数：开始时每条边的信息素量都相等。2、将各只蚂蚁放置各顶点，禁忌表为对应的顶点。3、取1只蚂蚁，计算转移概率，按轮盘赌的方式选择下一个顶点，更新禁忌表，再计算概率，再选择顶点，再更新禁忌表，直至遍历所有顶点1次。)(tPkij4、计算该只蚂蚁留在各边的信息素量，该蚂蚁死去。kij5、重复3~4，直至只蚂蚁都周游完毕。mij)(ntij6、计算各边的信息素增量和信息素量。7、记录本次迭代的路径，更新当前的最优路径，清空禁忌表。8、判断是否达到预定的迭代步数，或者是否出现停滞现象。若是，算法结束，输出当前最优路径；否，转2，进行下一次迭代。优点较强的鲁棒性——稍加修改即可应用于其他问题。（鲁棒性就是系统的健壮性，用以表征控制系统对特性或参数摄动的不敏感性。）分布式计算——本质上具有并行性。易于与其他启发式算法结合。不足一般需要较长的搜索时间。容易出现停滞现象。（六）AS算法的优点与不足三、算例——5个点的货郎担问题nm1,15.020100ijQ参数设置：▲最优解保留策略蚂蚁系统（带精英策略的蚂蚁系统ASelite）▲蚁群系统（ACS）▲最大-最小蚂蚁系统（MMAS）▲基于优化排序的蚂蚁系统（ASrank）▲最优最差蚂蚁系统（BWAS）▲一种新的自适应蚁群算法（AACA）▲基于混合行为的蚁群算法（HBACA）改进的蚂蚁算法四、改进的蚁群优化算法（一）带精英策略的蚂蚁系统eliteAS特点——在信息素更新时给予当前最优解以额外的信息素量，使最优解得到更好的利用。找到全局最优解的蚂蚁称为“精英蚂蚁”。ijijijijtnt1否则是当前最优解的一部分若边,0,ΔijLQτgbijijτΔgbL——精英蚂蚁在边上增加的信息素量；ij——精英蚂蚁个数；——当前全局最优解路径长度。特点１、状态转移规则——伪随机比率规则)1,0(0q)1,0(q0qq设为常数，为随机数，如果，则蚂蚁转移的下一座城市是使取最大值的城市；若，仍按转移概率确定。βijαijtηtτ)]([)]([0qq２、全局更新规则——只有精英蚂蚁才允许释放信息素，即只有全局最优解所属的边才增加信息素。３、局部更新规则——蚂蚁每次从城市转移到城市后，边上的信息素适当减少。ijji,0q一般，取值较大。（二）蚁群系统ACS规则１和２都是为了使搜索过程更具有指导性，即使蚂蚁的搜索主要集中在当前找出的最好解邻域内。规则３则是为了使已选的边对后来的蚂蚁具有较小的影响力，以避免蚂蚁收敛到同一路径。（三）最大最小蚂蚁系统MMASmaxmin,关于的取值，没有确定的方法，有的书例子中取为0.01，10；有的书提出一个在最大值给定的情况下计算最小值的公式。1、每次迭代后，只对最优解所属路径上的信息素更新。特点2、对每条边的信息素量限制在范围内，目的是防止某一条路径上的信息素量远大于其余路径，避免过早收敛于局部最优解。maxmin,（四）基于优化排序的蚂蚁系统rankAS特点：每次迭代完成后，蚂蚁所经路径由小到大排序，并根据路径长度赋予不同的权重，路径越短权重越大。信息素更新时对考虑权重的影响。kij特点：主要是修改了ACS中的全局更新公式，增加对最差蚂蚁路径信息素的更新，对最差解进行削弱，使信息素差异进一步增大。（五）最优最差蚂蚁系统BWAS（六）一种新的自适应蚁群算法AACA特点：将ACS中的状态转移规则改为自适应伪随机比率规则，动态调整转移概率，以避免出现停滞现象。说明：在ACS的状态转移公式中，是给定的常数；在AACA中，是随平均节点分支数ANB而变化的变量。ANB较大，意味着下一步可选的城市较多，也变大，表示选择信息素和距离最好的边的可能性增大；反之减小。0q0q0q（七）基于混合行为的蚁群算法HBACA特点：按蚂蚁的行为特征将蚂蚁分成4类，称为4个子蚁群，各子蚁群按各自的转移规则行动，搜索路径，每迭代一次，更新当前最优解，按最优路径长度更新各条边上的信息素，如此直至算法结束。蚂蚁行为——蚂蚁在前进过程中，用以决定其下一步移动到哪个状态的规则集合。1、蚂蚁以随机方式选择下一步要到达的状态。2、蚂蚁以贪婪方式选择下一步要到达的状态。3、蚂蚁按信息素强度选择下一步要到达的状态。4、蚂蚁按信息素强度和城市间距离选择下一步要到达的状态。蚂蚁行为五、蚁群算法与遗传、模拟退火算法的比较实验结果表明：1、蚁群算法所找出的解的质量最高，遗传算法次之，模拟退火算法最低。2、蚁群算法的收敛速度最快，遗传算法次之，模拟退火算法最慢。蚁群算法之所以能够快速收敛到全局最优解，是因为该算法的个体之间不断进行信息交流和传递。单个个体容易收敛于局部最优，多个个体通过合作可以很快地收敛于解空间的最优解的附近。讨论1、对已学过的算法作出某种改进。2、介绍自学的一种新的算法。3、查阅文献，介绍某算法在某领域的一个应用。4、应用某算法解决一个实际问题。已知资料表ABCDEA021083B10257C91036D104302E27510EABCD参数设置：2)0(100,,5.0,1,1,5ijQm否则如果,iJj,YXtηtτtηtτtpkiJsβisαisβijαijkijk0算例ijijd1ijijijtnt)()1()(mkkijijΔτ1否则在本次周游中经过边若蚂蚁,0),(,jikLQkkijQ——正常数，kLk——蚂蚁在本次周游中所走路径的长度。当所有蚂蚁完成1次周游后，各路径上的信息素为：Cij0开始时，令ktitabuk10AABCDE22220.470.0950.1180.315119.12.117BA,BCDE2220.5930.2370.1691.686CA,B,CDE220.670.331.0DA,B,C,DE21.01.0EA,B,C,D,E空集--)(tijkij)(tpkij)(iJkkLYktitabuk20BBACDE22220.540.270.110.08911.13.686AB,ACDE2220.180.220.601.117EB,A,ECD220.170.832.4DB,A,E,DC21.00.667CB,A,E,D,C空集--)(tijkij)(tpkij)(iJkkLYktitabuk30CCABDE22220.0690.620.2070.103911.13.222BC,BADE2220.7450.1490.1062.686AC,B,ADE220.2730.7270.917EC,B,A,ED21.02.0DC,B,A,E,D空集--)(tijkij)(tpkij)(iJkkLYktitabuk40DDABCE22220.0840.2110.2870.422119.12.367ED,EABC2220.5930.1690.2371.686AD,E,ABC220.830.171.2BD,E,A,BC21.01.0CD,E,A,B,C空集--)(tijkij)(tpkij)(iJkkLYktitabu