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
* Corresponding author
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
Document type :
Book sections
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download
https://hal.inria.fr/inria-00335923
Contributor : Bruno Pinaud <>
Submitted on : Friday, October 31, 2008 - 10:53:47 AM
Last modification on : Thursday, April 5, 2018 - 10:36:25 AM
Long-term archiving on : Monday, June 7, 2010 - 7:57:22 PM

File

ArticleMic01f.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

149

Files downloads

133

Contact


archive-ouverte@inria.fr