路 景
(威海職業(yè)學院信息工程系,山東威海,264210)
成熟前收斂(即早熟現(xiàn)象)就是目前遺傳算法中較為突出的問題之一。針對這一問題,本文提出了一種基于種群多樣性評價的自適應遺傳算法,經(jīng)實驗證明,該方法能夠較好地保持種群多樣性,并且在提高問題求解的精度等方面也有較好的效果。
在遺傳算法中,常用種群熵來對種群的多樣性程度進行度量,種群熵的估算方法主要有以下兩種:
第一種方法以種群中個體的適應度分布為依據(jù),根據(jù)適應度的集中程度對當前種群多樣性進行衡量。第代種群的種群熵的估算方法如下:
另一種估算種群熵的方法則是以種群中個體編碼串的分布情況作為依據(jù),其具體估算方法如下:
1) 假設P(t)為第t代種群,種群規(guī)模為N,根據(jù)個體編碼的不同可將種群劃分為個部分,顯然,并且對于
4) 計算第t代種群的熵。
這種種群熵的估算方法反映了種群中不同類型個體的分布情況,但是這種方法有時不能及時反映種群早熟現(xiàn)象的發(fā)生,具有一定的滯后性。
針對以上種群熵估算方法各自存在的不足,我們將兩種方法進行結合,用第一種估算方法的過于靈敏來彌補第二種估算方法相對滯后的缺點,采用指標作為第代種群的多樣性度量,的計算方法如下式:
為了評價改進算法的搜索性能,本文在MATLAB 7.0.1環(huán)境中分別對標準遺傳算法、自適應遺傳算法、以及文中改進算法進行實現(xiàn),并選用2個難度較大的測試函數(shù)對以上算法進行了對比仿真實驗。
3個測試函數(shù)的表達式及具體特征如下:
實驗中,選用了3種遺傳算法與改進算法進行結果比較,以對改進算法的性能進行評價。算法1為標準遺傳算法結合最優(yōu)保留策略;算法2為自適應遺傳算法;算法3為無操作概率宏觀調(diào)整的改進算法,即在文中改進算法基礎上,不進行操作概率的宏觀調(diào)整,其余操作與改進算法相同;算法4為文中改進算法。
將每種算法對每個函數(shù)均連續(xù)運行100次,記錄算法停止時的最優(yōu)解函數(shù)值與理想極值的平均誤差、尋優(yōu)成功次數(shù)、尋優(yōu)成功時的平均收斂代數(shù)和100次搜索得到的最優(yōu)函數(shù)值,結果如表1、2所示。
表1 四種算法對函數(shù)的實驗結果
表1 四種算法對函數(shù)的實驗結果
?
表2 四種算法對函數(shù)的實驗結果
表2 四種算法對函數(shù)的實驗結果
?
從以上統(tǒng)計數(shù)據(jù)可以看出改進遺傳算法無論是搜索停止時最優(yōu)解與理想極值的平均誤差、尋優(yōu)成功次數(shù)還是尋優(yōu)成功時的平均收斂代數(shù)都比算法1、2、3有一定程度上的提高。根據(jù)種群操作概率的宏觀、微觀調(diào)整能夠根據(jù)當前種群多樣性指標及時的提高或降低種群的操作概率,在避免由于種群多樣性喪失使算法陷入局部最優(yōu)的同時保證了算法的收斂速度。改進算法在收斂速度及尋優(yōu)精度上均優(yōu)于簡單遺傳算法及自適應遺傳算法。
本文以種群多樣性評價為基礎對遺傳算法操作概率的確定方法進行了改進,從宏觀和微觀兩方面對其進行調(diào)整,并將小生境技術中的確定性擁擠策略引入新舊個體的替換中來。通過對3個復雜測試函數(shù)進行的仿真對比實驗表明,改進算法能更好的根據(jù)種群當前狀態(tài)對交叉、變異操作進行控制,避免由于種群多樣性喪失造成過早收斂現(xiàn)象的發(fā)生。與傳統(tǒng)遺傳算法相比,改進算法能夠較好的保持種群多樣性,提升遺傳算法的全局尋優(yōu)能力,提高問題的求解精度。
[1]周明,孫樹棟.遺傳算法原理及應用[M].北京:國防工業(yè)出版社,1999.110~113
[2]張文修,梁怡.遺傳算法的數(shù)學基礎[M].西安:西安交通大學出版社,2001.104~106
[3]江瑞,羅予頻,胡東成等.一種基于種群熵估計的自適應遺傳算法[J].清華大學學報(自然科學版),2002,42(3):358~361