ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2017, Vol. 54 ›› Issue (5): 1012-1023.doi: 10.7544/issn1000-1239.2017.20160074

• 人工智能 • 上一篇    下一篇

基于网格排序的多目标粒子群优化算法

李笠,王万良,徐新黎,李伟琨   

  1. (浙江工业大学计算机科学与技术学院 杭州 310023) (liixac@gmail.com)
  • 出版日期: 2017-05-01
  • 基金资助: 
    “十二五”国家科技支撑计划基金项目(2012BAD10B01);国家自然科学基金项目(61379123)

Multi-Objective Particle Swarm Optimization Based on Grid Ranking

Li Li, Wang Wanliang, Xu Xinli, Li Weikun   

  1. (College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023)
  • Online: 2017-05-01

摘要: 在多目标进化算法中,近年的研究倾向于基于Pareto支配的最优化方法.针对传统的基于Pareto支配在排序效率上过低的问题,提出了一种基于网格排序的框架,利用网格同时表征收敛性与分布性的特性,结合粒子群算法,提出了一种基于网格排序的多目标粒子群优化算法.与个体两两进行比较的基于Pareto支配的策略不同,基于网格排序的机制融合了整个解空间中个体的占优信息,并利用占优信息进行排序,从而高效地得到个体在种群中的优劣关系;结合粒子到近似最优边界的距离,进一步加强了粒子在解空间中优劣关系的判别.对比实验分析表明:所提算法不论是在收敛性还是分布性上都具有较好的优势.在此基础上,讨论了网格划分数对算法效率的影响,从另一方面验证了算法的效率.

关键词: 多目标优化, 进化算法, 粒子群算法, 网格, 排序

Abstract: In multi-objective evolutionary algorithms, the majority of researches are Pareto-based. However, the efficiency of Pareto optimality in objective space will deteriorate when there are numerous weak dominance relations. Aiming at this problem, this paper presents a framework of grid-based ranking. By integrating gird strategy, which features both convergence and distribution, with the particle swarm optimization (PSO), we propose a novel grid-based ranking multi-objective particle swarm optimization (MOPSO). Unlike the strategy of Pareto-based dominance which conducts a pairwise comparison between individuals, the grid-based ranking mechanism combines the individual dominance information in the entire solution space, and takes advantage of this information to sort. As a result, we gain the merits of the relationship between individuals in the population effectively and efficiently. By incorporating the distance between particles and approximate optimal front, we reinforce the judgement of the merits of the relationship among particles in the solution space. The experimental assessment indicates that the proposed method in this paper has relative advantages in both convergence and distribution. On this basis, we discuss the influence of grid partition on efficiency in terms of the distribution of ranks over the process of evolutionary, which verifies the efficiency of the algorithm from the other aspect.

Key words: multi-objective optimization, evolutionary algorithm, particle swarm optimization (PSO), grid, ranking

中图分类号: