基于模拟退火算法的可逃逸粒子群算法摘要：通过引入模拟退火算法来保证PSO的全局收敛性，在群体最优信息陷入停滞时引入位置逃逸机制保持前期搜索速度快的特性。仿真结果表明本算法不但具有好的全局收敛性，而且有好的收敛速度。关键词：微粒群优化;模拟退火算法;逃逸位置：TP301．6文献标志码：A：1001-3695(2008)05-1326-02微粒群优化是由Kennedy和Eberhart[1,2]于1995年提出的，是群智能的代表性方法之一。相比于其他演化算法,PSO算法对解决高维复杂问题具有很大的优越性。然而,当遇到某些具有较多局部极小点的搜索空间时,PSO也会显示其不足之处,特别是当微粒在空间中运行到局部最优解附近时，群体的搜索效率可能会突然大大降低。增大微粒数目对算法性能有一定改善，但不能从根本上解决问题。如果为PSO算法提供一种新机制，使其在陷入局部最优时，以更大概率跳出局部最优位置，进入解空间的其他区域进行搜索，PSO算法的全局搜索能力就可大大增强。??针对这个问题,许多学者做了大量工作来改进算法的性能。有的从参数的控制出发[2]，有的从增加群体多样性出发[3~6]，有的从随机优化算法的全局收敛性条件出发[7~9]。本文提出了一种基于模拟退火算法的可逃逸微粒群算法。通过微粒群局部收敛性与模拟退火全局收敛性[10]的结合，有效地克服了微粒群算法的早熟收敛，又通过加入可逃逸机制加快了收敛速度。??1基本粒子群优化算法??PSO算法与其他演化算法相似,也是基于群体的,根据对环境的适应度将群体中的个体移动到好的区域。然而它不像其他演化算法那样对个体使用演化算子,而是将每个个体看做D维搜索空间中的一个没有体积的微粒点,在搜索空间中以一定的速度飞行。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。第i个微粒表示为X??i=x????i1,??x????i2,…,x????id,它经历过的最好位置记为p????ij,也称为P????best。在群体所有微粒经历过的最好位置的索引号用符号g，也称为G????best2模拟退火算法的逃逸微粒群??在理论上已经证明，基本微粒群算法并不能保证收敛于最优解,甚至是局部最优解[9]。所以用所有微粒的当前位置与全体最好位置相同时算法停止作为收敛准则是有缺陷的。模拟退火算法已经被证明依概率1收敛于全局最优解集，因此可以使用模拟退火算法作为PSO算法的收敛判据。当基本微粒群算法收敛到某一解p??g时，用p??g作为模拟退火算法的初始点进行搜索，根据Metropolis准则接受新解y。如果存在这样的一个解y,使得f(y)在现实生物界中，当物种生存密度过大时，群体有自动分家并找到新生存空间的特性。本文分析了PSO算法种群多样性与微粒位置的关系，指出可以通过控制微粒位置来协调算法的种群多样性。结合PSO算法的特性，对PSO算法模型进行了改进,给出了一种基于微粒位置的逃逸机制，用如下公式描述微粒的这种行为：3．2实验结果与讨论??本文同时用分段式微粒群优化算法和基本微粒群优化算法对以上函数进行优化测试实验。共有两组测试实验：第一组测试实验主要考察两种算法寻优时的达优率；第二组实验主要考察两种算法寻优时的搜索速度。实验中两种算法的群体规模均为20，惯性权重为ω的值均为从1．2线性递减至??0．0012,c??1=c??2=1．9。对于模拟退火算法，温度衰减函数取t????k+1=α×t??k,Markov链长取常数L,邻域结构取每维为[Y????k,i-q,Y????k,j+q]的超矩形。计算实例如表1所示。由表1可知,对于Rosenbrock、LevyF5、Ackley、Rastrigin和Alpine函数,NEPSO优化算法在实验中均能很好地逃脱局部极值点,并都能以1的概率找到全局最好解。??4结束语??从表1中可以看出，通过NEPSO计算取得最优值的概率要高于PSO获得最优值的概率,同时NEPSO获得最优解的迭代次数也比标准PSO少。另外,在处理高维优化问题时,NEPSO优化性能更加良好。以上结果说明了NEPSO与标准PSO相比,在优化效率和优化性能方面有比较大的提升；而NEPSO的算法运行时间与标准PSO相差不大。由此可见，NEPSO是一种稳健的全局收敛算法。??参考文献：??[1]KENNEDYJ,EBERHARTR.Pswarmoptimization[C]//ProcofIEEEIntConfonNeuralNetworks.Perth:[s.n.],1995:1942－1948.[2]EBERHARTR,KENNEDYJ.Anewoptimizerusingp...