A dynamic lattice searching method for fast optimization of Lennard-Jones clusters

A highly efficient unbiased global optimization method called dynamic lattice searching (DLS) was proposed. The method starts with a randomly generated local minimum, and finds better solution by a circulation of construction and searching of the dynamic lattice (DL) until the better solution approaches the best solution. The DL is constructed adaptively based on the starting local minimum by searching the possible location sites for an added atom, and the DL searching is implemented by iteratively moving the atom located at the occupied lattice site with the highest energy to the vacant lattice site with the lowest energy. Because the DL can greatly reduce the searching space and the number of the time-consuming local minimization procedures, the proposed DLS method runs at a very high efficiency, especially for the clusters of larger size. The performance of the DLS is investigated in the optimization of Lennard-Jones (LJ) clusters up to 309 atoms, and the structure of the LJ(500) is also predicted. Furthermore, the idea of dynamic lattice can be easily adopted in the optimization of other molecular or atomic clusters. It may be a promising approach to be universally used for structural optimizations in the chemistry field.     

Gravitational smoothing as a global optimization strategy

An optimization scheme for atomic cluster structures, based on exaggerating the importance of the gravitational force, is introduced. Results are presented for calculations on Lennard-Jones clusters of 13, 38, and 55 atoms, and the 13-atom Morse cluster.     

Composition-induced structural transitions in mixed Lennard-Jones clusters: global reparametrization and optimization

As extended benchmarks to global cluster structure optimization methods, we provide a first systematic point of entry into the world of strongly mixed rare gas clusters. A new set of generalized Lennard-Jones pair potentials is generated for this purpose, by fitting them to high-end ab initio reference data. Employing these potentials in our genetic algorithm-based global structure optimization framework, we examined various systems from binary to quinary mixtures of atom types. A central result from this study is that the famous fcc structure for 38 atoms can survive for certain binary mixtures but appears to be prone to collapsing into the dominating icosahedral structure, which we observed upon introduction of one single atom of a ternary type.     

Comparing search strategies for finding global optima on energy landscapes

We provide some tests of the convex global underestimator (CGU) algorithm, which aims to find global minima on funnel-shaped energy landscapes. We use two different potential functions—the reduced Lennard–Jones cluster potential, and the modified Sun protein folding potential, to compare the CGU algorithm with the simplest versions of the traditional trajectory-based search methods, simulated annealing (SA), and Monte Carlo (MC). For both potentials, the CGU reaches energies lower on the landscapes than both SA and MC, even when SA and MC are given the same number of starting points as in a full CGU run or when all methods are given the same amount of computer time. The CGU consistently finds the global minima of the Lennard–Jones potential for all cases with up to at least n=30 degrees of freedom. Finding the global or near-global minimum in the CGU method requires polynomial time [scaling between O(n³) and O(n⁴)], on average. ©1999 John Wiley & Sons, Inc. J Comput Chem 20: 1527–1532, 1999     

Combining genetic algorithm and simulated annealing: a molecular geometry optimization study

We introduce a new hybrid approach to determine the ground state geometry of molecular systems. Firstly, we compared the ability of genetic algorithm (GA) and simulated annealing (SA) to find the lowest energy geometry of silicon clusters with six and 10 atoms. This comparison showed that GA exhibits fast initial convergence, but its performance deteriorates as it approaches the desired global extreme. Interestingly, SA showed a complementary convergence pattern, in addition to high accuracy. Our new procedure combines selected features from GA and SA to achieve weak dependence on initial parameters, parallel search strategy, fast convergence and high accuracy. This hybrid algorithm outperforms GA and SA by one order of magnitude for small silicon clusters (Si₆ and Si₁₀). Next, we applied the hybrid method to study the geometry of a 20-atom silicon cluster. It was able to find an original geometry, apparently lower in energy than those previously described in literature. In principle, our procedure can be applied successfully to any molecular system.     

Global optimization of Lennard-Jones clusters by a parallel fast annealing evolutionary algorithm

A parallel fast annealing evolutionary algorithm (PFAEA) was presented and applied to optimize Lennard-Jones (LJ) clusters. All the lowest known minima up to LJ(116) with both icosahedral and nonicosahedral structure, including the truncated octahedron of LJ(38), central fcc tetrahedron of LJ(98), the Marks' decahedron of LJ(75)(-)(77), and LJ(102)(-)(104), were located successfully by the unbiased algorithm. PFAEA is a parallel version of fast annealing evolutionary algorithm (FAEA) that combines the aspect of population in genetic algorithm and annealing algorithm with a very fast annealing schedule. A master-slave paradigm is used to parallelize FAEA to improve the efficiency. The performance of PFAEA is studied, and the scaling of execution time with the cluster size is approximately cubic, which is important for larger scale energy minimization systems.     

A detailed investigation on the global minimum structures of mixed rare‐gas clusters: Geometry,energetics, and site occupancy

We performed a global minimum search of mixed rare‐gas clusters by applying an evolutionary algorithm (EA), which was recently proposed for binary atomic systems (Marques and Pereira, Chem. Phys. Lett. 2010, 485, 211). Before being applied to the potentials used in this work, the EA was further tested against results previously reported for the Ar_NXe_38?N clusters and several new putative global minima were discovered. We employed either simple Lennard‐Jones (LJ) potentials or more realistic functions to describe pair interactions in Ar_NKr_38?N, Ar_NXe_38?N, and Kr_NXe_38?N clusters. The long‐range tail of the pair‐potentials shows some influence on the energetic features and shape of the structure of clusters. In turn, core–shell type structures are mostly observed for global minima of the binary rare‐gas clusters, for both accurate and LJ potentials. However, the long‐range tail of the potential may have influence on the type of atoms that segregate on the surface or form the core of the cluster. While relevant differences for the preferential site occupancy occur between the two potentials for Ar_NKr_38?N (for N > 21), the type of atoms that segregate on the surface for Ar_NXe_38?N and Kr_NXe_38?N clusters is unaffected by the accuracy of the long‐range part of the interaction in almost all cases. Moreover, the global minimum search for model‐potentials in binary systems reveals that the surface‐site occupancy is mainly determined by the combination of two parameters: the size ratio of the two types of particles forming the cluster and the minimum‐energy ratio corresponding to the pair‐interactions between unlike atoms. © 2012 Wiley Periodicals, Inc.     

New optimization method for conformational energy calculations on polypeptides: Conformational space annealing

A new optimization method is presented to search for the global minimum-energy conformations of polypeptides. The method combines essential aspects of the build-up procedure and the genetic algorithm, and it introduces the important concept of “conformational space annealing.” Instead of considering a single conformation, attention is focused on a population of conformations while new conformations are obtained by modifying a “seed conformation.” The annealing is carried out by introducing a distance cutoff, D_cut, which is defined in the conformational space; D_cut effectively divides the whole conformational space of local minima into subdivisions. The value of D_cut is set to a large number at the beginning of the algorithm to cover the whole conformational space, and annealing is achieved by slowly reducing it. Many distinct local minima designed to be distributed as far apart as possible in conformational space are investigated simultaneously. Therefore, the new method finds not only the global minimum-energy conformation but also many other distinct local minima as by-products. The method is tested on Met-enkephalin, a 24-dihedral angle problem. For all 100 independent runs, the accepted global minimum-energy conformation was obtained after about 2600 minimizations on average. © 1997 John Wiley & Sons, Inc. J Comput Chem 18: 1222–1232     

PathOpt—A global transition state search approach: Outline of algorithm

We propose a new algorithm to determine reaction paths and test its capability for Ar₁₂ and Ar₁₃ clusters. Its main ingredient is a search for the local minima on a (n?1) dimensional hyperplane (n = dimension of the complete system in Cartesian coordinates) lying perpendicular to the straight line connection between initial and final states. These minima are part of possible reaction paths and are, hence, used as starting points for an uphill search to the next transition state. First, path fragments are obtained from subsequent relaxations starting from these transition states. They can be combined with information from the straight line connection procedure to obtain complete paths. Our test computations for Ar₁₂ and Ar₁₃ clusters prove that PathOpt delivers several reaction paths in one round. © 2013 Wiley Periodicals, Inc.     

On the mean spherical approximation for the Lennard–Jones fluid

Subtle details on the mean spherical approximation (MSA) theory for the Lennard–Jones potential [Fluid Phase Equilib. 134 (1997) 21] are presented. In order to enhance the appreciation of the theory, the accuracy of the mapping method and the contact approximation used in the theory are demonstrated by comparing with the exact results at certain extreme conditions. Technical derivation of internal energy of the MSA is also fully displayed. In addition, the typographic errors appeared in [Fluid Phase Equilib. 134 (1997) 21] are also corrected in this work.     

Gradient gravitational search: An efficient metaheuristic algorithm for global optimization

The adaptation of novel techniques developed in the field of computational chemistry to solve the concerned problems for large and flexible molecules is taking the center stage with regard to efficient algorithm, computational cost and accuracy. In this article, the gradient‐based gravitational search (GGS) algorithm, using analytical gradients for a fast minimization to the next local minimum has been reported. Its efficiency as metaheuristic approach has also been compared with Gradient Tabu Search and others like: Gravitational Search, Cuckoo Search, and Back Tracking Search algorithms for global optimization. Moreover, the GGS approach has also been applied to computational chemistry problems for finding the minimal value potential energy of two‐dimensional and three‐dimensional off‐lattice protein models. The simulation results reveal the relative stability and physical accuracy of protein models with efficient computational cost. © 2015 Wiley Periodicals, Inc.     

LigDockCSA: protein-ligand docking using conformational space annealing

Protein–ligand docking techniques are one of the essential tools for structure‐based drug design. Two major components of a successful docking program are an efficient search method and an accurate scoring function. In this work, a new docking method called LigDockCSA is developed by using a powerful global optimization technique, conformational space annealing (CSA), and a scoring function that combines the AutoDock energy and the piecewise linear potential (PLP) torsion energy. It is shown that the CSA search method can find lower energy binding poses than the Lamarckian genetic algorithm of AutoDock. However, lower‐energy solutions CSA produced with the AutoDock energy were often less native‐like. The loophole in the AutoDock energy was fixed by adding a torsional energy term, and the CSA search on the refined energy function is shown to improve the docking performance. The performance of LigDockCSA was tested on the Astex diverse set which consists of 85 protein–ligand complexes. LigDockCSA finds the best scoring poses within 2 Å root‐mean‐square deviation (RMSD) from the native structures for 84.7% of the test cases, compared to 81.7% for AutoDock and 80.5% for GOLD. The results improve further to 89.4% by incorporating the conformational entropy. © 2011 Wiley Periodicals, Inc. J Comput Chem, 2011     

A dynamic lattice searching method with constructed core for optimization of large Lennard-Jones clusters

A variation of the previous dynamic lattice searching (DLS) method, named as DLS with constructed core (DLSc), was proposed for structural optimization of Lennard-Jones (LJ) clusters. In the new method, the starting random structure is generated with an icosahedron or a decahedron as a core. For a cluster with n shells, the atoms in the inner n - 2 shells are set as a fixed core, and the remaining atoms in the outer 2 shells are optimized by DLS. With applications of DLSc to optimization of LJ100-200 and LJ660-670, it was found that all the putative global minima can be obtained by using the DLSc method, and the method was proved to be high efficient compared with the previous DLS, because the searching space is reduced by the use of the fixed core. However, although DLSc is still an unbiased approach for smaller LJ clusters, it turned out to be biased for large ones. Further works are still needed to make it to be a more general method for cluster optimization problem.     

A dynamic lattice searching method with interior operation for unbiased optimization of large Lennard-Jones clusters

For improving the efficiency of dynamic lattice searching (DLS) method for unbiased optimization of large Lennard-Jones (LJ) clusters, a variant of the interior operation (IO) proposed by Takeuchi was combined with DLS. The method is named as DLS-IO. In the method, the IO moves outer atoms with higher energy toward the coordinates center, i.e., (0, 0, 0), of a cluster and a local minimization (LM) follows each IO. This makes the interior atoms more compact and the outer atoms more uniformly distributed with lower potential energy. Therefore, the starting structure for DLS operations is closer to the global optimum compared with the randomly generated structures. On the other hand, a method to identify the central atom is proposed for the central vacancy problem. Optimizations of LJ(500), LJ(561), LJ(660), LJ(665), and LJ(670) were investigated with the DLS-IO, and the structural transition during the optimization was analyzed. It was found that the method is efficient and unbiased for optimization of large LJ clusters, and it may be a promising approach to be universally used for structural optimizations.     

A topological method for global optimization of clusters: application to (TiO2)n (n = 1-6)

A new topological method is presented to generate the isomer structures of compound clusters with well defined covalent bonds. This method, combined with density functional theory, has been used to perform global optimization of (TiO(2))(n) (n = 1-6) clusters. Our comprehensive search not only reproduces all of the known lowest-energy structures reported in previous works but also reveals some new low-energy structures. Some energetically unfavorable motifs that induce energy penalties are obtained and discussed. Based on the ground state structures of the anionic (TiO(2))(n). clusters, the electron affinities and photoelectron spectra are simulated and compared with available experimental data.     

Towards protein folding with evolutionary techniques

We present design details and first tests of a new evolutionary algorithm approach to ab initio protein folding. It does not focus on dihedral angles exclusively, but mainly operates on introduction, extension, break-up, and destruction of secondary structure elements, given as correlated dihedral angle values. In first test applications to polyalanines (up to 60 residues) and random primary sequences (up to 40 residues), we demonstrate that this use of prior knowledge is well balanced: On the one hand, it ensures quick introduction of secondary structure elements if they are favorable for a given primary sequence, but still allows for efficient location of pure random coil solutions without enforcing any secondary structure elements, if folds of this type are preferred by the given primary sequence. Furthermore, the algorithm is clearly able to pack several secondary structure elements into favorable tertiary structure arrangements, although no part of the algorithm is explicitly designed to do this. In first test examples on real-life peptides between 21 and 44 residues from the Protein Data Bank, the quality of the results depends on the force field used (as expected); nevertheless, we can show that the algorithm is able to find structures in good agreement with the targets easily and consistently, if the force field allows for that.     

An efficient molecular docking using conformational space annealing

Molecular docking falls into the general category of global optimization problems because its main purpose is to find the most stable complex consisting of a receptor and its ligand. Conformational space annealing (CSA), a powerful global optimization method, is incorporated with the Tinker molecular modeling package to perform molecular docking simulations of six receptor-ligand complexes (3PTB, 1ULB, 2CPP, 1STP, 3CPA, and 1PPH) from the Protein Data Bank. In parallel, Monte Carlo with the minimization (MCM) method is also incorporated into the Tinker package for comparison. The energy function, consisting of electrostatic interactions, van der Waals interactions, and torsional energy terms, is calculated using the AMBER94 all-atom empirical force field. Rigid docking simulations for all six complexes and flexible docking simulations for three complexes (1STP, 3CPA, and 1PPH) are carried out using the CSA and the MCM methods. The simulation results show that the docking procedures using the CSA method generally find the most stable complexes as well as the native-like complexes more efficiently and accurately than those using the MCM, demonstrating that CSA is a promising search method for molecular docking problems.     

Global optimization of atomic and molecular clusters using the space-fixed modified genetic algorithm method

A modified genetic algorithm approach has been applied to atomic Ar clusters and molecular water clusters up to (H₂O)₁₃. Several genetic operators are discussed which are suitable for real-valued space-fixed atomic coordinates and Euler angles. The performance of these operators has been systematically investigated. For atomic systems, it is found that a mix of operators containing a coordinate-averaging operator is optimal. For angular coordinates, the situation is less clear. It appears that inversion and two-point crossover operators are the best choice. © 1997 John Wiley & Sons, Inc. J Comput Chem 18: 1233–1244     

Re-examination of structure optimization of off-lattice protein AB models by conformational space annealing

The global structural optimization is carried out for off-lattice protein AB models in two and three dimensions by conformational space annealing. The models consist of hydrophobic and hydrophilic monomers in Fibonacci sequences. To accelerate the convergence, we have introduced a shift operator in the internal coordinate system, and effectively reduced the search space by forming a quotient space. With this, we significantly improve our previous results on AB models, and provide new low energy conformations. This work provides insights on exploring complicated energy landscapes by exploiting the advantages and limitations of CSA.     

All-atom de novo protein folding with a scalable evolutionary algorithm

The search for efficient and predictive methods to describe the protein folding process at the all-atom level remains an important grand-computational challenge. The development of multi-teraflop architectures, such as the IBM BlueGene used in this study, has been motivated in part by the large computational requirements of such studies. Here we report the predictive all-atom folding of the forty-amino acid HIV accessory protein using an evolutionary stochastic optimization technique. We implemented the optimization method as a master-client model on an IBM BlueGene, where the algorithm scales near perfectly from 64 to 4096 processors in virtual processor mode. Starting from a completely extended conformation, we optimize a population of 64 conformations of the protein in our all-atom free-energy model PFF01. Using 2048 processors the algorithm predictively folds the protein to a near-native conformation with an RMS deviation of 3.43 A in < 24 h.