Elements for the description of fitness landscapes associated with local operators for layered drawings of directed graphs

Pascale Kuntz 1 Bruno Pinaud 1, * Rémi Lehn 1
* Auteur correspondant
1 LINA - Laboratoire d'Informatique de Nantes Atlantique
Abstract : Minimizing arc crossings for drawing acyclic digraphs is a well-known NP-Complete problem for which several local-search approaches based onlocal transformations (switching, median ,...) have been proposed. Their adaptations have been recently included in different metaheuristics.As an attempt to better understand the dynamic of the search processes, we study the fitness landscapes associated with these transformations. We first resort to a set of multi-start descents to sample the search space for three hundred medium-sized graphs. Then, we investigate complete fitness landscapes for a set of 1875 smaller graphs, this aims at showing some instance characteristics that influence search strategies. The underlying idea is to consider a fitness landscape as a graph whose vertices are drawings and arcs representing a transformation of a drawing into another. We confirm that the properties of basins of attraction closely depend on the instances. Also, we show that the probability of being stuck on a local optimum is linked to the specific shapes of the basins of attraction of global optima which may be very different from the regular image of the continuous case generally used as a reference.
Keywords : layered digraph drawing fitness landscape metaheuristics local search
Type de document :
Chapitre d'ouvrage
M.G.C. Resende and J.P. de Sousa. Metaheuristics: Computer Decision-Making, 86, Kluwer Academic Publisher, pp.405-420, 2004, Applied optimization, 1402076533
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00335923
Contributeur : Bruno Pinaud <>
Soumis le : vendredi 31 octobre 2008 - 10:53:47
Dernière modification le : jeudi 5 avril 2018 - 10:36:25
Document(s) archivé(s) le : lundi 7 juin 2010 - 19:57:22

Fichier

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

Identifiants

  • HAL Id : inria-00335923, version 1

Collections

UNIV-NANTES | LINA | LINA-COD

Citation

Pascale Kuntz, Bruno Pinaud, Rémi Lehn. Elements for the description of fitness landscapes associated with local operators for layered drawings of directed graphs. M.G.C. Resende and J.P. de Sousa. Metaheuristics: Computer Decision-Making, 86, Kluwer Academic Publisher, pp.405-420, 2004, Applied optimization, 1402076533. 〈inria-00335923〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

133

Téléchargements de fichiers

85

Contact


archive-ouverte@inria.fr