自适应遗传算法的改进与研究
摘要
简单遗传算法作为一种启发式搜索算法,寻优理论还不完善。因此,在应用中常出现收敛过慢、稳定性差及早熟现象等问题,而现有的一些自适应遗传算法容易产生局部最优解。因此,对自适应遗传算法的进一步研究和探讨是很必要的。
针对简单遗传算法和现有的一些自适应遗传算法的缺陷,本文分析了种群“早熟”性能指标和计算量,并且判断种群当前适应度最大的那些个体是否重复或相互趋同,由此发展了一种新的种群“早熟”程度评价指标,结合自适应调整遗传算法的控制参数的思想,提出了一种改进的自适应遗传算法。作者希望本论文提出的新的自适应遗传算法,不仅能加快遗传进化速度,而且能增强遗传算法的全局收敛性能,从而得到满意的全局最优解。
本文首先介绍了遗传算法的背景、发展历程和应用,国内外研究现状,说明了研究的背景、目的和预期结果;其次介绍了简单遗传算法和几种改进自适应遗传算法,分析了现有的一些自适应遗传算法存在的缺陷,为下一步工作奠定基础;最后本文提出了一种新的判定种群“早熟”程度的方法,对算法的交叉概率和变异概率进行改进,设计实现了本文提出的新算法。实验结果说明新算法具有计算稳定性高、收敛速度快等特点,是一种性能良好的改进的自适应遗传算法。
Simple genetic algorithm is a heuristic searching algorithm. Its scheme of searching for the best result is not perfect. It has some shortages such as slow convergence, bad stability and premature phenomenon in application. Existing adaptive genetic algorithm has local optimization solution. Therefore, it is essential to implement a further research and discussion on the auto-adapted genetic algorithm.
In order to solve the disadvantages of simple genetic algorithms and existing adaptive genetic algorithms, we began with analyzing the performance index and the computation load of the population "premature", and then developed a new degree evaluating indicator of new population "premature". It is expected that the present paper will propose a new self-adapted genetic algorithm to reach the satisfactory globally optimal solution, which can not only speed up the genetic evolution speed but also strengthen the corresponding global convergence performance.
This article first introduced genetic algorithm's background, the development process and the application, the domestic and foreign present research situation, the research background, the research goal and the anticipated result. Next this thesis explained the simple heredity algorithm and several kinds of improved auto-adapted genetic algorithm, moreover analyzed some existing flaw in the auto-adapted genetic algorithm, laying the foundation for the later work. Finally this article proposed a new kind of determination population "precocious" degree method. The involved idea is making the improvement to the algorithm overlapping probability and the variation probability. Furthermore, it is successful for the design to realize the new algorithm this article proposed. The experimental result showed that the new improved auto-adapted genetic algorithm is of better performance such as good stability, quick convergent speed and so on.
针对简单遗传算法和现有的一些自适应遗传算法的缺陷,本文分析了种群“早熟”性能指标和计算量,并且判断种群当前适应度最大的那些个体是否重复或相互趋同,由此发展了一种新的种群“早熟”程度评价指标,结合自适应调整遗传算法的控制参数的思想,提出了一种改进的自适应遗传算法。作者希望本论文提出的新的自适应遗传算法,不仅能加快遗传进化速度,而且能增强遗传算法的全局收敛性能,从而得到满意的全局最优解。
本文首先介绍了遗传算法的背景、发展历程和应用,国内外研究现状,说明了研究的背景、目的和预期结果;其次介绍了简单遗传算法和几种改进自适应遗传算法,分析了现有的一些自适应遗传算法存在的缺陷,为下一步工作奠定基础;最后本文提出了一种新的判定种群“早熟”程度的方法,对算法的交叉概率和变异概率进行改进,设计实现了本文提出的新算法。实验结果说明新算法具有计算稳定性高、收敛速度快等特点,是一种性能良好的改进的自适应遗传算法。
Simple genetic algorithm is a heuristic searching algorithm. Its scheme of searching for the best result is not perfect. It has some shortages such as slow convergence, bad stability and premature phenomenon in application. Existing adaptive genetic algorithm has local optimization solution. Therefore, it is essential to implement a further research and discussion on the auto-adapted genetic algorithm.
In order to solve the disadvantages of simple genetic algorithms and existing adaptive genetic algorithms, we began with analyzing the performance index and the computation load of the population "premature", and then developed a new degree evaluating indicator of new population "premature". It is expected that the present paper will propose a new self-adapted genetic algorithm to reach the satisfactory globally optimal solution, which can not only speed up the genetic evolution speed but also strengthen the corresponding global convergence performance.
This article first introduced genetic algorithm's background, the development process and the application, the domestic and foreign present research situation, the research background, the research goal and the anticipated result. Next this thesis explained the simple heredity algorithm and several kinds of improved auto-adapted genetic algorithm, moreover analyzed some existing flaw in the auto-adapted genetic algorithm, laying the foundation for the later work. Finally this article proposed a new kind of determination population "precocious" degree method. The involved idea is making the improvement to the algorithm overlapping probability and the variation probability. Furthermore, it is successful for the design to realize the new algorithm this article proposed. The experimental result showed that the new improved auto-adapted genetic algorithm is of better performance such as good stability, quick convergent speed and so on.
引文
[1]De Jong K A.An Analysis of the Behavior of a Class of Genetic Adaptive Systems[J].Ph.D Dissertation,University of Michigan,No.76-9381,1975.
[2]Jomikow C Z,Michalewicz Z.An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithm[J].In:Proc.Of 4th Int.Confi.on Genetic Algorithms,Morgan Kaufmann,1991,31-36.
[3]Holland J H.Adaptation in Nature and Artificial Systems[M].MIT Press,1992.
[4]Goldberg D E.Genetic Algorithms in Search,Optimization and Machine Learning[M].Addison-Wesley,1989.
[5]Michalewicz Z,et.al.Genetic Algorithms and Optimal Control Problem.In:Proc.Of 29th IEEE Conf.on Decision and Control[J].1990.1664-1666.
[6]马钧水 刘贵忠 贾玉兰.《改进遗传算法搜索性能的大变异操作》[J].控制理论与应用,1998,15(3):404-408.
[7]许存禄.遗传算法的研究[D],硕士.兰州铁道学院,2002.
[8]Back T.The Interaction of Mutation Rate,Selection and Self-Adaptation within a Genetic Algorithm[J].In:Parallel Problem Solving from Nature 2,North Holland,1992,84-94
[9]Brindle A.Genetic Algorithms for Function Optimization[M].Ph.D Dissertation,University of Alberta,1981.
[10]Syswerda G.Uniform Crossover in Genetic Algorithm[J].In:Proc.Of 3rd Int.Conf.on Genetic Algorithms,Morgan Kaufmann,1989,2-9.
[11]Michalewicz Z.Genetic Algorithms Data Struction Evolution Program[M].Springer,1992.
[12]Michalewicz Z,et.al.A Modified Genetic Algorithm for Optimal Control Problems.Computers Math[J].Application,1992,23(12):83-94
[13]Davis L.Adapting Operator Probabilities in Genetic Algorithms[J].In:Proc.of 3rd In-tell.1990,2.189-214.
[14]Floudas C A,Pardalos P M.A Collection of Test Problems for Constrained Global Optimization Algorithms[M].LNCS,Vol.455,Springer-Verlag,1987.
[15]Hock W,Schittkowski K.Test Examples for Nonlinear Programming Codes[M].Lecture Notes in Economics and Mathematical Systems,Vol.187,Spring-Verlag,1981.
[16]陈国良,王煦法,庄镇泉等.遗传算法及其应用[M].北京:人民邮电出版社,1996
[17]张良安,郭大伟,徐乃平.遗传算法理论研究综述[J].西安电子科技大学学报,1998,25(3):363-368.
[18]Koza.J R.Genetic Programming Ⅱ,Automatic Discovery of Reusable Programs[M].MIT Press,1994.
[19]de Jong KA.An analysis of the behavior of a class of genetic adaptive systems[D].USA:University of Michigan,1975.
[20]Grefenstette J J.Optimization of control parameters for genetic algorithms[J].IEEE Trans on Systems,Man and Cybernetics,1986,16(1):122-128.
[21]Pham Q T.Competitive evolution:a natural approach to operator s election[A].In:Yao X,ed.Progress in Evolutionary Computation,Lecture Notes in Artificial Intelligence[C].Heidelberg:Springer Verlag,1995.49-60.
[22]Lis J.Parallel genetic algorithm with the dynamic control parameter[A].In:Proceedings of the 3 rd IEEE Conference on Evolutionary Computation[C].Nagoya:IEEE Press,1996,324-329.
[23]熊军 高敦堂 都思丹 沈庆宏.变异率和种群数目自适应的遗传算法[J].东南大学学报(自然科学版),2004,34(4):553-556.
[24]吴秋玲 杨启文.改进型自适应遗传变异算子[J].河海大学常州分校学报,2005,19(4):12-15.
[25]韩万林 张幼蒂.遗传算法的改进[J].中国矿业大学学报.2000,29(1):102-105.
[26]张晓馈,戴冠中,徐乃平.遗传算法种群多样性的分析研究[J].控制理论与应用,1998,15(1):17-23.
[27]潘伟 刁滑宗 井元伟.一种改进的实数自适应遗传算法[J].控制与决策,2006,21(7):792-796.
[28]金晶 苏勇:一种改进的自适应遗传算法[J].计算机工程与应用,2005,18:64-69.
[29]张思才 张方晓.一种遗传算法适应度函数的改进方法[J].计算机应用与软件,2006,23(2):108-110.
[30]黎钧琪 石国桢.遗传算法交叉率与变异率关系的研究[J].武汉理工大学学报(交通科学与工程版),2003,27(1):97-99.
[31]航宇 金晶 苏勇.自适应遗传算法交叉变异算子的改进[j].计算机工程与应用.2006,12,93-96.
[32]岳盼想 陈金梅 李法朝.带混合算子的自适应遗传算法的收敛性研究[J].河北科技大学学报,2006,27(4):272-276.
[33]刘德朋.基于变异率自适应调整的逆序遗传算法研究[J].杭州电子工业学院学报.2004,24(1):8-11.
[34]费烨 李楠楠 郑夕健 谢正义.基于结构和参数自适应的改进遗传算法[J].沈阳建筑大学学报,2006,22(2):338-340.
[35]张金华 胡铁松.基于种群差异度的自适应遗传算法[J].计算机工程与应用,2002,9:49-51.
[36]高汉平 康立山 杨族桥 肖小红.基于自适应杂交、变异率的演化算法[J].黄风师范学院学报,2003,23(3):57-60.
[37]胡觉亮 吴庆标.一种基于自适应混合遗传算法的非线性函数优化方法[J].高校应用数学学报A辑,2004,19:529-534.
[38]王正志,薄涛.进化计算[M].长沙:国防科技大学出版社,2000
[39]潘风萍 巩敦卫 孙晓燕 许世范.一种自适应遗传算法研究[J].中国矿业大学学报,2003,32(1):68-70.
[40]孙建永 申建中 徐宗本.一类自适应遗传算法[J].西安交通大学学报,2000,34(10):84-88.
[41]孙建永 申建中 徐宗本.一类自适应遗传算法的理论分析与数值模拟[J].西安交通大学学报,2000,34(12):84-87.
[42]房磊 张焕春 经亚枝.一种模糊自适应遗传算法[J].西安交通大学学报,2005,40(1):22-25.
[43]张春梅 行飞.用自适应的遗传算法求解大学课表安排问题[J].内蒙古大学学报(自然科学版),2002,33(4):459-464.
[44]张明辉 王尚锦.《自适应搜索的改进遗传算法及其应用》.西安交通大学学报,2002,36(3).226-129
[45]Srinivas M,Patnaik L.M.Adaptive Probabilities of Crossover and Mutation in Gas[J].IEEE Trans.On SMC,1994,24(4):pp.656-667.
[46]段玉倩,贺家李.遗传算法及其改进[J].电力系统及其自动化学报,1998,10(1):47-49
[47]任子武,伞冶.自适应遗传算法的改进及在系统辨识中应用研究[J].系统仿真学报.2006, 18(1):41-66.
[48]丁永生、任立红.人工免疫系统理论与应用[M].模式识别与人工智能,2000.
[2]Jomikow C Z,Michalewicz Z.An Experimental Comparison of Binary and Floating Point Representations in Genetic Algorithm[J].In:Proc.Of 4th Int.Confi.on Genetic Algorithms,Morgan Kaufmann,1991,31-36.
[3]Holland J H.Adaptation in Nature and Artificial Systems[M].MIT Press,1992.
[4]Goldberg D E.Genetic Algorithms in Search,Optimization and Machine Learning[M].Addison-Wesley,1989.
[5]Michalewicz Z,et.al.Genetic Algorithms and Optimal Control Problem.In:Proc.Of 29th IEEE Conf.on Decision and Control[J].1990.1664-1666.
[6]马钧水 刘贵忠 贾玉兰.《改进遗传算法搜索性能的大变异操作》[J].控制理论与应用,1998,15(3):404-408.
[7]许存禄.遗传算法的研究[D],硕士.兰州铁道学院,2002.
[8]Back T.The Interaction of Mutation Rate,Selection and Self-Adaptation within a Genetic Algorithm[J].In:Parallel Problem Solving from Nature 2,North Holland,1992,84-94
[9]Brindle A.Genetic Algorithms for Function Optimization[M].Ph.D Dissertation,University of Alberta,1981.
[10]Syswerda G.Uniform Crossover in Genetic Algorithm[J].In:Proc.Of 3rd Int.Conf.on Genetic Algorithms,Morgan Kaufmann,1989,2-9.
[11]Michalewicz Z.Genetic Algorithms Data Struction Evolution Program[M].Springer,1992.
[12]Michalewicz Z,et.al.A Modified Genetic Algorithm for Optimal Control Problems.Computers Math[J].Application,1992,23(12):83-94
[13]Davis L.Adapting Operator Probabilities in Genetic Algorithms[J].In:Proc.of 3rd In-tell.1990,2.189-214.
[14]Floudas C A,Pardalos P M.A Collection of Test Problems for Constrained Global Optimization Algorithms[M].LNCS,Vol.455,Springer-Verlag,1987.
[15]Hock W,Schittkowski K.Test Examples for Nonlinear Programming Codes[M].Lecture Notes in Economics and Mathematical Systems,Vol.187,Spring-Verlag,1981.
[16]陈国良,王煦法,庄镇泉等.遗传算法及其应用[M].北京:人民邮电出版社,1996
[17]张良安,郭大伟,徐乃平.遗传算法理论研究综述[J].西安电子科技大学学报,1998,25(3):363-368.
[18]Koza.J R.Genetic Programming Ⅱ,Automatic Discovery of Reusable Programs[M].MIT Press,1994.
[19]de Jong KA.An analysis of the behavior of a class of genetic adaptive systems[D].USA:University of Michigan,1975.
[20]Grefenstette J J.Optimization of control parameters for genetic algorithms[J].IEEE Trans on Systems,Man and Cybernetics,1986,16(1):122-128.
[21]Pham Q T.Competitive evolution:a natural approach to operator s election[A].In:Yao X,ed.Progress in Evolutionary Computation,Lecture Notes in Artificial Intelligence[C].Heidelberg:Springer Verlag,1995.49-60.
[22]Lis J.Parallel genetic algorithm with the dynamic control parameter[A].In:Proceedings of the 3 rd IEEE Conference on Evolutionary Computation[C].Nagoya:IEEE Press,1996,324-329.
[23]熊军 高敦堂 都思丹 沈庆宏.变异率和种群数目自适应的遗传算法[J].东南大学学报(自然科学版),2004,34(4):553-556.
[24]吴秋玲 杨启文.改进型自适应遗传变异算子[J].河海大学常州分校学报,2005,19(4):12-15.
[25]韩万林 张幼蒂.遗传算法的改进[J].中国矿业大学学报.2000,29(1):102-105.
[26]张晓馈,戴冠中,徐乃平.遗传算法种群多样性的分析研究[J].控制理论与应用,1998,15(1):17-23.
[27]潘伟 刁滑宗 井元伟.一种改进的实数自适应遗传算法[J].控制与决策,2006,21(7):792-796.
[28]金晶 苏勇:一种改进的自适应遗传算法[J].计算机工程与应用,2005,18:64-69.
[29]张思才 张方晓.一种遗传算法适应度函数的改进方法[J].计算机应用与软件,2006,23(2):108-110.
[30]黎钧琪 石国桢.遗传算法交叉率与变异率关系的研究[J].武汉理工大学学报(交通科学与工程版),2003,27(1):97-99.
[31]航宇 金晶 苏勇.自适应遗传算法交叉变异算子的改进[j].计算机工程与应用.2006,12,93-96.
[32]岳盼想 陈金梅 李法朝.带混合算子的自适应遗传算法的收敛性研究[J].河北科技大学学报,2006,27(4):272-276.
[33]刘德朋.基于变异率自适应调整的逆序遗传算法研究[J].杭州电子工业学院学报.2004,24(1):8-11.
[34]费烨 李楠楠 郑夕健 谢正义.基于结构和参数自适应的改进遗传算法[J].沈阳建筑大学学报,2006,22(2):338-340.
[35]张金华 胡铁松.基于种群差异度的自适应遗传算法[J].计算机工程与应用,2002,9:49-51.
[36]高汉平 康立山 杨族桥 肖小红.基于自适应杂交、变异率的演化算法[J].黄风师范学院学报,2003,23(3):57-60.
[37]胡觉亮 吴庆标.一种基于自适应混合遗传算法的非线性函数优化方法[J].高校应用数学学报A辑,2004,19:529-534.
[38]王正志,薄涛.进化计算[M].长沙:国防科技大学出版社,2000
[39]潘风萍 巩敦卫 孙晓燕 许世范.一种自适应遗传算法研究[J].中国矿业大学学报,2003,32(1):68-70.
[40]孙建永 申建中 徐宗本.一类自适应遗传算法[J].西安交通大学学报,2000,34(10):84-88.
[41]孙建永 申建中 徐宗本.一类自适应遗传算法的理论分析与数值模拟[J].西安交通大学学报,2000,34(12):84-87.
[42]房磊 张焕春 经亚枝.一种模糊自适应遗传算法[J].西安交通大学学报,2005,40(1):22-25.
[43]张春梅 行飞.用自适应的遗传算法求解大学课表安排问题[J].内蒙古大学学报(自然科学版),2002,33(4):459-464.
[44]张明辉 王尚锦.《自适应搜索的改进遗传算法及其应用》.西安交通大学学报,2002,36(3).226-129
[45]Srinivas M,Patnaik L.M.Adaptive Probabilities of Crossover and Mutation in Gas[J].IEEE Trans.On SMC,1994,24(4):pp.656-667.
[46]段玉倩,贺家李.遗传算法及其改进[J].电力系统及其自动化学报,1998,10(1):47-49
[47]任子武,伞冶.自适应遗传算法的改进及在系统辨识中应用研究[J].系统仿真学报.2006, 18(1):41-66.
[48]丁永生、任立红.人工免疫系统理论与应用[M].模式识别与人工智能,2000.