一種改進操作算子的加速收斂遺傳算法

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

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

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