 |
 |
 |
Circuitry Routing Using a Genetic Algorithm: Analysis
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 
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.
|
|
|
michael@obrienm.com
Last Updated: Ottawa, Canada