Hybrid particle swarm optimization and tabu search approach for selecting genes for tumor classification using gene expression data

Gene expression data are characterized by thousands even tens of thousands of measured genes on only a few tissue samples. This can lead either to possible overfitting and dimensional curse or even to a complete failure in analysis of microarray data. Gene selection is an important component for gene expression-based tumor classification systems. In this paper, we develop a hybrid particle swarm optimization (PSO) and tabu search (HPSOTS) approach for gene selection for tumor classification. The incorporation of tabu search (TS) as a local improvement procedure enables the algorithm HPSOTS to overleap local optima and show satisfactory performance. The proposed approach is applied to three different microarray data sets. Moreover, we compare the performance of HPSOTS on these datasets to that of stepwise selection, the pure TS and PSO algorithm. It has been demonstrated that the HPSOTS is a useful tool for gene selection and mining high dimension data.     

Gradient tabu search

This paper presents a modification of the tabu search called gradient tabu search (GTS). It uses analytical gradients for a fast minimization to the next local minimum and analytical diagonal elements of the Hessian to escape local minima. For an efficient blocking of already visited areas tabu regions and tabu directions are introduced into the tabu list (TL). Trials with various well-known test functions indicate that the GTS is a very promising approach to determine local and global minima of differentiable functions. Possible application areas could be optimization routines for force field parameters or conformational searches for large molecules.     

A parallel tabu search for conformational energy optimization of oligopeptides

We have developed and implemented a tabu search heuristic (TS) to determine the best energy minimum for oligopeptides. Our test molecule was Met‐enkephalin, a pentapetide that over the years has been used as a validation model for many global optimizers. The test potential energy function was ECEPP/3. Our tabu search implementation is based on assigning integer values to the variables to be optimized, and in facilitating the diversification and intensification of the search. The final output from the TS is treated with a local optimizer, and our best result competes both in quality and CPU time with those reported in the literature. The results indicate that TS is an efficient algorithm for conformational searches. We present a parallel TS version along with experimental results that show that this algorithm allows significant increases in speed. © 2000 John Wiley & Sons, Inc. J Comput Chem 21: 147–156, 2000     

Hybrid genetic algorithm–tabu search approach for optimising multilayer optical coatings

Constructing multilayer optical coatings (MOCs) is a difficult large-scale optimisation problem due to the enormous size of the search space. In the present paper, a new approach for designing MOCs is presented using genetic algorithms (GAs) and tabu search (TS). In this approach, it is not necessary to specify how many layers will be present in a design, only a maximum needs to be defined. As it is generally recognised that the existence of specific repeating blocks is beneficial for a design, a specific GA representation of a design is used which promotes the occurrence of repeating blocks. Solutions found by GAs are improved by a new refinement method, based on TS, a global optimisation method which is loosely based on artificial intelligence. The improvements are demonstrated by creating a visible transmitting/infrared reflecting filter with a wide variety of materials.     

Prediction of the lowest energy configuration for Lennard-Jones clusters

Based on the work of previous researchers, a new unbiased optimization algorithm—the dynamic lattice searching method with two-phase local search and interior operation (DLS-TPIO)—is proposed in this paper. This algorithm is applied to the optimization of Lennard-Jones (LJ) clusters with N=2–650, 660, and 665–680. For each case, the putative global minimum reported in the Cambridge Cluster Database (CCD) is successfully found. Furthermore, for LJ533 and LJ536, the potential energies obtained in this study a...     

Lennard-Jones团簇最低能量构型的预测

针对Lennard-Jones(LJ)团簇的结构优化问题,在前人工作的基础上,提出了一个新的无偏优化算法,即DLS-TPIO(dynamic lattice searching method with two-phase local searchand interior operation)算法.对LJ2-650,LJ660,LJ665-680这666个实例进行了优化计算.为其中每个实例所找到的构型其势能均达到了剑桥团簇数据库中公布的最好记录.对LJ533与LJ536这两个算例,所达到的势能则优于先前的最好记录.在DLS-TPIO算法中,采用了内部操作,两阶段局部搜索方法以及动态格点搜索方法.在优化的前一阶段,内部操作将若干能量较高的表面原子移入团簇的内部,从而降低团簇的能量,并使其构型逐渐地变为有序.与此同时,两阶段局部搜索方法指导搜索进入更有希望的构型区域.这种做法显著地提高了算法的成功率.在优化的后一阶段,借用动态格点搜索方法对团簇表面原子的位置作进一步优化,以再一次降低团簇的能量.另外,为识别二十面体构型的中心原子,本文给出了一个简单的新方法.相比于文献中一些著名的无偏优化算法,DLS-TPIO算法具...     

A genetic algorithm for the structural optimization of Morse clusters

This article describes the application of a genetic algorithm for the structural optimization of 19–50-atom clusters bound by medium-range and short-range Morse pair potentials. The GA is found to be efficient and reliable for finding the geometries corresponding to the previously published global minima [Doye JPK, Wales DJ (1997) J Chem Soc Faraday Trans 93: 4233]. Using the genetic algorithm, only a relatively small number of energy evaluations and minimizations are required to find the global minima. By contrast, a simple random search algorithm often cannot find the global minima of the larger clusters, even after many thousands of searches. Received: 27 October 1999 / Accepted: 7 December 1999 / Published online: 19 April 2000     

Efficiency of tabu‐search‐based conformational search algorithms

Efficient conformational search or sampling approaches play an integral role in molecular modeling, leading to a strong demand for even faster and more reliable conformer search algorithms. This article compares the efficiency of a molecular dynamics method, a simulated annealing method, and the basin hopping (BH) approach (which are widely used in this field) with a previously suggested tabu‐search‐based approach called gradient only tabu search (GOTS). The study emphasizes the success of the GOTS procedure and, more importantly, shows that an approach which combines BH and GOTS outperforms the single methods in efficiency and speed. We also show that ring structures built by a hydrogen bond are useful as starting points for conformational search investigations of peptides and organic ligands with biological activities, especially in structures that contain multiple rings. © 2011 Wiley Periodicals, Inc. J Comput Chem, 2011     

Tabu search algorithm for DNA sequencing by hybridization with isothermic libraries

In this paper, a problem of isothermic DNA sequencing by hybridization (SBH) is considered. In isothermic SBH a new type of oligonucleotide libraries is used. The library consists of oligonucleotides of different lengths depending on an oligonucleotide content. It is assumed that every oligonucleotide in such a library has an equal melting temperature. Each nucleotide adds its increment to the oligonucleotide temperature and it is assumed that A and T add 2 degrees C and C and G add 4 degrees C. The hybridization experiment using isothermic libraries should provide data with a lower number of errors due to an expected similarity of melting temperatures. From the computational point of view the problem of isothermic DNA sequencing with errors is hard, similarly like its classical counterpart. Hence, there is a need for developing heuristic algorithms that construct good suboptimal solutions. The aim of the paper is to propose a heuristic algorithm based on tabu search approach. The algorithm solves the problem with both positive and negative errors. Results of an extensive computational experiment are presented, which prove the high quality of the proposed method.     

Multi-swarm UPSO algorithm based on seed strategy for atomic clusters structure optimization

Particle Swarm Optimization (PSO) algorithm is prone to get trapped in local optima and insufficient information exchange among particles. To solve this problem, this paper proposes a Multi-swarm Unified Particle Swarm Optimization algorithm based on Seed Strategy (SS-DMS-UPSO) to optimize the atomic clusters structure. In this algorithm, the population is divided into some sub-populations evolving randomly and evenly, and each sub-population uses UPSO algorithm with different unification factors to evolve independently in parallel. After a certain number of independent evolution, the particles of all sub-populations are merged into a new population, and the population is again randomly divided into average sub-populations. Iterate the algorithm repeatedly in this way. And finally the global best particle can be obtained. The experimental results show that the SS-DMS-UPSO algorithm can search for the optimal structure or extremely similar optimal structure for atomic clusters with atomic numbers between 2 and 31. For atomic clusters with atomic numbers between 32 and 35, the algorithm can find its approximate optimal structure. Compared with other algorithms, the difference between the lowest energy value and the ideal energy value obtained by the SS-DMS-UPSO algorithm is much smaller. It means that its optimal structure of the atomic clusters is closer to the stable structure, and the algorithm is more stable, which proves the effectiveness of the SS-DMS-UPSO algorithm.     

Global geometry optimization of small silicon clusters at the level of density functional theory

By an application to small silicon clusters Si _N (with N = 4,5,7,10) it is shown that truly global geometry optimization on an ab initio or density functional theory level can be achieved, at a computational cost of approximately 1–5 traditional local optimization runs (depending on cluster size). This extends global optimization from the limited area of empirical potentials into the realm of ab initio quantum chemistry. Received: 24 February 1998 / Accepted: 6 March 1998 / Published online: 17 June 1998     

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     

Structural optimization of Cu-Ag-Au trimetallic clusters by adaptive immune optimization algorithm

The putative global minimum structures of Cu-Ag-Au trimetallic clusters with 19 and 55 atoms are obtained by adaptive immune optimization algorithm (AIOA) with the Gupta potential. For the 19-atom trimetallic clusters, the results indicate that all of them have double-icosahedral motifs. For the optimized structures of Cu(13)Ag(n)Au(42-n) (n = 1-41), the clusters can be categorized into 19 Mackay icosahedral structures, 1 6-fold pancake structure, and 21 ring-like structures linked by three face-sharing double-icosahedra. Furthermore, the segregation phenomena of the Cu, Ag, and Au atoms in the Cu-Ag-Au trimetallic clusters are studied to provide useful information for geometric character. Results show that Cu and Ag atoms prefer to locate in the inner-shell and on the surface, respectively, whereas Au atoms mainly locate in the middle-shell and tend to solve into Cu and Ag atoms.     

Molecular simulation of oxygen on supported platinum clusters

Molecular dynamics simulations are performed to study oxygen adsorption on platinum clusters supported on a graphite surface. The Sutton–Chen many-body potential is used for the Pt–Pt interaction, whereas a Steele potential was used to represent the carbon surface. The oxygen–oxygen intramolecular force is modeled by a harmonic oscillator model and other interactions are described by the Lennard–Jones potential. The results indicate an optimum loading of platinum for maximum specific adsorption of oxygen. Adsorption isotherms are constructed and the energies and orientation of adsorbed oxygen are reported. The relevance of this study to electrode processes is discussed.     

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.     

A comparison of heuristic search algorithms for molecular docking

This paper describes the implementation and comparison of four heuristic search algorithms (genetic algorithm, evolutionary programming, simulated annealing and tabu search) and a random search procedure for flexible molecular docking. To our knowledge, this is the first application of the tabu search algorithm in this area. The algorithms are compared using a recently described fast molecular recognition potential function and a diverse set of five protein–ligand systems. Statistical analysis of the results indicates that overall the genetic algorithm performs best in terms of the median energy of the solutions located. However, tabu search shows a better performance in terms of locating solutions close to the crystallographic ligand conformation. These results suggest that a hybrid search algorithm may give superior results to any of the algorithms alone.     

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.     

Using vibrational modes in the search for global minima of atomic and molecular clusters

The reaction between dimethyl sulfide (CH₃SCH₃) and nitrate radical (NO₃) is studied using density functional theory and ab initio methods. The transition state for this reaction is optimized at different levels of theory and basis sets, and then used for kinetics calculations of the rate constant. The CH₃SCH₃ + NO₃ reaction leading to CH₃SCH₂ and HNO₃ is shown to have a negative activation energy and thus negative temperature dependence. The study confirms that the NO₃ radical is a significant contributor to the oxidation of DMS in the troposphere.     

Smoothing techniques of global optimization: Distance scaling method in searches for most stable Lennard–Jones atomic clusters

Spatial averaging of the potential energy function facilitates the search for the most stable configuration of a molecular system. Recently some global optimization methods of this kind have been designed in the literature that rely on physical phenomena such as diffusion, wave function evolution in quantum mechanics, Smoluchowski dynamics, evolution in temperature of canonical ensembles, etc. In the present article we highlight the fact that all these methods, when applied to the Gaussian distributions of an ensemble, represent special cases of a set of differential equations involving the spatially averaged potential energy. Their structure suggests that the nature's strategy to cope with the global optimization is robust and differs only in the details in particular applications. The strategy consists of going downhill of the averaged potential energy, removing the barriers, and hunting for low energy regions by a selective increasing of the spatial averaging. In this study we explore the deformation of the potential rather than its averaging. The deformation comes from scaling of atomic distances and reduces the barriers even more effectively than the Gaussian averaging. The position and widths of the Gaussian distribution evolve similarly to the Gaussian density annealing (GDA), but we allow elliptical instead of spherical Gaussians as well as branching of the single trajectory of the system into multiple ones. When the temperature reaches 0 K, one has a number of independent Gaussian distributions, each corresponding to a structure and (usually low) energy of the system. The multiple elliptic-Gaussian distance scaling method has been applied to clusters of argon atoms (N=5,…,31), a system serving usually as a benchmark domain. The method found the global minima for all but three clusters (of very low energy). The procedure is 20 or more times less expensive than the GDA one. © 1997 John Wiley & Sons, Inc. J Comput Chem 18 : 2040–2049, 1997