基于群智能及博弈策略的多目标优化算法研究
|
摘要
多目标进化算法(MOEA)是模拟生物进化理论而产生的高性能、自组织、高鲁棒性的多目标优化问题求解方法。MOEA对Pareto前沿的形状不敏感,算法一次运行产生多个Pareto非支配解。正因为这些优点,MOEA已经成为解决多目标优化问题的主流方法。当前MOEA主要依靠非支配排序推动种群朝Pareto前沿进化,在算法的后期非支配排序的推力不足,使得算法的全局寻优能力较弱。
本文旨在深入探索和研究多目标进化算法蕴含的优化原理和进化机制,并探索将贝叶斯博弈模型引入到多目标进化算法中,以提高多目标遗传算法的全局寻优能力。本文的主要研究工作包括以下几个方面：
(1)讨论了群智能算法的优化原理和进化算法在解决多目标优化问题中的求解模型,介绍了博弈论的基础知识,并对多目标进化算法的收敛性和多样性进行了研究；
(2)提出了一种基于贝叶斯博弈模型的多目标遗传算法。将每个待优化目标视为一个博弈参与者,通过多个参与者的博弈共同拉动种群朝Pareto前沿搜索,使得算法表现出更好的收敛性和多样性。本文从理论上分析了基于贝叶斯博弈模型的多目标遗传算法的收敛性,并对算法的性能进行了对比验证,仿真实验结果表明算法在收敛性和解得分布性上优于NSGA-Ⅱ算法。
(3)针对网格调度的特点,本文提出了基于SBG-MOGA的网格调度求解模型。本文对网格调度问题做了详细描述,建立了多目标优化问题模型,设计了符合网格调度问题特点的编码方式、精英集合以及遗传操作。最后通过仿真实验,验证了算法的收敛性和可行性。
Multi-objective evolutionary algorithms (MOEAs) are proposed from simulating the biological evolutionary theory. These algorithms are.high-performance,self-organization and robustness.MOEAs are not sensitive to the figure of Pareto front and can get lots of results implemented once.Beacause of their advantage, MOEAs have been the mainstream on solving multi-objectives optimization problems.Conventional MOGAs use non-dominated sorting methods to push the population to move toward the real Pareto front.This approach has a good performance at earlier stages of the evolution, however it becomes hypodynamic at the later stages.
The objective of this study is to explore and research the optimization principle and the evolutionary mechanism of MOEAs.In this paper we add the static Bayesian game strategy into MOGA and propose a novel multi-objective genetic algorithm(SBG-MOGA),which improves the optimition ability at the later stages of algorithm.The study focuses on the following aspects:
(1)This article discusses the principles of swarm intelligence algorithm optimization and the solution model of multi-objective evolutionary algorithm,and then describes the game theory. And also multi-objective evolutionary algorithm convergence and diversity has been studied.
(2)Multi-Objective Genetic Algorithm Based on Static Bayesian Game Strategy (SBG-MOGA) has been introduced.In SBG-MOGA, a objective that needs to optimize is regarded as a participant of a game.The game strategy in SBG-MOGA generates a tensile force over the population and this will obtain a better multi-objective optimization performance.The convergence of SBG-MOGA has been proofed in the paper. Moreover, the algorithm is verified by several simulation experiments and its performance is tested by different benchmark functions.
(3)According to the characteristic of grid scheduling,this article proposed a grid scheduling solution model based on SBG-MOGA. In the paper, we gave a detailed description of scheduling problems on the grid, established the multi-objective optimization model of grid scheduling problem,and then improved the SBG-MOGA in order solving Grid scheduling problem.Finally, simulation experiments were given to verify the convergence and feasibility.
本文旨在深入探索和研究多目标进化算法蕴含的优化原理和进化机制,并探索将贝叶斯博弈模型引入到多目标进化算法中,以提高多目标遗传算法的全局寻优能力。本文的主要研究工作包括以下几个方面：
(1)讨论了群智能算法的优化原理和进化算法在解决多目标优化问题中的求解模型,介绍了博弈论的基础知识,并对多目标进化算法的收敛性和多样性进行了研究；
(2)提出了一种基于贝叶斯博弈模型的多目标遗传算法。将每个待优化目标视为一个博弈参与者,通过多个参与者的博弈共同拉动种群朝Pareto前沿搜索,使得算法表现出更好的收敛性和多样性。本文从理论上分析了基于贝叶斯博弈模型的多目标遗传算法的收敛性,并对算法的性能进行了对比验证,仿真实验结果表明算法在收敛性和解得分布性上优于NSGA-Ⅱ算法。
(3)针对网格调度的特点,本文提出了基于SBG-MOGA的网格调度求解模型。本文对网格调度问题做了详细描述,建立了多目标优化问题模型,设计了符合网格调度问题特点的编码方式、精英集合以及遗传操作。最后通过仿真实验,验证了算法的收敛性和可行性。
Multi-objective evolutionary algorithms (MOEAs) are proposed from simulating the biological evolutionary theory. These algorithms are.high-performance,self-organization and robustness.MOEAs are not sensitive to the figure of Pareto front and can get lots of results implemented once.Beacause of their advantage, MOEAs have been the mainstream on solving multi-objectives optimization problems.Conventional MOGAs use non-dominated sorting methods to push the population to move toward the real Pareto front.This approach has a good performance at earlier stages of the evolution, however it becomes hypodynamic at the later stages.
The objective of this study is to explore and research the optimization principle and the evolutionary mechanism of MOEAs.In this paper we add the static Bayesian game strategy into MOGA and propose a novel multi-objective genetic algorithm(SBG-MOGA),which improves the optimition ability at the later stages of algorithm.The study focuses on the following aspects:
(1)This article discusses the principles of swarm intelligence algorithm optimization and the solution model of multi-objective evolutionary algorithm,and then describes the game theory. And also multi-objective evolutionary algorithm convergence and diversity has been studied.
(2)Multi-Objective Genetic Algorithm Based on Static Bayesian Game Strategy (SBG-MOGA) has been introduced.In SBG-MOGA, a objective that needs to optimize is regarded as a participant of a game.The game strategy in SBG-MOGA generates a tensile force over the population and this will obtain a better multi-objective optimization performance.The convergence of SBG-MOGA has been proofed in the paper. Moreover, the algorithm is verified by several simulation experiments and its performance is tested by different benchmark functions.
(3)According to the characteristic of grid scheduling,this article proposed a grid scheduling solution model based on SBG-MOGA. In the paper, we gave a detailed description of scheduling problems on the grid, established the multi-objective optimization model of grid scheduling problem,and then improved the SBG-MOGA in order solving Grid scheduling problem.Finally, simulation experiments were given to verify the convergence and feasibility.
引文
[1]公茂果,焦李成,杨咚咚等.进化多目标优化算法研究.软件学报,2009,20(2)：271-289
[2]Coello Coello C.A.Evolutionary multi-objective optimization:a historical view of the field.Computational Intelligence Magazine,IEEE,2006,28-36
[3]William B W. The Papers of Benjamin Franklin.New Haven:Yale University Press,1975,299-300
[4]Rosenberg R S.Simulation of genetic populations with biochemical properties. Michigan:University of Michigan,1967,25-38
[5]N.Srinivas, K.Deb.Multiobjective optimization using nondominated sorting in genetic algorithms.Evolutionary Computation,1994,2(3):221-248
[6]J.Horn,N.Nafpliotis,D.E.Goldberg.A niched pareto genetic algorithm for multiobjective optimization.In Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, Piscataway, New Jersey,1994,1:82-87
[7]E.Zitzler, M.Laumanns,L.Thiele.SPEA2:Improving the strength pareto evolutionary algorithm. In:K. Giannakoglou editor, EUROGEN 2001. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems,2002,95-100
[8]K.Deb,S.Agrawal,A.Pratab, et al.A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization:NSGA-Ⅱ.Proceedings of the Parallel Problem Solving from Nature VI Conference.Paris,France,2000,849-858
[9]J.D.Knowles,D.W. Corne.Approximating the nondominated front using the pareto archived evolution strategy. Evolutionary Computation,2000,8(2): 149-172
[10]C.M. Fonseca, P. J. Fleming. Genetic algorithms for multiobjective Optimization:Formulation,discussion and generalization.In:Stephanie Forrest, Proceedings of the Fifth International Conference on Genetic Algorithms,1993, 416-423
[11]Kuhn H W, Tucker A W. Nonlinear programming,Proceedings of the second Berkeley Symposium on Mathematical Statistical and Probability. California: Univ. of California Press,1951,481-491
[12]Zhiyong Li,Rudolph.A framework of quantum-inspired multi-objective evolutionary algorithms and its convergence condition.Proceedings of the 9th annual conference on Genetic and evolutionary computation, London, England, 2007,908-908
[13]唐欢容,蒋浩,郑金华.量子多目标进化算法研究.计算机土程与应用,2007,43(13)：45-48
[14]李阳阳,焦李成.量子免疫克隆多目标优化算法.电子与信息学报,2008,30(6)：1367-1371
[15]张勇德,黄莎白.多目标优化问题的蚁群算法研究.控制与决策,2005,20(2)：170-173
[16]Carlo R R, Prospero C N.An effective use of crowding distance in multi objective particle swarm optimization.In:Proc.of the Genetic and Evolutionary Computation Conference.Washington DC,USA,2005,257-264
[17]Margarita R S,Carlos A C.Improving PSO-based multi-objective optimization using crowding, mutation and ε-dominance.In:Proc.of the Third Int.Conf. on Evolutionary Multi-Criterion Optimization.Mexico,2008,505-519
[18]Tapabrata R, Liew K M.A swarm metaphor for multi objective design optimization.Engineering Optimization,2002,34(2):141-153
[19]崔逊学,林闯.一种基于偏好的多目标调和遗传算法.软件学报,2005,16(5)：761-770
[20]崔逊学.多目标进化算法及其应用.北京：国防工业出版社,2006
[21]石川,李清勇,史忠植.一种快速的基于占优树的多目标进化算法.软件学报,2007,18(3)：505-516
[22]Agapie Alexandru, Rudolph Gunter. Convergence Properties of Some Multi-Objective Evolutionary Algorithms.In the 2000 Congress on Evolutionary Computation (CEC 2000),IEEE,Piscataway (NJ),2000
[23]Zhiyong Li,Rudolph.Convergence performance comparison of quantum-inspired multi-objective evolutionary algorithms.Proceedings of the International Conference,Bio-Inspired Computing-Theories and Applications BIC-TA 2007 Zhengzhou, China,2009,57(11-12):1843-1854
[24]Eberhart R C,Shi Y. Particle swarm optimization:developments,applications and resources.In:Proc.of the Congress on Evolutionary Computation.Seoul, Korea,2001,81-86
[25]Bartz B T, Limbourg P, Parsopoulos K E,et al.Particle swarm optimizers for pareto optimization with enhanced archiving techniques.In:Proc.of the Congress on Evolutionary Computation.Canberra, Australia,2003,1780-1787
[26]Rosenberg R S.Simulation of genetic populations with biochemical properties. Michigan:University of Michigan,1967,25-38
[27]Carlos A C,David A V, Gary B L.Evolutionary Algorithms for Solving Multi-Objective Problems.New York:Kluwer Academic Publishers,2002,66-67
[28]Colorni A,Dorigo M,Maniezzo V. Disttributed optimization by ant colonies.In: Proc.of European Conf. Artificial Life.Pans,France,1991,134-142
[29]彭喜元,彭宇,戴毓丰.群智能理论及应用.电子学报,2003,31(12)：1982-1988
[30]Kennedy J,Eberhart R C.Particle swarm optimization.In:Proc.of Int. Conf. on Neural Networks.Perth,Australia,1995,1942-1948
[31]Laura D, Mihai O. What Else Is the Evolution of PSO Telling Us.Journal of Artificial Evolution and Applications,2008,8(2):1-12
[32]Julio E A B,Richard M E,Jonathan E F.A MOPSO algorithm based exclusively on pareto dominance concepts.In:Proc.of the Third Int.Conf. on Evolutionary Multi-Criterion Optimization.Mexico,USA,2005,459-473
[33]Jonathan E F, Sameer S.A multi-objective algorithm based upon particle swarm optimisation,an efficient datastructure and turbulence.In:Proc.of the Workshop on Computational Intelligence.Birmingham,England,2002,37-44
[34]张葛祥,李娜,金炜东等.一种新量子遗传算法及其应用.电子学报,2004,32(3)：476-479.
[35]王凌,吴昊,唐芳等.混合量子遗传算法及其性能分析.控制与决策,2005,20(2)：156-160
[36]张维迎.博弈论与经济信息学.上海人民出版社,2004,106-135
[37]Tadahiko M,Hisao I.MOGA:Multi-Objective Genetic Algorithms.In:Proc.of Int.Conf. on Evolutionary Computation.Perth,Australia,1995,289-294
[38]Zitzler E,Thiele L.Multiobjective evolutionary algorithms:A comparative case study and the strength pareto approach.IEEE Transactions on Evolutionary Computation,1999,3(4):257-271
[39]崔逊学,李淼等,基于免疫原理的多目标进化算法群体多样性研究.模式识别与人工智能,2001,14(3)：291-296
[40]Parsopoulos K E, Vrahatis M N.Particle Swarm Optimization Method in Multiobjective Problems.In:Proc.of the Congress on Evolutionary Computation. Honolulu,USA,2002,46-53
[41]Parsopoulos K E,Tasoulis D K, Vrahatis M N.Multiobjective optimization using parallel vector evaluated particle swarm optimization.In:Proc.of Int.Conf. on Artificial Intelligence and Applications.Innsbruck, Austria,2004,823-828
[42]Foster T,Kesselman C,Tuecke S.The anatomy of the Grid:Enabling scalable virtual organizations.International Journal of Supercomputer Application,2001, 15(3):200-222
[43]杜晓丽,蒋昌俊,徐国荣等.一种基于模糊聚类的网格DAG任务图调度算法.软件学报,2006,17(11)：2277-2288.
[44]徐志伟,冯百明,李伟.网络计算技术.电子工业出版社,2004,93-124
[45]王树鹏,云晓春,余翔湛.基于生存性和Makespan的多目标网格任务调度算法研究.通信学报,2006,27(2)：42-49
[46]Holland J.Adaptation in natural and artificial systems.Michigan:The University of Michigan,1975,45-87
[2]Coello Coello C.A.Evolutionary multi-objective optimization:a historical view of the field.Computational Intelligence Magazine,IEEE,2006,28-36
[3]William B W. The Papers of Benjamin Franklin.New Haven:Yale University Press,1975,299-300
[4]Rosenberg R S.Simulation of genetic populations with biochemical properties. Michigan:University of Michigan,1967,25-38
[5]N.Srinivas, K.Deb.Multiobjective optimization using nondominated sorting in genetic algorithms.Evolutionary Computation,1994,2(3):221-248
[6]J.Horn,N.Nafpliotis,D.E.Goldberg.A niched pareto genetic algorithm for multiobjective optimization.In Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, Piscataway, New Jersey,1994,1:82-87
[7]E.Zitzler, M.Laumanns,L.Thiele.SPEA2:Improving the strength pareto evolutionary algorithm. In:K. Giannakoglou editor, EUROGEN 2001. Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems,2002,95-100
[8]K.Deb,S.Agrawal,A.Pratab, et al.A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization:NSGA-Ⅱ.Proceedings of the Parallel Problem Solving from Nature VI Conference.Paris,France,2000,849-858
[9]J.D.Knowles,D.W. Corne.Approximating the nondominated front using the pareto archived evolution strategy. Evolutionary Computation,2000,8(2): 149-172
[10]C.M. Fonseca, P. J. Fleming. Genetic algorithms for multiobjective Optimization:Formulation,discussion and generalization.In:Stephanie Forrest, Proceedings of the Fifth International Conference on Genetic Algorithms,1993, 416-423
[11]Kuhn H W, Tucker A W. Nonlinear programming,Proceedings of the second Berkeley Symposium on Mathematical Statistical and Probability. California: Univ. of California Press,1951,481-491
[12]Zhiyong Li,Rudolph.A framework of quantum-inspired multi-objective evolutionary algorithms and its convergence condition.Proceedings of the 9th annual conference on Genetic and evolutionary computation, London, England, 2007,908-908
[13]唐欢容,蒋浩,郑金华.量子多目标进化算法研究.计算机土程与应用,2007,43(13)：45-48
[14]李阳阳,焦李成.量子免疫克隆多目标优化算法.电子与信息学报,2008,30(6)：1367-1371
[15]张勇德,黄莎白.多目标优化问题的蚁群算法研究.控制与决策,2005,20(2)：170-173
[16]Carlo R R, Prospero C N.An effective use of crowding distance in multi objective particle swarm optimization.In:Proc.of the Genetic and Evolutionary Computation Conference.Washington DC,USA,2005,257-264
[17]Margarita R S,Carlos A C.Improving PSO-based multi-objective optimization using crowding, mutation and ε-dominance.In:Proc.of the Third Int.Conf. on Evolutionary Multi-Criterion Optimization.Mexico,2008,505-519
[18]Tapabrata R, Liew K M.A swarm metaphor for multi objective design optimization.Engineering Optimization,2002,34(2):141-153
[19]崔逊学,林闯.一种基于偏好的多目标调和遗传算法.软件学报,2005,16(5)：761-770
[20]崔逊学.多目标进化算法及其应用.北京：国防工业出版社,2006
[21]石川,李清勇,史忠植.一种快速的基于占优树的多目标进化算法.软件学报,2007,18(3)：505-516
[22]Agapie Alexandru, Rudolph Gunter. Convergence Properties of Some Multi-Objective Evolutionary Algorithms.In the 2000 Congress on Evolutionary Computation (CEC 2000),IEEE,Piscataway (NJ),2000
[23]Zhiyong Li,Rudolph.Convergence performance comparison of quantum-inspired multi-objective evolutionary algorithms.Proceedings of the International Conference,Bio-Inspired Computing-Theories and Applications BIC-TA 2007 Zhengzhou, China,2009,57(11-12):1843-1854
[24]Eberhart R C,Shi Y. Particle swarm optimization:developments,applications and resources.In:Proc.of the Congress on Evolutionary Computation.Seoul, Korea,2001,81-86
[25]Bartz B T, Limbourg P, Parsopoulos K E,et al.Particle swarm optimizers for pareto optimization with enhanced archiving techniques.In:Proc.of the Congress on Evolutionary Computation.Canberra, Australia,2003,1780-1787
[26]Rosenberg R S.Simulation of genetic populations with biochemical properties. Michigan:University of Michigan,1967,25-38
[27]Carlos A C,David A V, Gary B L.Evolutionary Algorithms for Solving Multi-Objective Problems.New York:Kluwer Academic Publishers,2002,66-67
[28]Colorni A,Dorigo M,Maniezzo V. Disttributed optimization by ant colonies.In: Proc.of European Conf. Artificial Life.Pans,France,1991,134-142
[29]彭喜元,彭宇,戴毓丰.群智能理论及应用.电子学报,2003,31(12)：1982-1988
[30]Kennedy J,Eberhart R C.Particle swarm optimization.In:Proc.of Int. Conf. on Neural Networks.Perth,Australia,1995,1942-1948
[31]Laura D, Mihai O. What Else Is the Evolution of PSO Telling Us.Journal of Artificial Evolution and Applications,2008,8(2):1-12
[32]Julio E A B,Richard M E,Jonathan E F.A MOPSO algorithm based exclusively on pareto dominance concepts.In:Proc.of the Third Int.Conf. on Evolutionary Multi-Criterion Optimization.Mexico,USA,2005,459-473
[33]Jonathan E F, Sameer S.A multi-objective algorithm based upon particle swarm optimisation,an efficient datastructure and turbulence.In:Proc.of the Workshop on Computational Intelligence.Birmingham,England,2002,37-44
[34]张葛祥,李娜,金炜东等.一种新量子遗传算法及其应用.电子学报,2004,32(3)：476-479.
[35]王凌,吴昊,唐芳等.混合量子遗传算法及其性能分析.控制与决策,2005,20(2)：156-160
[36]张维迎.博弈论与经济信息学.上海人民出版社,2004,106-135
[37]Tadahiko M,Hisao I.MOGA:Multi-Objective Genetic Algorithms.In:Proc.of Int.Conf. on Evolutionary Computation.Perth,Australia,1995,289-294
[38]Zitzler E,Thiele L.Multiobjective evolutionary algorithms:A comparative case study and the strength pareto approach.IEEE Transactions on Evolutionary Computation,1999,3(4):257-271
[39]崔逊学,李淼等,基于免疫原理的多目标进化算法群体多样性研究.模式识别与人工智能,2001,14(3)：291-296
[40]Parsopoulos K E, Vrahatis M N.Particle Swarm Optimization Method in Multiobjective Problems.In:Proc.of the Congress on Evolutionary Computation. Honolulu,USA,2002,46-53
[41]Parsopoulos K E,Tasoulis D K, Vrahatis M N.Multiobjective optimization using parallel vector evaluated particle swarm optimization.In:Proc.of Int.Conf. on Artificial Intelligence and Applications.Innsbruck, Austria,2004,823-828
[42]Foster T,Kesselman C,Tuecke S.The anatomy of the Grid:Enabling scalable virtual organizations.International Journal of Supercomputer Application,2001, 15(3):200-222
[43]杜晓丽,蒋昌俊,徐国荣等.一种基于模糊聚类的网格DAG任务图调度算法.软件学报,2006,17(11)：2277-2288.
[44]徐志伟,冯百明,李伟.网络计算技术.电子工业出版社,2004,93-124
[45]王树鹏,云晓春,余翔湛.基于生存性和Makespan的多目标网格任务调度算法研究.通信学报,2006,27(2)：42-49
[46]Holland J.Adaptation in natural and artificial systems.Michigan:The University of Michigan,1975,45-87