Kumara Sastry

Towards billion bit optimization via efficient genetic algorithms

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

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.

Related Posts:

• Towards billion bit optimization via parallel estimation of distribution algorithm
• Toward routine billion-variable optimization using genetic algorithms
• A billion bits or bust
• Evolutionary algorithms + graphical models = scalable black-box optimization
• Efficient cluster optimization using a hybrid extended compact genetic algorithm with a seeded population

2 Responses to “Towards billion bit optimization via efficient genetic algorithms”

1. David Says:
   October 5th, 2007 at 4:42 pm

   Congrats for this barrier breaking results and the best paper award at GECCO in particular and for the good job done at IlliGAL in general. I would have a small remark and some questions.

   For me it seems that in the probabilistic model update (Eq. 1) if $x_{w,i} = 0$ then the update should be $p_i^{t+1} = p_i^t - 1/n$ not + 1/n.

   Q:
   How multimodal billion-variable problems can be solved quickly, reliably and accurately? My first impression is that the parallel cGA might easily converge to a suboptimal solution in a multimodal search landscape.

   To put it more generally, if there are competing schemata in the problem, is there a way to handle them somehow with small memory requirements?

   Thanks for the answer.

   Keep up the good work!

2. Kumara Sastry Says:
   October 10th, 2007 at 2:28 am

   David,

   Thanks for the comments! Yes thats a typo. It should be minus.

   Regarding multimodal function, it depends on the type of multimodality. Note that cGA solved noisy problems. The addition of noise introduces many local optima (the global optima is not hill-climbable anymore) and cGA still is able to get to the global optima. However, if the multimodality comes from higher order building blocks, then yes cGA will converge to local optima.

   However, work is currently on-going to extend this work to develop efficient GAs that can solve million(s)-variable problems that require identification and exchange of higher order building blocks.

Leave a Reply