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

王永貴，林 琳，劉憲國

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

1 概述

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

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

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

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

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

2.1 云模型

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

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

2.2 云發(fā)生器

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

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

圖1 基本云發(fā)生器

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

圖2 Y條件云發(fā)生器

2.3 基本的云遺傳算法

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

Step1初始化種群。

Step2計(jì)算種群適應(yīng)度。

Step3選擇操作。

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

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

Step6轉(zhuǎn)到Step2直至條件滿足。

3 粒子群優(yōu)化算法

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

其中，zid為第i個(gè)粒子的d維位置矢量；vid為粒子的飛行速度；pid為粒子迄今為止搜索的最優(yōu)位置；pgd為整個(gè)粒子群迄今為止搜索的最優(yōu)位置；ω為慣性權(quán)重，表示先前粒子的速度對當(dāng)前速度的影響程度；r1和r2為[0,1]之間的隨機(jī)數(shù)；c1和c2為學(xué)習(xí)因子也稱加速因子。

粒子群算法雖然編碼簡單，容易實(shí)現(xiàn)，但它在優(yōu)化過程初期收斂速度較快，后期所有粒子都向最優(yōu)粒子學(xué)習(xí)，失去種群多樣性，易陷入局部最優(yōu)。

4 CGA-PSO算法

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

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

4.1 自調(diào)整慣性權(quán)值策略

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

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

4.2 信息交流機(jī)制

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

圖3 CGA-PSO算法中某一代個(gè)體運(yùn)動的趨勢

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

4.3 云變異機(jī)制

為防止算法過早收斂，在種群進(jìn)化到一定程度時(shí)對粒子群中的部分個(gè)體執(zhí)行云變異操作，以提高整個(gè)種群的多樣性。根據(jù)云理論中云模型的隨機(jī)性和穩(wěn)定性，利用PSO子群的全局最優(yōu)位置和最劣位置實(shí)現(xiàn)對粒子位置的變異過程。

當(dāng)整個(gè)群體的最優(yōu)適應(yīng)度在連續(xù)多代無明顯變化時(shí)，則將PSO子群的個(gè)體按適應(yīng)度值的大小進(jìn)行排序，對適應(yīng)度值較差的50%～70%的個(gè)體執(zhí)行云變異操作，即按式(5)在粒子現(xiàn)最優(yōu)位置的基礎(chǔ)上重新定義粒子的最優(yōu)位置。

其中，Ex，En，He分別為云模型的期望、熵和超熵；zbest，zworst分別是PSO子群當(dāng)前的最優(yōu)位置和最劣位置；RANDN(E n,H e)為產(chǎn)生期望為En、均方差為He的正態(tài)隨機(jī)數(shù)；RANDN(E x,E n ')為產(chǎn)生期望為Ex、均方差為En'的正態(tài)隨機(jī)數(shù)。

Ex體現(xiàn)了云層的重心位置，它是最典型的樣本。當(dāng)前最優(yōu)個(gè)體周圍往往存在更優(yōu)個(gè)體，更有機(jī)會找到最優(yōu)個(gè)體，因此選當(dāng)前最優(yōu)位置zbest為期望Ex；En體現(xiàn)了云水平覆蓋的范圍，En越大，水平覆蓋范圍越大，En越小，水平覆蓋范圍越小。進(jìn)化后期，應(yīng)減小En以提高搜索精度。結(jié)合算法的速度和精度，本文取，同時(shí)也是對En的動態(tài)調(diào)節(jié)。He體現(xiàn)了云層的厚度，過大會喪失隨機(jī)性，過小會喪失穩(wěn)定性。本文取

4.4 算法流程

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

Step1隨機(jī)產(chǎn)生2N大小的種群

Step2設(shè)置種群參數(shù)(最大迭代次數(shù)Genmax，另初始代數(shù)為Gen=0，初始慣性權(quán)值ω)且計(jì)算種群的適應(yīng)度值(為方便討論，設(shè)此處是解最小化的目標(biāo)函數(shù))。

Step3隨機(jī)將種群分為2組，每組N個(gè)個(gè)體，分別為CGA子群，PSO子群。

Step4(1)選擇CGA子群中適應(yīng)度值最小的個(gè)體Cbest；(2)選擇精英群復(fù)制；(3)隨機(jī)產(chǎn)生外來個(gè)體取代最差個(gè)體。

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

Step6選擇CGA’子群中適應(yīng)度值最小的個(gè)體Cbest’。

Step7選擇PSO子群中適應(yīng)度值最小的個(gè)體Pbest，當(dāng)Gen≥n時(shí)，用式(3)計(jì)算近幾代的最優(yōu)適應(yīng)度變化率r，按式(4)自調(diào)整慣性權(quán)值ω，對PSO子群中每個(gè)粒子按式(1)和式(2)更新粒子的速度和位置，得到種群PSO’子群。

Step8選擇PSO’子群中適應(yīng)度值最小的個(gè)體Pbest’。

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

Step10判斷整個(gè)種群適應(yīng)度最小值是否在規(guī)定的次數(shù)內(nèi)一直未發(fā)生改變，如果是，則按式(5)執(zhí)行云變異操作。否則，不執(zhí)行。

Step11Gen=Gen+1，若達(dá)到最大迭代次數(shù)Genmax，則輸出當(dāng)前適應(yīng)度值最小個(gè)體，算法終止。否則，令CGA子群=CGA’子群、PSO子群=PSO’子群，跳轉(zhuǎn)到Step4。

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

對上述5個(gè)特征的分析如下：

特征(1)：CGA子群后代的產(chǎn)生主要依賴于交叉操作和種群最優(yōu)個(gè)體，PSO子群根據(jù)自身最優(yōu)位置全局最優(yōu)位置(即最優(yōu)個(gè)體的最優(yōu)位置)動態(tài)調(diào)節(jié)自身速度和位置，因此，父代總包含種群最優(yōu)個(gè)體，增強(qiáng)了種群的開采能力。

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

特征(3)：根據(jù)最優(yōu)適應(yīng)度值的變化率來自動調(diào)整慣性權(quán)值，增強(qiáng)算法的全局和局部搜索能力的靈活性。

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

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

4.5 算法時(shí)空復(fù)雜度分析

4.5.1 空間復(fù)雜度

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

4.5.2 時(shí)間復(fù)雜度

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

在Step2中，設(shè)用來計(jì)算個(gè)體適應(yīng)度值的適應(yīng)度值函數(shù)的時(shí)間復(fù)雜度為O(D)，則計(jì)算種群規(guī)模為2N的群體適應(yīng)度值的時(shí)間復(fù)雜度為O(2ND)。

Step3對2N個(gè)個(gè)體進(jìn)行分組，時(shí)間復(fù)雜度為O(2N)。

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

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

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

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

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

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

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

在Step11中，當(dāng)達(dá)到最大迭代次數(shù)T時(shí)，輸出適應(yīng)度值最小的個(gè)體，此操作只執(zhí)行一次，對時(shí)間影響很小，可忽略。若沒達(dá)到T值，則將子代作為下一次進(jìn)化的父代，時(shí)間復(fù)雜度為O(2ND)。

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

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

為測試本文提出的CGA-PSO算法，選擇如下5個(gè)經(jīng)典函數(shù)進(jìn)行測試。

(1)Sphere函數(shù)

(2)Rosenbrock函數(shù)

(3)Rastrigin函數(shù)

(4)Griewank函數(shù)

(5)Schaffer函數(shù)

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

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

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

實(shí)驗(yàn)1搜索過程(個(gè)體的分布及搜索范圍)

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

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

圖4 CGA-PSO求解Rastrigin函數(shù)極值進(jìn)化時(shí)的各代個(gè)體分布

實(shí)驗(yàn)2全局搜索能力的對比分析

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

在CGA算法方面，選取了傳統(tǒng)的云遺傳算法(CGA)[1]和基于云控制的自適應(yīng)遺傳算法(AGAU)[12]進(jìn)行比較，實(shí)驗(yàn)結(jié)果對比如表1所示。其中，AGAU實(shí)驗(yàn)結(jié)果來自文獻(xiàn)[12]。

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

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

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

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

實(shí)驗(yàn)3收斂性的對比分析

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

圖5 3種算法在Sphere函數(shù)下的全局最優(yōu)值變化曲線

圖6 3種算法在Rastrigin函數(shù)下的全局最優(yōu)值變化曲線

6 結(jié)束語

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

[1]戴朝華,朱云芳,陳維榮.云遺傳算法及其應(yīng)用[J].電子學(xué)報(bào),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ì)的離散粒子群優(yōu)化算法[J].電子學(xué)報(bào),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]王守信,張 莉,李鶴松.一種基于云模型的主觀信任評價(jià)方法[J].軟件學(xué)報(bào),2010,21(6):1343-1344.

[7]李海林,郭崇慧,邱望仁.正態(tài)云模型相似度計(jì)算方法[J].電子學(xué)報(bào),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]李興生.基于云模型和數(shù)據(jù)場的分類和聚類挖掘研究[D].北京:中國人民解放軍理工大學(xué),2003.

[10]倪慶劍,長志政,王蓁蓁.一種基于可變多簇結(jié)構(gòu)的動態(tài)概率粒子群優(yōu)化算法[J].軟件學(xué)報(bào),2009,20(2):339-349.

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

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

[13]范培蕾,張曉今,楊 濤.克服早熟收斂現(xiàn)象的粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用,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.