基于CGA和PSO的雙種群混合算法

王永貴，林 琳，劉憲國

(遼寧工程技術大學軟件學院，遼寧 葫蘆島 125105)

1 概述

正態云模型具有隨機性和穩定傾向性的特點，云遺傳算法(Cloud Genetic Algorithm,CGA)正是利用了云模型的這2個特點進化，其中隨機性保證了種群的多樣性，避免陷入局部極值，保證全局范圍的搜索；穩定傾向性可以保護較優個體，從而可以很好地定位全局極值。云模型是用自然語言值表示的定性概念與其定量數據表示之間的不確定性轉換模型，為定性與定量相結合的信息處理提供了有效的手段[1]。

粒子群優化(Particle Swarm Optimization,PSO)[2]算法是由Kennedy和Eberhart于1995年提出的一種重要的群體智能算法，其源于對鳥類捕食行為的模擬，現已成為進化算法的一個重要分支。該算法通過初始化一群隨機粒子，每個粒子代表一個潛在的解，通過迭代的方式，使每個粒子向自身最好位置和群體最好位置靠近。該算法思想直觀、實現簡單且執行效率高[3]，但它自身也存在缺陷，其局部搜索能力較差，搜索精度不高，后期容易陷入局部最優，失去粒子的多樣性，難以保證搜索到全局最優解。

文獻[4]在基本PSO算法中引入了差分算子來更新種群中每個粒子的速度，通過種群中隨機產生的2個粒子的位置矢量差替代速度更新公式中自我認知部分。該方法有效改善了粒子的空間搜索能力，增加了種群的多樣性，從而避免陷入局部最優。文獻[5]提出了基于遺傳算法(Genetic Algorithm,GA)和PSO的混合算法(Genetic Algorithm-Particle Swarm Optimization,GA-PSO)，在該算法中，種群一部分個體使用遺傳算法進行交叉變異操作，產生新個體，這些新個體再通過PSO算法調整剩余的個體。

本文針對粒子群優化算法的缺陷設計一種自調整慣性權值策略，并將CGA與優化后的PSO算法結合，提出一種雙種群混合算法(CGA-PSO)。對一個群體采用云遺傳算法進化，另一個群體采用粒子群優化算法進化，給出一種新型信息交流機制，通過子代間及子代與父代間信息交流，優勝劣汰，且共享最優個體，使2個種群相互引導，實現共同進化，同時適時對粒子群個體進行云變異操作，避免陷入局部最優，以保證信息交流機制的有效性。

2 云理論及基本云遺傳算法

2.1 云模型

設U是一個用精確數值表示的論域，A為U上對應著的定性概念，對于U中的任意一個元素x，都存在一個有穩定傾向的隨機數 μA(x)，記做y(y∈[0,1])，y即為x對概念A的確定度，x在U上的分布稱為云，記為A(x,μ)。每一個x稱為一個云滴[6]。

云的數字特征——期望Ex、熵En和超熵He，用于反映云要表達的定性概念A的整體特性。(1)期望Ex：論域空間U中最能夠代表定性概念A的點，即這個概念量化的最典型樣本點。(2)熵En：熵是定性概念隨機性的度量，既反映了代表定性概念A的云滴出現的隨機程度，又反映了在論域空間U中可以被語言值A接受的云滴值范圍。(3)超熵He：超熵是熵的不確定性的度量，即熵的熵[7]。

2.2 云發生器

生成云滴的算法或硬件稱為云發生器[8]。下面主要介紹本文算法所用到的2個發生器，分別是基本云發生器和Y條件云發生器[9]。

(1)基本云發生器。輸入云的3個數字特征：期望Ex、熵En和超熵He，以及要生成的云滴個數N，生成N個云滴drop(xi,μi)，稱此發生器為基本云發生器，其結構見圖1。

圖1 基本云發生器

(2)Y條件云發生器。給定云的3個數字特征：期望Ex、熵En和超熵He，以及固定的確定度μ0和要生成的云滴個數N，生成N個云滴drop(xi,μ0)，稱此發生器為Y條件發生器，其結構見圖2。

圖2 Y條件云發生器

2.3 基本的云遺傳算法

云遺傳算法結合遺傳算法思想，沿用遺傳算法的交叉、變異操作概念，由Y條件云發生器實現交叉操作，基本云發生器實現變異操作[1]。具體步驟如下：

Step1初始化種群。

Step2計算種群適應度。

Step3選擇操作。

Step4交叉操作：(1)按均勻分布隨機生成μ；(2)由父母雙方適應度大小加權確定Ex；(3)En=變量搜索范圍/c1；(4)He=En/c2；(5)由Y條件發生器產生一對兒女。

Step5變異操作：(1)Ex取原個體；(2)En=變量搜索范圍/c3；(3)He=En/c4；(4)若μ小于變異概率，由基本云發生器得到變異個體。

Step6轉到Step2直至條件滿足。

3 粒子群優化算法

PSO算法在求解優化問題時，粒子被抽象成解空間中的點，具有位置和速度屬性，粒子在解空間中飛行，根據自身飛行經驗和群體飛行經驗動態更新自己的速度和位置[10]，其更新速度和位置公式如式(1)和式(2)所示。

其中，zid為第i個粒子的d維位置矢量；vid為粒子的飛行速度；pid為粒子迄今為止搜索的最優位置；pgd為整個粒子群迄今為止搜索的最優位置；ω為慣性權重，表示先前粒子的速度對當前速度的影響程度；r1和r2為[0,1]之間的隨機數；c1和c2為學習因子也稱加速因子。

粒子群算法雖然編碼簡單，容易實現，但它在優化過程初期收斂速度較快，后期所有粒子都向最優粒子學習，失去種群多樣性，易陷入局部最優。

4 CGA-PSO算法

CGA和PSO算法都是通過大量的個體聚合行為形成群體來尋找最優解，通過更新迭代的方式來完成進化過程。CGA算法利用了云模型的隨機性和穩定傾向性，保證了自身較好的搜索性能。PSO中的粒子有記憶功能，通過記憶自身的最優位置和整個群里的最優位置更新自己的速度和位置，但是由于前期收斂速度較快，它的自我學習和向群體學習的能力，后期很容易陷入局部最優。

為提高PSO算法解的質量，降低早熟收斂的比率，本文設計了一種自調整慣性權值策略。針對于CGA算法與PSO優化算法的優點，將2種算法相結合，引入一種新的信息交流機制，2個子種群分別采用不同的進化方法進行尋優，在每次進化前都要進行信息交流，2個子群共享最優個體，淘汰最劣的個體，整個過程兩子群相互引導，協同進化，并提出了云變異機制，引入其中，以防止早熟收斂，增強算法的搜索能力。將此算法命名CGA-PSO。

4.1 自調整慣性權值策略

在PSO算法中，慣性權值ω是一個非常重要的參數。較大的慣性權值有利于全局搜索，較小的慣性權值有利于局部搜索，合理地調整慣性權值能夠有效地權衡算法的全局搜索能力與局部搜索能力。因此，本文提出一種自調整慣性權值策略，它能改變ω為定值的單一模式，較好地權衡全局與局部搜索能力。自調整慣性權值策略的計算式如式(3)和式(4)所示：

其中，r為n代內最優適應度值的變化率；fitness(t)為第t代最優適應度值；fitness(t -n)為第t-n代最優適應度值；θ為均勻分布于[0,1]之間的隨機數。當變化率較大時，說明算法處于對新空間開發階段，增大慣性權值，有利于增強其全局搜索能力。當變化率較小時，算法處于局部搜索階段，減小慣性權值，有利于獲得精確的解。當變化率適中時，算法處于全局搜索與局部搜索之間，選取適當的慣性權值，平衡算法的全局與局部搜索能力。這種自調整慣性權值策略根據最優適應值的變化率靈活的調解ω的值，進而提高算法的性能。

4.2 信息交流機制

以某一次進化中，CGA子群進化得到的最優個體更接近目標值為例，說明在CGA-PSO算法中，2個子群信息交流的過程。為了方便說明，給出了CGA-PSO中個體運動的趨勢，如圖3所示。其中，Pbest’為用PSO算法進化得到的子代最優個體；Cbest’為用CGA算法進化得到的子代的最優個體；Solution為目標函數的最優解；Gbest’為Pbest’與Cbest’兩者中適應度值最接近最優解的個體；Gbest為2個子群中父代適應度值最優的個體。

圖3 CGA-PSO算法中某一代個體運動的趨勢

在某一次進化中，Cbest’的適應度值更接近最優解，如圖3(a)所示。經過Pbest’和Cbest’競爭后得到Gbest’，當Gbest’適應度值小于Gbest時(設為條件)，PSO子群將不再僅根據自身經驗進行進化，它還要吸收Cbest’個體的信息。隨著Cbest’的引入，PSO子群就會朝著更接近最優解的方向進化，如圖3(b)所示。當條件不成立時，則用兩子群父代的最優個體Gbest分別替換掉PSO子群與CGA子群的最劣個體，既保證了整個種群的優良性，同時也加快了進化的速度，如圖3(c)所示。PSO子群進化得到的最優個體更接近目標值，原理相同。

4.3 云變異機制

為防止算法過早收斂，在種群進化到一定程度時對粒子群中的部分個體執行云變異操作，以提高整個種群的多樣性。根據云理論中云模型的隨機性和穩定性，利用PSO子群的全局最優位置和最劣位置實現對粒子位置的變異過程。

當整個群體的最優適應度在連續多代無明顯變化時，則將PSO子群的個體按適應度值的大小進行排序，對適應度值較差的50%～70%的個體執行云變異操作，即按式(5)在粒子現最優位置的基礎上重新定義粒子的最優位置。

其中，Ex，En，He分別為云模型的期望、熵和超熵；zbest，zworst分別是PSO子群當前的最優位置和最劣位置；RANDN(E n,H e)為產生期望為En、均方差為He的正態隨機數；RANDN(E x,E n ')為產生期望為Ex、均方差為En'的正態隨機數。

Ex體現了云層的重心位置，它是最典型的樣本。當前最優個體周圍往往存在更優個體，更有機會找到最優個體，因此選當前最優位置zbest為期望Ex；En體現了云水平覆蓋的范圍，En越大，水平覆蓋范圍越大，En越小，水平覆蓋范圍越小。進化后期，應減小En以提高搜索精度。結合算法的速度和精度，本文取，同時也是對En的動態調節。He體現了云層的厚度，過大會喪失隨機性，過小會喪失穩定性。本文取

4.4 算法流程

本文提出的雙種群混合算法CGA-PSO具體步驟如下：

Step1隨機產生2N大小的種群

Step2設置種群參數(最大迭代次數Genmax，另初始代數為Gen=0，初始慣性權值ω)且計算種群的適應度值(為方便討論，設此處是解最小化的目標函數)。

Step3隨機將種群分為2組，每組N個個體，分別為CGA子群，PSO子群。

Step4(1)選擇CGA子群中適應度值最小的個體Cbest；(2)選擇精英群復制；(3)隨機產生外來個體取代最差個體。

Step5對Step4得到的精英群，用Y條件云發生器、基本云發生器進行交叉、變異操作得到種群CGA’子群。

Step6選擇CGA’子群中適應度值最小的個體Cbest’。

Step7選擇PSO子群中適應度值最小的個體Pbest，當Gen≥n時，用式(3)計算近幾代的最優適應度變化率r，按式(4)自調整慣性權值ω，對PSO子群中每個粒子按式(1)和式(2)更新粒子的速度和位置，得到種群PSO’子群。

Step8選擇PSO’子群中適應度值最小的個體Pbest’。

Step9Pbest’與Cbest’競爭，選擇出適應度值最小的個體設為Gbest’。如果Gbest’的適應度值均小于Pbest與Cbest的適應度值，則將CGA’子群與PSO’子群中適應度值最小的個體替換為Gbest’，否則用Pbest與Cbest兩者中適應度值最小的個體，分別替換CGA’子群與PSO’子群中適應度值最大的個體。

Step10判斷整個種群適應度最小值是否在規定的次數內一直未發生改變，如果是，則按式(5)執行云變異操作。否則，不執行。

Step11Gen=Gen+1，若達到最大迭代次數Genmax，則輸出當前適應度值最小個體，算法終止。否則，令CGA子群=CGA’子群、PSO子群=PSO’子群，跳轉到Step4。

該算法與基本的CGA算法和PSO算法相比，具有以下特征：(1)父代總包含種群最優個體；(2)CGA子群對于父代的選擇時，引入一個隨機個體；(3)PSO子群加入自調整慣性權值策略；(4)父代產生子代后，用最優個體替代最劣個體；(5)整個種群出現停滯現象時，進行云變異操作。

對上述5個特征的分析如下：

特征(1)：CGA子群后代的產生主要依賴于交叉操作和種群最優個體，PSO子群根據自身最優位置全局最優位置(即最優個體的最優位置)動態調節自身速度和位置，因此，父代總包含種群最優個體，增強了種群的開采能力。

特征(2)：隨機個體的引入相當于對新搜索空間的引入，種群對新的空間搜索，可避免近親繁殖導致早熟。

特征(3)：根據最優適應度值的變化率來自動調整慣性權值，增強算法的全局和局部搜索能力的靈活性。

特征(4)：最劣個體被替換掉，使整個種群能更快速地接近全局最優解，加快了收斂速度。

特征(5)：利用云模型的隨機性和穩定性對粒子的位置進行變異操作，增強種群多樣性，有利于跳出局部極值，避免早熟收斂。

4.5 算法時空復雜度分析

4.5.1 空間復雜度

算法第一步要初始化2N個個體，個體維數為D，即2ND維向量，因此，總的空間復雜度為O(2ND)。

4.5.2 時間復雜度

在Step1中，種群數量為2N，解空間為D維，則對2N個個體初始化，時間復雜度為O(2ND)。

在Step2中，設用來計算個體適應度值的適應度值函數的時間復雜度為O(D)，則計算種群規模為2N的群體適應度值的時間復雜度為O(2ND)。

Step3對2N個個體進行分組，時間復雜度為O(2N)。

Step4對已計算出的CGA子群(種群數量為N)適應度值進行統計，選擇適應度值最小個體，其時間復雜度為O(N)。對于精英體的選擇采用輪盤賭的方式，為了提高效率，選擇輪盤時采用折半查找的方法，時間復雜度為O(logN)。用隨機個體替換適應度值最大個體，選擇適應度值最大個體與選擇適應度值最小個體原理相同，時間復雜度為O(N)。因此，整個Step4的時間復雜度為O(2N+logN)。

在Step5中，對于維數為D的N個個體進行交叉操作的時間復雜度為O(ND)，對N個個體進行變異操作的時間復雜度為O(N)。因此，整個步驟的時間復雜度為O(ND+N)。

Step6與Step4中的(1)原理相似，時間復雜度為O(N)。

Step7對N個粒子的D維速度矢量和位置矢量根據公式進行更新，則時間復雜度為O(ND)。

Step8與Step4中的(1)原理相似，時間復雜度為O(N)。

Step9為本文提出的信息交流機制，與種群數量N、維數D大小無關，時間復雜度為O(1)。

Step10對50%N～70%N的個體進行云變異操作，則時間復雜度為O(CND)，其中C為常數，一般取0.5～0.7。

在Step11中，當達到最大迭代次數T時，輸出適應度值最小的個體，此操作只執行一次，對時間影響很小，可忽略。若沒達到T值，則將子代作為下一次進化的父代，時間復雜度為O(2ND)。

通過對CGA-PSO算法每一步的時間復雜度分析，可得到Step4～Step11的時間復雜度之和為O((5+C)ND+5N+logN+1)，時間復雜度數量級為O(ND)，則經過T次迭代的時間復雜度為O(TND)。因此，整個算法的時間復雜度為O(TND+4ND+2N)，時間復雜度數量級為O(TND)。因此，CGA-PSO算法的時間復雜度與迭代次數、種群規模以及解空間維數都有關系。

5 仿真實驗

為測試本文提出的CGA-PSO算法，選擇如下5個經典函數進行測試。

(1)Sphere函數

(2)Rosenbrock函數

(3)Rastrigin函數

(4)Griewank函數

(5)Schaffer函數

Sphere函數是較為簡單的單峰值函數，用以測試算法的尋優精度。Rosenbrock函數的每個等高線大致呈拋物線形，其中全局最小值也位于拋物線形的山谷中，很容易找到這個山谷，但山谷內值的變化不大，要找到全局極小值相當困難，是難度較大的復雜優化問題。Rastrigin、Griewank與Schaffer是多峰值函數，局部極小點較多，也是難度較大的復雜優化問題。

CGA算法的參數設置參照文獻[11]，其中，c1=c3=3p(p為種群大小)，c2=c4=10。

PSO算法的參數設置如下：初始ω=0.9，vmax和vmin分別是上限和下限的一半，c1=c2=2.0，n=5。

實驗1搜索過程(個體的分布及搜索范圍)

為實驗中觀察方便，本文利用Rosenbrock函數進行測試。實驗中，初始化種群個數為100，在[–10,10]上隨機產生100個個體，每個分組中50個。初始種群中個體分布如圖4(a)所示。測試過程中分別選取第8代、第14代、第18代中的個體，觀察它們的分布情況，如圖4(b)～圖4(d)所示。

通過觀察進化代中種群個體的分布可以發現，算法在第8代時大多數個體已經開始接近最優解的鄰域，第14代時除了少數個體外，其余個體基本都回歸到最優解附近，表明在第14代時，個體已經逼近最優值，在進化到第18代后整個種群收斂到測試函數的全局最優值。通過分析實驗結果可知，該算法能夠快速定位全局極值所在的鄰域，有效縮小對最優解的搜索空間，能夠避免CGA和PSO算法易陷入局部最優解的情況，從而保證向最優解方向進化。

圖4 CGA-PSO求解Rastrigin函數極值進化時的各代個體分布

實驗2全局搜索能力的對比分析

為說明CGA-PSO的全局搜索能力，本文將CGA-PSO算法分別與CGA算法和PSO算法基于上文所提到的5種函數進行最優值求解，前者基于函數f1,f2,f5，后者基于函數f1,f3,f4。初始化種群大小為100，每個分組的種群大小為50，進化代數為50，進行50次實驗。

在CGA算法方面，選取了傳統的云遺傳算法(CGA)[1]和基于云控制的自適應遺傳算法(AGAU)[12]進行比較，實驗結果對比如表1所示。其中，AGAU實驗結果來自文獻[12]。

在PSO算法方面，選取了基本的PSO算法[2]、基于混沌思想的粒子群優化算法(XPSO)[13]、廣泛式學習粒子群最佳化演算法(CLPSO)[14]作為比較對象，3種算法的ω,c1,c2的參數值均按照文中最好的方式設置，得到的結果如表2所示。

表1 CGA-PSO與CGA,AGAU算法的比較

表2 CGA-PSO與PSO,XPSO,CLPSO算法的比較

由表1和表2可見，CGA-PSO在所有函數中相對于其他算法，除了Schaffer函數，每次均能找到函數的精確最優解，所以其標準方差為0。而對于Schaffer函數，其平均值也達到了更好的精度，且標準方差也要小很多。在表1中，CGA-PSO最優值相對于CGA、AGAU具有明顯優勢。以上數據表明，CGA-PSO具有良好的精確性和穩定魯棒性。

實驗3收斂性的對比分析

基于實驗2的結果，本次實驗分別從表1和表2中選取各性能僅次于CGA-PSO算法的AGAU和CLPSO算法對Rastrigin和Sphere函數進行最小值測試，實驗參數設置同實驗2。各函數曲線值是在100次實驗中3種算法在每代所搜索的最小值的平均值，實驗結果如圖5和圖6所示。可見，無論是單峰值函數還是多峰值函數，CGA-PSO算法總能很快地收斂到最優值。圖5中AGAU在第18代左右就陷入了局部最優值。CLPSO和CGA-PSO算法能夠準確地搜索到最優值，但CGA-PSO算法的收斂速度明顯要快于CLPSO算法。CLPSO在第13代逼近最優值，在16代才收斂到全局最小值。CGA-PSO算法在第9代就逼近最優值，在第11代收斂到全局最小值0，不過由于顯示粒度的原因，不能夠完全在圖中表示出來。圖6中3種算法都能準確地搜索到全局最優值，但CGA-PSO算法的收斂速度較快，它能更快速地向全局極值收斂，明顯優于其他2種算法。

圖5 3種算法在Sphere函數下的全局最優值變化曲線

圖6 3種算法在Rastrigin函數下的全局最優值變化曲線

6 結束語

CGA算法利用云模型的隨機性和穩定傾向性的特點完成了進化操作，PSO算法能夠在解空間內追隨最優粒子進行搜索，能夠記憶個體最優值和全局最優值信息，但PSO算法容易陷入局部最優。為此，本文設計了自調整慣性權值策略，優化了PSO算法，利用2種算法的優勢，通過引入一種新型信息交流機制及云變異機制，提出一種雙種群混合算法(CGA-PSO)。由實驗結果可以看出，CGA-PSO不僅進化代數減小，進化速度增快，而且能夠很好地控制搜索范圍，快速地收斂到最優解，較好地避免容易陷入局部最優解和早熟收斂等問題，該算法具有易實現、精度高、求解速度快、魯棒性強、性能好等特點。拓寬CGA-PSO在優化問題中的應用范圍是下一步的研究方向。

[1]戴朝華,朱云芳,陳維榮.云遺傳算法及其應用[J].電子學報,2007,35(7):1419-1424.

[2]Kennedy J,Eberhart R.Particle Swarm Optimization[C]//Proc.of IEEE International Conferenceon Neural Networks.Piscataway,USA:IEEE Press,1995:1942-1948.

[3]周雅蘭,王甲海,印 鑒.一種基于分布估計的離散粒子群優化算法[J].電子學報,2008,26(6):1242-1248.

[4]Das S,Abraham A,Konar A.Particle Swarm Optimization and Differential Evolution Algorithms[J].Technical Analysis,Applications and Hybridization Perspectives,Studies in Computational Intelligence,2008,116:1-38.

[5]Kao Y,Zahara E.A Hybrid Genetic Algorithm and Particle Swarm Optimization for Multimodal Functions[J].Applied Soft Computing,2008,8(2):849-857.

[6]王守信,張 莉,李鶴松.一種基于云模型的主觀信任評價方法[J].軟件學報,2010,21(6):1343-1344.

[7]李海林,郭崇慧,邱望仁.正態云模型相似度計算方法[J].電子學報,2011,39(11):2561-2567.

[8]Hu Changhua,Si Xiaosheng,Yang jianbo.System Reliability Prediction Model Based on Evidential Reasoning Algorithm with Nonlinear Optimization[J]. Expert Systems with Applications,2010,37(3):2550-2562.

[9]李興生.基于云模型和數據場的分類和聚類挖掘研究[D].北京:中國人民解放軍理工大學,2003.

[10]倪慶劍,長志政,王蓁蓁.一種基于可變多簇結構的動態概率粒子群優化算法[J].軟件學報,2009,20(2):339-349.

[11]戴朝華,朱云芳,陳維榮.云遺傳算法[J].西南交通大學學報,2006,41(6):729-732.

[12]吳 濤,金義富.基于云控制的自適應遺傳算法[J].計算機工程,2011,37(8):189-191.

[13]范培蕾,張曉今,楊 濤.克服早熟收斂現象的粒子群優化算法[J].計算機應用,2009,29(6):122-124.

[14]Liang J J,Qin A K,Suganthan P N.Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multi modal Functions[J].IEEE Transactions on Evolutionary Computation,2006,10(3):281-295.