遺傳算法收斂效率研究

汪民樂?k

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

關(guān)鍵詞：遺傳算法；收斂效率；模式；自適應(yīng)選擇算子

中圖分類號：TP18文獻標(biāo)識碼：A

1引言

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

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

5結(jié)束語

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

參考文獻

[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，F(xiàn)ORGEL D，Michalewicz Zeds. Handbooks of Evolutionary computation[M]. New York：Oxford university Press，1997.

[9]SANKAR K.PAL，F(xiàn)ELLEW 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]王嵐. 基于自適應(yīng)交叉和變異概率的遺傳算法收斂性研究[J]. 云南師范大學(xué)學(xué)報，2010，30（3）：32-37.

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

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

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

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

[18]潘正君等. 演化計算[M]. 北京：清華大學(xué)出版社，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]. 小型微型計算機系統(tǒng)，2008，29（9）：1719-1725.

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

[22]XIAO FANG Qi，F(xiàn)RARCESCO 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]湯服成，薄運承. 模糊方程解的模糊尋優(yōu)算法[J].高技術(shù)通訊，1998（70）：26～30.

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

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