复合变异遗传算法的收敛性能研究
|
摘要
遗传算法是由美国自动控制论专家Holland于1975年提出的一种基于生物进化论及孟代尔基因遗传理论的搜索型优化算法,遗传算法主要是借鉴物种进化思想,从一组随机生成的初始可行种群出发,借助选择、交叉、变异等遗传操作,逐步逼近所研究问题的最优解。这种方法避开了所研究问题的复杂数学特征,对目标函数没有特殊的要求。但随着科学技术的发展,所研究问题规模的不断扩大,以及复杂度不断增加,对遗传算法求解质量和运行速度都提出了更高的要求,遗传算法在处理这些问题时的“未成熟”收敛性以及收敛解精度不高等方面的缺点暴露出来,该问题制约了遗传算法在复杂系统优化问题中的应用。本文针对遗传算法存在的这些问题作了相应的研究。
首先针对基本十进制编码遗传算法在求解复杂系统优化问题,尤其是寻优范围大、精度要求高的优化问题时经常出现的“未成熟”收敛及收敛解精度不高等缺点,结合生物进化的基本特征,从结构化和可视化的角度出发,提出一种变异准则函数,建立了一类基于复合变异的GA(简记为CM-GA)。进而,利用Markov链理论讨论了CM-GA的全局收敛性,并结合实例,比较和分析了CM-GA的收敛性能。针对基本二进制编码遗传算法运行过程中出现的解的范围变动比较大,不易于收敛到最优解的特点。本文结合生物进化的基本特征,从保护生物的优良特征的角度出发,提出了一种基于模式的复合变异策略,建立了一类基于模式变异的遗传算法(简记为SM-GA)。进而,利用Markov链理论讨论了SM-GA的全局收敛性,并结合实例,比较和分析了SM-GA的收敛性能。最后结合属性约简的特点,提出了一种基于模式变异遗传算法的属性约简算法。
Genetic Algorithm (GA for short), proposed by Holland in 1975, is a kind of search optimization algorithm based on the theory of evolution and the genetic mutation theory of Mendel. Genetic Algorithm, with the evolutionary theory and operation of selection, crossover and mutation, gradually approaching the optimal solution of the problem from a set of randomly initial feasible groups, The method has the feature of no consideration the complex mathematics characteristic of real problems and no restriction on objective function. However, with the development of science and technology, the scale of the problem expanding, and Increasing complexity, genetic Algorithm for the quality and speed have a higher demand. GA can not cover the shortcomings of poor convergence and premature phenomenon. The problem restricts greatly the application of GA to complex systems optimization problems. Considering this, we have the following findings.
Firstly, in view of the poor convergence and the low precision of convergence solution of B10GA, In feature of solving optimization problems of complex systems, especially the optimization range, high accuracy optimization problem. Combining with the essential, we propose the concept of mutation criteria function describing mutation characteristic from structural and visualized angle, and establish a genetic algorithm based on compound mutation (denoted by CM-GA, for short). Further, we discuss the global convergence of CM-GA by using the Markov chain theory, and analyze the performance of CM-GA through an example. Second, in the process of B2GA running, The scope of solutions can have a relatively large change and difficult to converge to the optimal solution. In this section, for protecting the fine features of biological and combining with the essential feature, we establish a genetic algorithm based on schema mutation (denoted by SM-GA, for short). Further, we discuss the global convergence of CM-GA by using the Markov chain theory, and analyze the performance of SM-GA through an example. Finally, we put forward a kind of attribute reduction algorithm based on schema mutation genetic algorithm combining with the feature of attribute reduction.
首先针对基本十进制编码遗传算法在求解复杂系统优化问题,尤其是寻优范围大、精度要求高的优化问题时经常出现的“未成熟”收敛及收敛解精度不高等缺点,结合生物进化的基本特征,从结构化和可视化的角度出发,提出一种变异准则函数,建立了一类基于复合变异的GA(简记为CM-GA)。进而,利用Markov链理论讨论了CM-GA的全局收敛性,并结合实例,比较和分析了CM-GA的收敛性能。针对基本二进制编码遗传算法运行过程中出现的解的范围变动比较大,不易于收敛到最优解的特点。本文结合生物进化的基本特征,从保护生物的优良特征的角度出发,提出了一种基于模式的复合变异策略,建立了一类基于模式变异的遗传算法(简记为SM-GA)。进而,利用Markov链理论讨论了SM-GA的全局收敛性,并结合实例,比较和分析了SM-GA的收敛性能。最后结合属性约简的特点,提出了一种基于模式变异遗传算法的属性约简算法。
Genetic Algorithm (GA for short), proposed by Holland in 1975, is a kind of search optimization algorithm based on the theory of evolution and the genetic mutation theory of Mendel. Genetic Algorithm, with the evolutionary theory and operation of selection, crossover and mutation, gradually approaching the optimal solution of the problem from a set of randomly initial feasible groups, The method has the feature of no consideration the complex mathematics characteristic of real problems and no restriction on objective function. However, with the development of science and technology, the scale of the problem expanding, and Increasing complexity, genetic Algorithm for the quality and speed have a higher demand. GA can not cover the shortcomings of poor convergence and premature phenomenon. The problem restricts greatly the application of GA to complex systems optimization problems. Considering this, we have the following findings.
Firstly, in view of the poor convergence and the low precision of convergence solution of B10GA, In feature of solving optimization problems of complex systems, especially the optimization range, high accuracy optimization problem. Combining with the essential, we propose the concept of mutation criteria function describing mutation characteristic from structural and visualized angle, and establish a genetic algorithm based on compound mutation (denoted by CM-GA, for short). Further, we discuss the global convergence of CM-GA by using the Markov chain theory, and analyze the performance of CM-GA through an example. Second, in the process of B2GA running, The scope of solutions can have a relatively large change and difficult to converge to the optimal solution. In this section, for protecting the fine features of biological and combining with the essential feature, we establish a genetic algorithm based on schema mutation (denoted by SM-GA, for short). Further, we discuss the global convergence of CM-GA by using the Markov chain theory, and analyze the performance of SM-GA through an example. Finally, we put forward a kind of attribute reduction algorithm based on schema mutation genetic algorithm combining with the feature of attribute reduction.
引文
[1]刘勇,康立山,陈毓屏.非数值并行算法(第二册)—遗传算法.北京:科学出版社, 1995
[2]雷亮,汪同庆,彭军.改进的自适应遗传算法应用研究.计算机科学, 2009, 36(6): 203-205
[3]陈国良.遗传算法及其应用[M].北京:科学出版社, 1993
[4] J. H. HOLLAND. Adaptation in Natural and Artificial Systems. MI: University of Michigan Press, 1975
[5] T. BAECK. The Interaction of Mutation Rate, Selection and Self-Adaptation within a Genetic Algorithm. Parallel Problem Solving from Nature. Amsterdam: Elsevier Science, 1992: 85-94
[6] H. MUHLENBEIN. Mutation and Hill climbing. Amsterdam: Elsevier Science, 1992: 15-25
[7]韩玲.经验遗传算法及其应用研究. [北京工业大学硕士论文]. 2004
[8]吴昊.并行遗传算法的研究与应用. [安徽大学硕士论文]. 2001
[9]韩炜,廖振鹏.关于遗传算法收敛性的注记.地震工程与工程振动, 1999, 19(4): 13-16
[10] H. ASOH, H. MUHLENBEIN. Parallel Problem Solving from Nature. Berlin: Springer- Verlag, 1994: 88-97
[11]杜文丽,原亮.遗传算法的特点及应用领域研究[J].科学信息(科学研究), 2008, 20(10): 30-32
[12] D. GOLDBERG. Genetic Algorithms in Search, Optimization and Machine Learning. Boston: Addison-Wesley Longman Publishing Company, 1989
[13]王志美,陈传仁.遗传算法理论及其应用发展[J].内蒙古石油化工, 2006, 23(9): 41-44
[14] H. AYTUG, G. J. KOEHLER. Stopping Criteria for Finite Length Genetic Algorithms. ORAS Journal of Computation, 1996, 8: 183-191
[15]宋小娜,朱齐亮.遗传算法在数据挖掘中的应用[J].科学信息(科学研究), 2008, 17: 400-404
[16] H. J. ZIMMERMANN. Fuzzy Set Theory and Its Applications. Second Edition. London: Kluwer Academic Publishers, 1991
[17] H. X. LI, C. L. PHILIP CHEN, H. P. HUANG. Fuzzy Neural Intelligent Systems. Boca Raton: CRC Press, 2001
[18]戴晓明,邹润民.混合并行遗传算法求解TSP问题.电子与信息学报, 2002, 24(10): 1424-1427
[19]赵宏立,庞小红,吴智铭.一种使用再编码染色体求解Job-Shop问题的并行遗传算法.机械科学与技术, 2004, 23(12): 1421-1425
[20]江雷.基于并行遗传算法的弹性TSP研究.微电子学与计算机, 2005, 22(8): 130-133
[21]李敏强.遗传算法的基本理论与应用[M].北京:科学出版社, 2002
[22] D. J. CAVICCHIO. Adaptive Search Using Simulated Evolution[D]. University of Michigan, 1970
[23]黄浩锋,陈少英.混合遗传算法概述[J].科学资讯, 2008, 5(12): 5-8
[24]高亮,王伟,吴涛.一种新的属性约简算法.计算机技术与发展, 2008, 18(5): 19-24
[25]黄聪明,陈湘秀.小生镜遗传算法的改进.北京理工大学学报, 2004, 24(8): 675-678
[26]杨尚达,李世平.遗传算法研究[J].兵工自动化, 2008, 9(27): 60-62
[27] H. AYTUG, G. J. KOEHLER. Stopping Criteria for Finite Length Genetic Algorithms. ORAS Journal of Computation, 1996, 8: 183-191
[28] H. AYTUG, S. BHATTACHARRYA, G. J. KOEHLER. A Markov China Analysis of Genetic Algorithms with Power of Cardinality Alphabets. European Journal of Operational Research, 1996, 96: 195-201
[29] J. J. BUCKLEY. Possibilistic Linear Programming with Triangular Fuzzy Numbers. Fuzzy Sets and Systems, 1988, 26(1): 135-138
[30] C. H. WANG, T. P. HONG. Integrating Fuzzy Knowledge by Genetic Slgorithms[J]. IEEE Trans. Evol. Compute, 1998, 2(4): 427-430
[31]黄友锐.十进制遗传算法的收敛性分析[J].淮南工业学院学报, 2001, 21(1): 28-31
[32]陈一虎,刘淳安.基于实数编码的遗传算法收敛性研究[J].西南民族大学学报, 2006, 32(4): 666-669
[33]曹慧卿,高峰.一种新的优化方法——遗传算法及其应用[J].机械设计与制造, 1997, 18(2): 24-25
[34]李培志,樊丁.基于实数编码的改进遗传算法研究[J].宇航计测技术, 2008, 28(1): 54-57
[35]张文修,梁怡.遗传算法的数学基础.第二版.西安交通大学出版社, 2003
[36]方兆本,缪柏其.随机过程[M].中国科学技术大学出版社, 1993
[37]苏日娜.基于二进制编码的遗传算法的研究[J].宁波工程学院学报, 2005, 2(17): 11-14
[38]赵青,杨倩.遗传算法三种编码策略的比较研究[J].重庆文理学院学报, 2008, 2(27): 67-70
[39]焦爱胜,谢娟文.遗传算法的改进与算法的收敛性分析.机械研究与应用, 2008, 21(4): 90-92
[40]唐少先,陈治.一种改进的遗传算法.计算机与现代化, 2008, 12(3): 12-15
[41]黄聪明,陈湘秀.小生镜遗传算法的改进.北京理工大学学报, 2004, 24(8): 675-678
[42]庄健,王孙安.自调节遗传算法的研究.系统仿真学报, 2003, 15(2): 281-283
[43] W. M. HUI, W. M. XI. The Analysis of Global Convergence and Computational Efficiency for Genetic algorithms. Journal of Control Theory and Applications, 1996, 13(4): 454-460
[44] E. ALBA, M. TOMASSINI. Parallelism and Evolutionary Algorithms. IEEE Transactions Evolutionary Computation, 2002, 6(5): 443-462
[45] X. H. HU, N. CERCONE. A rough set approach. Computational Intelligence, 1995, 11(2): 323-337
[46] J. H. DAI, Y. C. LI. An Algorithm for Reduction of Attributes in Decision System Based on Rough Set. Mini-Micro Systems, 2003, 3(3): 523-526
[47] K. Y. HU, Y. C. LU, C. Y. SHI. Feature Ranking in Rough Sets. AI Communications, 2003, 16: 41-50
[48]张丽.实数型遗传算法的研究.森林工程, 2005, 21(6): 50-52
[49]林丹,李敏等.基于实数编码的遗传算法的收敛性研究.计算机研究与发展, 2000, 37(11): 1321-1326
[50]巩敦卫,孙小燕,郭西进.一种新的优胜劣态遗传算法.控制与决策, 2002, 6: 908-912
[51]李裕奇,李永红.随机过程.国防工业出版社, 2003
[52]盛骤.概率论与数理统计[M].北京:高等教育出版社, 1989
[53] M. LOSIFESCU. Finite Markov Process and Their Applications [M]. Chichester: Wiley, 1980
[54]熊大国.随机过程理论与应用.北京:国防工业出版社, 1991
[2]雷亮,汪同庆,彭军.改进的自适应遗传算法应用研究.计算机科学, 2009, 36(6): 203-205
[3]陈国良.遗传算法及其应用[M].北京:科学出版社, 1993
[4] J. H. HOLLAND. Adaptation in Natural and Artificial Systems. MI: University of Michigan Press, 1975
[5] T. BAECK. The Interaction of Mutation Rate, Selection and Self-Adaptation within a Genetic Algorithm. Parallel Problem Solving from Nature. Amsterdam: Elsevier Science, 1992: 85-94
[6] H. MUHLENBEIN. Mutation and Hill climbing. Amsterdam: Elsevier Science, 1992: 15-25
[7]韩玲.经验遗传算法及其应用研究. [北京工业大学硕士论文]. 2004
[8]吴昊.并行遗传算法的研究与应用. [安徽大学硕士论文]. 2001
[9]韩炜,廖振鹏.关于遗传算法收敛性的注记.地震工程与工程振动, 1999, 19(4): 13-16
[10] H. ASOH, H. MUHLENBEIN. Parallel Problem Solving from Nature. Berlin: Springer- Verlag, 1994: 88-97
[11]杜文丽,原亮.遗传算法的特点及应用领域研究[J].科学信息(科学研究), 2008, 20(10): 30-32
[12] D. GOLDBERG. Genetic Algorithms in Search, Optimization and Machine Learning. Boston: Addison-Wesley Longman Publishing Company, 1989
[13]王志美,陈传仁.遗传算法理论及其应用发展[J].内蒙古石油化工, 2006, 23(9): 41-44
[14] H. AYTUG, G. J. KOEHLER. Stopping Criteria for Finite Length Genetic Algorithms. ORAS Journal of Computation, 1996, 8: 183-191
[15]宋小娜,朱齐亮.遗传算法在数据挖掘中的应用[J].科学信息(科学研究), 2008, 17: 400-404
[16] H. J. ZIMMERMANN. Fuzzy Set Theory and Its Applications. Second Edition. London: Kluwer Academic Publishers, 1991
[17] H. X. LI, C. L. PHILIP CHEN, H. P. HUANG. Fuzzy Neural Intelligent Systems. Boca Raton: CRC Press, 2001
[18]戴晓明,邹润民.混合并行遗传算法求解TSP问题.电子与信息学报, 2002, 24(10): 1424-1427
[19]赵宏立,庞小红,吴智铭.一种使用再编码染色体求解Job-Shop问题的并行遗传算法.机械科学与技术, 2004, 23(12): 1421-1425
[20]江雷.基于并行遗传算法的弹性TSP研究.微电子学与计算机, 2005, 22(8): 130-133
[21]李敏强.遗传算法的基本理论与应用[M].北京:科学出版社, 2002
[22] D. J. CAVICCHIO. Adaptive Search Using Simulated Evolution[D]. University of Michigan, 1970
[23]黄浩锋,陈少英.混合遗传算法概述[J].科学资讯, 2008, 5(12): 5-8
[24]高亮,王伟,吴涛.一种新的属性约简算法.计算机技术与发展, 2008, 18(5): 19-24
[25]黄聪明,陈湘秀.小生镜遗传算法的改进.北京理工大学学报, 2004, 24(8): 675-678
[26]杨尚达,李世平.遗传算法研究[J].兵工自动化, 2008, 9(27): 60-62
[27] H. AYTUG, G. J. KOEHLER. Stopping Criteria for Finite Length Genetic Algorithms. ORAS Journal of Computation, 1996, 8: 183-191
[28] H. AYTUG, S. BHATTACHARRYA, G. J. KOEHLER. A Markov China Analysis of Genetic Algorithms with Power of Cardinality Alphabets. European Journal of Operational Research, 1996, 96: 195-201
[29] J. J. BUCKLEY. Possibilistic Linear Programming with Triangular Fuzzy Numbers. Fuzzy Sets and Systems, 1988, 26(1): 135-138
[30] C. H. WANG, T. P. HONG. Integrating Fuzzy Knowledge by Genetic Slgorithms[J]. IEEE Trans. Evol. Compute, 1998, 2(4): 427-430
[31]黄友锐.十进制遗传算法的收敛性分析[J].淮南工业学院学报, 2001, 21(1): 28-31
[32]陈一虎,刘淳安.基于实数编码的遗传算法收敛性研究[J].西南民族大学学报, 2006, 32(4): 666-669
[33]曹慧卿,高峰.一种新的优化方法——遗传算法及其应用[J].机械设计与制造, 1997, 18(2): 24-25
[34]李培志,樊丁.基于实数编码的改进遗传算法研究[J].宇航计测技术, 2008, 28(1): 54-57
[35]张文修,梁怡.遗传算法的数学基础.第二版.西安交通大学出版社, 2003
[36]方兆本,缪柏其.随机过程[M].中国科学技术大学出版社, 1993
[37]苏日娜.基于二进制编码的遗传算法的研究[J].宁波工程学院学报, 2005, 2(17): 11-14
[38]赵青,杨倩.遗传算法三种编码策略的比较研究[J].重庆文理学院学报, 2008, 2(27): 67-70
[39]焦爱胜,谢娟文.遗传算法的改进与算法的收敛性分析.机械研究与应用, 2008, 21(4): 90-92
[40]唐少先,陈治.一种改进的遗传算法.计算机与现代化, 2008, 12(3): 12-15
[41]黄聪明,陈湘秀.小生镜遗传算法的改进.北京理工大学学报, 2004, 24(8): 675-678
[42]庄健,王孙安.自调节遗传算法的研究.系统仿真学报, 2003, 15(2): 281-283
[43] W. M. HUI, W. M. XI. The Analysis of Global Convergence and Computational Efficiency for Genetic algorithms. Journal of Control Theory and Applications, 1996, 13(4): 454-460
[44] E. ALBA, M. TOMASSINI. Parallelism and Evolutionary Algorithms. IEEE Transactions Evolutionary Computation, 2002, 6(5): 443-462
[45] X. H. HU, N. CERCONE. A rough set approach. Computational Intelligence, 1995, 11(2): 323-337
[46] J. H. DAI, Y. C. LI. An Algorithm for Reduction of Attributes in Decision System Based on Rough Set. Mini-Micro Systems, 2003, 3(3): 523-526
[47] K. Y. HU, Y. C. LU, C. Y. SHI. Feature Ranking in Rough Sets. AI Communications, 2003, 16: 41-50
[48]张丽.实数型遗传算法的研究.森林工程, 2005, 21(6): 50-52
[49]林丹,李敏等.基于实数编码的遗传算法的收敛性研究.计算机研究与发展, 2000, 37(11): 1321-1326
[50]巩敦卫,孙小燕,郭西进.一种新的优胜劣态遗传算法.控制与决策, 2002, 6: 908-912
[51]李裕奇,李永红.随机过程.国防工业出版社, 2003
[52]盛骤.概率论与数理统计[M].北京:高等教育出版社, 1989
[53] M. LOSIFESCU. Finite Markov Process and Their Applications [M]. Chichester: Wiley, 1980
[54]熊大国.随机过程理论与应用.北京:国防工业出版社, 1991