Abstract : Producing clear and intelligible layouts of hierarchical digraphs knows a renewed interest in information visualization. Recent experimental results show that metaheuristics are well-adapted methods for this problem. In this paper, we develop a new Hybridized Genetic Algorithm for arc crossing minimization. It follows the basic scheme of a GA with two major differences: problem-based crossovers adapted from ordering GAs are combined with a local search strategy based on averaging heuristics. Computational testing was performed on a set of 180 random hierarchical digraphs of standard sizes with various structures. Results show that the Hybridized Genetic Algorithm significantly outperforms Tabu Search -which is one of the best known methods for this problem- and also a multi-start descent except for highly connected graphs.
https://hal.inria.fr/inria-00335904
Contributor : Bruno Pinaud
<>
Submitted on : Friday, October 31, 2008 - 10:34:30 AM
Last modification on : Thursday, April 5, 2018 - 10:36:25 AM
Long-term archiving on : Monday, June 7, 2010 - 10:31:04 PM
Pascale Kuntz, Bruno Pinaud, Rémi Lehn. Minimizing crossings in a hierarchical digraphs with a hybridized genetic algorithm. Journal of Heuristics, Springer Verlag, 2006, 12 (1-2), pp.23-36. ⟨10.1007/s10732-006-4296-7⟩. ⟨inria-00335904⟩
