一种新的多目标优化遗传算法
|
摘要
为了更好的解决实际生活中的多目标优化问题,综合已有的理论和算法,提出了一种新的多目标优化遗传算法。在原有遗传算法基础上改进了遗传操作算子,并采用Pareto秩的方法来确定个体的适应度,为了使秩越小的个体被选择的概率越大,文中定义了一个与Pareto秩成反比例的函数。根据轮盘赌方法来进行选择操作、采用算数交叉算子和非均匀变异算子,并在运算过程增加了一个临时存储器,用来存放当前种群的Pareto最优解,将新加入的个体与当前临时存储器中的个体进行比较,将劣于新加入个体的解从临时存储器中删掉,始终保持这个存储器中的群体是最优的。为了提高算法在局部的搜索能力,在算法搜索过程中增加了一个黄金分割搜索,以提高算法的收敛速度,使其更快的逼近全局最优解。黄金分割搜索算法是经典的一维搜索方法,为了利用其良好的搜索能力,将其扩展到n维空间,并给出了具体算法步骤。通过对3个算例进行分析,检验了算法的有效性;任何一种算法都不是万能的,都是有其使用范围的,通过一个反例来说明给出的新的多目标遗传算法也不例外。最后通过Wolpert(沃伯特)和Macready(麦克雷)教授提出的无搜索和优化免费午餐定理(No Free Lunch定理)对这种观点加以说明,即算法在提高了对某类问题的解决速度的同时,必然降低了对另外一类问题的解决速度。
In order to solve multi-objective optimization problem in the real-life, according to the existing theory and algorithms, a new multi-objective genetic algorithms was presented. Based on the original genetic algorithm, to improve genetic operators, Pareto rank methods used to determine the individual fitness, the smaller the rank the greater the probability of the individual being selected, I define a function which is the inverse function of Pareto rank. According to roulette selection method, using arithmetic crossover and non-uniform mutation operator, in the computing process, increased a memory to store the current population of Pareto optimal solution, the new individuals was joined the temporary memory , compared with the current individual of memory, from the temporary memory, the individual which is worse than the new entrants’individual will be deleted. In the temporary memory, the solution of the individual is always optimal. To improve the local search capability of the algorithm, the artist applies a golden section search in the search process of the algorithm to improve the convergence speed. Golden section search is the classic one-dimensional search method, in order to use its good search capabilities; the artist extends it to the n-dimension of space, and gives the specific steps of the algorithm. According to the numerical examples, the artist tests the effectiveness of the algorithm; any of the algorithms are not omnipotent, which of all have the area, through a counter-example to illustrate the given new multi-objective genetic algorithm is no exception. Professor Wolpert and Macready presented a free search and optimization of free lunch theorem (No Free Lunch Theorem). According to the theorem , to support this view in the paper. The algorithm improved the speed of certain types of problem solving, while the other will inevitably reduce the settlement rate of a class of problems.
In order to solve multi-objective optimization problem in the real-life, according to the existing theory and algorithms, a new multi-objective genetic algorithms was presented. Based on the original genetic algorithm, to improve genetic operators, Pareto rank methods used to determine the individual fitness, the smaller the rank the greater the probability of the individual being selected, I define a function which is the inverse function of Pareto rank. According to roulette selection method, using arithmetic crossover and non-uniform mutation operator, in the computing process, increased a memory to store the current population of Pareto optimal solution, the new individuals was joined the temporary memory , compared with the current individual of memory, from the temporary memory, the individual which is worse than the new entrants’individual will be deleted. In the temporary memory, the solution of the individual is always optimal. To improve the local search capability of the algorithm, the artist applies a golden section search in the search process of the algorithm to improve the convergence speed. Golden section search is the classic one-dimensional search method, in order to use its good search capabilities; the artist extends it to the n-dimension of space, and gives the specific steps of the algorithm. According to the numerical examples, the artist tests the effectiveness of the algorithm; any of the algorithms are not omnipotent, which of all have the area, through a counter-example to illustrate the given new multi-objective genetic algorithm is no exception. Professor Wolpert and Macready presented a free search and optimization of free lunch theorem (No Free Lunch Theorem). According to the theorem , to support this view in the paper. The algorithm improved the speed of certain types of problem solving, while the other will inevitably reduce the settlement rate of a class of problems.
引文
[1]赖红松,董品杰,祝国瑞.求解多目标规划问题的Pareto多目标遗传算法[M].系统工程, 2003, 21(5): 24~27
[2]唐焕文,秦学志.实用最优化方法[M].大连:大连理工大学出版社,2004
[3]王宇平,焦永昌,张福顺.解多目标优化的均匀正交遗传算法[J].系统工程学报, 2003, 18(6): 481~486
[4]谢涛,陈火旺.多目标优化与决策问题的演化算法[J].中国工程科学, 2002, 4(2)
[5]崔逊学.多目标进化算法及其应用[M].北京:国防工业出版社, 2006
[6] Arturo Hemandez Aguirre, Salvador Botello Rioda, Carlos A. Use of muti-objective optimization concepts to handle constraints in single- objective optimization. Genetic and Computation Conference.IL, USA, 2003
[7] Horn J. Multi-criterion decision making. In: Back T ed. Handbook of Evolutionary Computation. Oxford: Oxford University Press. 1997
[8]刘勇,康立山,陈毓屏.非数值并行算法(第二册)[M].北京:科学出版社, 2003
[9]李敏强,寇纪淞,林丹等.遗传算法的基本原理与应用[M].北京:科学出版社, 2003
[10]周明,孙树栋.遗传算法原理及应用[M].国防工业出版社, 1999
[11]张文修,梁怡.遗传算法的数学基础[M].西安交通大学出版社, 2000
[12]陈国梁,王熙法,庄镇泉等.遗传算法及应用[M].人民邮电出版社, 1996
[13]姚文俊.遗传算法及其研究进展[J].计算机与数字工程, 2004, 4(32)
[14] Fonseca C.M, Fleming P.J. An overview of evolutionary algorithms in multi-objective optimization evolutionary computation. IEEE Transactions on Evolutionary Computation, 1995, 3(1): l~16
[15] Fonseca C.M, Fleming P.J. Genetic algorithms for multi-objective optimization: formulation, discussion and generalization. In: Proceedings of the 5th International Conference on Genetic Algorithms., 1993, 416~423
[16] Hajela-Lin C.Y. Genetic Structural Optimization, 1994,3: algorithms for multi-objective optional design, 102~117
[17] P.Hajela, C.Y Lin. Genetic search strearegies in multiciterion optimization. Vol.4, June 1992
[18] Eckart Zitzler, Evolutionary algorithms for multi-objective optimization: methods and applications. Ph.D dissertation, Computer Engineering and Networks Laboratory, Swiss Federal Institute of Technology Zurich, Swiss: 1999
[19] Zitziler E, Thiele L. Mufti-objective evolutionary algorithms:: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, 1999., 3(4): 257~271
[20] Zitzler E, Deb K, Thele L. Comparison of multi-objective evolutionary algorithms: empirical results [J]. Evolutionary Computation,, 2000, 8(2): l~24
[21] R Eberhart, J Kennedy. A new optimizer using particle swarm theory [J]. In: Proc of the 6th Int'1 Symposium on Micro Machine and Human Science. Piscataway. NJ: IEEE Service Center, 1995. 9~43
[22] Deb K. Multi-objective genetic algorithms: problem difficulties and construction of test problem [J]. Evolutionary Computation, 1999, 7(3): 205~230
[23] K.Deb, S.Agrawal, A.Pratab, T.Meyarivan. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In Proc. Conf. Parallel Problem Solving from Nature VI, 2000
[24]郑丽君.基于遗传算法的多目标优化与决策方法研究: [硕士学位论文].长沙:国防科学技术大学, 2003
[25]黄孔亮.多目标遗传算法研究与应用: [硕士学位论文].深圳:深圳大学, 2005
[26] J. Kennedy,R. Eberhart. Particle swarm optimization [J]. IEEE Int'1 Conf on Neural Networks, Perth, Australia, 1995
[27] K. C. Tan, T. H. Lee, E. F. Khor. Evolutionary algorithms with dynamic population size and local exploration for multi-objective optimization [J]. IEEE Transactions on Evolutionary Computation, 2001, 5(6): 565~587
[28]韩祯祥,文栓福.模拟进化优化方法及其应用遗传算法.计算机科学,1995,22 (2)
[29] Lino Costa, Pedro Oliveira. An elitist genetic algorithms for muti-objective optimization. Metaheuristics International Conference, Porto Portugal,, July 16-20, 2001
[30]雷英杰,张善文等Matlab遗传算法工具箱及应用[M].西安:西安电子科技大学出版社, 2005
[31]席裕庚,柴天佑.遗传算法综述.控制理论与应用, 1996
[32]王小平,曹立明.遗传算法:理论、应用与软件实现[M].西安:西安交通大学出版社, 2002
[33] C.M.Fonseca, P.J Fleming. On the performance assessment and comparison of stochastic multi-objectice optimizers. In Parallel Solving from Nature, H-M. Springer-Vorlag,, 1996
[34] M.P.Fourman. Compution of symbolic layout using genetic algorithms. In Proc. 1st Int. Conf. Genetic Algorithms, July 1985
[35]玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社, 2004
[36]唐焕文,秦学志.实用最优化方法[M].大连:大连理工大学出版社, 2004
[37]刘莉.混合遗传算法全局收敛性分析: [硕士学位论文].华中科技大学,概率论与数理统计, 2004
[38] Iosifescu M. Finite Markov Processes and Their Applications.Willey[J], 1980
[2]唐焕文,秦学志.实用最优化方法[M].大连:大连理工大学出版社,2004
[3]王宇平,焦永昌,张福顺.解多目标优化的均匀正交遗传算法[J].系统工程学报, 2003, 18(6): 481~486
[4]谢涛,陈火旺.多目标优化与决策问题的演化算法[J].中国工程科学, 2002, 4(2)
[5]崔逊学.多目标进化算法及其应用[M].北京:国防工业出版社, 2006
[6] Arturo Hemandez Aguirre, Salvador Botello Rioda, Carlos A. Use of muti-objective optimization concepts to handle constraints in single- objective optimization. Genetic and Computation Conference.IL, USA, 2003
[7] Horn J. Multi-criterion decision making. In: Back T ed. Handbook of Evolutionary Computation. Oxford: Oxford University Press. 1997
[8]刘勇,康立山,陈毓屏.非数值并行算法(第二册)[M].北京:科学出版社, 2003
[9]李敏强,寇纪淞,林丹等.遗传算法的基本原理与应用[M].北京:科学出版社, 2003
[10]周明,孙树栋.遗传算法原理及应用[M].国防工业出版社, 1999
[11]张文修,梁怡.遗传算法的数学基础[M].西安交通大学出版社, 2000
[12]陈国梁,王熙法,庄镇泉等.遗传算法及应用[M].人民邮电出版社, 1996
[13]姚文俊.遗传算法及其研究进展[J].计算机与数字工程, 2004, 4(32)
[14] Fonseca C.M, Fleming P.J. An overview of evolutionary algorithms in multi-objective optimization evolutionary computation. IEEE Transactions on Evolutionary Computation, 1995, 3(1): l~16
[15] Fonseca C.M, Fleming P.J. Genetic algorithms for multi-objective optimization: formulation, discussion and generalization. In: Proceedings of the 5th International Conference on Genetic Algorithms., 1993, 416~423
[16] Hajela-Lin C.Y. Genetic Structural Optimization, 1994,3: algorithms for multi-objective optional design, 102~117
[17] P.Hajela, C.Y Lin. Genetic search strearegies in multiciterion optimization. Vol.4, June 1992
[18] Eckart Zitzler, Evolutionary algorithms for multi-objective optimization: methods and applications. Ph.D dissertation, Computer Engineering and Networks Laboratory, Swiss Federal Institute of Technology Zurich, Swiss: 1999
[19] Zitziler E, Thiele L. Mufti-objective evolutionary algorithms:: a comparative case study and the strength Pareto approach. IEEE Transactions on Evolutionary Computation, 1999., 3(4): 257~271
[20] Zitzler E, Deb K, Thele L. Comparison of multi-objective evolutionary algorithms: empirical results [J]. Evolutionary Computation,, 2000, 8(2): l~24
[21] R Eberhart, J Kennedy. A new optimizer using particle swarm theory [J]. In: Proc of the 6th Int'1 Symposium on Micro Machine and Human Science. Piscataway. NJ: IEEE Service Center, 1995. 9~43
[22] Deb K. Multi-objective genetic algorithms: problem difficulties and construction of test problem [J]. Evolutionary Computation, 1999, 7(3): 205~230
[23] K.Deb, S.Agrawal, A.Pratab, T.Meyarivan. A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II. In Proc. Conf. Parallel Problem Solving from Nature VI, 2000
[24]郑丽君.基于遗传算法的多目标优化与决策方法研究: [硕士学位论文].长沙:国防科学技术大学, 2003
[25]黄孔亮.多目标遗传算法研究与应用: [硕士学位论文].深圳:深圳大学, 2005
[26] J. Kennedy,R. Eberhart. Particle swarm optimization [J]. IEEE Int'1 Conf on Neural Networks, Perth, Australia, 1995
[27] K. C. Tan, T. H. Lee, E. F. Khor. Evolutionary algorithms with dynamic population size and local exploration for multi-objective optimization [J]. IEEE Transactions on Evolutionary Computation, 2001, 5(6): 565~587
[28]韩祯祥,文栓福.模拟进化优化方法及其应用遗传算法.计算机科学,1995,22 (2)
[29] Lino Costa, Pedro Oliveira. An elitist genetic algorithms for muti-objective optimization. Metaheuristics International Conference, Porto Portugal,, July 16-20, 2001
[30]雷英杰,张善文等Matlab遗传算法工具箱及应用[M].西安:西安电子科技大学出版社, 2005
[31]席裕庚,柴天佑.遗传算法综述.控制理论与应用, 1996
[32]王小平,曹立明.遗传算法:理论、应用与软件实现[M].西安:西安交通大学出版社, 2002
[33] C.M.Fonseca, P.J Fleming. On the performance assessment and comparison of stochastic multi-objectice optimizers. In Parallel Solving from Nature, H-M. Springer-Vorlag,, 1996
[34] M.P.Fourman. Compution of symbolic layout using genetic algorithms. In Proc. 1st Int. Conf. Genetic Algorithms, July 1985
[35]玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社, 2004
[36]唐焕文,秦学志.实用最优化方法[M].大连:大连理工大学出版社, 2004
[37]刘莉.混合遗传算法全局收敛性分析: [硕士学位论文].华中科技大学,概率论与数理统计, 2004
[38] Iosifescu M. Finite Markov Processes and Their Applications.Willey[J], 1980