ch2智能理论蚁群算法(教学课件）

1、2021/8/23精品精品 PPT 模板模板1蚁群优化算法起源蚁群优化算法起源20世纪世纪90年代，意大利学者年代，意大利学者Dorigo等人从生物进化的机制等人从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出一中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出一种新型的模拟进化算法种新型的模拟进化算法蚁群算法，它是蚁群算法，它是群智能理论群智能理论研究研究领域的一种主要算法。领域的一种主要算法。用该方法求解用该方法求解TSP问题、分配问题、问题、分配问题、job-shop调度问题取调度问题取得了较好的试验结果。虽然研究时间不长，但是目前的研究得了较好的试验结果。虽然研究时间

2、不长，但是目前的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法。题）方面有一定优势，表明它是一种有发展前景的算法。2021/8/23精品精品 PPT 模板模板2蚁群优化算法应用领域蚁群优化算法应用领域l蚁群算法能够用于解决大多数优化问题或者能够被转化为蚁群算法能够用于解决大多数优化问题或者能够被转化为优化求解的问题。优化求解的问题。l目前，其应用领域已扩展到目前，其应用领域已扩展到 多目标优化多目标优化 数据分类数据分类 数据聚类数据聚类 模式识别模式识别 生物系统建模生物系统建模 流

3、程规划流程规划 信号处理信号处理 机器人控制机器人控制 决策支持决策支持 仿真和系统辩识仿真和系统辩识2021/8/23精品精品 PPT 模板模板3蚁群优化算法研究背景蚁群优化算法研究背景群智能理论研究领域有两种主要的算法：群智能理论研究领域有两种主要的算法： 蚁群算法蚁群算法(Ant Colony Optimization, ACO)l对蚂蚁群落食物采集过程的模拟对蚂蚁群落食物采集过程的模拟l已成功应用于许多离散优化问题。已成功应用于许多离散优化问题。 微粒群算法微粒群算法(Particle Swarm Optimization, PSO)l起源于对简单社会系统的模拟。起源于对简单社会系统的

4、模拟。l最初模拟鸟群觅食的过程，后来发现它是一种很好的优化工具。最初模拟鸟群觅食的过程，后来发现它是一种很好的优化工具。2021/8/23精品精品 PPT 模板模板4蚁群优化算法研究背景蚁群优化算法研究背景群智能依靠的是群智能依靠的是概率搜索算法概率搜索算法。虽然概率搜索算法通常要。虽然概率搜索算法通常要采用较多的评价函数，但与梯度法及传统的演化算法相比，采用较多的评价函数，但与梯度法及传统的演化算法相比，主要优点为：主要优点为： 无集中控制约束，不会因个别个体的故障影响整个问题的无集中控制约束，不会因个别个体的故障影响整个问题的求解，确保了系统具备更强的鲁棒性求解，确保了系统具备更强的鲁棒性

5、 以非直接的信息交流方式确保了系统的扩展性以非直接的信息交流方式确保了系统的扩展性 并行分布式算法模型，可充分利用多处理器并行分布式算法模型，可充分利用多处理器 对问题定义的连续性无特殊要求对问题定义的连续性无特殊要求 算法实现简单算法实现简单2021/8/23精品精品 PPT 模板模板5蚁群优化算法研究背景蚁群优化算法研究背景l群智能方法的易于实现体现在：群智能方法的易于实现体现在： 算法中仅涉及各种基本的数学操作算法中仅涉及各种基本的数学操作 数据处理过程对数据处理过程对CPU和内存的要求不高和内存的要求不高 只需要目标函数的输出值，不需要它的梯度信息。只需要目标函数的输出值，不需要它的梯

6、度信息。2021/8/23精品精品 PPT 模板模板6蚁群优化算法研究背景蚁群优化算法研究背景l已完成的群智能理论和应用方法研究证明已完成的群智能理论和应用方法研究证明 群智能方法能够有效解决大多数全局优化问题群智能方法能够有效解决大多数全局优化问题 群智能潜在的并行性和分布式特点为处理大量的、以数据库群智能潜在的并行性和分布式特点为处理大量的、以数据库形式存在的数据提供了技术保证。形式存在的数据提供了技术保证。l无论从理论研究还是应用研究的角度分析，群智能理论及无论从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是有重要学术意义和现实价值。其应用研究都是有重要学术意义和现实价值。2

7、021/8/23精品精品 PPT 模板模板7蚁群优化算法研究现状蚁群优化算法研究现状l从从Dorigo在在90年代最早提出蚁群算法年代最早提出蚁群算法-蚂蚁系统蚂蚁系统(Ant System, AS)，并将其应用于解决，并将其应用于解决TSP问题开始，基本的蚁问题开始，基本的蚁群算法得到了不断的发展和完善，并在其他许多实际优化群算法得到了不断的发展和完善，并在其他许多实际优化问题求解中进一步得到了验证。问题求解中进一步得到了验证。lAS改进版改进版 共同点：增强蚂蚁搜索过程中对最优解的探索能力共同点：增强蚂蚁搜索过程中对最优解的探索能力 差异：搜索控制策略差异：搜索控制策略2021/8/23精

8、品精品 PPT 模板模板8蚁群优化算法研究现状蚁群优化算法研究现状l最初提出的最初提出的AS有三种版本：有三种版本：Ant-density、Ant-quantity、Ant-cyclel前两种算法中，蚂蚁在两个位置节点间每移动一次后即更新信前两种算法中，蚂蚁在两个位置节点间每移动一次后即更新信息素。息素。lAnt-cycle中，所有蚂蚁都完成了自己的行程后，才对信息素进中，所有蚂蚁都完成了自己的行程后，才对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。质量的函数。 与其它各种通用的启发式算法相比，在不大于与其它各

9、种通用的启发式算法相比，在不大于75城市的城市的TSP中，它们的求解能力比较理想。但是当问题规模扩展时，中，它们的求解能力比较理想。但是当问题规模扩展时，AS的解题能力大幅度下降。的解题能力大幅度下降。2021/8/23精品精品 PPT 模板模板9蚁群优化算法研究现状蚁群优化算法研究现状其后的其后的ACO研究工作主要都集中在研究工作主要都集中在AS性能的改进方面。性能的改进方面。较早的一种改进是较早的一种改进是精英策略精英策略(Elitist Strategy)，其思想是：，其思想是： 在算法开始后，对所有已发现的最好路径给予额外增强，在算法开始后，对所有已发现的最好路径给予额外增强，并将随后

10、与之对应的行程记为并将随后与之对应的行程记为Tgb(全局最优行程全局最优行程)，当进行，当进行信息素更新时，对这些行程予以加权，同时将经过这些行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为程的蚂蚁记为“精英精英”，从而增大较好行程的选择机会。，从而增大较好行程的选择机会。 这种改进型算法能以更快的速度获得更好的解。但是若选这种改进型算法能以更快的速度获得更好的解。但是若选择的精英过多，则算法会由于较早收敛于局部次优解，而择的精英过多，则算法会由于较早收敛于局部次优解，而导致搜索的过早停滞。导致搜索的过早停滞。2021/8/23精品精品 PPT 模板模板10蚂蚁寻食过程蚂蚁寻食

11、过程l寻找路径时，在路径上释放出一种特殊的寻找路径时，在路径上释放出一种特殊的信息素信息素。l碰到没有走过的路口，随机挑选一条路径，并释放出与路碰到没有走过的路口，随机挑选一条路径，并释放出与路径长度有关的信息素。径长度有关的信息素。l路径越长，释放的激素浓度越低。路径越长，释放的激素浓度越低。l后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率相对较大。路径概率相对较大。l正反馈正反馈：最优路径上激素浓度越来越大，其它路径上激素：最优路径上激素浓度越来越大，其它路径上激素浓度随时间的流逝而消减。最终整个蚁群找出最优路径。浓度随时间的流

12、逝而消减。最终整个蚁群找出最优路径。2021/8/23精品精品 PPT 模板模板11简化的蚂蚁寻食过程简化的蚂蚁寻食过程l蚂蚁从蚂蚁从A点出发，速度相同，食物在点出发，速度相同，食物在D点。点。l可随机选择的路线：可随机选择的路线：ABD或或ACD。l设初始时每条路线分配一只蚂蚁，每单位时间行走一步设初始时每条路线分配一只蚂蚁，每单位时间行走一步l上图为经过上图为经过9个时间单位时的情形：走个时间单位时的情形：走ABD的蚂蚁到达终点，而走的蚂蚁到达终点，而走ACD的蚂蚁刚好走到的蚂蚁刚好走到C点，为一半路程。点，为一半路程。2021/8/23精品精品 PPT 模板模板12简化的蚂蚁寻食过程简化

13、的蚂蚁寻食过程本图为从开始算起，经过本图为从开始算起，经过18个时间单位时的情形：个时间单位时的情形：l走走ABD的蚂蚁到达终点后得到食物又返回了起点的蚂蚁到达终点后得到食物又返回了起点Al走走ACD的蚂蚁刚好走到的蚂蚁刚好走到D点。点。2021/8/23精品精品 PPT 模板模板13简化的蚂蚁寻食过程简化的蚂蚁寻食过程l设蚂蚁每经过一处所留下的信息素为一个单位。设蚂蚁每经过一处所留下的信息素为一个单位。l36个时间单位后，所有开始一起出发的蚂蚁都经过不同路个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从径从D点取得了食物。点取得了食物。 ABD的路线往返了的路线往返了2趟，每一处的信息素

14、为趟，每一处的信息素为4个单位个单位 ACD的路线往返了的路线往返了1趟，每一处的信息素为趟，每一处的信息素为2个单位个单位 信息素比值为信息素比值为2:1 按信息素指导，蚁群在按信息素指导，蚁群在ABD路线上增派一只蚂蚁路线上增派一只蚂蚁(共共2只只)，ACD路线上仍然是一只蚂蚁。路线上仍然是一只蚂蚁。2021/8/23精品精品 PPT 模板模板14简化的蚂蚁寻食过程简化的蚂蚁寻食过程l72个时间单位后，两条线路上的信息素单位积累为个时间单位后，两条线路上的信息素单位积累为12和和4，比值为比值为3:1。l若按以上规则继续，蚁群在若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁路线上再增派

15、一只蚂蚁(共共3只只)，ACD路线上仍然是一只蚂蚁。路线上仍然是一只蚂蚁。l再再36个时间单位后，两条线路上的信息素单位积累为个时间单位后，两条线路上的信息素单位积累为24和和6，比值为，比值为4：1。l若继续进行，按信息素指导，最终所有蚂蚁会放弃若继续进行，按信息素指导，最终所有蚂蚁会放弃ACD路路线，都选择线，都选择ABD路线，这就是正反馈效应。路线，这就是正反馈效应。2021/8/23精品精品 PPT 模板模板15自然蚁群与人工蚁群算法自然蚁群与人工蚁群算法l人工蚁群中把具有简单功能的工作单元看作蚂蚁。人工蚁群中把具有简单功能的工作单元看作蚂蚁。l相似处：优先选择信息素浓度大的路径。较短

16、路径的信息相似处：优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。优化结果。l区别：区别：人工蚁群能记忆已访问过的节点人工蚁群能记忆已访问过的节点，在选择下条路径，在选择下条路径时是按一定算法规律有意识地寻找最短路径。时是按一定算法规律有意识地寻找最短路径。l如，如，TSP问题中可预先知道当前城市到下一个目的地的距离。问题中可预先知道当前城市到下一个目的地的距离。2021/8/23精品精品 PPT 模板模板16蚁群算法与蚁群算法与TSP问题问题l初始的蚁群算法是基于图的蚁群算法初始的蚁群算法

17、是基于图的蚁群算法(graph-based ant system，GBAS)，2000年由年由Gutjahr在在Future Generation Computing Systems提出。提出。lTSP问题表示为问题表示为N个城市的有向图：个城市的有向图：G=(N, A)l目标函数目标函数 w=(i1, i2, , in)为城市为城市1, 2, , n的一个排列的一个排列 (dij)n n为城市间距离矩阵为城市间距离矩阵1,2,.,NnAi j i jN11llniilfwd2021/8/23精品精品 PPT 模板模板17蚁群算法与蚁群算法与TSP问题问题l设设m只蚂蚁在图的相邻节点间移动，协

18、作异步地得到解。只蚂蚁在图的相邻节点间移动，协作异步地得到解。l蚂蚁计算出下一步所有可达节点的一步转移概率，并按此蚂蚁计算出下一步所有可达节点的一步转移概率，并按此概率实现一步移动，依此往复。概率实现一步移动，依此往复。l一步转移概率由图中每条边上的两类参数决定：信息素值、一步转移概率由图中每条边上的两类参数决定：信息素值、可见度可见度(即先验值即先验值)。信息素的更新有信息素的更新有2种方式：种方式：l挥发挥发所有路径上信息素以一定比率减少所有路径上信息素以一定比率减少l增强增强给评价值给评价值“好好”(有蚂蚁走过有蚂蚁走过)的边增加信息素的边增加信息素 2021/8/23精品精品 PPT

19、模板模板18基于图的蚁群系统基于图的蚁群系统(GBAS)STEP 0 对对n个城市的个城市的TSP问题，问题，l城市间的距离矩阵为：城市间的距离矩阵为：(dij)n nl给给TSP图中的每一条弧图中的每一条弧(i, j)赋信息素初值：赋信息素初值： ij(0)=1/|A|l|A|：表示：表示图中弧图中弧(i, j)的数目的数目 ，即矩阵，即矩阵(dij)n n中不为零的数；中不为零的数；l设有设有m只蚂蚁工作，都从同一城市只蚂蚁工作，都从同一城市i0出发出发l当前最好解是：当前最好解是：w*=(1, 2, , n)l目标函数：目标函数：1,2,.,NnAi j i jN 11llniilf w

20、d2021/8/23精品精品 PPT 模板模板19基于图的蚁群系统基于图的蚁群系统(GBAS)STEP 1 (外循环外循环) l若满足算法停止规则，停止计算，输出计算得到的最好解若满足算法停止规则，停止计算，输出计算得到的最好解l给定外循环的最大数目，表明有足够的蚂蚁工作；给定外循环的最大数目，表明有足够的蚂蚁工作；l当前最优解连续当前最优解连续K次相同而停止，次相同而停止，K是给定的整数，表示算法已是给定的整数，表示算法已收敛；收敛；l给定优化问题的下界和误差值，当算法得到的目标值同下界之给定优化问题的下界和误差值，当算法得到的目标值同下界之差小于给定的误差值时，算法终止。差小于给定的误差值

21、时，算法终止。l否则使蚂蚁否则使蚂蚁s(1 s m)从起点从起点i0出发，用出发，用L(s)表示蚂蚁表示蚂蚁s行走行走的城市集合，初始的城市集合，初始L(s)为空集为空集 。2021/8/23精品精品 PPT 模板模板20基于图的蚁群系统基于图的蚁群系统(GBAS)STEP 2 (内循环内循环) 按蚂蚁按蚂蚁1 s m的顺序分别计算的顺序分别计算l在城市在城市i，若，若L(s)=N或或l|(i, l) A, l L(s)= ，完成蚂蚁完成蚂蚁s的的计算。计算。l否则，若否则，若T=l|(i, l) A, l L(s)-i0 ，以概率，以概率到达到达j，L(s)=L(s) j，il=jl若若L(

22、s) N且且T= ，则到达，则到达i0，L(s)=L(s) i0，il=i0重复重复STEP 2110ijijijl TkjTkpjT2021/8/23精品精品 PPT 模板模板21基于图的蚁群系统基于图的蚁群系统(GBAS)STEP 3 对蚂蚁对蚂蚁1 s m，l若若L(s)=N，按，按L(s)中城市的顺序计算路径长度；中城市的顺序计算路径长度；l若若L(s) N，路径长度置为无穷大，路径长度置为无穷大(即不可达即不可达)。l比较比较m只蚂蚁的路径长度，记走最短路径的蚂蚁为只蚂蚁的路径长度，记走最短路径的蚂蚁为t。l若若f(L(t)f(w*)，则，则w*=L(t) 2021/8/23精品精品

23、 PPT 模板模板22l修改信息素值修改信息素值l对固定的对固定的K 1，挥发因子挥发因子 k满足：满足：q加强加强w*路径上的信息素路径上的信息素q挥发其他路径上的信息素，经过挥发其他路径上的信息素，经过k次挥发，非最优路径的信息素逐次挥发，非最优路径的信息素逐渐减少至消失渐减少至消失。lk=k+1，重复重复STEP 1 11111,11,kkijijkijki jwwkki jw是上的一条弧不是上的一条弧1ln1,ln1kkkkkKk 2021/8/23精品精品 PPT 模板模板23关于关于信息素信息素蚂蚁以信息素的概率分布来决定从城市蚂蚁以信息素的概率分布来决定从城市i到到j的转移，信的

24、转移，信息素更新过程由两部分组成息素更新过程由两部分组成 挥发挥发每个连接上信息素逐渐减弱的过程由每个连接上信息素逐渐减弱的过程由(1- k-1) ij(k-1)表表示，该过程主要用于避免算法过快地向局部最优区域集中，示，该过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展。有助于搜索区域的扩展。l挥发过程是所有弧都进行的，与蚂蚁数量无关。挥发过程是所有弧都进行的，与蚂蚁数量无关。 增强增强观察蚁群中每只蚂蚁找到的路径，选择最优路径上观察蚁群中每只蚂蚁找到的路径，选择最优路径上的弧进行信息素增强，实现单个蚂蚁无法实现的集中行动。的弧进行信息素增强，实现单个蚂蚁无法实现的集中行动

25、。l增强过程是蚁群优化算法中可选的部分增强过程是蚁群优化算法中可选的部分。2021/8/23精品精品 PPT 模板模板24关于关于信息素信息素l信息素的更新分为离线和在线两种方式。信息素的更新分为离线和在线两种方式。 离线方式（同步更新方式）离线方式（同步更新方式）主要思想是在若干只蚂蚁完成主要思想是在若干只蚂蚁完成n个城市的访问后，统一对个城市的访问后，统一对残留信息进行更新处理。残留信息进行更新处理。 在线更新（异步更新方式）在线更新（异步更新方式）蚂蚁每走一步，立即回溯并且更新行走路径上的信息素。蚂蚁每走一步，立即回溯并且更新行走路径上的信息素。2021/8/23精品精品 PPT 模板模

26、板25基于图的蚁群系统基于图的蚁群系统(GBAS)l四个城市的非对称四个城市的非对称TSP问题问题010.5110111.55011110ijDd2021/8/23精品精品 PPT 模板模板26基于图的蚁群系统（基于图的蚁群系统（GBAS）l设共有设共有4只蚂蚁，都从城市只蚂蚁，都从城市A出发出发l挥发因子挥发因子l初始信息素记忆矩阵为：初始信息素记忆矩阵为：1,1,2,32kk 01 121 121 121 1201 121 1201 121 1201 121 121 121 1202021/8/23精品精品 PPT 模板模板27基于图的蚁群系统（基于图的蚁群系统（GBAS）l执行执行GBA

27、S算法的步骤算法的步骤2，设蚂蚁的行走路线分别为：，设蚂蚁的行走路线分别为：第一只第一只w1：ABCDAf(w1)=4第二只第二只w2：ACDBAf(w1)=3.5第三只第三只w3：ADCBAf(w1)=8第四只第四只w4：ABDCAf(w1)=4.5l当前最优解为当前最优解为w2也是截止到当前的最优解。也是截止到当前的最优解。2021/8/23精品精品 PPT 模板模板28基于图的蚁群系统（基于图的蚁群系统（GBAS）l更新信息素矩阵更新信息素矩阵 第一次外循环结束的状态第一次外循环结束的状态 11111,11,kkijijkijki jwwkki jw是上的一条弧不是上的一条弧 01 24

28、1 61 241 601 241 2411 241 1201 61 241 61 240 01 121 121 121 1201 121 1201 121 1201 121 121 121 1201,1,2,32kk2021/8/23精品精品 PPT 模板模板29基于图的蚁群系统（基于图的蚁群系统（GBAS）l重复外循环，由于重复外循环，由于w2已经是全局最优解，因此按已经是全局最优解，因此按STEP3的的信息素更新规则，无论蚂蚁如何行走，都只是对信息素更新规则，无论蚂蚁如何行走，都只是对w2路线上路线上的城市信息素进行增强，其他的城市信息素进行挥发。得的城市信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵到更新矩阵 01 485 241 4801 9611 481 965 2401 481 4811 4801 961 96231 481 4805 241 961 96011 481 485 241 4801 9611 481 9602021/8/23精品精品 PPT 模板模板30l9、 人的价值，在招收诱惑的一瞬间被决定。人的价值，在招收诱惑的一瞬间被决定。22.1.1222.1.12Wednesday, January 12, 2022l10、低头要有勇气，抬头要有低气。、低头要有勇气，抬头要有低气。*1/12/2022 9