A fast annealing evolutionary algorithm for global optimization

By combining the aspect of population in genetic algorithms (GAs) and the simulated annealing algorithm (SAA), a novel algorithm, called fast annealing evolutionary algorithm (FAEA), is proposed. The algorithm is similar to the annealing evolutionary algorithm (AEA), and a very fast annealing technique is adopted for the annealing procedure. By an application of the algorithm to the optimization of test functions and a comparison of the algorithm with other stochastic optimization methods, it is shown that the algorithm is a highly efficient optimization method. It was also applied in optimization of Lennard-Jones clusters and compared with other methods in this study. The results indicate that the algorithm is a good tool for the energy minimization problem.     

Protein structure optimization using improved simulated annealing algorithm on a three-dimensional AB off-lattice model

This paper proposed an improved simulated annealing (ISA) algorithm for protein structure optimization based on a three-dimensional AB off-lattice model. In the algorithm, we provided a general formula used for producing initial solution, and designed a multivariable disturbance term, relating to the parameters of simulated annealing and a tuned constant, to generate neighborhood solution. To avoid missing optimal solution, storage operation was performed in searching process. We applied the algorithm to test artificial protein sequences from literature and constructed a benchmark dataset consisting of 10 real protein sequences from the Protein Data Bank (PDB). Otherwise, we generated C_α space-filling model to represent protein folding conformation. The results indicate our algorithm outperforms the five methods before in searching lower energies of artificial protein sequences. In the testing on real proteins, our method can achieve the energy conformations with C_α-RMSD less than 3.0 Å from the PDB structures. Moreover, C_α space-filling model may simulate dynamic change of protein folding conformation at atomic level.     

Protein structure predictions by parallel simulated annealing molecular dynamics using genetic crossover

We propose a conformational search method to find a global minimum energy structure for protein systems. The simulated annealing is a powerful method for local conformational search. On the other hand, the genetic crossover can search the global conformational space. Our method incorporates these attractive features of the simulated annealing and genetic crossover. In the previous works, we have been using the Monte Carlo algorithm for simulated annealing. In the present work, we use the molecular dynamics algorithm instead. To examine the effectiveness of our method, we compared our results with those of the normal simulated annealing molecular dynamics simulations by using an α-helical miniprotein. We used genetic two-point crossover here. The conformations, which have lower energy than those obtained from the conventional simulated annealing, were obtained.     

A machine learning technique toward generating minimum energy structures of small boron clusters

The search for a global minimum related to molecular electronic structure and chemical bonding has received wide attention based on some theoretical calculations at various levels of theory. Particle swarm optimization (PSO) algorithm and modified PSO have been used to predict the energetically stable/metastable states associated with a given chemical composition. Out of a variety of techniques such as genetic algorithm, basin hopping, simulated annealing, PSO, and so on, PSO is considered to be one of the most suitable methods due to its various advantages over others. We use a swarm‐intelligence based parallel code to improve a PSO algorithm in a multidimensional search space augmented by quantum chemical calculations on gas phase structures at 0 K without any symmetry constraint to obtain an optimal solution. Our currently employed code is interfaced with Gaussian software for single point energy calculations. The code developed here is shown to be efficient. Small population size (small cluster) in the multidimensional space is actually good enough to get better results with low computational cost than the typical larger population. But for larger systems also the analysis is possible. One can try with a large number of particles as well. We have also analyzed how arbitrary and random structures and the local minimum energy structures gravitate toward the target global minimum structure. At the same time, we compare our results with that obtained from other evolutionary techniques.     

杂合型全局优化法优化水分子团簇结构

基于遗传算法、快速模拟退火及共轭梯度方法提出了一种快速的杂合型全局优化方法(fast hybrid global optimization algorithm, FHGOA),并将这一方法应用于TIP3P和TIPS2模型水分子团簇(H2O)n结构的优化.在进行TIP3P模型水分子团簇结构的优化过程中,发现了能量比文献值更低的团簇结构,且执行效率有较大提高.把该方法应用到优化TIPS2模型的水分子团簇,发现最优结构和采用TTM2-F模型优化的水分子团簇结构在n < 17时完全相同,为全表面结构;而在n=17、19、22时为单中心水分子笼状结构;在n=25、27时为双中心水分子笼状结构.说明随着团簇中水分子个数的增加,采用TIPS2和TTM2-F势能函数优化的团簇最优结构有相同的变化趋势.     

Simulated annealing to locate various stationary points in semiempirical methods

In this work, an algorithm was developed to study the potential energy surfaces in the coordinate spaces of molecules by a nonlocal way, in contrast to classic energy minimizers as the BFGS or the DFP method. This algorithm, based on the specificities of semiempirical methods, mixes simulated annealing and local searches to reduce computation costs. By this technique, the global energy minimum can be localized. Moreover, local minima that are close in energy to the global minimum are also obtained. If the search is not only for minima but for all stationary points (minima, saddle points…), then the energy is replaced by the gradient norm, which reaches its minimum values at stationary points. The annealing process is stopped before having accurately reached the global minimum and generates a list of geometries whose energies (respectively, whose gradients) are optimized by local minimizers. This list of geometries is shortened from the nearly equivalent geometries by a dynamic single-clustering analysis. The energy/gradient local minimizers act on the clustered list to produce a set of minima/stationary points. A targeted search of these points and reduction of the costs are reached by the way of several penalty functions. They eliminate—without energy calculation—most of the points generated by random walks on the potential energy surface. These penalty functions (on the total moment of inertia or on interatomic distances) are specific to the class of problem studied. They account for the nonrupture of either specific chemical bonds or rings in cyclic molecules, they assure that molecular systems are kept bonded, and they avoid the collapsing of atoms. © 1992 John Wiley & Sons, Inc.     

Do intelligent configuration search techniques outperform random search for large molecules?

We compare three global configuration search methods on a scalable model problem to measure relative performance over a range of molecule sizes. Our model problem is a 2-D polymer composed of atoms connected by rigid rods in which all pairs of atoms interact via Lennard–Jones potentials. The global minimum energy can be calculated analytically. The search methods are all hybrids combining a global sampling algorithm with a local refinement technique. The sampling methods are simulated annealing (SA ), genetic algorithms (GA ), and random search. Each of these uses a conjugate gradient (CG ) routine to perform the local refinement. Both GA and SA perform progressively better relative to random search as the molecule size increases. We also test two other local refinement techniques in addition to CG , coupled to random search as the global method. These are simplex followed by CG and simplex followed by block-truncated Newton. For small problems, the addition of the intermediate simplex step improved the performance of the overall hybrid method. © 1992 John Wiley & Sons, Inc.     

Polarizable protein packing

To incorporate protein polarization effects within a protein combinatorial optimization framework, we decompose the polarizable force field AMOEBA into low order terms. Including terms up to the third-order provides a fair approximation to the full energy while maintaining tractability. We represent the polarizable packing problem for protein G as a hypergraph and solve for optimal rotamers with the FASTER combinatorial optimization algorithm. These approximate energy models can be improved to high accuracy [root mean square deviation (rmsd) < 1 kJ mol(-1)] via ridge regression. The resulting trained approximations are used to efficiently identify new, low-energy solutions. The approach is general and should allow combinatorial optimization of other many-body problems.     

Determining the DNA stability parameters for the breathing dynamics of heterogeneous DNA by stochastic optimization

We suggest that the thermodynamic stability parameters (nearest neighbor stacking and hydrogen bonding free energies) of double-stranded DNA molecules can be inferred reliably from time series of the size fluctuations (breathing) of local denaturation zones (bubbles). On the basis of the reconstructed bubble size distribution, this is achieved through stochastic optimization of the free energies in terms of simulated annealing. In particular, it is shown that even noisy time series allow the identification of the stability parameters at remarkable accuracy. This method will be useful to obtain the DNA stacking and hydrogen bonding free energies from single bubble breathing assays rather than equilibrium data.     

Global minimum structure searches via particle swarm optimization

Novel implementation of the evolutionary approach known as particle swarm optimization (PSO) capable of finding the global minimum of the potential energy surface of atomic assemblies is reported. This is the first time the PSO technique has been used to perform global optimization of minimum structure search for chemical systems. Significant improvements have been introduced to the original PSO algorithm to increase its efficiency and reliability and adapt it to chemical systems. The developed software has successfully found the lowest-energy structures of the LJ(26) Lennard-Jones cluster, anionic silicon hydride Si(2)H(5) (-), and triply hydrated hydroxide ion OH(-) (H(2)O)(3). It requires relatively small population sizes and demonstrates fast convergence. Efficiency of PSO has been compared with simulated annealing, and the gradient embedded genetic algorithm.     

Genetic algorithms for protein conformation sampling and optimization in a discrete backbone dihedral angle space

We have investigated protein conformation sampling and optimization based on the genetic algorithm and discrete main chain dihedral state model. An efficient approach combining the genetic algorithm with local minimization and with a niche technique based on the sharing function is proposed. Using two different types of potential energy functions, a Go-type potential function and a knowledge-based pairwise potential energy function, and a test set containing small proteins of varying sizes and secondary structure compositions, we demonstrated the importance of local minimization and population diversity in protein conformation optimization with genetic algorithms. Some general properties of the sampled conformations such as their native-likeness and the influences of including side-chains are discussed.     

Global optimization of binary Lennard-Jones clusters using three perturbation operators

Global optimization of binary Lennard-Jones clusters is a challenging problem in computational chemistry. The difficulty lies in not only that there are enormous local minima on the potential energy surface but also that we must determine both the coordinate position and the atom type for each atom and thus have to deal with both continuous and combinatorial optimization. This paper presents a heuristic algorithm (denoted by 3OP) which makes extensive use of three perturbation operators. With these operators, the proposed 3OP algorithm can efficiently move from a poor local minimum to another better local minimum and detect the global minimum through a sequence of local minima with decreasing energy. The proposed 3OP algorithm has been evaluated on a set of 96 × 6 instances with up to 100 atoms. We have found most putative global minima listed in the Cambridge Cluster Database as well as discovering 12 new global minima missed in previous research.     

A Simulated Annealing Algorithm for Training Empirical Potential Functions of Protein Folding

In this paper are reported the local minimum problem by means of current greedy algorithm for training the empirical potential function of protein folding on 8623 non-native structures of 31 globular proteins and a solution of the problem based upon the simulated annealing algorithm. This simulated annealing algorithm is indispensable for developing and testing highly refined empirical potential functions.     

Heuristic energy landscape paving for protein folding problem in the three-dimensional HP lattice model

The protein folding problem, i.e., the prediction of the tertiary structures of protein molecules from their amino acid sequences is one of the most important problems in computational biology and biochemistry. However, the extremely difficult optimization problem arising from energy function is a key challenge in protein folding simulation. The energy landscape paving (ELP) method has already been applied very successfully to off-lattice protein models and other optimization problems with complex energy landscape in continuous space. By improving the ELP method, and subsequently incorporating the neighborhood strategy with the pull-move set into the improved ELP method, a heuristic ELP algorithm is proposed to find low-energy conformations of 3D HP lattice model proteins in the discrete space. The algorithm is tested on three sets of 3D HP benchmark instances consisting 31 sequences. For eleven sequences with 27 monomers, the proposed method explores the conformation surfaces more efficiently than other methods, and finds new lower energies in several cases. For ten 48-monomer sequences, we find the lowest energies so far. With the achieved results, the algorithm converges rapidly and efficiently. For all ten 64-monomer sequences, the algorithm finds lower energies within comparable computation times than previous methods. Numeric results show that the heuristic ELP method is a competitive tool for protein folding simulation in 3D lattice model. To the best of our knowledge, this is the first application of ELP to the 3D discrete space.     

Geometry optimizations of benzene clusters using a modified genetic algorithm

A modified genetic algorithm with real-number coding, non-uniform mutation and arithmetical crossover operators was described in this paper. A local minimization was used to improve the final solution obtained by the genetic algorithm. Using the exp-6-1 interatomic energy function, the modified genetic algorithm with local minimization (MGALM) was applied to the geometry optimization problem of small benzene clusters (C6H6)N(N = 2-7) to obtain the global minimum energy structures. MGALM is simple but the structures optimized are comparable to the published results obtained by parallel genetic algorithms.     

A reliable prediction of the global phase stability for liquid–liquid equilibrium through the simulated annealing algorithm: Application to NRTL and UNIQUAC equations

The simulated annealing algorithm is introduced to search the global optimal solutions for the multipeak phenomena which generally exist in the phase stability problems with continuous variables. The Gibbs free energy criterion was modeled by the NRTL and UNIQUAC activity coefficient equations. When previous approaches fail, it is usually because they locate local minima due to the nonconvex and nonlinear natures of the models used to predict phase equilibrium. In this paper, the preliminary results show that the global minimum of the tangent plane distance function (TPDF) can be obtained by using the simulated annealing algorithm. The effects of the initial and the final values of the control parameter, the decrement of the control parameter and the length of the Markov chains are analyzed. The optimal `cooling schedule' was obtained according to the calculation results of the phase stability problems for one ternary mixture. The liquid–liquid equilibrium compositions were calculated by the Newton–Raphson method on the basis of the global minimum of TPDF. The results of four examples show that the simulated annealing algorithm can effectively solve the global phase stability problem.     

Novel bare-bones particle swarm optimization and its performance for modeling vapor-liquid equilibrium data

Parameter estimation in models plays a significant role in developing mathematical models which are used for understanding and analyzing physical, chemical and biological systems. Parameter estimation problems for vapor-liquid equilibrium (VLE) data modeling are very challenging due to the high non-linearity of thermodynamic models. Recently, stochastic global optimizations and their applications to these problems have attracted greater interest. Of the many stochastic global optimization methods, Bare-bones particle swarm optimization (BBPSO) is attractive since it has no parameters to be tuned by the user. In this study, modifications are introduced to the original BBPSO using mutation and crossover operators of differential evolution algorithm to update certain particles in the population. The performance of the resulting algorithm is tested on 10 benchmark functions and applied to 16 VLE problems. The performance of the proposed BBPSO for VLE modeling is compared with that of other stochastic algorithms, namely, differential evolution (DE), DE with tabu list, genetic algorithm and simulated annealing in order to identify their relative strengths for VLE data modeling. The proposed BBPSO is shown to be better than or comparable to the other stochastic global optimization algorithms tested for parameter estimation in modeling VLE data.     

Heterogeneous catalyst design using stochastic optimization algorithms

We describe the application of two stochastic optimization algorithms to heterogeneous catalyst design. In particular, we discuss the optimal design of a two-component catalyst for the diffusion limited A + B --> 0 and A + B2 --> 0 reactions in which each of the reactants are adsorbed specifically on one of the two distinct catalytic sites. The geometric arrangement of the catalytic sites that maximizes the catalyst activity is determined by the use of a genetic algorithm and a simulated annealing algorithm. In the case of the A + B --> 0 reaction, it is found that the catalyst surface with the optimal active site distribution, that of a checkerboard, is approximately 25% more active than a random site distribution. A similar increase in catalytic activity is obtained for the A + B2 --> 0 reaction. While both the genetic and simulated annealing algorithms obtain identical optimal solutions for a given reaction, the simulated annealing algorithm is shown to be more efficient.