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
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))
(solve-steiner *bow-tie-problem* 1000 250 0.02)
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))
(solve-steiner *five-point-problem* 1000 250 0.02)
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))
(solve-steiner *panda-problem* 1000 250 0.02)
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.