A Contribution to the Study of the Fitness Landscape for a Graph Drawing Problem

摘要: These past few years genetic algorithms and stochastic hill-climbing have received a growing interest for different graph drawing problems. This paper deals with the layered of directed graphs which is known to be an NP-complete problem arc-crossing minimization criterium. Before setting out (n+1)th comparison between meta-heuristics, we here prefer study characteristics arccrossings landscape three local transformations (greedy switching, barycenter, median) adapted from Sugiyama heuristic propose descriptive analysis two families. First, all possible layouts 2021 small are generated optima (number, type, height, attracting sets) precisely defined. Then, second family 305 larger (up 90 vertices) examined one thousand hill-climbers. highlights diversity encountered configurations gives leads choice efficient heuristics.