一種改進(jìn)操作算子的加速收斂遺傳算法

摘 要：針對(duì)基本遺傳算法效率低和易早熟的缺陷，提出了一種改進(jìn)操作算子的遺傳算法。該算法在種群初始化、選擇、交叉、變異等基本算子的基礎(chǔ)上加以改進(jìn)，使算法具有更好的適應(yīng)性。對(duì)3組不同函數(shù)的測(cè)試表明，改進(jìn)算法較傳統(tǒng)的遺傳算法具有在種群很小的情況下收斂速度快穩(wěn)定性高的優(yōu)點(diǎn)，同時(shí)能有效地避免早熟現(xiàn)象。
關(guān)鍵詞：遺傳算法；變異；收斂速度；種群數(shù)

0 引 言
遺傳算法(Genetic Algorithm，GA)是一種宏觀意義下的仿生算法，它模仿的機(jī)制是一切生命與智能的產(chǎn)生與進(jìn)化過(guò)程，從一個(gè)初始種群出發(fā)，不斷重復(fù)執(zhí)行選擇，雜交和變異的過(guò)程，使種群進(jìn)化越來(lái)越接近某一目標(biāo)。它通過(guò)模擬達(dá)爾文“優(yōu)勝劣汰，適者生存”的原理激勵(lì)好的結(jié)構(gòu)；通過(guò)模擬孟德?tīng)栠z傳變異理論在迭代過(guò)程中保持已有的結(jié)構(gòu)，同時(shí)尋找更好的結(jié)構(gòu)。經(jīng)典遺傳算法的求解步驟為：初始化種群；選擇；交叉；變異；判斷終止條件。由于它簡(jiǎn)單有效，具有很強(qiáng)的魯棒性和通用性，所以被廣泛應(yīng)用于模式識(shí)別、神經(jīng)網(wǎng)絡(luò)、圖像處理、機(jī)器學(xué)習(xí)、工業(yè)優(yōu)化控制、自適應(yīng)控制、生物科學(xué)、社會(huì)科學(xué)等多種領(lǐng)域。
早熟和收斂時(shí)間過(guò)長(zhǎng)是影響遺傳算法效率的兩個(gè)主要因素，而選擇壓力過(guò)大是導(dǎo)致早熟收斂的一個(gè)重要原因，為此不少學(xué)者對(duì)遺傳算法做了改進(jìn)，但仍存在一定局限性。在此對(duì)遺傳算法個(gè)操作算子加以改進(jìn)，通過(guò)對(duì)經(jīng)典多極值測(cè)試函數(shù)的仿真研究表明，改進(jìn)后的算法能夠有效避免早熟且在種群規(guī)模較小的情況下具有較快的收斂速度。

l 改進(jìn)操作算子的遺傳算法
經(jīng)典遺傳算法的把變異作為一種輔助手段，認(rèn)為變異只是一個(gè)背景機(jī)制，這一觀點(diǎn)與生物學(xué)中的實(shí)際觀察是相符的，但作為設(shè)計(jì)人工求解問(wèn)題方法的思想，他正受到理論與實(shí)踐兩方面的挑戰(zhàn)。另外，從微觀角度來(lái)講，變異隨時(shí)都有可能發(fā)生，如果突變向不好的方向進(jìn)行．其“修復(fù)系統(tǒng)”立刻就能對(duì)其進(jìn)行修復(fù)。基于以上兩點(diǎn)，這里在選擇與交叉算子中滲入不同的變異行為，且動(dòng)態(tài)改進(jìn)變異算子，使算法能快速達(dá)到全局最優(yōu)。
1．1 初始化
為了改善初始群體的效能，提高模式的優(yōu)良度，采取如下方法：先隨機(jī)產(chǎn)生一個(gè)父染色體，對(duì)其進(jìn)行一定次數(shù)(20次左右)的逐位精英選擇高頻變異，方法如下：例如染色體為01001，先把第一位變異為1，成為11001。若適應(yīng)度提高，則此位以很大的概率p(如O．98)轉(zhuǎn)換為1，否則以很小的概率(如0．01)轉(zhuǎn)換為1，以此類(lèi)推。接著產(chǎn)生具有一定規(guī)模的染色體種群，隨機(jī)使其中每個(gè)染色體的某段基因與之前父染色體相應(yīng)基因段保持一致。如：假設(shè)父染色體為00110，隨機(jī)產(chǎn)生個(gè)體10101，若以第一和第二位基因與父染色體一致，則該個(gè)體變?yōu)椋?0101。該方法把較優(yōu)秀的模式分散到各個(gè)染色體中，使它一開(kāi)始就具有一定概率的優(yōu)秀短模式，從而有效提高算法的尋優(yōu)效率。
1．2 選擇操作
經(jīng)典遺傳算法根據(jù)適者生存原則選擇下一代個(gè)體。在選擇時(shí)，以適應(yīng)度為選擇原則。適應(yīng)度準(zhǔn)則體現(xiàn)了適者生存，不適應(yīng)者淘汰的自然法則。
然而基于適應(yīng)度的概率選擇機(jī)制如輪盤(pán)賭選擇法在種群中出現(xiàn)個(gè)別或極少數(shù)適應(yīng)度相當(dāng)高的個(gè)體時(shí)，就可能導(dǎo)致這些個(gè)體在群體中迅速繁殖，經(jīng)過(guò)少數(shù)迭代后占滿(mǎn)了種群的位置。這樣，遺傳算法的求解過(guò)程就結(jié)束了，也即收斂了。但這樣很有可能使收斂到局部最優(yōu)解，即出現(xiàn)早熟現(xiàn)象。為了從根本上避免早熟現(xiàn)象且加快收斂速度，采用基于高頻精英變異的錦標(biāo)賽選擇法。其操作如下：假設(shè)競(jìng)賽規(guī)模為2，首先選取種群中第1和第2個(gè)個(gè)體X和Y
如：X=100101，Y=011110
從第1位開(kāi)始比較適應(yīng)值的大小，即當(dāng)個(gè)體X與Y的第1位分別是1和O時(shí)，假設(shè)fitness(X)>fitness(Y)，于是把Y的第1位由0高頻變異為1，此時(shí)：
X=110101，Y=101110
此時(shí)，若fithess(X)fithess(Y)，則把Y的第1位由1高頻變異為O。如此下去，最終得到的為選擇出的個(gè)體，其中較高位(如第1至L／3位，其中L為染色體長(zhǎng)度)變異率為0．8，其他位變異率為0．95，理由是較高位的個(gè)體即使適應(yīng)度低也有可能在附近變異成適應(yīng)度更高的個(gè)體。
然后選取種群中第2和第3個(gè)個(gè)體應(yīng)用上法選擇出第2個(gè)個(gè)體，這個(gè)過(guò)程重復(fù)進(jìn)行，完成剩余個(gè)體的選擇。這種算子在選擇個(gè)體上就可以有方向性且極大地加快算法的收斂速度。
1．3 交叉操作
交叉是把兩個(gè)父?jìng)€(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作，從而在下一代產(chǎn)生新的個(gè)體。它的目的是開(kāi)發(fā)問(wèn)題解空間中新的區(qū)域，尋找父?jìng)€(gè)體已有的但未能合理組合的基因，盡量保證具有優(yōu)良模式的個(gè)體不被交叉操作所完全破壞，同時(shí)增大種群的離散程度，產(chǎn)生新的搜索空間。所有交叉操作的一個(gè)共同特征是，不破壞兩個(gè)父?jìng)€(gè)體之間的公共串模式，允許繼續(xù)搜索空間時(shí)保留好的模式。
對(duì)于選中用于繁殖下一代的個(gè)體，隨機(jī)地選擇2個(gè)個(gè)體的相同位置，按交叉概率P在選中的位置實(shí)行交換。在選中的位置實(shí)行交換。這個(gè)過(guò)程反映了隨機(jī)信息交換，目的在于產(chǎn)生新的基因組合，也即產(chǎn)生新的個(gè)體。在交叉時(shí)，可實(shí)行單點(diǎn)交叉或多點(diǎn)交叉。