The Ant System is a new meta-heuristic method particularly appropriate to solve hard combinatorial optimization problems. It is a population-based, nature-inspired approach exploiting positive feedback as well as local information and has been applied successfully to a variety of combinatorial optimization problem classes. The Ant System consists of a set of cooperating agents (artificial ants) and a set of rules that determine the generation, update and usage of local and global information in order to find good solutions. As the structure of the Ant System highly suggests a parallel implementation of the algorithm, in this paper two parallelization strategies for an Ant System implementation are developed and evaluated: the synchronous parallel algorithm and the partially asynchronous parallel algorithm. Using the Traveling Salesman Problem a discrete event simulation is performed, and both strategies are evaluated on the criteria "speedup", "efficiency" and "efficacy". Finally further improvements for an advanced parallel implementation are discussed. (author's abstract) / Series: Report Series SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

One of the simplest, but still NP-hard, routing problems is the Traveling Salesman Problem (TSP). In the TSP, one is given a set of cities and a way of measuring the distance between cities. One has to find the shortest tour that visits all cities exactly once and returns back to the starting city. In state-of-the-art algorithms, they all assume that a complete graph is given as an input. However, for very large graphs, generating all edges in a complete graph, which corresponds to finding shortest paths for all city pairs, could be time-consuming. This is definitely a major obstacle for some real-life applications, especially when the tour needs to be generated in real-time. The objective, in this thesis, is to find a near-optimal TSP tour with a reduced set of edges in the complete graph. In particular, the following problems are investigated: which subset of edges can be produced in a shorter time comparing to the time for generating the complete graph? Is there a subset of edges in the complete graph that results in a better near-optimal tour than other sets? With a non-complete graph, which improvement algorithms work better? In this thesis, we study six algorithms to generate subsets of edges in a complete graph. To evaluate the proposed algorithms, extensive experiments are conducted with the well-known TSP data in a TSP library. In these experiments, we evaluate these algorithms in terms of tour quality, time and scalability.

Previous research on DNA computing has shown that DNA algorithms are useful to solve some combinatorial problems, such as the Hamiltonian path problem and the traveling salesman problem. The basic concept implicit in previous DNA algorithms is the brute force method. That is, all possible solutions are created initially, then inappropriate solutions are eliminated, and finally the remaining solutions are correct or the best ones. However, correct solutions may be destroyed while the procedure is executed. In order to avoid such an error, we recommend combining the conventional concepts of DNA computing with a heuristic optimization method and apply the new approach to design strategies. In this thesis, we present a DNA algorithm based on ant colony optimization (ACO) for solving the traveling salesman problem (TSP). Our method manipulates DNA strands of candidate solutions initially. Even if the correct solutions are destroyed during the process of filtering out, the remaining solutions can be reconstructed and correct solutions can be reformed. After filtering out inappropriate solutions, we employ control of melting temperature to amplify the surviving DNA strings proportionally. The product is used as the input and the iteration is performed repeatedly. Accordingly, the concentration of correct solutions will be increased. Our results agree with that obtained by conventional ant colony optimization algorithms and are better than that obtained by genetic algorithms. The same idea can be applied to design methods for solving other combinatorial problems with DNA computing.

In this thesis we use greedy randomize adaptive search procedure (GRASP) to solve the traveling salesman problem (TSP). Starting with nearest neighbor method to construct the initial TSP tour, we apply the 2-opt and the path-relinking method for the initial tour improvement. To increase 2-opt search speed, fixed-radius near neighbor search and don0t − look bit techniques are introduced. For the same reason a new efficient data structure, the reverse array, is proposed to represent the TSP tour. Computational results show that GRASP gives fairly good solutions in a short time.

The ant system is a new meta-heuristic for hard combinatorial optimization problems. It is a population-based approach that uses exploitation of positive feedback as well as greedy search. It was first proposed for tackling the well known Traveling Salesman Problem (TSP), but has been also successfully applied to problems such as quadratic assignment, job-shop scheduling, vehicle routing and graph coloring.In this paper we introduce a new rank based version of the ant system and present results of a computational study, where we compare the ant system with simulated annealing and a genetic algorithm on several TSP instances. It turns out that our rank based ant system can compete with the other methods in terms of average behavior, and shows even better worst case behavior. (author's abstract) / Series: Working Papers SFB "Adaptive Information Systems and Modelling in Economics and Management Science"

Dynamic Programming is an optimization technique used in computer science and mathematics. Introduced in the 1950s, it has been applied to many classic combinatorial optimization problems, such as the Shortest Path Problem, the Knapsack Problem, and the Traveling Salesman Problem, with varying degrees of practical success. In this thesis, we present two applications of dynamic programming to optimization problems. The first application is as a method to compute the Branch-Cut-and-Price (BCP) family of lower bounds for the Traveling Salesman Problem (TSP), and several vehicle routing problems that generalize it. We then prove that the BCP family provides a set of lower bounds that is at least as strong as the Approximate Linear Program (ALP) family of lower bounds for the TSP. The second application is a novel dynamic programming model used to determine the placement of cuts for a particular form of skull surgery called Cranial Vault Remodeling.

Thesis (M.S.)--Cleveland State University, 2009. / Abstract. Title from PDF t.p. (viewed on Sept. 8, 2009). Includes bibliographical references (p. 70-73). Available online via the OhioLINK ETD Center and also available in print.

The Tour Construction Framework (TCF) integrates both global and local heuristics in a complementary framework in order to efficiently solve the Travelling Salesman Problem (TSP). Most tour construction heuristics are strictly local in nature. However, the experimental method presented in this research includes a global heuristic to efficiently solve the TSP. The Global Path (GP) component and Super Node (SN) component comprise the TCF. Each component heuristic is tuned with one or more parameters. Genetic Algorithms (GA) are used to train the collection of parameters for the TCF components on subsets of benchmark TSPs. The GA results are used to run the TCF on the full TSP instances. The performance of the TCF is evaluated for speed, accuracy, and computational complexity, and it is compared against six mainstream TSP solvers: Lin-Kernighan-Helsgaun (LKH-2), 2-Opt, Greedy, Boruvka, Quick-Boruvka, and Nearest Neighbor. The empirical study demonstrates the effectiveness of the TCF in achieving near-optimal solutions for the TSP with reasonable costs.

Indiana University-Purdue University Indianapolis (IUPUI) / Brain connectome network visualization could help the neurologists inspect the brain structure easily and quickly. In the thesis, the model of the brain connectome network is visualized in both three dimensions (3D) environment and two dimensions (2D) environment. One is named “Brain Explorer for Connectomic Analysis” (BECA) developed by the previous research already. It could present the 3D model of brain structure with region of interests (ROIs) in different colors [5]. The other is mainly for the information visualization of brain connectome in 2D. It adopts the force-directed layout to visualize the network. However, the brain network visualization could not bring the user intuitively ideas about brain structure. Sometimes, with the increasing scales of ROIs (nodes), the visualization would bring more visual clutter for readers [3]. So, brain connectome network properties visualization becomes a useful complement to brain network visualization. For a better understanding of the effect of Alzheimer’s disease on the brain nerves, the thesis introduces several methods about the brain graph properties visualization. There are the five selected graph properties discussed in the thesis. The degree and closeness are node properties. The shortest path, maximum flow, and clique are edge properties. Except for clique, the other properties are visualized in both 3D and 2D. The clique is visualized only in 2D. For the clique, a new hypergraph visualization method is proposed with three different algorithms. Instead of using an extra node to present a clique, the thesis uses a “belt” to connect all nodes within the same clique. The methods of node connections are based on the traveling salesman problem (TSP) and Law of cosines. In addition, the thesis also applies the result of the clique to adjust the force-directed layout of brain graph in 2D to dramatically eliminate the visual clutter. Therefore, with the support of the graph properties visualization, the brain connectome network visualization tools become more flexible.

No / This paper presents a new class of heuristics which embed an exact algorithm within the framework of a local search heuristic. This approach was inspired by related heuristics which we developed for a practical problem arising in electronics manufacture. The basic idea of this heuristic is to break the original problem into small subproblems having similar properties to the original problem. These subproblems are then solved using time intensive heuristic approaches or exact algorithms and the solution is re-embedded into the original problem. The electronics manufacturing problem where we originally used the embedded local search approach, contains the Travelling Salesman Problem (TSP) as a major subproblem. In this paper we further develop our embedded search heuristic, HyperOpt, and investigate its performance for the TSP in comparison to other local search based approaches. We introduce an interesting hybrid of HyperOpt and 3-opt for asymmetric TSPs which proves more efficient than HyperOpt or 3-opt alone. Since pure local search seldom yields solutions of high quality we also investigate the performance of the approaches in an iterated local search framework. We examine iterated approaches of Large-Step Markov Chain and Variable Neighbourhood Search type and investigate their performance when used in combination with HyperOpt. We report extensive computational results to investigate the performance of our heuristic approaches for asymmetric and Euclidean Travelling Salesman Problems. While for the symmetric TSP our approaches yield solutions of comparable quality to 2-opt heuristic, the hybrid methods proposed for asymmetric problems seem capable of compensating for the time intensive embedded heuristic by finding tours of better average quality than iterated 3-opt in many less iterations and providing the best heuristic solutions known, for some instance classes.