粒子群算法

1粒子群算法1.粒子群算法简介1.1集群智能（SwarmIntelligence）Swarm可被描述为一些相互作用相邻的个体的集合体，蜂群、蚁群、鸟群都是Swarm的典型例子。鱼聚集成群可以有效地逃避捕食者，因为任何一只鱼发现异常都可以带动整个鱼群逃避。蚂蚁成群则有利于寻找食物，因为任何一只蚂蚁发现食物都可以带领蚁群来共同搬运和进食。一只蜜蜂或蚂蚁的能力非常有限，它几乎不可能独立存在于自然世界中，而多个蜜蜂或蚂蚁形成的Swarm则具有非常强的生存能力，且这种能力不是通过多个个体之间的能力简单叠加所获得的。社会性动物群体所拥有的这种特性能够帮助个体很好的适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，其根本原因在于个体之间存在着信息交互能力。信息交互过程不仅仅在群体中传播信息，而且群内个体还能处理信息，并根据所获得的信息改变自身的一些行为模式和规范，这就使得群体涌现出一些单个个体不具备的能力和特性，尤其是对环境的适应能力。这种对环境变化所具有适应的能力可以被认为是一种智能，称为集群智能（SwarmIntelligence）。集群智能具有如下几个特点：1）群内个体具有执行简单的时间或空间上的评估和计算的能力。2）群内个体能对环境（包括群内其他个体）的关键性因素的变化做出响应。3）群内不同个体对环境中某一变化所表现出的响应行为具有多样性。4）不是每次环境的变化都会导致整个群体的行为模式发生改变。5）环境所发生的变化中，若出现群体值得付出代价的改变机遇，群体必须能够改变其行为模式。1.2粒子群算法介绍粒子群算法，也称粒子群优化算法（ParticleSwarmOptimization），缩写为PSO，是根据集群智能SwarmIntelligence思想发展而来的一种算法，最早由Kennedy和Eberhart提出，该算法模拟了鸟群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置距离食物还有多远。那么找到食物的最优策略是什么呢，最简单有效的就是搜寻目前距离食物最近的鸟的周围区域。PSO中，每个优化问题的解都是搜索空间中的一只鸟，我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。同遗传算法类似，SwarmIntelligence也是一种基于群体迭代的，但并没有遗传算法用得交叉以及变异，而是粒子在解空间追随最优的粒子进行搜寻。PSO的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，有特别适合工程应用，并且没有许多参数需要调整。22.PSO产生的背景一．复杂适应系统复杂适应系统CAS理论的最基本的思想可以概述如下：我们把系统中的成员称为具有适应性的主体，简称为主体。所谓具有适应性就是指它能够与环境以及其他主体进行交流，在这种交流的过程中“学习”或“积累经验”，并且根据学到的经验改变自身的结构和行为的方式。整个系统的演变或进化，包括新层次的产生、分化和多样性的出现，新的、聚合而成的、更大的主体的出现等等，都是在这个基础上出现的。CAS的四个基本特点：首先，主体是主动的、活的实体；其次，主体与环境的相互影响，相互作用，是系统演变和进化的主要动力；再次，这种方法不像许多其他方法那样，把宏观和微观截然分开，而是把它们有机的联系起来；最后，这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。二．人工生命人工生命是研究具有某些生命基本特征的人工系统。包括两方面的内容：①研究如何利用计算计算研究生物现象；②研究如何利用生物技术研究计算问题。我们现在关注的是第二部分的内容。现在已经有很多源于生物现象的计算技巧，例如，人工神经网络是简化的大脑模型；遗传算法是模拟基因进化的过程的。现在我们讨论另一种生物系统：社会系统，更确切的说，是由简单个体组成的群落与环境以及个体之间的互动行为，也可称为“群智能”。3.基本PSO算法粒子群优化算法源于1987年Reynolds对鸟群社会系统boids的仿真研究，boids是一个CAS。在boids中，一群鸟在空中飞行，每个鸟遵守以下三条规则：1）避免与相邻的鸟发生碰撞冲突；2）尽量与自己周围的鸟在速度上保持协调和一致；3）尽量试图像自己认为的群体中靠近。图1近年来粒子群算法相关文摘数量3仅通过使用这三条规则，boids系统就出现非常逼真的群体聚集行为，鸟成群的在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体。Kennedy和Eberhart在其中加入了一个特定点，定义为食物，鸟根据周围鸟的觅食行为来寻找食物。他们的初衷是希望通过这种模型来模拟鸟群寻找食物源的现象，然而实验结果却揭示这个仿真模型中蕴涵着很强的优化能力，尤其是在多维空间寻优中。PSO中，每个优化问题的解都是搜索空间中的一只鸟，称为“粒子”。所有的粒子都有一个被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机的粒子。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外，也可以不用整个种群而只是用其中一部分的邻居。PSO算法数学表示如下：设搜索空间为D维，总粒子数为n。第i个粒子位置表示为向量Xi=(Xi1，Xi2，…，XiD)；第i个粒子“飞行”历史中的过去最优位置（即该位置对应解最优）为Pi=(Pi1，Pi2，…，PiD)，其中第g个粒子的过去最优位置Pg为所有Pi（i=1,…,n）中的最优；第i个粒子的位置变化率（速度）为向量Vi=(Vi1,Vi2,…，ViD)。每个粒子的位置按如下公式进行变化（“飞行”）：𝑣𝑖𝑑=𝑤×𝑣𝑖𝑑(𝑡)+𝑐1×𝑟𝑎𝑛𝑑()×[𝑝𝑖𝑑(𝑡)−𝑥𝑖𝑑(𝑡)+𝑐2×𝑟𝑎𝑛𝑑()×[𝑝𝑔𝑑(𝑡)−𝑥𝑖𝑑(𝑡)]（1）𝑥𝑖𝑑(𝑡+1)=𝑥𝑖𝑑(𝑡)+𝑣𝑖𝑑(𝑡+1);1≤i≤n1≤d≤D（2）其中，C1，C2位正常数，称为加速因子；rand()为[0，1]之间的随机数；w称为惯性因子，w较大适于对解空间进行大范围探查，w较小适于进行小范围开挖。第d维的位置变化范围为[-Xmaxd，Xmaxd]，速度变化范围为[-Vmaxd，Vmaxd]，迭代中若位置和速度超过边界范围则取边界值。粒子群初始位置和速度随机产生，然后按照公式（1）（2）进行迭代，直至找到满意的解。目前，常用的粒子群算法将全体粒子群分成若干个有部分粒子重叠的相邻子群，每个粒子根据群内历史最优Pl调整位置，即公式（2）中Pgd换为Pld。4.粒子群算法的应用PSO算法的优势在于算法的间接性，易于实现，没有很多需要调整的参数，且不需要梯度信息。PSO算法是非线性连续优化问题，组合优化问题和混合整数非线性优化问题的有效化工具。一．函数优化大量的问题最终可归结为函数的优化问题，通常这些函数是非常复杂的，主要表现为规模大，维数高，非线性，非凸和不可微分等特性，而且有的函数存在大量局部极小。许多传统确定性优化算法收敛速度较快，计算精度高，但对初值敏感，易陷入局部最小。而一些具有全局性的优化算法，如遗传算法，模拟退火算法，进化规划等，受限于各自得机理和单一结构，对高维复杂函数难以实现高效优化。PSO算法通过改进或结合其他算法，对高维复杂函数可以实现高效优化。4二．神经网络的训练PSO算法用于神经网络的训练中，主要包含3个方面：连接权重，网络拓扑结构及传递函数，学习算法。每个粒子包含神经网络的所有参数，通过迭代来优化这些参数，从而达到训练的目的。与BP算法相比，使用PSO算法训练神经网络的优点在于不使用梯度信息，可使用一些不可微iede传递函数。多数情况下其训练结果优于BP算法，而且训练速度非常快。三．组合优化许多组合优化问题中存在序结构如何表达以及约束条件如何处理等问题，离散二进制版PSO算法不能完全适用。研究者们根据问题的不同，提出了相应问题的例子表达方式。目前，已提出多种解决TSP、VRP以及车间调度等问题的方案。组合优化四．参数优化PSO算法已广泛应用于各类连续问题和离散问题的参数优化。例如，在模糊控制器的设计，机器人路径规划，信号处理和模式识别等问题上均取得了不错的效果。五．多目标优化PSO算法在多目标优化问题中的应用是一个很有意思的研究方向。最近，已经有一些基于PSO求解多目标优化问题的算法被提出。多目标优化的多重任务要求整个群体既要向Pareto最优前端逼近，又要能维持群体的多样性，因此在为粒子选取最优经验时，这两个方面都应兼顾到，然而它们之间有存在着一定的矛盾。PSO算法能够用于获取多目标优化问题的非劣最优解集。5.实现的C++代码#includestdafx.h#includemath.h#includetime.h#includeiostream#includefstreamUsingnamespacestd;Intc1=2;//加速因子Intc2=2;//加速因子intKmax=110;//迭代次数intGdsCnt;//物资总数intconstDim=10;//粒子维数intconstPNum=50;//粒子个数intGBIndex=0;//最优粒子索引doublew=1;//惯性权重doubleWmax=1;//最大惯性权重5doubleWmin=0.6;//最小惯性权重doublea=0.6;//适应度调整因子doubleb=0.5;//适应度调整因子intXup[Dim];//粒子位置上界数组intXdown[Dim]=;//粒子位置下界数组intValue[Dim];//初始急需度数组intVmax[Dim];//最大速度数组classPARTICLE;//申明粒子节点voidCheck(PARTICLE&,int);//约束函数voidInput(ifstream&);//输入变量voidInitial();//初始化相关变量doubleGetFit(PARTICLE&);//计算适应度voidCalculateFit();//计算适应度voidBirdsFly();//粒子飞翔voidRun(ofstream&,int=2000);//运行函数classPARTICLE//微粒类{public:IntX[Dim];//微粒的坐标数组IntXBest[Dim];//微粒的最好位置数组IntV[Dim];//粒子速度数组DoubleFit;//微粒适合度DoubleFitBest;//微粒最好位置适合度};PARTICLEParr[PNum];//粒子数组Intmain()//主函数{ofstreamoutf(out.txt);ifstreaminf(data.txt);//关联输入文件infGdsCnt;//输入物资总数Input(inf);Initial();Run(outf,100);system(pause);return0;}voidCheck(PARTICLE&p,intcount)//参数:p粒子对象,count物资数量{srand((unsigned)time(NULL));Intsum=0;for(inti=0;iDim;i++){if(p.XXup)p.X=Xup;6elseif(p.XXdown){p.X=Xdown;}if(p.VVmax){p.V=Vmax;}elseif(p.V0){p.V=0;}sum+=p.X;}while(sumcount){p.X[rand()%Dim]--;sum=0;for(inti=0;iDim;i++){if(p.XXup)p.X=Xup;elseif(p