by Liang Fa Ming. / Publication date from spine. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1995. / Includes bibliographical references (leaves 49-53). / ABSTRACT --- p.1 / Chapter CHAPTER 1 : --- Introduction --- p.2 / Chapter 1.1 ： --- The TSP Problem --- p.2 / Chapter 1.2: --- Application --- p.3 / Chapter CHAPTER 2 : --- Review of Exact and Approximate Algorithms for TSP --- p.4 / Chapter 2.1 : --- Exact Algorithm --- p.4 / Chapter 2.2 : --- Heuristic Algorithms --- p.8 / Chapter CHAPTER 3 : --- Markov Chain Monte Carlo Methods --- p.16 / Chapter 3.1: --- Markov Chain Monte Carlo --- p.16 / Chapter 3.2 : --- Conditioning and Gibbs Sampler --- p.17 / Chapter 3.3: --- The Metropolis-Hasting Algorithm --- p.18 / Chapter 3.4: --- Auxiliary Variable Methods --- p.21 / Chapter CHAPTER 4: --- Weighted Markov Chain Monte Carlo Method --- p.24 / Chapter CHAPTER 5 : --- Traveling Salesman Problem --- p.31 / Chapter 5.1: --- Buildup Order --- p.33 / Chapter 5.2: --- Path Construction through a Group of Points --- p.34 / Chapter 5.3: --- Solving TSP Using the Weighted Markov Chain Method --- p.38 / Chapter 5.4: --- Temperature Scheme --- p.40 / Chapter 5.5 : --- How to Adjust the Constant Prior-Ratio --- p.41 / Chapter 5.6: --- Validation of Our Algorithm by a Simple Example --- p.41 / Chapter 5.7 : --- Adding/Deleting Blockwise --- p.42 / Chapter 5.8: --- The sequential Optimal Method and Post Optimization --- p.43 / Chapter 5. 9 : --- Composite Algorithm --- p.44 / Chapter 5.10: --- Numerical Comparisons and Tests --- p.45 / Chapter CHAPTER 6 : --- Conclusion --- p.48 / REFERENCES --- p.49 / APPENDIX A --- p.54 / APPENDIX B --- p.58 / APPENDIX C --- p.61

<p>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.</p>

Thesis. 1978. M.S.--Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING / Includes bibliographical references. / M.S.

Traveling salesman problem (TSP) is a well-known NP-hard problem which can not be solved within a polynomial bounded computation time. However, genetic algorithm (GA) is a familiar heuristic algorithm to obtain near-optimal solutions within reasonable time for TSPs. In TSPs, the geometric properties are problem specific knowledge can be used to enhance GAs. Some tour segments (edges) of TSPs are fine while some maybe too long to appear in a short tour. Therefore, this information can help GAs to pay more attention to fine tour segments and without considering long tour segments as often. Consequently, we propose a new algorithm, called intelligent-OPT hybrid genetic algorithm (IOHGA), to exploit local optimal tour segments and enhance the searching process in order to reduce the execution time and improve the quality of the offspring. The local optimal tour segments are assigned higher priorities for the selection of tour segments to be appeared in a short tour. By this way, tour segments of a TSP are divided into two separate sets. One is a candidate set which contains the candidate fine tour segments and the other is a non-candidate set which contains non-candidate fine tour segments. According to the priorities of tour segments, we devise two genetic operators, the skewed production (SP) and the fine subtour crossover (FSC). Besides, we combine the traditional GA with 2-OPT local search algorithm but with some modifications. The modified 2-OPT is named the intelligent OPT (IOPT). Simulation study was conducted to evaluate the performance of the IOHGA. The experimental results indicate that generally the IOHGA could obtain near-optimal solutions with less time and higher accuracy than the hybrid genetic algorithm with simulated annealing algorithm and the genetic algorithm using the gene expression algorithm. Thus, the IOHGA is an effective algorithm for solving TSPs. If the case is not focused on the optimal solution, the IOHGA can provide good near-optimal solutions rapidly. Therefore, the IOHGA could be incorporated with some clustering algorithm and applied to mobile agent planning problems (MAP) in a real-time environment.

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.

University of Macau / Faculty of Science and Technology / Department of Mathematics

This thesis is a survey on the approximability of the asymmetric traveling salesmanproblem with triangle inequality (ATSP).In the ATSP we are given a set of cities and a function that gives the cost of travelingbetween any pair of cities. The cost function must satisfy the triangle inequality, i.e.the cost of traveling from city A to city B cannot be larger than the cost of travelingfrom A to some other city C and then to B. However, we allow the cost function tobe asymmetric, i.e. the cost of traveling from city A to city B may not equal the costof traveling from B to A. The problem is then to find the cheapest tour that visit eachcity exactly once. This problem is NP-hard, and thus we are mainly interested in approximationalgorithms. We study the repeated cycle cover heuristic by Frieze et al. We alsostudy the Held-Karp heuristic, including the recent result by Asadpour et al. that givesa new upper bound on the integrality gap. Finally we present the result ofPapadimitriou and Vempala which shows that it is NP-hard to approximate the ATSP with a ratio better than 117/116.

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 &#8722; 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"