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