《现代优化算法蚁群算法.pptx》由会员分享，可在线阅读，更多相关《现代优化算法蚁群算法.pptx（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、现代智能优化算法现代智能优化算法I.I.模拟退火模拟退火II.II.遗传算法遗传算法III.III.蚁群优化算法蚁群优化算法第1页/共39页蚁群优化算法蚁群优化算法蚂蚁生物行为蚂蚁生物行为I.I.蚂蚁搬家，天要下雨。蚂蚁搬家，天要下雨。II.II.蚂蚁群体行为。蚂蚁群体行为。a.a.相互协作的一群相互协作的一群蚂蚁可以战胜比自己强壮的昆虫，蚂蚁可以战胜比自己强壮的昆虫，并把它搬回巢；而单个蚂蚁则不能。并把它搬回巢；而单个蚂蚁则不能。b.b.相互协作的一群相互协作的一群蚂蚁可以蚂蚁可以很容易找到从蚁巢到食很容易找到从蚁巢到食物源的最短路径，而单个蚂蚁则不能。此外，蚂物源的最短路径，而单个蚂蚁则不
2、能。此外，蚂蚁还能够适应环境的变化，例如在蚁群的运动路蚁还能够适应环境的变化，例如在蚁群的运动路线上突然出现障碍物时，它们能够很快地重新找线上突然出现障碍物时，它们能够很快地重新找到最优路径。到最优路径。不但引起昆虫学家，而且也引不但引起昆虫学家，而且也引起数学及计算机方面的专家和工程师的兴趣。起数学及计算机方面的专家和工程师的兴趣。第2页/共39页蚁群优化算法蚁群优化算法蚂蚁生物行为蚂蚁生物行为昆虫学家通过大量的研究发现：昆虫学家通过大量的研究发现：蚂蚁个体之间是通过信息蚂蚁个体之间是通过信息交流达到找到从蚁巢到食物源的最短路径的目的。交流达到找到从蚁巢到食物源的最短路径的目的。I.蚂蚁个体
3、通过在其所经过的路上留下一种称之为蚂蚁个体通过在其所经过的路上留下一种称之为“信息素信息素”（pheromone）或）或“迹迹”的物质来实现与的物质来实现与同伴之间的信息传递。同伴之间的信息传递。II.随后的蚂蚁遇到信息素时，不仅能检测出该物质的随后的蚂蚁遇到信息素时，不仅能检测出该物质的存在以及量的多少，而且可根据信息素的浓度来指存在以及量的多少，而且可根据信息素的浓度来指导自己对前进方向的选择。导自己对前进方向的选择。第3页/共39页蚁群优化算法蚁群优化算法蚂蚁生物行为蚂蚁生物行为III.信息素信息素随着时间的推移会逐渐挥发掉，于是路径的随着时间的推移会逐渐挥发掉，于是路径的长短及其蚂蚁的
4、多少就对残余信息素的强度产生影长短及其蚂蚁的多少就对残余信息素的强度产生影响，反过来信息素的强弱又指导着其它蚂蚁的行动响，反过来信息素的强弱又指导着其它蚂蚁的行动方向。方向。因此，某一路径上走过的蚂蚁越多，则后来者选择该路径因此，某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。这就构成了蚂蚁群体行为表现出的一种信的概率就越大。这就构成了蚂蚁群体行为表现出的一种信息正反馈现象，并实现找到息正反馈现象，并实现找到蚁巢到食物源的最短路径蚁巢到食物源的最短路径。第4页/共39页蚁群优化算法蚁群优化算法蚂蚁生物行为蚂蚁生物行为蚁群实现找到蚁群实现找到蚁巢到食物源的最短路径示意图蚁巢到食物源的最
5、短路径示意图障障碍碍物物ABCDEHd=1d=1d=0.5d=0.5图图1图图1中中设设A是是蚁蚁巢巢，E是是食食物物源源，H、C为为障障碍碍物物，由由于于障障碍碍物物的的存存在在，由由A外外出出觅觅食食或或由由E返返回回巢巢穴穴的的蚂蚂蚁蚁只只能能经经由由H或或C到到达达目目的的地地。BH和和HD距距离离为为1单单位位，BC和和DC距离为距离为0.5单位。单位。假假设设蚂蚂蚁蚁以以“1单单位位长长度度/单单位位时时间间”的的速速度度往往返返于于A和和E，每每经经过过一一个个单单位位时时间间各各有有30只只蚂蚂蚁蚁离离开开A和和E到到达达B和和D。第5页/共39页蚁群优化算法蚁群优化算法蚂蚁生
6、物行为蚂蚁生物行为蚁群实现找到蚁群实现找到蚁巢到食物源的最短路径示意图蚁巢到食物源的最短路径示意图障障碍碍物物ABCDEH15151515初初始始时时，各各有有30只只蚂蚂蚁蚁在在B和和D点点遇遇到到障障碍碍物物，开开始始选选择择路路径径。由由于于此此时时路路径径上上无无迹迹，蚂蚂蚁蚁便便以以相相同同的的概概率率随随机机地地走走两两条条路路中中的的任任意意一一条条，因因而而15只只选选往往H，15只选往只选往C（图（图2）。）。经经过过一一个个单单位位时时间间以以后后，路路径径BHD被被15只只蚂蚂蚁蚁爬爬过过，而而路路径径BCD上上则则被被30只只蚂蚂蚁蚁爬爬过过，BCD上上的的信信息息量量
7、是是BHD上信息量的两倍上信息量的两倍。图图2第6页/共39页蚁群优化算法蚁群优化算法蚂蚁生物行为蚂蚁生物行为蚁群实现找到蚁群实现找到蚁巢到食物源的最短路径示意图蚁巢到食物源的最短路径示意图障障碍碍物物ABCDEH10102020图图3此此时时，又又有有30只只蚂蚂蚁蚁离离开开B和和D，于于是是20只只选选择择往往C方方向向，而而另另外外10只只则则选选往往H（图图3）。这这样样，更更多多的的信信息息量量被被留留在更短的路径在更短的路径BCD上。上。随随着着时时间间的的推推移移和和上上述述过过程程的的重重复复，短短路路径径上上的的信信息息量量便便以以更更快快的的速速度度增增长长，于于是是会会有
8、有越越来来越越多多的的蚂蚂蚁蚁选选择择这这条短路径，以致最终完全选择这条短路径条短路径，以致最终完全选择这条短路径BCD。相对弱小，功能并不强大的个体是完成复杂的工作。相对弱小，功能并不强大的个体是完成复杂的工作。第7页/共39页蚁群优化算法蚁群优化算法算法提出算法提出一个著名的组合优化问题：一个著名的组合优化问题：旅旅行行商商问问题题（TSP,traveling salesman problem），一一个个商商人人欲欲到到 n 个个城城市市推推销销商商品品，每每个个两两个个城城市市 i 和和 j 之之间间的的距距离离为为 dij，如如何何选选择择一一条条道道路路使使得得商商人人每每个个城市走
9、一遍后回到起点且所走路径最短。城市走一遍后回到起点且所走路径最短。第8页/共39页蚁群优化算法蚁群优化算法算法提出算法提出一般旅行商问题一般旅行商问题TSP，数学模型描述：，数学模型描述：选择选择 ij 路线为路线为1 1，否则为，否则为0 0避免产生回路避免产生回路走入城市走入城市j只有一次只有一次从城市从城市i出发只有一次出发只有一次第9页/共39页蚁群优化算法蚁群优化算法算法提出算法提出例子，一般旅行商例子，一般旅行商TSP问题的解。问题的解。ABDEC如如图图所所示示，从从A城城市市出出发发回回到到A城城市市一一个个TSP问问题题的的解解是是ABCEDA，即图中红色线条路径。即图中红色
10、线条路径。这个解满足以上四个约束条件。这个解满足以上四个约束条件。第10页/共39页蚁群优化算法蚁群优化算法算法提出算法提出NP问问题题：至至今今为为止止，还还没没有有一一个个有有能能求求得得最最优优解解的的多多项项式式时时间间算算法法的的组组合合优优化化问题称为问题称为NP问题。问题。TSP问问题题就就是是一一个个著著名名的的NP问问题题。在在如如何何解解决决这这个个问问题题方方面面已已经经有有了了大大量量的的研研究。这其中包括遗传算法，退火算法，动态规划等等。究。这其中包括遗传算法，退火算法，动态规划等等。第11页/共39页蚁群优化算法蚁群优化算法算法提出算法提出TSP问题与蚁群寻径行为比
11、较：问题与蚁群寻径行为比较：TSP问题问题蚁群寻径行为蚁群寻径行为解解路径路径寻优过程寻优过程选择路径选择路径最短路径（最优解）最短路径（最优解）最短路径最短路径第12页/共39页蚁群优化算法蚁群优化算法算法提出算法提出在在20世世纪纪90年年代代，意意大大利利学学者者Dorigo等等人人从从生生物物进进化化的的机机理理中中受受到到启启发发，通通过过模模拟拟自自然然界界蚂蚂蚁蚁寻寻径径的的行行为为，提提出出了了一一种种全全新新的的模模拟拟进进化化算算法法，蚁蚁群群优优化化算算法法。并并用用该该方方法法求求解解TSP问问题题（及及其其他他组组合合优优化化问问题题，如如分分配配问题、问题、Job-
12、shop 调度问题等），取得了一系列较好的实验结果。调度问题等），取得了一系列较好的实验结果。第13页/共39页蚁群优化算法蚁群优化算法算法提出算法提出蚁群优化算法的核心思想有三条：蚁群优化算法的核心思想有三条：第一，选择机制：迹越多的路径，被选中的概率越大；第一，选择机制：迹越多的路径，被选中的概率越大；第二，迹更新机制：路径越短，迹增加越快；第二，迹更新机制：路径越短，迹增加越快；第三，协作机制：个体之间通过迹进行信息交流。第三，协作机制：个体之间通过迹进行信息交流。第14页/共39页蚁群优化算法蚁群优化算法算法流程算法流程蚁群优化算法实现（以蚁群优化算法实现（以TSPTSP问题为例）：问
13、题为例）：第一步，第一步，初始化，将初始化，将m只蚂蚁放入到只蚂蚁放入到n个随机选择的城市中。个随机选择的城市中。第二步，第二步，选择机制：选择机制：每一只蚂蚁每一步的行动是，根据一定的依据选择下一个每一只蚂蚁每一步的行动是，根据一定的依据选择下一个它还没有访问的城市；它还没有访问的城市；第三步，第三步，迹更新机制：迹更新机制：在完成一步（从一个城市到达另外一个城市）或者一个在完成一步（从一个城市到达另外一个城市）或者一个循环（完成对所有循环（完成对所有n个城市的访问）后，更新所有路径上的残留信息浓度。个城市的访问）后，更新所有路径上的残留信息浓度。第四步，第四步，判断是否停止算法，停止则输出
14、最优结果；否则，返回判断是否停止算法，停止则输出最优结果；否则，返回第二步第二步。第15页/共39页蚁群优化算法蚁群优化算法算法流程算法流程选择机制，选择下一个城市的依据主要是两点：选择机制，选择下一个城市的依据主要是两点：1）t 时刻连接城市时刻连接城市 i 和和 j 的路径上残留信息（迹）的浓度的路径上残留信息（迹）的浓度 。2）由城市）由城市 i 转移到城市转移到城市 j 的启发信息，该启发信息是由要解决的问题给出的的启发信息，该启发信息是由要解决的问题给出的 ，在，在TSP问题中一般取问题中一般取 ，其中，其中，表示城市表示城市 i，j 间的距离，间的距离，在这里可以称为先验知识。在这
15、里可以称为先验知识。第16页/共39页蚁群优化算法蚁群优化算法算法流程算法流程选择机制，选择机制，那么，那么，t 时刻位于城市时刻位于城市 i 的蚂蚁的蚂蚁 k 选择城市选择城市 j 为目标城市的概率是：为目标城市的概率是：残留信息的相对重要程度；：残留信息的相对重要程度；：启发信息的相对重要程度；：启发信息的相对重要程度；：所有可能的目标城市，即还没有：所有可能的目标城市，即还没有访问的城市。为了避免对同一访问的城市。为了避免对同一个城市的多次访问，每一只蚂个城市的多次访问，每一只蚂蚁都保存一个列表蚁都保存一个列表tabu(k)，用，用于记录到目前为止已经访问的于记录到目前为止已经访问的城市
16、；城市；：t时刻蚂蚁由时刻蚂蚁由 i 城市到城市到 j 城市的概城市的概率。率。第17页/共39页蚁群优化算法蚁群优化算法算法流程算法流程迹更新机制，迹更新机制，为了避免残留信息过多引起的残留信息淹没启发信息的问题，在每一只蚂蚁完为了避免残留信息过多引起的残留信息淹没启发信息的问题，在每一只蚂蚁完成对所有成对所有n个城市的访问后（也即一个循环结束后）或每走一步（从一个城市到个城市的访问后（也即一个循环结束后）或每走一步（从一个城市到下一个城市后），必须对残留信息进行更新处理，下一个城市后），必须对残留信息进行更新处理，Morigo介绍三种迹更新机制：介绍三种迹更新机制：1）ant-cycle算
17、法算法2）ant-density算法算法3）ant-quantity算法算法第18页/共39页蚁群优化算法蚁群优化算法算法流程算法流程迹更新机制迹更新机制ant-cycle算法，算法，在每一只蚂蚁完成对所有在每一只蚂蚁完成对所有n个城市的访问后，对旧的信息进行削弱，将最新的蚂个城市的访问后，对旧的信息进行削弱，将最新的蚂蚁访问路径的信息加入蚁访问路径的信息加入 。：残留信息的保留部分；：残留信息的保留部分；：残留信息被削弱的部分，小于：残留信息被削弱的部分，小于1；：蚂蚁：蚂蚁k在时间段在时间段t到到t+n内的访问过程中，在内的访问过程中，在i到到j的路径的路径上留下的残留信息浓度；上留下的残
18、留信息浓度；Q ：为常量；：为常量；Lk ：蚂蚁：蚂蚁k在本次循环中所选择路径的总长度。在本次循环中所选择路径的总长度。第19页/共39页蚁群优化算法蚁群优化算法算法流程算法流程迹更新机制迹更新机制ant-cycle算法，算法，：蚂蚁：蚂蚁k在时间段在时间段t到到t+n内的访问过程中，在内的访问过程中，在i到到j的路径的路径上留下的残留信息浓度；上留下的残留信息浓度；Q ：为常量；：为常量；Lk ：蚂蚁：蚂蚁k在本次循环中所选择路径的总长度；如果没有在本次循环中所选择路径的总长度；如果没有选择选择i到到j的路径，则的路径，则 第20页/共39页蚁群优化算法蚁群优化算法算法流程算法流程迹更新机制
19、迹更新机制ant-density算法，算法，在每一只蚂蚁完成下一个个城市的访问后，对旧的信息进行削弱，将最新的蚂在每一只蚂蚁完成下一个个城市的访问后，对旧的信息进行削弱，将最新的蚂蚁访问路径的信息加入蚁访问路径的信息加入 。蚂蚁蚂蚁k选择选择i到到j的路径的路径蚂蚁蚂蚁k没有选择没有选择i到到j的路径的路径第21页/共39页蚁群优化算法蚁群优化算法算法流程算法流程迹更新机制迹更新机制ant-quantity算法，算法，在每一只蚂蚁完成下一个个城市的访问后，对旧的信息进行削弱，将最新的蚂在每一只蚂蚁完成下一个个城市的访问后，对旧的信息进行削弱，将最新的蚂蚁访问路径的信息加入蚁访问路径的信息加入
20、。蚂蚁蚂蚁k选择选择i到到j的路径的路径蚂蚁蚂蚁k没有选择没有选择i到到j的路径的路径第22页/共39页蚁群优化算法蚁群优化算法算法流程算法流程迹更新机制迹更新机制三种算法的比较，三种算法的比较，ant-cycle算法的效果最好，这是因为它用的是算法的效果最好，这是因为它用的是全局信息全局信息Q/Lk；ant-density、ant-quantity算法用的是算法用的是局部信息局部信息Q、Q/dij。第23页/共39页蚁群优化算法蚁群优化算法算法流程算法流程迹更新机制迹更新机制优点：优点：1）保证了残留信息不至于无限累积，如果路径没有被选中，那么上面的）保证了残留信息不至于无限累积，如果路径没
21、有被选中，那么上面的残留信息会随时间的推移而逐渐减弱，这使算法能残留信息会随时间的推移而逐渐减弱，这使算法能“忘记忘记”不好的不好的路径；路径；2）即使路径经常被访问也不至于因为）即使路径经常被访问也不至于因为 的累积，而产生的累积，而产生 使启使启发信息的作用无法体现。发信息的作用无法体现。第24页/共39页蚁群优化算法蚁群优化算法算法流程算法流程NC=0，将，将m只蚂蚁放到只蚂蚁放到n个节点上个节点上开始开始对所有蚂蚁置初始城市到对所有蚂蚁置初始城市到tabu（k）NC=MAX吗？吗？对对所所有有蚂蚂蚁蚁计计算算概概率率，选选择择下下一一个个城城市市并并将将蚂蚂蚁移到下一个城市蚁移到下一个
22、城市j，将，将j加入到加入到tabu（k）tabu（k）满吗？）满吗？更新最佳路径，清空更新最佳路径，清空tabu（k），），NC=NC+1得到最佳路径，结束得到最佳路径，结束算法算法流程流程框图框图ant-cycle第25页/共39页蚁群优化算法蚁群优化算法算法流程算法流程算法复杂度：算法复杂度：如果程序终止于如果程序终止于NC次循环后，这个算法的复杂度为次循环后，这个算法的复杂度为O（NC*n2*m）。一般情况下，一般情况下，m一般取值与一般取值与n为同一数量级，因此整个算法的复杂度为同一数量级，因此整个算法的复杂度O（NC*n3）第26页/共39页蚁群优化算法蚁群优化算法优缺点优缺点优点
23、：优点：优点：优点：1 1）正反馈，能迅速找到较好的解；）正反馈，能迅速找到较好的解；）正反馈，能迅速找到较好的解；）正反馈，能迅速找到较好的解；2 2）分布式计算，可以避免过早地收敛；）分布式计算，可以避免过早地收敛；）分布式计算，可以避免过早地收敛；）分布式计算，可以避免过早地收敛；3 3）强启发，能在早期的寻优中迅速找到合适（可行）的解；）强启发，能在早期的寻优中迅速找到合适（可行）的解；）强启发，能在早期的寻优中迅速找到合适（可行）的解；）强启发，能在早期的寻优中迅速找到合适（可行）的解；4 4）强鲁棒性，对基本蚁群优化算法稍加修改，便可以应用）强鲁棒性，对基本蚁群优化算法稍加修改，便
24、可以应用）强鲁棒性，对基本蚁群优化算法稍加修改，便可以应用）强鲁棒性，对基本蚁群优化算法稍加修改，便可以应用于其他问题；于其他问题；于其他问题；于其他问题；5 5）易于与其他优化算法结合，以改善其优化性能。）易于与其他优化算法结合，以改善其优化性能。）易于与其他优化算法结合，以改善其优化性能。）易于与其他优化算法结合，以改善其优化性能。第27页/共39页蚁群优化算法蚁群优化算法优缺点优缺点缺点：缺点：缺点：缺点：1 1）算法有众多参数（如）算法有众多参数（如）算法有众多参数（如）算法有众多参数（如残留信息的相对重要程度、启发残留信息的相对重要程度、启发信息的相对重要程度、信息的相对重要程度、Q
25、常数、残留信息的保留部分常数、残留信息的保留部分）需要确定，并且算法对参数敏感；需要确定，并且算法对参数敏感；需要确定，并且算法对参数敏感；需要确定，并且算法对参数敏感；2 2）求解时间较长，蚁群算法的复杂度可以反映这一点；）求解时间较长，蚁群算法的复杂度可以反映这一点；）求解时间较长，蚁群算法的复杂度可以反映这一点；）求解时间较长，蚁群算法的复杂度可以反映这一点；3 3）易出现停滞现象，即算法搜索进行到一定程度后，所）易出现停滞现象，即算法搜索进行到一定程度后，所）易出现停滞现象，即算法搜索进行到一定程度后，所）易出现停滞现象，即算法搜索进行到一定程度后，所有个体发现的解都完全一致，不能对解
26、空间进一步进有个体发现的解都完全一致，不能对解空间进一步进有个体发现的解都完全一致，不能对解空间进一步进有个体发现的解都完全一致，不能对解空间进一步进行搜索。行搜索。行搜索。行搜索。第28页/共39页蚁群优化算法蚁群优化算法改进改进蚁群算法的各种改进：蚁群算法的各种改进：蚁群算法的各种改进：蚁群算法的各种改进：1 1）MAX-MIN ANT SYSTEM MAX-MIN ANT SYSTEM（MMASMMAS）算法）算法）算法）算法2 2）自适应蚁群优化算法）自适应蚁群优化算法）自适应蚁群优化算法）自适应蚁群优化算法3 3）自适应调整信息素的蚁群算法）自适应调整信息素的蚁群算法）自适应调整信息
27、素的蚁群算法）自适应调整信息素的蚁群算法4 4）自适应调整）自适应调整）自适应调整）自适应调整 （残留信息的保留部分残留信息的保留部分）的）的蚁群算法蚁群算法蚁群算法蚁群算法5 5）带杂交算子的蚁群算法）带杂交算子的蚁群算法）带杂交算子的蚁群算法）带杂交算子的蚁群算法6 6）在解决）在解决）在解决）在解决TSPTSP问题问题问题问题分段算法分段算法分段算法分段算法Section_MMMASSection_MMMAS7 7）在解决）在解决）在解决）在解决TSPTSP问题问题问题问题相遇算法相遇算法相遇算法相遇算法MMMASMMMAS第29页/共39页蚁群优化算法蚁群优化算法改进改进1 1）MAX
28、-MIN ANT SYSTEM MAX-MIN ANT SYSTEM（MMASMMAS）算法）算法）算法）算法I.I.只对最佳路径增加迹的浓度，从而更好地利用了历史只对最佳路径增加迹的浓度，从而更好地利用了历史只对最佳路径增加迹的浓度，从而更好地利用了历史只对最佳路径增加迹的浓度，从而更好地利用了历史信息；信息；信息；信息；II.II.为了避免算法过早收敛于并非全局最优的解，将各条为了避免算法过早收敛于并非全局最优的解，将各条为了避免算法过早收敛于并非全局最优的解，将各条为了避免算法过早收敛于并非全局最优的解，将各条路径可能的迹浓度限制于路径可能的迹浓度限制于路径可能的迹浓度限制于路径可能的迹
29、浓度限制于 ，超出这个范围的，超出这个范围的，超出这个范围的，超出这个范围的值被强制设为值被强制设为值被强制设为值被强制设为 或者为或者为或者为或者为 ，可以有效地避免某条，可以有效地避免某条，可以有效地避免某条，可以有效地避免某条路径上的信息量远大于其余路径，使得所有的蚂蚁都路径上的信息量远大于其余路径，使得所有的蚂蚁都路径上的信息量远大于其余路径，使得所有的蚂蚁都路径上的信息量远大于其余路径，使得所有的蚂蚁都集中到同一条路径上；集中到同一条路径上；集中到同一条路径上；集中到同一条路径上；III.III.将各条路径上迹的初始浓度设为将各条路径上迹的初始浓度设为将各条路径上迹的初始浓度设为将各
30、条路径上迹的初始浓度设为 ，这样便可以，这样便可以，这样便可以，这样便可以更加充分地进行寻优。更加充分地进行寻优。更加充分地进行寻优。更加充分地进行寻优。第30页/共39页蚁群优化算法蚁群优化算法改进改进2 2）自适应蚁群优化算法）自适应蚁群优化算法）自适应蚁群优化算法）自适应蚁群优化算法问题：问题：问题：问题：蚁群算法的主要依据是信息正反馈原理和某种启发式算蚁群算法的主要依据是信息正反馈原理和某种启发式算蚁群算法的主要依据是信息正反馈原理和某种启发式算蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合。在构造解的过程中，利用随机选择策略，法的有机结合。在构造解的过程中，利用随机选择
31、策略，法的有机结合。在构造解的过程中，利用随机选择策略，法的有机结合。在构造解的过程中，利用随机选择策略，这种选择策略使得进化速度慢；正反馈原理旨在强化性这种选择策略使得进化速度慢；正反馈原理旨在强化性这种选择策略使得进化速度慢；正反馈原理旨在强化性这种选择策略使得进化速度慢；正反馈原理旨在强化性能较好的解，却容易出现停滞现象。能较好的解，却容易出现停滞现象。能较好的解，却容易出现停滞现象。能较好的解，却容易出现停滞现象。解决：解决：解决：解决：从选择策略方面进行修改，采用确定性选择和随机选择从选择策略方面进行修改，采用确定性选择和随机选择从选择策略方面进行修改，采用确定性选择和随机选择从选择
32、策略方面进行修改，采用确定性选择和随机选择相结合的选择策略，并在搜索过程中动态地调整确定性相结合的选择策略，并在搜索过程中动态地调整确定性相结合的选择策略，并在搜索过程中动态地调整确定性相结合的选择策略，并在搜索过程中动态地调整确定性选择的概率。进化到一定代数后，进化方向已经基本确选择的概率。进化到一定代数后，进化方向已经基本确选择的概率。进化到一定代数后，进化方向已经基本确选择的概率。进化到一定代数后，进化方向已经基本确定，这时对路径上信息量作动态调整，缩小最好和最差定，这时对路径上信息量作动态调整，缩小最好和最差定，这时对路径上信息量作动态调整，缩小最好和最差定，这时对路径上信息量作动态调
33、整，缩小最好和最差路径上的信息两的差距，并适当增大随机选择的概率，路径上的信息两的差距，并适当增大随机选择的概率，路径上的信息两的差距，并适当增大随机选择的概率，路径上的信息两的差距，并适当增大随机选择的概率，以利于对解空间的更完全搜索。以利于对解空间的更完全搜索。以利于对解空间的更完全搜索。以利于对解空间的更完全搜索。第31页/共39页蚁群优化算法蚁群优化算法改进改进2 2）自适应蚁群优化算法）自适应蚁群优化算法）自适应蚁群优化算法）自适应蚁群优化算法该算法由下式确定蚂蚁该算法由下式确定蚂蚁该算法由下式确定蚂蚁该算法由下式确定蚂蚁 k k 从从从从 i i 城市转移到城市转移到城市转移到城市
34、转移到 s s 城市：城市：城市：城市：第32页/共39页蚁群优化算法蚁群优化算法改进改进3 3）自适应调整信息素的蚁群算法）自适应调整信息素的蚁群算法）自适应调整信息素的蚁群算法）自适应调整信息素的蚁群算法问题：问题：问题：问题：蚁群算法的主要依据是信息正反馈原理和某种启发式算蚁群算法的主要依据是信息正反馈原理和某种启发式算蚁群算法的主要依据是信息正反馈原理和某种启发式算蚁群算法的主要依据是信息正反馈原理和某种启发式算法的有机结合。在构造解的过程中，利用随机选择策略，法的有机结合。在构造解的过程中，利用随机选择策略，法的有机结合。在构造解的过程中，利用随机选择策略，法的有机结合。在构造解的过
35、程中，利用随机选择策略，这种选择策略使得进化速度慢；正反馈原理旨在强化性这种选择策略使得进化速度慢；正反馈原理旨在强化性这种选择策略使得进化速度慢；正反馈原理旨在强化性这种选择策略使得进化速度慢；正反馈原理旨在强化性能较好的解，却容易出现停滞现象。能较好的解，却容易出现停滞现象。能较好的解，却容易出现停滞现象。能较好的解，却容易出现停滞现象。解决：根据搜索进展情况，动态修改需要增加的信息素的方法。解决：根据搜索进展情况，动态修改需要增加的信息素的方法。解决：根据搜索进展情况，动态修改需要增加的信息素的方法。解决：根据搜索进展情况，动态修改需要增加的信息素的方法。算法采用时变函数算法采用时变函数
36、算法采用时变函数算法采用时变函数QQ（t t）来替代调整信息素）来替代调整信息素）来替代调整信息素）来替代调整信息素 中常量中常量中常量中常量QQ，即，即，即，即 ，QQ（t t）随着人）随着人）随着人）随着人工蚂蚁搜索过程做实时的调整和变化工蚂蚁搜索过程做实时的调整和变化工蚂蚁搜索过程做实时的调整和变化工蚂蚁搜索过程做实时的调整和变化第33页/共39页蚁群优化算法蚁群优化算法改进改进3 3）自适应调整信息素的蚁群算法）自适应调整信息素的蚁群算法）自适应调整信息素的蚁群算法）自适应调整信息素的蚁群算法自适应调整策略：自适应调整策略：自适应调整策略：自适应调整策略：通过对算法的监控，实时判断算法
37、的搜索状通过对算法的监控，实时判断算法的搜索状通过对算法的监控，实时判断算法的搜索状通过对算法的监控，实时判断算法的搜索状态，如果一段时间内获得的最优解没有变化，则减少要添加的态，如果一段时间内获得的最优解没有变化，则减少要添加的态，如果一段时间内获得的最优解没有变化，则减少要添加的态，如果一段时间内获得的最优解没有变化，则减少要添加的信息素，即减少信息素，即减少信息素，即减少信息素，即减少 中的中的中的中的QQ（t t）。）。）。）。Q（t）时变函数几）时变函数几个例子，针对不同个例子，针对不同情况使用情况使用第34页/共39页蚁群优化算法蚁群优化算法改进改进4 4）自适应调整）自适应调整）
38、自适应调整）自适应调整 （残留信息的保留部分残留信息的保留部分）的）的蚁群算法蚁群算法蚁群算法蚁群算法问题：问题：问题：问题：当问题规模比较大时，由于信息素的挥发系数当问题规模比较大时，由于信息素的挥发系数当问题规模比较大时，由于信息素的挥发系数当问题规模比较大时，由于信息素的挥发系数 1-1-的存的存的存的存在，使那些从未被搜索到的解上信息素会减少到接近于在，使那些从未被搜索到的解上信息素会减少到接近于在，使那些从未被搜索到的解上信息素会减少到接近于在，使那些从未被搜索到的解上信息素会减少到接近于0 0，降低，降低，降低，降低了算法的全局搜索能力，而且了算法的全局搜索能力，而且了算法的全局搜
39、索能力，而且了算法的全局搜索能力，而且 过大时，以前搜索过册解被选过大时，以前搜索过册解被选过大时，以前搜索过册解被选过大时，以前搜索过册解被选择的可能性过大，也会影响到算法全局搜索能力；通过减少择的可能性过大，也会影响到算法全局搜索能力；通过减少择的可能性过大，也会影响到算法全局搜索能力；通过减少择的可能性过大，也会影响到算法全局搜索能力；通过减少 ，虽然可以提高算法的全局搜索能力，但又会使算法的收敛速，虽然可以提高算法的全局搜索能力，但又会使算法的收敛速，虽然可以提高算法的全局搜索能力，但又会使算法的收敛速，虽然可以提高算法的全局搜索能力，但又会使算法的收敛速度降低。度降低。度降低。度降低
40、。解决：解决：解决：解决：自适应调整自适应调整自适应调整自适应调整 的值，的值，的值，的值，的初始值为的初始值为的初始值为的初始值为 =1=1；当算法求；当算法求；当算法求；当算法求得的最优值在得的最优值在得的最优值在得的最优值在N N次循环内没有明显改进时，次循环内没有明显改进时，次循环内没有明显改进时，次循环内没有明显改进时，减为：减为：减为：减为：第35页/共39页蚁群优化算法蚁群优化算法连续问题连续问题最初的蚁群算法思想起源于离散型的网络路径问题，因此，在一般函数优化问题中，必须对许多实施细节加以修正。第一，转移概率 第36页/共39页蚁群优化算法蚁群优化算法连续问题连续问题第二，强度更新方程 寻优过程：第37页/共39页蚁群优化算法蚁群优化算法连续问题连续问题一般函数优化的蚁群优化算法流程：第38页/共39页感谢您的观看！第39页/共39页