This paper proposes a method to improve accuracy of Traveling Salesman Problem (TSP). The proposed method combines perturbation method and parallel Hybrid Genetic Algorithm (HGA) with the island model. Our method changes perturbation level among islands. Perturbation method is a method of shifting the position of the city when we improve the solution using heuristic. Island model are based on independent GAs which evolved separately, and immigration process to intermittently exchange genetic material. Multi-level perturbation and migration process in island model increase diversity among tours described as individuals. Large diversity gives as expanding search space, it helps to find better solution. We evaluate our method comparing with parallel island model HGA without perturbation. Our method found a better solution than parallel island model HGA without perturbation in all of the three benchmarks.
雑誌名
宮崎大學工學部紀要
巻
43
ページ
201 - 205
発行年
2014-07-31
出版者
宮崎大学工学部
Miyazaki University
Faculty of Engineering, University of Miyazaki
リポジトリのご案内
マルチレベル摂動型島モデルを用いた並列HGAによるTSPの解精度向上
engineering43_201-205.pdf
(719.65KB)
