李 婭，張德豐，王 東

(佛山科學(xué)技術(shù)學(xué)院機(jī)電與信息工程學(xué)院，中國(guó) 佛山 528000)

粒子群算法是一種基于群體迭代，群體在解空間中追隨最優(yōu)粒子進(jìn)行搜索的算法，該算法簡(jiǎn)單方便，收斂速度快，并且對(duì)目標(biāo)函數(shù)要求較少，因此發(fā)展十分迅速，在函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，TSP問題求解，模糊系統(tǒng)控制等領(lǐng)域得到廣泛應(yīng)用．

作為一種有導(dǎo)向的隨機(jī)性的啟發(fā)式算法，在求解復(fù)雜優(yōu)化問題時(shí)，粒子群算法存在易陷入局部極值點(diǎn)，進(jìn)化后期收斂速度慢，魯棒性較差等缺陷．目前解決這類問題的主要方法是增加粒子群的規(guī)模，或者改進(jìn)粒子群算法的一些計(jì)算參數(shù)，或者將粒子群算法與其他算法結(jié)合產(chǎn)生各種混合算法．

文獻(xiàn)[1]提出的混沌粒子群優(yōu)化算法(CPSO)立足于利用混沌變量的遍歷性，以粒子群當(dāng)前搜索到的全局最優(yōu)位置為基礎(chǔ)迭代產(chǎn)生一個(gè)混沌序列，然后將序列中的最優(yōu)粒子位置隨機(jī)替代當(dāng)前粒子群中的某一粒子的位置并進(jìn)行迭代，從而解決了因?yàn)榱Ｗ油?dǎo)致的算法早熟問題．

CPSO算法僅僅是對(duì)粒子群中全局最優(yōu)位置用混沌序列替代，但粒子速度計(jì)算公式中的參數(shù)還是以隨機(jī)數(shù)出現(xiàn)，所以不能完全保證能提高CPSO算法的種群多樣性和優(yōu)化的遍歷性．本文作者在此算法的基礎(chǔ)之上，提出一種新的全局混沌雜交粒子群優(yōu)化算法(EC-CPSO)，將CPSO算法中的隨機(jī)數(shù)用混沌隨機(jī)序列來(lái)替代，同時(shí)應(yīng)用早熟判斷機(jī)制，借鑒遺傳算法中雜交的概念，在對(duì)最優(yōu)粒子進(jìn)行混沌化處理之外，將其余粒子隨機(jī)兩兩雜交，用雜交后的子代粒子替換親代粒子，在一定程度上提高了種群的多樣性，降低整個(gè)粒子群收斂于局部極值點(diǎn)的可能性，提高了運(yùn)算的速度，將之用于(N+M)容錯(cuò)系統(tǒng)優(yōu)化模型證明該算法與CPSO相比具有一定的優(yōu)勢(shì)．

1 基本粒子群算法(PSO)

PSO算法首先初始化一群隨機(jī)粒子，然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索，即通過迭代找到最優(yōu)解．假設(shè)d維搜索空間中的第i個(gè)粒子的位置和速度分別為xi(xi,1,xi,2，…，xi,d)和vi(vi,1,vi,2，…，vi,d),在每一次迭代中，粒子通過跟蹤兩個(gè)最優(yōu)解來(lái)更新自己，一個(gè)就是粒子本身所找到的最優(yōu)解，即個(gè)體極值pi=(pi,1,pi,2，…，pi,d)；另一個(gè)是整個(gè)種群目前找到的最優(yōu)解，即全局最優(yōu)解pg=(pg,1,pg,2，…，pg,d)．在找到這兩個(gè)最優(yōu)值時(shí)，粒子根據(jù)如下的公式來(lái)更新自己的速度和新的位置[2]．

vi,j(t+1)=wvi,j(t)+c1r1[pi,j-xi,j(t)]+c2r2[pg,j-xi,j(t)]，

(1)

xi,j(t+1)=xi,j(t)+vi,j(t+1),j=1,2,…,d，

(2)

其中w為慣性權(quán)因子，c1和c2為正的學(xué)習(xí)因子，r1和r2為0到1之間均勻分布的隨機(jī)數(shù)．從式(1)可以發(fā)現(xiàn)，新速度由3部分組成．第1部分反映粒子維持原速度的程度；第2部分反映粒子的自我認(rèn)知，表示粒子對(duì)自身過去成功經(jīng)驗(yàn)的肯定；第3部分反映粒子間的社會(huì)交流，表明粒子間的信息交流與合作．粒子在解空間不斷跟蹤個(gè)體極值點(diǎn)和全局極值點(diǎn)進(jìn)行搜索，直到結(jié)果滿足終止條件或者達(dá)到最大迭代次數(shù)為止．

2 基于混沌的粒子群優(yōu)化改進(jìn)算法

2.1 混沌運(yùn)動(dòng)

混沌是存在于非線性系統(tǒng)中的一種較為普遍的現(xiàn)象，是由確定性方程得到的具有隨機(jī)性的運(yùn)動(dòng)狀態(tài)．在一定范圍內(nèi)混沌變量的變化具有隨機(jī)性，遍歷性和規(guī)律性，利用混沌變量的這些特征優(yōu)化搜索，能使算法跳出局部最優(yōu)，保持群體多樣性，改善算法的全局搜優(yōu)性能．一個(gè)典型的混沌映射系統(tǒng)Logistic方程是[3]：

yn+1=4yn(1-yn),n=1,2,3,…

(3)

式中yn為混沌變量，yn∈[0,1]．

2.2 全局混沌雜交粒子群優(yōu)化算法(EC-CPSO)

本文作者在混沌粒子群優(yōu)化算法(CPSO)基礎(chǔ)上，除用混沌變量對(duì)粒子的位置和速度進(jìn)行初始化，提高種群的多樣性和遍歷性外，還把具有混沌遍歷機(jī)制的混沌變量嵌入到PSO算法的參數(shù)中，即用不同的混沌隨機(jī)序列分別替代PSO算法中的隨機(jī)數(shù)r1,r2參數(shù)，使混沌變量在每次算法迭代時(shí)產(chǎn)生一個(gè)PSO算法所需要的隨機(jī)數(shù)．混沌的遍歷性和混沌的搜索機(jī)制與PSO算法的有機(jī)結(jié)合，有利于提高PSO算法全局搜索尋優(yōu)能力和魯棒性．

新的混沌粒子群算法的粒子速度迭代公式為：

vi,j(t+1)=wvi,j(t)+c1R1,j(t)[pi,j-xi,j(t)]+c2R2,j(t)[pg,j-xi,j(t)]，

(4)

式中：R1,R2是混沌變量映射值的函數(shù)，R1,R2替代PSO中的r1,r2隨機(jī)數(shù)．

在CPSO算法中，以粒子群當(dāng)前搜索到的全局最優(yōu)位置為基礎(chǔ)迭代產(chǎn)生一個(gè)混沌序列，然后將序列中的最優(yōu)粒子位置隨機(jī)替代當(dāng)前粒子群中的某一粒子的位置并進(jìn)行迭代，從而解決了因?yàn)榱Ｗ油?dǎo)致的算法早熟問題．為進(jìn)一步提高算法的速度，本文在此基礎(chǔ)之上，借鑒遺傳算法的思想[4]，對(duì)其余粒子進(jìn)行雜交處理，進(jìn)一步加強(qiáng)了對(duì)粒子區(qū)域的搜索能力，擺脫局部最優(yōu)，獲得改進(jìn)的搜索結(jié)果，提高搜索的速度和精度．遺傳算法是一種隨機(jī)搜索最優(yōu)化方法，它的基本操作是復(fù)制，雜交和變異．粒子群中的粒子被賦予一個(gè)雜交概率，這個(gè)雜交概率是隨機(jī)的，與粒子的適應(yīng)值無(wú)關(guān)．在每次迭代中，依據(jù)雜交概率選取指定數(shù)量的粒子放入一個(gè)池中．池中的粒子隨機(jī)的兩兩雜交，產(chǎn)生同樣數(shù)目的孩子粒子，并用孩子粒子代替父母粒子，以保持種群粒子數(shù)目不變．孩子粒子的位置child(x)由父母粒子的位置parent1(x),parent2(x)進(jìn)行算術(shù)交叉來(lái)計(jì)算[2]，即：

child(x)=p·parent1(x)+(1-p)·parent2(x).

(5)

孩子粒子的速度child(v)由下式來(lái)計(jì)算：

(6)

其中parent1(v),parent2(v)為父母粒子的速度．

粒子群用產(chǎn)生的孩子粒子取代父母粒子．雜交操作使孩子粒子繼承了父母粒子的優(yōu)點(diǎn)，例如兩個(gè)父母粒子均處于不同的局部最優(yōu)區(qū)域，那么兩者雜交產(chǎn)生的孩子粒子往往能夠擺脫局部最優(yōu)，從而獲得改進(jìn)的搜索結(jié)果，保證了搜索速度和搜索精度．

算法的具體流程如下：

2)初始化一群粒子，并使R1,R2分別用Logistic映射產(chǎn)生混沌隨機(jī)序列．R1,R2產(chǎn)生的混沌隨機(jī)序列值在0.0～1.0之間．

3)計(jì)算每個(gè)粒子的適應(yīng)度值f，更新個(gè)體最優(yōu)值pi和全局最優(yōu)值pg．

4)若滿足停止條件(通常為預(yù)設(shè)的運(yùn)算精度或迭代次數(shù))，搜索停滯，輸出結(jié)果，否則轉(zhuǎn)(5)．

5)判斷算法是否進(jìn)入早熟．判斷的標(biāo)準(zhǔn)為粒子的平均粒距和粒子的適應(yīng)度方差[5]：

粒子的平均粒距D(t)：

(7)

種群的適應(yīng)度方差σ2[6]：

(8)

其中，fi為第i個(gè)粒子的適應(yīng)度值，favg為當(dāng)前種群的平均適應(yīng)度值，fmax為當(dāng)前粒子的最大適應(yīng)度．

種群適應(yīng)度方差反映的是種群中個(gè)體的聚集程度．σ2越小，則種群中個(gè)體的聚集程度越大；反之，則聚集程度越?。S著迭代次數(shù)的增加，種群的個(gè)體適應(yīng)度會(huì)越來(lái)越接近，因此σ2會(huì)越來(lái)越?。?/p>

如果σ2α(α為預(yù)先給定的值，本文取0.1)同時(shí)D(t)β(β為預(yù)先給定的值,本文取2.5)，認(rèn)為算法出現(xiàn)早熟收斂現(xiàn)象．如果算法早熟，轉(zhuǎn)步驟(6)，否則，轉(zhuǎn)步驟(9)．

6)對(duì)粒子群最優(yōu)位置xgbest進(jìn)行混沌優(yōu)化，方法為[7-8]：

將xgbest通過方程映射到Logistic方程的定義域[0，1]上：

(9)

將混沌序列通過下面的方程逆映射回原解空間：

(10)

9)對(duì)剩下的粒子，根據(jù)雜交概率選取指定數(shù)量的粒子放入雜交池，池中的粒子隨機(jī)兩兩雜交產(chǎn)生同樣數(shù)目的孩子粒子，孩子粒子的位置和速度按公式(5)和(6)計(jì)算．

10)利用公式(4)和(2)更新所有粒子的位置和速度．轉(zhuǎn)步驟3．

3 性能分析

為驗(yàn)證EC-CPSO算法的性能，將之用于(N+M)容錯(cuò)系統(tǒng)優(yōu)化模型求解，并與CPSO算法進(jìn)行比較．

3.1 (N+M)容錯(cuò)系統(tǒng)優(yōu)化模型

(N+M)容錯(cuò)系統(tǒng)優(yōu)化模型如下[9]：

(11)

上述費(fèi)用模型是一個(gè)同時(shí)具有離散和連續(xù)變量的混合優(yōu)化問題，決策變量為n,m,λ/μ,其中n和m是整型變量，λ/μ為連續(xù)變量．當(dāng)n為一定值時(shí)，上述問題即求解m和λ/μ，使(N+M)容錯(cuò)系統(tǒng)的費(fèi)用最?。?/p>

3.2 初始粒子群的確定和約束條件的處理

在本算法中，(m,λ/μ)1×21維數(shù)組構(gòu)成1個(gè)粒子，(m,λ/μ)(pop-size)×2數(shù)組構(gòu)成1個(gè)初始化粒子群，因此，在確定粒子的過程中，應(yīng)首先確定包含最優(yōu)解的區(qū)域，在此最優(yōu)解區(qū)域?yàn)锳≥GA產(chǎn)生隨機(jī)點(diǎn)，并驗(yàn)證其是否滿足約束條件，即共產(chǎn)生pop-size個(gè)粒子，在迭代過程中，每個(gè)粒子也要驗(yàn)證是否滿足約束條件，如不滿足，則需調(diào)整，直到滿足條件為止．

3.3 計(jì)算結(jié)果和算法性能比較

在本優(yōu)化模型中，給定K0=15；λ0/μ0=0.01；j=0.1；k1=120 000；保證可用度GA=0.999 5；取n=1,2,…26．粒子群規(guī)模為40，最大迭代次數(shù)M=100，混沌搜索迭代次數(shù)T=10，慣性權(quán)重w=0.5；學(xué)習(xí)因子C1,C2取值2.0．分別計(jì)算m和λ/μ，結(jié)果見表1，當(dāng)n一定時(shí)，得到最優(yōu)的m和λ/μ組合．

表1 (N+M)容錯(cuò)系統(tǒng)優(yōu)化模型混沌粒子群算法結(jié)果

從表1可以看出：當(dāng)n一定時(shí)，用EC-CPSO算法可以得到m和λ/μ的最優(yōu)解．在采用相同數(shù)量備件m的情況下，隨著n的增加，λ/μ相應(yīng)減少，即在備用控制器不變的條件下，隨著工作控制器的增加，對(duì)每一臺(tái)控制器的可靠性的要求也越高．

為全面評(píng)價(jià)EC-CPSO算法的性能，本文選用文獻(xiàn)[1]提出的CPSO算法與該算法進(jìn)行比較．每一算法程序在n=20的條件下各自運(yùn)行30次．

圖1給出了進(jìn)化代數(shù)t和最優(yōu)粒子所得的系統(tǒng)總費(fèi)用C的變化曲線，最優(yōu)粒子所得的系統(tǒng)總費(fèi)用取30次實(shí)驗(yàn)的平均值．

在n=20的條件下,由表1可知EC-CPSO算法達(dá)到全局最優(yōu)時(shí)m=5,λ/μ=0.0281，表2給出的全局最優(yōu)成功率為30次實(shí)驗(yàn)中m和λ/μ達(dá)到全局最優(yōu)的次數(shù)與30的商，每次實(shí)驗(yàn)的迭代次數(shù)為50次．CPSO算法全局最優(yōu)成功率計(jì)算與此類似．

表2 算法實(shí)驗(yàn)結(jié)果比較(n=20，迭代50次)

從圖1可以看出，EC-CPSO相對(duì)于CPSO，擴(kuò)大了搜索空間，提高了搜索速度，在搜索效率上有較大程度的提高．從表2可以看出，EC-CPSO算法在50次迭代內(nèi)達(dá)到全局最優(yōu)的成功率和搜索成功所用時(shí)間均優(yōu)于CPSO算法．

為了考察改進(jìn)后EC-CPSO算法收斂的穩(wěn)定性，對(duì)30次實(shí)驗(yàn)的最終結(jié)果進(jìn)行統(tǒng)計(jì)分析，每次實(shí)驗(yàn)結(jié)束后得到群體最優(yōu)粒子，根據(jù)最優(yōu)粒子的位置值計(jì)算出系統(tǒng)的總費(fèi)用，同時(shí)計(jì)算實(shí)驗(yàn)結(jié)束后群體中所有粒子位置的平均值，根據(jù)這個(gè)平均值計(jì)算出系統(tǒng)的平均總費(fèi)用，如圖2所示.

圖1 進(jìn)化代數(shù)t和最優(yōu)粒子所得的系統(tǒng)總費(fèi)用C的變化曲線 圖2 系統(tǒng)總費(fèi)用和系統(tǒng)平均總費(fèi)用在實(shí)數(shù)次數(shù)下的C的變化曲線

由圖2可見，EC-CPSO算法每次實(shí)驗(yàn)得到的系統(tǒng)總費(fèi)用(包括平均費(fèi)用和最優(yōu)解費(fèi)用)的變化總在較小的范圍，標(biāo)準(zhǔn)偏差也較小，由此可知，該改進(jìn)算法的收斂性能比較穩(wěn)定，顯示了該算法的優(yōu)越性．

4 結(jié)論

1)全局混沌雜交粒子群優(yōu)化算法(EC-CPSO)相對(duì)于單純的混沌粒子群算法(CPSO)，因其將具有混沌遍歷機(jī)制的混沌變量嵌入到PSO算法的參數(shù)r1,r2中去，同時(shí)引入早熟判斷機(jī)制，借鑒遺傳算法的思想，在對(duì)最優(yōu)粒子進(jìn)行混沌化處理之外，對(duì)其余粒子進(jìn)行雜交處理，提高了算法的尋優(yōu)能力，能有效避免算法陷入局部最優(yōu)并防止過早收斂，計(jì)算成本亦不致增加太大．

2)基于(N+M)容錯(cuò)系統(tǒng)優(yōu)化模型仿真實(shí)驗(yàn)證明了該算法的正確性和有效性，性能分析表明，該算法能夠擺脫局部極值，得到全局最優(yōu)解，該算法在搜索速度，搜索效率等方面均優(yōu)于CPSO算法，同時(shí)具有較好的收斂穩(wěn)定性．

參考文獻(xiàn)：

[1] 高 鷹，謝勝利.混沌粒子群優(yōu)化算法[J].計(jì)算機(jī)科學(xué)， 2004， 31(8):13-15.

[2] 龔 純,王正林.精通MATLAB最優(yōu)化計(jì)算[M].北京：電子工業(yè)出版社，2009.

[3] 紀(jì) 震，廖惠連，吳青華.粒子群算法及應(yīng)用[M].北京：科學(xué)出版社，2009.

[4] CHEN R Q, YU J S. Study and application of chaos-particle swarm optimization based hybrid optimization algorithm[J]. Journal of System Simulation, 2008, 20(6):685-688.

[5] 段曉東，高紅橄，張學(xué)東，等.粒子群算法種群結(jié)構(gòu)與種群多樣性的關(guān)系研究[J].計(jì)算機(jī)科學(xué), 2007, 34 (11):164-166.

[6] 劉軍民，高岳林.混沌粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用， 2008， 28(2):323-324.

[7] 高 尚, 楊靜宇. 混沌粒子群優(yōu)化算法研究[J]. 模式識(shí)別與人工智能, 2006, 19(2):266-270.

[8] 孟紅記, 鄭 鵬, 梅國(guó)暉, 等. 基于混沌序列的粒子群優(yōu)化算法[J].控制與決策, 2006， 21(3):263-266.

[9] WANG S T. Intelligent networked (N+M) fault tolerant systems for hydro power station[J]. International Journal of Hydroelectric Energy, 1999, 17(1)：46-50.