Transcript Using a parallel approach to help evolution

Genetic Algorithms on Steroids
Using a parallel approach to help evolution along...
Asanka Herath
&
Buddhika Kottahachchi
Motivation
Genetic Algorithm's are generally slow.
•
Constrained by the dependence on randomness to
create good genes.
•
Parallelizing usually just allows the examination
of a larger set of candidates – still constrained by
randomness to provide good genes.
•
What if?
Use a different randomized but faster algorithm to
generate candidate solutions in parallel.
•
Inject these candidate solutions into the gene pool
of the Genetic Algorithm.
•
Help the fitness level of the gene pool improve
faster than with pure randomization...
•
... leads to better solutions quicker?
Problem Domain: Bin Packing Rectangles
Given a set of rectangles and the width of a bin,
determine the minimum height for a bin
containing those rectangles.
•
Only allow two orientations (ie. Horizontal &
Vertical).
•
Approach
1 Node devoted as a Coordinator.
•
Half of the others run a fast simulated annealing
algorithm (Candidate Generator).
•
The rest run independent GA's.
•
Coordinator polls for candidates and pushes them
out to the GA's between GA iterations
•
Uses C++ and MPI
•
Validation Method
60 rectangles (side length up to 100 units)
•
Hopper E. and Turton B. C. H., 2002, "An empirical study of meta-heuristics
applied to 2D rectangular bin packing" Special Issue on Cutting, Packing and
Knapsacking Problems, Studia Informatica, vol. 2, no. 1
Bin width 100 units
•
4 Nodes/16 virtual Nodes
•
50/100 GA iterations, 50 SA iterations per GA
iteration.
•
Results
Control Case vs. Test Case
Average Solution Height (2300+)
25
22.5
20
17.5
15
Control
Test
12.5
10
7.5
5
2.5
0
50 Iterations
100 Iterations
Control case runs all independent Genetic Algorithms
•Test case injects “good genes” into the Genetic Algorithms
•
Observations
Solutions generated are very close to optimal
•
(~ 10% wastage)
Small improvements required vast amounts of
computation
•
This approach on average yielded about .5%
improvement in solution quality (based on
wastage).
•
Conclusions
Given the constraints – the improvement is
significant.
•
Problem selected to test hypothesis – non-ideal?
•
This approach merits further investigation
•Other problem domains
•