Practical Approach To Structure Prediction Of Atomic Clusters-High-Performance Heuristic Algorithms

The geometrical structure of an atomic or molecular cluster is one of the most fundamental properties, which directly determines the physical and chemical properties of the cluster. Thus, the determination of the ground state structures of the clusters usually becomes the first step of the cluster studies. On the other hand, this problem has been in theory proved to be NP-hard problem due to the fact that the number of the possible structures exponentially increases with the cluster size.It is commonly believed that for NP-hard problems there does not exist any exact solution algorithm with polynomial time complexity. In this context, various heuristics algorithms are proposed by many researchers from different fields. Heuristic algorithms are not able to guarantee to reach the globally optimal solutions but are able to generate some sub-optimal solutions that satisfy the requirements of practical appications within reasonable computational time, thus becoming the practial approaches to solve a number of NP-hard problems encountered in practical applications.This paper presents four heuristic algorithms for the optimization of three kinds of atomic clusters, namely Lennard-Jones (LJ) clusters, metal clusters and bimetallic clusters. LJ clusters consist of identical atoms interacting via the LJ pair potential. Due to the simplicity of the function form, LJ clusters become popular benchmarks for evaluating the performance of the newly developed cluster optimization methods. However, LJ potential can only describe the interactions between the heavy inert gases cluster atoms. For other atomic clusers like metal and bimetallic clusters, the many-body potentials widely used by researchers from chemistry and physics are more exact for modelling the interactions between cluster atoms. Therefore, in this study we use many-body Gupta poetential to model the metal and bimetallic clusters.For the optimization of LJ clusters, a hybrid heuristic algorithm is proposed, which combines the interior operator, the two-stage local minimization and the dynamic lattice search method. At the beginning of the algorithm, the interior operator gradually decreases the energy of the cluster and makes the configuration of the cluster more ordered by moving some high-energy surface atoms to the interior of the cluster; and the two-stage local minimization leads the search to more promising region of the search space, thus greatly increasing the success rate of the algorithm. At the second stage of the algorithm, an efficient heuristic algorithm called the dynamic lattice search method is used to optimize the positions of the surface atoms, further reducing the energy of the cluster. The proposed algorithm was tested on the LJ clusters in the size range of N<680, and the computational results show that the algorithm is quite competitive relative to the best performing algorithms from the literature and the putative global minimum strucutures were improved for LJ533and LJ536. In addition, in order to reduce the bias of the algorithm, a variate of the present algorithm is also propsed, and computational results shows its efficacy.In order to optimize metal clusters described by the Gupta many-body potential, we have proposed an improved dynamic lattice search method. In the previous literature, the dynamic lattice search method was applied to optimize Ag clusters, where a traditional definition for the energy of a single atom is adopted. However, computational results show that the dynamic lattice search method with the traditional definition of the atomic energy is not competitive. In order to make the dynamic lattice search method more efficient for the optimization of metal clusters, an improved version of dynamic lattice search method is proposed, where a new definition of the atomic energy is used. Extensive computational experiments show that the improved version of the dynamic lattice search method is superior to the previous one for the optimization of metal clusters and a large number of new putative global minimum structures are found for the considered clusters.Geometry optimization of bimetallic clusters involves continuous optimization that aims at finding the best geometry and combinatorial optimization that aims at seeking for the best arrangement for two kinds of atoms when the geometry is fixed. In this paper, we have designed a heuristic algorithm by taking into account the problem-specific knowledge, where three kinds of operations have been jointly used, i.e., monotonic basin-hopping algorithm (MBH), surface optimization operator, iterated local search method. Through the optimization for three kinds of bimetallic clusters, the proposed algorithm finds a number of new putative global minimum structures and confirms the previously putative global minimum strucutures for the remaining clusters. Moreover, the algorithm is obviously superior to those algorithms from the literature in terms of computational speed. These results clearly demonstrate the effictiveness and the search capacity of the algorithm.In conclusion, the present study shows that heuristic algorithms are highly effective for the optimization of atomic clusters. There are some promising derections to extend the present study, such as a combination of heuristic algorithm with evolutionary algorithm. The future study will be devoted to the design of highly effective heuristic algorithms for the optimization of atomic cluster.