Return to search

Solving the Traveling Salesman Problem by Ant Colony Optimization Algorithms with DNA Computing

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.

Identiferoai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0729104-141607
Date29 July 2004
CreatorsHuang, Hung-Wei
ContributorsYaw-Ling Lin, Yow-Ling Shiue, Chia-Ning Yang, Chang-Biau Yang, Yu-Li Wang
PublisherNSYSU
Source SetsNSYSU Electronic Thesis and Dissertation Archive
LanguageEnglish
Detected LanguageEnglish
Typetext
Formatapplication/pdf
Sourcehttp://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0729104-141607
Rightsoff_campus_withheld, Copyright information available at source archive

Page generated in 0.002 seconds