Solving the graphical Steiner tree problem using genetic algorithms

The authors develop a genetic algorithm (GA) to solve the Steiner Minimal Tree problem in graphs. To apply the GA paradigm, a simple bit string representation is used, where a 1 or 0 corresponds to whether or not a node is included in the solution tree. The standard genetic operators-selection, crossover and mutation-are applied to both random and seeded initial populations of representations. Various parameters within the algorithm have to be set and the authors discuss how and why they have selected the values used. A standard set of graph problems used extensively in the comparison of Steiner tree algorithms has been solved using the present resulting algorithm. The authors report their results (which are encouragingly good) and draw conclusions.