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.
| Identifer | oai:union.ndltd.org:NSYSU/oai:NSYSU:etd-0729104-141607 |
| Date | 29 July 2004 |
| Creators | Huang, Hung-Wei |
| Contributors | Yaw-Ling Lin, Yow-Ling Shiue, Chia-Ning Yang, Chang-Biau Yang, Yu-Li Wang |
| Publisher | NSYSU |
| Source Sets | NSYSU Electronic Thesis and Dissertation Archive |
| Language | English |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | http://etd.lib.nsysu.edu.tw/ETD-db/ETD-search/view_etd?URN=etd-0729104-141607 |
| Rights | off_campus_withheld, Copyright information available at source archive |
Page generated in 0.0022 seconds