Computer Engineering and Applications ›› 2015, Vol. 51 ›› Issue (8): 47-52.

Previous Articles     Next Articles

Multi-objective evolutionary algorithm based on Bayesian game strategy and its convergence property

LI Zhiyong, HU Jieqiong, CHEN Dong, LI Renfa   

  1. College of Information Science and Engineering, Hunan University, Changsha 410082, China
  • Online:2015-04-15 Published:2015-04-29

贝叶斯博弈多目标进化算法及其收敛性分析

李智勇,胡杰琼,陈  冬,李仁发   

  1. 湖南大学 信息科学与工程学院,长沙 410082

Abstract: Nowadays most of traditional Multi-Objective Evolutionary Algorithms(MOEAs) search global Pareto front based on the non-dominant sorting method. By this way evolutionary populations can get high convergence performance in the early iterative stage, however there maybe exists convergence stagnation for complex problems in the late iterative stage, which cuts off the global optimization ability. To address this problem a method based on Static Bayesian Game strategy Multi-Objective Evolutionary Algorithm(SBG-MOEA) is proposed. Each optimization object is emulated as one game participant and their convergence performances to Pareto solution set are mapped to the game incomes in the algorithm. The profit and loss Nash equilibrium game mechanism is applied to drive the evolutionary population chasing the Pareto front. Theoretical analysis proves that the approach can converge to the global Pareto optimal set. Compared with the classic multi-objective evolutionary algorithms, such as NAGAII, the simulation optimization results show that Bayesian game strategy can enhance the global optimal searching ability of MOEAs.

Key words: multi-objective optimization, evolutionary algorithm, static Bayesian game

摘要: 多目标进化算法(MOEAs)主要依靠非支配解排序推动种群搜索Pareto前沿,在种群迭代搜索前期具有较好的全局寻优性能,但进化后期易出现收敛停滞现象,影响算法对于复杂优化问题的全局寻优能力。由此提出了一种基于静态贝叶斯博弈策略的多目标进化算法(SBG-MOEA),将每个优化目标模拟为一个博弈参与者,以多次迭代中优化目标Pareto优化收敛程度映射为博弈收益,通过损益纳什均衡博弈机制驱动种群的Pareto寻优,理论分析证明了该方法具有全局收敛特性。基准测试函数的优化实验表明,与NSGA-II等经典算法相比,贝叶斯博弈策略有助于增强进化种群全局搜索能力。

关键词: 多目标优化, 进化算法, 静态贝叶斯博弈