A Genetic Algorithm for Restricted Cases of the Rectilinear Steiner Problem with Obstacles

摘要

Given a collection of points and obstacles in the plane, the rectilinear Steiner problem with obstacles seeks a shortest tree made up of vertical and horizontal line segments that connects the points and does not intersect the obstacles. Here, rectangular obstacles are aligned with the coordinate axes, and each point can be connected to at least one other, and thus to the tree, by at most one vertical and one horizontal segment. A genetic algorithm for the problem encodes candidate trees as spanning trees augmented with specifications of one vertical and one horizontal segment for each spanning tree edge. The GA 's operators and a greedy heuristic for the problem imitate Kruskal's algorithm. In tests of the GA and the greedy heuristic on 45 instances of the restricted rectilinear Steiner problem with obstacles, the mean length of the trees the genetic algorithm found was always less than the length of the greedy heuristic's tree. However, the coding by which the genetic algorithm represents candidate trees cannot represent the problem's entire search space, which in general contains shorter trees. Searching this larger space requires a coding of rectilinear Steiner trees that is not based on spanning trees.