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
Contributeur : Bruno Pinaud
<>
Soumis le : vendredi 31 octobre 2008 - 10:34:30
Dernière modification le : jeudi 5 avril 2018 - 10:36:25
Document(s) archivé(s) le : lundi 7 juin 2010 - 22:31:04
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〉
