自適應變異粒子群優化算法

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

（皖西學院計算機科學技術系,安徽六安 237012）

自適應變異粒子群優化算法

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

（皖西學院計算機科學技術系,安徽六安 237012）

提出了一種自適應變異粒子群優化算法,該算法通過遺傳變異提高種群多樣性的方法使算法增強持續搜索能力,解決了PSO算法的早熟收斂問題。采用標準測試函數進行仿真實驗,結果表明:提出的算法具有提高局部最優值的能力,且優化精度更高。

粒子群優化;遺傳算法;變異;自適應性

粒子群優化算法:粒子群優化（Particle Swarm Optimization,PSO）算法是一種進化計算技術,由Eberhart博士和 Kennedy博士發明。算法源于對鳥群捕食的行為研究。

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

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

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

1 AMPSO算法

1.1 基本粒子群算法

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

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

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

1.2 AMPSO算法

針對基本粒子群優化算法的不足,一些學者對粒子群算法,以不同途徑,作了各式各樣的改進。本文是通過遺傳變異算子來提高種群多樣性的途徑實現標準粒子群算法的改進。

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

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

算法如下:

在粒子群算法迭代過程中,判斷粒子群最優粒子位置是否在不斷變化或變化很小,可通過設置一個粒子群最優位置連續不變化次數的閾值,當粒子群最優粒子位置連續不變化或變化極小的迭代次數大于閾值時,認為有集聚傾向,即出現早熟收斂。

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

粒子結點位置向量變異公式如公式（3）:

其中,pm為變異算子,Rand（）取（0,1）之間的隨機數,C為變異因子[4]。

2 AMPSO算法實現

自適應變異粒子群優化算化流程見圖1。

圖1 自適應變異粒子群優化算法流程

PSO算法中自適應變異代碼實現過程:

其中,m為當前已迭代次數,Mmax為粒子群進化到Mmax代后發生變異,Nmax最優粒子適應度值穩定不變的代數閥值,popSize為粒子群規模,Pmax為位置向量每一維的最大值,P為粒子位置向量矩陣,N為每個粒子向量維數。

3 仿真實驗與結果分析

為驗證本文提出的自適應變異粒子群算法（AMPSO）性能,在MATLAB環境下做了實驗仿真,并與基礎粒子群算法及遺傳算法（GA）進行比較。

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

并采用一下標準測試函數:

對于Rastrigin函數,當誤差小于0.003時,找到最優解;Rosnebork函數在xi=l,（i=l,2,…n）處達到的全局極小值0;對于Schaffer’s f6函數,突破局部極大值點.09903,就算找到最優解:而Schaffer’s f7函數在 =0,（i=,1,2,…n）處達到全局極小值0。試驗的結果如表l所示:

表1 三種算法仿真結果比較

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

三種算法對四個函數的優化曲線的比較如圖2—圖5所示:

圖2 函數Rastrigin優化比較

圖3 函數Rosnebork優化比較

圖4 函數Schaffer’s f6優化比較

圖5 函數Schaffer’s f7優化比較

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

4 結論

自適應變異粒子群算法實際上是在標準粒子群優化算法的基礎上,根據環境的變化,增加變異操作來提高算法跳出局部收斂的能力。仿真實驗結果表明:該算法的收斂速度快,迭代次數較少,精確率高,其算法思想更接近于自然進化規律。

[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網絡及入侵檢測中的應用[J].計算機工程,2008,30（24）:1030 -1033.

[3]蘇守寶,汪繼文,方杰.粒子群優化技術的研究與應用進展[J].計算機技術與發展,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

安徽省自然科學基金項目（090412261X）;安徽高校省級自然科學重點項目（KJ2007A 072,KJ2007A 087）。

黃繼紅（1977-）,男,安徽六安人,碩士,研究方向:計算機網絡與信息安全;蘇守寶（1965-）,男,博士,教授,研究方向:群智能與控制優化。