EVOLUTIONARY OPTIMIZATION OF MOLECULAR CLUSTERS

Ioan Zaharie1,  Daniela Zaharie2

1Physics Department, “Politehnica” University, 
Piaţa Regina Maria, nr. 1,  300004, Timişoara izaharie@etv.utt.ro
2Computer Science Department, West University, 
bv. V. Pârvan, nr. 4, 300223, Timişoara

	Optimization of molecular clusters has as aim the identification of stable structures and is of practical importance in semiconductor industry and in structure-based drug design. Frequently used models of cluster structures are those based on potential energy functions. Different variants of potential functions, modeling structural behavior relevant to rare gases, metals and molecular clusters bound by dispersion forces, have been proposed and used in the past decades. These potential functions generate different cluster models, e.g. Lennard-Jones clusters, Morse clusters, Dzugutov clusters [1]. The problem of identifying the global minimum of the energy function is notoriously difficult, mainly due to the fact that classical optimization methods are easily trapped in local minima which correspond to metastable structures. Different methods for cluster optimization have been proposed lately. Some of them use the idea of finding the global optimum by identifying attraction regions of different optima and refining the approximation by a local search (e.g. basin hopping method [1]). Other methods, e.g. simulated annealing, are based on the idea of escaping from the local optima by accepting structure modifications which, temporarily lead to an increase of the energy. In the last decade another approach, based on evolutionary algorithms, proved to be adequate in identifying optimal structures mainly in the case of large clusters [2]. 
Evolutionary optimization is a paradigm based on the idea of using  a population of configurations, each one representing a trial structure, and evolving this population toward better configurations by applying some nature inspired operations: crossover, mutation and selection.  Despite the fact that evolutionary algorithms proved to be robust global optimization tools, difficulties (especially related with slow convergence), can arise in applying them for cluster optimization. To eliminate this problem, Deaven and Ho [2] proposed the use of  hybridization between a genetic algorithm and a local search method.  On the other hand, because of the huge number of local minima in the energy landscape in the case of large structures even the evolutionary algorithms have difficulties in identifying the global minimum. In order to reduce the risk of a premature convergence to a local minimum, the diversity of the population should be preserved. Different mechanisms for diversity preservation (e.g. sharing and crowding) have been proposed. The effect of these mechanisms is that the population will eventually contain elements grouped in regions of attractions of different optima. Starting a local search from each attraction region increases the chance of identifying the global minimum. The aim of this work is to analyze the ability of a hybrid evolutionary algorithm (obtained by combining a crowding version of differential evolution with a gradient based local search) in identifying stable clusters. Preliminary results obtained for Lennard-Jones and Morse potentials are encouraging.

References:
[1] J.K. Doye, Physical Perspectives on the Global Optimization of Atomic Clusters, in Global Optimization-Selected Case Studies, ed. J.D. Pinter, Kluwer, 2005.
[2] D.M. Deaven, K.M. Ho, Molecular Geometry Optimization with a Genetic Algorithm, Phys Rev Lett 75, pp 288, 1995