《【教学课件】第八章蚁群优化算法.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第八章蚁群优化算法.ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第八章第八章 蚁群优化算法蚁群优化算法1 1第八章第八章 蚁群优化蚁群优化一一.导言导言二二.ACO.ACO算法算法2 21.ACO的产生的产生Ant Colony Optimization(ACO)Ant Colony Optimization(ACO)，蚁群优化，开，蚁群优化，开，蚁群优化，开，蚁群优化，开始时称为始时称为始时称为始时称为“蚁群系统蚁群系统蚁群系统蚁群系统”19911991年，年，年，年，意大利学者意大利学者意大利学者意大利学者DorigoDorigo正式正式正式正式提出提出提出提出ACOACO算法算法算法算法 M.Dorigo.Optimization,learning
2、and natural M.Dorigo.Optimization,learning and natural algorithms D.Italy:Politecnico diMilano,algorithms D.Italy:Politecnico diMilano,Department of Electronics,1992.Department of Electronics,1992.一一.导言导言3 32.基本思想基本思想一个小例子一个小例子一个小例子一个小例子一一.导言导言4 42.基本思想基本思想一个小例子一个小例子一个小例子一个小例子一一.导言导言出现障碍物出现障碍物5 52.基
3、本思想基本思想一个小例子一个小例子一个小例子一个小例子一一.导言导言搜索新路搜索新路6 62.基本思想基本思想一个小例子一个小例子一个小例子一个小例子一一.导言导言最佳路径形成最佳路径形成7 72.基本思想基本思想蚂蚁的觅食行为蚂蚁的觅食行为蚂蚁的觅食行为蚂蚁的觅食行为 主体：蚂蚁主体：蚂蚁主体：蚂蚁主体：蚂蚁 规则：分工、通讯规则：分工、通讯规则：分工、通讯规则：分工、通讯 相互作用（相互作用（相互作用（相互作用（interactioninteraction）：）：）：）：a.a.蚂蚁蚂蚁蚂蚁蚂蚁=蚂蚁蚂蚁蚂蚁蚂蚁b.b.蚂蚁蚂蚁蚂蚁蚂蚁=环境环境环境环境 整体往往大于部分的整体往往大于部分
4、的整体往往大于部分的整体往往大于部分的“简单和简单和简单和简单和”a.a.蚂蚁的蚂蚁的蚂蚁的蚂蚁的低低低低智能智能智能智能蚁群的蚁群的蚁群的蚁群的高高高高智慧智慧智慧智慧 b.b.蚂蚁的蚂蚁的蚂蚁的蚂蚁的简单简单简单简单行为行为行为行为蚁群的蚁群的蚁群的蚁群的智能智能智能智能突现突现突现突现一一.导言导言8 82.基本思想基本思想蚂蚁的觅食行为：昆虫学家通过大量研究发现，蚂蚁的觅食行为：昆虫学家通过大量研究发现，蚂蚁的觅食行为：昆虫学家通过大量研究发现，蚂蚁的觅食行为：昆虫学家通过大量研究发现，蚂蚁个体之间通过信息交流达到找到从蚁巢到蚂蚁个体之间通过信息交流达到找到从蚁巢到蚂蚁个体之间通过信息
5、交流达到找到从蚁巢到蚂蚁个体之间通过信息交流达到找到从蚁巢到食物源的最短路径的目的食物源的最短路径的目的食物源的最短路径的目的食物源的最短路径的目的 蚂蚁个体在运动过程能够在它经过的路径上留下蚂蚁个体在运动过程能够在它经过的路径上留下蚂蚁个体在运动过程能够在它经过的路径上留下蚂蚁个体在运动过程能够在它经过的路径上留下称为信息素（称为信息素（称为信息素（称为信息素（pheromonepheromone）的物质）的物质）的物质）的物质 随后的蚂蚁在遇到信息素时，不仅能够检测出该随后的蚂蚁在遇到信息素时，不仅能够检测出该随后的蚂蚁在遇到信息素时，不仅能够检测出该随后的蚂蚁在遇到信息素时，不仅能够检测
6、出该物质的存在以及量的多少，还可以根据信息素的物质的存在以及量的多少，还可以根据信息素的物质的存在以及量的多少，还可以根据信息素的物质的存在以及量的多少，还可以根据信息素的浓度指导自己对前进方向的选择浓度指导自己对前进方向的选择浓度指导自己对前进方向的选择浓度指导自己对前进方向的选择一一.导言导言9 92.基本思想基本思想蚂蚁的觅食行为蚂蚁的觅食行为蚂蚁的觅食行为蚂蚁的觅食行为 信息素会随着时间的推移逐渐挥发掉，于是路径信息素会随着时间的推移逐渐挥发掉，于是路径信息素会随着时间的推移逐渐挥发掉，于是路径信息素会随着时间的推移逐渐挥发掉，于是路径的长短及其蚂蚁的多少就会对残余信息素的强度的长短及
7、其蚂蚁的多少就会对残余信息素的强度的长短及其蚂蚁的多少就会对残余信息素的强度的长短及其蚂蚁的多少就会对残余信息素的强度产生影响，反过来信息素的强弱又指导着其他蚂产生影响，反过来信息素的强弱又指导着其他蚂产生影响，反过来信息素的强弱又指导着其他蚂产生影响，反过来信息素的强弱又指导着其他蚂蚁的前进方向蚁的前进方向蚁的前进方向蚁的前进方向 由大量蚂蚁组成的群体行为便表现出一种信息正由大量蚂蚁组成的群体行为便表现出一种信息正由大量蚂蚁组成的群体行为便表现出一种信息正由大量蚂蚁组成的群体行为便表现出一种信息正反馈现象：某一条路径上走过的蚂蚁越多，则后反馈现象：某一条路径上走过的蚂蚁越多，则后反馈现象：某
8、一条路径上走过的蚂蚁越多，则后反馈现象：某一条路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大，蚂蚁就通过这种来者选择该路径的概率就越大，蚂蚁就通过这种来者选择该路径的概率就越大，蚂蚁就通过这种来者选择该路径的概率就越大，蚂蚁就通过这种信息的交流找到从蚁巢到食物源的最短路径信息的交流找到从蚁巢到食物源的最短路径信息的交流找到从蚁巢到食物源的最短路径信息的交流找到从蚁巢到食物源的最短路径一一.导言导言10102.基本思想基本思想从真实蚂蚁到人工蚂蚁从真实蚂蚁到人工蚂蚁从真实蚂蚁到人工蚂蚁从真实蚂蚁到人工蚂蚁一一.导言导言11111.旅行商问题描述旅行商问题描述TSPTSP问题：一个商人欲到问
9、题：一个商人欲到问题：一个商人欲到问题：一个商人欲到n n个城市推销商品，已个城市推销商品，已个城市推销商品，已个城市推销商品，已知每两个城市知每两个城市知每两个城市知每两个城市i i和和和和j j之间的距离之间的距离之间的距离之间的距离d dij ij，如何选择一条，如何选择一条，如何选择一条，如何选择一条路径使得商人每个城市走一遍后回到起点且所路径使得商人每个城市走一遍后回到起点且所路径使得商人每个城市走一遍后回到起点且所路径使得商人每个城市走一遍后回到起点且所走的路径最短走的路径最短走的路径最短走的路径最短二二.ACO.ACO算法算法12122.ACO算法流程算法流程Step 1Step
10、 1初始化初始化初始化初始化:设定路径信息素初值，随机将设定路径信息素初值，随机将设定路径信息素初值，随机将设定路径信息素初值，随机将mm只人只人只人只人工蚂蚁放置到城市中工蚂蚁放置到城市中工蚂蚁放置到城市中工蚂蚁放置到城市中Step 2Step 2 选择机制：每只人工蚂蚁的选择机制是根据选择机制：每只人工蚂蚁的选择机制是根据选择机制：每只人工蚂蚁的选择机制是根据选择机制：每只人工蚂蚁的选择机制是根据一定的概率选择下一个未访问的城市一定的概率选择下一个未访问的城市一定的概率选择下一个未访问的城市一定的概率选择下一个未访问的城市二二.ACO.ACO算法算法13132.ACO算法流程算法流程Ste
11、p 3Step 3信息素更新：每只人工蚂蚁完成一步（从一信息素更新：每只人工蚂蚁完成一步（从一信息素更新：每只人工蚂蚁完成一步（从一信息素更新：每只人工蚂蚁完成一步（从一城市移动到另一个城市）或者完成一个巡回城市移动到另一个城市）或者完成一个巡回城市移动到另一个城市）或者完成一个巡回城市移动到另一个城市）或者完成一个巡回（完成对所有（完成对所有（完成对所有（完成对所有n n个城市的访问）后，更新所有个城市的访问）后，更新所有个城市的访问）后，更新所有个城市的访问）后，更新所有路径上的信息素浓度路径上的信息素浓度路径上的信息素浓度路径上的信息素浓度Step 4Step 4停止准则：若停止，则输出
12、结果，否则，转停止准则：若停止，则输出结果，否则，转停止准则：若停止，则输出结果，否则，转停止准则：若停止，则输出结果，否则，转到到到到Step 2Step 2二二.ACO.ACO算法算法14144.ACO算法的构成要素算法的构成要素选择概率选择概率选择概率选择概率二二.ACO.ACO算法算法蚂蚁标号蚂蚁标号蚂蚁标号蚂蚁标号迭代次数迭代次数迭代次数迭代次数信息素的影响信息素的影响信息素的影响信息素的影响15154.ACO算法的构成要素算法的构成要素选择概率选择概率选择概率选择概率二二.ACO.ACO算法算法16164.ACO算法的构成要素算法的构成要素选择概率选择概率选择概率选择概率二二.AC
13、O.ACO算法算法17174.ACO算法的构成要素算法的构成要素信息素更新信息素更新信息素更新信息素更新二二.ACO.ACO算法算法蚂蚁蚂蚁蚂蚁蚂蚁k k的巡回长度的巡回长度的巡回长度的巡回长度常量常量常量常量所有蚂蚁留下的信息所有蚂蚁留下的信息所有蚂蚁留下的信息所有蚂蚁留下的信息信息素增量信息素增量信息素增量信息素增量遗忘因子遗忘因子遗忘因子遗忘因子18184.ACO的核心思想的核心思想选择机制：信息素越多的路径，被选中的概率选择机制：信息素越多的路径，被选中的概率选择机制：信息素越多的路径，被选中的概率选择机制：信息素越多的路径，被选中的概率越大越大越大越大信息素更新机制：路径越短，信息素增加越快信息素更新机制：路径越短，信息素增加越快信息素更新机制：路径越短，信息素增加越快信息素更新机制：路径越短，信息素增加越快协作机制：个体之间通过信息素进行信息交流协作机制：个体之间通过信息素进行信息交流协作机制：个体之间通过信息素进行信息交流协作机制：个体之间通过信息素进行信息交流二二.ACO.ACO算法算法1919