Abstract
Given a set of points in the Euclidean plane the Steiner Minimal Tree problem seeks a minimal cost collection of edges spanning the given points. A generalization of this problem is introduced in which the Euclidean plane is partitioned into hexagonal cells, each having an associated cost to traverse. The goal is to minimize the cost required to span the given points in this non-uniform metric. A genetic algorithm is described which builds Steiner trees by combining full components from two participant Steiner trees. The solution quality is compared against standard library instances, for which optimal solutions are known, and random instances. The results show that the genetic algorithm generates high quality solutions.