Unbalanced Mallows Models for Optimizing Expensive Black-Box Permutation Problems - Equipe Signal, Statistique et Apprentissage Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Unbalanced Mallows Models for Optimizing Expensive Black-Box Permutation Problems

Résumé

Expensive black-box combinatorial optimization problems arise in practice when the objective function is evaluated by means of a simulator or a real-world experiment. Since each fitness evaluation is expensive in terms of time or resources, the number of possible evaluations is typically several orders of magnitude smaller than in non-expensive problems. Classical optimization methods are not useful in this scenario. In this paper, we propose and analyze UMM, an estimation-of-distribution (EDA) algorithm based on a Mallows probabilistic model and unbalanced rank aggregation (uBorda). Experimental results on black-box versions of LOP and PFSP show that UMM outperforms the solutions obtained by CEGO, a Bayesian optimization algorithm for combinatorial optimization. Nevertheless, a slight modification to CEGO, based on the different interpretations for rankings and orderings, significantly improves its performance, thus producing solutions that are slightly better than those of UMM and dramatically better than the original version. Another benefit of UMM is that its computational complexity increases linearly with both the number of function evaluations and the permutation size, which results in computation times an order of magnitude shorter than CEGO, making it specially useful when both computation time and number of evaluations are limited. CCS CONCEPTS • Mathematics of computing → Combinatorial optimization; • Theory of computation → Random search heuristics.
Fichier principal
Vignette du fichier
main.pdf (5.63 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03224929 , version 1 (12-05-2021)

Identifiants

Citer

Ekhine Irurozki, Manuel López-Ibáñez. Unbalanced Mallows Models for Optimizing Expensive Black-Box Permutation Problems. The Genetic and Evolutionary Computation Conference (GECCO21), Jul 2021, Lille, France. ⟨10.1145/3449639.3459366⟩. ⟨hal-03224929⟩
109 Consultations
91 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More