A Parallel Multi-Objective Dividing Rectangles Algorithm Based on Normalized Decomposition

Li Chen; Chen Yidong; Lu Zhonghua; Yang Xueying; Wang Zitian; Chi Xuebin

doi:10.7544/issn1000-1239.202330093

Journal of Computer Research and Development > 2024 > 61(11): 2909-2922. > DOI: 10.7544/issn1000-1239.202330093 CSTR: 32373.14.issn1000-1239.202330093

Li Chen, Chen Yidong, Lu Zhonghua, Yang Xueying, Wang Zitian, Chi Xuebin. A Parallel Multi-Objective Dividing Rectangles Algorithm Based on Normalized Decomposition[J]. Journal of Computer Research and Development, 2024, 61(11): 2909-2922. DOI: 10.7544/issn1000-1239.202330093

Citation:

PDF (1972 KB)

A Parallel Multi-Objective Dividing Rectangles Algorithm Based on Normalized Decomposition

Li Chen^1,,
Chen Yidong^{1, 2,},
Lu Zhonghua^1,,
Yang Xueying^{1, 2},
Wang Zitian^3,,
Chi Xuebin^1,

1.
Computer Network Information Center, Chinese Academy of Sciences, Beijing 100083
2.
University of Chinese Academy of Sciences, Beijing 100049
3.
Beijing AIHPC Co., Ltd., Beijing 100037

Funds: This work was supported by the China Postdoctoral Science Foundation (2021M693226) and the National Natural Science Foundation of China (61873254).

More Information

Author Bio:
Li Chen: born in 1993. PhD, assistant professor. Member of CCF. Her main research interests include high performance computing, multi-objective optimization, and fuzzy computing

Chen Yidong: born in 1996. PhD candidate. His main research interest includes high performance computing technology in the computational finance. (chenyidong@cnic.cn)

Lu Zhonghua: born in 1965. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interest includes high performance computing and its application. (zhlu@cnic.cn)

Yang Xueying: born in 1997. PhD candidate. Her main research interest includes high performance computing technology in the computational finance. (yangxueying@cnic.cn)

Wang Zitian: born in 1982. PhD. His main research interests include high performance computing and multi-objective optimization. (wzt@aihpc.cn)

Chi Xuebin: born in 1963. PhD, professor, PhD supervisor. Distinguished member of CCF. His main research interests include high performance computing and grid technology. (chi@sccas.cn)
Received Date: February 15, 2023
Revised Date: December 28, 2023
Accepted Date: March 05, 2024
Available Online: March 06, 2024

Graphical Abstract

Abstract

Abstract

Multi-objective optimization problems are common in real-world applications. However, the high computational complexity severely hinders their solution. Currently, multi-objective evolutionary algorithms are mostly used for their solving. Nevertheless, these methods usually contain random operations in the process of population initialization and evolution to maintain diversity, which leads to non-reproducibility and lacking the theoretical guarantee of global convergence. Therefore, a novel multi-objective Dividing Rectangles(DIRECT) algorithm is introduced based on decomposition strategy. In this algorithm, the original problem is decomposed into a series of subproblems by a normalized decomposition method that can better capture the complex frontier to reduce the computational complexity of the problem. Meanwhile, the Dividing Rectangles algorithm is used to simultaneously optimize the decomposed subproblems, and the generated candidate solutions are assigned to the corresponding subproblems based on the global association mechanism in the optimization process to better retain the good candidate solutions and improve the algorithm search efficiency. Finally, the convergence of the algorithm is demonstrated. To further improve the computational efficiency, a multi-level and multi-granularity parallel scheme based on the adaptive associative migration strategy is proposed, based on which the proposed algorithm is parallelized. Furthermore, the proposed algorithm and its parallel version are applied to several benchmark optimization problems, and the experimental results show that the proposed algorithm can obtain a Pareto set with better convergence and diversity than NSGA-II, and the parallel version can further improve the accuracy of Pareto frontier approximation while massively reducing the problem-solving time.
- multi-objective optimization,
- objective space decomposition,
- Dividing Rectangles algorithm,
- parallel computing,
- global optimization

FullText(HTML)

References (38)

References

[1]	Wong C S Y, Al-Dujaili A, Sundaram S. Hypervolume-based direct for multi-objective optimization [C] //Proc of the 16th Genetic and Evolutionary Computation Conf Companion. New York: ACM, 2016: 1201−1208
[2]	田野. 高维多目标优化算法的若干关键问题研究 [D]. 合肥:安徽大学,2015 Tian Ye. Research on several key problems of many-objective optimization algorithms [D]. Hefei: Anhui University, 2015 (in Chinese)
[3]	Zelinka I. A survey on evolutionary algorithms dynamics and its complexity−Mutual relations, past, present and future[J]. Swarm and Evolutionary Computation, 2015, 25: 2−14 doi: 10.1016/j.swevo.2015.06.002
[4]	Hernandez Gomez R, Coello Coello C A, Alba E. A parallel version of SMS-EMOA for many-objective optimization problems [C] // Proc of the 16th Genetic and Evolutionary Computation Conf Companion. New York: ACM, 2016: 568−577
[5]	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 doi: 10.1109/4235.996017
[6]	Zhang Qingfu, Li Hui. MOEA/D: A multiobjective evolutionary algorithm based on decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712−731 doi: 10.1109/TEVC.2007.892759
[7]	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, 2013, 18(4): 577−601
[8]	Mashwani W K. MOEA/D with DE and PSO: MOEA/D-DE+ PSO [C] //Proc of the 31st SGAI Int Conf on Innovative Techniques and Applications of Artificial Intelligence. Berlin: Springer, 2011: 217−221
[9]	Jones D R, Perttunen C D, Stuckman B E. Lipschitzian optimization without the Lipschitz constant[J]. Journal of Optimization Theory and Applications, 1993, 79(1): 157−181 doi: 10.1007/BF00941892
[10]	Jones D R, Martins J R. The DIRECT algorithm: 25 years later[J]. Journal of Global Optimization, 2021, 79((3): ): 521−566 doi: 10.1007/s10898-020-00952-6
[11]	Zitzler E, Thiele L. Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(4): 257−271 doi: 10.1109/4235.797969
[12]	唐炜森. 基于hypervolume的多目标优化算法研究 [D]. 广州:广东工业大学,2018 Tang Weisen. Research on hypervolume based evolutionary multi-objective optimization algorithms [D]. Guangzhou: Guangdong University of Technology, 2018 (in Chinese)
[13]	刘垚,郑琳,郑凯,等. 基于申威众核处理器的NSGA-Ⅱ并行和优化方法[J]. 计算机应用研究,2020,37(1):96−101 Liu Yao, Zheng Lin, Zheng Kai, et al. Parallelization and optimization of NSGA-Ⅱ based on Sunway many-core processor[J]. Application Research of Computers, 2020, 37(1): 96−101 (in Chinese)
[14]	Zitzler E, Laumanns M, Thiele L. SPEA2: Improving the strength Pareto evolutionary algorithm[J]. Technical Report Gloriastrasse, 2001, 103(1): 1−21
[15]	Zhan Zhihui, Li Jingjing, Cao Jiannong, et al. Multiple populations for multiple objectives: A coevolutionary technique for solving multiobjective optimization problems[J]. IEEE Transactions on Cybernetics, 2013, 43(2): 445−463 doi: 10.1109/TSMCB.2012.2209115
[16]	Liu Hailin, Gu Fangqing, Zhang Qingfu. Decomposition of a multiobjective optimization problem into a number of simple multiobjective subproblems[J]. IEEE Transactions on Evolutionary Computation, 2014, 18(3): 450−455 doi: 10.1109/TEVC.2013.2281533
[17]	Cheng Ran, Jin Yaochu, Olhofer M, et al. A reference vector guided evolutionary algorithm for many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2016, 20(5): 773−791 doi: 10.1109/TEVC.2016.2519378
[18]	Zitzler E, Künzli S. Indicator-based selection in multiobjective search [C] //Proc of the 8th Int Conf on Parallel Problem Solving from Nature-PPSN VIII. Berlin: Springer, 2004: 832−842
[19]	Bader J, Zitzler E. HypE: An algorithm for fast hypervolume-based many-objective optimization[J]. Evolutionary Computation, 2011, 19(1): 45−76 doi: 10.1162/EVCO_a_00009
[20]	Falcón-Cardona J G, Coello Coello A C. A new indicator-based many-objective ant colony optimizer for continuous search spaces[J]. Swarm Intelligence, 2017, 11(1): 71−100 doi: 10.1007/s11721-017-0133-x
[21]	Shubert B O. A sequential method seeking the global maximum of a function [J]. SIAM Journal on Numerical Analysis, 1972, 9(3): 379−388
[22]	Wang Luyi, Ishida H, Hiroyasu T, et al. Examination of multiobjective optimization method for global search using DIRECT and GA [C] //Proc of the 2008 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2008: 2446−2451
[23]	Al-Dujaili A, Suresh S. Dividing rectangles attack multi-objective optimization [C] //Proc of the 2016 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2016: 3606−3613
[24]	Campana E F, Diez M, Liuzzi G S, et al. A multi-objective direct algorithm for ship hull optimization[J]. Computational Optimization and Applications, 2018, 71(1): 53−72 doi: 10.1007/s10589-017-9955-0
[25]	Houssein E H, Mahdy M A, Shebl D, et al. An efficient slime mould algorithm for solving multi-objective optimization problems[J]. Expert Systems with Application, 2022, 187: 115870 doi: 10.1016/j.eswa.2021.115870
[26]	Miettinen K. Nonlinear Multiobjective Optimization [M]. New York: Springer, 2012
[27]	万沙沙,裴丽,王喜奎,等. 利用DIRECT算法设计基于FBG延迟线的微波光子滤波器[J]. 光电技术应用,2008,23(6):41−44 doi: 10.3969/j.issn.1673-1255.2008.06.011 Wan Shasha, Pei Li, Wang Xikui, et al. Design of PMF based on FBG delay line using DIRECT algorithm[J]. Electrooptic Technology Application, 2008, 23(6): 41−44 (in Chinese) doi: 10.3969/j.issn.1673-1255.2008.06.011
[28]	何洪文,黄贤广,张亚明,等. 基于DIRECT算法的混合动力汽车参数优化研究[J]. 汽车工程学报,2011,1(1):35−41 He Hongwen, Huang Xianguang, Zhang Yaming, et al. Study on parameters optimization of hybrid electric vehicle based on DIRECT algorithm[J]. Chinese Journal of Automotive Engineering, 2011, 1(1): 35−41 (in Chinese)
[29]	Mohammadi A, Omidvar M N, Li Xiaodong. Reference point based multi-objective optimization through decomposition [C] //Proc of the 2012 IEEE Congress on Evolutionary Computation. Piscataway, NJ: IEEE, 2012: 1150−1157
[30]	魏建乐. 基于协同分解的多目标进化算法设计与应用 [D]. 广州:广州大学,2022 Wei Jianle. Design and application of multi-objective evolutionary algorithm based on cooperative decomposition [D]. Guangzhou: Guangzhou University, 2022 (in Chinese)
[31]	王丽萍,吴峰,张梦紫,等. 基于差异化邻域策略的分解多目标进化算法[J]. 模式识别与人工智能,2017,30(12):1069−1082 Wang Liping, Wu Feng, Zhang Mengzi, et al. Decomposition multi-objective evolutionary algorithm based on differentiated neighborhood strategy[J]. Pattern Recognition and Artificial Intelligence, 2017, 30(12): 1069−1082 (in Chinese)
[32]	Zitzler E, Deb K, Thiele L. Comparison of multiobjective evolutionary algorithms: Empirical results[J]. Evolutionary Computation, 2000, 8(2): 173−195 doi: 10.1162/106365600568202
[33]	李璐. 基于双层分解的并行多目标演化算法研究 [D]. 西安:西安电子科技大学,2020 Li Lu. Research on parallel multi-objective evolutionary algorithm based on bi-level decomposition [D]. Xi’an: Xidian University, 2020 (in Chinese)
[34]	Deb K, Thiele L, Laumanns M, et al. Scalable Test Problems for Evolutionary Multiobjective Optimization [M]. Berlin: Springer, 2005
[35]	葛梦瑶. 人工蜂群算法在多目标模糊投资组合优化中的应用 [D]. 北京:首都经济贸易大学,2016 Ge Mengyao. Application of artificial bee colony algorithm in multi-objective fuzzy portfolio optimization [D]. Beijing: Capital University of Economics and Business, 2016 (in Chinese)
[36]	Van Veldhuizen D A. Multiobjective evolutionary algorithms: Classifications, analyses, and new innovations [D]. Dayton, OH: Air Force Institute of Technology, 1999
[37]	Coello Coello C A, Reyes Sierra M. A study of the parallelization of a coevolutionary multi-objective evolutionary algorithm [C] //Proc of the 3rd Mexican Int Conf on Artificial Intelligence. Berlin: Springer, 2004: 688−697
[38]	Li Chen, Wu Yulei, Lu Zhonghua, et al. A multiperiod multiobjective portfolio selection model with fuzzy random returns for large scale securities data[J]. IEEE Transactions on Fuzzy Systems, 2021, 29(1): 59−74 doi: 10.1109/TFUZZ.2020.2992866

[1]	Zhou Yuanding, Gao Guopeng, Fang Yaodong, Qin Chuan. Perceptual Authentication Hashing with Image Feature Fusion Based on Window Self-Attention[J]. Journal of Computer Research and Development. DOI: 10.7544/issn1000-1239.202330669
[2]	Gao Wei, Chen Liqun, Tang Chunming, Zhang Guoyan, Li Fei. One-Time Chameleon Hash Function and Its Application in Redactable Blockchain[J]. Journal of Computer Research and Development, 2021, 58(10): 2310-2318. DOI: 10.7544/issn1000-1239.2021.20210653
[3]	Wu Linyang, Luo Rong, Guo Xueting, Guo Qi. Partitioning Acceleration Between CPU and DRAM: A Case Study on Accelerating Hash Joins in the Big Data Era[J]. Journal of Computer Research and Development, 2018, 55(2): 289-304. DOI: 10.7544/issn1000-1239.2018.20170842
[4]	Jiang Jie, Yang Tong, Zhang Mengyu, Dai Yafei, Huang Liang, Zheng Lianqing. DCuckoo: An Efficient Hash Table with On-Chip Summary[J]. Journal of Computer Research and Development, 2017, 54(11): 2508-2515. DOI: 10.7544/issn1000-1239.2017.20160795
[5]	Wang Wendi, Tang Wen, Duan Bo, Zhang Chunming, Zhang Peiheng, Sun Ninghui. Parallel Accelerator Design for High-Throughput DNA Sequence Alignment with Hash-Index[J]. Journal of Computer Research and Development, 2013, 50(11): 2463-2471.
[6]	Yuan Xinpan, Long Jun, Zhang Zuping, Luo Yueyi, Zhang Hao, and Gui Weihua. Connected Bit Minwise Hashing[J]. Journal of Computer Research and Development, 2013, 50(4): 883-890.
[7]	Qin Chuan, Chang Chin Chen, Guo Cheng. Perceptual Robust Image Hashing Scheme Based on Secret Sharing[J]. Journal of Computer Research and Development, 2012, 49(8): 1690-1698.
[8]	Ding Zhenhua, Li Jintao, Feng Bo. Research on Hash-Based RFID Security Authentication Protocol[J]. Journal of Computer Research and Development, 2009, 46(4): 583-592.
[9]	Li Zhiqiang, Chen Hanwu, Xu Baowen, Liu Wenjie. Fast Algorithms for Synthesis of Quantum Reversible Logic Circuits Based on Hash Table[J]. Journal of Computer Research and Development, 2008, 45(12): 2162-2171.
[10]	Liu Ji. One-Way Hash Function based on Integer Coupled Tent Maps and Its Performance Analysis[J]. Journal of Computer Research and Development, 2008, 45(3): 563-569.