Scalability of a Hybrid Extended Compact Genetic Algorithm for Ground State Optimization of Clusters

Abstract

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 Θ(n ^0.83)) with the cluster size. The total number of function evaluations (cluster energy calculations) scales sub-cubically (as Θ(n ^2.45)), which is a significant improvement over exponential scaling of poorly designed evolutionary algorithms.

Keywords:

• Cluster optimization
• Competent and efficient optimization
• Competent genetic algorithms
• Efficiency enhancement techniques
• Efficient genetic algorithms
• Extended compact genetic algorithms
• Hybridization
• Scalability analysis
• Seeding
• Silicon clusters

ACKNOWLEDGMENTS

This work was also sponsored by the Air Force Office of Scientific Research, Air Force Material Command, USAF, under grant FA9550-06-1-0096, the National Science Foundation under ITR grant DMR-03-25939 at the Materials Computation Center. The U.S. Government is authorized to reproduce and distribute reprints for government purposes notwithstanding any copyright notation thereon.

The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of the Air Force Office of Scientific Research, the National Science Foundation, or the U.S. Government.

Notes

¹Note that a BB of length k has 2 ^k possible sequences where the first sequence denotes be 00…0 and the last sequence 11…1.