Towards billion bit optimization via efficient genetic algorithms
15 February 2007Sastry, 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].
Abstract:
This paper presents a highly efficient, fully parallelized implementation of the compact genetic algorithm to solve very large scale problems with millions to billions of variables. The paper presents principled results demonstrating the scalable solution of a difficult test function on instances over a billion variables using a parallel implementation of compact genetic algorithm (cGA). The problem addressed is a noisy, blind problem over a vector of binary decision variables. Noise is added equaling up to a tenth of the deterministic objective function variance of the problem, thereby making it difficult for simple hillclimbers to find the optimal solution. The compact GA, on the other hand, 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 search problems.
No comments yet