On the Influence of the instance structure for metaheuristic performances -- Application to a graph drawing problem

Abstract : Metaheuristics are now so common that for some classical hard combinatorial problems, there exist more than ten variants. Thus, the issue of comparing optimization methods is crucial. In this paper, we focus on one aspect of this question: the impact of the choice of the test instances on the metaheuristic performances and the possible link with the fitness landscape structure. We base our experimental framework on the arc crossing minimization problem for layered digraphs. We compare a hybridized genetic algorithm and a multistart descent which are among the best approaches to this problem. We worked on two instance families with various sizes and structural complexities: small graphs which are easy to draw on a standard size support, and large graphs specifically built for our experiments. We show that, for the smallest instances, there is no significant difference between methods whereas for graphs similar to those classically used nowadays in applications the genetic algorithm is better, and for the largest graphs (with a scaling factor up to $10^{300}$), the multistart descent is the best method. These results suggest that for ``structured'' fitness landscapes associated with real-life instances the GA exploits its implicit learning. On the other hand for very large landscapes with probably numerous local optima, only one exploration on a larger scale can be provided by local searches from a random starting point, cheap in computing effort.
Type de document :
Communication dans un congrès
IEEE Congress on Evolutionary Computation (CEC), Sep 2007, Singapour, Singapore. IEEE, pp.4684-4690, 2007, 〈10.1109/CEC.2007.4425086〉
Liste complète des métadonnées

Littérature citée [38 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00335938
Contributeur : Bruno Pinaud <>
Soumis le : vendredi 6 août 2010 - 19:29:30
Dernière modification le : jeudi 11 janvier 2018 - 06:19:29
Document(s) archivé(s) le : lundi 8 novembre 2010 - 15:06:09

Fichier

cec.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Bruno Pinaud, Pascale Kuntz. On the Influence of the instance structure for metaheuristic performances -- Application to a graph drawing problem. IEEE Congress on Evolutionary Computation (CEC), Sep 2007, Singapour, Singapore. IEEE, pp.4684-4690, 2007, 〈10.1109/CEC.2007.4425086〉. 〈inria-00335938〉

Partager

Métriques

Consultations de la notice

106

Téléchargements de fichiers

71