一種改進操作算子的加速收斂遺傳算法
加入技術(shù)交流群
一點交叉是經(jīng)典的交叉方法，它是對于給定的兩個父個體，隨機地選取1個交叉位置，然后相互交換兩個個體交叉位置右邊部分基因，形成2個子代，一點交叉能夠搜索到的空間十分有限。多點交叉的破壞性可以促進解空間的搜索，而不是促進過早地收斂，因此搜索更加健壯。這里在采取多點交叉的同時考慮父個體間的多樣度。
當(dāng)兩個父個體的漢明距離較低，可能導(dǎo)致交叉操作無效。另外，由于交叉點隨機產(chǎn)生，可能會導(dǎo)致交叉后新個體無變化，例如，兩父個體分別為01100101和01011010，如果交叉點取值為第2位，則交叉后的兩個新個體與父個體相同，交叉操作無效。在此采取交叉概率與漢明距離成正比的策略：兩父體相似度高時交叉概率減小以避免無效操作，一旦在這種情況下進行交叉，首先保持具有高適應(yīng)度的父個體不變，然后對低適應(yīng)度個體或者交叉點左右具有相同子串的個體采取變異操作以增大它們之間的漢明距離，從而提高交叉操作的有效性。
1．4 變異操作
根據(jù)生物遺傳中基因變異的原理，以變異概率Pm對某些個體的某些位執(zhí)行變異。在變異時，對執(zhí)行變異的串的對應(yīng)位求反，即把1變?yōu)镺，把O變?yōu)?。
單靠變異不能在求解中得到好處。但是，它能保證算法過程不會產(chǎn)生無法進化的單一群體。因為在所有的個體一樣時．交叉是無法產(chǎn)生新的個體的，這時只能靠變異產(chǎn)生新的個體。也就是說，變異增加了全局優(yōu)化的特質(zhì)。
這里提出一種自適應(yīng)快速收斂變異法：對每一個體采取從高位到低位逐位變異的策略。在尋優(yōu)的早期主要是全局搜索，此時各變量二進制的高位應(yīng)采用高變異率，低位采用低變異率。在尋優(yōu)過程中不斷調(diào)整各位的變異率，即高位變異率逐漸降低，低位變異率逐漸增加。到尋優(yōu)后期，主要是局部優(yōu)化，全局優(yōu)化次之，此時各位變異率與早期相反，即低位變異率要比高位變異率大。在變異過程中采用概率精英保留策略，也就是每位變異后若適應(yīng)值增加，則以高概率保留，否則放棄此位變異。實驗證明，這種變異策略在種群規(guī)模較小的情況下能獲得較滿意的進化能力。本文引用地址：http://www.ex-cimer.com/article/192077.htm
2 算法描述
算法描述為：
(1)采用二進制編碼，隨機產(chǎn)生一個體，通過逐位高頻精英變異，提高其適應(yīng)度；
(2)利用上述較優(yōu)父染色體產(chǎn)生產(chǎn)生種群；
(3)進行基于高頻精英變異的錦標(biāo)賽選擇；
(4)進行改進的交叉運算；
(5)進行自適應(yīng)變異運算；
(6)是否到最大的遺傳代數(shù)，如果達到，結(jié)束；否則轉(zhuǎn)到步驟(3)。
3 仿真試驗及結(jié)果分析
3．1 試驗
為驗證改進算法的效率，用經(jīng)典遺傳算法SGA和文中的加速收斂改進遺傳算法相比較，其中SGA采用的遺傳操作及相應(yīng)參數(shù)為比例選擇、單點交叉(交叉概率0．85)及基本位變異(變異概率0．05)，種群規(guī)模為100，進化代數(shù)為100。兩者都采用保留個體精英的方法。選擇如下3個算例進行仿真計算。
(1)Camel函數(shù)
此函數(shù)有6個極小點，其中有2個(一0．089 8，O．712 6)和(0．089 8，一O．712 6)為全局最小點，最小值為一1．031 628，自變量的取值范圍為一100x，y100。
(2)Shubert函數(shù)
該函數(shù)有760個局部極小點，其中只有1個(一1．425 13，一O．800 32)為全局最小，最小值為186．730 9。自變量取值范圍一10x，y10。此函數(shù)極易陷入局部極小值186．34。
(3)Schaffer函數(shù)
該函數(shù)有無限個局部極大點，其中只有一個(0，0)為全局最大，最大值為1。自變量的取值范圍為一100x，y100。該函數(shù)最大值峰周圍有一個圈脊，它們的取值均為O．990 283，因此很容易停滯在局部極大值。
改進后算法的種群規(guī)模為20，進化代數(shù)為60。對兩種算法進行100次隨機仿真，試驗結(jié)果如表1所示。
3．2 結(jié)果分析
從以上結(jié)果可以看出，SGA容易早熟收斂，而改進后的算法能很好地擺脫早熟，并能以很高的成功概率快速搜索到最優(yōu)值。從各參數(shù)也可以看出，改進后的遺傳算法在種群規(guī)模很小的情況下也具有很高的尋優(yōu)效率。因此，這里提出的改進算子GA從全局收斂概率和平均進化代數(shù)來看，是成功的，它具有高效的全局以及局部搜索能力。
4 結(jié) 語
通過對算法各算子的改進，較好地解決了一般遺傳算法收斂速度慢和全局尋優(yōu)能力弱的缺點。實踐表明，改進GA和標(biāo)準(zhǔn)GA相比，在花費更少的情況下具有更快的收斂速度和精度。
評論