微粒群优化算法及其应用-讲座2015

12023/9/23微粒群优化理论及应用张勇中国矿业大学信电学院10月29日，中国科学院文献情报中心与汤森路透旗下的知识产权与科技事业部在北京共同发布《2015研究前沿》报告。

在数学、计算机科学与工程领域，《2014研究前沿》中“基于粒子群算法的搜索优化”是当年最年轻的热点前沿，今年“粒子群优化与差分进化算法”和“忆阻器、忆阻电路及忆阻神经网络的相关研究”入选今年重点热点前沿。32023/9/23目录群体智能基本微粒群优化算法微粒群优化算法的收敛性微粒群的拓扑结构并行微粒群优化算法微粒群优化算法的改进或变形面向多目标优化问题的微粒群优化算法基于微粒群优化的多机器人协同搜索我们的工作42023/9/231.群体智能群体智能(Swarmintelligence,SI)这个概念来自对自然界中昆虫群体的观察和模拟。一般群居性生物通过协作表现出的宏观智能行为特征被称为群体智能。一个群体智能系统通常包含多个简单的智能个体(智能体)，每个智能体与其它智能体以及环境之间存在相互作用。所有智能体遵守着非常简单的规则，尽管没有中心控制结构指导单个智能体的行为，但是，各智能体之间直接或间接的局部通信催生了系统复杂全局行为的产生。(来自Wikipedia)1.1群体智能的概念52023/9/2362023/9/23大自然中的智能群体：蚂蚁群、鸟类群体、细菌繁衍和鱼群等等。典型的群体智能优化算法包括：蚁群优化算法、微粒群优化算法、鱼群算法和蛙跳算法等。72023/9/231.2蚁群优化

蚁群优化(Antcolonyoptimization,ACO)是Marco在1992年提出的一种快速随机优化技术，被用于处理那些可以归纳为发现图中最短路径的计算问题。(DorigoandStützle,2004)

现实世界中，(初始状态)每个蚂蚁将在一定范围内随机游走，并通过在所经过路径上遗留信息素的方式，不断把相关的食物信息反馈给蚁群。如果其他蚂蚁发现了那条路径，那么这些蚂蚁很可能不再保持原来的随机游走，而跟随这条路径(一条路径上的信息素越多，其他蚂蚁选择这条路径的可能性越大)。如果由该路径他们最终发现了食物，那么他们将在这条路径上继续增加信息素。由于这条路径上信息素的不断增加，最终所有蚂蚁将找到食物。82023/9/23有兴趣的同学可以参考Marco的AntColonyOptimization

个人网址,或者他的专著“AntColonyOptimization”。(该图来自TheresaMeggieetal.)(a)(b)(c)(d)92023/9/23微粒群优化算法(Particleswarmoptimization,PSO)是Kennedy和Eberhart在1995年提出的。1.3微粒群优化算法

正如提出者所说“微粒群优化算法模拟了昆虫(或人类)的社会行为。个体在学习自身经验的同时相互交换信息，由此，种群成员将逐渐移到问题空间中较好的区域。”为什么取名“微粒”而不是“点“呢？Kennedy和Eberhart都认为速度和加速度比较适合应用于微粒。(X.LiandA.P.Engelbrecht)102023/9/23粒子群优化算法的发展

1997年，Eberhart首次提出了微粒群优化算法的离散二进制版，揭开了离散变量微粒群优化算法研究的序幕。1998年和1999年，Shi和Clerc等分别提出了基于惯性模型和压缩因子的算法模型。2002年,Clerc等给出了PSO的稳定性和收敛性分析。2002年，Coello等把PSO算法用于多目标优化问题，为算法研究注入了新的动力。

2004年，Kennedy和Mendes研究微粒间拓扑结构，给出了一种全息微粒群优化算法。

2006年，Parrott和Li提出了用于动态多峰优化问题的PSO。112023/9/23微粒群优化算法的应用

函数优化——数值函数优化，动态、多峰值、多目标组合优化——旅行商问题、布局优化等问题生产调度——工件加工问题自动控制——智能控制器优化、最优控制器设计机器人学——路径规划、协调控制机器学习——分类、数据挖掘图像处理——多边形近似问题机械设计——碳纤维强化塑料神经网络训练参数辨识等等122023/9/23相关资源2001年,Kennedy等出版优秀著作《SwarmIntelligence》，对微粒群优化及其应用作了全面而系统的论述。专著

1999年首届进化计算会议上微粒群优化算法即被定为会议讨论议题。IEEE群体智能研讨会GeneticandEvolutionaryComputation国际会议会议及其杂志网址

，

/~hux/pso.shtml.EvolutionaryComputation(MITpress)IEEETransactionsonEvolutionaryComputationIEEETransactionsonNeuralNetworkIEEETransactionsonSystems,Man,andCyberneticsPart:A,BSwarmIntelligence132023/9/232.1算法原理1）一个鸟群正在某一区域内随机寻找食物，在这一区域只有一份食物。

2）鸟群不知道这份食物究竟在哪里，但是它们知道食物距离它们有多远以及它们同伴的位置

首先给出两个假设：鸟群怎样尽量快的找到食物？一个最有效的方法就是跟随或学习目前离食物最近同伴的位置。2.基本微粒群优化算法142023/9/23单个鸟整个鸟群鸟群寻找食物的飞行策略单个微粒由多个微粒组成的微粒群微粒位置的更新策略PSO鸟群行为最大化问题一个微粒代表问题的一个解每个微粒都有一个由被优化函数值决定的适应值

每个微粒通过跟踪自身找到的最好位置以及邻域内其它微粒找到的最好位置，完成对整个搜索空间的搜索PSO就是对鸟群或鱼群寻找食物这种群体行为的模拟。152023/9/23基本PSO

：t次迭代后第i个微粒的位置；：微粒从初始到目前迭代次数所得到的最好位置（即自身找到的最好位置），通常称为微粒个体最优点；

：微粒邻域内所有微粒从开始到目前迭代次数所得到的最优位置，通常称为微粒全局最优点；

：两个加速度系数，用来控制和对微粒飞行方向的影响。：[0,1]之间服从均匀分布的两个随机数；162023/9/23惯性权重(续)172023/9/23基本PSO速度冲量认知项社会项微粒速度更新公式(1a)包括三项:速度冲量：指引微粒继续飞行的先前微粒速度；认知项：当前微粒重新返回所经最好位置的趋势；社会项：当前微粒被其邻域所找到的最好位置吸引的趋势。邻域拓扑结构可以用来控制微粒之间信息的传播，即社会项的影响，部分典型结构如全连接形、环形或星形等。全局版PSO(gbestPSO)和局部版PSO(lbestPSO)。182023/9/23PSO程序(最大化问题)1.在搜索空间中随机生成N个微粒，组成微粒群;2.重复下列步骤：for(i=1toN)

评价微粒适应值；iffor(j=1toD)//*D为决策变量维数*//

由式(1)更新当前微粒的第j个分量；endend3.如果满足终止条件，那么终止算法，并输出结果.

//*更新微粒全局最优点*//微粒优化中微粒变化图192023/9/23惯性权重由于速度冲量容易导致微粒按照先前速度方向继续移动，因而，Shi提出个惯性权重w，用来控制先前微粒速度所产生的影响。惯性权重在没有的特定情况下，基于惯性权重的PSO也能收敛。2.2控制参数分析202023/9/23惯性权重(续)通过调节w值，可以控制PSO的全局探索和局部开发能力：

w≥1：微粒速度随迭代次数的增加而增加，微粒发散。0<w<1：微粒减速，算法的收敛性依靠惯性权重和。

w<0：微粒速度随迭代次数的增加而减小，最后趋近0，算法收敛。实验表明，w=0.7298和时算法具有较好的收敛性能。

Eberhart和Shi：w的线性递减策略；陈贵敏等：开口向下抛物线、开口向上抛物线和指数曲线等3种非线性权值递减策略；Shi和Eberhart：以当前算法最优值为模糊系统的输入，给出一种惯性权重的模糊控制方法。自适应或动态惯性权重值：

212023/9/23加速度系数(Accelerationcoefficients)：两个加速度系数，又称学习因子，用来控制和对微粒飞行方向的影响。

每个微粒执行局部搜索；

微粒群转化为一个随机爬山法；微粒逐渐移向和的加权均值；

算法比较适合于单峰优化问题；

算法比较适合于多峰优化问题。222023/9/23自适应或动态加速度系数：

实验建议：Ratnaweera等：基于迭代次数对两个加速度系数进行动态调节，其中，随进化代数增加而减小；相反，随进化代数增加而增大。232023/9/233.PSO算法的收敛性

VandenBergh(2002)、Trelea(2003)以及Bergh和Engelbrecht(2006)

已经证明PSO能够收敛到一个平衡状态。那么，

对于全局版PSO算法，如果

这意味着随着迭代次数的增加所有微粒将收敛到一个点。但是，这不意味着微粒个体最优点和全局最优点的加权和就是问题的最优解。242023/9/234.微粒群拓扑结构每个微粒的行为受到邻域微粒的影响，该邻域可以看做微粒群拓扑中的一个子区域。微粒群拓扑中所有子区域通过一定方式相互关联，共同对问题空间进行协同搜索。全局版PSO：每个微粒受整个微粒群所发现最好位置的影响，即每个微粒的邻域是整个微粒群；局部版PSO：每个微粒受所定义的局部邻域中微粒的影响，而微粒的邻域由拓扑图中每条边上距离它最近的微粒组成。常用的两类PSO算法：252023/9/23几种拓扑结构：全连接拓扑(all)环形拓扑(ring)VonNeumann拓扑星状拓扑(star)锥形拓扑(pyramid)四聚类拓扑(clusters)全连接拓扑为全局拓扑，其余都为邻域规模不同的局部拓扑。部分图来自Mendes和Kennedy(2004).262023/9/23我们应该选择那种拓扑结构？全连接拓扑信息传输速度快，相应地，PSO算法收敛速度快，但是易于早熟收敛；环形拓扑信息传输速度最慢，相应地，PSO算法收敛速度慢，但是微粒有更多的机会发现最优解。Kennedy(1999)指出：在处理复杂问题时，采用较小邻域的PSO算法性能较好；在处理简单问题时，采用较大邻域的PSO算法性能较好。Mendes和Kennedy(2002)在对比不同拓扑结构时发现：VonNeumann拓扑优于其它拓扑。

Suganthan(1999)，在PSO算法初期采用局部版PSO,后期采用全局版PSO;

Hu和Eberhart(2002),

提出了动态拓扑结构的概念。每次迭代时选择与当前微粒最近的m个微粒作为它的新邻域。272023/9/235.并行微粒群优化算法

面对复杂优化问题,PSO在优化速度上显得“力不从心”。

为求得满意的优化结果，常需要计算相当多次的函数值；对于一些实际问题，计算单个函数值就可能需要付出昂贵代价。并行算法具有如下优点(Jaimes,2007)：提高计算速度，减少优化时间；为问题提供更多的存储空间；提高种群的多样性；易于与其它算法并行。并行PSO的分类：

★主从式模式★细粒度模式★粗粒度模式282023/9/23主从式模式，又称全局式PSO主处理器：执行微粒全局最优点的选择、微粒位置更新等算子；从处理器：并行计算多个微粒的函数值。算法每次迭代时，

主处理器分配新生微粒到各从处理器；

从处理器计算所接受微粒的函数值，并将其返回给主处理器；

主处理器利用从处理器返回的微粒函数值，首先更新微粒的个体最优点和全局最优点，接着，更新微粒的速度和位置。

返回。缺点：由于未对PSO算法框架进行改动，所以该模式存在主从节点负荷忙闲不均衡的问题292023/9/23细粒度模式，又称扩散式PSO赋予每个微粒一个处理器。对每个微粒，微粒全局最优点的选择和微粒位置更新皆在其所处处理器及其邻域(红色图标)中进行。该模型可以最大限度的发挥算法的并行潜力但算法的实现对处理器数量要求很高，其应用范围受到了很大限制。优缺点：302023/9/23粗粒度模式，又称迁移式PSO将随机生成的初始种群依处理器个数分割成若干个子种群，各个子种群在不同的处理器上并行进化。每经过一定进化代数，各子群间交换若干最优信息。

该模型不仅通信代价较小,而且非常适合在通信带宽较低的集群上运行,是适应性强且应用范围广的并行模型.可以提高种群多样性，防止未成熟收敛的发生优点：

312023/9/236.微粒群优化算法的改进或变形最初的PSO算法是从处理连续优化问题中发展起来的。

Kennedy和Eberhart首次将实数版PSO扩展为二进制PSO。微粒位置为二进制向量，微粒速度仍为浮点向量；微粒速度将被逻辑函数s(v)转化为判断位置项选择0还是1的概率。6.1二进制PSO(BinaryPSO)322023/9/23为了防止s(v)饱和，Kennedy等还建议将限制在[-4,4]之间。其中，具体更新公式如下：332023/9/236.2简洁PSO(BareBonesPSO)简洁微粒群优化算法是Kennedy在2003年提出的。删除了传统的微粒速度更新公式。利用一个基于微粒全局最优点和个体最优点的高斯采样公式，更新微粒位置：如果固定和不变，PSO将以中心在和之间的钟形分布对搜索空间进行采样。342023/9/236.3全息PSO(FullyInformedPSO)先前微粒更新公式：令，得由上式可见，微粒趋向于收敛到一个确定点，该点是微粒和全局最优点的加权和。个体最优点352023/9/23进一步，可把扩展为关于多个邻域微粒信息的加权和：其中，NB为当前微粒的邻域，为NB中第k个微粒的个体最优点。如果|NB|=2，和，那么上式退化为传统PSO。

除和之外，上式允许我们自由利用更多的邻域信息。362023/9/236.4其它本态性PSO算法(Essen