particle-swarm-optimization-粒子群优化算法

粒子群算法群体智能〔SwarmIntelligence〕生物学家研究说明：在这些群居生物中虽然每个个体的智能不高，行为简单，也不存在集中的指挥，但由这些单个个体组成的群体，似乎在某种内在规律的作用下，却表现出异常复杂而有序的群体行为。Swarm可被描述为一些相互作用相邻个体的集合体，蜂群、蚁群、鸟群都是Swarm的典型例子。鱼聚集成群可以有效地逃避捕食者，因为任何一只鱼发现异常都可带动整个鱼群逃避。蚂蚁成群那么有利于寻找食物，因为任一只蚂蚁发现食物都可带着蚁群来共同搬运和进食。一只蜜蜂或蚂蚁的行为能力非常有限，它几乎不可能独立存在于自然世界中，而多个蜜蜂或蚂蚁形成的Swarm那么具有非常强的生存能力，且这种能力不是通过多个个体之间能力简单叠加所获得的。社会性动物群体所拥有的这种特性能帮助个体很好地适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，其根本原因在于个体之间存在着信息交互能力。SwarmIntelligence蚁群算法〔AntColonyOptimization,ACO〕由Colorni，Dorigo和Maniezzo在1991年提出，它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下“信息素”〔pheromone〕作为蚁群前往食物所在地的标记。信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。蚁群算法ACO算法设计虚拟的“蚂蚁”，让它们摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。根据“信息素较浓的路线更近”的原那么，即可选择出最正确路线。目前，ACO算法已被广泛应用于组合优化问题中，在图着色问题、车间流问题、车辆调度问题、机器人路径规划问题、路由算法设计等领域均取得了良好的效果。也有研究者尝试将ACO算法应用于连续问题的优化中。由于ACO算法具有广泛实用价值，成为了群智能领域第一个取得成功的实例，曾一度成为群智能的代名词，相应理论研究及改进算法近年来层出不穷。蚁群算法(续)ACACAC生物社会学家指出：“至少从理论上，在搜索食物过程中群体中个体成员可以得益于所有其他成员的发现和先前的经历。当食物源不可预测地零星分布时，这种协作带来的优势是决定性的，远大于对食物的竞争带来的劣势。”鱼群觅食模型防止碰撞速度匹配中心聚集鸟群的飞行行为鸟群觅食模型FoodGlobalBestSolutionPastBestSolution社会型行为的模拟Randomly

searchingfoods先前经验认知行为26Max1社会行为１２6MaxRandomly

searchingfoods社会型行为的模拟粒子群算法(particleswarmoptimization，PSO)由Kennedy和Eberhart在1995年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体到达最优目的，是一种基于SwarmIntelligence的优化方法。同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。PSO的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。PSO算法简介

RussEberhart整合群体行为、人类决策与鸟群行为开展而成称为粒子群算法。 【Eberhart,Kennedy,1995】粒子群特性当其它鸟发现了更佳的觅食地点时，鸟群间会有某种类似播送的沟通行为，渐渐的将其它鸟群引领至较佳的地点这样的觅食行为是利用社会中所存在的互相影响的概念，来引领所有个体朝向最正确解位置起源粒子群的概念视为一个简单的社会系统每只个体被视为一个解答，称之为粒子(Particle)每个粒子经由适应函数的衡量而具有一个适应値起源PSO算法数学表示如下：设搜索空间为D维，总粒子数为n。第i个粒子位置表示为向量Xi=(xi1,xi2,…,xiD)；第i个粒子“飞行”历史中的过去最优位置pbest〔即该位置对应解最优〕为Pi=(pi1,pi2,…,piD)，其中第g个粒子的过去最优位置Pg为所有Pi(i=1,…,n)中的最优gbest；第i个粒子的位置变化率〔速度〕为向量Vi=(vi1,vi2,…,viD)。每个粒子的位置按如下公式进行变化〔“飞行”〕：根本PSO算法(续)根本PSO算法(续)〔1〕〔2〕其中，C1,C2为正常数，称为加速因子；rand()为[0，1]之间的随机数；w称惯性因子，w较大适于对解空间进行大范围探查(exploration)，w较小适于进行小范围开挖(exploitation)。第d〔1≤d≤D〕维的位置变化范围为[-XMAXd,XMAXd]，速度变化范围为[-VMAXd,VMAXd]，迭代中假设位置和速度超过边界范围那么取边界值。粒子群初始位置和速度随机产生，然后按公式(1)(2)进行迭代，直至找到满意的解。目前，常用的粒子群算法将全体粒子群(Global)分成假设干个有局部粒子重叠的相邻子群，每个粒子根据子群(Local)内历史最优Pl调整位置，即公式(2)中Pgd换为Pld。根本PSO算法(续)每个寻优的问题解都被想像成一支鸟，也称为“Particle”。所有的Particle都有一个fitnessfunction以判断目前的位置之好坏，每一个Particle具有记忆性，能记得所搜寻到最正确位置。每一个Particle还有一个速度以决定飞行的距离与方向。PSO算法局部最优解全局最优解运动向量惯性向量StudyFactor速度与位置更新HereIam!Thebest

positionofteamMybestpositionx(t)pgpivPBestgBestx(t+1)初始化：将种群做初始化，以随机的方式求出每一粒子之初始位置与速度。评估：依据适应度函数计算每一个粒子适应度以判断其好坏。计算自身最优：找出每一个粒子到目前为止的搜寻过程中最正确解，这个最正确解称之为Pbest。计算全局最优：找出种群中的最正确解，此最正确解称之为Gbest。更新速度和位置：根据速度与位置公式更新每一粒子的速度与位置。算法终止.返回步骤2继续执行，直到获得一个令人满意的结果或符合终止条件为止。算法流程粒子数:一般取20–40.其实对于大局部的问题10个粒子已经足够可以取得好的结果,不过对于比较难的问题或者特定类别的问题,粒子数可以取到100或200粒子的维数:这是由优化问题决定,就是问题解的长度粒子的范围:由优化问题决定,每一维可以设定不同的范围Vmax:最大速度,决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度学习因子:c1和c2通常等于2.不过在文献中也有其他的取值.但是一般c1等于c2并且范围在0和4之间中止条件:最大循环数以及最小错误要求.参数选择相同点都是基于种群的都需要适应度函数.都是随机计算技术

不能保证100%收敛

不同点PSO没有交叉变异等进化操作.PSO中通过粒子的竞争与协作实现种群进化粒子具有记忆能力

优点PSO容易实现具有较小的调整参数收敛速度快、解质量高、鲁棒性好

2024/6/231PSO与遗传算法的比较

IEEETRANSACTIONONEVOLUTIONARYCOMPUTION