procedure PSO for each particle i Initialize velocity Vi and position Xi for particle i Evaluate particle i and set pBesti = Xi end for gBest = min {pBesti} while not stop for i=1 to N Update the velocity and position of particle i Evaluate particle i if fit (Xi) < fit (pBesti) pBesti = Xi; if fit(pBesti) < fit (gBest) gBest = pBesti; end for end while print gBest
对
应
蚁巢到食物的一条路径
关
找到的最短路径
系
信息素
问题的搜索空间 搜索空间的一组有效解
一个有效解 问题的最优解 信息素浓度变量
算法基本原理
蚁群算法流程
ACO基本要素
路径构建
每只蚂蚁都随机选择 一个城市作为其出发 城市，并维护一个路 径记忆向量，用来存 放该蚂蚁依次经过的 城市。蚂蚁在构建路 径的每一步中，按照 一个随机比例规则选 择下一个要到达的城 市。
算法流程
❖ 粒子速度与位置的更新
令 x i ( t ) 表示t时刻第i 个粒子 P 把速度矢量 v i ( t ) 加至当前位置，则iP在超空间来自位置。 的位置变为：i
xi (t)xi (t1 )vi (t)
算法流程
算法流程
//功能：粒子群优化算法伪代码 //说明：本例以求问题最小值为目标 //参数：N为群体规模
粒子群算法原理
粒子群算法的提出
源于对鸟群捕食行为的研究，是基于迭代的方法 简单易于实现，需要调整的参数相对较少 在函数优化、神经网络训练、工业系统优化和模糊
系统控制等领域得到了广泛的应用。
粒子群算法原理
粒子群算法的原理描述
鸟群： 假设一个区域，所有的鸟都不知道食物的位置，但 是它们知道当前位置离食物还有多远。
蚁群算法流程
pk(i, j)
(i, j)(i, j)
(i,u)(i,u),
if
jJk(i)
uJk(i)
0,
otherwise
蚁群算法原理
蚁群算法原理
蚁群算法原理
蚁群算法原理
入口
日光浴场
储备室 育婴室
寝室
蚁后室
蚁群算法原理
❖ 蚁群觅食的“双桥实验”
通过遗留在来往路径上的信息素（Pheromone） 的挥发性化学物质来进行 通信和协调。
❖ 蚁群觅食过程
蚁群算法
算法基本原理
自然界蚂蚁觅食行为
蚁群优化算法
觅食空间
蚁群
✓ 若加速系数、最大速度等参数太大，粒子群可能错过 最优解，算法不收敛；
✓ 而在收敛的情况下，由于所有的粒子都向最优解的方 向飞去，所以粒子趋向同一化（失去了多样性），使 得后期收敛速度明显变慢，同时算法收敛到一定精度 时，无法继续优化，所能达到的精度也不高。
内容提要
第九章：群智能系统 1.粒子群优化算法 2.蚁群算法 ……
PSO算法 每个解看作一只鸟，称为“粒子(particle)”，所有 的粒子都有一个适应值，每个粒子都有一个速度决 定它们的飞翔方向和距离，粒子们追随当前最优粒 子在解空间中搜索。
算法流程
算法流程
PSO算法 初始化为一群随机粒子，通过迭代找到最优。 每次迭代中，粒子通过跟踪“个体极值（pbest）” 和“全局极值(gbest)”来 更新自己的位置。
社会心理学
群体智慧 个体认知 社会影响
……
人工生命
鸟群觅食
鱼群学习
群理论
粒子群算法原理
粒子群优化算法
鸟群觅食现象
粒子群算法原理
❖ 从生物现象到 PSO算法
鸟群觅食现象
•鸟群 •觅食空间 •飞行速度 •所在位置 •个体认知与群体协作 •找到食物
鸟群觅食现象
类比关系
粒子群优化算法
粒子群优化算法
•搜索空间的一组有效解 •问题的搜索空间 •解的速度向量 •解的位置向量 •速度与位置的更新 •找到全局最优解
end procedure
开始 随机初始化每个粒子 评估每个粒子并得到全局最优 是 满足结束条件
否 更新每个粒子的速度和位置 评估每个粒子的函数适应值 更新每个粒子历史最优位置 更新群体的全局最优位置
结束
粒子群算法
❖ 粒子群算法的特点
✓ PSO算法收敛速度快，特别是在算法的早期，但也存在 着精度较低，易发散等缺点。
湘潭大学 人工智能课件 群智能
内容提要
第九章：群智能系统 1.粒子群优化算法 2.蚁群算法 ……
内容提要
第九章：群智能系统 1.粒子群优化算法 2.蚁群算法 ……
群智能
描述 群智能作为一种新兴的演化计算技术已成为研究焦 点，它与人工生命，特别是进化策略以及遗传算法 有着极为特殊的关系。
特性 指无智能的主体通过合作表现出智能行为的特性， 在没有集中控制且不提供全局模型的前提下，为寻 找复杂的分布式问题求解方案提供了基础。
蚂蚁系统 (Ant System， AS ) 的蚂蚁圈（Ant cycle）版本是最基本的 ACO算法，是以TSP作 为应用实例提出的。
信息素更新
当所有蚂蚁构建完路 径后，算法将会对所 有的路径进行全局信 息素的更新。注意， 我们所描述的是AS的 ant-cycle版本，更新 是在全部蚂蚁均完成 了路径的构造后才进 行的，信息素的浓度 变化与蚂蚁在这一轮 中构建的路径长度相 关。
粒子群算法原理
粒子群算法原理
粒子群算法的提出
由James Kenney（社会心理学博士）和Russ Eberhart（电子工程学博士， ）于1995年提出粒 子群算法（Particle Swarm Optimization, PSO）
粒子群算法原理
生物界现象
群体行为 群体迁徙 生物觅食
……
粒子群 优化算法
群智能
优点 灵活性：群体可以适应随时变化的环境； 稳健性：即使个体失败，整个群体仍能完成任务； 自我组织：活动既不受中央控制，也不受局部监管。
典型算法 蚁群算法（蚂蚁觅食） 粒子群算法（鸟群捕食）
粒子群算法原理
粒子群算法原理
大家应该也有点累了，稍作休息
大家有疑问的，可以询问和交流
粒子群算法原理