- Yilu Liu ORCID:orcid.org/0000-0002-5926-863X14,15,
- Chengyu Lu ORCID:orcid.org/0000-0002-0412-633514,15,
- Xi Lin ORCID:orcid.org/0000-0001-5298-689314,15 &
- …
- Qingfu Zhang ORCID:orcid.org/0000-0003-0786-067114,15
Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 15151))
Included in the following conference series:
423Accesses
Abstract
Many-objective optimization (MaO) is a basic issue in various research areas. Although Pareto optimality is a common criterion for MaO, it may bring many troubles when facing a huge number (e.g., up to 100) of objectives. This paper provides a new perspective on MaO by introducing a many-objective cover problem (MaCP). Givenm objectives, MaCP aims to find a solution set with sizek (\(1 < k \ll m\)) to cover all objectives (i.e., each objective can be approximately optimized by at least one solution in this set). We prove the NP-hard property of MaCP and develop a clustering-based swarm optimizer (CluSO) with a convergence guarantee to tackle MaCP. Then, we propose a decoupling many-objective test suite (DC-MaTS) with practical significance and use it to evaluate CluSO. Extensive experimental results on various test problems with up to 100 objectives demonstrate both the efficiency and effectiveness of CluSO, while also illustrating that MaCP is a feasible perspective on MaO.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 22879
- Price includes VAT (Japan)
- Softcover Book
- JPY 10581
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ahmed, M., Seraj, R., Islam, S.M.S.: The k-means algorithm: a comprehensive survey and performance evaluation. Electronics9(8), 1295 (2020)
Blank, J., Deb, K.: Pymoo: multi-objective optimization in python. IEEE Access8, 89497–89509 (2020)
Brockhoff, D., Wagner, T., Trautmann, H.: On the properties of the R2 indicator. In: Proceedings of the Annual Conference on Genetic and Evolutionary Computation, pp. 465–472 (2012)
Censor, Y.: Pareto optimality in multiobjective problems. Appl. Math. Optim.4(1), 41–59 (1977)
Chen, W., Ishibuchi, H., Shang, K.: Fast greedy subset selection from large candidate solution sets in evolutionary multiobjective optimization. IEEE Trans. Evol. Comput.26(4), 750–764 (2021)
Cheng, R., Jin, Y.: A competitive swarm optimizer for large scale optimization. IEEE Trans. Cybern.45(2), 191–204 (2014)
Cheng, R., Jin, Y.: A social learning particle swarm optimization algorithm for scalable optimization. Inf. Sci.291, 43–60 (2015)
Cheng, R., Jin, Y., Olhofer, M., Sendhoff, B.: A reference vector guided evolutionary algorithm for many-objective optimization. IEEE Trans. Evol. Comput.20(5), 773–791 (2016)
Cheng, R., Li, M., Tian, Y., Zhang, X., Yang, S., Jin, Y., Yao, X.: A benchmark test suite for evolutionary many-objective optimization. Complex Intell. Syst.3, 67–81 (2017)
Chugh, T., Jin, Y., Miettinen, K., Hakanen, J., Sindhya, K.: A surrogate-assisted reference vector guided evolutionary algorithm for computationally expensive many-objective optimization. IEEE Trans. Evol. Comput.22(1), 129–142 (2016)
Clerc, M., Kennedy, J.: The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Trans. Evol. Comput.6(1), 58–73 (2002)
Cuate, O., Schütze, O.: Pareto explorer for solving real world applications. Res. Comput. Sci.149(3), 29–36 (2020)
Deb, K., Jain, H.: An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: Solving problems with box constraints. IEEE Trans. Evol. Comput.18(4), 577–601 (2014)
Deb, K., Thiele, L., Laumanns, M., Zitzler, E.: Scalable test problems for evolutionary multiobjective optimization. In: Evolutionary Multiobjective Optimization: Theoretical Advances and Applications, pp. 105–145. Springer, London (2005).https://doi.org/10.1007/1-84628-137-7_6
Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of Mathematics, pp. 439–485 (2005)
Drineas, P., Frieze, A., Kannan, R., Vempala, S., Vinay, V.: Clustering large graphs via the singular value decomposition. Mach. Learn.56, 9–33 (2004)
Duro, J.A., Saxena, D.K.: Timing the decision support for real-world many-objective optimization problems. In: Proceedings of the Evolutionary Multi-Criterion Optimization, pp. 191–205 (2017)
Grandoni, F.: A note on the complexity of minimum dominating set. J. Discrete Algorithms4(2), 209–214 (2006)
Gu, Y.R., Bian, C., Li, M., Qian, C.: Subset selection for evolutionary multi-objective optimization. IEEE Trans. Evol. Comput.28(2), 403–417 (2023)
Guerreiro, A.P., Fonseca, C.M., Paquete, L.: The hypervolume indicator: computational problems and algorithms. ACM Comput. Surv.54(6), 1–42 (2021)
Hassin, R., Levin, A.: A better-than-greedy approximation algorithm for the minimum set cover problem. SIAM J. Comput.35(1), 189–200 (2005)
Huband, S., Hingston, P., Barone, L., While, L.: A review of multiobjective test problems and a scalable test problem toolkit. IEEE Trans. Evol. Comput.10(5), 477–506 (2006)
Ishibuchi, H., Imada, R., Setoguchi, Y., Nojima, Y.: Reference point specification in inverted generational distance for triangular linear Pareto front. IEEE Trans. Evol. Comput.22(6), 961–975 (2018)
Jaimes, A.L., Oyama, A., Fujii, K.: Space trajectory design: Analysis of a real-world many-objective optimization problem. In: Proceedings of the IEEE Congress on Evolutionary Computation, pp. 2809–2816 (2013)
Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of International Conference on Neural Networks, vol. 4, pp. 1942–1948 (1995)
Lambrinidis, G., Tsantili-Kakoulidou, A.: Multi-objective optimization methods in novel drug design. Expert Opin. Drug Discov.16(6), 647–658 (2021)
Laumanns, M., Thiele, L., Deb, K., Zitzler, E.: Combining convergence and diversity in evolutionary multiobjective optimization. Evol. Comput.10(3), 263–282 (2002)
Li, B., Li, J., Tang, K., Yao, X.: Many-objective evolutionary algorithms: a survey. ACM Comput. Surv.48(1), 1–35 (2015)
Li, K., Wang, H., Wang, W., Wang, F., Cui, Z.: Improving artificial bee colony algorithm using modified nearest neighbor sequence. J. King Saud Univ. Comput. Inf. Sci.34(10), 8807–8824 (2022)
Li, K., Xu, M., Zeng, T., Ye, T., Zhang, L., Wang, W., Wang, H.: A new artificial bee colony algorithm based on modified search strategy. Int. J. Comput. Sci. Math.15(4), 387–395 (2022)
Li, Y., Fan, J., Wang, Y., Tan, K.L.: Influence maximization on social graphs: a survey. IEEE Trans. Knowl. Data Eng.30(10), 1852–1872 (2018)
Liu, Y., Liu, J., Teng, X.: Single-particle optimization for network embedding preserving both local and global information. Swarm Evol. Comput.71, 101069 (2022)
Liu, Y., Liu, J., Wu, K.: Cost-effective competition on social networks: a multi-objective optimization perspective. Inf. Sci.620, 31–46 (2023)
Ntakolia, C., Iakovidis, D.K.: A swarm intelligence graph-based pathfinding algorithm (SIGPA) for multi-objective route planning. Comput. Oper. Res.133, 105358 (2021)
Ostachowicz, W., Soman, R., Malinowski, P.: Optimization of sensor placement for structural health monitoring: a review. Struct. Health Monit.18(3), 963–988 (2019)
Owen, S.H., Daskin, M.S.: Strategic facility location: a review. Eur. J. Oper. Res.111(3), 423–447 (1998)
Pan, L., He, C., Tian, Y., Wang, H., Zhang, X., Jin, Y.: A classification-based surrogate-assisted evolutionary algorithm for expensive many-objective optimization. IEEE Trans. Evol. Comput.23(1), 74–88 (2018)
Paschos, V.T.: A survey of approximately optimal solutions to some covering and packing problems. ACM Comput. Surv.29(2), 171–209 (1997)
Shi, L., Cai, X.: An exact fast algorithm for minimum hitting set. In: Proceedings of the International Joint Conference on Computational Science and Optimization, vol. 1, pp. 64–67 (2010)
Singh, H.K., Bhattacharjee, K.S., Ray, T.: Distance-based subset selection for benchmarking in evolutionary multi/many-objective optimization. IEEE Trans. Evol. Comput.23(5), 904–912 (2018)
Sviridenko, M., Ward, J.: Large neighborhood local search for the maximum set packing problem. In: Proceedings of the International Colloquium on Automata, Languages, and Programming, pp. 792–803 (2013)
Wu, Q., Hao, J.K.: A review on algorithms for maximum clique problems. Eur. J. Oper. Res.242(3), 693–709 (2015)
Yang, S., Li, M., Liu, X., Zheng, J.: A grid-based evolutionary algorithm for many-objective optimization. IEEE Trans. Evol. Comput.17(5), 721–736 (2013)
Yuan, Y., Xu, H., Wang, B., Yao, X.: A new dominance relation-based evolutionary algorithm for many-objective optimization. IEEE Trans. Evol. Comput.20(1), 16–37 (2016)
Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput.11(6), 712–731 (2007)
Zhang, Q., Zhou, A., Jin, Y.: RM-MEDA: a regularity model-based multiobjective estimation of distribution algorithm. IEEE Trans. Evol. Comput.12(1), 41–63 (2008)
Zhang, T., Wang, H., Yuan, B., Jin, Y., Yao, X.: Surrogate-assisted evolutionary Q-learning for black-box dynamic time-linkage optimization problems. IEEE Trans. Evol. Comput.27(5), 1162–1176 (2022)
Zhou, A., Qu, B.Y., Li, H., Zhao, S.Z., Suganthan, P.N., Zhang, Q.: Multiobjective evolutionary algorithms: a survey of the state of the art. Swarm Evol. Comput.1(1), 32–49 (2011)
Acknowledgments
This work was supported by the Research Grants Council of the Hong Kong Special Administrative Region, China (CityU11215622), the Key Basic Research Foundation of Shenzhen, China (JCYJ20220818100005011), and the Natural Science Foundation of China (62276223).
Disclosure of Interest. The authors declare that they have no known competing interest that could appear to influence the work reported in this paper.
Author information
Authors and Affiliations
Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong
Yilu Liu, Chengyu Lu, Xi Lin & Qingfu Zhang
City University of Hong Kong Shenzhen Research Institute, Shenzhen, China
Yilu Liu, Chengyu Lu, Xi Lin & Qingfu Zhang
- Yilu Liu
You can also search for this author inPubMed Google Scholar
- Chengyu Lu
You can also search for this author inPubMed Google Scholar
- Xi Lin
You can also search for this author inPubMed Google Scholar
- Qingfu Zhang
You can also search for this author inPubMed Google Scholar
Corresponding authors
Correspondence toYilu Liu orQingfu Zhang.
Editor information
Editors and Affiliations
University of Applied Sciences Upper Austria, Wels, Austria
Michael Affenzeller
University of Applied Sciences Upper Austria, Hagenberg, Austria
Stephan M. Winkler
Leiden University, Leiden, The Netherlands
Anna V. Kononova
University of Paderborn, Paderborn, Germany
Heike Trautmann
Jožef Stefan Institute, Ljubljana, Slovenia
Tea Tušar
University of Coimbra, Coimbra, Portugal
Penousal Machado
Leiden University, Leiden, The Netherlands
Thomas Bäck
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Liu, Y., Lu, C., Lin, X., Zhang, Q. (2024). Many-Objective Cover Problem: Discovering Few Solutions to Cover Many Objectives. In: Affenzeller, M.,et al. Parallel Problem Solving from Nature – PPSN XVIII. PPSN 2024. Lecture Notes in Computer Science, vol 15151. Springer, Cham. https://doi.org/10.1007/978-3-031-70085-9_5
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-031-70084-2
Online ISBN:978-3-031-70085-9
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative