遺傳算法的有效基因塊保護策略

摘要：遺傳算法是一種結合全局搜索和局部搜索兩種特性的自適應搜集隨機算法，但存在早熟性收斂和收斂速度慢兩方面問題。由于遺傳算法運行過程中最小誘導模式普遍存在于個體中，同時在遺傳算法運行后期，個體中存在很多屬于收斂優化解或全局最優解的基因塊。通過分析和論證，建立了保護屬于最小誘導模式或優化解的有效基因塊的控制策略。該策略可與其他雜交算子和變異算子結合，為遺傳操作中父代個體包含的非有效基因塊基因座上的基因提供更多進化機會，從而提高這些基因座上的有效基因數量，維持有效的種群多樣性，較好地抑制了GA的早熟現象，提高了算法收斂速度和全局尋優能力。

關鍵詞：遺傳算法； 等位基因； 有效基因塊； 保護策略

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001-3695(2008)05-1319-04

0引言

遺傳算法(GA)是近年來發展起來的一種基于Darwin進化論和Mendel遺傳學說的問題求解算法。該算法具有很好的普適性，不存在求導和函數連續性的限定，對非線性復雜問題顯示出很強的求解能力，因而被成功地應用于諸多領域。GA作為一種通用的自適應隨機搜索算法，結合了全局搜索和局部搜索兩種特性，經過隨機選擇充分多個優化解，并按照某種策略取舍后，問題的求解質量能夠達到令人滿意的地步。

雖然在使用GA求解問題時需要搜索的解空間是有限的，在不受時間和空間限制的前提下，算法能找到問題的全局最優解；但隨著問題規模的擴大，問題求解需要花費問題規模的指數階時間[1，2]，導致由于計算時間過長使算法喪失可行性。上述問題集中體現為GA研究工作中的兩個難題：早熟性收斂和收斂速度慢。文獻[3]認為，GA中兩個最重要因素是種群多樣性和選擇壓力。選擇壓力越大，使種群中適應度較低的個體被淘汰的速度越快，雖然算法收斂速度也得到相應加快，但種群多樣性被破壞得也就越快，最終導致算法早熟性收斂；而選擇壓力越小，雖然能維持較高的種群多樣性，增加了算法搜索到全局最優解的概率，但降低了搜索效率，使算法的收斂速度變慢。文獻[4]則認為，產生早熟性收斂主要是由有效等位基因的缺失造成的。為此，維持種群多樣性、保持更多的有效基因是延遲算法早熟性收斂的有效手段之一。

本文稱個體中已包含的屬于最小誘導模式、算法收斂優化解或全局最優解中的基因塊為有效基因塊。由于各種遺傳算子隨機性過強，不能充分利用個體中的有效信息進行重組，對EGB不具有判斷能力。如果雜交點或變異點選擇在這些EGB中的某個基因座時，EGB將遭到破壞，這勢必影響算法的收斂速度和效果。當種群中越來越多的個體接近算法收斂的優化解時，EGB的長度越長，其數量也越多，隨機選擇雜交點或變異點的方法對EGB破壞概率就隨之越高。因此，保持豐富的有效基因和維持EGB是一個矛盾。如何判斷EGB并使其遺傳到下一代個體，是一個很值得探討的問題。

本文根據文獻[5，6]中提出的TSP解空間大峽谷原理，以及文獻[7]中提出的優化解之間邊的部分覆蓋結論，提出保存父代個體中EGB的控制策略。通過將該策略應用于GA中的遺傳算子，在高概率、大范圍保持EGB的前提下，擴展了算法的搜索空間，減少算法跳出局部最優區域所消耗的迭代時間，提高了算法收斂速度和全局尋優能力。通過對TSPLIB[8]中的大量實例進行測試，結果表明，使用保護策略的GA在全局尋優能力和收斂速度上得到明顯提高。

1基于基因塊保護的遺傳算子

當GA運行后期，由于個體與問題優化解的相似度很高，收斂的優化解與問題的全局最優解的相似度也在不斷提高，應用定理1可判斷滿意基因存在，將遺傳算子的操作應用于非滿意基因座上，可提高GA收斂質量和速度。雖然對于個體之間相似度小于0．5的情況不能完成上述分析，根據GA運行中存在的最小誘導模式機理，最小誘導模式普遍存在于個體之中，通過相同的判斷方式，同樣能達到以較高概率保護最小誘導模式的作用，加快算法的收斂速度。

應用定理1的結論在實施遺傳算子操作前，按照如下方法判斷本次操作中應選取的雜交點或變異點：取兩個體的差操作獲得等位基因集合，其元素即為本次判定為不屬于EGB或最小誘導模式的基因座，相應的遺傳操作應施加在這些基因座上。下面以TSP為例觀察GA種群進化過程中與優化解之間相似度變化趨勢。

1．2種群相似度變化情況實驗

實驗GA以保留杰出者為進化策略，采用兩點雜交、單點變異，種群規模為50，雜交概率為0.615，變異概率為0.15，進化200代，距離按取整方式計算。在每代進化前計算所有個體與問題的全局最優解相似度的平均值，問題的全局最優解利用Concorde[9]工具求得。為了使實驗具有對比性，每個數據集做三組實驗，每組實驗分別采用不同的局部搜索優化算法，分別是Concorde代碼中的2－Opt、3－Opt和鏈式Lin－Kernighan(chained Lin－Kernighan，CLK)算法。每組實驗重復1 000次，取每代的平均值。數據集選用TSPLIB中的eil51、ch150、a280和rd400為實例。實驗結果如圖1所示。

由實驗情況可以看出，GA的種群與全局最優解的平均相似度處于不斷上升趨勢。問題規模越小，這種變化趨勢的速度越快。圖1中采用CLK算法的eil51數據集在接近200時已經趨近于1，其不等于1的主要原因在于該問題存在多個全局最優解。由此可見，種群的相似度變化趨勢滿足定理1的條件。下面根據定理1給出相關的基于基因塊保護的遺傳算子設計。

1．3基于基因塊保護的遺傳算子

到目前為止，學術界提出的雜交算子的雜交方式主要包括一點雜交、兩點雜交、多點雜交和一致雜交等，具有代表性的雜交算子包括PMX、OX、ERX、SSX、DPX、CSEX、EAX和Inver-Over等。定理1可以應用于上述算子的改進。本文僅以兩點雜交為例建立基于EGB保護的兩點雜交算子，改進的算子如下：

參照變異個體X2可根據具體情況進行選擇。如果希望種群更快向最小誘導模式進化，則可以選擇種群中適應度最高的個體；如果希望擴大種群的多樣性，可隨機選擇一個個體或選擇種群中適應度最低的個體。

2實驗情況及分析

下述實驗環境均為Intel T2300E 1．66 MHz CPU，1 GB內存，操作系統為Windows XP。實驗數據集均采用來自TSPLIB中的國際標準數據集。

2．1應用保護策略前后的GA收斂特性對比

下面對應用EGB保護策略前后的GA收斂效果進行實驗對比，采用與2.2節的GA作為基準GA，另一個是在基準GA中應用EGB保護策略。為了驗證本文提出的控制策略的普適性，實驗分為三組：一組使用2－Opt求解eil51數據集，一組使用3－Opt求解ch150數據集，一組使用CLK求解rd400數據集。每組采用不同的局部搜索算法。每組分別運行1 000次，記錄每代最優個體的環路長度，最后求每代最優環路長度的平均值。實驗情況如圖2所示。

圖2應用EGB保護策略前后GA收斂特性對比圖

從圖2的統計結果可以看出，改進后的GA均具有更好的平均收斂優化解，局部搜索算法在不同控制策略顯現效果不同。但無論采用何種局部搜索優化算法，GA的后期收斂階段采用保護策略的算法都表現出了更高質量的收斂趨勢，表明本文提出的保護策略具有普適性。同時，CLK具有較2－Opt和3－Opt更好的優化效果。圖2(c)反映了兩種算法之間的平均收斂質量上差異更大，表明本文提出的控制策略的有效性。

從三組實驗統計結果的一致形態同樣可以看出，本文提出的控制策略在算法的尋優能力上得到增強，特別在進化后半階段，表現出比基準GA更好的尋優特性。其中圖2(b)組實驗中，基準GA在1 000次重復運行過程中求得30次問題的全局最優解，而改進后的GA求得120次；(c)組實驗中，僅改進后GA就求得了10次全局最優解。

2．2應用保護策略GA實驗結果

下面對TSPLIB中不同規模數據集進行了實驗。為了解決較大規模數據集，本實驗算法除采用2．2節的基準GA外，使用本文提出的控制策略，同時使用重復N/2次CLK作為局部搜索優化算法。其中N為問題規模。算法搜索到全局最優解即停止，否則進化200代停止。每個實例都是在連續運行10次后得到的統計結果，并給出了平均解距離全局最優解的偏差值。偏差＝(平均環路長度-全局最優解環路長度)/全局最優解環路長度×100%。實驗結果如表1和2所示。從實驗情況以及對TSPLIB其他中小規模數據集的實驗情況可知，應用本文控制策略改進的GA在200代以內能求解中小規模TSP的全局最優解。

對于大規模TSP，沒有使用保護策略的GA在求解d1291(1 291個城市)數據集時，就出現不能收斂于全局最優解的情況，而改進的GA已經能求解u2152(2 152個城市)及該規模以下TSP的全局最優解。對于規模更大的TSP，實驗的pcb3038在10次運行中有2次求得全局最優解，且平均偏差很小，為0．000 19%。為了進一步驗證本文提出的保護策略效果，下面對沒有使用新策略GA和使用策略GA進行對比，兩個算法之間僅存在除保護策略上的差異。實驗結果如表3所示。

通過表3可看出，沒有采用保護策略的GA在求解d1291(1 291個城市)數據集時，已出現不能在200代收斂于全局最優解的情況；而采用保護策略的GA在200代以內均收斂于全局最優解。這表明本文提出的控制策略的有效性。

采用基因庫GA[10]，其基因庫中收集的基因塊被認定屬于問題的全局最優解，不再發生改變。由于算法搜索的隨機性，仍有低概率采集到非全局最優解中邊或多值問題的多個全局最優解中邊的可能性。一旦發生這種情況算法，將較難發現問題的全局最優解，這也就是該算法求解規模僅能達到fl1577（包含1 577個城市的TSP）的主要原因。本文提出的控制策略僅在本次遺傳操作中保護EGB；在后續的遺傳操作中，EGB仍有較高的概率被遺傳算子調整或修改，所以抑制了采用基因庫的GA存在的上述問題。佳點集遺傳算法[11]采用在高適應度模式為祖先的家族方向上搜索出更好樣本的策略，其雜交算子適用于多種組合優化問題，并取得了較好的求解效果。它與文中列舉的雜交算子具有一個共同特點，即算子的設計和時間復雜度比較高。本文提出的控制策略普遍適用于組合優化問題，實現極為簡單，可與多種雜交算子和變異算子結合，改善了算法的收斂性能。

3結束語

通過分析及論證，本文建立了適用于組合優化問題的GA有效基因塊控制策略。該策略可與GA中雜交算子和遺傳算子結合，在高概率保護父代個體中已有有效基因塊的前提下，為父代個體中非有效基因塊基因座上的基因提供更多進化機會，從而提高了這些基因座上的有效基因數量，較好地抑制了GA的早熟現象，有效地提高了算法收斂速度和全局尋優能力。

參考文獻：

[1]JOHNSON D S， PAPADIMITRIOU C H， YANNAKAKIS M. How easy is local search?[J].Journal of Computer and System Scie-nces， 1988， 37(1):79-100.

[2]PAPADIMITRIOU C H， YANNAKAKIS M. Optimization， approximation and complexity classes [J]. Journal of Computer and System Sciences， 1991， 43(3):425-440.

[3]WHITLEY D. The GENITOR algorithm and selection pressure: why rank based allocation reproduction trials is best[C]//Proc of the 3rd International Conference on Genetic Algorithm. Los Altos: Morgan Kaufmann Publishers， 1989:116－123.

[4]POTTS J C， TERRI D G， SURYA B Y. The development and evolution of an improved genetic algorithm based on migration an artificial selection [J]. IEEE Trans on Systems， Man and Cybernetics， 1994， 24(1):73-86.

[5]HU T C， KLEE V， LARMAN D. Optimization of globally convex function [J]. SIAM J on Control and Optimization， 1989， 27(5):1026－1047.

[6]BOESE K. Cost versus distance in the traveling salesman problem， TR-950018[R].[S.l.]: CS Department， UCLA， 1995.

[7]LIN S， KERNIGHAN B W. An effective heuristic algorithm for the traveling－salesman problem [J]. Operations Research， 1973，31(2):498-516.

[8]University of Heidelberg. Traveling salesman problems library[EB/OL].(1997-08-08)[2006－11-07]. http://www.iwr.uni－heidelberg.de/groups/comopt/software/TSPLIB95/.

[9]DAVID A， ROBERT B， VASEK C. Concorde network optimization package[EB/OL].(1997-08-08)[2006－11-07]. http://www.tsp.gatech.edu/concorde/downloads/codes/src/co031219.tgz.

[10]楊輝， 康立山， 陳毓屏. 一種基于構建基因庫求解TSP問題的遺傳算法[J]. 軟件學報， 2003， 26(12):1753－1758.

[11]張鈴， 張鈸. 佳點集遺傳算法[J]. 軟件學報， 2001， 24(9):917-922.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”