Elements for the description of fitness landscapes associated with local operators for layered drawings of directed graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Chapitre D'ouvrage Année : 2004

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

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
ArticleMic01f.pdf (148.62 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00335923 , version 1 (31-10-2008)

Identifiants

  • HAL Id : inria-00335923 , version 1

Citer

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⟩
76 Consultations
248 Téléchargements

Partager

Gmail Facebook X LinkedIn More