Scalability of a hybrid extended compact genetic algorithm for ground state optimization of clusters

We analyze the utility and scalability of extended compact genetic algorithm (eCGA)-a genetic algorithm (GA) that automatically and adaptively mines the regularities of the fitness landscape using machine learning methods and information theoretic measures-for ground state optimization of clusters. In order to reduce the computational time requirements while retaining the high reliability of predicting near-optimal structures, we employ two efficiency-enhancement techniques: (1) hybridizing eCGA with a local search method, and (2) seeding the initial population with lowest energy structures of a smaller cluster. The proposed method is exemplified by optimizing silicon clusters with 4-20 atoms. The results indicate that the population size required to obtain near-optimal solutions with 98% probability scales sub linearly (as Theta(n(0.83))) with the cluster size. The total number of function evaluations (cluster energy calculations) scales sub-cubically (as Theta(n(2.45))), which is a significant improvement over exponential scaling of poorly designed evolutionary algorithms.