第2讲_蚁群算法100712学习教案

1、会计学1第第2讲讲_蚁群算法蚁群算法(sun f)100712第一页，共27页。2022-5-252第1页/共26页第二页，共27页。2022-5-253 20 20世纪世纪5050年代年代(nindi)(nindi)中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。第2页/共26页第三页，共27页。2022-5-2542.1.1

2、2.1.1 蚁群优化算法蚁群优化算法(sun f)(sun f)起源起源 2/2 2/2 20 20世纪世纪9090年代意大利学者年代意大利学者M MDorigoDorigo，V VManiezzoManiezzo，A AColorniColorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法(sun f)(sun f)蚁群算法蚁群算法(sun f)(sun f)，是群智能理论研究领域的一种主要算法，是群智能理论研究领域的一种主要算法(sun f)(sun

3、 f)。用该方法求解。用该方法求解TSPTSP问题、分配问题、问题、分配问题、job-shop job-shop 调度问题，取得了较好的试验结果虽然研究时间不长，但是现在的研究显示出，蚁群算法调度问题，取得了较好的试验结果虽然研究时间不长，但是现在的研究显示出，蚁群算法(sun f)(sun f)在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法(sun f)(sun f)。第3页/共26页第四页，共27页。2022-5-255 这种方法能够被用于解决大多数优化问题或者能够转化

4、为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类(fn li)(fn li)、数据聚类、模式识别、电信、数据聚类、模式识别、电信QoSQoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径。管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径。第4页/共26页第五页，共27页。2022-5-256第5页/共26

5、页第六页，共27页。2022-5-257 与大多数基于梯度的应用优化算法不同，群智能与大多数基于梯度的应用优化算法不同，群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数用较多的评价函数(hnsh)(hnsh)，但是与梯度方法及传统，但是与梯度方法及传统的演化算法相比，其优点还是显著的，主要表现在以的演化算法相比，其优点还是显著的，主要表现在以下几个方面：下几个方面： 1 1 无集中控制约束，不会因个别个体的故障影响无集中控制约束，不会因个别个体的故障影响整个问题的求解，确保了系统具备更强的鲁棒性整个问题的求解，确保了系统具备更强

6、的鲁棒性 2 2 以非直接的信息交流方式确保了系统的扩展性以非直接的信息交流方式确保了系统的扩展性 3 3 并行分布式算法模型，可充分利用多处理器并行分布式算法模型，可充分利用多处理器 4 4 对问题定义的连续性无特殊要求对问题定义的连续性无特殊要求 5 5 算法实现简单算法实现简单 第6页/共26页第七页，共27页。2022-5-258第7页/共26页第八页，共27页。2022-5-259第8页/共26页第九页，共27页。2022-5-2510第9页/共26页第十页，共27页。2022-5-25112.2.1 2.2.1 蚁群算法蚁群算法(sun f)(sun f)原理原理 2/2 2/2

7、为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低。当后来的蚂蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大而其它的路径上激素浓度却会随着为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻

8、找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低。当后来的蚂蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大而其它的路径上激素浓度却会随着(su zhe)(su zhe)时间的流逝而消减。最终整个蚁群会找出最优路径。时间的流逝而消减。最终整个蚁群会找出最优路径。第10页/共26页第十一页，共27页。2022-5-2512 蚂蚁从蚂蚁从A A点出发，速度相同，食物在点出发，速度相同，食物在D D点，可能随点，可能随机

9、选择路线机选择路线ABDABD或或ACDACD。假设初始时每条分配路线一只。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过蚂蚁，每个时间单位行走一步，本图为经过9 9个时间个时间单位时的情形：走单位时的情形：走ABDABD的蚂蚁到达终点，而走的蚂蚁到达终点，而走ACD ACD 的的蚂蚁刚好蚂蚁刚好(gngho)(gngho)走到走到C C点，为一半路程。点，为一半路程。第11页/共26页第十二页，共27页。2022-5-2513 本图为从开始算起，经过本图为从开始算起，经过1818个时间单位时的情形：走个时间单位时的情形：走ABDABD的蚂蚁到达的蚂蚁到达(dod)(dod)

10、终点后得到食物又返回了起点终点后得到食物又返回了起点A A，而走，而走ACDACD的蚂蚁刚好走到的蚂蚁刚好走到D D点。点。第12页/共26页第十三页，共27页。2022-5-2514第13页/共26页第十四页，共27页。2022-5-25152.2.2 2.2.2 简化简化(jinhu)(jinhu)的蚂蚁寻食过程的蚂蚁寻食过程 4/4 4/4 若按以上规则继续，蚁群在若按以上规则继续，蚁群在ABDABD路线上再增派一只蚂蚁（共路线上再增派一只蚂蚁（共3 3只），而只），而ACD ACD 路线上仍然为一只蚂蚁。再经过路线上仍然为一只蚂蚁。再经过36 36 个时间单位后，两条线路上的信息素单位

11、积累为个时间单位后，两条线路上的信息素单位积累为2424和和6 6，比值为，比值为4 4：1 1。 若继续进行，则按信息素的指导，最终所有若继续进行，则按信息素的指导，最终所有(suyu)(suyu)的蚂蚁会放弃的蚂蚁会放弃ACD ACD 路线，而都选择路线，而都选择 ABD ABD路线。这也就是前面所提到的正反馈效应。路线。这也就是前面所提到的正反馈效应。第14页/共26页第十五页，共27页。2022-5-2516 基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题。基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题。 人工蚁群中把具有简单

12、功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。 两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路

13、径，而不是(b shi)(b shi)盲目的。盲目的。第15页/共26页第十六页，共27页。2022-5-2517第16页/共26页第十七页，共27页。2022-5-25182.2.4 2.2.4 实数实数(shsh)(shsh)编码的小生境蚁群算法（编码的小生境蚁群算法（NACANACA） 2/5 2/5 NACA NACA伪代码描述如下：伪代码描述如下： P0 = P0 = ？；？； % P0 % P0为全局转移概率为全局转移概率 P = P = ？；？； % P % P为信息素蒸发系数为信息素蒸发系数 For each ant For each ant Xi = (start+(end-

14、start) Xi = (start+(end-start)* *rand(1);rand(1);% % 随机产生蚂蚁的初始位置（限制在可行域内随机产生蚂蚁的初始位置（限制在可行域内start, endstart, end） Ti = k Ti = k* *f(Xi); % f(Xi); % 计算计算(j sun)(j sun)每个蚂蚁的初始信息素（正比于函数值），每个蚂蚁的初始信息素（正比于函数值），k k为比例常数为比例常数 End End第17页/共26页第十八页，共27页。2022-5-25192.2.4 2.2.4 实数实数(shsh)(shsh)编码的小生境蚁群算法（编码的小生境蚁

15、群算法（NACANACA） 3/5 3/5 DO % DO % 循环迭代循环迭代 T_Best = max(T); % T_Best = max(T); %求出最大信息素求出最大信息素 For each ant For each ant Probi = (T_Best-Ti)/T_Best; % Probi = (T_Best-Ti)/T_Best; % 求每个蚂蚁的下一步转移概率求每个蚂蚁的下一步转移概率(gil)(gil) End End For each ant For each ant If ProbiP0 If ProbiP0 Temp = Xi+min_step Temp = Xi

16、+min_step* *(rand(1)-0.5); % (rand(1)-0.5); % 局部搜索局部搜索 第18页/共26页第十九页，共27页。2022-5-25202.2.4 2.2.4 实数编码实数编码(bin m)(bin m)的小生境蚁群算法（的小生境蚁群算法（NACANACA） 4/5 4/5 For each ant For each ant If ProbiP0 If Probif(Xi) % If f(Temp)f(Xi) % 目标函数目标函数(hnsh)(hnsh)值比较值比较 Xi = Temp Xi = Temp；% % 更新蚂蚁的位置成功更新蚂蚁的位置成功 End

17、End End End For each ant For each ant Ti = (1-P) Ti = (1-P)* *Ti + kTi + k* *f(Xi); % f(Xi); % 更新每个蚂蚁的信息素更新每个蚂蚁的信息素 End End While ( While (设定的最大迭代次数设定的最大迭代次数) )第20页/共26页第二十一页，共27页。2022-5-25222.3 2.3 小生境蚁群算法小生境蚁群算法(sun f)(sun f)应用举例应用举例如图所示：如图所示：该函数该函数(hnsh)有多个局部极大点。有多个局部极大点。 计算下列计算下列(xili)函数的全局最大值：函

18、数的全局最大值：max f(x) = cos(2*pi*x)*cos(2*pi*y)*exp(-(x2+y2)/10) s.t. -1 x , y 1第21页/共26页第二十二页，共27页。2022-5-2523第22页/共26页第二十三页，共27页。2022-5-25243、利用、利用(lyng)蚁群算法求下面加权有向图中从蚁群算法求下面加权有向图中从A到到G的最短路：的最短路： AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766583338422213335526643第23页/共26页第二十四页，共27页。2022-5-252512345678910111213141516531368766583338422213335526643如给出编码如给出编码 1010100