基于仿生學(xué)改進(jìn)的粒子群算法

那日蘇，李強(qiáng)，烏力吉

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

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

基于仿生學(xué)改進(jìn)的粒子群算法

那日蘇1，李強(qiáng)2，烏力吉3

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

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

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

粒子群；負(fù)梯度；仿生學(xué)

1 引言

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

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

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

2 基本粒子群算法

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

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

3 帶有負(fù)梯度項(xiàng)的粒子群算法

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

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

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

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

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

4 仿真實(shí)驗(yàn)

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

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

4.1 算法性能測(cè)試

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

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

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

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

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

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

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

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

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

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

4.2 結(jié)果分析

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

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

5 結(jié)束語

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

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

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

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

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

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

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

[9]陳麗麗.改進(jìn)的粒子群算法[J].計(jì)算機(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.

國(guó)家科技支撐項(xiàng)目計(jì)劃（No.2011BAG03B03）。

那日蘇（1976—），女，博士研究生，講師，研究領(lǐng)域?yàn)闄C(jī)械系統(tǒng)動(dòng)力學(xué)優(yōu)化；李強(qiáng)（1963—），男，博士，教授，研究領(lǐng)域?yàn)闄C(jī)械系統(tǒng)動(dòng)力學(xué)；烏力吉（1962—），男，博士，教授，研究領(lǐng)域?yàn)閮?yōu)化方法。E-mail：nrs3000@163.com

2012-06-28

2012-08-13

1002-8331（2014）06-0061-03

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