第7章 群智能算法及其应用（AI应用3版）

《第7章 群智能算法及其应用（AI应用3版）》由会员分享，可在线阅读，更多相关《第7章 群智能算法及其应用（AI应用3版）（93页珍藏版）》请在金锄头文库上搜索。

1、Artificial Intelligence Principles and Applications第第 7 章章 群智能算法及其应用群智能算法及其应用教材：教材： 王万良王万良人工智能及其应用人工智能及其应用（第（第3版）版） 高等教育出版社，高等教育出版社，2016. 22第7章 群智能算法及其应用7.1 群智能算法产生的背景群智能算法产生的背景o7.2 粒子群优化算法粒子群优化算法 o7.3 量子粒子群优化算法量子粒子群优化算法 o7.4 粒子群优化算法的应用粒子群优化算法的应用o7.5 基本蚁群算法基本蚁群算法o7.6 改进蚁群算法改进蚁群算法 o7.7 蚁群算法的应用蚁群算法的应用

2、3 7.1 群智能算法产生的背景群智能算法产生的背景 群群智智能能算算法法（swarm algorithms，SI）：受动物群体智能启发的算法。 群体智能：由简单个体组成的群落与环境以及个体之间的互动行为。 群智能算法包括：粒子群优化算法、蚁群算法、蜂群算法、4 7.1 群智能算法产生的背景群智能算法产生的背景5第7章 群智能算法及其应用o7.1 群智能算法产生的背景群智能算法产生的背景7.2 粒子群优化算法粒子群优化算法 o7.3 量子粒子群优化算法量子粒子群优化算法 o7.4 粒子群优化算法的应用粒子群优化算法的应用o7.5 基本蚁群算法基本蚁群算法o7.6 改进蚁群算法改进蚁群算法 o7

3、.7 蚁群算法的应用蚁群算法的应用67.2 粒子群优化算法o产生背景产生背景粒子群优化（Particle Swarm Optimization, PSO）算法是由美国普渡大学的Kennedy和Eberhart于1995年提出，它的基本概念源于对鸟群觅食行为的研究。o设想这样一个场景：设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最最简单有效的就是搜寻目前离食物最近的鸟的周围区域。简单有效的就是搜寻目前离食物最近的鸟的周围区域。77.2 粒子群优化算法7.2.1 粒子群优化算法的

4、基本原理粒子群优化算法的基本原理7.2.2 粒子群优化算法的参数分析粒子群优化算法的参数分析87.2.1 粒子群优化算法的基本原理粒子群优化算法的基本原理 o基本思想基本思想将每个个体看作n维搜索空间中一个没有体积质量的粒子，在搜索空间中以一定的速度飞行，该速度决定粒子飞行的方向和距离。所有粒子还有一个由被优化的函数决定的适应值。o基本基本原理原理PSO初始化为一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解称为个体极值。另个一是整个种群目前找到的最优解，这个解称为全局极值。97.2.1 粒子群优化算法的基本原理

5、粒子群优化算法的基本原理 o算法定义算法定义在n 维连续搜索空间中，对粒子群中的第i (i=1, 2, , m)个粒子进行定义： ：表示搜索空间中粒子的当前位置。 ：表示该粒子至今所获得的具有最优适应度 的位置。 ：表示该粒子的搜索方向。10 7.2.1 粒子群优化算法的基本原理粒子群优化算法的基本原理 每个粒子经历过的最优位置（pbest）记为 ，群体经历过的最优位置(gbest)记为 ，则基本的PSO算法为：（7.1a）（7.1b）其中， 是惯性权重因子。1 ，2 是加速度常数，均为非负值。 和 为0, a1、0, a2范围内的具有均匀分布的随机数，a1 与 a2 为相应的控制参数。11

6、7.2.1 粒子群优化算法的基本原理粒子群优化算法的基本原理 （7.1a）o式式(7.1a)(7.1a)右边的第右边的第1 1部分是粒子在前一时刻的速度；部分是粒子在前一时刻的速度；o第第2 2部部分分为为个个体体“认认知知”分分量量，表表示示粒粒子子本本身身的的思思考考，将现有的位置和曾经经历过的最优位置相比。将现有的位置和曾经经历过的最优位置相比。o第第3 3部部分分是是群群体体“社社会会(social)”(social)”分分量量，表表示示粒粒子子间间的信息共享与相互合作。的信息共享与相互合作。o1 ，2分分别别控控制制个个体体认认知知分分量量和和群群体体社社会会分分量量相相对对贡献的学

7、习率。贡献的学习率。o随机系数随机系数增加搜索方向的随机性和算法多样性。增加搜索方向的随机性和算法多样性。127.2.1 粒子群优化算法的基本原理粒子群优化算法的基本原理 基于学习率基于学习率 ， ， Kennedy给出以下出以下4种种类型的型的PSO模型：模型：若若 1 1 0 0， 2 2 0 0，则称该算法为PSO全模型。若若 1 1 0 0， 2 2 = = 0 0，则称该算法为PSO认知模型。若若 1 = 1 = 0 0， 2 2 0 0，则称该算法为PSO社会模型。若若 1 =1 = 0 0， 2 2 0 0且且g g i i，则称该算法为PSO无私模型。137.2.1 粒子群优化

8、算法的基本原理 粒子群优化粒子群优化算法的流程：算法的流程：（1）初始化每个粒子，即在允许范围内随机设置每个粒 子的初始位置和速度。（2）评价每个粒子的适应度，计算每个粒子的目标函数。（3）设置每个粒子的 。对每个粒子，将其适应度与其经 历过的最好位置 进行比较，如果优于 ，则将其作为该粒子的最好位置 。147.2.1 粒子群优化算法的基本原理 粒子群优化粒子群优化算法的流程：算法的流程：（4）设置全局最优值 。对每个粒子，将其适应度与群体经历过的最好位置 进行比较，如果优于 ，则将其作为当前群体的最好位置 。（5）根据式（7.1）更新粒子的速度和位置。（6）检查终止条件。如果未达到设定条件（

9、预设误差或者迭代的次数），则返回第（2）步。157.2.1 粒子群优化算法流程图167.2.2 粒子群优化算法的参数分析1. PSO算法的参数算法的参数包包括括：群体规模m，惯性权重，加速度1，2，最大速度Vmax， 最大代数Gmax。对速度vi，算法中有最大速度Vmax作为限制，如果当前粒子的某维速度大于最大速度Vmax，则该维的速度就被限制为最大速度Vmax。（1）最大速度最大速度Vmax（2）权重因子）权重因子3个权重因子：惯性权重，加速度1，2 。177.2.2 粒子群优化算法的参数分析2. 位置更新方程中各部分的影响位置更新方程中各部分的影响（1）只有第）只有第1部分，即部分，即 1

10、= 2=0 粒子将一直以当前的速度飞行，直到达边界。由于它只能搜索有限的区域，所以很难找到好解。187.2.2 粒子群优化算法的参数分析2. 位置更新方程中各部分的影响位置更新方程中各部分的影响（2）没有第）没有第1部分，部分，即即 =0速度只取决于粒子当前位置和其历史最好位置Pi 和 Pg，速度本身没有记忆性。197.2.2 粒子群优化算法的参数分析（3）没有第）没有第2部分，部分，即即 1=0 粒子没有认知能力，也就是“只有社会模型”。在粒子的相互作用下，有能力达到新的搜索空间。但对复杂问题，容易陷入局部最优点。207.2.2 粒子群优化算法的参数分析（4）没有第）没有第3部分，部分，即即

11、 2=0 粒子间没有社会共享信息，也就是“只有认知”模型。因为个体间没有交互，一个规模为M的群体等价于M个单个粒子的运行，因而得到最优解的机率非常小。217.2.2 粒子群优化算法的参数分析3. 参数设置参数设置早早期期的的实实验验： 固定为1.0，1和2固定为2.0，因此Vmax成为唯一需要调节的参数，通常设为每维变化范围1020%。Suganthan的实验表明，1和2 为常数时可以得到较好的解，但不一定必须为2。这些参数也可以通过模糊系统进行调节。Shi和Eberhart提出一个模糊系统来调节 。22第7章 群智能算法及其应用o7.1 群智能算法产生的背景群智能算法产生的背景o7.2 粒子

12、群优化算法粒子群优化算法 7.3 量子粒子群优化算法量子粒子群优化算法 o7.4 粒子群优化算法的应用粒子群优化算法的应用o7.5 基本蚁群算法基本蚁群算法o7.6 改进蚁群算法改进蚁群算法 o7.7 蚁群算法的应用蚁群算法的应用237.3 量子粒子群优化算法o产生背景产生背景在量子力学中是没有确定的轨迹的，因为根据不确定性原理，位置向量xi和速度向量vi是不可能同时确定的。J. Sun受到量子物理学的启发，于2004年提出了一种能够保证全局收敛的具有量子行为的量子粒子群优化 (Quantum-behaved particle swarm optimization，QPSO) 算法，并对算法的

13、收敛性进行了分析。247.3 量子量子粒子群优化算法7.3.1 基本量子粒子群优化算法基本量子粒子群优化算法7.3.2 改进量子粒子群优化算法改进量子粒子群优化算法251.粒子不再被描述粒子不再被描述为位置向量位置向量 xi和速度向量和速度向量vi ，而是，而是采用波函数来表示。采用波函数来表示。7.3.1 基本量子粒子群优化算法 粒子的波函数为 （7.2） 其概率密度函数为 （7.3）其中，p为每个粒子历史的最好位置。 参数L的取值定义为 （7.4）L指出了微粒的搜索空间范围。 262. 引入了引入了mbest为所有微粒的中心所有微粒的中心7.3.1 基本量子粒子群优化算法 （7.5）其中，

14、M是种群数目， pi 是第 i 个粒子的最好位置。通过将所有粒子的中心mbest取代每个粒子的最好位置p，可以有效提高算法的全局搜索能力。277.3.1 基本量子粒子群优化算法o参数L表示为o （7.6）o其中， 为收敛系数，不同的 影响算法的收敛速度，一般取 的值为o （7.7）o其中，MAXITER为最大迭代次数。 o由概率密度函数通过Monte Carlo算法计算得到o o （7.8）o代入参数L，QPSO算法的进化方程为o （7.9）287.3.1 基本量子粒子群优化算法o量子粒子群优化量子粒子群优化算法的基本步骤：算法的基本步骤：oStep1：确定种群规模和粒子维数，初始化粒子群体；

15、oStep2：计算个体历史最优值(pbest)：计算每一个微粒的适应度值，通过和个体的历史最优值比较，如果当前值优于个体历史最优值，则把当前值替换为个体最优值(pbest)，否则不替换；oStep3：计算所有微粒的适应值，与当前全局最优值(gbest)比较，若当前值优于全局最优值，则把当前值替换为全局最优值；oStep4：计算所有粒子的重心（mbest）；根据公式(7.5)来更新所有粒子的重心（mbest）；oStep5: 根据进化方程(7.9)更新每个粒子的位置，产生新种群；oStep6：粒子适应度满足收敛条件或者是达到最大迭代次数，则算法结束，否则跳转到步骤2继续迭代执行。29优点优点：相

16、对于粒子群优化算法具有更好的收敛性和全局搜索能力。 缺点：缺点：求解约束优化问题的时 会产生大量的不可行解 破坏种群的多样性 导致算法陷入局部极值7.3.1 基本量子粒子群优化算法301.三种概率分布函数三种概率分布函数7.3.2 改进量子粒子群优化算法（1）正）正态分布分布 正态分布是具有两个参数 和 2 的连续型随机变量的分布，正态分布记作 。正态分布的概率密度函数为 （7.10）其中， 是服从正态分布的随机变量的均值，2是该随机变量的方差。 311.三种概率分布函数三种概率分布函数7.3.2 改进量子粒子群优化算法（2） 2 分布分布 设随机变量 相互独立，并且都服从标准正态分布 ，则随

17、机变量 的概率密度为 （7.11）321.三种概率分布函数三种概率分布函数7.3.2 改进量子粒子群优化算法（3）t 分布分布 设随机变量X与Y独立，并且X服从标准正态分布 ，Y服从自由度为 k 的 2 分布，则随机变量 的概率密度为 （7.12）337.3.2 改进量子粒子群优化算法2. 变异操作异操作（1）生成符合正）生成符合正态分布的随机数分布的随机数 产生 均匀分布的随机数30个，记为 ；由于 ， 。根据中心极限定理，可以认为近似服从均值为 ，方差为2.5的正态分布。计算 ，由中心极限定理，它可以看作是来自标准正态分布 的一个随机数。347.3.2 改进量子粒子群优化算法2. 变异操作

18、异操作（2）对个体的每个个体的每个维度度产生在可行域区生在可行域区间内符合概率分布的内符合概率分布的可行解可行解 正态分布生成1个符合正态分布的随机数v，变换x=+v由，正态分布的性质可知，它可以看作是来自正态分布N(, 2)的一个随机数。取 。为可变参数，用于控制解在可行域范围内的分布情况。可行解 。 2 分布生成k个满足标准正态分布N(0,1)的随机数 ，取 。 k为 可 变 参 数 ， 用 于 控 制 解 在 可 行 域 范 围 内 的 分 布 情 况 。 可 行 解 。 t 分布生成2个满足标准正态分布N(0,1)的随机数 ，取 ，生成一个符合正态分布的随机数 X，取 。可行解 。35

19、7.3.2 改进量子粒子群优化算法2. 变异操作异操作（3）计算适算适应度度由前面所生成的个体 在可行域区间内，符合概率分布。根据适应度公式计算个体的适应度 。（4）以一定的概率接受解）以一定的概率接受解计算动态变异率 (7.13)其中， 为原个体的适应度。 为变异操作后个体的适应度。依照概率 接受解，即将原个体X替换为变异后的解X。上式表明若pm1则表示X是个极好解，这个解必定被接受。36基于概率分布的量子粒子群优化算法流程图37第7章 群智能算法及其应用o7.1 群智能算法产生的背景群智能算法产生的背景o7.2 粒子群优化算法粒子群优化算法 o7.3 量子粒子群优化算法量子粒子群优化算法

20、7.4 粒子群优化算法的应用粒子群优化算法的应用o7.5 基本蚁群算法基本蚁群算法o7.6 改进蚁群算法改进蚁群算法 o7.7 蚁群算法的应用蚁群算法的应用387.4 粒子群优化算法的应用7.4.1 粒子群优化算法应用领域粒子群优化算法应用领域7.4.2 粒子群优化算法在粒子群优化算法在PID参数整定中的应用参数整定中的应用7.4.3 粒子群优化算法在车辆路径问题中的应用粒子群优化算法在车辆路径问题中的应用397.4.1 粒子群优化算法应用领域（1）神经网络训练 （7）经济领域（2）化工系统领域 （8）图像处理领域（3）电力系统领域 （9）生物信息领域（4）机械设计领域 （10）医学领域（5）

21、通讯领域 （11）运筹学领域（6）机器人领域 .粒子群粒子群优化算法已在化算法已在诸多多领域得到域得到应用，用，归纳如下如下：40 7.4.2 粒子群优化算法在PID参数整定中的应用典型的PID控制系统的控制量u与偏差e=(R-y)之间满足以下差分方程 （7.14）PID控制器就是通过调整Kp，Ti，Td这3个参数来使系统的控制性能达到给定的要求。从最优控制的角度，就是在Kp，Ti，Td这3个变量的参数空间中，寻找最优的值使系统的控制性能达到最优。为优化PID参数，可以选取如下函数作为评价控制性能的指标 （7.15）411.编码与初始种群与初始种群 7.4.2 粒子群优化算法在PID参数整定中

22、的应用2. 适适应度函数度函数 实数编码 在初始群体的生成上，首先根据经验估计出PID三个参数的取值范围，在此范围内采用随机生成的方式，使粒子群优化算法在整个可行解空间中进行搜索。 由于PID参数优化是求目标函数Q的极小值问题，因而需要将极小值问题转换为极大值问题，适应度函数可以取为 （7.16）42举例举例 7.4.2 粒子群优化算法在PID参数整定中的应用采用PID控制器对被控对象进行控制，假定控制对象具有二阶惯性加延迟的模型，其传递函数为: 。假定采样周期选择为0.1s，根据经验Kp参数范围为（0，4），Ti参数范围为（0，1），Td参数范围为（0，1）。取粒子群种群规模为20，迭代次数

23、为50，c1的取值根据迭代的次数线性减小，初始值为1.5，最终值0.4。 1= 2=2。43举例举例 7.4.2 粒子群优化算法在PID参数整定中的应用PID参数粒子群优化算法寻优结果见表7.1所示。为了说明粒子群优化算法的有效性，表中同时也给出了用单纯形法的寻优结果。算法KpTiTdQ粒子群优化算法0.629320.593490.237154.84232单纯形法0.630570.594810.237034.86818表7.1 优化结果及比较 441.车辆路径路径问题（VRP）的模型）的模型 7.4.3 粒子群优化算法在车辆路径问题中的应用车辆路径问题：假定配送中心最多可以用 辆车对 个客户进

24、行运输配送， 表示仓库。每个车辆载重为 ，每个客户的需求为 ，客户i到客户 j 的运输成本为 cij（可以是距离，时间，费用等）。定义如下变量：451.车辆路径路径问题（VRP）的模型）的模型 7.4.3 粒子群优化算法在车辆路径问题中的应用则车辆路径问题的数学模型如下表示： (7.17a) (7.17b) 每辆车的能力约束 (7.17c) 保证每个客户都被服务 (7.17d) 保证客户是仅被一辆车访问 (7.17e) 保证客户是仅被一辆车访问 (7.17f) 消除子回路 (7.17g) 表示变量的取值范围 (7.17h) 表示变量的取值范围46 7.4.2 粒子群优化算法在车辆路径问题中的应

25、用2. 编码与初始种群与初始种群 对这类组合优化问题，编码方式、初始解的设置对问题的求解都有很大的影响。采用常用的自然数编码方式。 对于K辆车和L个客户的问题，用从1到L的自然数随机排列来产生一组解 。然后分别用节约法或者最近插入法构造初始解。47 7.4.2 粒子群优化算法在PID参数整定中的应用粒子群优化算法的各个参数设置如下：种群规模p=50 ，迭代次数N=1000 ， c1的初始值为1，随着迭代的进行，线性减小到0，c2=c3=1.4 ， 。表7.2 优化结果及其比较3. 实验结果果实例PSOGAbestdev(%)bestdev(%)A-n32-k58295.738184.34A-n

26、33-k57056.656741.97A-n34-k58326.948215.52A-n39-k68726.088665.35A-n44-k610168.499915.76A-n46-k79776.899574.7A-n54-k712053.2612033.08A-n60-k914769.0114104.13A-n69-k912751012437.24A-n80-k10199212.9818716.1248第7章 群智能算法及其应用o7.1 群智能算法产生的背景群智能算法产生的背景o7.2 粒子群优化算法粒子群优化算法 o7.3 量子粒子群优化算法量子粒子群优化算法 o7.4 粒子群优化算法的

27、应用粒子群优化算法的应用7.5 基本蚁群算法基本蚁群算法o7.6 改进蚁群算法改进蚁群算法 o7.7 蚁群算法的应用蚁群算法的应用49 20世纪90年代初，意大利科学家Marco Dorigo等受蚂蚁觅食行为的启发，提出蚁群算法(Ant Colony Optimization，ACO)。 7.5 基本蚁群算法 一种应用于组合优化问题的启发式搜索算法。 在解决离散离散组合优化方面具有良好的性能。 产生背景产生背景50 基本思想基本思想7.5 基本蚁群算法 信信息息素素跟跟踪踪：按照一定的概概率率沿着信息素较强的路径觅食。 信信息息素素遗遗留留：会在走过的路上会释放信息素，使得在一定的范围内的其他

28、蚂蚁能够觉察到并由此影响它们的行为。51 7.5 基本蚁群算法 （1）环境）环境：有障碍物、有其他蚂蚁、有信息素。 （2）觅觅食食规规则则：范围内寻找是否有食物，否则看是否有信息素，每只蚂蚁都会以小概率犯错。 （3）移移动动规规则则：都朝信息素最多的方向移动，无信息素则继续朝原方向移动，且有随机的小的扰动，有记忆性。 （4）避避障障规规则则：移动的方向如有障碍物挡住，蚂蚁会随机选择另一个方向。（5）信信息息素素规规则则：越靠近食物播撒的信息素越多，越离开食物播撒的信息素越少。527.5 基本蚁群算法7.5.1 基本蚁群算法模型基本蚁群算法模型7.5.2 蚁蚁群算法群算法的参数选择的参数选择53

29、7.5.1 基本蚁群算法模型蚁群优化算法的第一个应用是著名的旅行商问题。蚁群优化算法的第一个应用是著名的旅行商问题。旅行商问题旅行商问题阐明 蚁群系统模型蚁群系统模型旅行商旅行商问题（Traveling Salesman Problem，TSP）：在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。蚂蚁搜索食物的搜索食物的过程程 ：通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径。54蚁群系群系统的的模型模型 7.5.1 基本蚁群算法模型 m 是蚁群中蚂蚁的数量 表示元素(城市) 和元素(城市) 之间的距离 表示能见度，称为启发信息函数，等于距离

30、 的倒数，即 表示t时刻位于城市x的蚂蚁的个数， 表示t时刻在xy连线上残留的信息素，初始时 刻，各条路径上的信息素相等即 蚂蚁k在运动过程中，根据各条路径上的信息素决定转移方向。55 7.5.1 基本蚁群算法模型 表示在t时刻蚂蚁 k 选择从元素(城市) x 转移到元素(城市) y 的概率，也称为随机比例规则。信息素 共同决定局部启发信息蚁群系统的模型蚁群系统的模型56 7.5.1 基本蚁群算法模型 表示如下： （7.18） 其中： 表示蚂蚁k下一步允许选择的城市 记录蚂蚁k当前所走过的城市 是信息素启发式因子，表示轨迹的相对重要性57 7.5.1 基本蚁群算法模型 表示如下： （7.18）

31、 其中： 值越大该蚂蚁越倾向于选择其它蚂蚁经过的路径，该状态转移概率越接近于贪婪规则。当 = 0时不再考虑信息素水平，算法就成为有多重起点的随机贪婪算法。当 = 0时算法就成为纯粹的正反馈的启发式算法。58 7.5.1 基本蚁群算法模型用参数1-表示信息素消逝程度，蚂蚁完成一次循环，各路径上信息素浓度消散规则为： （7.19）蚁群的信息素浓度更新规则为： （7.20）M. Dorigo给出 的三种不同模型591.蚂蚁圈系圈系统（Ant-cycle System） 7.5.1 基本蚁群算法模型单只蚂蚁所访问路径上的信息素浓度更新规则为： （7.21）其中： 为当前路径上的信息素 为路径（x, y

32、）上信息素的增量 第k只蚂蚁留在路径（x, y）上的信息素的增量 Q 为常数 Lk 为优化问题的目标函数值，表示第k只蚂蚁在本次循环 中所走路径的长度602. 蚂蚁数量数量系系统（Ant-quantity System） 7.5.1 基本蚁群算法模型 （7.22）3. 蚂蚁密度密度系系统（Ant-density System） （7.23）61 7.5.1 基本蚁群算法模型蚂蚁圈系统利用的是全局信息 ，即蚂蚁完成一个循环后，更新所有路径上的信息。蚂蚁数量系统利用的是局部信息 ，即蚂蚁每走一步都要更新残留信息素的浓度。蚂蚁密度系统利用的是局部信息 ，即蚂蚁每走一步都要更新残留信息素的浓度。三种模

33、型比三种模型比较效果最好，通常作效果最好，通常作为蚁群群优化算法的基本模型。化算法的基本模型。627.5.1 基本蚁群算法模型全局信息更新方法全局信息更新方法o优点：优点：l 保证了残留信息素不至于无限累积；l 如果路径没有被选中，那么上面的残留信息素会随时间的o 推移而逐渐减弱，这使算法能“忘记”不好的路径；l 即使路径经常被访问也不至于因为 的累积，而产生o 使期望值的作用无法体现；l 充分体现了算法中全局范围内较短路径(较好解)的生存能力；l 加强了信息正反馈性能；l 提高了系统搜索收敛的速度。63信息素启信息素启发因子因子 7.5.2 蚁群算法的参数选择反映了蚁群在路径搜索中随机性因素

34、作用的强度； 值越大，蚂蚁选择以前走过的路径的可能性越大，搜索的随机性减弱；当 过大时会使蚁群的搜索过早陷于局部最优。期望期望值启启发式因子式因子 反映了蚁群在路径搜索中先验性、确定性因素作用的强度； 值越大，蚂蚁在某个局部点上选择局部最短路径的可能性越大；虽然搜索的收敛速度得以加快，但蚁群在最优路径的搜索过程中随机性o 减弱，易于陷入局部最优。64信息素信息素挥发度度1- 7.5.2 蚁群算法的参数选择当要处理的问题规模比较大时，会使那些从来未被搜索到的路径(可行解)上的信息量减小到接近于0，因而降低了算法的全局搜索能力；而且当1- 过大时，以前搜索过的路径被再次选择的可能性过大，也会影响到

35、算法的随机性能和全局搜索能力；反之，通过减小信息素挥发度 1- 虽然可以提高算法的随机性能和全局搜索能力，但又会使算法的收敛速度降低。信息素启信息素启发因子因子 期望期望值启启发式因子式因子 信息素信息素挥发度度1- 65第7章 群智能算法及其应用o7.1 群智能算法产生的背景群智能算法产生的背景o7.2 粒子群优化算法粒子群优化算法 o7.3 量子粒子群优化算法量子粒子群优化算法 o7.4 粒子群优化算法的应用粒子群优化算法的应用o7.5 基本蚁群算法基本蚁群算法7.6 改进蚁群算法改进蚁群算法 o7.7 蚁群算法的应用蚁群算法的应用667.6 改进蚁群算法7.6.1 蚂蚁蚂蚁-Q系统系统7

36、.6.2 蚁群系统蚁群系统7.6.2 最大最大-最小蚂蚁系统最小蚂蚁系统7.6.2 自适应蚁自适应蚁群群算法算法67 1995年，意大利学者M.Luca，M.Gambardella, M.Dorigo提出了蚂蚁Q 系统（Ant-Q System）。7.6.1 蚂蚁-Q系统 在解构造过程中提出了伪随机比例状态迁移规则；信息素局部更新规则引入强化学习中的Q学习机制；在在ACA算法的算法的基基础上，上，进行了以下行了以下创新：新： 在信息素的全局更新中采用了精英策略。68 7.6.1 蚂蚁-Q系统（7.24）根据式（7.25）计算概率分布：（7.25）AQ值按照如下规则进行更新：（7.26）（7.2

37、7）69 1996年，Gambardella和Dorigo又在Ant-Q算法的基础上，提出一种修正的蚁群算法，称之为蚁群系统(ant colony system, ACS)，该算法可以看成是Ant-Q算法的特例。7.6.2 蚁群系统 蚂蚁选择城市时遵循的规则不同，这里使用的是所谓的状态转移规则:与与ACA算法算法的不同之的不同之处：（7.28）其中：Sk是序号为k的蚂蚁所选中的下一个节点; q表示一个随机变量，q0是一个适当选定的阈值。707.6.2 蚁群系统 主要不同在于蚂蚁选择下一城市之前，多进行了一次随机试 验，将选择情况分成“利用已知信息”和“探索”两类。相比相比ACA算法算法，进行了

38、以下行了以下创新：新： 还提出了所谓的精英策略(elitist strategy) 。 结果发现，对精英蚂蚁数而言有一个最优的范围：低于此范 围，增加精英蚂蚁数可较早地发现更好的路径，高于此范围， 精英蚂蚁会在搜索早期迫使寻优过程始终在次优解附近，导致 性能变差。71 最大-最小蚂蚁系统(Max-Min Ant System，MMAS)是德国学者Thomas Stutzle等在1997年提出的。7.6.3 最大-最小蚂蚁系统 该算法在启动时将所有支路上的信息素浓度初始化为最大值 max；为了更好地利用历史信息，每次迭代后按挥发系数降低信息素浓度，只有最佳路径上的支路才允许增加其信息素浓度并保持

39、在高水平上，也就是用当前找到的最好解更新信息素来指引蚂蚁向更高质量的解空间搜索的贪婪策略。MMAS算法思想：算法思想：72 7.6.3 最大-最小蚂蚁系统（7.29）为了避免算法过早收敛于局部最优解，将各条路径可能的信息素浓度限制于min, max。采用了让轨迹上信息素浓度的增加正比于max和当前浓度(x, y)之差的平滑机制，如式（7.30）所示，其中0 n0+1 时 开始减小 n 越大 越小。算法具体实现时，0 、n0 可以根据需要进行调节。787.6.4 自适应蚁群算法784.自适自适应信息素信息素强强度度Q(n)当算法陷入局部收敛时采用时变函数Q(n)来代替基本蚁群算法中调整信息素 中

40、为常数项的信息素强度Q，即选择 ，随着人工蚂蚁搜索过程动态的调整，Q(n)如下所示： （7.34）其中，Q0为初始信息素强度，可以根据需要调整。 797.6.4 自适应蚁群算法795. 改改进的信息素更新策略的信息素更新策略o信息素更新策略存在多种方式：走过的全部路径上的信息素进行更新，导致算法获得的结果振荡, 不易收敛更新搜索到最优边上的信息素，则进一步加强了蚁群算法的正反馈作用，导致搜索过程迅速陷入局部最优解807.6.4 自适应蚁群算法805. 改改进的信息素更新策略的信息素更新策略记l为每代最优解对应的蚂蚁，蚂蚁总数为m。 （1） 当算法未陷入局部最当算法未陷入局部最优时，采用全局更新

41、和局部更新，采用全局更新和局部更新结合的合的策略，其中策略，其中 和和Q均均为初始初始值： Step1：全局更新，计算所有蚂蚁经过路径上的信息素增量： （7.35） Step2：局部更新，如果该代最优解为历代最优解，则调整蚂蚁l经过路径上的信息素增量： （7.36） Step3：更新所有蚂蚁经过路径上的信息素： （7.37） 817.6.4 自适应蚁群算法815. 改改进的信息素更新策略的信息素更新策略记l为每代最优解对应的蚂蚁，蚂蚁总数为m。 （2）当算法陷入局部最当算法陷入局部最优时,仅采用全局更新策略：采用全局更新策略： Step1：计算除最优蚂蚁l外所有其他蚂蚁经过路径上的信息素增量：

42、 （7.38） Step2：计算蚂蚁l经过的路径上的信息素增量： （7.39） Step3：更新除蚂蚁l外所有其他蚂蚁经过路径上的信息素： （7.40） Step4：更新蚂蚁l经过路径上的信息素： （7.41） 827.6.4 自适应蚁群算法826. 限定信息素的范限定信息素的范围通过缩小各路径信息素的差距，可以使算法有更好的全局收敛性。对各路径上的信息素进行限定，以防止某些路径上的信息素过大或过小而影响算法的全局收敛性。837.6.4 自适应蚁群算法83图7.5 自适自适应蚁群算法流程群算法流程图84第7章 群智能算法及其应用o7.1 群智能算法产生的背景群智能算法产生的背景o7.2 粒子群

43、优化算法粒子群优化算法 o7.3 量子粒子群优化算法量子粒子群优化算法 o7.4 粒子群优化算法的应用粒子群优化算法的应用o7.5 基本蚁群算法基本蚁群算法o7.6 改进蚁群算法改进蚁群算法 7.7 蚁群算法的应用蚁群算法的应用85表9.3 遗传算法运行的结果 7.7 蚁群算法的应用柔性作业车间调度问题：某加工系统有6台机床，要加工4个工件，每个工件有3道工序，如表7.3所示。86表表7.3 柔性作柔性作业车间调度事例度事例7.7 蚁群算法的应用87由图7.6可以看出机器6并没有加工任何工件。分析其原因为它虽然可以加工工序p23 ，p33 ，p42 ，p43 但从表7.3可知机器6的加工时间大

44、于其他可加工机器，特别是 p23 ，p33的加工时间，因此机器6并未分到任何加工任务。表9.3 遗传算法运行的结果 7.7 蚁群算法的应用887.7 蚁群算法的应用图7.6 最最优解甘特解甘特图897.7 蚁群算法的应用图7.7 历代最代最优解收解收敛图由图7.7可知，算法在大约30代以前就收敛到最优解，且各代最优解相差不大，可见算法较为稳定。90表9.3 遗传算法运行的结果 7.8 小结1.粒子群粒子群优化算法化算法初始化每个粒子，即在允许范围内随机设置每个粒 子的初始位置和速度。评价每个粒子的适应度，计算每个粒子的目标函数。设置每个粒子的 Pi。对每个粒子，将其适应度与其经 历过的最好位置

45、 Pi进行比较，如果优于 Pi ，则将其作为该粒子的最好位置Pi 。设置全局最优值Pg 。对每个粒子，将其适应度与群体经历过的最好位置Pg 进行比较，如果优于 Pg ，则将其作为当前群体的最好位置Pg 。根据式（7.1）更新粒子的速度和位置。检查终止条件。如果未达到设定条件（预设误差或者迭代的次数），则返回第 步。91表9.3 遗传算法运行的结果 7.8 小结o2. 量子粒子群量子粒子群优化算法化算法确定种群规模和粒子维数，初始化粒子群体。计算个体历史最优值(pbest)：根据适应度函数计算每一个微粒的适应度值，通过和个体的历史最优值比较，如果当前值优于个体历史最优值，则把当前值替换为个体最优

46、值(pbest)，否则不替换。计算群体的历史最优值(gbest)：计算所有微粒的适应值，并与当前的全局最优值(gbest)比较，若当前值优于全局最优值，则把当前值替换为全局最优值(gbest) 。计算所有粒子的重心(mbest)；根据公式(7.5)来更新所有粒子的重心(mbest) 。根据量子粒子群进化方程(7.9)更新每个粒子的位置，产生新的种群。粒子适应度满足收敛条件或者是达到最大迭代次数，则算法结束，否则跳转到步骤2继续迭代执行。92表9.3 遗传算法运行的结果 7.8 小结o3. 基本基本蚁群算法群算法蚂蚁在运动过程中，根据各条路径上的信息素决定转移方向。在t时刻蚂蚁k选择从元素(城市) x转移到元素(城市) y的概率：各路径上信息素浓度消散规则为：蚁群的信息素浓度更新规则为：93Artificial Intelligence Principles and ApplicationsTHE END