蚁群优化算法ppt课件.ppt

《蚁群优化算法ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、蚁群优化算法AntColonyOptimization蚁群优化算法蚁群优化算法简介一蚂蚁系统二蚁群优化算法的改进版本三蚁群优化算法相关应用四ACO是一种全局最优化搜索方法，解决典型组合优化问题具有明显的优越性，具有鲁棒性强、全局搜索、并行分布式计算、易于其他算法结合的优点。蚁群优化算法（ACO）由Dorigo（多里格）等人于1991年提出，是模拟自然界真实蚂蚁觅食过程的一种随机搜素算法。1.1基本原理提出性质1.1基本原理A（1）蚂蚁没有发育完全的视觉感知系统，其在寻找食物的过程中是如何选择路径的呢？（2）蚂蚁往往像军队般有纪律、有秩序地搬运

2、食物，它们通过什么方式进行群体间的交流协作呢？信息素是一种化学物质，由蚂蚁自身释放，是实现蚁群内间接通信的物质。蚂蚁随机选择路径，但是能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向前进。信息素1.1基本原理双桥实验蚁穴食物源（a）两个路具有同样的长度自身催化（正反馈）过程1.起初两条分支上不存在信息素，蚂蚁以相同的概率进行选择。2.随机波动的出现，选择某一条分支的蚂蚁数量可能比另外一条多。3.实验最终结果：所有的蚂蚁都会选择同一分支。1.1基本原理双桥实验（b）两条分支具有不同长度1.起初两条分支上不存在信息素，蚂蚁随机选择一条路

3、径。2.短分支上的信息素积累速度比长分支的快。3.实验最终结果：所有的蚂蚁都会选择较短的分支。4.有很小比例的蚂蚁会选择较长的分支。路径探索1.1基本理论蚁穴食物源（c）30分钟后添加短分支30分钟后双桥实验1.实验最终结果：除了极少的蚂蚁选择较短的分支以外，整个群体几乎都困在较长的分支上。2.长分支上的信息素浓度高，而信息素的蒸发速度过于缓慢。1.1基本理论双桥实验总结1选择路径是一个概率随机过程，启发式信息多以及信息浓度大的路径被选中概率更大。2信息素会不断的蒸发。3路径探索也是必需的，否则容易陷入局部最优。1.1基本理论蚁群觅食现象和蚁

4、群优化算法的基本定义对照表2001年至今1996年-2001年意大利学者Dorigo1991年启发各种改进算法的提出，应用领域更广引起学者关注，在应用领域得到拓宽ACO首次被系统的提出自然界中真实蚁群集体行为1.2研究进展历史进展1.2研究进展算法进展蚂蚁系统(AS)1991年基于排列蚂蚁系统1997年蚁群系统(ACS)1997年连续蚁群(CACO)2000年超立方体AS(HC-ACO)2001年连续正交蚁群(COAC)2008年精华蚂蚁系统(EAS)1991年最大最小蚂蚁系统(EAS)1996年1.2研究进展理论进展总结1.收敛性证明。一些

5、性能优越的ACO算法（MMAS和ACS）不管有没有使用局部搜素，都是值收敛的。2.将ACO纳入了基于模型的搜索框架中。趋势1.利用ACO算法去解决更为复杂的优化问题，例如：动态问题、随机问题、多目标问题。2、ACO算法的高效并行执行。3.更理论化的理解和刻画ACO算法在求解问题时的行为。4.与其他算法结合（粒子群算法）。蚁群优化算法蚁群优化算法简介一蚂蚁系统二蚁群优化算法的改进版本三蚁群优化算法相关应用四2.1TSP问题问题简述：已知有个城市的集合，任意两个城市之间均有路径连接，表示城市与之间的距离。旅行商问题就是需要寻找这样的一中周游方案：

6、周游路线从某个城市出发，经过每个城市一次且仅一次，最终回到出发城市，使得周游的路线总长度最短。第一个ACO——蚂蚁系统，就是以NP难的TSP问题作为应用实例提出的。2.2贪婪算法贪婪算法在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。基本理论P87页，四个城市间的距离矩阵如下：用贪婪算法求解：例如从城市A出发得ACDBA路径长度为：1+2+4+3=102.3蚂

7、蚁系统理论AS系统三个版本：1.蚂蚁圈2.蚂蚁数量3.蚂蚁密度其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；L为第k只蚂蚁经过路径的长度。d为城市间的距离。信息素更新方式2.3蚂蚁系统理论AS算法（蚂蚁圈版本）对TSP的求解流程主要有两大步骤：路径构建和信息素更新1.路径构建定义5.1AS中的随机比例规则：对每只蚂蚁k，路径记忆向量按照访问顺序记录了所有k已经经过的城市序号。设蚂蚁k当前所在的城市为i，则其选择城市j作为下一个访问对象的概率为：其中，表示从城市i可以直接到达的且又不在蚂蚁访问过的城市序列中的城市集合。是一个启发式信息，通

8、常由直接计算。表示边上的信息量2.3蚂蚁系统理论1.路径构建由公式知，长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。和是两个预先设置的参数，用来控制启发式信息