A novel framework to construct quality indicators using the linear assignment problem

• Diana Cristina Valencia-Rodríguez ^[1] ; Carlos A. Coello Coello ^[1]
  1. [1] Departamento de Computación, CINVESTAV-IPN, Mexico
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 33, Nº. Extra 2, 2025 (Ejemplar dedicado a: Metaheuristics), págs. 378-394
• Idioma: inglés
• DOI: 10.1007/s11750-024-00693-9
• Enlaces
  • Texto completo
• Resumen

  • In multi-objective optimization problems (MOPs), we aim to simultaneously find the maximum or minimum values of two or more (often conflicting) objective functions. MOPs are often found in real-world applications and, consequently, many methods have been proposed to solve them. Multi-Objective Evolutionary Algorithms (MOEAs) are popular techniques to solve MOPs due to their ease of use and their generality. Assessing the performance of MOEAs has become increasingly important due to the high number of MOEAs that have been developed in recent years. This work presents a novel framework for creating quality indicators using the linear assignment problem. In addition, we introduce two novel quality indicators generated using this framework and present examples to validate their performance. Furthermore, we present a novel algorithm called MOEA-kAP that can incorporate any indicator generated using our proposed framework as a density estimator. Our experimental results show that MOEA-kAP outperforms state-of-the-art algorithms.

• Referencias bibliográficas
  • Audet C, Bigeon J, Cartier D et al (2021) Performance indicators in multiobjective optimization. Eur J Oper Res 292(2):397–422. https://doi.org/10.1016/j.ejor.2020.11.016
  • Bai GZ (2009) A new algorithm for k-cardinality assignment problem. In: 2009 International Conference on Computational Intelligence and Software...
  • Beume N, Fonseca CM, Lopez-Ibanez M et al (2009) On the complexity of computing the hypervolume indicator. IEEE Trans Evol Comput 13(5):1075–1082
  • Branke J, Deb K (2005) Integrating user preferences into evolutionary multi-objective optimization. In: Jin Y (ed) Knowledge incorporation...
  • Burkard RE, Dell’Amico M, Martello S (2012) Assignment problems. Other titles in applied mathematics, society for industrial and applied mathematics,...
  • Coello Coello CA, Reyes Sierra M (2004) A study of the parallelization of a coevolutionary multi-objective evolutionary algorithm. In: Monroy...
  • Coello Coello CA, Lamont GB, Van Veldhuizen DA (2007) Evolutionary algorithms for solving multiobjective problems. 2nd edn. Springer, New...
  • Das I, Dennis JE (1998) Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization...
  • Deb K (2001)Multi-Objective Optimization using Evolutionary Algorithms. JohnWiley & Sons, Chichester, UK, iSBN 0-471-87339-X
  • Deb K, Jain H (2014) An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part...
  • Deb K, Thiele L, Laumanns M et al (2005) Scalable test problems for evolutionary multiobjective optimization. In: Abraham A, Jain L, Goldberg...
  • Dell’Amico M, Martello S (1997) The k-cardinality assignment problem. Discrete Applied Mathematics 76(1):103–121. https://doi.org/10.1016/S0166-218X(97)00120-0,...
  • Fleischer M (2003) The Measure of Pareto Optima. Applications to multi-objective metaheuristics. In: Fonseca CM, Fleming PJ, Zitzler E, et...
  • Hardin D, Saff E (2004) Discretizing manifolds via minimum energy points. Not Am Math Soc 51(10):1186– 1194
  • Ishibuchi H, Masuda H, Tanigaki Y, et al (2015) Modified distance calculation in generational distance and inverted generational distance....
  • Kuhn HW (1955) The hungarian method for the assignment problem. Naval Res Logist Q 2(1–2):83–97. https://doi.org/10.1002/nav.3800020109
  • Li M, Yao X (2019) Quality evaluation of solution sets in multiobjective optimisation: a survey. ACM Comput Surv 52(2):1–38
  • Miettinen K (1999) Nonlinear multiobjective optimization, international series in operations research & management science, vol 12. Kluwer...
  • Molinet Berenguer JA, Coello Coello CA (2015) Evolutionary many-objective optimization based on Kuhn– Munkres’ algorithm. In: Gaspar-Cunha...
  • Munkres J (1957) Algorithms for the assignment and transportation problems. J Soc Ind Appl Math 5(1):32– 38. https://doi.org/10.1137/0105003
  • Qingfu Z, Hui L (2007) MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans Evol Comput 11(6):712–731. https://doi.org/10.1109/TEVC.2007.892759
  • Storn R, Price K (1997) Differential evolution—a simple and efficient heuristic for global optimization over continuous spaces. J Global Optim...
  • Tutum CC, Deb K (2015) A multimodal approach for evolutionary multi-objective optimization (memo): proof-of-principle results. In: Gaspar-Cunha...
  • Valencia-Rodríguez DC, Coello Coello CA (2023) A novel performance indicator based on the linear assignment problem. In: Emmerich M, Deutz...
  • Zitzler E (1999) Evolutionary algorithms for multiobjective optimization: methods and applications. PhD thesis, Swiss Federal Institute of...
  • Zitzler E, Thiele L, Laumanns M et al (2003) Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol...