| HAL-Inria | Publications, software ... of Inria's scientists |
Journal articles
Minimizing crossings in a hierarchical digraphs with a hybridized genetic algorithm
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.
Cited literature [32 references]
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
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
File
GrapheGA-Tabu.pdf
Files produced by the author(s)