湘潭大学-人工智能课件-群智能

1、Artificial Intelligence (AI) 人工智能人工智能 第九章：群智第九章：群智 能系统能系统 内容提要 第九章：群智能系统第九章：群智能系统 1.1.粒子群优化算法粒子群优化算法 2.2.蚁群算法蚁群算法 内容提要 第九章：群智能系统第九章：群智能系统 1.1.粒子群优化算法粒子群优化算法 2.2.蚁群算法蚁群算法 n描述描述 群智能作为一种新兴的演化计算技术已成为研究焦群智能作为一种新兴的演化计算技术已成为研究焦 点，它与人工生命，特别是进化策略以及遗传算法点，它与人工生命，特别是进化策略以及遗传算法 有着极为特殊的关系。有着极为特殊的关系。 n特性特性 指无智能的主体

2、通过合作表现出智能行为的特性，指无智能的主体通过合作表现出智能行为的特性， 在没有集中控制且不提供全局模型的前提下，为寻在没有集中控制且不提供全局模型的前提下，为寻 找复杂的分布式问题求解方案提供了基础。找复杂的分布式问题求解方案提供了基础。 群智能 n优点优点 灵活性：群体可以适应随时变化的环境；灵活性：群体可以适应随时变化的环境； 稳健性：即使个体失败，整个群体仍能完成任务；稳健性：即使个体失败，整个群体仍能完成任务； 自我组织：活动既不受中央控制，也不受局部监管。自我组织：活动既不受中央控制，也不受局部监管。 n典型算法典型算法 蚁群算法（蚂蚁觅食）蚁群算法（蚂蚁觅食） 粒子群算法（鸟群

3、捕食）粒子群算法（鸟群捕食） 群智能 粒子群算法原理 粒子群算法原理 粒子群算法原理 粒子群算法原理 n由由James Kenney（社会心理学博士）和（社会心理学博士）和Russ Eberhart（电子工程学博士，（电子工程学博士， /eberhart/ ）于）于1995年提年提 出粒子群算法（出粒子群算法（Particle Swarm Optimization, PSO） 粒子群算法原理 粒子群算法原理 生物界现象生物界现象 群体行为群体行为 群体迁徙群体迁徙 生物觅食生物觅食 社会心理学社会心理学 群体智慧群体智慧 个体认知个体认知 社会影

4、响社会影响 人工生命人工生命鸟群觅食鸟群觅食鱼群学习鱼群学习群理论群理论 粒子群算法原理 粒子群算法原理 鸟群觅食现象鸟群觅食现象 鸟群鸟群 觅食空间觅食空间 飞行速度飞行速度 所在位置所在位置 个体认知与群体协作个体认知与群体协作 找到食物找到食物 粒子群优化算法粒子群优化算法 搜索空间的一组有效解搜索空间的一组有效解 问题的搜索空间问题的搜索空间 解的速度向量解的速度向量 解的位置向量解的位置向量 速度与位置的更新速度与位置的更新 找到全局最优解找到全局最优解 粒子群优化算法粒子群优化算法 类比关系类比关系 鸟群觅食现象鸟群觅食现象 n源于对鸟群捕食行为的研究，是基于迭代的方法源于对鸟群捕

5、食行为的研究，是基于迭代的方法 n简单易于实现，需要调整的参数相对较少简单易于实现，需要调整的参数相对较少 n在函数优化、神经网络训练、工业系统优化和模糊在函数优化、神经网络训练、工业系统优化和模糊 系统控制等领域得到了广泛的应用。系统控制等领域得到了广泛的应用。 粒子群算法原理 n鸟群：鸟群： 假设一个区域，所有的鸟都不知道食物的位置，但假设一个区域，所有的鸟都不知道食物的位置，但 是它们知道当前位置离食物还有多远。是它们知道当前位置离食物还有多远。 nPSO算法算法 每个解看作一只鸟，称为每个解看作一只鸟，称为“粒子粒子(particle)”，所有，所有 的粒子都有一个适应值，每个粒子都有

6、一个速度决的粒子都有一个适应值，每个粒子都有一个速度决 定它们的飞翔方向和距离，粒子们追随当前最优粒定它们的飞翔方向和距离，粒子们追随当前最优粒 子在解空间中搜索。子在解空间中搜索。 粒子群算法原理 算法流程 PSO中的个体，也叫中的个体，也叫粒子粒子，在多维搜索空间中飞行。，在多维搜索空间中飞行。 PSO中的每个粒子维护两个向量中的每个粒子维护两个向量 位置向量位置向量xi ：粒子在解空间中的当前位置：粒子在解空间中的当前位置 速度向量速度向量vi ：粒子在解空间中的飞行速度：粒子在解空间中的飞行速度 pBest ：粒子自身的历史最优位置：粒子自身的历史最优位置 gBest ：群体全局最优向

7、量：群体全局最优向量 lBest ：邻域中的最好位置：邻域中的最好位置 nPSO算法算法 初始化为一群随机粒子，通过迭代找到最优。初始化为一群随机粒子，通过迭代找到最优。 每次迭代中，粒子通过跟踪每次迭代中，粒子通过跟踪“个体极值（个体极值（pbest）” 和和“全局极值全局极值(gbest)”来来 更新自己的位置。更新自己的位置。 算法流程 算法流程 (t) i v 令令 表示表示t t时刻第时刻第i i 个粒子个粒子 在超空间的位置。在超空间的位置。 把速度矢量把速度矢量 加至当前位置，则加至当前位置，则 的位置变为：的位置变为： (t) i x i P (t)(t1)(t) iii xx

8、v i P 算法流程 速度向量反映了粒子速度向量反映了粒子自身的经验知识自身的经验知识和和来自邻域粒子来自邻域粒子 的社会交换信息的社会交换信息。 粒子的经验知识通常叫做粒子的经验知识通常叫做认知部分认知部分，它和粒子与其，它和粒子与其自自 身的身的历史最优位置（历史最优位置（ pbest ）的距离成正比。）的距离成正比。 社会交换信息叫做速度方程的社会交换信息叫做速度方程的社会部分社会部分。 gbest PSO，全局最佳粒子群优化，全局最佳粒子群优化 lbest PSO，局部最佳粒子群优化，局部最佳粒子群优化 算法流程 粒子群算法 v粒子群算法的特点粒子群算法的特点 PSO算法收敛速度快，特

9、别是在算法的早期，但也存在算法收敛速度快，特别是在算法的早期，但也存在 着精度较低，易发散等缺点。着精度较低，易发散等缺点。 若加速系数、最大速度等参数太大，粒子群可能错过若加速系数、最大速度等参数太大，粒子群可能错过 最优解，算法不收敛；最优解，算法不收敛； 而在收敛的情况下，由于所有的粒子都向最优解的方而在收敛的情况下，由于所有的粒子都向最优解的方 向飞去，所以粒子趋向同一化（失去了多样性），使向飞去，所以粒子趋向同一化（失去了多样性），使 得后期收敛速度明显变慢，同时算法收敛到一定精度得后期收敛速度明显变慢，同时算法收敛到一定精度 时，无法继续优化，所能达到的精度也不高。时，无法继续优化

10、，所能达到的精度也不高。 内容提要 第九章：群智能系统第九章：群智能系统 1.1.粒子群优化算法粒子群优化算法 2.2.蚁群算法蚁群算法 蚁群算法原理 蚁群算法原理 蚁群算法原理 蚁群算法原理 育婴室育婴室 储备室储备室 寝室寝室蚁后室蚁后室 日光浴场日光浴场入口入口 蚁群算法原理 通过遗留在来往路径上的信息素（通过遗留在来往路径上的信息素（Pheromone） 的挥发性化学物质来进行的挥发性化学物质来进行 通信和协调。通信和协调。 蚁群算法 v蚁群觅食过程蚁群觅食过程 算法基本原理 自然界蚂蚁觅食行为自然界蚂蚁觅食行为蚁群优化算法蚁群优化算法 蚁群蚁群搜索空间的一组有效解搜索空间的一组有效解

11、 问题的搜索空间问题的搜索空间 信息素浓度变量信息素浓度变量 一个有效解一个有效解 问题的最优解问题的最优解 觅食空间觅食空间 信息素信息素 蚁巢到食物的一条路径蚁巢到食物的一条路径 找到的最短路径找到的最短路径 对对 应应 关关 系系 算法基本原理 蚂蚁在寻找食物的过程中往往是蚂蚁在寻找食物的过程中往往是随机选择路径随机选择路径的，但它们能的，但它们能 感知当前地面上的信息素浓度感知当前地面上的信息素浓度，并倾向于往信息素浓度高的并倾向于往信息素浓度高的 方向行进方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信。信息素由蚂蚁自身释放，是实现蚁群内间接通信 的物质。的物质。 由于较短路径上

12、蚂蚁的往返时间比较短，单位时间内经过该由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该 路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此， 当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾 向于选择一条较短的路径前行。向于选择一条较短的路径前行。 这种这种正反馈机制正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最使得越来越多的蚂蚁在巢穴与食物之间的最 短路径上行进。由于其他路径上的信息素会短路径上行进。由于其他路径上的信息素会随着时间蒸发随着时间蒸发， 最终所有的蚂蚁都在最优路

13、径上行进。最终所有的蚂蚁都在最优路径上行进。 蚁群算法流程 路径构建路径构建 每只蚂蚁都随机选择每只蚂蚁都随机选择 一个城市作为其出发一个城市作为其出发 城市，并维护一个路城市，并维护一个路 径记忆向量，用来存径记忆向量，用来存 放该蚂蚁依次经过的放该蚂蚁依次经过的 城市。蚂蚁在构建路城市。蚂蚁在构建路 径的每一步中，按照径的每一步中，按照 一个随机比例规则选一个随机比例规则选 择下一个要到达的城择下一个要到达的城 市。市。 ACO基本要素基本要素 信息素更新信息素更新 当所有蚂蚁构建完路当所有蚂蚁构建完路 径后，算法将会对所径后，算法将会对所 有的路径进行全局信有的路径进行全局信 息素的更新

14、。注意，息素的更新。注意， 我们所描述的是我们所描述的是AS的的 ant-cycle版本版本，更新，更新 是在全部蚂蚁均完成是在全部蚂蚁均完成 了路径的构造后才进了路径的构造后才进 行的，信息素的浓度行的，信息素的浓度 变化与蚂蚁在这一轮变化与蚂蚁在这一轮 中构建的路径长度相中构建的路径长度相 关。关。 蚂蚁系统蚂蚁系统 (Ant System， AS ) 的蚂蚁圈（的蚂蚁圈（Ant - cycle）版本是最基本的）版本是最基本的 ACO算法，是以算法，是以TSP作作 为应用实例提出的。为应用实例提出的。 蚁群算法流程 伪随机比例选择规则伪随机比例选择规则 对于每只蚂蚁对于每只蚂蚁k，路径记忆

15、向量，路径记忆向量Rk按照访问顺序记录了所有按照访问顺序记录了所有k已经已经 经过的城市序号。经过的城市序号。 设蚂蚁设蚂蚁k当前所在城市为当前所在城市为i，则其选择城市，则其选择城市j作为下一个访问对象的作为下一个访问对象的 概率如上式。概率如上式。Jk(i) 表示从城市表示从城市i 可以直接到达的、且又不在蚂蚁访可以直接到达的、且又不在蚂蚁访 问过的城市序列问过的城市序列Rk中的城市集合。中的城市集合。 (i, j) 是一个启发式信息，通常由是一个启发式信息，通常由 (i, j)=1/dij 直接计算。直接计算。 (i, j) 表示边表示边(i, j)上的信息素量。上的信息素量。 ( )

16、( , )( , ) , if ( ) ( , )( , )( , ) 0, otherwise k k k u Ji i ji j jJi pi ji ui u 蚁群算法流程 伪随机比例选择规则伪随机比例选择规则 长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。长度越短、信息素浓度越大的路径被蚂蚁选择的概率越大。 和和是两个预先设置的参数，用来是两个预先设置的参数，用来控制启发式信息与信息素浓度控制启发式信息与信息素浓度 作用的权重关系作用的权重关系。 当当 =0时，算法演变成传统的随机贪心算法，最邻近城市被选中时，算法演变成传统的随机贪心算法，最邻近城市被选中 的概率最大。当的概率最大

17、。当 =0时，蚂蚁完全只根据信息素浓度确定路径，时，蚂蚁完全只根据信息素浓度确定路径， 算法将快速收敛，这样构建出的最优路径与实际目标差异较大，算法将快速收敛，这样构建出的最优路径与实际目标差异较大， 算法性能较差。算法性能较差。 ( ) ( , )( , ) , if ( ) ( , )( , )( , ) 0, otherwise k k k u Ji i ji j jJi pi ji ui u 蚁群算法流程 (1) 在算法初始化时，问题空间中所有的边上的信息素都被在算法初始化时，问题空间中所有的边上的信息素都被 初始化初始化为为0。 (2) 算法迭代每一轮，问题空间中的算法迭代每一轮，问

18、题空间中的所有路径上的信息素都所有路径上的信息素都 会发生蒸发会发生蒸发，我们为所有边上的信息素乘上一个小于，我们为所有边上的信息素乘上一个小于1的常的常 数数( : 信息素的蒸发率信息素的蒸发率)。信息素蒸发是自然界本身固有的特。信息素蒸发是自然界本身固有的特 征，在算法中能够帮助避免信息素的无限积累，使得算法可征，在算法中能够帮助避免信息素的无限积累，使得算法可 以快速丢弃之前构建过的较差的路径。以快速丢弃之前构建过的较差的路径。 (3) 蚂蚁根据自己构建的路径长度在它们本轮经过的边上释蚂蚁根据自己构建的路径长度在它们本轮经过的边上释 放信息素。放信息素。蚂蚁构建的路径越短、释放的信息素就

19、越多蚂蚁构建的路径越短、释放的信息素就越多。一。一 条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。 (4) 迭代迭代 (2)，直至算法终止。，直至算法终止。 蚁群算法流程 信息素的更新公式：信息素的更新公式： m：蚂蚁个数；：蚂蚁个数； ：信息素的蒸发率，规定：信息素的蒸发率，规定0r1。 (i, j)：第第k只蚂蚁在它经过的边上释放的信息素量，它等只蚂蚁在它经过的边上释放的信息素量，它等 于蚂蚁于蚂蚁k本轮构建路径长度的倒数。本轮构建路径长度的倒数。 Ck：路径长度，它是：路径长度，它是Rk中所有边的长度和。中所有边的长度和。 1 1 (

20、 , )(1)( , )( , ), (), if ( , ) ( , ) 0, otherwise m k k k k k i ji ji j Ci jR i j 蚁群算法流程 路径构建路径构建 信息素更新信息素更新 蚁群算法的应用 车辆路径问题车辆路径问题 （Vehicle Routing Problem，VRP） 车间作业调度问题车间作业调度问题 （Job-Shop Scheduling Problem，JSP） 分配问题分配问题 （Assignment problem, AP） 网络路由网络路由 （ Network Routing） 其他其他 子集问题子集问题 （Set Problem） ACO n共同特点共同特点 基于概率计算的随机搜索进化算法，在结构、研