Weight-biased edge-crossover in evolutionary algorithms for two graph problems
Bryant A. Julstrom, Günther Robert Raidl · 2001
Many optimization problems on weighted graphs seek a subset of the graph's edges that has minimum weight and satisfies the problem's constraints. Two examples are the traveling salesman problem (TSP) and the degree-constrained minimum spanning tree problem (d-MSTP). Heuristics like evolutionary algorithms often construct candidate solutions to such problems iteratively, repeatedly including an edge selected from those currently eligible. Not surprisingly, low weight edges usually predominate in good and optimal solutions, an observation we confirm empirically for the TSP and the d-MSTP. This suggests that any process that builds candidate solutions should, with higher probability, select edges of lower weight. We incorporate into crossover operators and compare in a genetic algorithm four edge-selection techniques: random, greedy, according to probabilities inversely proportional to the edges' weights, and 2-tournament. Tests on instances of the TSP and the d-MSTP indicate that with the weight-biased techniques, the GA identifies better solutions faster than with random edge-selection.