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.     

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.     

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     

A novel method for estimating linkage maps

The goal of linkage mapping is to find the true order of loci from a chromosome. Since the number of possible orders is large even for a modest number of loci, the problem of finding the optimal solution is known as a NP-hard problem or traveling salesman problem (TSP). Although a number of algorithms are available, many either are low in the accuracy of recovering the true order of loci or require tremendous amounts of computational resources, thus making them difficult to use for reconstructing a large-scale map. We developed in this article a novel method called unidirectional growth (UG) to help solve this problem. The UG algorithm sequentially constructs the linkage map on the basis of novel results about additive distance. It not only is fast but also has a very high accuracy in recovering the true order of loci according to our simulation studies. Since the UG method requires n-1 cycles to estimate the ordering of n loci, it is particularly useful for estimating linkage maps consisting of hundreds or even thousands of linked codominant loci on a chromosome.     

Genetic algorithms for the traveling salesman problem based on a heuristic crossover operation

We apply strategies inspired by natural evolution to a classical example of discrete optimization problems, the traveling salesman problem. Our algorithms are based on a new knowledge-augmented crossover operation. Even if we use only this operation in the reproduction process, we get quite good results. The most obvious faults of the solutions can be eliminated and the results can further be improved by allowing for a simple form of mutation. If each crossover is followed by an affordable local optimization, we get the optimum solution for a 318-town problem, probably the optimum solutions for several different 100-town problems, and very nearly optimum solutions for 350-town and 1000-town problems. A new strategy for the choice of parents considerably speeds up the convergence of the latter method.     

Simulation of neurocomputing based on the photophobic reactions of Euglena with optical feedback stimulation

To explore possible forms of unconventional computers that have high capacities for adaptation and exploration, we propose a new approach to developing a biocomputer based on the photophobic reactions of microbes (Euglena gracilis), and perform the Monte-Carlo simulation of Euglena-based neural network computing, involving virtual optical feedback to the Euglena cells. The photophobic reactions of Euglena are obtained experimentally, and incorporated in the simulation, together with a feedback algorithm with a modified Hopfield–Tank model for solving a 4-city traveling salesman problem. The simulation shows high performances in terms of (1) reaching one of the best solutions of the problem, and (2) searching for a number of solutions via dynamic transition among the solutions. This dynamic transition is attributed to the fluctuation of state variables, global oscillation through feedback instability, and the one-by-one change of state variables.     

Reconstruction of phylogenetic trees using the ant colony optimization paradigm

We developed a new approach for the reconstruction of phylogenetic trees using ant colony optimization metaheuristics. A tree is constructed using a fully connected graph and the problem is approached similarly to the well-known traveling salesman problem. This methodology was used to develop an algorithm for constructing a phylogenetic tree using a pheromone matrix. Two data sets were tested with the algorithm: complete mitochondrial genomes from mammals and DNA sequences of the p53 gene from several eutherians. This new methodology was found to be superior to other well-known softwares, at least for this data set. These results are very promising and suggest more efforts for further developments.     

Reducing topological defects in self-organizing maps using multiple scale neighborhood functions

In this paper, we propose a method of reducing topological defects in self-organizing maps (SOMs) using multiple scale neighborhood functions. The multiple scale neighborhood functions are inspired by multiple scale channels in the human visual system. To evaluate the proposed method, we applied it to the traveling salesman problem (TSP), and examined two indexes: the tour length of the solution and the number of kinks in the solution. Consequently, the two indexes are lower for the proposed method. These results indicate that our proposed method has the ability to reduce topological defects.     

Solving traveling salesman problems with DNA molecules encoding numerical values

We introduce a DNA encoding method to represent numerical values and a biased molecular algorithm based on the thermodynamic properties of DNA. DNA strands are designed to encode real values by variation of their melting temperatures. The thermodynamic properties of DNA are used for effective local search of optimal solutions using biochemical techniques, such as denaturation temperature gradient polymerase chain reaction and temperature gradient gel electrophoresis. The proposed method was successfully applied to the traveling salesman problem, an instance of optimization problems on weighted graphs. This work extends the capability of DNA computing to solving numerical optimization problems, which is contrasted with other DNA computing methods focusing on logical problem solving.     

Finding the trade-off between emissions and disturbance in an urban context

We introduce the bi-objective emissions disturbance traveling salesman problem (BEDTSP), which aims at minimizing carbon dioxide emissions (\(\hbox {CO}_2\)) as well as disturbance to urban neighborhoods, when planning the tour of a single vehicle delivering goods to customers. Although there exist recent studies on minimizing emissions, we are not aware of any work on minimizing disturbance. We develop four different mathematical models for the BEDTSP. We also develop several data generation strategies for minimizing disturbance. These strategies consider optional nodes, thus allowing detours that yield less disturbance but also possibly more emissions. All models and strategies are compared in an extensive computational study. Experimental results allow us to derive clear guidelines for which model and data generation strategy to use in which context. Following these guidelines, we conduct a case study for the city of Vienna.     

Sequencing of parts and robot moves in a robotic cell

In this paper, we deal with the problem of sequencing parts and robot moves in a robotic cell where the robot is used to feed machines in the cell. The robotic cell, which produces a set of parts of the same or different types, is a flow-line manufacturing system. Our objective is to maximize the long-run average throughput of the system subject to the constraint that the parts are to be produced in proportion of their demand. The cycle time formulas are developed and analyzed for this purpose for cells producing a single part type using two or three machines. A state space approach is used to address the problem. Both necessary and sufficient conditions are obtained for various cycles to be optimal. Finally, in the case of many part types, the problem of scheduling parts for a specific sequence of robot moves in a two machine cell is formulated as a solvable case of the traveling salesman problem.     

Probabilistic nucleotide assembling method for sequencing by hybridization

MOTIVATION: Developing a new method of assembling small sequences based on sequencing by hybridization with many positive and negative faults. First, an interpretation of a generic traveling salesman problem is provided (i.e. finding the shortest route for visiting many cities), using genetic algorithms. Second, positive errors are excluded before assembly by a sanitization process. RESULTS: The present method outperforms those described in previous studies, in terms of both time and accuracy. AVAILABILITY: http://kamit.med.u-tokai.ac.jp/~takaho/sbh/index.html     

Machine setup and component placement in printed circuit board assembly

Populating printed circuit boards is one of the most costly and time-consuming steps in electronics assembly. At the beginning of each work order, three decisions are required: (1) a sequence must be specified for placing the individual components on the board; (2) tape reels must be assigned to positions on the magazine rack; and (3) a retrieval plan must be determined should the same component type be assigned to more than one magazine slot. Collectively, these problems can be modeled as a nonlinear integer program. In this paper, we develop a series of algorithms for solving each using an iterative two step approach. Initially, a placement sequence is generated with a weighted, nearest neighbor traveling salesman problem (TSP) heuristic; the two remaining problems are then formulated as a quadratic integer program and solved with a Lagrangian relaxation scheme. As a final step, the current magazine assignments are used to update the placement sequence, and the entire process is repeated. Our ability to deal, at least in part, with simultaneous machine operations represents the major contribution of this work. The methodology was simulated for a set of boards obtained from Texas Instruments and theoretically compared with a heuristic currently in use.     

Reconstruction of Ancestral Gene Orders Using Probabilistic and Gene Encoding Approaches

Current tools used in the reconstruction of ancestral gene orders often fall into event-based and adjacency-based methods according to the principles they follow. Event-based methods such as GRAPPA are very accurate but with extremely high complexity, while more recent methods based on gene adjacencies such as InferCARsPro is relatively faster, but often produces an excessive number of chromosomes. This issue is mitigated by newer methods such as GapAdj, however it sacrifices a considerable portion of accuracy. We recently developed an adjacency-based method in the probabilistic framework called PMAG to infer ancestral gene orders. PMAG relies on calculating the conditional probabilities of gene adjacencies that are found in the leaf genomes using the Bayes'' theorem. It uses a novel transition model which accounts for adjacency changes along the tree branches as well as a re-rooting procedure to prevent any information loss. In this paper, we improved PMAG with a new method to assemble gene adjacencies into valid gene orders, using an exact solver for traveling salesman problem (TSP) to maximize the overall conditional probabilities. We conducted a series of simulation experiments using a wide range of configurations. The first set of experiments was to verify the effectiveness of our strategy of using the better transition model and re-rooting the tree under the targeted ancestral genome. PMAG was then thoroughly compared in terms of three measurements with its four major competitors including InferCARsPro, GapAdj, GASTS and SCJ in order to assess their performances. According to the results, PMAG demonstrates superior performance in terms of adjacency, distance and assembly accuracies, and yet achieves comparable running time, even all TSP instances were solved exactly. PMAG is available for free at http://phylo.cse.sc.edu.     

Stress-induced male sterility and mixed mating in the island plantCedronella canariensis (Lamiaceae)

Reaction norms were determined in two natural populations of the perennial plantIris pumila from contrasting light conditions at two levels of photosynthetically active radiation (105 and 35 µmol m^–2s^–1). Seedlings developed from free-pollinated seed families sampled individually from 19 and 12 randomly selected clonal genotypes in an exposed and a shaded population respectively, were grown in a growth room using a mixed model nested factorial experimental design and scored for a number of phenological and morphological traits. Ambient light conditions significantly affected all of the juvenile traits measured. In both populations, relatively convergent norms of reactions were revealed for leaf appearance dates, as well as for leaf number, suggesting the importance of these traits for functional adjustment to prevailing light conditions. Reaction norms for morphological traits, however, were largely nonparallel, but although often crossing each other, a significant family-by-treatment interaction in the ANCOVAs performed was not detected for any of the traits measured, indicating a small amount of genetic variation for plasticity in these populations. The extent of plastic response to light availability was determined and expressed as an index that estimates the percentage change in a trait value from a high to a low light level. Evolutionary and ecological implications of the observed plastic variations are also discussed.     

A semi-localized elastic net for surface reconstruction of objects from multislice images

The traveling salesman problem (TSP) is a prototypical problem of combinatorial optimization and, as such, it has received considerable attention from neural-network researchers seeking quick, heuristic solutions. An early stage in many computer vision tasks is the extraction of object shape from an image consisting of noisy candidate edge points. Since the desired shape will often be a closed contour, this problem can be viewed as a version of the TSP in which we wish to link only a subset of the points/cities (i.e. the "noisefree" ones). None of the extant neural techniques for solving the TSP can deal directly with this case. In this paper, we present a simple but effective modification to the (analog) elastic net of Durbin and Willshaw which shifts emphasis from global to local behavior during convergence, so allowing the net to ignore some image points. Unlike the original elastic net, this semi-localized version is shown to tolerate considerable amounts of noise. As an example practical application, we describe the extraction of "pseudo-3D" human lung outlines from multiple preprocessed magnetic resonance images of the torso. An effectiveness measure (ideally zero) quantifies the difference between the extracted shape and some idealized shape exemplar. Our method produces average effectiveness scores of 0.06 for lung shapes extracted from initial semi-automatic segmentations which define the noisefree case. This deteriorates to 0.1 when extraction is from a noisy edge-point image obtained fully-automatically using a feedforward neural network.     

Optimization with neural networks: a recipe for improving convergence and solution quality

Artificial Neural Networks, particularly the Hopfield Network have been applied to the solution of a variety of tasks formulated as optimization problems. However, the network often converges to invalid solutions, which have been attributed to an improper choice of parameters and energy functions. In this letter, we propose a fundamental change of viewpoint. We assert that the problem is not due to the bad choice of parameters or the form of the energy function chosen. Instead, we show that the Hopfield Net essentially performs only one iteration of a Sequential Unconstrained Minimization Technique (SUMT). Thus, it is not surprising that unsatisfactory results are obtained. We present results on an SUMT-based formulation for the Travelling Salesman Problem, where we consistently obtained valid tours. We also show how shorter tours can be systematically obtained.     

Polyamines are absorbed through a y+ amino acid carrier in rat intestinal epithelial cells

Summary. Due to the similarity in transport characteristics of polyamines and the y⁺ basic amino acid system, we hypothesized that both substrates could be moving through a common carrier site. Competitive and cross inhibition experiments in intestinal epithelial cells revealed the possibility of a common transport site. N-ethylmalemide (NEM) inhibited both lysine and putrescine transport, confirming that both were carried by a y⁺ transporter. Overexpressing the y⁺ transporter CAT-1 in a polyamine transport-deficient cell line, CHO-MG, did not reconstitute polyamine-transport. Thus, polyamines are not traveling through CAT-1. To determine if lysine is carried by a polyamine transport site, an antizyme-overexpressing cell line was used. Antizyme overexpression decreased polyamine uptake by 50%; in contrast, lysine transport was unaffected. Therefore, lysine is not traveling through a polyamine transport site. It appears that polyamines and lysine are likely traveling through a common unknown y⁺ transport site.     

A novel ACO algorithm for optimization via reinforcement and initial bias

In this paper, we introduce the MAF-ACO algorithm, which emulates the foraging behavior of ants found in nature. In addition to the usual pheromone model present in ACO algorithms, we introduce an incremental learning component. We view the components of the MAF-ACO algorithm as stochastic approximation algorithms and use the ordinary differential equation (o.d.e.) method to analyze their convergence. We examine how the local stigmergic interaction of the individual ants results in an emergent dynamic programming framework. The MAF-ACO algorithm is also applied to the multi-stage shortest path problem and the traveling salesman problem. Research of Prof. V.S. Borkar was supported in part by grant no. III.5(157)/99-ET and a J.C. Bose Fellowship from the Department of Science and Technology, Government of India.