Performance of heuristic methods driven by chaotic dynamics for ATSP and applications to DNA fragment assembly

スポンサーリンク

概要

• 論文の詳細を見る

• Chaotic dynamics has been shown to be effective in improving the performance of combinatorial optimization algorithms. In this paper, the performance of chaotic dynamics in the asymmetric traveling salesman problem (ATSP) is investigated by introducing three types of heuristic solution update methods. Numerical simulation has been carried out to compare its performance with simulated annealing and tabu search; thus, the effectiveness of the approach using chaotic dynamics for driving heuristic methods has been shown. The chaotic method is also evaluated in the case of a combinatorial optimization problem in the real world, which can be solved by the same heuristic operation as that for the ATSP. We apply the chaotic method to the DNA fragment assembly problem, which involves building a DNA sequence from several hundred fragments obtained by the genome sequencer. Our simulation results show that the proposed algorithm using chaotic dynamics in a block shift operation exhibits the best performance for the DNA fragment assembly problem.

• The Institute of Electronics, Information and Communication Engineersの論文

著者

• Hasegawa Mikio

  Dept. of Electrical Engineering, Tokyo University of Science

• Kato Tomohiro

  Dept. of Electrical Engineering, Tokyo University of Science

関連論文

• A hybrid approach using chaotic dynamics and global search algorithms for combinatorial optimization problems
• Performance of heuristic methods driven by chaotic dynamics for ATSP and applications to DNA fragment assembly

スポンサーリンク