Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Many-Objective Cover Problem: Discovering Few Solutions to Cover Many Objectives

  • Conference paper
  • First Online:
Parallel Problem Solving from Nature – PPSN XVIII (PPSN 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 15151))

Included in the following conference series:

  • 244 Accesses

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). Given m objectives, MaCP aims to find a solution set with size k (\(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

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 169.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 79.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Ahmed, M., Seraj, R., Islam, S.M.S.: The k-means algorithm: a comprehensive survey and performance evaluation. Electronics 9(8), 1295 (2020)

    Article  Google Scholar 

  2. Blank, J., Deb, K.: Pymoo: multi-objective optimization in python. IEEE Access 8, 89497–89509 (2020)

    Article  Google Scholar 

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

    Google Scholar 

  4. Censor, Y.: Pareto optimality in multiobjective problems. Appl. Math. Optim. 4(1), 41–59 (1977)

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  6. Cheng, R., Jin, Y.: A competitive swarm optimizer for large scale optimization. IEEE Trans. Cybern. 45(2), 191–204 (2014)

    Article  Google Scholar 

  7. Cheng, R., Jin, Y.: A social learning particle swarm optimization algorithm for scalable optimization. Inf. Sci. 291, 43–60 (2015)

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  12. Cuate, O., Schütze, O.: Pareto explorer for solving real world applications. Res. Comput. Sci. 149(3), 29–36 (2020)

    Google Scholar 

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

    Article  Google Scholar 

  14. 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

  15. Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of Mathematics, pp. 439–485 (2005)

    Google Scholar 

  16. Drineas, P., Frieze, A., Kannan, R., Vempala, S., Vinay, V.: Clustering large graphs via the singular value decomposition. Mach. Learn. 56, 9–33 (2004)

    Article  Google Scholar 

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

    Google Scholar 

  18. Grandoni, F.: A note on the complexity of minimum dominating set. J. Discrete Algorithms 4(2), 209–214 (2006)

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

  20. Guerreiro, A.P., Fonseca, C.M., Paquete, L.: The hypervolume indicator: computational problems and algorithms. ACM Comput. Surv. 54(6), 1–42 (2021)

    Article  Google Scholar 

  21. Hassin, R., Levin, A.: A better-than-greedy approximation algorithm for the minimum set cover problem. SIAM J. Comput. 35(1), 189–200 (2005)

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

  25. Kennedy, J., Eberhart, R.: Particle swarm optimization. In: Proceedings of International Conference on Neural Networks, vol. 4, pp. 1942–1948 (1995)

    Google Scholar 

  26. Lambrinidis, G., Tsantili-Kakoulidou, A.: Multi-objective optimization methods in novel drug design. Expert Opin. Drug Discov. 16(6), 647–658 (2021)

    Article  Google Scholar 

  27. Laumanns, M., Thiele, L., Deb, K., Zitzler, E.: Combining convergence and diversity in evolutionary multiobjective optimization. Evol. Comput. 10(3), 263–282 (2002)

    Article  Google Scholar 

  28. Li, B., Li, J., Tang, K., Yao, X.: Many-objective evolutionary algorithms: a survey. ACM Comput. Surv. 48(1), 1–35 (2015)

    Article  Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  32. Liu, Y., Liu, J., Teng, X.: Single-particle optimization for network embedding preserving both local and global information. Swarm Evol. Comput. 71, 101069 (2022)

    Article  Google Scholar 

  33. Liu, Y., Liu, J., Wu, K.: Cost-effective competition on social networks: a multi-objective optimization perspective. Inf. Sci. 620, 31–46 (2023)

    Article  Google Scholar 

  34. Ntakolia, C., Iakovidis, D.K.: A swarm intelligence graph-based pathfinding algorithm (SIGPA) for multi-objective route planning. Comput. Oper. Res. 133, 105358 (2021)

    Article  MathSciNet  Google Scholar 

  35. Ostachowicz, W., Soman, R., Malinowski, P.: Optimization of sensor placement for structural health monitoring: a review. Struct. Health Monit. 18(3), 963–988 (2019)

    Article  Google Scholar 

  36. Owen, S.H., Daskin, M.S.: Strategic facility location: a review. Eur. J. Oper. Res. 111(3), 423–447 (1998)

    Article  Google Scholar 

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

    Article  Google Scholar 

  38. Paschos, V.T.: A survey of approximately optimal solutions to some covering and packing problems. ACM Comput. Surv. 29(2), 171–209 (1997)

    Article  Google Scholar 

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

    Google Scholar 

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

    Article  Google Scholar 

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

    Google Scholar 

  42. Wu, Q., Hao, J.K.: A review on algorithms for maximum clique problems. Eur. J. Oper. Res. 242(3), 693–709 (2015)

    Article  MathSciNet  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

  45. Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6), 712–731 (2007)

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

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

    Article  Google Scholar 

Download references

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

  1. Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong

    Yilu Liu, Chengyu Lu, Xi Lin & Qingfu Zhang

  2. City University of Hong Kong Shenzhen Research Institute, Shenzhen, China

    Yilu Liu, Chengyu Lu, Xi Lin & Qingfu Zhang

Authors
  1. Yilu Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chengyu Lu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xi Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Qingfu Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Yilu Liu or Qingfu Zhang .

Editor information

Editors and Affiliations

  1. University of Applied Sciences Upper Austria, Wels, Austria

    Michael Affenzeller

  2. University of Applied Sciences Upper Austria, Hagenberg, Austria

    Stephan M. Winkler

  3. Leiden University, Leiden, The Netherlands

    Anna V. Kononova

  4. University of Paderborn, Paderborn, Germany

    Heike Trautmann

  5. Jožef Stefan Institute, Ljubljana, Slovenia

    Tea Tušar

  6. University of Coimbra, Coimbra, Portugal

    Penousal Machado

  7. Leiden University, Leiden, The Netherlands

    Thomas Bäck

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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

  • DOI: https://doi.org/10.1007/978-3-031-70085-9_5

  • 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)

Publish with us

Policies and ethics

Search

Navigation