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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [38 references]  Display  Hide  Download

https://hal.inria.fr/inria-00335938
Contributor : Bruno Pinaud <>
Submitted on : Friday, August 6, 2010 - 7:29:30 PM
Last modification on : Thursday, April 5, 2018 - 10:36:25 AM
Long-term archiving on : Monday, November 8, 2010 - 3:06:09 PM

File

cec.pdf
Files produced by the author(s)

Identifiers

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), IEEE, Sep 2007, Singapour, Singapore. pp.4684-4690, ⟨10.1109/CEC.2007.4425086⟩. ⟨inria-00335938⟩

Share

Metrics

Record views

129

Files downloads

85