石雙龍，林 亮，李紅菊

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

0 引言

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

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

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

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

1 初始化染色體

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

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

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

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

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

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

3 選擇過程

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

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

4 交叉算子

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

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

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

5 變異算子

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

6 遺傳算法步驟

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

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

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

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

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

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

7 數(shù)值實驗

7.1 實驗?zāi)Ｐ?/h3>

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

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

7.2 Matlab實驗結(jié)果

運(yùn)用Matlab軟件來實現(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é)論

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

[1]胡輝.粒子群優(yōu)化算法的Visual C++實現(xiàn)研究[J].科技廣場,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)化計算方法[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.