Scalability of a hybrid extended compact genetic algorithm for ground state optimization of clusters
4 June 2007Sastry, K., Goldberg, D. E., Johnson, D. D. (2007). Materials and Manufacturing Processes, 22(5), 570-576. [Full Paper - DOI].
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 Θ(n0.83)) with the cluster size. The total number of function evaluations (cluster energy calculations) scales sub-cubically (as Θ(n2.45)), which is a significant improvement over exponential scaling of poorly designed evolutionary algorithms.
No comments yet