| HAL-Inria | Publications, software ... of Inria's scientists |
Book sections
Elements for the description of fitness landscapes associated with local operators for layered drawings of directed graphs
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.
Cited literature [22 references]
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
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)