Estimation-based ant colony optimization and local search for the probabilistic traveling salesman problem

The use of ant colony optimization for solving stochastic optimization problems has received a significant amount of attention in recent years. In this paper, we present a study of enhanced ant colony optimization algorithms for tackling a stochastic optimization problem, the probabilistic traveling salesman problem. In particular, we propose an empirical estimation approach to evaluate the cost of the solutions constructed by the ants. Moreover, we use a recent estimation-based iterative improvement algorithm as a local search. Experimental results on a large number of problem instances show that the proposed ant colony optimization algorithms outperform the current best algorithm tailored to solve the given problem, which also happened to be an ant colony optimization algorithm. As a consequence, we have obtained a new state-of-the-art ant colony optimization algorithm for the probabilistic traveling salesman problem.     

Evaluation of a particle swarm algorithm for biomechanical optimization

Optimization is frequently employed in biomechanics research to solve system identification problems, predict human movement, or estimate muscle or other internal forces that cannot be measured directly. Unfortunately, biomechanical optimization problems often possess multiple local minima, making it difficult to find the best solution. Furthermore, convergence in gradient-based algorithms can be affected by scaling to account for design variables with different length scales or units. In this study we evaluate a recently-developed version of the particle swarm optimization (PSO) algorithm to address these problems. The algorithm's global search capabilities were investigated using a suite of difficult analytical test problems, while its scale-independent nature was proven mathematically and verified using a biomechanical test problem. For comparison, all test problems were also solved with three off-the-shelf optimization algorithms--a global genetic algorithm (GA) and multistart gradient-based sequential quadratic programming (SQP) and quasi-Newton (BFGS) algorithms. For the analytical test problems, only the PSO algorithm was successful on the majority of the problems. When compared to previously published results for the same problems, PSO was more robust than a global simulated annealing algorithm but less robust than a different, more complex genetic algorithm. For the biomechanical test problem, only the PSO algorithm was insensitive to design variable scaling, with the GA algorithm being mildly sensitive and the SQP and BFGS algorithms being highly sensitive. The proposed PSO algorithm provides a new off-the-shelf global optimization option for difficult biomechanical problems, especially those utilizing design variables with different length scales or units.     

Heuristic combinatorial optimization by simulated Darwinian evolution: a polynomial time algorithm for the Traveling Salesman Problem

A genetic algorithm simulating Darwinian evolution is proposed to yield near-optimal solutions to the Traveling Salesman Problem. Noting that Darwinian evolution is itself an optimization process, we propose a heuristic algorithm that incorporates the tenets of natural selection. The time complexity of this algorithm is equivalent to the fastest sorting scheme! Computer simulations indicate rapid convergence is maintained even with increasing problem complexity. This methodology can be adapted to tackle a host of other combinatorial problems.     

The threshold bootstrap clustering: a new approach to find families or transmission clusters within molecular quasispecies

Background

Phylogenetic methods produce hierarchies of molecular species, inferring knowledge about taxonomy and evolution. However, there is not yet a consensus methodology that provides a crisp partition of taxa, desirable when considering the problem of intra/inter-patient quasispecies classification or infection transmission event identification. We introduce the threshold bootstrap clustering (TBC), a new methodology for partitioning molecular sequences, that does not require a phylogenetic tree estimation.

Methodology/Principal Findings

The TBC is an incremental partition algorithm, inspired by the stochastic Chinese restaurant process, and takes advantage of resampling techniques and models of sequence evolution. TBC uses as input a multiple alignment of molecular sequences and its output is a crisp partition of the taxa into an automatically determined number of clusters. By varying initial conditions, the algorithm can produce different partitions. We describe a procedure that selects a prime partition among a set of candidate ones and calculates a measure of cluster reliability. TBC was successfully tested for the identification of type-1 human immunodeficiency and hepatitis C virus subtypes, and compared with previously established methodologies. It was also evaluated in the problem of HIV-1 intra-patient quasispecies clustering, and for transmission cluster identification, using a set of sequences from patients with known transmission event histories.

Conclusion

TBC has been shown to be effective for the subtyping of HIV and HCV, and for identifying intra-patient quasispecies. To some extent, the algorithm was able also to infer clusters corresponding to events of infection transmission. The computational complexity of TBC is quadratic in the number of taxa, lower than other established methods; in addition, TBC has been enhanced with a measure of cluster reliability. The TBC can be useful to characterise molecular quasipecies in a broad context.     

Quasispecies made simple

Quasispecies are clouds of genotypes that appear in a population at mutation–selection balance. This concept has recently attracted the attention of virologists, because many RNA viruses appear to generate high levels of genetic variation that may enhance the evolution of drug resistance and immune escape. The literature on these important evolutionary processes is, however, quite challenging. Here we use simple models to link mutation–selection balance theory to the most novel property of quasispecies: the error threshold—a mutation rate below which populations equilibrate in a traditional mutation–selection balance and above which the population experiences an error catastrophe, that is, the loss of the favored genotype through frequent deleterious mutations. These models show that a single fitness landscape may contain multiple, hierarchically organized error thresholds and that an error threshold is affected by the extent of back mutation and redundancy in the genotype-to-phenotype map. Importantly, an error threshold is distinct from an extinction threshold, which is the complete loss of the population through lethal mutations. Based on this framework, we argue that the lethal mutagenesis of a viral infection by mutation-inducing drugs is not a true error catastophe, but is an extinction catastrophe.     

Set-based particle swarm optimization applied to the multidimensional knapsack problem

Particle swarm optimization algorithms have been successfully applied to discrete/valued optimization problems. However, in many cases the algorithms have been tailored specifically for the problem at hand. This paper proposes a generic set-based particle swarm optimization algorithm for use in discrete-valued optimization problems that can be formulated as set-based problems. A detailed sensitivity analysis of the parameters of the algorithm is conducted. The performance of the proposed algorithm is then compared against three other discrete particle swarm optimization algorithms from literature using the multidimensional knapsack problem and is shown to statistically outperform the existing algorithms.     

Image 1D OMP sparse decomposition with modified fruit-fly optimization algorithm

The Fruit-fly optimization algorithm (FOA) is good at parallel search ability in the evolution process, but it traps in local optimum sometimes. Simulated Annealing (SA) algorithm accepts the second-optimum solution with Mrtropolis criterion so as to jump out of the local optimum. So, combined the advantages of two algorithms, modified FOA (FOA-SA) algorithm is presented in this paper. In FOA-SA, the smell concentration function is improved as well, so as to get the whole searching directions for fruit-fly. At the same time, in order to solve the problem of the computational complexity in image 2D sparse decomposition, image 1D orthogonal matching pursuit (OMP) algorithm with FOA-SA algorithm is implemented. Experimental results show that the convergence of FOA-SA is better than that in FOA, and the speed of image 1D sparse algorithm is 2.41 times faster than 2D for the 512 \(\times \) 512 image under the same conditions.     

Improving metabolic flux estimation via evolutionary optimization for convex solution space

MOTIVATION: Flux estimation by using (13) C-labeling pattern information of metabolites is currently the only method that can give accurate, detailed quantification of all intracellular fluxes in the central metabolism of a microorganism. In essence, it corresponds to a constrained optimization problem which minimizes a weighted distance between measured and simulated results. Characteristics, such as existence of multiple local minima, non-linear and non-differentiable make this problem a special difficulty. RESULTS: In the present work, we propose an evolutionary-based global optimization algorithm taking advantage of the convex feature of the problem's solution space. Based on the characteristics of convex spaces, specialized initial population and evolutionary operators are designed to solve (13)C-based metabolic flux estimation problem robustly and efficiently. The algorithm was applied to estimate the central metabolic fluxes in Escherichia coli and compared with conventional optimization technique. Experimental results illustrated that our algorithm is capable of achieving fast convergence to good near-optima and maintaining the robust nature of evolutionary algorithms at the same time. AVAILABILITY: Available from the authors upon request.     

Impact of Stoichiometry Representation on Simulation of Genotype-Phenotype Relationships in Metabolic Networks

Genome-scale metabolic networks provide a comprehensive structural framework for modeling genotype-phenotype relationships through flux simulations. The solution space for the metabolic flux state of the cell is typically very large and optimization-based approaches are often necessary for predicting the active metabolic state under specific environmental conditions. The objective function to be used in such optimization algorithms is directly linked with the biological hypothesis underlying the model and therefore it is one of the most relevant parameters for successful modeling. Although linear combination of selected fluxes is widely used for formulating metabolic objective functions, we show that the resulting optimization problem is sensitive towards stoichiometry representation of the metabolic network. This undesirable sensitivity leads to different simulation results when using numerically different but biochemically equivalent stoichiometry representations and thereby makes biological interpretation intrinsically subjective and ambiguous. We hereby propose a new method, Minimization of Metabolites Balance (MiMBl), which decouples the artifacts of stoichiometry representation from the formulation of the desired objective functions, by casting objective functions using metabolite turnovers rather than fluxes. By simulating perturbed metabolic networks, we demonstrate that the use of stoichiometry representation independent algorithms is fundamental for unambiguously linking modeling results with biological interpretation. For example, MiMBl allowed us to expand the scope of metabolic modeling in elucidating the mechanistic basis of several genetic interactions in Saccharomyces cerevisiae.     

Guidelines: From artificial evolution to computational evolution: a research agenda

Computational scientists have developed algorithms inspired by natural evolution for at least 50 years. These algorithms solve optimization and design problems by building solutions that are 'more fit' relative to desired properties. However, the basic assumptions of this approach are outdated. We propose a research programme to develop a new field: computational evolution. This approach will produce algorithms that are based on current understanding of molecular and evolutionary biology and could solve previously unimaginable or intractable computational and biological problems.     

Residue-rotamer-reduction algorithm for the protein side-chain conformation problem

MOTIVATION: The protein side-chain conformation problem is a central problem in proteomics with wide applications in protein structure prediction and design. Computational complexity results show that the problem is hard to solve. Yet, instances from realistic applications are large and demand fast and reliable algorithms. RESULTS: We propose a new global optimization algorithm, which for the first time integrates residue reduction and rotamer reduction techniques previously developed for the protein side-chain conformation problem. We show that the proposed approach simplifies dramatically the topology of the underlining residue graph. Computations show that our algorithm solves problems using only 1-10% of the time required by the mixed-integer linear programming approach available in the literature. In addition, on a set of hard side-chain conformation problems, our algorithm runs 2-78 times faster than SCWRL 3.0, which is widely used for solving these problems. AVAILABILITY: The implementation is available as an online server at http://eudoxus.scs.uiuc.edu/r3.html     

What is a quasispecies?

A quasispecies is a well-defined distribution of mutants that is generated by a mutation-selection process. Selection does not act on a single mutant but on the quasispecies as a whole. Experimental systems have been designed to study quasispecies evolution under laboratory conditions. More recently, virus populations have been called quasispecies to indicate their extensive genetic heterogeneity. The most prominent examples are probably the human immunodeficiency viruses HIV-1 and HIV-2. The quasispecies nature of HIV has formed the basis of a model that provides a mechanism for the pathogenesis of acquired immunodeficiency syndrome (AIDS) in humans. This article focuses on the nature of the quasispecies concept and its implications for evolutionary biology and virology.     

Learning Bayesian network classifiers using ant colony optimization

Bayesian networks are knowledge representation tools that model the (in)dependency relationships among variables for probabilistic reasoning. Classification with Bayesian networks aims to compute the class with the highest probability given a case. This special kind is referred to as Bayesian network classifiers. Since learning the Bayesian network structure from a dataset can be viewed as an optimization problem, heuristic search algorithms may be applied to build high-quality networks in medium- or large-scale problems, as exhaustive search is often feasible only for small problems. In this paper, we present our new algorithm, ABC-Miner, and propose several extensions to it. ABC-Miner uses ant colony optimization for learning the structure of Bayesian network classifiers. We report extended computational results comparing the performance of our algorithm with eight other classification algorithms, namely six variations of well-known Bayesian network classifiers, cAnt-Miner for discovering classification rules and a support vector machine algorithm.     

Parameter Estimation of Fractional-Order Chaotic Systems by Using Quantum Parallel Particle Swarm Optimization Algorithm

Parameter estimation for fractional-order chaotic systems is an important issue in fractional-order chaotic control and synchronization and could be essentially formulated as a multidimensional optimization problem. A novel algorithm called quantum parallel particle swarm optimization (QPPSO) is proposed to solve the parameter estimation for fractional-order chaotic systems. The parallel characteristic of quantum computing is used in QPPSO. This characteristic increases the calculation of each generation exponentially. The behavior of particles in quantum space is restrained by the quantum evolution equation, which consists of the current rotation angle, individual optimal quantum rotation angle, and global optimal quantum rotation angle. Numerical simulation based on several typical fractional-order systems and comparisons with some typical existing algorithms show the effectiveness and efficiency of the proposed algorithm.     

Multiple RNA structure alignment

Ribonucleic Acid (RNA) structures can be viewed as a special kind of strings where characters in a string can bond with each other. The question of aligning two RNA structures has been studied for a while, and there are several successful algorithms that are based upon different models. In this paper, by adopting the model introduced in Wang and Zhang,(19) we propose two algorithms to attack the question of aligning multiple RNA structures. Our methods are to reduce the multiple RNA structure alignment problem to the problem of aligning two RNA structure alignments. Meanwhile, we will show that the framework of sequence center star alignment algorithm can be applied to the problem of multiple RNA structure alignment, and if the triangle inequality is met in the scoring matrix, the approximation ratio of the algorithm remains to be 2-2(over)n, where n is the total number of structures.     

A trade-off between neutrality and adaptability limits the optimization of viral quasispecies

Theoretical studies of quasispecies usually focus on two properties of those populations at the mutation-selection equilibrium, namely asymptotic growth rate and population diversity. It has been postulated that, as a consequence of the high error rate of quasispecies replication, an increase of neutrality facilitates population optimization by reducing the amount of mutations with a deleterious effect on fitness. In this study we analyse how the optimization of equilibrium properties is affected when a quasispecies evolves in an environment perturbed through frequent bottleneck events. By means of a simple model we demonstrate that high neutrality may be detrimental when the population has to overcome repeated reductions in the population size, and that the property to be optimized in this situation is the time required to regenerate the quasispecies, i.e. its adaptability. In the scenario described, neutrality and adaptability cannot be simultaneously optimized. When fitness is equated with long-term survivability, high neutrality is the appropriate strategy in constant environments, while populations evolving in fluctuating environments are fitter when their neutrality is low, such that they can respond faster to perturbations. Our results might be relevant to better comprehend how a minority virus could displace the circulating quasispecies, a fact observed in natural infections and essential in viral evolution.     

基于遗传算法的土地利用优化：NSGA-Ⅱ和NSGA-Ⅲ的对比研究

土地利用优化通常要兼顾不同群体的多种要求,理论上是复杂的超多目标(4个及以上)优化问题。但实际操作中却往往被简化为多目标(2—3个)优化问题,通过一种流行的多目标优化算法第Ⅱ代非支配排序遗传算法(NSGA-Ⅱ)求解。究其原因是对超多目标优化算法认知的缺失和与多目标优化算法理论对比的匮乏。对NSGA系列中应用最广泛的多目标优化算法NSGA-Ⅱ和最新提出、面向超多目标优化的算法NSGA-Ⅲ进行探究,从理论和实验两方面对Ⅲ和Ⅱ进行对比,从而探究二者进行土地利用优化时的优劣。在理论上,对比两种算法原理的异同。在实验中,分别设计多目标(3个目标)和超多目标(13个目标)土地利用优化问题,利用两种算法进行求解。对实验结果采用四层架构、六大指标进行全面评价,以对比两种算法的可用性。理论对比发现,两个算法只有种群多样性保护的方法不同,其中NSGA-Ⅲ是基于与固定的参考点的距离,而NSGA-Ⅱ则是基于相邻解间的距离。通过实验对比发现,NSGA-Ⅲ在超多目标优化时运算速度快,且产生的最优方案实用价值更高,NSGA-Ⅱ在算法的有效性方面更有优势。     

Folding small proteins via annealing stochastic approximation Monte Carlo

Recently, the stochastic approximation Monte Carlo algorithm has been proposed by Liang et al. (2007) as a general-purpose stochastic optimization and simulation algorithm. An annealing version of this algorithm was developed for real small protein folding problems. The numerical results indicate that it outperforms simulated annealing and conventional Monte Carlo algorithms as a stochastic optimization algorithm. We also propose one method for the use of secondary structures in protein folding. The predicted protein structures are rather close to the true structures.     

A New Cyclic Scheduling Algorithm for Flexible Manufacturing Systems

Flexible manufacturing system control is an NP-hard problem. A cyclic approach has been demonstrated to be adequate for an infinite scheduling problem because of maximal throughput reachability. However, it is not the only optimization criterion in general. In this article we consider the minimization of the work in process (WIP) as an economical and productivity factor. We propose a new cyclic scheduling algorithm giving the maximal throughput (a hard constraint) while minimizing WIP. This algorithm is based on progressive operations placing. A controlled beam search approach has been developed to determine at each step the schedule of the next operations. After presenting the main principles of the algorithm, we compare our approach to several most known cyclic scheduling algorithms using a significant existing example from the literature.