摘要
遗传算法是模拟自然界生物进化过程与机制求解问题的一类自组织与自适应的人工智能技术,已广泛应用于计算机科学、人工智能、信息技术及工程实践,但在算法性能方面还有不足之处,因而对其进行改进研究具有理论意义和实用价值。
国内外对遗传算法已经作过许多改进研究。目前,遗传算法的主要问题有两个:早熟收敛和开采能力差。相应的解决策略是:维持种群个体多样性和增强对局部领域的搜索开采能力。
针对遗传算法存在的问题,在总体解决思路的指引下,本文在三个方面对遗传算法进行改进研究。
一、将自适应策略引入种间竞争遗传算法。该方法不仅运用交叉算子和变异算子的自适应调节技术协调种内进化过程,而且通过种间竞争频率的自适应调节促进最优个体的生成。
二、将小生境技术和单纯形方法融入遗传算法中提出一种新的基于小生境的混合遗传算法。该方法一方面运用小生境技术增强遗传算法“探测”能力,另一方面通过使用单纯形搜索方法提高遗传算法的“开采”能力,从而有效消除遗传算法的两大弱点。
三、针对多模态函数优化问题中的小生境半径变化差异悬殊的特点,给出一种小生境半径自动确定的设计方法。算例仿真表明了该方法的有效性。
最后,应用改进的遗传算法求解供水泵站效率优化问题,验证了改进算法的有效性。
Genetic algorithm is an artificial intelligence technology of self-organization and adaptation, which imitates natural organisms' evolutionary process and mechanism to solve problems. Although the algorithm has been widely applied to the computer science, artificial intelligence, information technology and engineering projects, but it still suffers from performance deficiency. So more studies should be carried out to improve its performance because of its large value in theory research and practical application.
Presently, the algorithm still suffers from two drawbacks, premature convergence and weak exploitation capabilities. The effective ways to overcome such problems are to maintain the population diversity and enhance exploitation of local search domains.
By using the idea mentioned above to solve such problems, three modified schemes of genetic algorithm are proposed in this paper from following aspects:
1. A new method of connecting adaptive techniques with genetic algorithm based on the competition between populations is proposed. The method not only can coordinate evolutionary process inside each population by using an adaptive regulation of crossover and mutation operators, but also can advance the formation of-best design by using adaptive adjustment of the competition frequency between populations.
2. A new niche hybrid genetic algorithm is proposed, which organically merges the niche technique and simplex method into genetic algorithm. The proposed method not only makes the exploration capabilities of genetic algorithm stronger through niche techniques, but also has more powerful exploitation capabilities by using simplex method.
So it effectively alleviates the two major drawbacks of genetic algorithm.
3. A new technique for calculating niche radius automatically is proposed, according to the character of the large difference of the niche radii in multi-modal function optimization problems. A set of benchmark functions is used to demonstrate the validity of the method.
Finally, the first method mentioned above is applied to the efficiency optimization of a water-supply bumping station, and the simulation reveals its reliability.
引文
[1] Andre J, Siarry P, Dognon T. An improvement of the standard genetic algorithm fighting premature convergence in continuous optimization. Advances in Engineering Software, 2001, 32(1):49-60.
[2] 唐飞,腾弘飞.一种改进的遗传算法及其在布局优化中的应用.软件学报,1999,10(10):1096-1102.
[3] 何新贵,梁久祯.利用目标函数梯度的遗传算法.软件学报,2001,12(7):981-985.
[4] 陶卿,曹进德,孙德敏.基于约束区域神经网络的动态遗传算法.软件学报,2001,12(3):462-467.
[5] 李智勇,童调生.基于多种群进化小生境遗传算法的神经网络进化设计方法研究.控制与决策,2003,18(5):607-610.
[6] Potts J C, Giddens T D, Yadav S B. The Development and Evaluation of an Improved Genetic Algorithm Based on Migration and Artificial Selection. IEEE Transactions on systems, Man, and Cybernetics, 1994,24(1):73-86.
[7] Muhtenbein S V. Predictive models for breeder genetic algorithm: Continuous parameter optimization. Evolutionary Computation, 1993, 1 (1): 25-49.
[8] Back T. Selective pressure in evolutionary algorithms: A characterization of selection mechanisms. Proceedings of the 1st IEEE International Conference on Evolutionary Computation (ICEC94), Orlando, Dlorida IEEE Press, 1994, 57,62.
[9] Miller B L, Goldberg D E. Genetic algorithms, selection schemes, and the varying effects of noise. Journal of Evolutionary Computation, 1996, 4(2): 113-131.
[10] Thierens D, Goldberg D E, Perieira A G. Domina convergence, drift and the temporal-salience structure of problems. Proceedings of the 1998 IEEE Conference of Evolutionary Computation, New York, IEEE Press, 1998.
[11] Kuo T, Huang S Y. A Genetic Algorithm with Disruptive Selection. IEEE Transactions on Systems, Man, and Cybernetics, 1996, 26(2): 29-307.
[12] 吴少岩,许卓群.遗传算法中遗传算子的启发式构造策略.计算机学报,1998,21(11):1003-1008.
[13]Mmichhalewicz Z. Genetic Algorithm data Structure Evolution Programs. 2nd ed, New York, Springer-Verlag, 1994.
[14]杨启文,蒋静坪,张国宏.遗传算法优化速度的改进.软件学报.2001,12(2):270-275.
[15]张良杰,毛志宏,李衍达.遗传算法中突变算子的数学分析及改进策略.电子科学学刊,1996,18(6):590-595.
[16]侯广坤,骆江鹏.一种理想并行遗传算法模型.软件学报,1999,10(5):557-559.
[17]彭伟,卢锡城.一种函数优化问题的混合遗传算法.软件学报,1999,10(8):819-823.
[18]Chakraborty U K, Janikow C Z. An analysis of Gray versus binary encoding in genetic search, Information Sciences, 2003,156(3-4): 253-269.
[19]李敏强,寇纪淞,林丹,李书全.遗传算法的基本理论与应用.第1版,北京,科学出版社,2003.
[20]Sehraudolph N N, Belew R K. Dynamic parameter encoding for genetic algorithms. Machine Learning, 1992,9(1): 9-21.
[21]Yang X H, Yang Z F, Lu G H, Li J Q. A gray-encoded, hybrid-accelerated, genetic algorithm for global optimizations in dynamical systems. Communications in Nonlinear science and Numerical Simulation. 2004, in press.
[22]Lionel M, Laszlo N K, Christian F, Ivan M. Multi-criteria optimization of a single-cell oil production. European Journal of Operational Research, 2004,153(2): 360-369.
[23]Miller B, Goldberg D. Genetic algorithms, selection schemes, and the varying effects of noise. Evolutionary Computation, 1996,4(2):25-49.
[24]Aleksandra B D. Elite genetic algorithms with adaptive mutations for solving continuous optimization problems: application to modeting of the optical constants of solids. Optics Communications. 1998, 151: 147-159.
[25]De Jong K A, Spears W M. A formal analysis of the role of multi-point crossover in genetic algorithms. Annals of Mathematics and Artificial Intelligence, 1992,5(1): 1-26.
[26]Grefenstette J J. Optimization of control parameters for genetic algorithms. IEEE Transaction on Systems, Man, and Cybernetics, 1986,16(1): 122-128.
[27]Schaffer J D. A study of control parameters affecting on-line performance of genetic algorithms for function optimization. Schaffer J D. Proceedings of the Third International Conference on Genetic Algorithms (ICGA 3). San Mateo, CA. Morgan Kaufmann Publishers, 1989:51-60.
[28]符曦.系统最优化及控制.第1版,北京,机械工业出版社.1995:333-337.
[29]周北岳,郭观七.引入适应值曲面结构的小生境遗传算法初探.岳阳师范学院学报.2002,15(1):59-62.
[30]王小平,曹立明.遗传算法——理论、应用与软件实现.第1版,西安,西安交通大学出版社,2002.
[31]段玉倩,贺家李.遗传算法及其改进.电力系统自动化,1998,10(1):39-51.
[32]李大卫,王梦光.一种改进的混合遗传算法.信息与控制,1997,26(6):449-454.
[33]王宁,蔚承建,盛韶翰.基于嵌入混沌序列的遗传算法.系统工程理论与实践,1999(11):1-7.
[34]李建华,王孙安.最优家族遗传算法.西安交通大学学报,2004,38(1):77-80.
[35]陈建能.基于种间竞争的遗传算法的改进.福建农林大学学报,2003,32(1):127-129.
[36]Goldberg D E, Genetic Algorithm in Search, Optirnization and Machine Learning, Addisan-Wesley, New York, 1989.
[37]Berthiau G, Siarry P, A genetic algorithm for globally minimizing functions of several continuous variables. Sophia-Antipolis, Second International Conference on Meta-heuristies, France, 1997.
[38]Chelouah R, Siarry P. A continuous genetic algorithm designed for the global optimization of multimodal functions, Journal of Heuristics, 2000(6): 191-213.
[39]Michalewicz Z. Genetic algorithms + Data Structures=Evolution Programs, Springer-Verlag, Heidelberg, 1996.
[40]Chelouah R, Siarry P. Genetic and Nelder-Mead algorithms hybridized for a more accurate global optimization of continuous multi-minima functions, European
Journal of Operational Research, 2003 (148): 335-348.
[41] Siarry P, Pétrowski A, Bessaou M. A multi-population genetic algorithm aimed at multimodal optimization, Advances in Engineering Software, 2002,33(4): 207-213.
[42] Mahfoud S W. Niching Methods for Genetic Algorithm, Ph.D.dissertation, Univ. Of Illinois, Urbana-Champaign, 1995.
[43] Yin X., Germay N. A fast genetic algorithm with sharing scheme using cluster analysis methods in multimodal function optimization. Albrecht R F, Reeves C, Steele N C, Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms, in Innsbruek, Springer-Verlag, Berlin, Germany, 1993: 450-457.
[44] Prtrowski A, Crirod M. Genet: A classification tree for speeiation. Congress on Evolutionary Computation (CEC99), Proceedings of IEEE, 1999:204-211.
[45] Prtrowski A. A clearing procedure as a niching method for genetic algorithms, Proceedings of the 1996 IEEE International Conference on Evolutionary Computation, Nagoya, Japan, 1996: 798-803.
[46] Sareni B, Krhenbühl L. Fitness sharing and niching methods revisited, IEEE Transactions on Evolutionary Computation, 1998, 3(2): 97-106.
[47] Preuxa P, Taibi E G. Towards hybrid evolutionary algorithms, Intermational Transactions in Operational Research, 1999(6): 557-570.
[48] Mathias K E, Whitley L D, Stork C, Kusuma T. Staged hybrid genetic search for seismic data imaging, Proceedings of the First IEEE Conference on Evolutionary Computation, Orlando, FL, 1994: 356-361.
[49] Renders J M, Flasse S P. Hybrid method using genetic algorithms for the global optimization, IEEE Transactions on Systems, Man, and Cyhernetics, 1996, 26(2): 243-258.
[50] Nelder J A, Mead R. A simplex method for function minimization. The Computer Journal, 1995: 308-313.
[51] Glover F, Laguna M. Tabu Search, Kluwer, London, 1997.
[52] Smith S. The simplex method and evolutionary algorithms. Proceedings of 1998 IEEE International Conference on Evolutionary Computation, Prieataway, 1998: 799-804.
[53] 李敏强,寇纪淞.多模态函数优化的协同多群体遗传算法.自动化学报,2002,28(4):497-504.
[54] De Jong K A, An analysis of the behavior of a class of genetic adaptive systems. PhD Thesis. University of Michigan. Dissertation Abstracts International 1975, 36(10): 5140B.
[55] De Jong K A. Genetic algorithms: A 25 year perspective. Proceedings of the fifth International Conference on Genetic Algorithms, Los Altos, CA: Morgan Kaufmann Publishers, 1993.
[56] Mahfoud S W. Crowding and preselection revisited. Manner R, Manderiek B. Proceedings of the Second International Conference on Parallel Problem Solving from Nature. Berlin, Springer, 1992: 67-76.
[57] Mahfoud S W. Crossover interactions among niches. Proceedings of the First IEEE Conference on Evolutionary Computation, 1994(1): 188-193.
[58] Mengshoel O J, Goldberg D E. Probabilistie crowding: Deterministic crowding with probabilistic replacement. Banzhaf W. Proceedings of the Genetic and Evolutionary Computation Conference 1999 (GECCO-99). San Fransisco, CA. Morgan Kaufmann, 1999: 173-179.
[59] Goldberg D E, Richardson J. Genetic algorithm with shaging for multimodal function optimization. Proceedings of the Seeond International Conference on Genetic Algorithms, 1987: 41-49.
[60] Deb K, Goldberg D E. An investigation of niche and species formation in genetic function optimization. Proceedings of the Third International Conference on Genetic Algorithms, 1989:42-50.
[61] Goldberg D E, Deb K, Horn J. Massive multi-modality, deception, and genetic algorithms. Manner R, Manderick B, Proceedings of the Secand International Conference on Parallel Problem Solving from Nature, Berlin, Springer, 1992(2): 37-46.
[62] Lin C Y, Yang Y J. Cluster identification techniques in genetic algorithms for multimodal optimization. Computer-Aided Civil Infrastructure Engineering 1998, 13(1): 53-62.
[63] Beasley D, Bull D R, Martin R R. A sequential niche technique for multi-modal function optimization. Evolutionary Computation 1993, 1(2): 101-125.
[64] Lin C Y, Lou J Y, Yang Y J. Hybrid multi-modal optimization with clustering genetic strategies. Engineering Optimization 1998, (30): 263-280.
[65] Yin X, Germay N. A fast genetic algorithm with sharing scheme using duster analysis methods in multi-modal function optimization. Proceedings of the International conference on Artificial Neural Networks and Genetic Algorithms. 2002: 450-457.
[66] Beasley D, Bull D R, Martin R R. A sequential niche technique for multi-modal function optimization. Evolutionary Computation, 1993, 1(2): 101-125.
[67] Holland J H. Adaptation in natural and artificial systems. Arm Arbor: The University of Michigan Press, 1975.
[68] 廖莉,林家恒,张承慧.用遗传算法求解供水泵站的效率优化问题.中国工程科学,2002,4(9):54-58.
[69] 杨鹏,纪晓华,史旺旺.考虑变频调速时泵站优化调度的改进遗传算法.扬州大学学报,2002,5(1):67-70.
[70] 杨鹏,纪晓华,史旺旺.基于遗传算法的泵站优化调度.扬州大学学报,2001,4(3):72-74.
[71] 田一梅,李江涛,戴雄奇,李鸿.遗传算法在供水系统优化调度中的应用.中国给水排水,2001,17(12):63-65.
[72] 杜京义.供水泵站自动化系统及其应用.工矿自动化,2002(5):32-33.
[73] 杨海清,杨东勇,周向阳,陈思兴,袁南儿,金家钟.基于Host Link协议的制水过程微机监控工业网络系统的研制.计算机应用研究.2001,18:248-249,244.