3M-7
Javaマルチスレッドによる枝組立交叉（EAX）の並列処理実現方式の検討～巡回セールスマン問題（TSP）を解くGAの並列処理～
○元田 剛，髙橋良英（八戸工大）
TSPとは、セールスマンがn箇所の都市を全て訪問し出発都市に
戻る時、短くなる経路を求める組合せ最適化問題である。TSPの最
適解の近似を得る手法としてGAが有効であるとされる。GAの探索
性能は、交叉機能に依存するため、交叉が提案されている。その中
でもEAXは、探索率、探索時間の両面において優秀である。我々の
実験では、集団サイズを大きくすれば、最適解を100％探索できる
が、計算量も増加してしまう。このため、集団を複数のスレッドに
分割し、並列処理する手法が探索時間短縮を図るために必要と考え
る。
Javaマルチスレッドによる、EAXを並列化させる方法を検討する。
TSPLIBを用いた性能評価、性能改善結果を報告する。