【优化算法】基于matlab融合飞行机制的粒子群优化算法【含Matlab源码 1924期】

【优化算法】基于matlab融合飞行机制的粒子群优化算法【含Matlab源码 1924期】

二、基于莱维飞行的粒子群优化算法简介

1 引言 粒子群优化算法(particle swarm optimization algorithm,PSO)是在1995年提出的一种模仿自然界中鸟类和鱼类群体行为的智能优化算法。该算法具有概念简单、实现容易、收敛速度快等优点。在过去的二十来年间,有许多学者和粒子群优化算法的爱好者对其进行了全方位、多角度的研究,从算法改进到算法应用,在学术和工程领域被许多研究人员关注,取得了较大发展,成功应用于许多领域 。目前,粒子群优化算法已经成为进化算法领域应用最为广泛的重要分支之一,也是当今研究的热门问题之一。

粒子群优化算法在优化单峰函数最优值时,效果良好,通常能够达到令人满意的效果,但是在多峰函数优化时,粒子群优化算法虽然收敛速度极快,但是却极易陷入局部最优无法跳出,从而无法求解出最终目标值,即函数的全局最优值。目前改进粒子群算法主要方式为:通过引入其他智能算法的思想或策略,提高算法的搜索性能。

本文针对原始粒子群优化算法易陷入局部最优而进行改进,通过在粒子群优化算法的进化过程中引入莱维飞行的方式,增加粒子的活动和跳跃能力,促使粒子在陷入局部最优时具备跳出局部最优位置的能力,从而达到算法的最终目的,找到全局最优。

2 粒子群优化算法 在原始粒子群优化算法中,粒子模拟优化问题在搜索空间中的解 。粒子的适应度值是对粒子位置的评价值,通常由目标函数或者优化问题计算得出,粒子速度是一个向量,表示其将要移动的方向和距离 。PSO算法过程描述如下:

a)初始化。随机生成粒子种群,初始化包括随机生成每个粒子的位置和速度矢量。

b)进化迭代。每个粒子根据到目前为止自己的最优位置以及种群的最优位置,通过更新自身速度和位置的方式搜索整个解空间。粒子群位置更新时,粒子的最优位置以及种群最优位置也随之更新。

c)迭代终止。满足迭代终止条件,算法停止搜索。最后搜索到的最优位置就是最优解。

粒子速度更新式为

粒子位置更新式为

其中:j=1,2,…,d;t为当前迭代次数;w为惯性权重;c1、c2为学习因子;r1、r2为[0,1]内均匀分布的随机数。

算法的控制参数对粒子群优化算法的性能具有极大影响 ,参数c1和r1表示粒子受自身最优的影响程度,c2和r2表示粒子受种群最优的影响程度,通常取c1和c2为2。惯性权重决定了对粒子当前速度继承的多少。遇到两种条件则搜索终止:a)当前迭代次数t达到预设的最大迭代;b)优化求解满足算法精度要求。

2 莱维飞行 莱维分布是法国数学家莱维(Lévy)于20世纪30年代提出的一种概率分布,后来很多学者对其进行了大量研究。到目前为止,已经有学者证明自然界的许多动物和昆虫(如信天翁、蜜蜂和果蝇)的觅食轨迹符合莱维分布(Lévy distribution)模式 。

Lévy飞行是服从莱维分布的随机搜索路径 ,是一种短距离的搜索与偶尔较长距离的行走相间的行走方式,它能够解释自然界的很多随机现象,如布朗运动、随机行走等。目前莱维飞行行为已被用于优化领域,比如布谷鸟算法中就采用莱维飞行进行位置更新。莱维飞行能增加种群多样性和扩大搜索范围,因此采用莱维飞行的智能优化算法更容易跳出局部最优点 。

莱维飞行位置更新式为

其中:xi(t)表示xi第t代位置;⊕为点对点乘法;α表示步长控制量;Levy(λ)为随机搜索路径,并且满足:

莱维飞行实质是一种随机步长,其步长符合莱维分布,由于莱维分布十分复杂,目前还没有其实现。所以常用的是使用Mantegna算法模拟,Mantegna算法数学表示如下。步长s计算式为

其中:u、v为正态分布,定义

其中:

其中:β通常取值为常数1.5。

大量文献研究显示莱维飞行可以提高不确定环境下的搜索效率。为了说明莱维飞行的优越性,在MATLAB中作图对比莱维飞行和随机行走的区别。如图1所示,图中莱维飞行和随机行走都是200步,可以证明莱维飞行具有更广泛的搜索能力,因此能够扩大搜索范围,应用于粒子群优化算法能够提高粒子群的活力和跳跃能力,从而提高算法的全局寻优能力。

3 基于莱维飞行的粒子群优化算法 3.1 算法思想 在粒子群优化算法过程中,第t次迭代后得到一组较优的粒子群位置表示为xit(i=1,2,…,n),LPSO算法是不让xit直接进入下一次迭代,而是继续使用莱维飞行进行位置更新,使xit得到进一步搜索。

进一步对粒子位置进行莱维飞行的方式有:a)直接进行莱维飞行;b)判断粒子的位置是否长时间没有更新,若是长时间没有更新,再对粒子位置进行莱维飞行,否则不进行莱维飞行,也就是有选择地进行莱维飞行。实验证明方式a)虽然效果略好于方式b),但是方式a)的时间复杂度大大高于方式b),因此在实际应用时,其不利之处会带来极大不便。本文采用方式b)进行莱维飞行。

3.2 算法表示 首先记xi(t)(i=1,2,…,n),为第i个粒子,则粒子未进化迭代次数记为gi(i=1,2,…,n),表示种群粒子位置未进化到更优位置的迭代次数。粒子xi(t)的未进化迭代次数gi达到10时,则xi(t)通过式(3)进行莱维飞行。其中xi(t)'表示第t次迭代时莱维飞行后的粒子位置;xi(t)表示第t次迭代时莱维飞行前的粒子位置;α表示步长控制量;⊕表示点对点乘法;L(λ)表示莱维飞行。

对比xi(t)'和xi(t)位置对应的适应度值,更新粒子位置到xi(t)″,当xi(t)'的位置好于xi(t)时,xi(t)″采用xi(t)'位置,反之采用xi(t)位置。为进化方便,将xi(t)″记为xi(t)。

3.3 算法步骤 a)种群初始化。按照随机生成的方式初始化种群粒子的位置和速度,并找出当前的最优粒子位置和最优解。

b)计算适应值。评价粒子的适应度值fitness,并且将粒子的适应度值存储在pbest中,将种群中适应度值最优个体的适应度值存储于gbest中。

c)更新粒子位置。按照式(1)和(2)更新粒子的速度和位移。

d)更新个体最优。将粒子的适应度值与其未更新前的位置比较,取较好的粒子为本次迭代后的粒子。

e)更新全局最优。比较pbest和gbest的值,如果存在pbest好于gbest,则通过把pbest的值赋值给gbest的方式更新gbest。

f)莱维飞行。判断粒子位置是否未进化迭代次数超过10次,若是则使用式(3)莱维飞行更新粒子的位置。莱维飞行后,根据步骤d)f),更新个体最优pbest和全局最优gbest。

g)算法终止。若满足迭代结束条件,算法搜索停止;否则返回步骤c)继续搜索。

LPSO算法流程如图2所示。

图2 LPSO算法流程

三、部分源代码

clear all clc

四、运行结果

五、matlab版本及参考文献

1 matlab版本 2014a

2 参考文献 [1] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例（第2版）[M].电子工业出版社，2016. [2]张岩,吴水根.MATLAB优化算法源代码[M].清华大学出版社，2017. [3]王庆喜,郭晓波.基于莱维飞行的粒子群优化算法[J].计算机应用研究. 2016,33(09)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。