Computer Science

Computer Science ›› 2022, Vol. 49 ›› Issue (6): 297-304.doi: 10.11896/jsjkx.210500095

• Artificial Intelligence • Previous Articles     Next Articles

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

SUN Gang1, WU Jiang-jiang1, CHEN Hao1, LI Jun1, XU Shi-yuan2   

  1. 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).

PDF (PC)

1082

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

CLC Number: 

  • TP301.6
[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.
[1] ZHANG Jia, DONG Shou-bin. Cross-domain Recommendation Based on Review Aspect-level User Preference Transfer [J]. Computer Science, 2022, 49(9): 41-47.
[2] PIAO Yong, ZHU Si-yuan, LI Yang. Hybrid Housing Resource Recommendation Based on Combined User and Location Characteristics [J]. Computer Science, 2022, 49(6A): 733-737.
[3] XIONG Zhong-min, SHU Gui-wen, GUO Huai-yu. Graph Neural Network Recommendation Model Integrating User Preferences [J]. Computer Science, 2022, 49(6): 165-171.
[4] LI Hao-dong, HU Jie, FAN Qin-qin. Multimodal Multi-objective Optimization Based on Parallel Zoning Search and Its Application [J]. Computer Science, 2022, 49(5): 212-220.
[5] PENG Dong-yang, WANG Rui, HU Gu-yu, ZU Jia-chen, WANG Tian-feng. Fair Joint Optimization of QoE and Energy Efficiency in Caching Strategy for Videos [J]. Computer Science, 2022, 49(4): 312-320.
[6] YANG Xu-hua, WANG Lei, YE Lei, ZHANG Duan, ZHOU Yan-bo, LONG Hai-xia. Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding [J]. Computer Science, 2022, 49(3): 121-128.
[7] CHEN Jin-peng, HU Ha-lei, ZHANG Fan, CAO Yuan, SUN Peng-fei. Convolutional Sequential Recommendation with Temporal Feature and User Preference [J]. Computer Science, 2022, 49(1): 115-120.
[8] GUAN Zheng, DENG Yang-lin, NIE Ren-can. Non-negative Matrix Factorization Based on Spectral Reconstruction Constraint for Hyperspectral and Panchromatic Image Fusion [J]. Computer Science, 2021, 48(9): 153-159.
[9] WANG Hui, ZHU Guo-yu, SHEN Zi-hao, LIU Kun, LIU Pei-qian. Dummy Location Generation Method Based on User Preference and Location Distribution [J]. Computer Science, 2021, 48(7): 164-171.
[10] SHAO Chao, SONG Shu-mi. Collaborative Filtering Recommendation Algorithm Based on User Preference Under Trust Relationship [J]. Computer Science, 2021, 48(6A): 240-245.
[11] LI Li, LI Guang-peng, CHANG Liang, GU Tian-long. Survey of Constrained Evolutionary Algorithms and Their Applications [J]. Computer Science, 2021, 48(4): 1-13.
[12] ZHOU Sheng-yi, ZENG Hong-wei. Program Complexity Analysis Method Combining Evolutionary Algorithm with Symbolic Execution [J]. Computer Science, 2021, 48(12): 107-116.
[13] WANG Ke, QU Hua, ZHAO Ji-hong. Multi-objective Optimization Method Based on Reinforcement Learning in Multi-domain SFC Deployment [J]. Computer Science, 2021, 48(12): 324-330.
[14] ZHAO Yang, NI Zhi-wei, ZHU Xu-hui, LIU Hao, RAN Jia-min. Multi-worker and Multi-task Path Planning Based on Improved Lion Evolutionary Algorithm forSpatial Crowdsourcing Platform [J]. Computer Science, 2021, 48(11A): 30-38.
[15] ZHU Han-qing, MA Wu-bin, ZHOU Hao-hao, WU Ya-hui, HUANG Hong-bin. Microservices User Requests Allocation Strategy Based on Improved Multi-objective Evolutionary Algorithms [J]. Computer Science, 2021, 48(10): 343-350.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.