《蚁群优化算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《蚁群优化算法ppt课件.ppt（59页珍藏版）》请在三一办公上搜索。
1、蚁群优化算法Ant Colony Optimization,2,算法介绍,群智能算法 群智能是一种由简单智能的个体通过某种形式的聚集协同而表现出智能行为。它在没有集中控制，不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础。群智能算法通过模仿生物界的进化机理和群体协作行为而提出的仿生类随机搜索算法。,去,人工蜂群算法 细菌觅食算法 萤火虫算法粒子群算法 人工鱼群算法 鸟群算法,3,蚁群算法的提出,Gambardella,Macro Dorigo,4,蚁群算法的发展,2001年至今,1996年-2001年,意大利学者Dorigo1991年Dorigo1991年,启发,5,蚁群算法原理,
2、如何找到最短路径 ？,类比：大肠杆菌在人体肠道内觅食的过程,信息素：信息素多的地方显然经过这里的蚂蚁多，因而会有更多的蚂蚁聚集过来。正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。,6,蚁群算法原理,自然蚂蚁的智能特点,7,蚁群算法原理,人工蚂蚁的模型,8,蚁群算法原理,自然蚁群与人工蚁群,相似之处在于：都是优先选择信息素浓度大的路径。两者的区别在于： （1）人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。 （2）人工蚁群选择路径时不是盲目的，而是按一定规律有意识地寻找最短路径。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。,9,求解组合优化问题的蚁群
3、算法,10,基本蚁群算法,蚂蚁k(k=1,2，,m)根据各个城市间连接路径上的信息素浓度决定其下一个访问城市，设 表示t时刻蚂蚁k从城市i转移到城市j的概率，其计算公式为：,信息更新公式为：,11,基本蚁群算法,针对蚂蚁释放信息素问题，M.Dorigo等人曾给出3中不同的模型，分别为蚁周系统、蚁量系统和蚁密系统，其计算公式如下：,1.Ant-cycle,2.Ant-quantity,3.Ant-density,其中，Q为常数，表示蚂蚁循环一次所释放的信息素总量；L为第k只蚂蚁经过路径的长度；d为城市间的距离。,12,蚁群算法的主要特点,采用分布式控制,每个个体只能感知局部的信息,个体可以改变环
4、境,具有自组织性,是一类概率型的全局搜索方法,优化过程不依赖于优化问题本身的严格数学性质,是一种基于多主体(Multi-Agent)的智能算法,具有潜在的并行性,13,蚁群算法参数选择,蚁群数量m的选择,子集越大信息正反馈的作用不明显，搜索的随机性增强，造成收敛速度变慢; 反之，子集越小，搜索的随机性减弱，虽然收敛速度较快，但是会使算法的全局性能降低，影响算法的稳定性。,信息素挥发度 的选取,信息素挥发度的大小对蚁群算法的收敛性能影响极大; 当 比较小时，搜索的全局性好，但收敛速度变慢; 当 比较大时，收敛速度比较快，但是容易陷入局部最优。,14,蚁群算法参数选择,因子和的选取,启发式因子的大
5、小则反映了在蚁群路径搜索中的随机性因素作用的强度; 启发式因子的大小反映了在蚁群路径搜索中确定性因素作用的强度。,总信息量Q的选取,总信息量Q越大，可以加强蚁群搜索时的正反馈性能，有助于算法的快速收敛。,蚂蚁的初始分布,所有蚂蚁初始时刻放在同一个城市; 蚂蚁分布在不同的城市中。,15,蚁群算法时间复杂度及优缺点,M.Dorigo曾经对经典的TSP问题求解复杂度进行过深入的研究，所得到的经验结果表明，算法的时间复杂度为O(NCn2m)，NC表示迭代次数，n表示城市数，m则表示参与搜索的蚂蚁数量。当参与搜索的蚂蚁数量m大致与规模大小n相等时，算法的时间复杂度变为O(NCn3),较强的鲁棒性,分布式
6、计算,易于与其他方法结合,需要较长的搜索时间,容易出现停滞现,16,带精英策略的蚂蚁系统,每次循环之后给予最优解以额外的信息素量这样的解被称为全局最优解（global-best solution）找出这个解的蚂蚁被称为精英蚂蚁(elitist ants),带精英策略的蚂蚁系统（Ant System with elitist strategy, ASelite）是最早的改进蚂蚁系统。,遗传算法中的精英策略,蚂蚁系统中的精英策略,传统的遗传算法可能会导致最适应个体的遗传信息丢失精英策略的思想是保留住一代中的最适应个体,17,带精英策略的蚂蚁系统,信息素根据下式进行更新,其中,18,带精英策略的蚂蚁
7、系统,表示精英蚂蚁引起的路径(i, j)上的信息素量的增加,是所找出的最优解的路径长度 特点：,是精英蚂蚁的个数,可以使蚂蚁系统找出更优的解 找到这些解的时间更短 精英蚂蚁过多会导致搜索早熟收敛,19,蚁群系统,蚁群系统的状态转移规则,其中，S根据下列公式得：到,一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市s：,20,蚁群系统,蚁群系统全局更新原则,只有全局最优的蚂蚁才被允许释放信息素。,目的：使蚂蚁的搜索主要集中在当前循环为止所找出的最好路径领域内。,全局更新在所有蚂蚁都完成它们的路径之后执行，用下式对所建立的路径进行更新：,21,蚁群系统,蚁群系统局部更新原则,类似
8、于蚁密和蚁量模型中的更新规则,蚂蚁应用下列局部更新规则对它们所经过的边进行信息素更新,实验发现， 可以产生好的结果，其中n是城市的数量， 是由最近的邻域启发产生的一个路径长度,局部更新规则可以有效地避免蚂蚁收敛到同一路径,22,Max-Min Ant System（MMAS）,信息素轨迹更新原则,在MMAS中，只有一只蚂蚁用于在每次循环后更新信息轨迹。经修改的轨迹更新原则如下：,表示迭代最优解或全局最优解的值。在蚁群算法中主要使用全局最优解，而在MMAS中则主要使用迭代最优解。,23,Max-Min Ant System（MMAS）,信息素轨迹的限制,MMAS对信息素轨迹的最小值和最大值分别施
9、加了 和 的限制，从而使得对所有信息素轨迹 ，有,的选取要基于两点假设：1.最优解在搜索停滞发生之前不久被找出。2.对解构造的主要影响是由信息素轨迹的上限与下限之间的相对差异决定,24,Max-Min Ant System（MMAS）,信息素轨迹的平滑化,基本思想：通过增加选择有着低强度信息素轨迹量解元素的概率以提高探索新解的能力,平滑机制有助于对搜索空间进行更有效的探索,25,Max-Min Ant System（MMAS）,26,蚁群算法的应用,27,蚁群算法的应用,TSP问题,问题描述：旅行商按一定的顺序访问n个城市，使得每个城市都被访问且仅能被访问一次而使花费代价最小，从图论的观点来看
10、，就是找出一个最短的封闭回路。,TSP的求解是NP-hard问题。随着城市数目的增多,问题空间将呈指数级增长,TSP在许多工程领域具有广泛的应用价值，例如电路板布线、机器人控制、交通路由等。,28,蚁群系统在TSP问题中的应用,29,蚁群算法求解TSP问题,下面以TSP为例说明基本蚁群算法模型。,首先将m只蚂蚁随机放置在n个城市，位于城市i的第k只蚂蚁选择下一个城市j的概率为:,表示边（i，j）上的信息素浓度； 是启发信息，d是城市i和j之间的距离；和反映了信息素与启发信息的相对重要性； 表示蚂蚁k已经访问过的城市列表。,30,蚁群算法求解TSP问题,当所有蚂蚁完成周游后，按以下公式进行信息素
11、更新。,其中，为小于1的常数，表示信息的持久性。,其中，Q为常数； 表示第k只蚂蚁在本次迭代中走过的路径长度。,31,Initialization,Distribute the ants, Modify the tabu,Calculate the probability of moving between cities,i+,Update pheromone between cities,i=city.N,Meet the requirement of the solution,Number of traverse city i=1,output,Move to j and modify t
12、he tabu,N,Y,Calculate the distance each ant walks the loop,Y,N,Each ant choose the next city,32,实现过程,33,实现过程,34,实现过程,35,实现过程,36,中国旅行商问题,1.5602e+04,ACATSP(C,100,10,1,5,0.1,100),37,遗传算法和蚁群算法在求解TSP问题上的对比分析,38,细菌觅食机理,趋向性操作,设细菌种群大小为S，一个细菌所处的位置表示一个问题的候选解，细菌i的信息用D维向量表示为,细菌i在第j次趋向性操作、第k次复制操作和第l次迁徙操作之后的位置表示为
13、,细菌i的每一步趋向性操作表示如下：,C(i)0 表示向前游动的步长单位,表示旋转后选择的一个随机前进方向,39,细菌觅食机理,聚群行为 “抱团” 在细菌趋向最佳生存环境的过程中，菌落的个体根据自身当前的适应度值对其他所有细菌释放信息，吸引素和排斥素，即信息素。同时，此细菌接受其他所有细菌的释放的吸引素和排斥素，在其所有信息素的作用下修改自己的适应值。保证向局部环境变好的位置移动。在一个菌落中，上述个体间的信息素浓度计算方法可表示为：,40,算法简介,41,细菌觅食机理,聚群行为 “抱团” 其中，Jcc(,P(j,k,l)是一种随种群分布状态变化的目标函数，当它被叠加到问题的实际目标函数时，就
14、表示了细菌与最佳个体的相对距离变化趋势；S 表示种群的大小；p指明了优化问题的维度。,类比：其他群智能算法的聚群行为：花蜜源比较差的侦查蜂转向花蜜源比较好的侦查蜂，变成跟随蜂 -舞蹈 亮度比较弱的萤火虫转向亮度比较好的萤火虫-荧光素,42,细菌觅食机理,复制（优胜劣汰） 经过一个周期的趋向操作后，菌落进行复制操作。该操作遵循达尔文的优胜劣汰原理。首先，菌落依据适应度值排序，获得足够多食物（适应度函数较优）的个体进行分裂，而能量不足的个体将会死去。同时，分裂的个体和死去的个体数量相等，这保证了种群数量的稳定。产生的新一代个体进入下一个趋向操作周期。,其他群智能算法的淘汰机制：花蜜源比较差的侦查蜂
15、转向花蜜源比较好的侦查蜂过程 淘汰花蜜源比较差的蜜蜂萤火虫亮度比较弱的淘汰,43,细菌觅食机理,前提,经过复制操作后算法的种群大小不变,44,细菌觅食机理,驱散行为 几次复制操作后，菌落将呈现几个聚集簇，种群多样性退化，“早熟”。为了避免这种现象，BFO 算法引入了变异操作驱散行为。该操作模拟了细菌随水流或其他生物迁徙到新环境的生物现象，其运行模式是菌落中的一些个体以小概率（通常选择 25%）重新在搜索空间中随机选择一个位置。经过驱散操作后新一代个体进入新的趋向操作周期。,45,聚群与驱散,46,输入：运行相关的参数组,初始化（菌落在搜索环境中随机散开，并初始化每一个个体的健康指标向量，三层循
16、环的l,j,k索引均为0）,驱散索引：l=l+1,jNc?,复制（依据health进行排序，淘汰后一半，复制前一半）,驱散（对每一个细菌：取一随机数，若小于驱散概率，则重新初始化）,kNre?,lNed?,复制索引:k=k+1,寻优终止输出环境最好的位置和相应值,趋向索引:j=j+1,种群趋向,重初始趋向索引,重初始化趋向，复制索引j=0,k=0,47,细菌觅食算法参数问题,种群大小S：S小，算法的计算速度快，但种群的多样性降低，影响算法的优化性能；S大，避免算法陷入局部极小值，但计算量增加，收敛速度变慢。游动步长C：C不小于某一特定值，能有效避免算法过早收敛； C太大，降低算法的收敛速度。趋
17、向性操作次数Nc:Nc越大，搜索更细致，但复杂度增加；Nc越小，算法容易陷入局部最小值。复制操作次数Nre：Nre太大，会增加算法的复杂度；Nre太小，算法容易早熟收敛。迁徙（驱散）操作Ned:Ned 越大，避免算法陷入早熟，但复杂度随之增加；Ned越小，算法没有发挥迁徙操作的随机搜索作用。,48,细菌觅食算法的改进,自适应步长调整策略 在趋向行为中，原始BFO使用固定步长求解问题不利于算法的收敛。因此提出了一种基于细菌拥挤度的自适应步长调整策略。,当 crowd较小时，细菌以较大的步长寻优; 当crowd 较大时，细菌以较小的步长寻优。这样能够保证算法在优化初期有很强的全局搜索能力，在优化后
18、期有很强的局部开采能力。,49,细菌觅食算法的改进,基于环境感知的细菌觅食优化算法 在趋向行为中，赋予细菌对周围细菌状态进行感知。在执行中，所有细菌按照适应度分成两类：优于适应度平均值的，通过追踪最优细菌进行搜索；劣于适应度平均值的，通过追踪细菌群体中心位置进行搜索。,第一种情况：相当于细菌位置的精细搜索。第二种情况：有助于全局最优和快速收敛。,50,细菌觅食算法的改进,具有协同思想的细菌觅食优化算法 针对细菌趋向行为中随机翻转和游动环节，引入PSO算法粒子向个体和社会学习的思想，赋予细菌能够记忆当前细菌群体的最优位置和最优解。在翻转过程中适应度变差，则向群体最优学习。若随机转向失效，则反方向
19、学习。,除此之外：基于免疫进化的细菌觅食优化算法基于高斯分布的细菌觅食算法,51,细菌觅食算法的应用-JSP作业调度问题,车间调度问题（Job-Scheduling Problem，简称JSP），指车间有一些机器和一些工件，每个工件都有其特定的加工顺序，现用m台机器加工n个工件，每个工件都有若干有序操作组成，每个操作必须在指定的机器上才能完成。每台机器在同一时刻只能进行一个工序操作。,52,细菌觅食算法的应用-JSP作业调度问题,53,细菌觅食算法的应用-JSP作业调度问题,54,细菌觅食算法的应用-JSP作业调度问题,实际实验的Benchmark算例,55,细菌觅食算法的应用-JSP作业调度问题,BFO算法的JSP问题性能测试（minF=59）,56,细菌觅食算法的应用-JSP作业调度问题,环境感知BFO算法的JSP问题性能测试（minF=58）,57,细菌觅食算法的应用-JSP作业调度问题,具有协同思想的BFO算法的JSP问题性能测试（minF=59）,58,细菌觅食算法的应用-JSP作业调度问题,BFO算法与PSO算法30次随机测试结果比较,59,谢谢！,
