A Hybrid Evolutionary Algorithm for
the Rectilinear Steiner Problem

Bryant A. Julstrom
Department of Computer Science
St. Cloud State University
720 Fourth Avenue South
St. Cloud, MN 56301 USA
julstrom@eeyore.stcloudstate.edu

Abstract

One form of hybrid evolutionary algorithm encodes solutions to its target problem as permutations of the problem's elements. A greedy heuristic assembles the solution a permutation represents by appending the problem's elements to the solution in the order the permutation specifies. The algorithm searches the problem's solution space by searching the space of permutations. A hybrid genetic algorithm for the rectilinear Steiner problem encodes candidate trees as permutations of the terminal points, each labeled positive or negative. A decoder based on Prim's algorithm builds the tree such a genotype represents; each symbol's sign (except the first) indicates a pair of rectilinear edges associated with a spanning tree edge. A second GA encodes candidate trees directly as pairs of rectilinear edges, each associated with a spanning tree edge. The algorithms are compared on twenty sets of terminals. The hybrid algorithm returns decisively better results on the larger instances, though its performance still deteriorates as the number of terminals grows.