Toward routine billion-variable optimization using genetic algorithms
18 January 2007Goldberg, D. E., Sastry, K., Llorà X. (2007) Complexity, 12(3), 27—29. [Full paper-PDF] [Press release].
Abstract:
The push for better understanding and design of complex systems requires the solution of challenging optimization problems with large numbers of decision variables. This note presents principled results demonstrating the scalable solution of a difficult test function on instances over a billion variables using a parallel implementation of a genetic algorithm (GA). The problem addressed is a noisy, blind problem over a vector of binary decision variables. Noise is added equaling a tenth of the deterministic objective function variance of the problem, thereby making it difficult for simple hillclimbers to find the optimal solution. The genetic algorithm used - the compact GA - is able to find the optimum in the presence of noise quickly, reliably, and accurately, and the solution scalability follows known convergence theories. These results on noisy problem together with other results on problems involving varying modularity, hierarchy, and overlap foreshadow routine solution of billion-variable problems across the landscape of complexity science.
3 Responses to “Toward routine billion-variable optimization using genetic algorithms”
February 6th, 2007 at 1:05 pm
Hello!
Congratulations for all three researchers involved with that over one billion variable problem.
If you permit me, I have some questions about that:
1 - Is the problem decomposable?
2 - Why use binary decision variables which, without noise, can assume only two values/states?
3 - Is the cGA rotationally invariant?
4 - Would be possible to rotate the coordinate system of the variables?
5 - Is that problem some modification of the OneMax?
6 - What kind of random variable that added noise is?
7 - How does that noise increase the problem difficulty?
Thanks!
Marcelo
February 8th, 2007 at 6:54 am
First of all Congrats to all the three researchers. Great Job Kumar.
As a genetic engineer am really excited to see that billion variable handling.
Thanks and regards
KATHIRVEL M.
June 26th, 2007 at 9:13 pm
[…] Sastry, K., Goldberg, D. E., Llorà, X. (2007). IlliGAL Report No. 2007007. University of Illinois at Urbana-Champaign, Urbana IL. [Full paper - PDF] [Full paper - PS]. [Also see the following paper in the journal complexity]. […]