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

The Unreasonable Effectiveness of Optimal Transport Distance in the Design of Multi-Objective Evolutionary Optimization Algorithms

  • Conference paper
  • First Online:
Numerical Computations: Theory and Algorithms (NUMTA 2023)

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

  • 121 Accesses

Abstract

Most Multi-Objective Evolutionary Algorithms (MOEAs) face significant challenges in many-objective optimization. MOEAs have random elements in the selection and crossover operators which endow them with global convergence properties. The key contribution of this paper is to integrate discrete probability distributions instead of just randomization in the design of the algorithm. This allows us to use the Wasserstein distance to drive the selection operator, instead of the Euclidean distance. Achieving balance between convergence and diversity is a key issue in evolutionary multi-objective optimization. The use of the Wasserstein distance constitutes a novel approach to the diversity management mechanism. This approach can be applied to the two main strategies: Pareto sampling, as in NSGA-II, and decomposition, as in MOEA/D, resulting in new algorithms NSGA-II/W and MOEA/D/W. The performance of the proposed algorithms is validated on a number of unconstrained and constrained benchmark problems with up to 10 objectives.

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 64.99
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

Notes

  1. 1.

    https://github.com/andreaponti5/moeadw.

  2. 2.

    https://github.com/andreaponti5/nsga2w.

References

  1. Wang, Z., Pei, Y., Li, J.: A Survey on Search Strategy of Evolutionary Multi-Objective Optimization Algorithms. Appl. Sci. 13, 4643 (2023)

    Article  MATH  Google Scholar 

  2. Zhou, H., Qiao, J.: Multiobjective optimal control for wastewater treatment process using adaptive MOEA/D. Appl. Intell. 49, 1098–1126 (2019)

    Article  MATH  Google Scholar 

  3. Konstantinidis, A., Charalambous, C., Zhou, A., Zhang, Q.: Multi-objective mobile agent-based sensor network routing using MOEA/D. In: IEEE Congress on Evolutionary Computation, pp. 1–8. IEEE (2010)

    Google Scholar 

  4. Murugeswari, R., Radhakrishnan, S., Devaraj, D.: A multi-objective evolutionary algorithm based QoS routing in wireless mesh networks. Appl. Soft Comput. 40, 517–525 (2016)

    Article  MATH  Google Scholar 

  5. Zhang, Q., Li, H., Maringer, D., Tsang, E.: MOEA/D with NBI-style Tchebycheff approach for portfolio management. In: IEEE Congress on Evolutionary Computation, pp. 1–8. IEEE (2010)

    Google Scholar 

  6. Fu, G., Kapelan, Z., Kasprzyk, J.R., Reed, P.: Optimal design of water distribution systems using many-objective visual analytics. J. Water Resour. Plan. Manag. 139, 624–633 (2013)

    Article  Google Scholar 

  7. Lygoe, R.J., Cary, M., Fleming, P.J.: A real-world application of a many-objective optimisation complexity reduction process. In: Evolutionary Multi-Criterion Optimization: 7th International Conference, EMO 2013, Sheffield, UK, March 19–22, 2013. Proceedings 7, pp. 641–655. Springer (2013)

    Google Scholar 

  8. Chikumbo, O., Goodman, E., Deb, K.: Approximating a multi-dimensional Pareto front for a land use management problem: A modified MOEA with an epigenetic silencing metaphor. In: 2012 IEEE congress on evolutionary computation, pp. 1–9. IEEE (2012)

    Google Scholar 

  9. Bacardit, J., Brownlee, A.E., Cagnoni, S., Iacca, G., McCall, J., Walker, D.: The intersection of evolutionary computation and explainable AI. In: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 1757–1762 (2022)

    Google Scholar 

  10. Candelieri, A., Perego, R., Archetti, F.: Green machine learning via augmented Gaussian processes and multi-information source optimization. Soft Comput., 1–13 (2021)

    Google Scholar 

  11. Fadaee, M., Radzi, M.A.M.: Multi-objective optimization of a stand-alone hybrid renewable energy system by using evolutionary algorithms: A review. Renew. Sustain. Energy Rev. 16, 3364–3369 (2012)

    Article  MATH  Google Scholar 

  12. Candelieri, A., Ponti, A., Giordani, I., Bosio, A., Archetti, F.: Distributional learning in multi-objective optimization of recommender systems. J. Ambient Intell. Human. Comput., 1–17 (2022)

    Google Scholar 

  13. Ishibuchi, H., Tsukamoto, N., Nojima, Y.: Evolutionary many-objective optimization: a short review. In: 2008 IEEE Congress on Evolutionary Computation IEEE World Congress on Computational Intelligence, pp. 2419–2426. IEEE (2008)

    Google Scholar 

  14. Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6, 182–197 (2002). https://doi.org/10.1109/4235.996017

    Article  MATH  Google Scholar 

  15. Zitzler, E., Laumanns, M., Thiele, L.: SPEA2: improving the strength Pareto evolutionary algorithm. TIK-report 103, (2001)

    Google Scholar 

  16. Monge, G.: Mémoire sur la théorie des déblais et des remblais. Mem. Math. Phys. Acad. Royale Sci., 666–704 (1781)

    Google Scholar 

  17. Kantorovich, L.: On the transfer of masses. In: Doklady Akademii Nauk, pp. 227–229 (1942) (in Russian)

    Google Scholar 

  18. Villani, C.: Optimal transport: old and new. Springer Science & Business Media (2008)

    Google Scholar 

  19. Peyré, G., Cuturi, M.: Computational optimal transport. arXiv preprint arXiv:1803.00567 (2020)

  20. Bonneel, N., Peyré, G., Cuturi, M.: Wasserstein Barycentric coordinates: histogram regression using optimal transport. ACM Trans. Graph. 35, 71–81 (2016)

    Article  MATH  Google Scholar 

  21. Vayer, T., Chapel, L., Flamary, R., Tavenard, R., Courty, N.: Optimal Transport for structured data with application on graphs. arXiv preprint arXiv:1805.09114. (2018)

  22. Huang, G., Quo, C., Kusner, M.J., Sun, Y., Weinberger, K.Q., Sha, F.: Supervised word mover’s distance. In: Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 4869–4877 (2016)

    Google Scholar 

  23. Ponti, A., Candelieri, A., Archetti, F.: A Wasserstein distance based multiobjective evolutionary algorithm for the risk aware optimization of sensor placement. Intell. Syst. Appl. 10, (2021)

    Google Scholar 

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

    Article  MATH  Google Scholar 

  25. Li, K., Fialho, A., Kwong, S., Zhang, Q.: Adaptive operator selection with bandits for a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 18, 114–130 (2013)

    Article  MATH  Google Scholar 

  26. Sindhya, K., Miettinen, K., Deb, K.: A hybrid framework for evolutionary multi-objective optimization. IEEE Trans. Evol. Comput. 17, 495–511 (2012)

    Article  MATH  Google Scholar 

  27. Li, K., Zhang, Q., Kwong, S., Li, M., Wang, R.: Stable matching-based selection in evolutionary multiobjective optimization. IEEE Trans. Evol. Comput. 18, 909–923 (2013)

    MATH  Google Scholar 

  28. Giagkiozis, I., Fleming, P.J.: Methods for multi-objective optimization: an analysis. Inf. Sci. 293, 338–350 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  29. Li, H., Deb, K., Zhang, Q., Suganthan, P.N., Chen, L.: Comparison between MOEA/D and NSGA-III on a set of novel many and multi-objective benchmark problems with challenging difficulties. Swarm Evol. Comput. 46, 104–117 (2019)

    Article  Google Scholar 

  30. Li, K., Deb, K., Zhang, Q., Kwong, S.: An evolutionary many-objective optimization algorithm based on dominance and decomposition. IEEE Trans. Evol. Comput. 19, 694–716 (2014)

    Article  MATH  Google Scholar 

  31. Ishibuchi, H., Hitotsuyanagi, Y., Tsukamoto, N., Nojima, Y.: Many-objective test problems to visually examine the behavior of multiobjective evolution in a decision space. In: Parallel Problem Solving from Nature, PPSN XI: 11th International Conference, Kraków, Poland, September 11–15, 2010, Proceedings, Part II 11, pp. 91–100. Springer (2010)

    Google Scholar 

  32. Ishibuchi, H., Akedo, N., Nojima, Y.: Relation between neighborhood size and MOEA/D performance on many-objective problems. In: Evolutionary Multi-Criterion Optimization: 7th International Conference, EMO 2013, Sheffield, UK, March 19–22, 2013. Proceedings 7. pp. 459–474. Springer (2013)

    Google Scholar 

  33. 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, 577–601 (2013)

    Article  MATH  Google Scholar 

  34. Adra, S.F., Fleming, P.J.: Diversity management in evolutionary many-objective optimization. IEEE Trans. Evol. Comput. 15, 183–195 (2010)

    Article  MATH  Google Scholar 

  35. Knowles, J.D.: ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems. IEEE Trans. Evol. Comput. 10, 50–66 (2006). https://doi.org/10.1109/TEVC.2005.851274

    Article  MATH  Google Scholar 

  36. Liu, J., Wang, Y., Sun, G., Pang, T.: Solving highly expensive optimization problems via evolutionary expected improvement. IEEE Trans. Syst. Man Cybern. Syst. (2023)

    Google Scholar 

  37. Lin, X., Zhen, H.-L., Li, Z., Zhang, Q., Kwong, S.: A batched scalable multi-objective Bayesian optimization algorithm. arXiv preprint arXiv:1811.01323 (2018)

  38. Konakovic Lukovic, M., Tian, Y., Matusik, W.: Diversity-guided multi-objective Bayesian optimization with batch evaluations. Adv. Neural. Inf. Process. Syst. 33, 17708–17720 (2020)

    Google Scholar 

  39. Lin, X., Yang, Z., Zhang, X., Zhang, Q.: Pareto set learning for expensive multi-objective optimization. arXiv preprint arXiv:2210.08495 (2022)

  40. Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press (2004)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Economics, Management and Statistics, University of Milano-Bicocca, Milan, Italy

    Andrea Ponti

  2. Department of Computer Science, Systems and Communication, University of Milano-Bicocca, Milan, Italy

    Francesco Archetti

Authors
  1. Andrea Ponti
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Francesco Archetti
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Andrea Ponti .

Editor information

Editors and Affiliations

  1. University of Calabria, Rende, Italy

    Yaroslav D. Sergeyev

  2. University of Calabria, Rende, Italy

    Dmitri E. Kvasov

  3. University of Calabria, Rende, Italy

    Annabella Astorino

Rights and permissions

Reprints and permissions

Copyright information

© 2025 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

Ponti, A., Archetti, F. (2025). The Unreasonable Effectiveness of Optimal Transport Distance in the Design of Multi-Objective Evolutionary Optimization Algorithms. In: Sergeyev, Y.D., Kvasov, D.E., Astorino, A. (eds) Numerical Computations: Theory and Algorithms. NUMTA 2023. Lecture Notes in Computer Science, vol 14476. Springer, Cham. https://doi.org/10.1007/978-3-031-81241-5_11

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-81241-5_11

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-81240-8

  • Online ISBN: 978-3-031-81241-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation