遗传算法收敛效率研究

汪民乐�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.