|
|
|
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