遺傳算法收斂效率研究

汪民樂?k

摘要：遺傳算法的收斂效率問題，嚴重制約了其理論發展和應用。本文提出新的遺傳算法收斂效率指標，對其給出嚴格的定義，對基于模式的GA收斂效率的有關研究進展進行系統綜述與分析，包括對遺傳算法運行中模式的變化規律及典型遺傳算法模式定理的描述，在此基礎上，提出一種新型高效率自適應選擇算子，從而為提高遺傳算法收斂效率提供了有效途徑。

關鍵詞：遺傳算法；收斂效率；模式；自適應選擇算子

中圖分類號：TP18文獻標識碼：A

1引言

由于遺傳算法（Genetic Algorithm—GA）具有傳統優化方法無可比擬的優點[1]，因而近年來被廣泛應用于函數優化、機器學習、自動控制及神經網絡設計等領域[2～5]，其有效性得到體現。在以上領域的實際問題幾乎都可以歸結為復雜系統優化問題。對于這類問題，形形色色的傳統求解算法均為基于單點迭代的搜索算法，這也是計算數學中的經典方法。這類方法在求解復雜系統優化問題時有著嚴重缺陷：一是搜索效率低，二是易陷入局部極優。而GA是智能化仿生類隨機搜索算法，能有效搜索全局最優解，這也正是它的重要價值之一。盡管如此，目前仍然存在嚴重制約GA理論發展及其應用的障礙，即GA的收斂效率問題。GA的大計算量使其時間復雜性隨種群規模和遺傳代數的增加而劇增，雖然理論上已證明帶有最優保持操作的GA一定收斂于全局最優解，但這一結論是建立在進化時間T→∞的基礎之上的，因而不具有實際意義。對于大規模問題，GA收斂效率低的問題更顯突出。為了提高GA收斂效率，國內外一些學者進行了有益的探討，取得了一些研究成果[6～16]，主要集中于收斂性的理論證明、模式分析和算子的改進等方面。但這些研究仍顯不足，主要表現在以下幾個方面：一是研究不系統，多為GA的局部改進，在克服一個問題的同時，可能導致新問題的產生。如：提出新的高效率選擇算子，可能導致早熟現象的發生；二是開展的研究多為針對具體問題，因而不具有通用性；三是理論基礎薄弱，多為實驗性的，缺乏嚴格的理論證明和分析。綜上所述，提高GA的收斂效率具有非常重要的意義，但目前，如何提高GA的收斂效率仍是一個亟待解決的問題，本文就這一問題從GA收斂效率指標、GA基礎理論、算法改進等多個方面展開探索。

由算例的計算結果可知：由于該問題規模較小，表面上看來采用自適應選擇算子后減少的CPU時間不多，似乎效益不大，但正如前面所分析的，對于大規模問題，其效益將是明顯的。事實上，即使被減少的計算時間僅以秒計，對于廣泛存在的計算機實時控制問題，其意義也是很大的。

5結束語

提高遺傳算法的收斂效率是遺傳算法研究中十分有價值的方向之一，具有重要的理論和實踐意義。目前，有關遺傳算法收斂效率的研究還有待進一步深入，尤其需要具有實際應用價值的研究成果。本文提出新的遺傳算法收斂效率指標，進而對基于模式的GA收斂效率分析的有關研究進展進行了系統分析與總結，包括遺傳算法運行中模式的變化規律對其收斂效率的影響及典型遺傳算法模式定理的描述，在此基礎上，提出了一種新型高效率自適應選擇算子，并進行了仿真實驗分析，從而為提高遺傳算法收斂效率提供了有效途徑。

參考文獻

[1]GOLDBERG D E. Genetic algorithm in Search， optimization and machine learning[M]. Reading， Addison-Wesley，1989.

[2]KRISTISSON K，DUMENT G A. System identification and control using Genetic Algorithms[J]. IEEE Trans on SMC.1992，22（5）：1033-1046.

[3]YAO X. A Review of Evolutionary Artificial Neural networks[J]. Int.J.Intelligent Systems， 1993，8（6）：539-567.

[4]A.J.Chipperfield. Multiobjective turbine engine controller design using GA[J]. IEEE trans. Int Electron，1996，4（3）：583-589.

[5]FOGEL D.B. A comparison of evolutionary Programming and genetic algorithms on selected constrained Optimization Problems[J]. Simulation，1995， 64 （6）：397-406.

[6]CARLOS M. Multiobjective optimization and multiple constraint handling with evolutionary algorithm[J]. IEEE Trans on SMC，1998，28（1）：26-34.

[7]GLOVFER F. GA and tabu search： hybrids for optimization[J]. Computer Ops. Res.1995，22（1）：111-134.

[8]BACK T，FORGEL D，Michalewicz Zeds. Handbooks of Evolutionary computation[M]. New York：Oxford university Press，1997.

[9]SANKAR K.PAL，FELLEW C.A.MURTHY. GA for generation of class boundaries[J]. IEEE Trans on SMC-Part B：cybemetics，1998，28（6）：816-828.

[10]POTTS JC，et al. The Development and Evaluation of an Improved Genetic Algorithm Based on Migration and Artificial Selection[J]. IEEE Trans on SMC，1994，24（1）：73-86.

[11]RUDOLPH G. Convergence Analysis of Canonical GA[J]. IEEE Trans on Neural Networks，1994，5（1）：96-101.

[12]SRINIVAS M，PATNAIK LM. Adaptive Probabilities of Crossover and Mutation in GA[J]. IEEE Trans on SMC，1994，24（4）：656-667.

[13]王嵐. 基于自適應交叉和變異概率的遺傳算法收斂性研究[J]. 云南師范大學學報，2010，30（3）：32-37.

[14]明亮，王宇平. 關于一類遺傳算法收斂速度的研究[J]. 計算數學，2007，29（1）：15-26.

[15]應偉勤，李元香. 熱力學遺傳算法計算效率的改進[J]. 軟件學報，2008，19（7）：1613-1622

[16]喻壽益，鄺溯瓊. 保留精英遺傳算法收斂性和收斂速度的鞅方法分析[J]. 控制理論與應用，2010，27（7）：843-848.

[17]陳國良. 遺傳算法及其應用[M]. 北京：人民郵電出版社，1996.

[18]潘正君等. 演化計算[M]. 北京：清華大學出版社，1998.

[19]PIERRE S，LEGAULT G. An evolutionary approach for configuring economical Packet Switched computer networks[J].Artificial Intelligence in Engineering，1996，10（5）：127-134.

[20]肖宏峰，譚冠政. 基于單純形的小生境混合遺傳算法[J]. 小型微型計算機系統，2008，29（9）：1719-1725.

[21]孫艷豐，王眾托. 具有倒位算子的圖式定理. 系統工程與電子技術[J]，1995（10）.

[22]XIAO FANG Qi，FRARCESCO P. Theoretical Analysis of Evolutionary Algorithms with on Infinite Population Size in Continuous Space， Part I and PartII： Basic Properties of Selection and Mutation[J]. IEEE Trans on neural network， 1994，5 （1）：102～129.

[23]MICHALEWICZ Z. Genetic Algorithms+Data Structure=Evolution[M] Program. 2nd edition. Berlin：Springer—Verlag，1994.

[24]湯服成，薄運承. 模糊方程解的模糊尋優算法[J].高技術通訊，1998（70）：26～30.

[25]李茂軍，樊韶勝，童調生. 單親遺傳算法在模式聚類中的應用[J]. 模式識別與人工智能，1999，12（1）：32-37.

[26]惲為民，席裕庚. 遺傳算法收斂機理[J].控制理論與應用，1996，13（3）：297-304.