自適應(yīng)變異粒子群優(yōu)化算法

黃繼紅,蘇守寶,馬 艷,陳振偉

（皖西學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系,安徽六安 237012）

自適應(yīng)變異粒子群優(yōu)化算法

黃繼紅,蘇守寶,馬 艷,陳振偉

（皖西學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系,安徽六安 237012）

提出了一種自適應(yīng)變異粒子群優(yōu)化算法,該算法通過遺傳變異提高種群多樣性的方法使算法增強(qiáng)持續(xù)搜索能力,解決了PSO算法的早熟收斂問題。采用標(biāo)準(zhǔn)測試函數(shù)進(jìn)行仿真實(shí)驗(yàn),結(jié)果表明:提出的算法具有提高局部最優(yōu)值的能力,且優(yōu)化精度更高。

粒子群優(yōu)化;遺傳算法;變異;自適應(yīng)性

粒子群優(yōu)化算法:粒子群優(yōu)化（Particle Swarm Optimization,PSO）算法是一種進(jìn)化計(jì)算技術(shù),由Eberhart博士和 Kennedy博士發(fā)明。算法源于對鳥群捕食的行為研究。

PSO算法著重強(qiáng)調(diào)種群的社會屬性,通過模擬群體的社會行為實(shí)現(xiàn)對空間的搜索,與GA算法相比較,粒子群算法需要調(diào)節(jié)的參數(shù)不多,不需要對變量進(jìn)行二進(jìn)制編碼,而且在迭代過程中不需要進(jìn)行交叉、變異等遺傳操作,而以粒子的速度參數(shù)進(jìn)行路徑搜索。由于粒子群算法中目標(biāo)函數(shù)即為適應(yīng)度函數(shù),故省去了GA中從目標(biāo)函數(shù)到適應(yīng)度函數(shù)的轉(zhuǎn)換。因此,粒子群算法在多數(shù)情況下能較遺傳算法更快地收斂于全局最優(yōu)解[1]。

PSO算法雖然具有收斂速度快、易實(shí)現(xiàn)、易理解并且僅有少量參數(shù)需要調(diào)整的優(yōu)點(diǎn),但也有自身的不足之處。對高維復(fù)雜問題,粒子群算法常出現(xiàn)早熟收斂,陷入局部極小。

針對基本PSO算法的不足,本文對粒子群算法的收斂性進(jìn)行了研究,并根據(jù)遺傳變異能增加種群多樣性的特性給出了改進(jìn)型算法,即自適應(yīng)變異粒子群優(yōu)化（Particle Swarm Optimization with Adaptive Mutation,AMPSO）算法。

1 AMPSO算法

1.1 基本粒子群算法

PSO算法是對鳥群捕食行為的研究,經(jīng)過抽象,鳥被抽象為沒有質(zhì)量和體積的粒子（點(diǎn)）,并延伸到n維空間,每個粒子分別由位置向量 Pi=（P1,P2,… Pn）和速度向量Vi=（V 1,V 2,…,Vn）表示,都有一個由目標(biāo)函數(shù)確定的適應(yīng)值（fitness value）,并且知道自己到目前為止發(fā)現(xiàn)的最好位置（pbest）和現(xiàn)在的位置Pi.,這個可以看做粒子自己的飛行經(jīng)驗(yàn)。另外,每個粒子還知道當(dāng)前整個群體中所有粒子發(fā)現(xiàn)的最好位置（gbest）,其中 gbest是pbest中的最好位置。把這個值可以看作粒子群體經(jīng)驗(yàn)。每個粒子通過自己的經(jīng)驗(yàn)和群體經(jīng)驗(yàn)來決定下一步的運(yùn)動行為[2]。

PSO算法首先對這群粒子初始化,并通過迭代找到最優(yōu)解。在每一次迭代中粒子通過跟蹤兩個“極值”來更新自己。公式（1）、（2）為 PSO算法的標(biāo)準(zhǔn)公式。

其中,T為迭代次數(shù)vi、Pi、pbest、gbest如前定義;Rand（）是介于（0,1）之間的隨機(jī)數(shù);C1、C2為學(xué)習(xí)因子,一般C1=C2=2.;ω為慣性因子;在每一維,粒子都有一個最大限速度Vmax（Vmax＞0）,如果某一維的速度超過設(shè)定的Vmax,則該維速度被限定為Vmax[3]。

1.2 AMPSO算法

針對基本粒子群優(yōu)化算法的不足,一些學(xué)者對粒子群算法,以不同途徑,作了各式各樣的改進(jìn)。本文是通過遺傳變異算子來提高種群多樣性的途徑實(shí)現(xiàn)標(biāo)準(zhǔn)粒子群算法的改進(jìn)。

遺傳中的變異算子,一方面可以提高算法的局部搜索效果;另一方面可以使群體進(jìn)化過程中丟失的等位基因信息得以恢復(fù),以保持群體的個體差異性,防止發(fā)生早熟收斂?？梢越梃b這一思想,來改善粒子群優(yōu)化算法在搜索過程中可能出現(xiàn)的多樣性丟失的情況。即對整個粒子群位置向量引入變異概率因子,以擴(kuò)大對解空間的搜索范圍,使算法能有效地進(jìn)行全局搜索,從而增加了粒子收斂到全局最優(yōu)解的概率。

但是過大的變異率在增加種群多樣性的同時也將會導(dǎo)致群體發(fā)生混亂,使種群不能進(jìn)行精確局部搜索,減緩算法的收斂速度。而過小的變異率,不能快速、有效地逃出局部極小點(diǎn)。所以“變異”的特性必須根據(jù)當(dāng)前環(huán)境的變化而調(diào)整變異率因子的大小,從而增強(qiáng)變異的自適應(yīng)性[2]。本文把這種改進(jìn)的粒子群算法稱為自適應(yīng)變異粒子群優(yōu)化算法（Particle Swarm Optimization with Adaptive Mutation,AMPSO）。

算法如下:

在粒子群算法迭代過程中,判斷粒子群最優(yōu)粒子位置是否在不斷變化或變化很小,可通過設(shè)置一個粒子群最優(yōu)位置連續(xù)不變化次數(shù)的閾值,當(dāng)粒子群最優(yōu)粒子位置連續(xù)不變化或變化極小的迭代次數(shù)大于閾值時,認(rèn)為有集聚傾向,即出現(xiàn)早熟收斂。

如果有集聚傾向,對整個粒子群位置向量按隨機(jī)變異概率因子發(fā)生變異。每一次迭代過程中,粒子更新完速度向量和位置向量后,判斷是否集聚。若是,位置根據(jù)變異因子發(fā)生變異;若否,則正常循環(huán)迭代。

粒子結(jié)點(diǎn)位置向量變異公式如公式（3）:

其中,pm為變異算子,Rand（）?。?,1）之間的隨機(jī)數(shù),C為變異因子[4]。

2 AMPSO算法實(shí)現(xiàn)

自適應(yīng)變異粒子群優(yōu)化算化流程見圖1。

圖1 自適應(yīng)變異粒子群優(yōu)化算法流程

PSO算法中自適應(yīng)變異代碼實(shí)現(xiàn)過程:

其中,m為當(dāng)前已迭代次數(shù),Mmax為粒子群進(jìn)化到Mmax代后發(fā)生變異,Nmax最優(yōu)粒子適應(yīng)度值穩(wěn)定不變的代數(shù)閥值,popSize為粒子群規(guī)模,Pmax為位置向量每一維的最大值,P為粒子位置向量矩陣,N為每個粒子向量維數(shù)。

3 仿真實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證本文提出的自適應(yīng)變異粒子群算法（AMPSO）性能,在MATLAB環(huán)境下做了實(shí)驗(yàn)仿真,并與基礎(chǔ)粒子群算法及遺傳算法（GA）進(jìn)行比較。

在實(shí)驗(yàn)中,三種算法所用參數(shù)相同或相似,具體參數(shù)為:種群個數(shù)為50,迭代次數(shù)為500,運(yùn)行100次,AMPSO算法的變異概率為0.8,最優(yōu)值連續(xù)不變閾值為10。遺傳算法采用實(shí)數(shù)編碼。

并采用一下標(biāo)準(zhǔn)測試函數(shù):

對于Rastrigin函數(shù),當(dāng)誤差小于0.003時,找到最優(yōu)解;Rosnebork函數(shù)在xi=l,（i=l,2,…n）處達(dá)到的全局極小值0;對于Schaffer’s f6函數(shù),突破局部極大值點(diǎn).09903,就算找到最優(yōu)解:而Schaffer’s f7函數(shù)在 =0,（i=,1,2,…n）處達(dá)到全局極小值0。試驗(yàn)的結(jié)果如表l所示:

表1 三種算法仿真結(jié)果比較

由表1實(shí)驗(yàn)結(jié)果分析可知,AMPSO算法無論是在正確收斂的次數(shù),還是在搜索到的最優(yōu)值的平均值方面都要優(yōu)于 PSO算法和 GA算法,例如對于Schaffer’s f6函數(shù)能夠達(dá)到100%的正確收斂,而且精度也很高。AMPSO算法在收斂速度方面也有其優(yōu)勢。

三種算法對四個函數(shù)的優(yōu)化曲線的比較如圖2—圖5所示:

圖2 函數(shù)Rastrigin優(yōu)化比較

圖3 函數(shù)Rosnebork優(yōu)化比較

圖4 函數(shù)Schaffer’s f6優(yōu)化比較

圖5 函數(shù)Schaffer’s f7優(yōu)化比較

對圖2—圖5的分析可以發(fā)現(xiàn):遺傳算法收斂最慢,且能夠達(dá)到的精度也是最低的;而基本PSO算法收斂的速度都是最快的,但是一旦陷入局部最優(yōu)值后,PSO算法就無法再有突破,這正符合基本 PSO算法收斂速度快,但是易早熟的特點(diǎn),AMPSO算法的收斂速度大體與基本PSO算法相當(dāng),但是有很強(qiáng)的突破局部最優(yōu)值的能力,最終能夠達(dá)到的優(yōu)化精度也是最高的。這充分說明了AMPSO算法在函數(shù)優(yōu)化方面的優(yōu)勢。

4 結(jié)論

自適應(yīng)變異粒子群算法實(shí)際上是在標(biāo)準(zhǔn)粒子群優(yōu)化算法的基礎(chǔ)上,根據(jù)環(huán)境的變化,增加變異操作來提高算法跳出局部收斂的能力。仿真實(shí)驗(yàn)結(jié)果表明:該算法的收斂速度快,迭代次數(shù)較少,精確率高,其算法思想更接近于自然進(jìn)化規(guī)律。

[1]A Banks,J Wincent,C Anyakoha.A Review of Particle Swarm Optimization.Part I:Background and Development [J].Nat Comput:An Int J,2008,6（4）:467-484.

[2]肖曉麗,黃繼紅,劉志鵬.基于變異PSO的BP網(wǎng)絡(luò)及入侵檢測中的應(yīng)用[J].計(jì)算機(jī)工程,2008,30（24）:1030 -1033.

[3]蘇守寶,汪繼文,方杰.粒子群優(yōu)化技術(shù)的研究與應(yīng)用進(jìn)展[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17（5）:249-253.

[4]P Asokan,J Jerald,S Arunachalam,et al.Application of A-daptive Genetic Algorithm and Particle Swarm Optimisation in scheduling of jobs and AS/RS in FMS[J].International Journal of Manufacturing Research,2008,3（4）:393 -405.

Particle Swarm Optimization Algorithm with Adaptive Mutation

Huang Ji-hong,Su Shou-bao,Ma Yan,Chen Zhen-wei

（Department of Computer Science and Technology,West Anhui University,L u’an237012,China）

A particle swarm optimization algorithm with adaptive mutation（AMPSO）is presented in this paper.The algorithm of genetic variation through increased population diversity means to make the algorithm of continuing the search capabilities of the PSO algorithm to overcome the phenomenon of premature convergence.Adopting well-know n benchmark test functions Rosenbork function simulation experiments,it show s that the proposed algorithm has a strong breakthrough in the capacity of local optimal value and optimal precision.

particle swam optimization;genetic algorithm;mutation;adaptive

TP183

A

1009-9735（2010）02-0027-04

2009-10-20

安徽省自然科學(xué)基金項(xiàng)目（090412261X）;安徽高校省級自然科學(xué)重點(diǎn)項(xiàng)目（KJ2007A 072,KJ2007A 087）。

黃繼紅（1977-）,男,安徽六安人,碩士,研究方向:計(jì)算機(jī)網(wǎng)絡(luò)與信息安全;蘇守寶（1965-）,男,博士,教授,研究方向:群智能與控制優(yōu)化。