Minimizing crossings in hierarchical digraphs with a hybridized genetic algorithm

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.