基于種群多樣性評(píng)價(jià)的自適應(yīng)遺傳算法

路 景

（威海職業(yè)學(xué)院信息工程系，山東威海，264210）

0 引言

成熟前收斂(即早熟現(xiàn)象)就是目前遺傳算法中較為突出的問題之一。針對(duì)這一問題，本文提出了一種基于種群多樣性評(píng)價(jià)的自適應(yīng)遺傳算法，經(jīng)實(shí)驗(yàn)證明，該方法能夠較好地保持種群多樣性，并且在提高問題求解的精度等方面也有較好的效果。

1 種群熵

在遺傳算法中，常用種群熵來對(duì)種群的多樣性程度進(jìn)行度量，種群熵的估算方法主要有以下兩種：

第一種方法以種群中個(gè)體的適應(yīng)度分布為依據(jù)，根據(jù)適應(yīng)度的集中程度對(duì)當(dāng)前種群多樣性進(jìn)行衡量。第代種群的種群熵的估算方法如下：

另一種估算種群熵的方法則是以種群中個(gè)體編碼串的分布情況作為依據(jù)，其具體估算方法如下：

1) 假設(shè)P(t)為第t代種群，種群規(guī)模為N，根據(jù)個(gè)體編碼的不同可將種群劃分為個(gè)部分，顯然，并且對(duì)于

4) 計(jì)算第t代種群的熵。

這種種群熵的估算方法反映了種群中不同類型個(gè)體的分布情況，但是這種方法有時(shí)不能及時(shí)反映種群早熟現(xiàn)象的發(fā)生，具有一定的滯后性。

針對(duì)以上種群熵估算方法各自存在的不足，我們將兩種方法進(jìn)行結(jié)合，用第一種估算方法的過于靈敏來彌補(bǔ)第二種估算方法相對(duì)滯后的缺點(diǎn)，采用指標(biāo)作為第代種群的多樣性度量，的計(jì)算方法如下式：

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

為了評(píng)價(jià)改進(jìn)算法的搜索性能，本文在MATLAB 7.0.1環(huán)境中分別對(duì)標(biāo)準(zhǔn)遺傳算法、自適應(yīng)遺傳算法、以及文中改進(jìn)算法進(jìn)行實(shí)現(xiàn)，并選用2個(gè)難度較大的測(cè)試函數(shù)對(duì)以上算法進(jìn)行了對(duì)比仿真實(shí)驗(yàn)。

2.1 測(cè)試函數(shù)及算法

3個(gè)測(cè)試函數(shù)的表達(dá)式及具體特征如下：

實(shí)驗(yàn)中，選用了3種遺傳算法與改進(jìn)算法進(jìn)行結(jié)果比較，以對(duì)改進(jìn)算法的性能進(jìn)行評(píng)價(jià)。算法1為標(biāo)準(zhǔn)遺傳算法結(jié)合最優(yōu)保留策略；算法2為自適應(yīng)遺傳算法；算法3為無操作概率宏觀調(diào)整的改進(jìn)算法，即在文中改進(jìn)算法基礎(chǔ)上，不進(jìn)行操作概率的宏觀調(diào)整，其余操作與改進(jìn)算法相同；算法4為文中改進(jìn)算法。

2.2 實(shí)驗(yàn)結(jié)果分析

將每種算法對(duì)每個(gè)函數(shù)均連續(xù)運(yùn)行100次，記錄算法停止時(shí)的最優(yōu)解函數(shù)值與理想極值的平均誤差、尋優(yōu)成功次數(shù)、尋優(yōu)成功時(shí)的平均收斂代數(shù)和100次搜索得到的最優(yōu)函數(shù)值，結(jié)果如表1、2所示。

表1 四種算法對(duì)函數(shù)的實(shí)驗(yàn)結(jié)果

表1 四種算法對(duì)函數(shù)的實(shí)驗(yàn)結(jié)果

?

表2 四種算法對(duì)函數(shù)的實(shí)驗(yàn)結(jié)果

表2 四種算法對(duì)函數(shù)的實(shí)驗(yàn)結(jié)果

?

從以上統(tǒng)計(jì)數(shù)據(jù)可以看出改進(jìn)遺傳算法無論是搜索停止時(shí)最優(yōu)解與理想極值的平均誤差、尋優(yōu)成功次數(shù)還是尋優(yōu)成功時(shí)的平均收斂代數(shù)都比算法1、2、3有一定程度上的提高。根據(jù)種群操作概率的宏觀、微觀調(diào)整能夠根據(jù)當(dāng)前種群多樣性指標(biāo)及時(shí)的提高或降低種群的操作概率，在避免由于種群多樣性喪失使算法陷入局部最優(yōu)的同時(shí)保證了算法的收斂速度。改進(jìn)算法在收斂速度及尋優(yōu)精度上均優(yōu)于簡單遺傳算法及自適應(yīng)遺傳算法。

3 總結(jié)

本文以種群多樣性評(píng)價(jià)為基礎(chǔ)對(duì)遺傳算法操作概率的確定方法進(jìn)行了改進(jìn)，從宏觀和微觀兩方面對(duì)其進(jìn)行調(diào)整，并將小生境技術(shù)中的確定性擁擠策略引入新舊個(gè)體的替換中來。通過對(duì)3個(gè)復(fù)雜測(cè)試函數(shù)進(jìn)行的仿真對(duì)比實(shí)驗(yàn)表明，改進(jìn)算法能更好的根據(jù)種群當(dāng)前狀態(tài)對(duì)交叉、變異操作進(jìn)行控制，避免由于種群多樣性喪失造成過早收斂現(xiàn)象的發(fā)生。與傳統(tǒng)遺傳算法相比，改進(jìn)算法能夠較好的保持種群多樣性，提升遺傳算法的全局尋優(yōu)能力，提高問題的求解精度。

[1]周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京：國防工業(yè)出版社，1999.110～113

[2]張文修，梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)[M].西安：西安交通大學(xué)出版社，2001.104～106

[3]江瑞，羅予頻，胡東成等.一種基于種群熵估計(jì)的自適應(yīng)遺傳算法[J].清華大學(xué)學(xué)報(bào)(自然科學(xué)版)，2002，42(3)：358～361