COMPUTING NEAR-OPTIMAL SOLUTIONS TO THE STEINER PROBLEM IN A GRAPH USING A GENETIC ALGORITHM

A new genetic algorithm (GA) for the Steiner Problem in a Graph (SPG) is presented. The algorithm is based on a bitstring encoding of selected Steiner vertices and the corresponding Steiner tree is computed using a deterministic SPG heuristic. The GA is tested on all SPG instances from the OR-Library having from 500 to 2500 vertices and up to 62,500 edges. For these graphs, the algorithm finds a global optimum in 70% of all program executions and is within 1% from the global optimum value in 90% of all executions. The performance is compared to that of two branch-and-cut algorithms and two of the very best deterministic heuristics: an iterated version of the Takahashi and Matsuyama heuristic (ITM) and an iterated version of the Kou, Markowsky, and Berman heuristic (IKMB). In almost all cases, even the worst result ever found by the GA is equal to or better than the best result of ITM and IKMB. Furthermore, while none of the deterministic heuristics or the branch-and-cut algorithms are capable of solving all problem instances within a reasonable time limit, the GA finds a near-optimal solution to every problem in a moderate amount of time. (C) 1995 John Wiley & Sons, Inc.