Journal Home > Volume 29 , Issue 2
Tsinghua Science and Technology 2024, 29(2): 325-342 https://doi.org/10.26599/TST.2023.9010031
Open Access | Issue | Published: 22 September 2023

Exploring a Promising Region and Enhancing Decision Space Diversity for Multimodal Multi-Objective Optimization

Show Author's Information Fei Ming1,  Wenyin Gong1( )
School of Computer Science, China University of Geosciences, Wuhan 430074, China
Keywords:
coevolution, evolutionary algorithms, multimodal multi-objective optimization, promising region, neighbor distance, decision space
Cite this article:
Ming F, Gong W. Exploring a Promising Region and Enhancing Decision Space Diversity for Multimodal Multi-Objective Optimization. Tsinghua Science and Technology, 2024, 29(2): 325-342. https://doi.org/10.26599/TST.2023.9010031
Download citation
EndNote(RIS)
BibTeX

286

Views

57

Downloads

Citations

1

Crossref

0

WoS

0

Scopus

0

CSCD

Abstract Full text Electronic supplementary material About this article

During the past decade, research efforts have been gradually directed to the widely existing yet less noticed multimodal multi-objective optimization problems (MMOPs) in the multi-objective optimization community. Recently, researchers have begun to investigate enhancing the decision space diversity and preserving valuable dominated solutions to overcome the shortage caused by a preference for objective space convergence. However, many existing methods still have limitations, such as giving unduly high priorities to convergence and insufficient ability to enhance decision space diversity. To overcome these shortcomings, this article aims to explore a promising region (PR) and enhance the decision space diversity for handling MMOPs. Unlike traditional methods, we propose the use of non-dominated solutions to determine a limited region in the PR in the decision space, where the Pareto sets (PSs) are included, and explore this region to assist in solving MMOPs. Furthermore, we develop a novel neighbor distance measure that is more suitable for the complex geometry of PSs in the decision space than the crowding distance. Based on the above methods, we propose a novel dual-population-based coevolutionary algorithm. Experimental studies on three benchmark test suites demonstrates that our proposed methods can achieve promising performance and versatility on different MMOPs. The effectiveness of the proposed neighbor distance has also been justified through comparisons with crowding distance methods.


menu
Abstract
Full text
Outline
Electronic supplementary material
About this article

Exploring a Promising Region and Enhancing Decision Space Diversity for Multimodal Multi-Objective Optimization

Show Author's information Fei Ming1, Wenyin Gong1( )
School of Computer Science, China University of Geosciences, Wuhan 430074, China

Abstract

During the past decade, research efforts have been gradually directed to the widely existing yet less noticed multimodal multi-objective optimization problems (MMOPs) in the multi-objective optimization community. Recently, researchers have begun to investigate enhancing the decision space diversity and preserving valuable dominated solutions to overcome the shortage caused by a preference for objective space convergence. However, many existing methods still have limitations, such as giving unduly high priorities to convergence and insufficient ability to enhance decision space diversity. To overcome these shortcomings, this article aims to explore a promising region (PR) and enhance the decision space diversity for handling MMOPs. Unlike traditional methods, we propose the use of non-dominated solutions to determine a limited region in the PR in the decision space, where the Pareto sets (PSs) are included, and explore this region to assist in solving MMOPs. Furthermore, we develop a novel neighbor distance measure that is more suitable for the complex geometry of PSs in the decision space than the crowding distance. Based on the above methods, we propose a novel dual-population-based coevolutionary algorithm. Experimental studies on three benchmark test suites demonstrates that our proposed methods can achieve promising performance and versatility on different MMOPs. The effectiveness of the proposed neighbor distance has also been justified through comparisons with crowding distance methods.

Keywords: coevolution, evolutionary algorithms, multimodal multi-objective optimization, promising region, neighbor distance, decision space

References(45)

[1]
S. Han, K. Zhu, M. Zhou, and X. Cai, Competition-driven multimodal multiobjective optimization and its application to feature selection for credit card fraud detection, IEEE Trans. Syst., Man, Cybern.: Syst., vol. 52, no. 12, pp. 7845–7857, 2022.
DOI Google Scholar
[2]
V. Barichard and J. K. Hao, Genetic tabu search for the Multi-Objective knapsack problem, Tsinghua Science and Technology, vol. 8, no. 1, pp. 8–13, 2003.
Google Scholar
[3]
Y. Tian, R. Liu, X. Zhang, H. Ma, K. C. Tan, and Y. Jin, A multipopulation evolutionary algorithm for solving large-scale multimodal multiobjective optimization problems, IEEE Trans. Evol. Comput., vol. 25, no. 3, pp. 405–418, 2021.
DOI Google Scholar
[4]
H. Zhang, L. Ma, J. Wang, and L. Wang, Furnace-grouping problem modeling and multi-objective optimization for special aluminum, IEEE Trans. Emerg. Top. Comput. Intell., vol. 6, no. 3, pp. 544–555, 2022.
DOI Google Scholar
[5]
X. Ma, Y. Fu, K. Gao, L. Zhu, and A. Sadollah, A multi-objective scheduling and routing problem for home health care services via brain storm optimization, Complex System Modeling and Simulation, vol. 3, no. 1, pp. 32–46, 2023.
DOI Google Scholar
[6]
L. Wang, Z. Pan, and J. Wang, A review of reinforcement learning based intelligent optimization for manufacturing scheduling, Complex System Modeling and Simulation, vol. 1, no. 4, pp. 257–270, 2021.
DOI Google Scholar
[7]
R. Tanabe and H. Ishibuchi, A review of evolutionary multimodal multiobjective optimization, IEEE Trans. Evol. Comput., vol. 24, no. 1, pp. 193–200, 2020.
DOI Google Scholar
[8]
W. Gong, Z. Liao, X. Mi, L. Wang, and Y. Guo, Nonlinear equations solving with intelligent optimization algorithms: A survey, Complex System Modeling and Simulation, vol. 1, no. 1, pp. 15–32, 2021.
DOI Google Scholar
[9]
C. Yue, B. Qu, and J. Liang, A multiobjective particle swarm optimizer using ring topology for solving multimodal multiobjective problems, IEEE Trans. Evol. Comput., vol. 22, no. 5, pp. 805–817, 2018.
DOI Google Scholar
[10]
W. Li, X. Yao, T. Zhang, R. Wang, and L. Wang, Hierarchy ranking method for multimodal multiobjective optimization with local Pareto fronts, IEEE Trans. Evol. Comput., pp. vol. 27, no. 1, pp. 98–110, 2023.
DOI Google Scholar
[11]
J. J. Liang, C. T. Yue, and B. Y. Qu, Multimodal multi-objective optimization: A preliminary study, in Proc. 2016 IEEE Congress on Evolutionary Computation, Vancouver, Canada, 2016, pp. 2454–2461.
DOI Google Scholar
[12]
Q. Lin, W. Lin, Z. Zhu, M. Gong, J. Li, and C. A. C. Coello, Multimodal multiobjective evolutionary optimization with dual clustering in decision and objective spaces, IEEE Trans. Evol. Comput., vol. 25, no. 1, pp. 130–144, 2021.
DOI Google Scholar
[13]
Y. Liu, G. G. Yen, and D. Gong, A multimodal multiobjective evolutionary algorithm using two-archive and recombination strategies, IEEE Trans. Evol. Comput., vol. 23, no. 4, pp. 660–674, 2019.
DOI Google Scholar
[14]
W. Li, T. Zhang, R. Wang, and H. Ishibuchi, Weighted indicator-based evolutionary algorithm for multimodal multiobjective optimization, IEEE Trans. Evol. Comput., vol. 25, no. 6, pp. 1064–1078, 2021.
DOI Google Scholar
[15]
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Trans. Evol. Comput., vol. 6, no. 2, pp. 182–197, 2002.
DOI Google Scholar
[16]
R. Tanabe and H. Ishibuchi, A framework to handle multimodal multiobjective optimization in decomposition-based evolutionary algorithms, IEEE Trans. Evol. Comput., vol. 24, no. 4, pp. 720–734, 2020.
DOI Google Scholar
[17]
Y. Peng and H. Ishibuchi, A diversity-enhanced subset selection framework for multimodal multiobjective optimization, IEEE Trans. Evol. Comput., vol. 26, no. 5, pp. 886–900, 2022.
DOI Google Scholar
[18]
Q. Fan and X. Yan, Solving multimodal multiobjective problems through zoning search, IEEE Trans. Syst., Man, Cybern.: Syst., vol. 51, no. 8, pp. 4836–4847, 2021.
DOI Google Scholar
[19]
G. Li, W. Wang, W. Zhang, W. You, F. Wu, and H. Tu, Handling multimodal multi-objective problems through self-organizing quantum-inspired particle swarm optimization, Inf. Sci., vol. 577, pp. 510–540, 2021.
DOI Google Scholar
[20]
Z. Li, J. Zou, S. Yang, and J. Zheng, A two-archive algorithm with decomposition and fitness allocation for multi-modal multi-objective optimization, Inf. Sci., vol. 574, pp. 413–430, 2021.
DOI Google Scholar
[21]
J. Liang, K. Qiao, C. Yue, K. Yu, B. Qu, R. Xu, Z. Li, and Y. Hu, A clustering-based differential evolution algorithm for solving multimodal multi-objective optimization problems, Swarm Evol. Comput., vol. 60, p. 100788, 2021.
DOI Google Scholar
[22]
B. Qu, G. Li, L. Yan, J. Liang, C. Yue, K. Yu, and O. D. Crisalle, A grid-guided particle swarm optimizer for multimodal multi-objective problems, Appl. Soft Comput., vol. 117, p. 108381, 2022.
DOI Google Scholar
[23]
K. Zhang, C. Shen, G. G. Yen, Z. Xu, and J. He, Two-stage double niched evolution strategy for multimodal multiobjective optimization, IEEE Trans. Evol. Comput., vol. 25, no. 4, pp. 754–768, 2021.
DOI Google Scholar
[24]
S. Han, K. Zhu, M. Zhou, and X. Cai, Information-utilization-method-assisted multimodal multiobjective optimization and application to credit card fraud detection, IEEE Trans. Comput. Soc. Syst., vol. 8, no. 4, pp. 856–869, 2021.
DOI Google Scholar
[25]
Y. Liu, H. Ishibuchi, G. G. Yen, Y. Nojima, and N. Masuyama, Handling imbalance between convergence and diversity in the decision space in evolutionary multimodal multiobjective optimization, IEEE Trans. Evol. Comput., vol. 24, no. 3, pp. 551–565, 2020.
Google Scholar
[26]
C. Yue, P. N. Suganthan, J. Liang, B. Qu, K. Yu, Y. Zhu, and L. Yan, Differential evolution using improved crowding distance for multimodal multiobjective optimization, Swarm Evol. Comput., vol. 62, p. 100849, 2021.
DOI Google Scholar
[27]
Y. Tian, T. Zhang, J. Xiao, X. Zhang, and Y. Jin, A coevolutionary framework for constrained multiobjective optimization problems, IEEE Trans. Evol. Comput., vol. 25, no. 1, pp. 102–116, 2021.
DOI Google Scholar
[28]
J. Yuan, H. L. Liu, Y. S. Ong, and Z. He, Indicator-based evolutionary algorithm for solving constrained multiobjective optimization problems, IEEE Trans. Evol. Comput., vol. 26, no. 2, pp. 379–391, 2022.
DOI Google Scholar
[29]
Y. Tian, L. Si, X. Zhang, K. Tan, and Y. Jin, Local model-based Pareto front estimation for multiobjective optimization, IEEE Trans. Syst., Man, Cybern.: Syst., vol. 53, no. 1, pp. 623–634, 2023.
DOI Google Scholar
[30]
Y. Tian, R. Cheng, X. Zhang, and Y. Jin, PlatEMO: A MATLAB platform for evolutionary multi-objective optimization [Educational Forum], IEEE Comput. Intell. Mag., vol. 12, no. 4, pp. 73–87, 2017.
DOI Google Scholar
[31]
R. B. Agrawal, K. Deb, and R. B. Agrawal, Simulated binary crossover for continuous search space, Complex Syst., vol. 9, no. 3, pp. 115–148, 2000.
Google Scholar
[32]
H. Ishibuchi, R. Imada, N. Masuyama, and Y. Nojima, Comparison of hypervolume, IGD and IGD+ from the viewpoint of optimal distributions of solutions, in Proc. 10th Int. Conf. Evolutionary Multi-Criterion Optimization, East Lansing, MI, USA, 2019, pp. 332–345.
DOI Google Scholar
[33]
Y. Tian, X. Xiang, X. Zhang, R. Cheng, and Y. Jin, Sampling reference points on the Pareto fronts of benchmark multi-objective optimization problems, in Proc. 2018 IEEE Congress on Evolutionary Computation, Rio de Janeiro, Brazil, 2018, pp. 1–6.
DOI Google Scholar
[34]
A. Zhou, Q. Zhang, and Y. Jin, Approximating the set of Pareto-optimal solutions in both the decision and objective spaces by an estimation of distribution algorithm, IEEE Trans. Evol. Comput., vol. 13, no. 5, pp. 1167–1189, 2009.
DOI Google Scholar
[35]
H. Ishibuchi, L. M. Pang, and K. Shang, Difficulties in fair performance comparison of multi-objective evolutionary algorithms [research frontier], IEEE Comput. Intell. Mag., vol. 17, no. 1, pp. 86–101, 2022.
DOI Google Scholar
[36]
J. Alcalá-Fdez, L. Sánchez, S. García, M. J. del Jesus, S. Ventura, J. M. Garrell, J. Otero, C. Romero, J. Bacardit, V. M. Rivas, et al., KEEL: A software tool to assess evolutionary algorithms for data mining problems, Soft Comput., vol. 13, no. 3, pp. 307–318, 2009.
DOI Google Scholar
[37]
E. Jiang, L. Wang, and J. Wang, Decomposition-based multi-objective optimization for energy-aware distributed hybrid flow shop scheduling with multiprocessor tasks, Tsinghua Science and Technology, vol. 26, no. 5, pp. 646–663, 2021.
DOI Google Scholar
[38]
W. Zhang, X. Chen, and J. Jiang, A multi-objective optimization method of initial virtual machine fault-tolerant placement for star topological data centers of cloud systems, Tsinghua Science and Technology, vol. 26, no. 1, pp. 95–111, 2021.
DOI Google Scholar
[39]
F. Zhao, X. Hu, L. Wang, and Z. Li, A memetic discrete differential evolution algorithm for the distributed permutation flow shop scheduling problem, Complex Intell. Syst., vol. 8, no. 1, pp. 141–161, 2022.
DOI Google Scholar
[40]
K. Gao, Y. Huang, A. Sadollah, and L. Wang, A review of energy-efficient scheduling in intelligent production systems, Complex Intell. Syst., vol. 6, no. 2, pp. 237–249, 2020.
DOI Google Scholar
[41]
H. Ma, H. Wei, Y. Tian, R. Cheng, and X. Zhang, A multi-stage evolutionary algorithm for multi-objective optimization with complex constraints, Inf. Sci., vol. 560, pp. 68–91, 2021.
DOI Google Scholar
[42]
J. Liang, X. Ban, K. Yu, B. Qu, K. Qiao, C. T. Yue, K. Chen, and K. C. Tan, A survey on evolutionary constrained multiobjective optimization, IEEE Trans. Evol. Comput., vol. 27, no. 2, pp. 201–221, 2023.
DOI Google Scholar
[43]
H. Ishibuchi, Y. Peng, and K. Shang, A scalable multimodal multiobjective test problem, in Proc. 2019 IEEE Congress on Evolutionary Computation, Wellington, New Zealand, 2019, pp. 310–317.
DOI Google Scholar
[44]
Z. Cui, J. Zhang, Y. Wang, Y. Cao, X. Cai, W. Zhang, and J. Chen, A pigeon-inspired optimization algorithm for many-objective optimization problems, Sci. China Inf. Sci., vol. 62, no. 7, p. 70212, 2019.
DOI Google Scholar
[45]
R. Cheng, M. Li, Y. Tian, X. Zhang, S. Yang, Y. Jin, and X. Yao, A benchmark test suite for evolutionary many-objective optimization, Complex Intell. Syst., vol. 3, no. 1, pp. 67–81, 2017.
DOI Google Scholar
File
325-342ESM.pdf (5 MB)
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 19 February 2023
Revised: 06 March 2023
Accepted: 06 April 2023
Published: 22 September 2023
Issue date: April 2024

Copyright

© The author(s) 2024.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (No. 62076225).

Rights and permissions

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).

Return