改進自適應遺傳算法的性能分析

丁知平

摘要：遺傳算法存在未成熟收斂和收斂速度慢等不足之處，傳統(tǒng)的自適應遺傳算法雖能有效提高算法的收斂速度，卻難以增強算法的魯棒性。文中提出的改進的自適應遺傳算法，提高了其搜索能力，具有更快的收斂速度和更可靠的穩(wěn)定性，達到了預期的效果。關鍵詞：遺傳算法；自適應；收斂；改進；性能

中圖分類號: TP18文獻標識碼：A文章編號：1009-3044(2012)21-5202-04

遺傳算法(Genetic Algorithm，以下簡稱GA)[1]是一種模仿生物群體進化的隨機優(yōu)化算法，它是由美國密歇根大學J.H.Holland教授創(chuàng)立的。標準的遺傳算法(Standard GA，以下簡稱SGA)往往存在一定的不足之處，比如容易出現(xiàn)早熟以及過慢的收斂速度等不良現(xiàn)象。鑒于此，Srinvas等提出了自適應遺傳算法(Adaptive GA，以下簡稱AGA)[4]，在GA中應用自適應調整交叉率和變異率，結果證明，這種算法在GA的收斂速度方面能夠較好的改進。不過，AGA在演化初期存在停滯現(xiàn)象，故將自適應調整交叉率和變異率的方法用于GA以提高算法收斂速度和魯棒性仍十分具有挑戰(zhàn)性[6]。文獻[3]提出一種改進的自適應遺傳算法，在一定程度上提高算法的計算速度和收斂速度。但因為它們計算所得到的變異概率Pm及交叉概率Pc具有不良的穩(wěn)定性，同時該算法對整體協(xié)作能力存在不足。

為此，該文提出一種新的改進遺傳算法，改進后的算法效果良好，在算法的收斂速度以及全局搜索性能等方面都具備良好的效果。

公式中：?max是指群體的最大適應度；?avg是指群體的適應度平均值；?是指雜交雙方適應度大者的適應度；?是指個體的適應度；0

這種算法可以根據(jù)每代個體適應度的改變來自適應地改變Pm和Pc，在保護最優(yōu)個體的同時，加快了較差個體的淘汰速度。該算法在一定程度上可以改善遺傳算法的性能。但該算法也存在不容易跳出局部最優(yōu)解，因為該算法是以個體為單位改變Pm和Pc，缺乏對整體的協(xié)作精神。同時，由于該算法對每個個體都要分別計算Pm和Pc，這樣會影響程序的執(zhí)行效率，也不利于硬件的實現(xiàn)。1.2文獻[3]提出的自適應遺傳算法(本文中簡稱IAGA)

針對M.Srinivas所提出的算法的缺點，文獻[3]提出一種改進的自適應遺傳算法。其通過判斷適應度集中程度的情況，對整個群體的Pm以及Pc進行自適應地變化調整，同時將群體適應度的集中程度用三個變量來衡量，即：適應度平均值、群體的最大適應度、最小適應度。文獻[3]提出的算法在一定程度上可以提高算法的計算速度和收斂速度。但因為它們計算所得到的變異概率Pm及交叉概率Pc具有不良的穩(wěn)定性。尤其在遇到峰值密度較高的多峰值函數(shù)時，更容易出現(xiàn)得到概率較大的結果的現(xiàn)象。同時，該算法在一定程度上也是缺乏對算法的整體協(xié)作能力。

整體把控能力等方面都存在一定的不足之處。為此，本文在基于上述自適應遺傳算法的基礎上，提出一種新的自適應遺傳算法，以改進其在上述所存在的不足。

2.1與進化代數(shù)有關的雜交概率的改進介紹

雜交算子的主要目的是用來產(chǎn)生新個體，同時也是為了讓算法具備全局搜索的能力。因此，當我們以種群中的個體來觀察時，如果雜交的概率偏大，群體中的優(yōu)良模式就會被破壞；而如果雜交的概率偏小時，對于新個體的產(chǎn)生速度又會變得緩慢。在這里可以看出，與個體適應度有關的雜交概率的算法是具有一定的優(yōu)勢的。當我們以種群整體進化的整個過程來觀察時，雜交概率應該會一個穩(wěn)定但會慢慢變小，最終會向某一個穩(wěn)定值靠近的過程。當我們以新個體的產(chǎn)生方面來看，在雜交操作上，群體中所有的個體應該具有相同的地位，也就是概率是一樣的，這樣就可以使得遺傳算法在搜索空間擁有每個方向的勻稱性。文獻[3，4]的交叉概率算法都只注意了個體的作用，而忽視了整個種群的進化趨勢情況和各個體的變異機會。

在本文中，為了改善目前算法所存在的不足，設計了一種與適應度沒有關系，只同進化代數(shù)有關的概率公式：

本公式可以達到交叉概率隨著進化過程而逐漸變化，同時能夠對同一代的種群中的個體給予一樣的交叉能力。這樣也可以更好的實現(xiàn)全局搜索能力，同時，算法的計算速度也可以得到極大的提高。相對文獻[4]，該文的算法對劣質個體的處理顯得相對薄弱,但可以通過下面的方法來進行彌補此缺陷。

2.2自適應變異概率的改進介紹

維持種群多樣性是變異算子的主要用處，其主要是用來抑制早熟現(xiàn)象的出現(xiàn)以及產(chǎn)生新個體。但雜交算子則不同，其主要是在全局搜索中起作用。因此，就變異概率來說，應該是在同一種群中每個個體都是隨著個體本身的好壞而發(fā)生變化。同時，變異概率的取值也是十分關鍵的。如果變異概率的取值偏小，就很容易導致抑制早熟現(xiàn)象以及產(chǎn)生新個體的能力減弱。而如果變異概率取值偏大，又容易導致遺傳算法搜索過程成為隨機過程的現(xiàn)象產(chǎn)生，從而使種群中較好的模式被破壞的可能性增加。所以，自適應變化的變異操作的設計十分重要。

變異概率設計需要滿足：（1）應該使變異概率慢慢減小，從而能夠使得群體快速集中。（2）較小的變異概率給優(yōu)秀的個體。（3）較大的變異概率給劣質的個體。針對上述條件，在本文中設計了如下的自適應變異概率公式：

在公式中，Pm(t)指的是第t代種群中個體Xi的變異概率；Pm,min指的是預先設置的最小的變異概率；Pm,max指的是預先設置的最大的變異概率。

以上式子的計算可以實現(xiàn)變異概率隨進化過程自適應地變化。也能夠針對所有待變異個體的適應值做相應的自適應變化。

上面所選取的函數(shù)在遺傳算法性能測試方面都是很經(jīng)典的函數(shù)，它們都有全局最小值，不過也存在有多個極值點的函數(shù)。在本實驗中，先對函數(shù)?1、?3和?4進行求負處理，目的是方便對這些函數(shù)求最大值。

3.2仿真實驗結果及分析

在對上面三種遺傳算法進行仿真實驗時，對所用到的參數(shù)作說明：收斂時間的單位是秒；群體的規(guī)模是64；最大進化代數(shù)是180。其他參數(shù)見表2

表2各算法中參數(shù)說明

針對傳統(tǒng)遺傳算法的早熟和收斂速度慢等缺點，文中提出一種改進的自適應遺傳算法，實驗數(shù)據(jù)表明，該算法具有良好的搜索能力，具有更快的收斂速度和更可靠的穩(wěn)定性，達到了預期的效果。

[1] Holland J H.Adaptation in Natural Artificial Systems[M].MIT Press,1975.

[2] Masanori Suglsaka,Xinjian Fan.Adaptive Genetic Algorithm with a Cooperative Mode[C].Proceedings of IEEE International Symposium on Industrial Electronics,2001.

[3]王蕾,沈庭芝,招揚.一種改進的自適應遺傳算法[J].系統(tǒng)工程與電子技術,2002:24（5）:75-78.

[4] Srinvas M,Patnaik L.M.Adaptive Probabilities of Crossover and Mutation in Genetic Algorithms[J].IEEE Trans on Systems,Man and Cyber? netics,1994:24(4).

[5]歐陽森,王建華,耿英三,等.一種新的改進遺傳算法[J].計算機工程與應用, 2003(11).

[6] F Herrera,M Lozano.Adaptive Genetic Operators Based on Coevolution with Fuzzy Behaviors[J].IEEE Trans on Evolutionary Computation, 2001(5):149-165.

[7]李茂軍,童調生.用單親遺傳算法求解有序組合優(yōu)化問題[J].系統(tǒng)工程與電子技術,1998(20):58-61.

[8]王小平,曹立明.遺傳算法:理論、應用與軟件實現(xiàn)[M].西安:西安交通大學出版社,2002.

[9]沙智明.基于改進自適應遺傳算法的電力系統(tǒng)相量測量裝置安裝地點選擇優(yōu)化[J].電工技術學報,2004(8).