Automatic Combination of Operators in a Genetic Algorithm to Solve the Traveling Salesman Problem

Genetic algorithms are powerful search methods inspired by Darwinian evolution. To date, they have been applied to the solution of many optimization problems because of the easy use of their properties and their robustness in finding good solutions to difficult problems. The good operation of genetic algorithms is due in part to its two main variation operators, namely, crossover and mutation operators. Typically, in the literature, we find the use of a single crossover and mutation operator. However, there are studies that have shown that using multi-operators produces synergy and that the operators are mutually complementary. Using multi-operators is not a simple task because which operators to use and how to combine them must be determined, which in itself is an optimization problem. In this paper, it is proposed that the task of exploring the different combinations of the crossover and mutation operators can be carried out by evolutionary computing. The crossover and mutation operators used are those typically used for solving the traveling salesman problem. The process of searching for good combinations was effective, yielding appropriate and synergic combinations of the crossover and mutation operators. The numerical results show that the use of the combination of operators obtained by evolutionary computing is better than the use of a single operator and the use of multi-operators combined in the standard way. The results were also better than those of the last operators reported in the literature.     

Genetic algorithm with local optimization

A hybrid of genetic algorithm and local optimization was tested on a massively multimodal spin-lattice problem involving a huge configuration space. The results are good, and global optima will probably be achieved in a sizeable proportion of cases, especially if a selection scheme is applied that maintains genetic diversity by introducing a spatial separation between the members of the population. If we use single-point cross-over, the performance of the algorithm depends strongly on the order of the units corresponding to individual spins in the bit strings that the genetic part of the algorithm processes. Due to some interplay between the genetic algorithm and local optimization, the best performance is achieved with a peculiar ordering, while the results with the most obvious ordering are much worse. I introduce an ordering-invariant crossover operation that gives excellent performance: it almost always yields states of the lowest energy. I expect this or some similar crossover operation to work well in the hybrid scheme for many other problems as well.     

Enhanced hybrid search algorithm for protein structure prediction using the 3D-HP lattice model

The problem of protein structure prediction in the hydrophobic-polar (HP) lattice model is the prediction of protein tertiary structure. This problem is usually referred to as the protein folding problem. This paper presents a method for the application of an enhanced hybrid search algorithm to the problem of protein folding prediction, using the three dimensional (3D) HP lattice model. The enhanced hybrid search algorithm is a combination of the particle swarm optimizer (PSO) and tabu search (TS) algorithms. Since the PSO algorithm entraps local minimum in later evolution extremely easily, we combined PSO with the TS algorithm, which has properties of global optimization. Since the technologies of crossover and mutation are applied many times to PSO and TS algorithms, so enhanced hybrid search algorithm is called the MCMPSO-TS (multiple crossover and mutation PSO-TS) algorithm. Experimental results show that the MCMPSO-TS algorithm can find the best solutions so far for the listed benchmarks, which will help comparison with any future paper approach. Moreover, real protein sequences and Fibonacci sequences are verified in the 3D HP lattice model for the first time. Compared with the previous evolutionary algorithms, the new hybrid search algorithm is novel, and can be used effectively to predict 3D protein folding structure. With continuous development and changes in amino acids sequences, the new algorithm will also make a contribution to the study of new protein sequences.     

Minimizing total flow time on a single flexible machine

In this study, we address a job sequencing and tool switching problem arising in flexible manufacturing systems. We consider the single machine problem of minimizing total flow time. We prove that the problem is NP-hard in the strong sense and show that the tool switching problem is polynomially solvable for a given sequence. We propose a branch-and-bound algorithm whose efficiency is improved by precedence relations and several lower and upper bounding techniques. Our computational results reveal that the branch and bound approach produces optimal solutions in reasonable times for moderate sized problems. Our upper bounds produce very satisfactory solutions; therefore they can be an attractive alternative to solve larger sized problems.     

Stationary solutions to a system of size-structured populations with nonlinear growth rate

We study stationary solutions to a system of size-structured population models with nonlinear growth rate. Several characterizations of stationary solutions are provided. It is shown that the steady-state problem can be converted into different problems such as two types of eigenvalue problems and a fixed-point problem. In the two-species case, we give an existence result of nonzero stationary solutions by using the fixed-point problem.     

On problem solving with Hopfield neural networks

Hopfield and Tank have shown that neural networks can be used to solve certain computationally hard problems, in particular they studied the Traveling Salesman Problem (TSP). Based on network simulation results they conclude that analog VLSI neural nets can be promising in solving these problems. Recently, Wilson and Pawley presented the results of their simulations which contradict the original results and cast doubts on the usefulness of neural nets. In this paper we give the results of our simulations that clarify some of the discrepancies. We also investigate the scaling of TSP solutions found by neural nets as the size of the problem increases. Further, we consider the neural net solution of the Clustering Problem, also a computationally hard problem, and discuss the types of problems that appear to be well suited for a neural net approach.     

Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics

We investigate a difficult scheduling problem in a semiconductor manufacturing process that seeks to minimize the number of tardy jobs and makespan with sequence-dependent setup time, release time, due dates and tool constraints. We propose a mixed integer programming (MIP) formulation which treats tardy jobs as soft constraints so that our objective seeks the minimum weighted sum of makespan and heavily penalized tardy jobs. Although our polynomial-sized MIP formulation can correctly model this scheduling problem, it is so difficult that even a feasible solution can not be calculated efficiently for small-scale problems. We then propose a technique to estimate the upper bound for the number of jobs processed by a machine, and use it to effectively reduce the size of the MIP formulation. In order to handle real-world large-scale scheduling problems, we propose an efficient dispatching rule that assigns a job of the earliest due date to a machine with least recipe changeover (EDDLC) and try to re-optimize the solution by local search heuristics which involves interchange, translocation and transposition between assigned jobs. Our computational experiments indicate that EDDLC and our proposed reoptimization techniques are very efficient and effective. In particular, our method usually gives solutions very close to the exact optimum for smaller scheduling problems, and calculates good solutions for scheduling up to 200 jobs on 40 machines within 10 min.     

A linear programming approach for identifying a consensus sequence on DNA sequences

MOTIVATION: Maximum-likelihood methods for solving the consensus sequence identification (CSI) problem on DNA sequences may only find a local optimum rather than the global optimum. Additionally, such methods do not allow logical constraints to be imposed on their models. This study develops a linear programming technique to solve CSI problems by finding an optimum consensus sequence. This method is computationally more efficient and is guaranteed to reach the global optimum. The developed method can also be extended to treat more complicated CSI problems with ambiguous conserved patterns. RESULTS: A CSI problem is first formulated as a non-linear mixed 0-1 optimization program, which is then converted into a linear mixed 0-1 program. The proposed method provides the following advantages over maximum-likelihood methods: (1) It is guaranteed to find the global optimum. (2) It can embed various logical constraints into the corresponding model. (3) It is applicable to problems with many long sequences. (4) It can find the second and the third best solutions. An extension of the proposed linear mixed 0-1 program is also designed to solve CSI problems with an unknown spacer length between conserved regions. Two examples of searching for CRP-binding sites and for FNR-binding sites in the Escherichia coli genome are used to illustrate and test the proposed method. AVAILABILITY: A software package, Global Site Seer for the Microsoft Windows operating system is available by http://www.iim.nctu.edu.tw/~cjfu/gss.htm     

A new fast algorithm for solving the minimum spanning tree problem based on DNA molecules computation

The minimum spanning tree (MST) problem is to find minimum edge connected subsets containing all the vertex of a given undirected graph. It is a vitally important NP-complete problem in graph theory and applied mathematics, having numerous real life applications. Moreover in previous studies, DNA molecular operations usually were used to solve NP-complete head-to-tail path search problems, rarely for NP-hard problems with multi-lateral path solutions result, such as the minimum spanning tree problem. In this paper, we present a new fast DNA algorithm for solving the MST problem using DNA molecular operations. For an undirected graph with n vertex and m edges, we reasonably design flexible length DNA strands representing the vertex and edges, take appropriate steps and get the solutions of the MST problem in proper length range and O(3m + n) time complexity. We extend the application of DNA molecular operations and simultaneity simplify the complexity of the computation. Results of computer simulative experiments show that the proposed method updates some of the best known values with very short time and that the proposed method provides a better performance with solution accuracy over existing algorithms.     

Genome rearrangement based on reversals that preserve conserved intervals

The order of genes in the genomes of species can change during evolution and can provide information about their phylogenetic relationship. An interesting method to infer the phylogenetic relationship from the gene orders is to use different types of rearrangement operations and to find possible rearrangement scenarios using these operations. One of the most common rearrangement operations is reversals, which reverse the order of a subset of neighbored genes. In this paper, we study the problem to find the ancestral gene order for three species represented by their gene orders. The rearrangement scenario should use a minimal number of reversals and no other rearrangement operations. This problem is called the Median problem and is known to be NP--complete. In this paper, we describe a heuristic algorithm for finding solutions to the Median problem that searches for rearrangement scenarios with the additional property that gene groups should not be destroyed by reversal operations. The concept of conserved intervals for signed permutations is used to describe such gene groups. We show experimentally, for different types of test problems, that the proposed algorithm produces very good results compared to other algorithms for the Median problem. We also integrate our reversal selection procedure into the well-known MGR and GRAPPA algorithms and show that they achieve a significant speedup while obtaining solutions of the same quality as the original algorithms on the test problems.     

Evolutionary optimization of RBF networks

One of the main obstacles to the widespread use of artificial neural networks is the difficulty of adequately defining values for their free parameters. This article discusses how Radial Basis Function (RBF) networks can have their parameters defined by genetic algorithms. For such, it presents an overall view of the problems involved and the different approaches used to genetically optimize RBF networks. A new strategy to optimize RBF networks using genetic algorithms is proposed, which includes new representation, crossover operator and the use of a multiobjective optimization criterion. Experiments using a benchmark problem are performed and the results achieved using this model are compared to those achieved by other approaches.     

Controlling precise movement with stochastic signals

In a noisy system, such as the nervous system, can movements be precisely controlled as experimentally demonstrated? We point out that the existing theory of motor control fails to provide viable solutions. However, by adopting a generalized approach to the nonconvex optimization problem with the Young measure theory, we show that a precise movement control is possible even with stochastic control signals. Numerical results clearly demonstrate that a considerable significant improvement of movement precisions is achieved. Our generalized approach proposes a new way to solve optimization problems in biological systems when a precise control is needed.     

No braiding of Holliday junctions in positively supercoiled DNA molecules

The Holliday junction is a prominent intermediate in genetic recombination that consists of four double helical arms of DNA flanking a branch point. Under many conditions, the Holliday junction arranges its arms into two stacked domains that can be oriented so that genetic markers are parallel or antiparallel. In this arrangement, two strands retain a helical conformation, and the other two strands effect the crossover between helical domains. The products of recombination are altered by a crossover isomerization event, which switches the strands fulfilling these two roles. It appears that effecting this switch from the parallel conformation by the simplest mechanism results in braiding the crossover strands at the branch point. In previous work we showed by topological means that a short, parallel, DNA double crossover molecule with closed ends did not braid its branch point; however, that molecule was too short to adopt the necessary positively supercoiled topology. Here, we have addressed the same problem using a larger molecule of the same type. We have constructed a parallel DNA double crossover molecule with closed ends, containing 14 double helical turns in each helix between its crossover points. We have prepared this molecule in a relaxed form by simple ligation and in a positively supercoiled form by ligation in the presence of netropsin. The positively supercoiled molecule is of the right topology to accommodate braiding. We have compared the relaxed and supercoiled versions for their responses to probes that include hydroxyl radicals, KMnO4, the junction resolvases endonuclease VII and RuvC, and RuvC activation of KMNO4 sensitivity. In no case did we find evidence for a braid at the crossover point. We conclude that Holliday junctions do not braid at their branch points, and that the topological problem created by crossover isomerization in the parallel conformation is likely to be solved by distributing the stress over the helices that flank the branch point.     

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.     

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.     

Ecology after 100 years: Progress and pseudo-progress

Has the science of ecology fulfilled the promises made by the originators of ecological science at the start of the last century? What should ecology achieve? Have good policies for environmental management flowed out of ecological science? These important questions are rarely discussed by ecologists working on detailed studies of individual systems. Until we decide what we wish to achieve as ecologists we cannot define progress toward those goals. Ecologists desire to achieve an understanding of how the natural world operates, how humans have modified the natural world, and how to alleviate problems arising from human actions. Ecologists have made impressive gains over the past century in achieving these goals, but this progress has been uneven. Some sub-disciplines of ecology are well developed empirically and theoretically, while others languish for reasons that are not always clear. Fundamental problems can be lost to view as ecologists fiddle with unimportant pseudo-problems. Bandwagons develop and disappear with limited success in addressing problems. The public demands progress from all the sciences, and as time moves along and problems get worse, more rapid progress is demanded. The result for ecology has too often been poor, short-term science and poor management decisions. But since the science is rarely repeated and the management results may be a generation or two down the line, it is difficult for the public or for scientists to decide how good or bad the scientific advice has been. In ecology over the past 100 years we have made solid achievements in behavioural ecology, population dynamics, and ecological methods, we have made some progress in understanding community and ecosystem dynamics, but we have made less useful progress in developing theoretical ecology, landscape ecology, and natural resource management. The key to increasing progress is to adopt a systems approach with explicit hypotheses, theoretical models, and field experiments on a scale defined by the problem. With continuous feedback between problems, possible solutions, relevant theory and experimental data we can achieve our scientific goals.     

Solving the SAT problem using a DNA computing algorithm based on ligase chain reaction

A new DNA computing algorithm based on a ligase chain reaction is demonstrated to solve an SAT problem. The proposed DNA algorithm can solve an n-variable m-clause SAT problem in m steps and the computation time required is O (3m+n). Instead of generating the full-solution DNA library, we start with an empty test tube and then generate solutions that partially satisfy the SAT formula. These partial solutions are then extended step by step by the ligation of new variables using Taq DNA ligase. Correct strands are amplified and false strands are pruned by a ligase chain reaction (LCR) as soon as they fail to satisfy the conditions. If we score and sort the clauses, we can use this algorithm to markedly reduce the number of DNA strands required throughout the computing process. In a computer simulation, the maximum number of DNA strands required was 2(0.48n) when n=50, and the exponent ratio varied inversely with the number of variables n and the clause/variable ratio m/n. This algorithm is highly space-efficient and error-tolerant compared to conventional brute-force searching, and thus can be scaled-up to solve large and hard SAT problems.     

Advances in blind source separation (BSS) and independent component analysis (ICA) for nonlinear mixtures

In this paper, we review recent advances in blind source separation (BSS) and independent component analysis (ICA) for nonlinear mixing models. After a general introduction to BSS and ICA, we discuss in more detail uniqueness and separability issues, presenting some new results. A fundamental difficulty in the nonlinear BSS problem and even more so in the nonlinear ICA problem is that they provide non-unique solutions without extra constraints, which are often implemented by using a suitable regularization. In this paper, we explore two possible approaches. The first one is based on structural constraints. Especially, post-nonlinear mixtures are an important special case, where a nonlinearity is applied to linear mixtures. For such mixtures, the ambiguities are essentially the same as for the linear ICA or BSS problems. The second approach uses Bayesian inference methods for estimating the best statistical parameters, under almost unconstrained models in which priors can be easily added. In the later part of this paper, various separation techniques proposed for post-nonlinear mixtures and general nonlinear mixtures are reviewed.     

Enhancing distributed EAs by a proactive strategy

In this work we propose a new distributed evolutionary algorithm that uses a proactive strategy to adapt its migration policy and the mutation rate. The proactive decision is carried out locally in each subpopulation based on the entropy of that subpopulation. In that way, each subpopulation can change their own incoming flow of individuals by asking their neighbors for more frequent or less frequent migrations in order to maintain the genetic diversity at a desired level. Moreover, this proactive strategy is reinforced by adapting the mutation rate while the algorithm is searching for the problem solution. All these strategies avoid the subpopulations to get trapped into local minima. We conduct computational experiments on large instances of the NK landscape problem which have shown that our proactive approach outperforms traditional dEAs, particularly for not highly rugged landscapes, in which it does not only reaches the most accurate solutions, but it does the fastest.