Computing Near-Optimal Solutions to the Steiner Problem in a Graph Using a Genetic Algorithm

Abstract

A new Genetic Algorithm (GA) for the Steiner Problem in a Graph (SPG) is presented. The algorithm is based on a bitstring encoding. A bitstring specifies selected Steiner vertices and the corresponding Steiner tree is computed using the Distance Network Heuristic. This scheme ensures that every bitstring correspond to a valid Steiner tree and thus eliminates the need for penalty terms in the cost function.

The GA is tested on all SPG instances from the OR-Library of which the largest graphs have 2,500 vertices and 62,500 edges. When executed 10 times on each of 58 graph examples, the GA finds the global optimum at least once for 55 graphs and every time for 43 graphs. In total the GA finds the global optimum in 77 % of all program executions and is within 1 % from the global optimum in more than 92 % of all executions.

The performance is compared to that of two branch-and-cut algorithms and one of the very best deterministic heuristics, an iterated version of the Shortest Path Heuristic (SPH-I). For all test examples but one, even the worst result ever found by the GA is equal to or better than the result of SPH-I and in many cases the average error ratio of the GA is an order of magnitude better than that of SPH-I. The runtime of the GA is moderate for all test examples. This is in contrast to SPH-I as well as the branch-and-cut algorithms, for which the runtime in some cases are extremely high.