蚁群优化算法

2020/4/24copyright:hhq蚁群优化算法概述2020/4/24copyright:hhq内容基本概念及原理1数学模型与算法流程2研究现状及进展3算法优缺点及应用42020/4/24copyright:hhq基本概念蚁群优化算法（AntColonyOptimization,ACO）是一种针对难解的离散优化问题的元启发式算法，利用一群人工蚂蚁的协作来寻找好的解。既适用于静态组合优化问题，又适用于动态组合优化问题。前者如旅行商问题（TSP），后者如通讯领域的路由问题等。启发式算法（HeuristicAlgorithm）在可接受的花费（指时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定能事先预计，也不能保证每次能用相同的时间求出结果。2020/4/24copyright:hhq有趣的问题1.为何大多数蚂蚁在觅食时，会选择相同的路径，而且这条路径往往是一条食物和巢穴之间的最短路径，它们是如何做到的？2.当原来最优路径上出现了障碍物或者食物位置改变了；蚁群仍能够重新探索出新的一条最优路径？2020/4/24copyright:hhq蚁群行为描述仿生学家经过长期研究发现：蚂蚁虽然没有视觉，但是存在一种化学物质—信息素（pheromone）用于蚂蚁之间以及蚂蚁与环境的交互。在没有信息素的情况下，蚂蚁是随机挑选路径的，同时释放出与路径有关的信息素。路径越长，信息素量越小。如果当前路径上存在信息素，蚂蚁倾向于信息素浓度高的路径。由于较短路径上，蚂蚁往返的时间短，单位时间内经过的蚂蚁数多，信息素累计的也多，因此会吸引更多的蚂蚁。信息素还会随着时间蒸发，其他路径上的信息素浓度下降，最终绝大多数的蚂蚁将沿着最优路径前行。2020/4/24copyright:hhq蚂蚁行为图解食物该走那条路呢？我走我自己的路这条路好远，少产生信息素这条路好近，多产生点信息素跟着信息素多的准没错图1蚁群觅食行为图2020/4/24copyright:hhq蚁群优化算法起源蚁群觅食现象蚁群优化算法蚁群种群(求解主体)规模m觅食空间问题的搜索空间n信息素信息素浓度变量蚁穴到食物的路径一个有效解最短路径问题的最优解表1蚁群觅食现象和蚁群优化算法定义对照表2020/4/24copyright:hhq蚁群优化算法机制原理蚁群优化的本质在于：选择机制：信息素越多的路径，被选择的概率越大。更新机制：路径上面的信息素会随蚂蚁的经过而增长，同时也随时间的推移逐渐挥发消失。协调机制：蚂蚁间通过环境中的信息素来协同工作。蚁群算法的寻优包含两个基本过程：蚂蚁构建解（ConstructAntSolution）通过使一群蚂蚁并行异步访问邻近点，逐步建立优化问题的解。更新信息素（UpdatePheromones）依据蚂蚁所构建的解修改空间内的信息素浓度。2020/4/24copyright:hhq蚂蚁系统解决TSP问题蚂蚁系统（AntSystem）作为第一个ACO算法，是以NP-hard的TSP问题作为应用实例而提出的。虽然它的算法性能不及其他各种扩展算法，但是最基本的ACO算法，易于学习和掌握。旅行商问题一位商人从自家出发，希望能找到一条最短路径，途径给定集合的所有城市最后返回家乡，并且每个城市都被访问且仅访问一次。形式上，TSP问题可以用一个带权完全图G=（N,A）来描述，目标就是寻找一条具有最小成本值的哈密尔顿回路。2020/4/24copyright:hhqTSP问题数学描述设是n个城市的集合，是集合C中元素两两连接的集合，是的距离，对任意i，j有称为对称旅行商问题，若存在某组i，j之间的则称为非对称旅行商问题。目标函数表示为对于n个城市规模的TSP，存在条不同的闭合路径，当n较大时很难精确求解每个解再寻找最优。}c,...,c,{cCn21C}c,c|{lLjiij),...,2,1,(njidijijljiijddjiijdd}min{)()1()()1(i)(11ππππniddfni2)!1(n2020/4/24copyright:hhq蚂蚁系统数学模型（一）设n表示TSP规模，i和j是集合C中的两个元素，m为蚁群蚂蚁总数，表示t时刻位于i的蚂蚁数目，则设为t时刻路径(i,j)上的信息素量，是t时刻集合C中所有信息素的集合。初始时刻，各条路径上的信息量是相同的。)(tbiniitbm1)()(tij},|)({Ccctjiij2020/4/24copyright:hhq蚂蚁系统数学模型（二）蚂蚁在运动过程中有三个因素决定其转移方向信息素量，启发式信息和禁忌表为启发函数，其表达式一般表示为；禁忌表用于记录蚂蚁k当前走过的城市，表示蚂蚁k下步允许选择的城市。),...,2,1(mkk)(tij)(tijktabuijijdt1)()(tijktabu}{kktabuCallowed2020/4/24copyright:hhq蚂蚁系统数学模型（三）表示蚂蚁k在t时刻由i转到j的概率上式中，α为信息素因子，β为启发式因子，用于控制信息素浓度和启发式信息作用的权重关系。值越大表示重要性越大，当α=0，算法演变为传统的随机贪心算法，当β=0，蚂蚁仅依据信息素决策，算法将快速收敛，可能获得局部最优。)(tpkijotherwiseallowedjiftttttpkallowedsisisijijkijkk,0,)]([)]([)]([)]([)(2020/4/24copyright:hhq蚂蚁系统数学模型（四）信息素更新公式1.原有信息素的挥发通常的做法是设置信息持久率让所有乘以。在算法中用于避免信息素的无限增长淹没启发式信息，也有助于丢弃那些构建过的较差的路径。2.新生信息素的释放AS算法曾有过三种信息素释放策略Ant-Density模型：若蚂蚁k在t到t+1之间经过(i,j)Ant-Quantity模型：若蚂蚁k在t到t+1之间经过(i,j)Ant-Cycle模型：若蚂蚁k在本次循环中经过(i,j))10()(tijQkijmkkijijijijijtnt1;)()(ijkijdQkkijLQ2020/4/24copyright:hhq蚂蚁系统解决TSP步骤⑴初始化随机放置蚂蚁，为每只蚂蚁建立禁忌表，⑵迭代过程k=1whilek=Countdo(执行迭代)fori=1tomdo(对m只蚂蚁循环)forj=1ton-1do(对n个城市循环)根据蚂蚁行动原则选择下一个城市j并将j置入禁忌表,endforendfor计算每只蚂蚁的路径长度依据信息素更新方法更新所有路径上的信息量;k=k+1;endwhile⑶输出结果,结束算法.2020/4/24copyright:hhq蚂蚁系统解决TSP算法流程开始初始化（蚁群，信息素量）迭代次数加1挑选一只蚂蚁根据概率公式选择下一元素修改禁忌表k达到总数m根据公式修改信息量满足结束条件结束输出结果NYYN2020/4/24copyright:hhq算法复杂度分析步骤内容时间复杂度1初始化参数2设置禁忌表3每只蚂蚁构造解4解的评价5信息素浓度更新6判断终止条件7输出结果2()Onm()Om2()Onm2()Onm2()On()Omn(1)O空间复杂度：2()()()SnOnOnm2020/4/24copyright:hhq研究现状AS是第一个ACO算法由Dorigo等人于1991年在第一届欧洲人工生命会议上提出。1996年，Dorigo发表Antsystem:optimizationbyacolonyofcooperationagents,成为里程碑。随后，精英蚂蚁系统、最大最小蚂蚁系统和基于排列的蚂蚁系统大多在AS上直接改进。1997年，Dorigo提出了大幅改动AS特征的算法—蚁群系统(AntColonySystem，ACS)性能明显优于AS。21世纪出现了连续蚁群算法，能够优化连续空间问题。2020/4/24copyright:hhq精英蚂蚁系统精英蚂蚁系统（EAS）是最早的改进蚂蚁系统。遗传算法中的精英策略传统的遗传算法可能会导致最适应个体的遗传信息丢失精英策略的思想是保留住一代中的最适应个体蚂蚁系统中的精英策略每次循环之后给予最优解以额外的信息素量这样的解被称为全局最优解（global-bestsolution）找出这个解的蚂蚁被称为精英蚂蚁(elitistants)2020/4/24copyright:hhq精英蚂蚁系统信息素根据下式进行更新*(1)()ijijijijtt**,0,ijQL如果边(i,j)是所找出的最优解的一部分否则是精英蚂蚁的个数是所找出的最优解的路径长度精英蚂蚁系统特点：更高的求解精度，更快的求解速度，但精英蚂蚁设置太多会加速早熟。*L2020/4/24copyright:hhq基于排列的蚂蚁系统基于排列蚂蚁系统(ASrank)由Bullnheimer于1997年提出。基本思想与EAS类似，具体做法是在每一轮所有蚂蚁构建完路径后，将各自所得的路径进行排名，只有生成了至今最优路径的蚂蚁以及排名在前(ω-1)的蚂蚁才允许释放信息素。最优蚂蚁释放的信息素量，在本次迭代中排名的蚂蚁将释放的信息素。一般设置ω=6。bL/)1,...,2,1(kkkLk/)(2020/4/24copyright:hhq最大最小蚂蚁系统前两种改进算法将蚂蚁的搜索行为偏向当前最优解虽然提高解的质量和收敛速度，进而改进算法的性能。但这种搜索方式无法避免早熟收敛问题。最大-最小蚂蚁系统(Max-MinAntSystem,MMAS)于1997年由Stützle提出。这种算法将之前的搜索方式和一种能够有效避免早熟收敛的机制结合在一起，从而使其获得更好的全局搜索能力。2020/4/24copyright:hhq最大最小蚂蚁系统MMAS和AS主要有四个方面不同：在每次循环之后，只有一只蚂蚁进行信息素更新。这只蚂蚁可能是找出当前循环中最优解的蚂蚁，也可能是找出从实验开始以来最优解的蚂蚁在每个解的元素上的的信息素量被限制在范围区间内信息素初始值为信息素取值范围的上限，信息维持率保持一个较大值。当系统陷入停滞，将问题空间所有边的信息素重新初始化。maxminmax[,]2020/4/24copyright:hhq最大最小蚂蚁系统改进1借鉴了EAS，但有不同。使用至今最优的蚂蚁释放可加快收敛，当前迭代最优可增强探索，应该交替使用，逐渐增大至今最优蚂蚁的使用概率。改进2通过给信息素设定上界目的是避免信息素增长过快，淹没了启发式信息的影响。启发式信息在每次迭代中是无法增长的。改进3设置较大的信息素维持度（一般设置为0.98）可以保证初始阶段的探索能力。改进4可以利用停滞后的迭代周期继续进行搜索。2020/4/24copyright:hhq蚁群系统蚁群系统(AntColonySystem,ACS)是由Dorigo和Gambardella在1997年提出的。蚁群系统做了三个方面的改进：使用一种伪随机比例规则选择下一元素j，利用了先验知识。信息素全局更新规则将只应用于至今最优蚂蚁路径。新增信息素局部信息素更新规则。2020/4/24copyright:hhq蚁群系统状态转移规则一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市J0argmax{[]},,kililjallowedqqjJ如果否则是一个[0,1]区间的参数，是一个[0,1]区间的随机数，当蚂蚁选择开发当前最优路径；当蚂蚁进行偏向选择，探索其他区域通过调节值可以平衡开发和探索的关系。0q0qq0qq0qq2020/4/24copyright:hhq蚁群系统全局更新规则只有一只至今最优的蚂蚁（大