基于仿生學改進的粒子群算法

那日蘇，李強，烏力吉

1.內(nèi)蒙古工業(yè)大學機械學院，呼和浩特 010051 2.北方工業(yè)大學機電工程學院，北京 100144

3.內(nèi)蒙古工業(yè)大學理學院，呼和浩特 010051

基于仿生學改進的粒子群算法

那日蘇1，李強2，烏力吉3

1.內(nèi)蒙古工業(yè)大學機械學院，呼和浩特 010051 2.北方工業(yè)大學機電工程學院，北京 100144

3.內(nèi)蒙古工業(yè)大學理學院，呼和浩特 010051

針對標準粒子群算法收斂速度慢和易陷入局部最優(yōu)的局限性，提出了一種基于仿生學改進的粒子群算法。即通過在標準粒子群公式中加入負梯度項，使算法更加符合鳥群覓食的實際規(guī)律，同時使算法的全局和局部搜索能力得到了平衡。仿真對比結(jié)果表明，改進的粒子群算法減小了陷入局部極值的可能性，能夠提高最優(yōu)解的精度和優(yōu)化效率。

粒子群；負梯度；仿生學

1 引言

粒子群算法是一種源于鳥群覓食行為的群體智能算法，最早由Kennedy和Eberhart在1995年提出[1]。粒子群算法通過鳥之間的集體協(xié)作對優(yōu)化問題進行求解，每只鳥代表解空間的一個候選解，在算法中稱之為“粒子”。粒子群算法從一組隨機解出發(fā)，通過迭代搜尋最優(yōu)解，但是它沒有像遺傳算法那樣應用交叉和變異算子，而是粒子在解空間追隨最優(yōu)的粒子進行搜索。較之其他優(yōu)化算法，粒子群算法簡單易行，通用性強，近年來已經(jīng)被廣泛應用于各個研究領域中。

但經(jīng)典粒子群算法也存在局限性，如在算法初期局部搜索能力較差，在算法后期易陷入局部最優(yōu)等。對此，很多學者提出了相關(guān)的改進措施，如：Shi等提出了在迭代過程中ω值線性減小的LDIW策略[2]；武建新提出了指數(shù)型自適應慣性權(quán)重粒子群算法[3]等。大部分措施致力于改進慣性權(quán)重ω，以協(xié)調(diào)粒子群的全局和局部搜索能力[4-9]。

為此，本文提出一種改進的粒子群算法，通過在公式中引入負梯度項，隨著迭代次數(shù)的增加逐漸增加負梯度項的比重，并結(jié)合慣性權(quán)重ω，能夠使粒子群算法在迭代初期有較好的全局搜索能力，在迭代后期能夠有效提高收斂速度。

2 基本粒子群算法

在標準粒子群算法中，i個粒子組成一個群體，相當于由i只鳥組成的一個鳥群。每個粒子相當于d維搜索空間中待優(yōu)化問題的一個可行解。將第i個粒子的位置和飛行速度分別表示為Xi=(xi1，xi2，…，xid)，Vi= (vi1，vi2，…，vid)，第i個粒子迄今為止搜索到的最好位置表示為Pi=(pi1，pi2，…，pid)，記為pbest；群體迄今為止搜索到的最好位置表示為Pg=(pg1，pg2，…，pgd)，記為gbest。

對于第k次迭代，第i個粒子的第d維根據(jù)以下方程更新位置和速度：

3 帶有負梯度項的粒子群算法

從仿生學的角度來說，標準粒子群算法在給定每只鳥的初始位置和初始速度后，每個個體的運動方向和大小的更新由原來運動的慣性速度、個體的“經(jīng)驗”和群體的“經(jīng)驗”三部分構(gòu)成。事實上，在鳥群覓食過程中，每個個體都能觀測到附近的食物，把這一因素融入算法中更符合客觀規(guī)律。

如實值函數(shù)f(x)在點a處可微，函數(shù)f(x)在點a的充分小鄰域內(nèi)，沿函數(shù)的負梯度方向：

函數(shù)值下降最快。因此，可以把負梯度方向看成是每個鳥在當前位置上所看到的食物。

據(jù)此，在速度迭代公式（1）中加入負梯度項，得到改進的粒子群算法更新位置和速度的公式如下：

本文構(gòu)造的粒子群算法在算法初期慣性權(quán)重所占比例大于負梯度項，到了算法后期，趨勢相反。即隨著迭代次數(shù)的增加，慣性權(quán)重遞減，而負梯度項的遞增。這是因為在算法初期，鳥群離食物較遠，如負梯度項所占比重過大會導致算法陷入局部最優(yōu)；反之，在算法后期，鳥群慢慢接近食物，增大負梯度項的比重會加快收斂速度。

4 仿真實驗

為了進一步驗證基于仿生學改進的負梯度粒子群算法（FPSO）的優(yōu)化性能，本文采用4個標準測試函數(shù)分別對標準粒子群算法（PSO）和負梯度的粒子群算法（FPSO）進行了仿真實驗，為了保證結(jié)果的客觀性，所有結(jié)果都經(jīng)過50次獨立實驗。所選標準測試函數(shù)如下：

f1(x)為單峰函數(shù)，在xi=0時達到最小值，最小值f1(xi)=0；f2(x)為多峰函數(shù)，在xi=420.968 7時達到全局最小值，最小值f2(xi)=0；f3(x)是多峰函數(shù)，在xi=0時達到全局最小值，最小值f3(xi)=0；f4(x)為多峰函數(shù)，在xi=0時達到全局最小值，最小值f4(xi)=0。

4.1 算法性能測試

為了確定慣性權(quán)重ω=e-αk中不同的α值對函數(shù)的影響，對每個測試函數(shù)分別采用α=0.01，0.02，…，0.09，0.1，0.2，…，0.9共18個值，計算50次，觀測其優(yōu)化結(jié)果?？v坐標的“成功率”表示在50次計算中，最優(yōu)值小于1E-6的百分比。不同α值對函數(shù)的影響如圖1所示。

圖1 不同α值對函數(shù)的影響

經(jīng)過實驗對比可見，在α=0.6時優(yōu)化效果較好。

對于上述4個測試函數(shù)，均設種群規(guī)模為30，粒子維數(shù)為10維，ω=0.729，c1=c2=2，對負梯度粒子群算法分別設ω=e-0.6k，c3=arctan(k)，最大進化代數(shù)為200，求得最小適應值的均值，若算法求得的結(jié)果與理想最優(yōu)解誤差小于10-6，則視其達到收斂，計算采用MATLAB實現(xiàn)，比較標準粒子群算法（PSO）和負梯度粒子群算法（FPSO）的搜索效率以及最優(yōu)值的分布，結(jié)果見表1。

表1 PSO算法和FPSO算法的比較

圖2～圖5表示了在標準粒子群算法（PSO）和負梯度粒子群算法（FPSO）下，每個函數(shù)的最優(yōu)值隨迭代次數(shù)的進化情況。

圖2 f1(x)最優(yōu)值隨代數(shù)進化情況

圖3 f2(x)最優(yōu)值隨代數(shù)進化情況

圖4 f3(x)最優(yōu)值隨代數(shù)進化情況

圖5 f4(x)最優(yōu)值隨代數(shù)進化情況

4.2 結(jié)果分析

（1）由表1可見，較之標準PSO算法，F(xiàn)PSO算法對于4個測試函數(shù)在成功率、計算時間上都有顯著提高，同時求得的平均適應值更接近理想適應值。

（2）由圖2～圖5可見，對于同一測試函數(shù)，較之標準PSO算法，F(xiàn)PSO算法起始點低，下降速度更快，并且在迭代過程中，更接近理想適應值。

5 結(jié)束語

針對標準粒子群算法優(yōu)化性能較差的不足，基于鳥群覓食的實際情況，提出了帶有負梯度項的改進的粒子群算法，通過引入負梯度項，使算法更加吻合鳥群覓食的實際規(guī)律。為了證明算法的可行性，分別對4個標準測試函數(shù)進行了仿真對比，計算結(jié)果證明了改進的粒子群算法改善了解的質(zhì)量，提高了收斂速度和優(yōu)化成功率。因此，該算法在實際的工程優(yōu)化領域值得推廣和應用。

[1]Kennedy，Eberhart R C.Particle Swarm Optimization[C]// Proc IEEE International Conference on Neural Networks. USA：IEEE Press，1995.

[2]Shi Y H，Eberhart R C.A modified particle swarm optimizer[C]//Proceedings of the IEEE Congress on Evolutionary Computation.Piscataway，USA：IEEE Service Center，1998：69-73.

[3]李強，武建新，孫燕.機電耦聯(lián)系統(tǒng)指數(shù)慣性權(quán)粒子群動力學優(yōu)化方法[J].機械科學與技術(shù)，2009（3）：288-290.

[4]王俊偉，汪定偉.一種帶有梯度加速的粒子群算法[J].控制與決策，2004（11）：1298-1304.

[5]陳貴敏，賈建援，韓琪.粒子群優(yōu)化算法的慣性權(quán)值遞減策略研究[J].西安交通大學學報，2006，40（10）：53-56.

[6]任銳.帶有梯度加速的粒子群算法在邊坡穩(wěn)定分析中的應用[J].中國高新技術(shù)企業(yè)，2009（14）：15-16.

[7]張選平，杜玉平，秦國強，等.一種動態(tài)改變慣性權(quán)的自適應粒子群算法[J].西安交通大學學報，2005，39（10）：1039-1042.

[8]劉偉，周育人.一種改進慣性權(quán)重的PSO算法[J].計算機工程與應用，2009，45（7）：46-48.

[9]陳麗麗.改進的粒子群算法[J].計算機與數(shù)字工程，2009，37（8）：33-34.

NA Risu1,LI Qiang2,WU Liji3

1.College of Mechanics,Inner Mongolia University of Technology,Hohhot 010051,China
2.College of Mechanical and Electrical Engineering,North China University of Technology,Beijing 100144,China
3.College of Science,Inner Mongolia University of Technology,Hohhot 010051,China

The classic Particle Swarm Optimization has some deficiencies,such as falling in the local optimal region,slow convergence velocity,and so on.Aimed at these disadvantages an improved PSO algorithm is proposed.By employing the information about negative gradient to the standard particle swarm algorithm formula,an improved PSO algorithm can make the equilibrium more closed to the real rules of birds swarm’s foraging.At the same time,the global and local search ability of algorithm is balanced.Simulation results show that,an improved PSO algorithm reduces the chances of getting into the local extremum.At the same time,it can improve the solution accuracy of optimal solution and optimizing efficiency.

Particle Swarm Optimization（PSO）;negative gradient;bionics

A

TP301.6

10.3778/j.issn.1002-8331.1206-0446

NA Risu,LI Qiang,WU Liji.Particle Swarm Optimization based on bionics.Computer Engineering and Applications,2014,50（6）：61-63.

國家科技支撐項目計劃（No.2011BAG03B03）。

那日蘇（1976—），女，博士研究生，講師，研究領域為機械系統(tǒng)動力學優(yōu)化；李強（1963—），男，博士，教授，研究領域為機械系統(tǒng)動力學；烏力吉（1962—），男，博士，教授，研究領域為優(yōu)化方法。E-mail：nrs3000@163.com

2012-06-28

2012-08-13

1002-8331（2014）06-0061-03

CNKI網(wǎng)絡優(yōu)先出版：2012-09-25，http://www.cnki.net/kcms/detail/11.2127.TP.20120925.0959.005.html