基于拐点和区域划分的高维多目标进化算法

杨景明; 郝佳佳; 孙浩; 魏之慧; 李霞霞

doi:10.3969/j.issn.1000-1158.2021.08.14

PDF(1552 KB)

计量学报 ›› 2021, Vol. 42 ›› Issue (8) : 1068-1075. DOI: 10.3969/j.issn.1000-1158.2021.08.14

无线电、时间频率计量

基于拐点和区域划分的高维多目标进化算法

杨景明,郝佳佳,孙浩,魏之慧,李霞霞

作者信息 +

A Many-objective Evolutionary Algorithm Based on Knee Point and Region Division

YANG Jing-ming,HAO Jia-jia,SUN Hao,WEI Zhi-hui,LI Xia-xia

Author information +

文章历史 +

摘要

针对高维多目标优化问题中收敛性和分布性难以同时保持的问题,提出一种基于拐点和区域划分的高维多目标进化算法KnSP。算法选取拐点作为第1次区域划分的中心点,自适应生成邻域;然后采用角度分层法进行二次区域划分,将点到超平面的距离作为个体选择的准则;最后通过候选解与其余个体的角度来增加或删除个体以保证种群规模。实验结果表明,算法在多个测试函数中性能表现较其它比较算法更优。

Abstract

A many-objective evolutionary algorithm KnSP is proposed based on knee point and region division to solve the problem that is difficult to maintain convergence and distribution. The algorithm selects the knee points as the center point of the first region division and adaptively generates a corresponding neighborhood.Then the angle is used to divide the second area, and the distance of the point to the hyperplane is used as the criterion for individual selection.Finally, from the perspective of the candidate solutions and the other individuals, individuals are added or deleted to ensure the population size.Experimental result shows that the algorithm performs better in some test functions than compared algorithms.

导出引用

杨景明,郝佳佳,孙浩,魏之慧,李霞霞. 基于拐点和区域划分的高维多目标进化算法[J]. 计量学报. 2021, 42(8): 1068-1075 https://doi.org/10.3969/j.issn.1000-1158.2021.08.14

YANG Jing-ming,HAO Jia-jia,SUN Hao,WEI Zhi-hui,LI Xia-xia. A Many-objective Evolutionary Algorithm Based on Knee Point and Region Division[J]. Acta Metrologica Sinica. 2021, 42(8): 1068-1075 https://doi.org/10.3969/j.issn.1000-1158.2021.08.14

中图分类号： TB973

参考文献

［1］郑金华, 邹娟. 多目标进化优化［M］. 北京: 科学出版社, 2017.
［2］赵志伟, 侯宇浩, 王伟志, 等. 基于参考点和差分变异策略的高维多目标冷轧负荷分配［J］. 计量学报, 2017, 38 (6): 730-734.
Zhao Z W, Hou Y H, Wang W Z, et al. Many-objective Load Distribution for Cold Rolling Based on Reference Point and Differential Mutation Strategy ［J］. Acta Metrologica Sinica, 2017, 38 (6): 730-734.
［3］Yang S X, Li M Q, Liu X H, et al. A Grid-Based Evolutionary Algorithm for Many-Objective Optimization［J］. IEEE Transactions on Evolutionary Computation, 2013, 17 (5): 721-736.
［4］Das S S, Islam M M, Arafat N A. Evolutionary algorithm using adaptive fuzzy dominance and reference point for many-objective optimization ［J］. Swarm and evolutionary computation, 2019, 44: 1092-1107.
［5］Deb K, Mohan M, Mishra S. Evaluating the ε-domination based multi-objective evolutionary algorithm for a quick computation of Pareto-optimal solutions ［J］. Evolutionary computation, 2005, 13 (4): 501-525.
［6］Zhang X, Tian Y, Jin Y. A knee point-driven evolu-tionary algorithm for many-objective optimization ［J］. IEEE Transactions on Evolutionary Computation, 2014, 19 (6): 761-776.
［7］Li K, Deb K, Zhang Q F, et al. An evolutionary many-objective optimization algorithm based on dominance and decomposition ［J］. IEEE Transactions on Evolutionary Comp-utation, 2014, 19 (5): 694-716.
［8］Cheng T, Jin Y C, Miettinen K, et al. A surrogate-assisted reference vector guided evolutionary algorithm for many-objective optimization ［J］. IEEE Transactions on Evolutionary Computation, 2016, 22 (1): 129-142.
［9］Bader J, Zitzler E. HypE: an algorithm for fast hypervo-lumebased many-objective optimization ［J］. Evolutionary Computation, 2011, 19 (1): 45-76.
［10］Hernández Gómez R, Coello Coello C A. Improved metaheuristic based on the R2 indicator for many-objective optimization［C］//ACM. Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Compu-tation. 2015: 679-686.
［11］王丽萍,邱飞岳. 复杂多目标问题的优化方法及应用［M］. 北京: 科学出版社, 2018.
［12］Das I. On characterizing the knee of the Pareto curve based on Normal-Boundary Intersection ［J］. Structural & Multidisciplinary Optimization, 1999, 18 (2-3): 107-115.
［13］Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II ［J］. IEEE transactions on evolutionary computation, 2002, 6 (2): 182-197.
［14］Agrawal R B, Deb K, Agrawal R B. Simulated Binary Crossover for Continuous Search Space ［J］. Complex Systems, 2000, 9 (3): 115-148.
［15］Deb K, Goyal M. A combined genetic adaptive search (Gene AS)for engineering design ［J］. Comput Sci Informat, 1996, 26,4: 30-45.
［16］Deb K. Multi-Objective Optimization Using Evolutionary Algorithms ［M］. New York: Wiley, 2001.
［17］While L, Hingston P, Barone L, et al. A faster algorithm for calculating hypervolume［J］. IEEE Trans Evol Comput, 2006, 10 (1): 29-38.
［18］Zhang Q F, Zhou A M, Jin Y C. RM-MEDA: A regu-larity model-based multiobjective estimation of distribu-tion algorithm ［J］. IEEE Trans Evol Comput, 2008, 12 (1): 41-63.
［19］Li M, Zheng J. Spread assessment for evolutionary multi-objective optimization［C］//International confer-ence on evolutionary multi-criterion optimization. Sprin-ger, Berlin, Heidelberg, 2009: 216-230.
［20］Bai H, Zheng J H, Yu G, et al. A Pareto-based many-objective evolutionary algorithm using space partitioning selection and angle-based truncation ［J］. Information Sciences, 2019, 478: 186-207.
［21］Deb K, Gupta S. Understanding knee points in bicriteria problems and their implications as preferred solution principles ［J］. Engineering optimization, 2011, 43 (11): 1175-1204.
［22］Yu G, Jin Y C, Olhofer M. Benchmark Problems and Performance Indicators for Search of Knee Points in Multiobjective Optimization ［J］. IEEE transactions on cyber-netics, 2019, 99: 1-14.
［23］Maltese J, Ombuki-Berman B M, Engelbrecht A P. Pareto-based many-objective optimization using knee points［C］//IEEE. 2016 IEEE Congress on Evolutionary Computation (CEC). 2016: 3678-3686.
［24］Sudeng S, Wattanapongsakorn N. A decompositionbased approach for knee solution approximation in multi-objective optimization［C］//IEEE. 2016 IEEE Congress on Evolutionary Computation (CEC). 2016: 3710-3717.
［25］刘彬, 刘泽仁, 赵志彪, 等. 基于速度交流的多种群多目标粒子群算法研究［J］. 计量学报, 2020, 41(8): 1002-1011.
Liu B, Liu Z R, Zhao Z B, et al. Research on Multi-population Multi-objective Particle Swarm Optimization Algorithm Based on Velocity Communication［J］. Acta Metrologica Sinica, 2020, 41(8): 1002-1011.
［26］刘彬, 顾昕峰, 孙超, 等. 基于梯形区间软约束的多目标优化预测控制算法研究［J］. 计量学报, 2018, 39(4): 562-567.
Liu B,Gu X F,Sun C, et al. A Predictive Control Algorithm Based on Trapezoid Interval Soft Constraint and Multi-objective Optimization［J］. Acta Metrologica Sinica, 2018, 39(4): 562-567.