情報処理学会 第74回全国大会講演要旨

巡回セールスマン問題（TSP）とは，各都市を1度ずつ通る最短経路を求める問題である．
考えられる巡回路の数は都市数をNとすると(N-1)!/2通り存在する．
そのため厳密解を求めようとすると莫大な時間を必要とするため，一般的に近似解を用いて求める．
本研究では近似解を求める手法として遺伝的アルゴリズム（GA）の枝組み立て交叉（EAX）を用いる．
この手法は，10000都市を超える問題において良質な個体を生成することを可能としているが，多くの実行時間を必要としている．
そこで，並列処理を得意とするハードウェアであるGPU（Graphics Processing Unit）を用いてGAの高速化を図る．