基于粒子群算法的改進(jìn)遺傳算法

石雙龍，林 亮，李紅菊

桂林理工大學(xué)理學(xué)院，廣西 桂林 541004

0 引言

遺傳算法是根據(jù)自然界的“物競(jìng)天擇，適者生存”現(xiàn)象二提出的一種隨機(jī)搜索算法。1975年，Holland教授在他的專著《Adaptation in Natural and Artificial Systems》[2]中，首次系統(tǒng)地提出了遺傳算法(GA or Genetic Algorithm)的基本原理，標(biāo)志著遺傳算法的誕生。該算法將優(yōu)化問(wèn)題看作是自然界中生物進(jìn)化過(guò)程，通過(guò)模擬大自然中生物進(jìn)化過(guò)程中的遺傳規(guī)律，來(lái)達(dá)到尋優(yōu)的目的。

進(jìn)入90年代，遺傳算法作為一種新的全局優(yōu)化搜索方法，適用于處理傳統(tǒng)搜索方法難以解決的復(fù)雜的和非線性的問(wèn)題、組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制和人工生命等方面，都得到了極為廣泛的應(yīng)用[3-8]，是21世紀(jì)有關(guān)智能計(jì)算的關(guān)鍵技術(shù)之一。

1995 年Eberhart 博士和Kennedy 博士提出了粒子群優(yōu)化算法。這種算法以其實(shí)現(xiàn)容易、精度高、收斂快等優(yōu)點(diǎn)引起了學(xué)術(shù)界的響應(yīng)，并且在解決某些實(shí)際問(wèn)題時(shí)，展示了其優(yōu)越性。粒子群優(yōu)化算法是一種新的進(jìn)化算法，與遺傳算法相似，它也是從隨機(jī)解出發(fā)，通過(guò)迭代尋找最優(yōu)解，它也是通過(guò)適應(yīng)度來(lái)評(píng)價(jià)解的優(yōu)劣。但是它比遺傳算法規(guī)則更為簡(jiǎn)單，它沒(méi)有遺傳算法的“交叉”和“變異”操作，它通過(guò)追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)。

根據(jù)坐標(biāo)的可平移性，從整體上看，我們可以假設(shè)優(yōu)化問(wèn)題的最優(yōu)解在整個(gè)解空間服從均勻分布。按照最大熵原則，最優(yōu)解應(yīng)該更加趨向于較優(yōu)解。為了能夠更快地搜索到最優(yōu)解，本文將粒子群算法和遺傳算法相結(jié)合。得到了一個(gè)應(yīng)用更加廣泛的改進(jìn)遺傳算法。

1 初始化染色體

在遺傳算法中，初始染色體是隨機(jī)產(chǎn)生的，最優(yōu)化問(wèn)題的解轉(zhuǎn)換成染色體一般有兩種表示方法：二進(jìn)制向量或浮點(diǎn)向量。使用二進(jìn)制向量作為一個(gè)染色體來(lái)表示決策變量的真實(shí)值，向量的長(zhǎng)度依賴于要求的精度，但使用二進(jìn)制代碼的必要性已經(jīng)受到了一些批評(píng)。在求解復(fù)雜優(yōu)化問(wèn)題時(shí)，二進(jìn)制向量表示結(jié)構(gòu)有時(shí)不太方便。

另一種表示方法是用浮點(diǎn)向量，每一個(gè)染色體有一個(gè)浮點(diǎn)向量表示，其長(zhǎng)度與解向量相同。用向量 x=(x1，x2，???,xn)表示最優(yōu)解問(wèn)題的解，其中是維數(shù)。則相應(yīng)的染色體是 V=(x1，x2，???,xn)。

對(duì)于每一個(gè)染色體V，我們選取已知的可行解做隨機(jī)的擾動(dòng)，這樣便得到一個(gè)染色體V =(x1，x2，???,xM)。如果如此得到的染色體可行，即說(shuō)明滿足約束條件。對(duì)于每一個(gè)染色體V在約束條件中，我們可以得出可行集中的一個(gè)內(nèi)點(diǎn)，記為V0。我們定義一個(gè)足夠大的數(shù)M ，以保證遺傳操作遍及整個(gè)可行集。當(dāng)然M的選取依賴于不同的決策問(wèn)題。在 RM中，首先隨機(jī)選擇一個(gè)方向d，如果 V0+M?d 滿足不等式約束，則將 V=V0+M?d作為一個(gè)染色體，否則，置M為0到M之間的隨機(jī)數(shù)，直到 V0+M?d可行為止。由于V0是內(nèi)點(diǎn)，所以在有限步內(nèi)，總是可以找到滿足不等式約束的可行解。重復(fù)以上過(guò)程popsize次，從而產(chǎn)生popsize個(gè)初始染色體V1,V2，???,Vpopsize，其中popsize為種群規(guī)模。

2 適應(yīng)函數(shù)

比較常用的評(píng)價(jià)函數(shù)是基于序的評(píng)價(jià)函數(shù)，我們將一代種群的染色體按照從好到差的順序排列成{V1, V2,???,Vpopsize}。在極大化問(wèn)題中，這個(gè)順序就是指對(duì)應(yīng)目標(biāo)函數(shù)值由大到小排列染色體，在極小化問(wèn)題中則正好相反。為了得到每個(gè)染色體的適應(yīng)度，我們根據(jù)這個(gè)順序給出如下的評(píng)價(jià)函數(shù)，

其中a∈(0,1)是一個(gè)事先給定的數(shù)。可以看到，機(jī)會(huì)越大的解適應(yīng)值也越大。

3 選擇過(guò)程

選擇過(guò)程是以popsize個(gè)扇區(qū)的旋轉(zhuǎn)賭輪為基礎(chǔ)的。賭輪上的刻度是按各染色體的適應(yīng)值來(lái)劃分的，染色體的適應(yīng)值越大，則其在賭輪上所占的面積就越大，該染色體被選中的概率也就越大，每旋轉(zhuǎn)一次都會(huì)為新的種群選擇一個(gè)染色體。但是為了避免早熟現(xiàn)象，在這里，我們結(jié)合粒子群算法的優(yōu)越性，首先選出最佳染色體V0。然后，令 q0=0，對(duì)于各染色體Vi，令其累次概率為

我們?cè)趨^(qū)間 中隨機(jī)產(chǎn)生一個(gè)實(shí)數(shù)。如果滿足，則選擇。重復(fù)上述過(guò)程，直至生成個(gè)新的染色體終止，于是我們得到一個(gè)新的種群。

4 交叉算子

首先給定交叉概率，則每次種群中平均有pc?popsize個(gè)染色體進(jìn)行交叉操作。對(duì)各染色體我們隨機(jī)產(chǎn)生[0，1]上的一個(gè)隨機(jī)數(shù)p，若p＜pc，則該染色體被選中作為父代可以進(jìn)行交叉操作。將選中的染色體進(jìn)行編組，。以第一個(gè)父代染色體為例，顯然，兩個(gè)子代染色體V1和V0是兩個(gè)父代染色體的線性組合，寫(xiě)成向量形式即

其中隨機(jī)數(shù)c∈[0,1]。經(jīng)過(guò)上述交叉操作，我們可以得到一個(gè)子代染色體。最后，我們可以用約束條件對(duì)它進(jìn)行可行性檢驗(yàn)。若該子代染色體滿足約束條件，則用子代染色體替代原染色體，否則，

重新檢驗(yàn)該子代染色體的可行性，若還是不滿足越深條件，則重新產(chǎn)生新的隨機(jī)數(shù)，再次進(jìn)行交叉操作，直到新的可行染色體出現(xiàn)或者達(dá)到最大交叉上限，則停止。這樣，我們幾可以得到popsize個(gè)新的染色體Vi，i=1,2,???,popsize 。

5 變異算子

變異操作是產(chǎn)生新染色體的輔助方法，但它決定了遺傳算法的全局搜索能力，可以保證群體的多樣性，防止早熟現(xiàn)象。同樣給定一個(gè)變異概率Pm，并從區(qū)間上隨機(jī)產(chǎn)生p∈(0,1)，若 p＜pm，則該染色體被選中作為父代，進(jìn)行變異操作。對(duì)于各需要變異的父代染色體 V'，在空間 Rn中隨機(jī)選取一個(gè)變異方向d和步長(zhǎng)M ＞0（足夠大），其中向量與染色體維數(shù)相同，則變異后的染色體X=V'+M ×d 。同理，我們對(duì)進(jìn)行可行性和優(yōu)越性檢驗(yàn)。如果通過(guò)檢驗(yàn)則用X替換掉 V'，否則，d=d/2，繼續(xù)進(jìn)行變異操作，直到用X替換掉 V'或者達(dá)到最大變異次數(shù)，則停止變異并保留。這樣，我們通過(guò)變異可以得到新的種群 Vi， i=1,2,???,p opsize 。

6 遺傳算法步驟

步驟1：根據(jù)約束條件隨機(jī)產(chǎn)生popsize個(gè)染色體，即種群。

步驟2：按照轉(zhuǎn)盤(pán)賭原則，隨機(jī)選取一個(gè)最佳父代染色體和其它popsize個(gè)父代染色體作為交叉種群（交叉種群不能包含最佳父代染色體）。

步驟3：對(duì)于每個(gè)父代染色體都以概率pc與最佳染色體進(jìn)行交叉運(yùn)算，即隨機(jī)生成r∈(0,1)，若 r＜pc，則對(duì)應(yīng)的染色體將與最佳染色體進(jìn)行交叉運(yùn)算，否則不進(jìn)行交叉運(yùn)算。

步驟4：將所新得到的各子代染色體以概率Pm進(jìn)行變異操作，即隨機(jī)生成r∈(0,1)，若 r＜pm，則對(duì)應(yīng)的染色體進(jìn)行變異運(yùn)算，否則不進(jìn)行變異運(yùn)算。

步驟5：更新父代染色體，即在子代染色體中，擇優(yōu)選取較好的染色體代替原來(lái)的父代染色體，作為下次交叉變異的父代染色體，并計(jì)算各自相應(yīng)的適應(yīng)值。

步驟6： 重復(fù)步驟2—步驟5知道達(dá)到精度要求，或者達(dá)到約定的最大循環(huán)次數(shù)。

7 數(shù)值實(shí)驗(yàn)

7.1 實(shí)驗(yàn)?zāi)Ｐ?/h3>

例1 現(xiàn)運(yùn)用遺傳算法求解以下最大值問(wèn)題，

對(duì)于這個(gè)問(wèn)題，我們可以直接將解 (x1， x2， x3)是為遺傳迭代的染色體。顯然染色體屬于集合內(nèi)

7.2 Matlab實(shí)驗(yàn)結(jié)果

運(yùn)用Matlab軟件來(lái)實(shí)現(xiàn)遺傳算法，并設(shè)定相應(yīng)的各參數(shù)如下：

最大交叉、最大變異次數(shù)、最大變異半徑以及最大遺傳迭代次數(shù)均設(shè)為1000。利用Matlab7.6得到結(jié)果如下：

遺傳迭代次數(shù)：i=135

最佳染色體：( x1， x2， x3)=(0.6332,0.3990,0.3058)

最優(yōu)值：1.9805

顯然這一結(jié)果要優(yōu)于Liu[9]給出的遺傳迭代400次的結(jié)果：

最佳染色體：( x1， x2， x3)=(0.636,0.395,0.307)

最優(yōu)值：1.980

結(jié)果誤差曲線圖：

結(jié)果分析

圖1 結(jié)果誤差曲線圖

其中橫坐標(biāo)為遺傳迭代次數(shù)，縱坐標(biāo)為每次迭代的誤差取值。

8 結(jié)論

本文按照最大熵原理，用粒子群算法代替了遺傳算法的交叉算子，得到了一個(gè)應(yīng)用更加廣泛的改進(jìn)遺傳算法。最后的數(shù)值實(shí)驗(yàn)結(jié)果也表明，改進(jìn)后的算法不管是在收斂速度還是精度上都明顯優(yōu)于原有的算法，說(shuō)明該算法確實(shí)是有效可行的。實(shí)際上本文給出了一種判斷算法優(yōu)越性的新思路。

[1]胡輝.粒子群優(yōu)化算法的Visual C++實(shí)現(xiàn)研究[J].科技廣場(chǎng),2008(5).

[2]Goldberg D E.Genetic Algorithms in Search, Optimization and Machine Learning[M]. MA:Addison-Wesley, 1989.

[3]Koza J R.Genetic Programming[M].Cambridge,MA:MIT Press,1992.

[4]Koza J R.Genetic Programming II[M].Cambridge,MA: MIT Press,1994.

[5]Michalewicz Z.Genetic Algorithms+ Data Structures=Evolution Programs[M]. New York:Springer-Verlag,1996.

[6]Yoshitomi Y,Ikemoue H,Takaba T.Genetic algorithm in uncertain environments for solving stochastic programming problem[J].Journal of the Operations Research Society of Japan,2000,43(2):266-290.

[7]邢文訓(xùn),謝金星.現(xiàn)代優(yōu)化計(jì)算方法[M].北京:清華大學(xué)出版社,1999.

[8]Zadeh L A. Fuzzy sets as a basis for a theory of possibility[J]. Fuzzy Sets and Systems, 1978, 1: 3-28.

[9]Liu B,Theory and Practice of Uncertain Programming,2nd ed.,Springer-Verlag,Berlin,2009.