Using traveling salesman problem algorithms for evolutionary tree construction

MOTIVATION: The construction of evolutionary trees is one of the major problems in computational biology, mainly due to its complexity. RESULTS: We present a new tree construction method that constructs a tree with minimum score for a given set of sequences, where the score is the amount of evolution measured in PAM distances. To do this, the problem of tree construction is reduced to the Traveling Salesman Problem (TSP). The input for the TSP algorithm are the pairwise distances of the sequences and the output is a circular tour through the optimal, unknown tree plus the minimum score of the tree. The circular order and the score can be used to construct the topology of the optimal tree. Our method can be used for any scoring function that correlates to the amount of changes along the branches of an evolutionary tree, for instance it could also be used for parsimony scores, but it cannot be used for least squares fit of distances. A TSP solution reduces the space of all possible trees to 2n. Using this order, we can guarantee that we reconstruct a correct evolutionary tree if the absolute value of the error for each distance measurement is smaller than f2.gif" BORDER="0">, where f3.gif" BORDER="0">is the length of the shortest edge in the tree. For data sets with large errors, a dynamic programming approach is used to reconstruct the tree. Finally simulations and experiments with real data are shown.     

An evolutionary approach to the traveling salesman problem

Evolutionary optimization has been proposed as a method to generate machine learning through automated discovery. A simulation of natural evolution is conducted using the traveling salesman problem as an artificial environment. For an exact solution of a traveling salesman problem, the only known algorithms require the number of steps to grow at least exponentially with the number of elements in the problem. Three adaptive techniques are described and analyzed. Evolutionary adaptation is demonstrated to be worthwhile in a variety of contexts. Local stagnation is prevented by allowing for the probabilistic survival of the simulated organisms. In complex problems, the final routing is estimated to be better than 99.99999999999% of all possible tours, even though only a small fraction (8.58 × 10^–151) of the total number of tours are examined.     

Learning to cooperate in solving the traveling salesman problem

A cooperative team of agents may perform many tasks better than single agents. The question is how cooperation among self-interested agents should be achieved. It is important that, while we encourage cooperation among agents in a team, we maintain autonomy of individual agents as much as possible, so as to maintain flexibility and generality. This paper presents an approach based on bidding utilizing reinforcement values acquired through reinforcement learning. We tested and analyzed this approach and demonstrated that a team indeed performed better than the best single agent as well as the average of single agents.     

Evolutionary algorithms for solving multi-objective travelling salesman problem

This paper studies the application of evolutionary algorithms for bi-objective travelling salesman problem. Two evolutionary algorithms, including estimation of distribution algorithm (EDA) and genetic algorithm (GA), are considered. The solution to this problem is a set of trade-off alternatives. The problem is solved by optimizing the order of the cities so as to simultaneously minimize the two objectives of travelling distance and travelling cost incurred by the travelling salesman. In this paper, binary-representation-based evolutionary algorithms are replaced with an integer-representation. Three existing EDAs are altered to use this integer-representation, namely restricted Boltzmann machine (RBM), univariate marginal distribution algorithm (UMDA), and population-based incremental learning (PBIL). Each city is associated with a representative integer, and the probability of any of this representative integer to be located in any position of the chromosome is constructed through the modeling approach of the EDAs. New sequences of cities are obtained by sampling from the probabilistic model. A refinement operator and a local search operator are proposed in this piece of work. The EDAs are subsequently hybridized with GA in order to complement the limitations of both algorithms. The effect that each of these operators has on the quality of the solutions are investigated. Empirical results show that the hybrid algorithms are capable of finding a set of good trade-off solutions.     

Theoretical analysis of two ACO approaches for the traveling salesman problem

Bioinspired algorithms, such as evolutionary algorithms and ant colony optimization, are widely used for different combinatorial optimization problems. These algorithms rely heavily on the use of randomness and are hard to understand from a theoretical point of view. This paper contributes to the theoretical analysis of ant colony optimization and studies this type of algorithm on one of the most prominent combinatorial optimization problems, namely the traveling salesperson problem (TSP). We present a new construction graph and show that it has a stronger local property than one commonly used for constructing solutions of the TSP. The rigorous runtime analysis for two ant colony optimization algorithms, based on these two construction procedures, shows that they lead to good approximation in expected polynomial time on random instances. Furthermore, we point out in which situations our algorithms get trapped in local optima and show where the use of the right amount of heuristic information is provably beneficial.     

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.     

Optimal foraging and the traveling salesman

Optimal foraging models are examined that assume animals forage for discrete point resources on a plane and attempt to minimize their travel distance between resources. This problem is similar to the well-known traveling salesman problem: A salesman must choose the shortest path from his home office to all cities on his itinerary and back to his home office again. The traveling salesman problem is in a class of enigmatic problems, called NP-complete, which can be so difficult to solve that animals might be incapable of finding the best solution. Two major results of this analysis are: (1) The simple foraging strategy of always moving to the closest resource site does surprisingly well. More sophisticated strategies of “looking ahead” a small number of steps, choosing the shortest path, then taking a step, do worse if all the resource sites are visited, but do slightly better (less than 10%) if not all the resource sites are visited. (2) Short cyclical foraging routes resulted when resources were allowed to renew. This is suggested as an alternative explanation for “trap-lining” in animals that forage for discrete, widely separated resources.     

Solving a combinatorial problem via self-organizing process: An application of the Kohonen algorithm to the traveling salesman problem

We present an application of the Kohonen algorithm to the traveling salesman problem: Using only this algorithm, without energy function nor any parameter choosen ad hoc, we found good suboptimal tours. We give a neural model version of this algorithm, closer to classical neural networks. This is illustrated with various numerical examples.     

A traveling salesman approach for predicting protein functions

Background  

Protein-protein interaction information can be used to predict unknown protein functions and to help study biological pathways.     

Amoeba-based computing for traveling salesman problem: Long-term correlations between spatially separated individual cells of Physarum polycephalum

A single-celled, multi-nucleated amoeboid organism, a plasmodium of the true slime mold Physarum polycephalum, can perform sophisticated computing by exhibiting complex spatiotemporal oscillatory dynamics while deforming its amorphous body. We previously devised an “amoeba-based computer (ABC)” to quantitatively evaluate the optimization capability of the amoeboid organism in searching for a solution to the traveling salesman problem (TSP) under optical feedback control. In ABC, the organism changes its shape to find a high quality solution (a relatively shorter TSP route) by alternately expanding and contracting its pseudopod-like branches that exhibit local photoavoidance behavior. The quality of the solution serves as a measure of the optimality of which the organism maximizes its global body area (nutrient absorption) while minimizing the risk of being illuminated (exposure to aversive stimuli). ABC found a high quality solution for the 8-city TSP with a high probability. However, it remains unclear whether intracellular communication among the branches of the organism is essential for computing. In this study, we conducted a series of control experiments using two individual cells (two single-celled organisms) to perform parallel searches in the absence of intercellular communication. We found that ABC drastically lost its ability to find a solution when it used two independent individuals. However, interestingly, when two individuals were prepared by dividing one individual, they found a solution for a few tens of minutes. That is, the two divided individuals remained correlated even though they were spatially separated. These results suggest the presence of a long-term memory in the intrinsic dynamics of this organism and its significance in performing sophisticated computing.     

State-space search strategies gleaned from animal behavior: a traveling salesman experiment

A widespread search strategy employed by predators in both vertebrate and invertebrate phyla is the well-known area-restricted search strategy. The generality, simplicity, and effectiveness of this strategy have made it emerge many times during the course of natural selection. In this work, an artificial intelligence state-space search procedure is developed using search guidelines gleaned from the foraging behavior of predators. This procedure, which we call predatory search, has been implemented on a NP-Hard combinatorial problem: the traveling salesman problem. Numerical results are presented for a limited set of benchmark problems, and area-restricted search seems to be effective: We have been able to find the optimal solution to, among others, a 400-city Manhattan problem. Received: 9 July 1997 / Accepted in revised form: 24 November 1997     

基于启发式算法预测含假结RNA二级结构的研究进展

RNA二级结构的预测算法研究已有近40年的发展历程,研究假结也将近30年的历史。在此期间,RNA二级结构的预测算法取得了很大进步,但假结预测的正确率依然偏低。其中启发式算法能较好地处理复杂假结,使其成为率先解决假结预测难题可能性最大的算法。迄今为止,未见系统地专门总结预测假结的各种启发式算法及其优点与缺点的报道。本文详细介绍了近年来国际上流行的贪婪算法、遗传算法、ILM算法、HotKnots算法以及FlexStem算法等五种算法,并总结分析了每种算法的优点与不足,最后提出在未来一段时期内,利用启发式算法提高假结预测准确度应从建立更完善的假结模型、加入更多影响因素、借鉴不同算法的优势等方面入手。为含假结RNA二级结构预测的研究提供参考。     

HLA serum screening based on an heuristic solution of the set cover problem.

A computer program initially written by the Milwaukee Blood Bank has been modified to use a new algorithm for the assignment of HLA specificities to antisera. The assignment is based on the reactions of cells with known specificities. Specificities which are present only on cells which do not react are first ruled out. This step is followed by one or more steps in which the 'least reactive' specificities are ruled out. The rationale for the algorithm is discussed and an example is presented.     

Exact and heuristic algorithms for the Indel Maximum Likelihood Problem.

Given a multiple alignment of orthologous DNA sequences and a phylogenetic tree for these sequences, we investigate the problem of reconstructing the most likely scenario of insertions and deletions capable of explaining the gaps observed in the alignment. This problem, that we called the Indel Maximum Likelihood Problem (IMLP), is an important step toward the reconstruction of ancestral genomics sequences, and is important for studying evolutionary processes, genome function, adaptation and convergence. We solve the IMLP using a new type of tree hidden Markov model whose states correspond to single-base evolutionary scenarios and where transitions model dependencies between neighboring columns. The standard Viterbi and Forward-backward algorithms are optimized to produce the most likely ancestral reconstruction and to compute the level of confidence associated to specific regions of the reconstruction. A heuristic is presented to make the method practical for large data sets, while retaining an extremely high degree of accuracy. The methods are illustrated on a 1-Mb alignment of the CFTR regions from 12 mammals.     

A neural network algorithm for the multiple traveling salesmen problem

We developed an efficient neural network algorithm for solving the Multiple Traveling Salesmen Problem (MTSP). A new transformation of the N-city M-salesmen MTSP to the standard Traveling Salesmen Problem (TSP) is introduced. The transformed problem is represented by an expanded version of Hopfield-Tank's neuromorphic city-position map with (N + M-1)-cities and a single fictitious salesmen. The dynamic model associated with the problem is based on the Basic Differential Multiplier Method (BDMM) [26] which evaluates Lagrange multipliers simultaneously with the problem's state variables. The algorithm was successfully tested on many problems with up to 30 cities and five salesmen. In all test cases, the algorithm always converged to valid solutions. The great advantage of this kind of algorithm is that it can provide solutions to complex decision making problems directly by solving a system of ordinary differential equations. No learning steps, logical if statements or adjusting of parameters are required during the computation. The algorithm can therefore be implemented in hardware to solve complex constraint satisfaction problems such as the MTSP at the speed of analog silicon VLSI devices or possibly future optical neural computers.     

An efficient harris hawk optimization algorithm for solving the travelling salesman problem

Cluster Computing - Travelling Salesman Problem (TSP) is an Np-Hard problem, for which various solutions have been offered so far. Using the Harris Hawk Optimization (HHO) algorithm, this paper...     

Improving genetic algorithms for protein folding simulations by systematic crossover

To improve protein folding simulations, we investigated a new search strategy in combination with the simple genetic algorithm on a two-dimensional lattice model. This search strategy, we called systematic crossover, couples the best individuals, tests every possible crossover point, and takes the two best individuals for the next generation. We compared the standard genetic algorithm with and without this new implementation for various chain lengths and showed that this strategy finds local minima with better energy values and is significantly faster in identifying the global minimum than the standard genetic algorithm.     

Parallel deterministic local search heuristic for minimum latency problem

Cluster Computing - Minimum latency problem (MLP) is an NP-Hard combinatorial optimization problem. Metaheuristics use perturbation and randomization to arrive at a satisfactory solution under time...     

A heuristic algorithm for the loading problem in flexible manufacturing systems

The paper considers the loading problem in flexible manufacturing systems (FMSs). This problem involves the assignment to the machine tools of all operations and associated cutting tools required for part types that have been selected to be produced simultaneously. The loading problem is first formulated as a linear mixed 0–1 program with the objective to minimize the greatest workload assigned to each machine. A heuristic procedure is presented in which an assignment of operations to machine tools is obtained by solving a parameterized generalized assignment problem with an objective function that approximates the use of tool slots required by the operations assigned to the machines. The algorithm is coded in FORTRAN and tested on an IBM-compatible personal computer. Computational results are presented for different test problems to demonstrate the efficiency and effectiveness of the suggested procedure.     

Ramping up a heuristic procedure for storage location assignment problem with precedence constraints

Flexible Services and Manufacturing Journal - The retail industry is becoming increasingly competitive; as a result, companies are seeking to reduce inefficiencies in their supply chains. One way...