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