粒子群优化算法

第27卷第4期华侨大学学报(自然科学版)Vol.27 No. 42006年10月.Jourmal of Huaqiao University ( Natural Science )Oct. 2006文章编号1000-5013( 2006 )04 0343-05.粒子群优化算法崔长彩李兵张认成(华侨大学机电及自动化学院,福建泉州362021 )摘要论述粒子 群优化算法( PSO )的基本原理、特点实现步骤,以及PSO的各种改进技术,包括基于PSO参数的改进技术(主要是惯性权重)基于遗传算法进化机理的改进技术(受遗传算法启发提出的带交叉算子的PSO、带变异算子的PSO、带选择算子的PSO),以及其他算法融合的改进技术(模拟退火PSO、免疫PSO、混沌PSO)并总结PSO热点研究问题.关键词粒子群 , 优化算法,遗传算法,惯性权重中图分类号TP 301.6文献标识码A1995年,Kennedy和Eberhartf12]提出一种较为新颖的优化算法一粒子群优化算法(ParticleSwarm Optimization ,PSO ).该算法与蚁群算法( Ant Colony Optimization , ACO )相似，也是一种基 于群体智能Swarm Inelligence , SI )的优化算法即模拟鸟群觅食的过程,而其功能与遗传算法( Genetic Algo-rithm ,GA )非常相似. PSO优化算法起源于对简单社会系统的模拟是-种很好的优化工具由于其简单易于实现的优点被越来越多地应用于函数优化、神经网络训练模式分类,以及传统优化算法的应用领域.但是其数学基础不完善实现技术不规范在适应度函数选取、参数设置、收敛理论等方面还存在许多需要深入研究的问题.围绕PSO的实现技术和数学理论基础以Kennedy和Eberhart 为代表的许多专家学者-直在对PSO做深入的探索尤其在实现技术方面提出了各种改进版本的PSO.1基本PSO原理和特点1.1 算法原理PSO的基本概念源于对鸟群(BirdFlock)捕食行为的研究,人们从鸟群捕食模型当中得到启示并用于解决优化问题(1-3).在PSO中,每个优化问题的解都是搜索空间中的一只鸟称之为粒孔( Parti-cle).所有的粒子都有-个由被优化的函数决定的适应度值(FitnessValue)每个粒子还有-个速度( Velocity )决定它们飞翔的方向和距离. PSO初始化为-群随机粒子(随机解).然后粒子们就追随当前的最优粒子在解空间中搜索找到最优解.在每一次迭代/ 飞跃中粒子通过跟踪两个极值”来更新自己.第一个就是粒子自己找到的最优解, 称个体极值( Personal Best );另-个极值是整个粒子群目前找到的最优解称全局极值( Global Best ).假设用X;=(xn x a .. xid )表示第i个粒子其中d是粒子的维数,它经历过的最好位置(有最好的适应值)表示为p.=(pa P2 P3. Pu )而整个群体经历过的最好位置表示为gn=(Pa1 Pea Ps,.. pa:).粒子i的速度用V;=( 0; v2 D3... pia )表示.对于每一代个体在找到两个最优值时粒子根据如下公式来更新自己的速度和位置(45)即'd = wXDu +C; X randon( ) x(pad - xn中国煤化工 -xa), .(1)x;a=xij(2 ):fYHCNMHG收稿日期2006-03-08作者简介崔长彩 1972-)女副教授博士后主要从事精密测量技术与优化算法方面的研究. E-mail xcuichc@ hqu.edu. cn基金项肪韻建猶青年科技人才创新基金资助项目(2005J030)344华侨大学学报(自然科学版)2006年其中20为惯性权重random( )是介于(0 1 )之间的随机数& r2 是学习因孔(或者称为加速度系数).另外粒子的每一维速度都会被-一个最大速度Vm.限定如果某一维的速度更新后的速度超过用户设定的V.那么这一维的速度就被限定为V. .1.2基本PSO实现步骤PSO主要有6个基本实现步骤4).( 1 )初始化每个微粒的起始位置和速度.( 2 )计算每一个微粒的适应度值.( 3 )对于每一个微粒，如其适应度值优于其本身经历过的最好位置则用当前的适应度值作为其新的最好位置.(4)对于整个微粒群如果存在这样的个体其适应度值优于整个微粒群的历史最好位置则用整个微粒群中适应度值最好的个体作为新的整体最好位置.(5)对于每一个微粒先根据方程(1)重新计算微粒的速度然后根据方程(2)重新计算微粒的位置.(6)如果达到最大迭代次数或者最小准则终止程序否则跳转到步骤( 2).1.3基本PSO的特点虽然PSO的功能与遗传算法非常相似,但是其实现技术却有如下5个显著的优点.( 1 )无交叉和变异运算依靠粒子速度完成搜索.(2)有记忆性粒子和群体的历史最好位置可以记忆并传递给其他粒子.( 3 )需调整的参数较少结构简单易于实现.( 4 )采用实数编码，直接由问题的解决定问题解的变量数直接作为粒子的维数.(5)收敛速度快在迭代进化中只有最优的粒子把信息传递给其他粒子，属于单向信息流动.2 PSO改进技术由于粒子群优化算法是-种比较新颖的进化算法,在近10年的发展中其数学理论基础、实现技术、应用技术等方面都获得许多进展.以Kennedy和Eberhart为代表的许多专家、学者都对其产生极大的兴趣并在各自的领域内进行了许多卓有成效的探索.PSO的改进技术主要围绕基于PSO参数(主要是惯性权重)的改进技术基于进化机理的改进技术与其他算法融合的改进技术等等.2.1基于 PSO参数的改进技术对PSO参数的研究主要针对式1 )中的惯性权重w、学习因子c1和c2其中对PSO参数取值的改进技术中研究最多的是，关于惯性权重的取值问题. PSO最初的算法是没有惯性权重的12].自从PSO基本算法中对粒子的速度和位置更新引入惯性权重45] ,包括Eberhart ,Shi 等在内的许多学者对其取值方法和取值范围作了大量的研究(6-9].目前大致可分为固定惯性权重取值法'121、线性自适应惯性权重取值法(45)、非线性惯性权重取值法10-13)等.最初的PSO算法可认为是将惯性权重固定为1~3)后来,Shi等'4~6]建议按照线性递减规律改变惯性权重取值其具体计算公式为(l) =- max_( w; -w{)+ o)p(3 )式中1当前进化代数1ms最大进化代数0;初始惯性权重w1最终惯性权重.线性惯性权重的引入可以调节PSO的局部与全局搜索能力.为改善PSO局部与全局搜索增强PSO对复杂系统的寻优能力Shi等又提出模糊惯性权重取值法'10].该法需要在优化之前根据专家知识建立模糊控制规则具体规则有9条即有两个输入和一个输出每个输入和输出定义了3个模糊集.其中,-个输入为当前的全局最好适应值另一个为当前的惯性权重而输出为惯性权重的变化.张丽平等"提出随机惯性权重取值法,以更好地平衡算法在搜索过程中的寻优能力使其更好地适应复杂系统的实际环境其方法是先根据适应值定义一个最优适应值变化率k即h =((I)-J(t- 10中国煤化工(4)上式中1( t )是种群在第t代的最优适应值( t- 10 )是和YHCNMHG适应值k表示在进化10代内最优适应值的相对变化率.当h≥0.05时惯性权重按c=a +0. 5r取随机值而h<0.05时,则按o=ar +0.5r取值.其中r是[01 ]之间的随机数.数学期望值将随k:而变当k≥0. 05时期望值比wo)=a| +0.25 ;而当k<0.05 时期望值E w)=a2 +0.25 ,且令a1>a2.为了改害算法的收敛速度和对多维空间的精细搜索能力,Chatterjee等121提出非线性惯性权重的第4期崔长彩等:粒子群优化算法PSO其惯性权重的自适应变化式为a(t) =[(tmx -t)"/( tmax)"]w; -w)+ W)p.(5 )在式(5 )中n为非线性调节指数.对n取值为0.6 0.8 ,1.0 1.2和1.4等作了实验研究给出不同指数取值时惯性权重随进化迭代次数的变化规律.其中,当n取值为1.0时惯性权重为线性变化规律.为改善线性减小惯性权重存在的不足王启付等(13)提出了一种动态改变惯性权重的粒子群算法,即在优化迭代过程中惯性权重值随粒子的位置和目标函数的性质而变化，从而增强了搜索方向的启发性.其方法是在惯性权重计算中引入工程指数项e即at)=e/d-'.其中a'=-21Nx)(xmin)I 1=0,mi= I1 2.. (x.)=_ min (x)(x{)为第i个粒子在第t代的适应度值( xm )为最优粒子在第t代的适应度值.除了对惯性权重取值方式的研究同时还对其取值区间的探讨,目前除了将其固定为1.0之外还有0.9 0.4]5b)[0.95 0.214)[ 1.4 ρ]4等.2.2基于遗传算法进化机理的改进技术PSO是一种随机优化技术其实现技术与遗传算法( GA )非常相似15.16).受GA的启发人们提出多种改进的PSO算法,如带交叉算子的PSO、带变异算子的PSO、带选择算子的PSO等等. Lovbjerg等17]在粒子群每次迭代后按几率在粒子间交换各维通过交叉来生成更优秀的粒子算法对某些多峰函数效果较好. Higashi 等18)提出带变异算子的粒子群优化算法希望引入变异算子增加群体的多样性避免陷入局部最优.吕振肃等I9'提出了-种新的基于群体适应度方差自适应变异的粒子群优化算法.该算法在运行过程中根据群体适应度方差及当前最优解的大小,来确定当前最佳粒子的变异概率,变异操作增强了粒子群优化算法跳出局部最优解的能力.针对PSO算法存在易陷入局部最优点的缺点李宁等'20)提出了带变异算子的PSO算法.它在算法搜索的后期引入变异算子使算法摆脱后期易于陷入局部极优点的束缚同时又保持前期搜索速度快的特性.付国江等(21 )提出了一种新型的PSO变异策略CP。 变异.该变异首先定义了全局收敛度最大位置C并在搜索循环的每次迭代中,以一定的概率交替使用C和P。(所有粒子历史最好位置)来代替原迭代公式中的P.通过对4个多峰的测试函数所做的对比实验表明,C变异增强了搜索能力求得全局最优的成功率和收敛到速度大为提高.方法克服了原始的PSO算法易于收敛到局部最优点的缺点,也明显优于对原始PSO进行传统变异的方法. Angeline' 2将选择算子引入PSO中选择每次迭代后的较好粒子复制到下一代，以保证每次迭代的粒子群都具有较好的性能.这种算法对某些单峰函数效果较好.2.3与其他 优化算法融合的改进技术实践表明各种计算方法都有其各自的优点和长处而粒子群优化算法同样具有其特点和优点,但是还存在许多不足之处.因此人们希望通过借鉴其他算法的优点取长补短,改善和提高PSO算法的精确性、稳定性和适应性.吴晓军等(231提出一个比遗传规划算法GP更优的GA-PSO混合的规划算法.方法通过将层次型问题的描述转换为固定长度线形结构的描述方式使GP算法与GA规划算法达到统一通过构造运算符将PSO算法引入到GA规划算法框架之中形成GA-PSO混合规划算法.结果从解的描述、遗传算子、PSO运算符的构造再到GA-PSO算法框架提出了完整的GA-PSO混合规划算法.高鹰、高尚等24-26]提出模拟退火算法( Simulating Algorithm , SA )思想的粒子群优化算法.在基本粒子群优化算法中虽然粒子速度作了限制不会变化太大但位置更新时未作限制就有可能新的位置会变得很坏引起收敛速度缓慢所以对更新的位置也要作限制.限制方法采用模拟退火算法思想其基本思想是从-给定解开始的,从邻域中随机产生另一个解接受准则允许目标函数在有限范围内变坏,以-定概率接受新的解.高尚等25)给出了3种方法改进.受生物体中国煤化Iicial Immunity,Al )的启发高鹰等127)把免疫系统的免疫信息处理机制引入到CNMHG了免疫粒子群优化算法.这种免疫粒子群优化算法结合了粒子群优化算法具有的全局寻优能力和免疫系统的免疫信息处理机制实现简单,改善了粒子群优化算法摆脱局部极值点的能力提高了算法进化过程中的收敛速度和精度.文[ 28 ~31 ]把混沌寻优( Chaos )思想引入到粒子群优化算法中提出混沌粒子群优化算法.这种方法利用混沌逸動的随机性、遍历性和规律性等特性对当前粒子群体中的最优粒子进行混沌寻优然346华侨大学学报(自然科学版)2006年后把混沌寻优的结果随机替换粒子群体中的一个粒子.通过这种处理使得粒子群体的进化速度加快,从而改善了粒子群优化算法摆脱局部极值点的能力提高了算法的收敛速度和精度.3 PSO热点研究问题PSO一种新兴的优化算法其数学基础薄弱在收敛性理论、计算性能、实现技术和参数的设置等方面缺乏严密的数学基础其应用大多数仍然依靠经验和实验.因此，文[32 ,33 ]展开了-系列研究取得了-些建设性成果,如关于算法收敛性的分析.值得一提的是早期的PSO主要应用于连续空间优化问题34-361.随着实现技术的发展和工程问题的需要,PSO也被大量用于离散优化问题并取得令人满意结果,但是对其应用领域的研究还需进一步 加强.2004年,EEE 进化计算会议PSO专集( Guest EditorialSpecial Issue on Particle Swarm Optimization )指出了PSO目前研究的主要问题(37)算法收敛性的分析、粒子群拓扑结构、参数选择与优化、与其他进化算法融合技术、应用领域的开拓等等.毋庸置疑,对PSO算法数学基础、实现技术、应用领域的深入研究仍将是PSO的研究热点而且可能需要相当长的时间.PSO作为一种发展仅仅10年的优化算法,引起人们的广泛关注.尽管它还有许多不尽人意的地,方需要进一步的发展和完善但是其优势给了它强大的生命力.目前,关于PSO的国外文献较多并开辟有专门的网站( http ://www. particleswarm. net ) ,而国内研究刚刚起步,所 见文献主要集中在近几年,而且相对较少.参考文1 Kennedy J , Eberhart R C. Particle swarm optimizatior[ J] . Institute of Electrical and Electronics Engineers ,1995 ( 11 ):1942~1 9482 Eberhart R C , Kennedy J. A new optimizer using particle swarm theory[ J ]. Institute of Electrical and Electronics Engi-neers ,1995 ( 10 ) 39 ~433 Kennedy J. The particle swarm : Social adaptation of knowledgeC J ] Institute of Electrical and Electronics Engineers ,1997,( 4):303 ~ 3084 Shi Y , Eberhart R C. A modified particle swarm optimizer[ J ] Institute of FElectrical and Electronics Engineers , 1998 ,(5):69 ~735 Shi Y , Eberhart R C. Parameter selection in particle swarm optimization[ J ] Lecture Notes in Computer Science ,1998 ( 1447 ) :591 ~ 6006 Shi Y , Eberhart R C. Empirical study of particle swarm optimization[ J ] Institute of Electrical and Electronics Engineers ,1999 (7 )1 945~1 9507 Clerc M. The swarm and the queen :Towards a deterministic and adaptive particle swarm optimization[ J ] Institute of Elec-trical and Electronics Engineers 1999 ,(7 ):1 951~1 9578 Eberhart R C ,Shi Y. Comparing inerta weights and constriction factors in particle swarm optimization[ J ] Institute of Elec-trical and Electronics Engineers ,2000 ,( 7 ):84~889 Yasuda K ,Ide A , Iwasaki N. Adaptive particle swarm optimization[ J ] Institute of Electrical and Electronics Engineers ,2003 ( 10):1 554~1 55910 Shi Y , Eberhart R C. Fuzzy adaptive particle swarm optimization[ J ] Institute of Electrical and Electronics Engineers ,2001 ,(5):101 ~ 10611 张丽平,俞欢军,陈德钊,等.粒子群优化算法的分析与改进J]信息与控制,2004 ,33(5):513 ~51712 Chatterjee , Siarry P. Nonlinear inertia weight variation for dynamic adaptation in particle swarm optimizatior[ J ]. Computers& Operations Research ,2006 ,335( 3 ) :859 ~ 87113 王启付,王战江,王书亭.一种动态改变惯性权重的粒子群中国煤化工.2005 ,16 11 ):945 -94814 Suganthan P N. Particle swarm optimizer with neighborhood operl:TYHCN M H G and Eleronies Engines,1999 (7):1 958 ~1 96215 Eberhart R C ,Shi Y. Comparison between genetic algorithms and particle swarm optimization[ J ] Lecture Notes in Com-puter Science ,1998 ,( 1 447 ):611 ~61616 RobinsonJ , Sinton S , Rahmat-Sami Y. Particle swarm optimization , genetic algorithm , and their hybrids : Optimization ofa pofiriarilgated horn antenna [ J] IEEE Antennas Propag Soc APS Int Symp ,2002 ,( 1 ):314 ~317第4期崔长彩等:粒子群优化算法34717 Lovbjerg M , Rasmussen T K , Krink T. Hybrid particle swarm optimizer with breeding and subpopulations[ J ] Institute ofElectrical and Elctronics Engineers ,2001 ,( 7 ):115~118 .18 Higashi N , Iba H. Particle swarm optimization with Gaussian mutation[ J ] Institute of Electrical and Electronics Engi-neers ,2003 ,( 4 ):72 ~7919 吕振肃候志荣.自适应变异的粒子群优化算法J]电子学报,2004 ,32(3 ) 416 ~42020李宁孙德宝岑翼刚等，带变异算子的粒子群优化算法J]计算机工程与应用2004 AO( 17)12~14 3521 付国江,王少梅,李 宁一种新的PS0变异策略[ J]武汉理工大学学报(信息与管理工程版),2005 ,27(2):192 ~ 19622 Angeline P J. Using selection to improve particle swarm optimization[ J ] Institute of Electrical and Electronics Engineers ,1998 ,(5)84 ~ 8923 吴晓军,薛惠锋,李 憋,等.GA-PSO混合规划算法J]西北大学学报(自然科学版) ,2005 ,35( 1 )39 ~4324高鹰,谢胜利.基于模拟退火的粒子群优化算法[ J]计算机工程与应用,2004 ,40( 1 ):47 ~5025 高尚,杨静宇,吴小俊,等.基于模拟退火算法思想的粒子群优化算法[ J]计算机应用与软件,2005 ,22( 1 ):103~104 8026 窦全胜,周春光,马 铭.粒子群优化的两种改进策略[ J]计算机研究与发展2005 A42( 5 ):897 ~90427 高鹰,谢胜利.免疫粒子群优化算法[ J]计算机工程与应用2004 ,40(6):4~6 ,728 高鹰,谢胜利.混沌粒子群优化算法[ J]计算机科学2004 31(8):13~1529杨俊杰 ,周建中,喻菁,等.基于混沌搜索的粒子群优化算法[ J].计算机工程与应用,2005 ,41( 16):69~7130 Jiang Chuanwen , Etorre B. A hybrid method of chaotic particle swarm optimization and linear interior for reactive power op-timizatior[ J ] Mathematics and Computers in Simulation ,2005 68( 1 ):57 ~6531 Jiang Chuanwen , Etorre B. A self-adaptive chaotic particle swarm algorithm for short term hydroelectric system scheduling inderegulated environmen[ J ] Energy Conversion and Management ,2005 ,46( 17 ):2 689 ~2 69632 Clerc M , Kennedy J. The particle swarm : Explosion stability and convergence in a multi-dimensional complex space[ J ]IEEE Trans Evolution Comput ,2002 ,6( 1 ):58 ~7333 Trelea I C. The particle swarm optimization algorithm : convergence analysis and parameter selectior[ J ] Information Pro-cessing Letters ,2003 ,85(6 ):317 ~32534 Yoshida H , Fukuyama Y , Takayama S ,et al. A particle swarm optimization for reactive power and voltage control in elec-tric power systems considering voltage security assessment[ J ] Institute of Eletrical and Electronics Engineers , 1999 ,( 10 ):497 ~ 50235 NakaS , Genji T , Yura T ,et al. Practical distribution state estimation using hybrid particle swarm optimization[ J ] Insti-tute of Electrical and Electronics Engineers , 2001 ( 2 ) 815 ~ 82036 Van-Den B F , Engelbrecht A P. Training product unit networks using cooperative particle swarm optimizers[ J] Institute ofElectrical and Electronics Engineers ,2001 ,( 7 ) :126~ 13137 Eberhart R C ,Shi Y. Guest editorial special Issue on particle swarm optimization[ J ]. IEEE Transactions on EvolutionaryComputation , 2004 ,8(3 ):201 ~ 203Particle Swarm OptimizationCui ChangcaiLi BingZhang Rencheng( College of Mechanical Engineering and Automation , Huaqiao University ,362021 , Quanzhou , China )Abstract The particle swarm optimization( PSO ) was introduced about its fundamentals , characteristics , implementationsteps , and its improved versions , which were based on the parameter updating( mainly inertia weight ) , or iluminated by the evo-lutionary principles of genetic algorithm( GA X e.g PSOs with crossover，mutation or selection operator ) , or combined with oth-er algorithm( e. g. simulating annealing PSO , immune PSO , chaotic中国煤化工”) were summarized too.Keywords particle swarm , optimization algorithm , genetic algorithYTHCNM HG