基于线性权重最优支配的高维多目标优化算法

doi:10.11772/j.issn.1001-9081.2017.10.2823

计算机应用 ›› 2017, Vol. 37 ›› Issue (10): 2823-2827.DOI: 10.11772/j.issn.1001-9081.2017.10.2823

基于线性权重最优支配的高维多目标优化算法

朱占磊, 李征, 赵瑞莲

北京化工大学信息科学与技术学院, 北京 100029

收稿日期:2017-04-05 修回日期:2017-05-30 出版日期:2017-10-10 发布日期:2017-10-16
通讯作者: 李征(1974-),男,河北清苑人,教授,博士生导师,CCF高级会员,主要研究方向:基于搜索的软件工程、软件测试,E-mail:lizheng@mail.buct.edu.cn
作者简介:朱占磊(1990-),男,河南许昌人,硕士研究生,主要研究方向:进化优化算法、多目标优化;李征(1974-),男,河北清苑人,教授,博士生导师,CCF高级会员,主要研究方向:基于搜索的软件工程、软件测试;赵瑞莲(1964-),女,山西忻州人,教授,博士生导师,CCF会员,主要研究方向:软件测试、软件可靠性分析.
基金资助:
国家自然科学基金资助项目（61472025，61672085）。

Many-objective optimization algorithm based on linear weighted minimal/maximal dominance

ZHU Zhanlei, LI Zheng, ZHAO Ruilian

College of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China

Received:2017-04-05 Revised:2017-05-30 Online:2017-10-10 Published:2017-10-16
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61472025, 61672085).

摘要/Abstract

摘要： 在高维多目标优化问题中，Pareto支配关系存在非支配解随优化目标数增加呈指数级增长和种群选择压力下降等问题。针对这些问题，基于线性权重聚合函数和支配关系两种比较多目标解方法的思想，提出一种线性权重最优支配关系（LWM-dominance），并理论证明了LWM非支配解集是Pareto非支配解集的子集，同时保留了种群中重要的角解。进一步地，基于LWM支配关系，实现了一个高维多目标进化优化算法，基于该算法的实验验证了LWM支配关系的性质。在随机解空间中的实验结果表明LWM支配关系适用于5~15个目标的高维多目标优化问题，通过DTLZ1~DTLZ7高维多目标优化问题进化过程中LWM非支配解集与Pareto非支配解集规模的对比实验，结果表明优化目标数为10和15时非支配解的比例平均下降了约17%。

关键词: 进化优化算法, 高维多目标优化, 线性权重函数, 支配关系, Pareto前沿

Abstract: In Many-objective Optimization Problems (MaOP), the Pareto dominance has exponential increase of non-dominated solutions and the decrease of selection pressure with increasing optimization objectives. To solve these issues, a new type of dominance, namely Linear Weighted Minimal/Maximal dominance (LWM-dominance) was proposed based on the ideas of comparing multi-objective solutions by using linear weighted aggregation and Pareto dominance. It is theoretically proved that LWM non-dominated solution set is a subset of Pareto non-dominated solution set, meanwhile the important corner solutions are reserved. Furthermore, an MaOP algorithm based on LWM dominance was presented. The empirical studies proved the corollaries of the proposed LWM dominance. In detail, the experimental results in random objective space show that the LWM dominance is suitable for the MaOPs with 5-15 objectives; the experiment on comparing the number of LWM non-dominated solutions and Pareto non-dominated solutions with subjects of DTLZ1-DTLZ7 shows that the proportion of non-dominated solutions decreases by about 17% on average when the number of optimization objectives is 10 and 15.

Key words: evolutionary optimization algorithm, many-objective optimization, linear weighted function, dominant relationship, Pareto Front (PF)

中图分类号:

TP18

朱占磊, 李征, 赵瑞莲. 基于线性权重最优支配的高维多目标优化算法[J]. 计算机应用, 2017, 37(10): 2823-2827.

ZHU Zhanlei, LI Zheng, ZHAO Ruilian. Many-objective optimization algorithm based on linear weighted minimal/maximal dominance[J]. Journal of Computer Applications, 2017, 37(10): 2823-2827.

参考文献

[1] DEB K, JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(4): 577-601.
[2] ISHIBUCHI H, TSUKAMOTO N, NOJIMA Y. Evolutionary many-objective optimization: a short review[C]//CEC 2008: Proceedings of the 2008 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2008: 2419-2426.
[3] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[4] GARZA-FABRE M, PULIDO G T, COELLO C A C. Ranking methods for many-objective optimization[C]//MICAI 2009: Proceedings of the 2009 Mexican International Conference on Artificial Intelligence. Berlin: Springer, 2009: 633-645.
[5] DEB K. Multi-objective optimization using evolutionary algorithms[M]. New York: John Wiley & Sons, 2001: 47-75.
[6] STEHR G, GRAEB H, ANTREICH K. Performance trade-off analysis of analog circuits by normal-boundary intersection[C]//Proceedings of the 40th Annual Design Automation Conference. New York: ACM, 2003: 958-963.
[7] KLAMROTH K, JØRGEN T. Constrained optimization using multiple objective programming[J]. Journal of Global Optimization, 2007, 37(3): 325-355.
[8] HUGHES E J. Multiple single objective Pareto sampling[C]//CEC 2003: Proceedings of the 2003 Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2003: 2678-2684.
[9] LI B, LI J, TANG K, et al. Many-objective evolutionary algorithms: a survey[J]. ACM Computing Surveys, 2015, 48(1): 13.
[10] KUNG H T, LUCCIO F, PREPARATA F P. On finding the maxima of a set of vectors[J]. Journal of the ACM, 1975, 22(4): 469-476.
[11] 公茂果, 焦李成, 杨咚咚, 等. 进化多目标优化算法研究[J]. 软件学报, 2009, 20(2): 271-289. (GONG M G, JIAO L C, YANG D D, et al. Evolutionary multi-objective optimization algorithms[J]. Journal of Software, 2009, 20(2): 271-289.)
[12] EMMERICH M, DEUTZ A, KRUISSELBRINK J, et al. Cone-based hypervolume indicators: Construction, properties, and efficient computation[C]//EMO 2013: Proceedings of the 2013 International Conference on Evolutionary Multi-Criterion Optimization. Berlin: Springer, 2013: 111-127.
[13] RACHMAWATI L, SRINIVASAN D. A multi-objective evolutionary algorithm with weighted-sum niching for convergence on knee regions[C]//Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation. New York: ACM, 2006: 749-750.
[14] SINGH H K, ISAACS A, RAY T. A pareto corner search evolutionary algorithm and dimensionality reduction in many-objective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(4): 539-556.
[15] WANG H, YAO X. Corner sort for Pareto-based many-objective optimization[J]. IEEE Transactions on Cybernetics, 2014, 44(1): 92-102.
[16] DURILLO J J, NEBRO A J. jMetal: a Java framework for multi-objective optimization[J]. Advances in Engineering Software, 2011, 42(10): 760-771.
[17] HUBAND S, HINGSTON P, BARONE L, et al. A review of multiobjective test problems and a scalable test problem toolkit[J]. IEEE Transactions on Evolutionary Computation, 2006, 10(5): 477-506.

基于线性权重最优支配的高维多目标优化算法

Many-objective optimization algorithm based on linear weighted minimal/maximal dominance

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 7

编辑推荐

Metrics

[1]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[2]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[3]	李二超, 李康伟. 基于最小距离和聚合策略的分解多目标进化算法[J]. 计算机应用, 2021, 41(1): 22-28.
[4]	谭阳, 唐德权, 曹守富. 基于超球形模糊支配的高维多目标粒子群优化算法[J]. 计算机应用, 2019, 39(11): 3233-3241.
[5]	马艺元, 宋卫平, 宁爱平, 牛海帆. 混沌云模型多目标布谷鸟搜索算法[J]. 计算机应用, 2017, 37(4): 1088-1092.
[6]	洪留荣. 在线手写数学公式结构分析算法[J]. 计算机应用, 2010, 30(9): 2545-2548.
[7]	王江晴杨勋. 基于Pareto-ε优胜的自适应快速多目标演化算法[J]. 计算机应用, 2010, 30(4): 997-999.