Circuitry Routing Using a Genetic Algorithm: Analysis

ALife Home



Genetic Algorithms

Neural Networks





Problem Statement: Is there some way that a Genetic Algorithm can optimize the layout of wires on this circuit board on the left as good or better than a human.
It took me over 30 iterations of a total of around 60 hours to layout this circuit to the point on the right.

Before solving the complete problem, we will see how the GA Router Sun Java Applet solves a simple routing problem, one with only two wires that must cross each other.
Below, are some of the top individuals (solutions) that represent a possible layout.

Generation: 0 Fitness: 11250

Generation: 9 Fitness: 15300

Generation: 560 Fitness: 16050

Generation: 840 Fitness: 16200

As we can see, the solution converges easily to a "good" solution within 9 generations for GA with the following parameters

Population: 200
Crossover: 20 %
Mutation: 0.1 %
izMaxSimulationSteps: 300
CrossoverPointEqual?: false

This GA converges too rapidly to a sub-optimal solution, it is then left up to the Mutation operator to maintain a diverse population.
We can see where the innovation in the following graph levels off as the population becomes homogeneous.
Last Updated: Ottawa, Canada

GA Router Applet Version 1 GA Router Applet Version 1 People People Artificial Life Home Artificial Life Home