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

1、Artificial Intelligence (AI),第九章：群智能系统,内容提要,第九章：群智能系统,内容提要,第九章：群智能系统,描述 群智能作为一种新兴的演化计算技术已成为研究焦点，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。 特性 指无智能的主体通过合作表现出智能行为的特性，在没有集中控制且不提供全局模型的前提下，为寻找复杂的分布式问题求解方案提供了基础。,群智能,优点 灵活性：群体可以适应随时变化的环境；稳健性：即使个体失败，整个群体仍能完成任务； 自我组织：活动既不受中央控制，也不受局部监管。 典型算法 蚁群算法（蚂蚁觅食） 粒子群算法（鸟群捕食）,群智能,粒子

2、群算法原理,粒子群算法（PSO）,粒子群算法原理,粒子群算法（PSO）,粒子群算法原理,粒子群算法（PSO）,粒子群算法原理,粒子群算法（PSO）,由James Kenney（社会心理学博士）和Russ Eberhart（电子工程学博士， /eberhart/ ）于1995年提出粒子群算法（Particle Swarm Optimization, PSO）,粒子群算法的提出,粒子群算法原理,粒子群算法原理,PSO的思想来源,粒子群算法原理,从生物现象到 PSO算法,鸟群觅食现象,粒子群优化算法,粒子群算法原理,从生物现象到 PSO算法,源于对鸟群

3、捕食行为的研究，是基于迭代的方法 简单易于实现，需要调整的参数相对较少 在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的应用。,粒子群算法原理,粒子群算法的提出,鸟群： 假设一个区域，所有的鸟都不知道食物的位置，但是它们知道当前位置离食物还有多远。 PSO算法 每个解看作一只鸟，称为“粒子(particle)”，所有的粒子都有一个适应值，每个粒子都有一个速度决定它们的飞翔方向和距离，粒子们追随当前最优粒子在解空间中搜索。,粒子群算法的原理描述,粒子群算法原理,算法流程,PSO算法的相关定义 PSO中的个体，也叫粒子，在多维搜索空间中飞行。 PSO中的每个粒子维护两个向量

4、位置向量xi ：粒子在解空间中的当前位置 速度向量vi ：粒子在解空间中的飞行速度 pBest ：粒子自身的历史最优位置 gBest ：群体全局最优向量 lBest ：邻域中的最好位置,PSO算法 初始化为一群随机粒子，通过迭代找到最优。 每次迭代中，粒子通过跟踪“个体极值（pbest）”和“全局极值(gbest)”来 更新自己的位置。,算法流程,算法流程,粒子速度与位置的更新,令 表示t时刻第i 个粒子 在超空间的位置。 把速度矢量 加至当前位置，则 的位置变为：,算法流程,PSO算法驱动优化过程的是速度vi(t)向量。 速度向量反映了粒子自身的经验知识和来自邻域粒子的社会交换信息。 粒子的

5、经验知识通常叫做认知部分，它和粒子与其自身的历史最优位置（ pbest ）的距离成正比。 社会交换信息叫做速度方程的社会部分。 邻域大小不同的两种算法 gbest PSO，全局最佳粒子群优化 lbest PSO，局部最佳粒子群优化,算法流程,gbest PSO：全局最佳粒子群优化,粒子群算法,粒子群算法的特点 PSO算法收敛速度快，特别是在算法的早期，但也存在着精度较低，易发散等缺点。 若加速系数、最大速度等参数太大，粒子群可能错过最优解，算法不收敛； 而在收敛的情况下，由于所有的粒子都向最优解的方向飞去，所以粒子趋向同一化（失去了多样性），使得后期收敛速度明显变慢，同时算法收敛到一定精度时，

6、无法继续优化，所能达到的精度也不高。,内容提要,第九章：群智能系统,蚁群算法原理,蚁群的觅食行为,蚁群算法原理,蚁群的分工,蚁群算法原理,蚁穴的结构,蚁群算法原理,蚁穴的结构,育婴室,储备室,寝室,蚁后室,日光浴场,入口,蚁群算法原理,蚁群觅食的“双桥实验”,通过遗留在来往路径上的信息素（Pheromone）的挥发性化学物质来进行 通信和协调。,蚁群算法,蚁群觅食过程,算法基本原理,自然界蚂蚁觅食行为,蚁群优化算法,蚁群,搜索空间的一组有效解,问题的搜索空间,信息素浓度变量,一个有效解,问题的最优解,觅食空间,信息素,蚁巢到食物的一条路径,找到的最短路径,对应关系,算法基本原理,蚁群优化算法（

7、 Ant Colony Optimization , ACO） 蚂蚁在寻找食物的过程中往往是随机选择路径的，但它们能感知当前地面上的信息素浓度，并倾向于往信息素浓度高的方向行进。信息素由蚂蚁自身释放，是实现蚁群内间接通信的物质。 由于较短路径上蚂蚁的往返时间比较短，单位时间内经过该路径的蚂蚁多，所以信息素的积累速度比较长路径快。因此，当后续蚂蚁在路口时，就能感知先前蚂蚁留下的信息，并倾向于选择一条较短的路径前行。 这种正反馈机制使得越来越多的蚂蚁在巢穴与食物之间的最短路径上行进。由于其他路径上的信息素会随着时间蒸发，最终所有的蚂蚁都在最优路径上行进。,蚁群算法流程,蚂蚁系统 (Ant Syst

8、em，AS ) 的蚂蚁圈（Ant -cycle）版本是最基本的ACO算法，是以TSP作为应用实例提出的。,蚁群算法流程,路径构建：伪随机比例选择规则 对于每只蚂蚁k，路径记忆向量Rk按照访问顺序记录了所有k已经经过的城市序号。 设蚂蚁k当前所在城市为i，则其选择城市j作为下一个访问对象的概率如上式。Jk(i) 表示从城市i 可以直接到达的、且又不在蚂蚁访问过的城市序列Rk中的城市集合。 (i, j) 是一个启发式信息，通常由 (i, j)=1/dij 直接计算。 (i, j) 表示边(i, j)上的信息素量。,蚁群算法流程,路径构建：伪随机比例选择规则 长度越短、信息素浓度越大的路径被蚂蚁选择

9、的概率越大。 和是两个预先设置的参数，用来控制启发式信息与信息素浓度作用的权重关系。 当 =0时，算法演变成传统的随机贪心算法，最邻近城市被选中的概率最大。当 =0时，蚂蚁完全只根据信息素浓度确定路径，算法将快速收敛，这样构建出的最优路径与实际目标差异较大，算法性能较差。,蚁群算法流程,信息素更新： (1) 在算法初始化时，问题空间中所有的边上的信息素都被初始化为0。 (2) 算法迭代每一轮，问题空间中的所有路径上的信息素都会发生蒸发，我们为所有边上的信息素乘上一个小于1的常数( : 信息素的蒸发率)。信息素蒸发是自然界本身固有的特征，在算法中能够帮助避免信息素的无限积累，使得算法可以快速丢弃

10、之前构建过的较差的路径。 (3) 蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素。蚂蚁构建的路径越短、释放的信息素就越多。一条边被蚂蚁爬过的次数越多、它所获得的信息素也越多。 (4) 迭代 (2)，直至算法终止。,蚁群算法流程,信息素更新： 信息素的更新公式： m：蚂蚁个数； ：信息素的蒸发率，规定0r1。 (i, j)：第k只蚂蚁在它经过的边上释放的信息素量，它等于蚂蚁k本轮构建路径长度的倒数。 Ck：路径长度，它是Rk中所有边的长度和。,蚁群算法流程,路径构建,信息素更新,蚁群算法的应用,共同特点 基于概率计算的随机搜索进化算法，在结构、研究内容、方法以及步骤上有较大的相似性； 存在的问题 （1）数学理论基础相对薄弱； （2）参数设置没有确切的理论依据，对具体问题和应用环境的依赖性大；,群智能优化的特点与不足,存在的问题 （3）比较性研究不足，缺乏用于性能评估的标准测试集； （4）不具备绝对的可信性，存在应用风险； 进一步的工作 （1）进一步研究真实群居动物的行为特征； （2）进一步研究算法的收敛性；,群智能优化的特点与不足,存在的问题 （3