The Challenge

Over at The Panda's Thumb, Dave Thomas posted a detailed analysis of how he used a genetic algorithm (GA) to solve Steiner's Problem: Given a two-dimensional set of points, what is the most compact network of straight-line segments that connects the points?

He followed this up with an open challenge to come up with the Steiner Network for a set of six points. One week later he released the results which showed, in his words, "Evolution is Smarter than You Are."

This challenge intrigued me not only because of the math behind it but also because a GA solution directly refutes the claims of some Intelligent Design Creationists that GAs only work by sneaking in information about the solution. While some GA examples that are designed as simple teaching tools do have a single correct answer explicitly used in the fitness function, those are not representative of the capabilities of GAs in general. The Steiner Network is an excellent example of a problem where the solution is not known in advance. The fitness function rates certain characteristics of each candidate solution, it does not compare them to any expected result.

A GA Engine

My first implementation had all the code in a single file. I've since extracted the core engine into a stand-alone package and documented it separately.

The GA engine manipulates bit strings and uses tournament selection to determine parent strings. New strings are generated by crossing the parents over at a single point to create two children which are then subject to a (typically low) rate of mutation. Both parents and both children become part of the next generation.

This is a probabilistic technique — the most fit individual is not guaranteed to be selected.

The Steiner Problem Genome

The first step in using a GA to solve a problem is to define a genome to represents a candidate solution that can be evaluated by a fitness funtion. The Steiner Problem requires a way to specify the coordinates of a number of variable nodes, not all of which will necessarily be used, and the connections between any pairs of nodes, either variable or fixed.

The genome I came up with for the Steiner Problem consists of a series of bits that represent the coordinates of the variable nodes followed by bits that represent the connections between nodes (both variable and fixed). As an example, for a Steiner network that consists of three fixed nodes and up to two variable nodes, assuming that the coordinates can be represented in three bits, a candidate solution would look like this:

    000 001 010 011 1111111111
     x1  y1  x2  y2 fully connected
The coordinates of the fixed nodes are not mutable and so are not part of the genome. Only one bit is required to indicate a connection between any pair of nodes, so the last set of bits shows the connections for the pairs 4-3, 4-2, 4-1, 4-0, 3-2, 3-1, 3-0, 2-1, 2-0, 1-0, in that order. Fixed nodes are given lower indices, 0, 1, and 2 in this example.

Obviously the genome for a realistic Steiner network would be longer. The code defines the class steiner-problem, the function make-steiner-problem to create an instance of steiner-problem from a list of fixed node coordinates and maximum variable node count, and the method genome-length to compute the right size for the bit string.

The Steiner Problem Fitness Function

The fitness function for the Steiner problem is simply the total length of all the paths between connected points, with a penalty added for candidate solutions that do not connect all the nodes. That's it. No particular solution is specified by or known to the fitness function.

Evolving a Solution

During tournament selection, two bit strings are picked to be parents. Each parent is chosen by selecting two bit strings at random from the population and keeping the one with the highest fitness (the shortest length). The two parent strings are crossed at a single random point to generate two children. A mutation operator is applied to each child. Every bit in each child string has the potential to be flipped. Finally, both parent strings and both child strings are added to the next generation population. This process repeats until the next generation population is the same size as the previous population.

There are two important points to note about this process. First, the selection mechanism is stochastic; the most fit individual is not guaranteed to reproduce. In fact, in most simulation runs the best fitness for one generation will often be seen to be worse than the best in the previous generation. This is analogous to the biological world where the early bird gets the worm but the second mouse gets the cheese.

Second, mutation can affect any bit in the genomes of the children. No beneficial aspects of the parent genome are locked in.

Results

Dave Thomas provided three different Steiner problems, each with a different number of fixed nodes. I ran the GA multiple times on each.

The Four Node Network

The four node problem has fixed nodes at (0,0), (400,0), (0,300), and (400,300). The ideal Steiner network for this configuration is a "bow-tie" with two variable nodes.

I set this problem up with a maximum of five variable nodes:

    (defparameter *bow-tie-problem*
      (make-steiner-problem '((0 0) (400 0) (0 300) (400 300)) 5))
and ran the GA for 250 generations on a population of 1000 with a mutation rate of 2%:
    (solve-steiner *bow-tie-problem* 1000 250 0.02)
A typical result was a network with a total length of 919.6167 and two variable nodes at (313,150) and (87,150) — a perfect bow-tie.

The Five Node Network

The five node problem has fixed nodes at (150,0), (450,0), (0,260), (600 260), and (300,433). The ideal Steiner network for this configuration has a total length of 1212 with three variable nodes.

I set this problem up with a maximum of seven variable nodes:

    (defparameter *five-point-problem*
      (make-steiner-problem '((150 0) (450 0) (0 260) (600 260) (300 433)) 7))
and ran the GA for 250 generations on a population of 1000 with a mutation rate of 2%:
    (solve-steiner *five-point-problem* 1000 250 0.02)
A typical result was a network with a total length of 1246.6409 and one variable node at (463,339) or one with a total length of 1248.994 and four variable nodes at (185,208), (220,67), (139,221), and (323,340). Both of these are within approximately 3% of the optimum length.

The Six Node Challenge Network

The six node problem that Dave Thomas specified as the challenge has fixed nodes at (0,0), (400,0), (800,0), (0,300), (400,300), and (800,300). The Steiner solution has a total segment length of 1586.53 with four variable nodes.

I set this problem up with a maximum of nine variable nodes:

    (defparameter *panda-problem*
      (make-steiner-problem
       '((0 0) (400 0) (800 0) (0 300) (400 300) (800 300)) 9))
and ran the GA for 250 generations on a population of 1000 with a mutation rate of 2%:
    (solve-steiner *panda-problem* 1000 250 0.02)
A typical result was a network with a total length of 1678.3081 and variable nodes at (458,221), (409,29), (419,267), (457,222), and (397,295). This has one extra variable node, but the network length is within 6% of the optimum.

Letting it run for 1000 generations produced a network with a total length of 1596.2639 and variable nodes at (72,175), (313,149), (313,149), (87,149), and (730,75). Technically that's one extra node, but two of those are at the same location. That's 0.61% from the optimum. Not bad for "unintelligent" searching.

A Note On the Biological Metaphor

This GA implementation is obviously not even remotely as complex as real biological evolution. It is simply a simulation of one (important) mechanism of biological evolution, namely differential reproductive success operating on random changes to a population of genomes. By demonstrating that this mechanism can generate solutions that are not specified, or even known a priori, GAs such as this one refute the assertion that any form of supernatural (excuse me, "intelligent") intervention is required for evolution to produce novel constructs.

Unfortunately, due to disingenuous claims by creationists, including Intelligent Design proponents, it does not go without saying that neither this simulation nor actual biological evolution work via "blind chance." Mutations are indeed random; differential reproductive success is anything but.

Summary

This simulation demonstrates the ability of a simple implementation of just one evolutionary mechanism to rapidly search a solution space for a near optimal result. The spaces searched are impressively large: the solution to the five node problem requires 199 bits and that for the six node problem requires 276 bits. The total number of unique 276 bit strings is more than 1.2 x 10^83. The GA found the six node solution in 1000 generations of a population of 1000 genomes, for a total of one million (10^6) individual strings. Further, half of the strings in each generation after the first come from the previous population, so the total number of unique strings considered is at most 500,500.

As Dave Thomas emphasizes, this simulation does not specify an explicit target. The optimal and near optimal solutions emerge from random mutation and differential reproductive success, with a fitness function that ranks shorter, fully connected networks higher than longer or disconnected networks. No solution is specified, explicitly or implicitly, in the implementation.

Source Code

The code is available in two files:

This requires the GA Engine code:

Please contact me by email if you have any questions, comments, or suggestions.

www.softwarematters.org