蚁群优化算法PPT.pptx

《蚁群优化算法PPT.pptx》由会员分享，可在线阅读，更多相关《蚁群优化算法PPT.pptx（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1算法介绍算法介绍群智能算法 群智能是一种由简单智能的个体通过某种形式的聚集协同而表现出智能行为。它在没有集中控制，不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础。群智能算法通过模仿生物界的进化机理和群体协作行为而提出的仿生类随机搜索算法。去人工蜂群算法 细菌觅食算法 萤火虫算法粒子群算法 人工鱼群算法 鸟群算法第1页/共59页2蚁群算法的提出蚁群算法的提出 GambardellaMacro Dorigo第2页/共59页3蚁群算法的发展蚁群算法的发展2001年至今1996年-2001年意大利学者Dorigo1991年Dorigo1991年 启发各种改进算法的提出，应用领域更广 引

2、起学者关注，在应用领域得到拓宽ACO首次被系统的提出自然界中真实蚁群集体行为第3页/共59页4蚁群算法原理蚁群算法原理如何找到最短路径？F类比：大肠杆菌在人体肠道内觅食的过程信息素：信息素多的地方显然经过这里的蚂蚁多，因而会有更多的蚂蚁聚集过来。正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。第4页/共59页5蚁群算法原理蚁群算法原理自然蚂蚁的智能特点 第5页/共59页6蚁群算法原理蚁群算法原理人工蚂蚁的模型 第6页/共59页7蚁群算法原理蚁群算法原理自然蚁群与人工蚁群 相似之处在于：都是优先选择信息素浓度大的路径。两者的区别在于：（1）人工蚁群有一定的记忆能力，能够记忆

3、已经访问过的节点。（2）人工蚁群选择路径时不是盲目的，而是按一定规律有意识地寻找最短路径。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。第7页/共59页8求解组合优化问题的蚁群算法求解组合优化问题的蚁群算法第8页/共59页9基本蚁群算法基本蚁群算法u 蚂蚁k(k=1,2，,m)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市，设 表示t时刻蚂蚁k从城市i转移到城市j的概率，其计算公式为：u 信息更新公式为：第9页/共59页10基本蚁群算法基本蚁群算法u 针对蚂蚁释放信息素问题，等人曾给出3中不同的模型，分别为蚁周系统、蚁量系统和蚁密系统，其计算公式如下：其中，Q为常数，

4、表示蚂蚁循环一次所释放的信息素总量；L为第k只蚂蚁经过路径的长度；d为城市间的距离。第10页/共59页11蚁群算法的主要特点蚁群算法的主要特点u 采用分布式控制 u 每个个体只能感知局部的信息 u 个体可以改变环境 u 具有自组织性 u 是一类概率型的全局搜索方法 u 优化过程不依赖于优化问题本身的严格数学性质 u 是一种基于多主体(Multi-Agent)的智能算法 u 具有潜在的并行性 第11页/共59页12蚁群算法参数选择蚁群算法参数选择蚁群数量m的选择 u 子集越大信息正反馈的作用不明显，搜索的随机性增强，造成收敛速度变慢;u 反之，子集越小，搜索的随机性减弱，虽然收敛速度较快，但是会

5、使算法的全局性能降低，影响算法的稳定性。信息素挥发度 的选取 u 信息素挥发度的大小对蚁群算法的收敛性能影响极大;u 当 比较小时，搜索的全局性好，但收敛速度变慢;u 当 比较大时，收敛速度比较快，但是容易陷入局部最优。第12页/共59页13蚁群算法参数选择蚁群算法参数选择因子和的选取 u 启发式因子的大小则反映了在蚁群路径搜索中的随机性因素作用的强度;u 启发式因子的大小反映了在蚁群路径搜索中确定性因素作用的强度。总信息量Q的选取 u 总信息量Q越大，可以加强蚁群搜索时的正反馈性能，有助于算法的快速收敛。蚂蚁的初始分布 u 所有蚂蚁初始时刻放在同一个城市;u 蚂蚁分布在不同的城市中。第13页

6、/共59页14蚁群算法时间复杂度及蚁群算法时间复杂度及优缺点优缺点u M.Dorigo曾经对经典的TSP问题求解复杂度进行过深入的研究，所得到的经验结果表明，算法的时间复杂度为O(NCn2m)，NC表示迭代次数，n表示城市数，m则表示参与搜索的蚂蚁数量。当参与搜索的蚂蚁数量m大致与规模大小n相等时，算法的时间复杂度变为O(NCn3)较强的鲁棒性 分布式计算 易于与其他方法结合 u需要较长的搜索时间u容易出现停滞现第14页/共59页15带精英策略的蚂蚁系统带精英策略的蚂蚁系统每次循环之后给予最优解以额外的信息素量这样的解被称为全局最优解（global-best solution）找出这个解的蚂蚁

7、被称为精英蚂蚁(elitist ants)带精英策略的蚂蚁系统（Ant System with elitist strategy,ASelite）是最早的改进蚂蚁系统。遗传算法中的精英策略 蚂蚁系统中的精英策略 传统的遗传算法可能会导致最适应个体的遗传信息丢失精英策略的思想是保留住一代中的最适应个体第15页/共59页16带精英策略的蚂蚁系统带精英策略的蚂蚁系统信息素根据下式进行更新 其中第16页/共59页17带精英策略的蚂蚁系统带精英策略的蚂蚁系统 表示精英蚂蚁引起的路径(i,j)上的信息素量的增加 是所找出的最优解的路径长度 特点：是精英蚂蚁的个数 u 可以使蚂蚁系统找出更优的解u 找到这些

8、解的时间更短 u 精英蚂蚁过多会导致搜索早熟收敛第17页/共59页18蚁群系统蚁群系统 蚁群系统的状态转移规则 其中，S根据下列公式得：到u 一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市s：第18页/共59页19蚁群系统蚁群系统 蚁群系统全局更新原则 u 只有全局最优的蚂蚁才被允许释放信息素。u 目的：使蚂蚁的搜索主要集中在当前循环为止所找出的最好路径领域内。u 全局更新在所有蚂蚁都完成它们的路径之后执行，用下式对所建立的路径进行更新：第19页/共59页20蚁群系统蚁群系统 蚁群系统局部更新原则 u 类似于蚁密和蚁量模型中的更新规则 u 蚂蚁应用下列局部更新规则对它们所

9、经过的边进行信息素更新u 实验发现，可以产生好的结果，其中n是城市的数量，是由最近的邻域启发产生的一个路径长度u 局部更新规则可以有效地避免蚂蚁收敛到同一路径第20页/共59页21Max-Min Ant System（MMAS）信息素轨迹更新原则 u在MMAS中，只有一只蚂蚁用于在每次循环后更新信息轨迹。经修改的轨迹更新原则如下：u 表示迭代最优解或全局最优解的值。u在蚁群算法中主要使用全局最优解，而在MMAS中则主要使用迭代最优解。第21页/共59页22Max-Min Ant System（MMAS）信息素轨迹的限制 uMMAS对信息素轨迹的最小值和最大值分别施加了 和 的限制，从而使得对所

10、有信息素轨迹 ，有u 的选取要基于两点假设：1.最优解在搜索停滞发生之前不久被找出。2.对解构造的主要影响是由信息素轨迹的上限与下限之间的相对差异决定第22页/共59页23Max-Min Ant System（MMAS）信息素轨迹的平滑化u基本思想：通过增加选择有着低强度信息素轨迹量解元素的概率以提高探索新解的能力u平滑机制有助于对搜索空间进行更有效的探索第23页/共59页24Max-Min Ant System（MMAS）第24页/共59页25蚁群算法的应用蚁群算法的应用第25页/共59页26蚁群算法的应用蚁群算法的应用TSP问题u问题描述：旅行商按一定的顺序访问n个城市，使得每个城市都被访

11、问且仅能被访问一次而使花费代价最小，从图论的观点来看，就是找出一个最短的封闭回路。uTSP的求解是NP-hard问题。随着城市数目的增多,问题空间将呈指数级增长uTSP在许多工程领域具有广泛的应用价值，例如电路板布线、机器人控制、交通路由等。第26页/共59页27蚁群系统在蚁群系统在TSPTSP问题中的应用问题中的应用第27页/共59页28蚁群算法求解蚁群算法求解TSPTSP问题问题下面以TSP为例说明基本蚁群算法模型。u首先将m只蚂蚁随机放置在n个城市，位于城市i的第k只蚂蚁选择下一个城市j的概率为:u 表示边（i，j）上的信息素浓度；是启发信息，d是城市i和j之间的距离；和反映了信息素与启

12、发信息的相对重要性；表示蚂蚁k已经访问过的城市列表。第28页/共59页29蚁群算法求解蚁群算法求解TSPTSP问题问题u当所有蚂蚁完成周游后，按以下公式进行信息素更新。u其中，为小于1的常数，表示信息的持久性。u其中，Q为常数；表示第k只蚂蚁在本次迭代中走过的路径长度。第29页/共59页30InitializationDistribute the ants,Modify the tabu Calculate the probability of moving between citiesi+Update pheromone between cities Meet the requirement

13、 of the solution Number of traverse city i=1outputMove to j and modify the tabuNYCalculate the distance each ant walks the loopYNEach ant choose the next city 第30页/共59页31实现过程实现过程第31页/共59页32实现过程实现过程第32页/共59页33实现过程实现过程第33页/共59页34实现过程实现过程第34页/共59页35中国旅行商问题中国旅行商问题1.5602e+04ACATSP(C,100,10,1,5,0.1,100)第3

14、5页/共59页36遗传算法和蚁群算法在遗传算法和蚁群算法在求解求解TSPTSP问题上的对比分析问题上的对比分析第36页/共59页37细菌觅食机理 趋向性操作设细菌种群大小为S，一个细菌所处的位置表示一个问题的候选解，细菌i的信息用D维向量表示为细菌i在第j次趋向性操作、第k次复制操作和第l次迁徙操作之后的位置表示为细菌i的每一步趋向性操作表示如下：C(i)0 表示向前游动的步长单位 表示旋转后选择的一个随机前进方向第37页/共59页38细菌觅食机理 聚群行为 “抱团”在细菌趋向最佳生存环境的过程中，菌落的个体根据自身当前的适应度值对其他所有细菌释放信息，吸引素和排斥素，即信息素。同时，此细菌接

15、受其他所有细菌的释放的吸引素和排斥素，在其所有信息素的作用下修改自己的适应值。保证向局部环境变好的位置移动。在一个菌落中，上述个体间的信息素浓度计算方法可表示为：第38页/共59页39算法简介第39页/共59页40细菌觅食机理 聚群行为 “抱团”其中，Jcc(,P(j,k,l)是一种随种群分布状态变化的目标函数，当它被叠加到问题的实际目标函数时，就表示了细菌与最佳个体的相对距离变化趋势；S 表示种群的大小；p指明了优化问题的维度。F类比：其他群智能算法的聚群行为：l花蜜源比较差的侦查蜂转向花蜜源比较好的侦查蜂，变成跟随蜂 -舞蹈l 亮度比较弱的萤火虫转向亮度比较好的萤火虫-荧光素第40页/共5

16、9页41细菌觅食机理 复制（优胜劣汰）经过一个周期的趋向操作后，菌落进行复制操作。该操作遵循达尔文的优胜劣汰原理。首先，菌落依据适应度值排序，获得足够多食物（适应度函数较优）的个体进行分裂，而能量不足的个体将会死去。同时，分裂的个体和死去的个体数量相等，这保证了种群数量的稳定。产生的新一代个体进入下一个趋向操作周期。F其他群智能算法的淘汰机制：l花蜜源比较差的侦查蜂转向花蜜源比较好的侦查蜂过程 淘汰花蜜源比较差的蜜蜂l萤火虫亮度比较弱的淘汰第41页/共59页42细菌觅食机理 前提经过复制操作后算法的种群大小不变第42页/共59页43细菌觅食机理 驱散行为 几次复制操作后，菌落将呈现几个聚集簇，

17、种群多样性退化，“早熟”。为了避免这种现象，BFO 算法引入了变异操作驱散行为。该操作模拟了细菌随水流或其他生物迁徙到新环境的生物现象，其运行模式是菌落中的一些个体以小概率（通常选择 25%）重新在搜索空间中随机选择一个位置。经过驱散操作后新一代个体进入新的趋向操作周期。第43页/共59页44聚群与驱散第44页/共59页45输入：运行相关的参数组初始化（菌落在搜索环境中随机散开，并初始化每一个个体的健康指标向量，三层循环的l,j,k索引均为0）驱散索引：l=l+1jNc?复制（依据health进行排序，淘汰后一半，复制前一半）驱散（对每一个细菌：取一随机数，若小于驱散概率，则重新初始化）kNr

18、e?lNed?复制索引:k=k+1寻优终止输出环境最好的位置和相应值趋向索引:j=j+1种群趋向是重初始趋向索引重初始化趋向，复制索引j=0,k=0第45页/共59页46细菌觅食算法参数问题F种群大小S：S小，算法的计算速度快，但种群的多样性降低，影响算法的优化性能；S大，避免算法陷入局部极小值，但计算量增加，收敛速度变慢。F游动步长C：C不小于某一特定值，能有效避免算法过早收敛；C太大，降低算法的收敛速度。F趋向性操作次数Nc:Nc越大，搜索更细致，但复杂度增加；Nc越小，算法容易陷入局部最小值。F复制操作次数Nre：Nre太大，会增加算法的复杂度；Nre太小，算法容易早熟收敛。F迁徙（驱散

19、）操作Ned:Ned 越大，避免算法陷入早熟，但复杂度随之增加；Ned越小，算法没有发挥迁徙操作的随机搜索作用。第46页/共59页47细菌觅食算法的改进自适应步长调整策略 在趋向行为中，原始BFO使用固定步长求解问题不利于算法的收敛。因此提出了一种基于细菌拥挤度的自适应步长调整策略。当 crowd较小时，细菌以较大的步长寻优;当crowd 较大时，细菌以较小的步长寻优。这样能够保证算法在优化初期有很强的全局搜索能力，在优化后期有很强的局部开采能力。第47页/共59页48细菌觅食算法的改进基于环境感知的细菌觅食优化算法 在趋向行为中，赋予细菌对周围细菌状态进行感知。在执行中，所有细菌按照适应度分

20、成两类：l优于适应度平均值的，通过追踪最优细菌进行搜索；l劣于适应度平均值的，通过追踪细菌群体中心位置进行搜索。第一种情况：相当于细菌位置的精细搜索。第二种情况：有助于全局最优和快速收敛。第48页/共59页49细菌觅食算法的改进具有协同思想的细菌觅食优化算法 针对细菌趋向行为中随机翻转和游动环节，引入PSO算法粒子向个体和社会学习的思想，赋予细菌能够记忆当前细菌群体的最优位置和最优解。l在翻转过程中适应度变差，则向群体最优学习。l若随机转向失效，则反方向学习。除此之外：F基于免疫进化的细菌觅食优化算法F基于高斯分布的细菌觅食算法第49页/共59页50细菌觅食算法的应用-JSP作业调度问题车间调

21、度问题（Job-Scheduling Problem，简称JSP），指车间有一些机器和一些工件，每个工件都有其特定的加工顺序，现用m台机器加工n个工件，每个工件都有若干有序操作组成，每个操作必须在指定的机器上才能完成。每台机器在同一时刻只能进行一个工序操作。第50页/共59页51细菌觅食算法的应用-JSP作业调度问题第51页/共59页52细菌觅食算法的应用-JSP作业调度问题第52页/共59页53细菌觅食算法的应用-JSP作业调度问题实际实验的Benchmark算例第53页/共59页54细菌觅食算法的应用-JSP作业调度问题BFO算法的JSP问题性能测试（minF=59）第54页/共59页55细菌觅食算法的应用-JSP作业调度问题环境感知BFO算法的JSP问题性能测试（minF=58）第55页/共59页56细菌觅食算法的应用-JSP作业调度问题具有协同思想的BFO算法的JSP问题性能测试（minF=59）第56页/共59页57细菌觅食算法的应用-JSP作业调度问题BFO算法与PSO算法30次随机测试结果比较第57页/共59页58第58页/共59页感谢您的观看！第59页/共59页