蚁群优化算法.pptx

《蚁群优化算法.pptx》由会员分享，可在线阅读，更多相关《蚁群优化算法.pptx（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/2/23内容基本概念及原理基本概念及原理1 数学模型与算法流程数学模型与算法流程2研究现状及进展研究现状及进展3 算法优缺点及应用算法优缺点及应用4第1页/共33页2023/2/23基本概念蚁群优化算法（Ant Colony Optimization,ACO）是一种针对难解的离散优化问题的元启发式算法，利用一群人工蚂蚁的协作来寻找好的解。既适用于静态组合优化问题，又适用于动态组合优化问题。前者如旅行商问题（TSP），后者如通讯领域的路由问题等。启发式算法（Heuristic Algorithm）在可接受的花费（指时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最

2、优解的偏离程度不一定能事先预计，也不能保证每次能用相同的时间求出结果。第2页/共33页2023/2/23有趣的问题1.为何大多数蚂蚁在觅食时，会选择相同的路径，而且这条路径往往是一条食物和巢穴之间的最短路径，它们是如何做到的？2.当原来最优路径上出现了障碍物或者食物位置改变了；蚁群仍能够重新探索出新的一条最优路径？第3页/共33页2023/2/23蚁群行为描述仿生学家经过长期研究发现：蚂蚁虽然没有视觉，但是存在一种化学物质信息素（pheromone）用于蚂蚁之间以及蚂蚁与环境的交互。在没有信息素的情况下，蚂蚁是随机挑选路径的，同时释放出与路径有关的信息素。路径越长，信息素量越小。如果当前路径上

3、存在信息素，蚂蚁倾向于信息素浓度高的路径。由于较短路径上，蚂蚁往返的时间短，单位时间内经过的蚂蚁数多，信息素累计的也多，因此会吸引更多的蚂蚁。信息素还会随着时间蒸发，其他路径上的信息素浓度下降，最终绝大多数的蚂蚁将沿着最优路径前行。第4页/共33页2023/2/23蚂蚁行为图解图1 蚁群觅食行为图第5页/共33页2023/2/23蚁群优化算法起源表1 蚁群觅食现象和蚁群优化算法定义对照表第6页/共33页2023/2/23蚁群优化算法机制原理蚁群优化的本质在于：选择机制：信息素越多的路径，被选择的概率越大。更新机制：路径上面的信息素会随蚂蚁的经过而增长，同 时也随时间的推移逐渐挥发消失。协调机制

4、：蚂蚁间通过环境中的信息素来协同工作。蚁群算法的寻优包含两个基本过程：蚂蚁构建解（ConstructAntSolution）通过使一群蚂蚁并行异步访问邻近点，逐步建立优化问题的解。更新信息素（UpdatePheromones）依据蚂蚁所构建的解修改空间内的信息素浓度。第7页/共33页2023/2/23蚂蚁系统解决TSP问题蚂蚁系统（Ant System）作为第一个ACO算法，是以NP-hard的TSP问题作为应用实例而提出的。虽然它的算法性能不及其他各种扩展算法，但是最基本的ACO算法，易于学习和掌握。旅行商问题一位商人从自家出发，希望能找到一条最短路径，途径给定集合的所有城市最后返回家乡，并

5、且每个城市都被访问且仅访问一次。形式上，TSP问题可以用一个带权完全图G=（N,A）来描述，目标就是寻找一条具有最小成本值的哈密尔顿回路。第8页/共33页2023/2/23TSP问题数学描述设 是n个城市的集合，是集合C中元素两两连接的集合，是 的距离，对任意i，j有称为对称旅行商问题，若存在某组i，j之间的则称为非对称旅行商问题。目标函数表示为对于n个城市规模的TSP，存在 条不同的闭合路径，当n较大时很难精确求解每个解再寻找最优。第9页/共33页2023/2/23蚂蚁系统数学模型（一）设n表示TSP规模，i和j是集合C中的两个元素，m为蚁群蚂蚁总数，表示t时刻位于i的蚂蚁数目，则设 为t时

6、刻路径(i,j)上的信息素量，是t时刻集合C中所有信息素的集合。初始时刻，各条路径上的信息量是相同的。第10页/共33页2023/2/23蚂蚁系统数学模型（二）蚂蚁 在运动过程中有三个因素决定其转移方向信息素量 ，启发式信息 和禁忌表 为启发函数，其表达式一般表示为 ；禁忌表 用于记录蚂蚁k当前走过的城市，表示蚂蚁k下步允许选择的城市。第11页/共33页2023/2/23蚂蚁系统数学模型（三）表示蚂蚁k在t时刻由i转到j的概率 上式中，为信息素因子，为启发式因子，用于控制信息素浓度和启发式信息作用的权重关系。值越大表示重要性越大，当=0，算法演变为传统的随机贪心算法，当=0，蚂蚁仅依据信息素决

7、策，算法将快速收敛，可能获得局部最优。第12页/共33页2023/2/23蚂蚁系统数学模型（四）信息素更新公式 1.原有信息素的挥发 通常的做法是设置信息持久率让所有 乘以 。在算法中用于避免信息素的无限增长淹没启发式信息，也有助于丢弃那些构建过的较差的路径。2.新生信息素的释放 AS算法曾有过三种信息素释放策略Ant-Density模型：若蚂蚁k在t到t+1之间经过(i,j)Ant-Quantity模型：若蚂蚁k在t到t+1之间经过(i,j)Ant-Cycle模型：若蚂蚁k在本次循环中经过(i,j)第13页/共33页2023/2/23蚂蚁系统解决TSP步骤初始化随机放置蚂蚁，为每只蚂蚁建立禁

8、忌表，迭代过程k=1while k=Count do(执行迭代)for i=1 to m do (对m只蚂蚁循环)for j=1 to n-1 do (对n个城市循环)根据蚂蚁行动原则 选择下一个城市j并将j置入禁忌表,end for end for 计算每只蚂蚁的路径长度 依据信息素更新方法更新所有路径上的信息量;k=k+1;end while输出结果,结束算法.第14页/共33页2023/2/23蚂蚁系统解决TSP算法流程第15页/共33页2023/2/23算法复杂度分析空间复杂度：第16页/共33页2023/2/23研究现状AS是第一个ACO算法由Dorigo等人于1991年在第一届欧洲

9、人工生命会议上提出。1996年，Dorigo发表Ant system:optimization by a colony of cooperation agents,成为里程碑。随后，精英蚂蚁系统、最大最小蚂蚁系统和基于排列的蚂蚁系统大多在AS上直接改进。1997年，Dorigo提出了大幅改动AS特征的算法蚁群系统(Ant Colony System，ACS)性能明显优于AS。21世纪出现了连续蚁群算法，能够优化连续空间问题。第17页/共33页2023/2/23精英蚂蚁系统精英蚂蚁系统（EAS）是最早的改进蚂蚁系统。o遗传算法中的精英策略n传统的遗传算法可能会导致最适应个体的遗传信息丢失n精英策

10、略的思想是保留住一代中的最适应个体o蚂蚁系统中的精英策略n每次循环之后给予最优解以额外的信息素量n这样的解被称为全局最优解（global-best solution）n找出这个解的蚂蚁被称为精英蚂蚁(elitist ants)第18页/共33页2023/2/23精英蚂蚁系统信息素根据下式进行更新o 是精英蚂蚁的个数 是所找出的最优解的路径长度精英蚂蚁系统特点：更高的求解精度，更快的求解速度，但精英蚂蚁设置太多会加速早熟。第19页/共33页2023/2/23基于排列的蚂蚁系统基于排列蚂蚁系统(ASrank)由Bullnheimer于1997年提出。基本思想与EAS类似，具体做法是在每一轮所有蚂蚁

11、构建完路径后，将各自所得的路径进行排名，只有生成了至今最优路径的蚂蚁以及排名在前(-1)的蚂蚁才允许释放信息素。最优蚂蚁释放 的信息素量，在本次迭代中排名 的蚂蚁将释放 的信息素。一般设置=6。第20页/共33页2023/2/23最大最小蚂蚁系统前两种改进算法将蚂蚁的搜索行为偏向当前最优解虽然提高解的质量和收敛速度，进而改进算法的性能。但这种搜索方式无法避免早熟收敛问题。o最大-最小蚂蚁系统(Max-Min Ant System,MMAS)于1997年由Sttzle提出。这种算法将之前的搜索方式和一种能够有效避免早熟收敛的机制结合在一起，从而使其获得更好的全局搜索能力。第21页/共33页202

12、3/2/23最大最小蚂蚁系统MMAS和AS主要有四个方面不同：在每次循环之后，只有一只蚂蚁进行信息素更新。这只蚂蚁可能是找出当前循环中最优解的蚂蚁，也可能是找出从实验开始以来最优解的蚂蚁在每个解的元素上的的信息素量被限制在范围区间内信息素初始值为信息素取值范围的上限 ，信息维持率保持一个较大值。当系统陷入停滞，将问题空间所有边的信息素重新初始化。第22页/共33页2023/2/23最大最小蚂蚁系统改进1借鉴了EAS，但有不同。使用至今最优的蚂蚁释放可加快收敛，当前迭代最优可增强探索，应该交替使用，逐渐增大至今最优蚂蚁的使用概率。改进2通过给信息素设定上界目的是避免信息素增长过快，淹没了启发式信

13、息的影响。启发式信息在每次迭代中是无法增长的。改进3设置较大的信息素维持度（一般设置为）可以保证初始阶段的探索能力。改进4可以利用停滞后的迭代周期继续进行搜索。第23页/共33页2023/2/23蚁群系统蚁群系统(Ant Colony System,ACS)是由Dorigo和Gambardella在1997年提出的。o蚁群系统做了三个方面的改进：n使用一种伪随机比例规则选择下一元素j，利用了先验知识。n信息素全局更新规则将只应用于至今最优蚂蚁路径。n新增信息素局部信息素更新规则。第24页/共33页2023/2/23蚁群系统状态转移规则一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动

14、到的城市J是一个0,1区间的参数，是一个0,1区间的随机数，当 蚂蚁选择开发当前最优路径；当 蚂蚁进行偏向选择，探索其他区域通过调节 值可以平衡开发和探索的关系。第25页/共33页2023/2/23蚁群系统全局更新规则只有一只至今最优的蚂蚁（大规模问题性能更优）才被允许释放信息素每轮迭代中，所有蚂蚁构建完路径后，信息素全局更新规则才被使用。更新公式如下所示：本公式用一种隐含的方式对信息素上界进行了限制。第26页/共33页2023/2/23蚁群系统局部更新规则每只蚂蚁应用下列局部更新规则对它们所经过的边进行信息素更新：实验发现，可以产生好的结果，其中n是城市的数量，是由最近的邻域启发产生的路径长

15、度局部更新规则作用于某条边会使这条边被其他蚂蚁选择的概率减少，可以有效地避免蚂蚁收敛到同一路径。是信息素局部维持率，是信息素初始值第27页/共33页2023/2/23蚁群优化算法优缺点蚁群优化算法有如下优点：l是具有自学习能力，可以对自身知识库或自身的组织结构进行再组织，实现算法能力的进化l采用正反馈机制，能加快搜索l采用分布式并行计算多点同时独立搜索易于找到全局最优 l易于和其他方法结合 l有较强的鲁棒性蚁群优化算法有如下缺点：l要么搜索时间长要么易陷入局部最优，很难保持平衡。l算法机理的复杂和环境的变化会增加蚁群算法的不确定性第28页/共33页2023/2/23蚁群优化算法的应用基于算法的

16、诸多优点，蚁群优化已被成功地应用于二次分配问题(quadratic assignment problem,QAP),作业调度问题(job-scheduling problem,JSP),图表着色问题(graph coloring problem,GCP),车辆路径问题(Vehicle Routing Problem,VRP),通信网络的路由优化(network route,NR)等另外也为数据挖掘、图像处理、系统识别等问题提供了有效且高效的解决手段。第29页/共33页2023/2/23蚁群优化算法参数设置（一）第30页/共33页2023/2/23蚁群优化算法参数设置（二）第31页/共33页2023/2/23Questions?第32页/共33页2023/2/23copyright:hhq感谢您的观看！第33页/共33页