一种基于切比雪夫距离的隐式偏好多目标进化算法

计算机科学 ›› 2022, Vol. 49 ›› Issue (6): 297-304.doi: 10.11896/jsjkx.210500095

一种基于切比雪夫距离的隐式偏好多目标进化算法

孙刚¹, 伍江江¹, 陈浩¹, 李军¹, 徐仕远²

1 国防科技大学电子科学学院长沙 410073
2 北方工业大学信息学院北京 100144

收稿日期:2021-05-13 修回日期:2021-09-04 出版日期:2022-06-15 发布日期:2022-06-08
通讯作者: 陈浩(hchen@nudt.edu.cn)
作者简介:(sungang19@nudt.edu.cn)
基金资助:
国家自然科学基金(61806211,U19A2058);湖南省自然科学基金(2020JJ4103)

Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance

SUN Gang¹, WU Jiang-jiang¹, CHEN Hao¹, LI Jun¹, XU Shi-yuan²

1 College of Electronic Science and Technology,National University of Defense Technology,Changsha 410073,China
2 School of Information Science and Technology,North China University of Technology,Beijing 100144,China

Received:2021-05-13 Revised:2021-09-04 Online:2022-06-15 Published:2022-06-08
About author:SUN Gang,born in 1988,postgraduate.His main research interests include multi-objective evolutionary algorithms and satellite range scheduling problems.
CHEN Hao,born in 1982,Ph.D,professor.His main research interests include data mining,machine learning and evolutionary computation.
Supported by:
National Natural Science Foundation of China(61806211,U19A2058) and Natural Science Foundation of Hunan Province(2020JJ4103).

摘要/Abstract

摘要： 偏好多目标进化算法作为多目标优化方法的重要分支,被广泛应用于科学研究和工程实践,具有重要的研究意义。为了求得多目标优化问题中的极点解及在各优化目标上性能最折衷的膝点解,提出了用切比雪夫距离来定义膝点的方法并给出了几何解释,基于此构建了一种求解极点解和膝点解的多目标进化算法HP-NSGA-II。该算法通过区域动态更新策略使得目标区域随迭代过程动态更新,最终收敛于目标区域;通过区域间平衡性保持策略确保各区域间个体数量的平衡性,使得个体较为均匀地分布在各区域内部。基于广泛采用的测试函数开展了充分的实验验证,结果表明,HP-NSGA-II算法在二维测试问题及三维测试问题上具有较好的收敛性、区域间平衡性以及区域可控性,可以准确求得测试问题的极点解及膝点解。

关键词: 多目标优化, 极点解, 进化算法, 偏好, 切比雪夫距离, 膝点解

Abstract: As an important branch of multi-objective optimization,preference-based multi-objective evolutionary algorithms have been widely used in scientific researches and engineering practices,which have important research significance.In order to obtain the extreme solutions and the knee solution with the most compromised performance over each optimization objective in multi-objective optimization problems,a definition of knee solution based on Chebyshev distance and its geometric interpretation is presented.Based on the definition,a multi-objective evolutionary algorithm HP-NSGA-II aiming to search for the extreme solutions and the knee solution is proposed.The regional dynamic updating strategy of the proposed algorithm updates the target regions dynamically in each iteration,and finally converges to the target regions.The strategy of maintaining the balance between regions ensures the balance of the number of individuals in each region,so that the individuals could be distributed evenly in each region.Based on widely used test functions,sufficient experimental verification is carried out,and the experimental results indicate that HP-NSGA-II algorithm can achieve better performance in terms of convergence,regional balance and regional controllability in two-dimensional and three-dimensional test problems,and can accurately obtain the extreme solutions and knee solution.

Key words: Chebyshev distance, Evolutionary algorithm, Extreme solution, Knee solution, Multi-objective optimization, Preference

中图分类号:

TP301.6

孙刚, 伍江江, 陈浩, 李军, 徐仕远. 一种基于切比雪夫距离的隐式偏好多目标进化算法[J]. 计算机科学, 2022, 49(6): 297-304. https://doi.org/10.11896/jsjkx.210500095

SUN Gang, WU Jiang-jiang, CHEN Hao, LI Jun, XU Shi-yuan. Hidden Preference-based Multi-objective Evolutionary Algorithm Based on Chebyshev Distance[J]. Computer Science, 2022, 49(6): 297-304. https://doi.org/10.11896/jsjkx.210500095

参考文献

[1] LI L M,WANG Y L,TRAUTMANN H,et al.Multiobjective evolutionary algorithms based on target region preferences[J].Swarm and Evolutionary Computation,2018,40:196-215.
[2] ZHENG J H,ZOU J.Multi-objective evolutionary optimization[M].Science Press,2017:1-9.
[3] BRANKE J.MCDA and multi-objective evolutionary algorithms[M].Springer,2016:977-1008.
[4] DEB K,PRATAP A,AGARWAL S,et al.A fast and elitistmultiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.
[5] 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.
[6] ZHANG Q,LI H.MOEA/D:A multiobjective evolutionary algorithm based on decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.
[7] WANG L P,FENG M L,QIU Q C,et al.Survey on preference-based multi-objective evolutionary algorithms[J].Chinese Journal of Computers,2019,42(6):1289-1315.
[8] SAID L B,BECHIKH S,GHEDIRA K.The r-dominance:a new dominance relation for interactive evolutionary multicriteria decision making[J].IEEE Transactions on Evolutionary Computation,2010,14(5):801-818.
[9] SATO H,TOMITA K,MIYAKAWA M.Preferred region based evolutionary multi-objective optimization using parallel coordinates interface[C]//Proceedings of the International Symposium on Computational and Business Intelligence.IEEE,2016:33-38.
[10] ZHENG J H,LAI N,GUO G Q.ε-Pareto dominance strategy based on angle preference in MOEA[J].Pattern Recognition & Artificial Intelligence,2014,27(6):569-576.
[11] DEB K,GUPTA S.Understanding knee points in bicriteriaproblems and their implications as preferred solution principles[J].Engineering Optimization,2011,43(11):1175-1204.
[12] WANG H,HE S,YAO X.Nadir point estimation for many-objective optimization problems based on emphasized critical regions[J].Soft Computing,2017,21(9):2283-2295.
[13] BRANKE J,DEB K,DIEROLF H,et al.Finding knees in multi-objective optimization[C]//Proceedings of the Parallel Problem Solving from Nature.Springer,2004:722-731.
[14] DAS I.On characterizing the “knee” of the Pareto curve based on normal-boundary intersection[J].Structural and Multidisciplinary Optimization,1999,18(2):107-115.
[15] BECHIKH S,BEN S L,GHÉDIRA K.Searching for knee re-gions in multi-objective optimization using mobile reference points[C]//Proceedings of the 2010 ACM Symposium on Applied Computing.ACM,2010:1118-1125.
[16] DEB K,SUNDAR J,BHASKARA U,et al.Reference pointbased multi-objective optimization using evolutionary algorithms[J].Journal of Computational Intelligence Research,2006,2(3):635-642.
[17] RACHMAWATI L,SRINIVASAN D.A multi-objective genetic algorithm with controllable convergence on knee regions[C]//IEEE Congress on Evolutionary Computation.IEEE,2006:1916-1923.
[18] CHIU W Y,YEN G G,JUAN T K.Minimum manhattan distance approach to multiple criteria decision making in multiobjective optimization problems[J].IEEE Transactions on Evolutionary Computation,2016,20(6):972-985.
[19] DAVID H.MOEAFramework[EB/OL].(2019-12-30)[2020-11-12].http://moeaframework.org/.
[20] BELEGUNDU A,CONSTANS E,SALAGAME R,et al.Multi-objective optimization of laminated ceramic composites using genetic algorithms[C]//5th Symposium on Multidisciplinary Analysis and Optimization.AIAA,1994:1015-1022.
[21] ZITZLER E,DEB K,THIELE L.Comparison of multi-objective evolutionary algorithms:Empirical result[J].Evolutionary Computation,2000,8(2):173-195.
[22] ZITZLER E,THIELE L,LAUMANNS M,et al.Performance assessment of multi-objective optimizers:An analysis and review[J].IEEE Transactions on Evolutionary Computation,2003,7(2):117-132.
[23] VLENNET R,FONTEIX C,MARC I.Multicriteria optimization using a genetic algorithm for determining a Pareto set[J].International Journal of Systems Science,1996,27(2):255-260.
[24] ZHOU Y,YEN G G,ZHANG Y.A knee-guided evolutionary algorithm for compressing deep neural networks[J].IEEE Transactions on Cybernetics,2019,30(7):1926-1938.

相关文章 15

[1]	张佳, 董守斌. 基于评论方面级用户偏好迁移的跨领域推荐算法 Cross-domain Recommendation Based on Review Aspect-level User Preference Transfer 计算机科学, 2022, 49(9): 41-47. https://doi.org/10.11896/jsjkx.220200131
[2]	刘宝宝, 杨菁菁, 陶露, 王贺应. 基于DE-LSTM模型的教育统计数据预测研究 Study on Prediction of Educational Statistical Data Based on DE-LSTM Model 计算机科学, 2022, 49(6A): 261-266. https://doi.org/10.11896/jsjkx.220300120
[3]	朴勇, 朱锶源, 李阳. 融合用户和区位资源特征的混合房源推荐方法 Hybrid Housing Resource Recommendation Based on Combined User and Location Characteristics 计算机科学, 2022, 49(6A): 733-737. https://doi.org/10.11896/jsjkx.210800062
[4]	熊中敏, 舒贵文, 郭怀宇. 融合用户偏好的图神经网络推荐模型 Graph Neural Network Recommendation Model Integrating User Preferences 计算机科学, 2022, 49(6): 165-171. https://doi.org/10.11896/jsjkx.210400276
[5]	李浩东, 胡洁, 范勤勤. 基于并行分区搜索的多模态多目标优化及其应用 Multimodal Multi-objective Optimization Based on Parallel Zoning Search and Its Application 计算机科学, 2022, 49(5): 212-220. https://doi.org/10.11896/jsjkx.210300019
[6]	彭冬阳, 王睿, 胡谷雨, 祖家琛, 王田丰. 视频缓存策略中QoE和能量效率的公平联合优化 Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos 计算机科学, 2022, 49(4): 312-320. https://doi.org/10.11896/jsjkx.210800027
[7]	杨旭华, 王磊, 叶蕾, 张端, 周艳波, 龙海霞. 基于节点相似性和网络嵌入的复杂网络社区发现算法 Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding 计算机科学, 2022, 49(3): 121-128. https://doi.org/10.11896/jsjkx.210200009
[8]	王辉, 朱国宇, 申自浩, 刘琨, 刘沛骞. 基于用户偏好和位置分布的假位置生成方法 Dummy Location Generation Method Based on User Preference and Location Distribution 计算机科学, 2021, 48(7): 164-171. https://doi.org/10.11896/jsjkx.200800069
[9]	邵超, 宋淑米. 基于信任关系下用户兴趣偏好的协同过滤推荐算法 Collaborative Filtering Recommendation Algorithm Based on User Preference Under Trust Relationship 计算机科学, 2021, 48(6A): 240-245. https://doi.org/10.11896/jsjkx.200700113
[10]	李笠, 李广鹏, 常亮, 古天龙. 约束进化算法及其应用研究综述 Survey of Constrained Evolutionary Algorithms and Their Applications 计算机科学, 2021, 48(4): 1-13. https://doi.org/10.11896/jsjkx.200600151
[11]	周晟伊, 曾红卫. 进化算法与符号执行结合的程序复杂度分析方法 Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution 计算机科学, 2021, 48(12): 107-116. https://doi.org/10.11896/jsjkx.210200052
[12]	王珂, 曲桦, 赵季红. 多域SFC部署中基于强化学习的多目标优化方法 Multi-objective Optimization Method Based on Reinforcement Learning in Multi-domain SFC Deployment 计算机科学, 2021, 48(12): 324-330. https://doi.org/10.11896/jsjkx.201100159
[13]	赵杨, 倪志伟, 朱旭辉, 刘浩, 冉家敏. 基于改进狮群进化算法的面向空间众包平台的多工作者多任务路径规划方法 Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform 计算机科学, 2021, 48(11A): 30-38. https://doi.org/10.11896/jsjkx.201200085
[14]	崔国楠, 王立松, 康介祥, 高忠杰, 王辉, 尹伟. 结合多目标优化算法的模糊聚类有效性指标及应用 Fuzzy Clustering Validity Index Combined with Multi-objective Optimization Algorithm and Its Application 计算机科学, 2021, 48(10): 197-203. https://doi.org/10.11896/jsjkx.200900061
[15]	朱汉卿, 马武彬, 周浩浩, 吴亚辉, 黄宏斌. 基于改进多目标进化算法的微服务用户请求分配策略 Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms 计算机科学, 2021, 48(10): 343-350. https://doi.org/10.11896/jsjkx.201100009

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed