MPIを用いた並列処理 ～GAによるTSPの解法～ 平成18年6月22日（木） B5 小池和洋
巡回セールスマン問題(TSP)とは Traveling Salesman Problem 多くの都市と各都市間の移動コストが与えられたとき、全ての都市を一度だけ回って戻ってくるルートのうち、コスト最小のものを求める問題。 都市が増えるほど、コスト最小のものを求めるのが困難になる。
遺伝的アルゴリズム(GA)とは Genetic Algorithm 近似解を探索するアルゴリズムの一つ。 データ（解の候補）を遺伝子で表現し、 選択（淘汰）・交叉・突然変異などの操作を繰り返しながら解を探索する。
GAによるTSPの解法 大まかな流れ マップの読み込み 初期集団の生成 交叉 （突然変異） 選択（淘汰）
選択（淘汰） 選択の方法 ルーレット選択 ランキング選択 トーナメント選択 etc. 今回はトーナメント選択を使用
トーナメント選択 結果のいい遺伝子を残す
交叉 交叉の方法 循環交叉 部分的交叉 順序交叉 etc. 今回は部分的交叉を使用
部分的交叉 2 3 4 1 4 3 6 5 4 3 2 5 3 4 1 6 切れ目を右に１つずらし、同様の作業を行う 親1 4 3 2 5 3 4 1 6 親2 切れ目を右に１つずらし、同様の作業を行う 交叉するペアをランダムに選び出す 切れ目の右側の数字を確認 ランダムに切れ目を選択 対応する数字を入れ換える （一度入れ換えた数字にはフラグを立て、それ以降動かないようにする）
突然変異 突然変異の種類 逆位 スクランブル 位置移動 etc. 今回は位置移動を使用
位置移動 2 4 13 6 5 二番目の値を一番目の値の前に移動 二つの値をランダムに選択
MPIへの実装 大まかな流れ （移住） rank=0 マップの読み込み マップの読み込み rank!=0 初期集団の生成 ・配布 MPI_Send() 初期集団の生成 ・配布 初期集団の受け取り MPI_Recv() 交叉 交叉 （移住） （突然変異） （移住） （突然変異） MPI_Send() MPI_Recv() 選択（淘汰） 選択（淘汰）
移住 ランダムに選んだ遺伝子を他の端末へ送信する。 bi-Directional Ring
計算に用いたパラメータ マップ ：30x30 都市数 ：50都市 遺伝子数：200 世代数 ：100,000世代 都市数 ：50都市 遺伝子数：200 世代数 ：100,000世代 移住間隔：1,000世代ごと 移住数 ：10遺伝子（5%） 端末数 ：1台、2台、4台、8台、16台
マップ コスト１
台数効果の検証方法 より最適解に近い経路を見つけ出すことができるか 収束の早さ プログラムの実行時間はどれぐらい長くなるのか
より最適に近い経路を探せたか 各並列数で20回ずつ実行させ、最も良かった結果をグラフで比較 並列台数が多いほど 良い結果を得られた！
経路 1台(236) 2台(227) クロスしている箇所が少ないほど 最適解に近づいている 4台(219) 8台(206)
台数効果の検証方法 より最適解に近い経路を見つけ出すことができるか 収束の早さ プログラムの実行時間はどれぐらい長くなるのか
収束の早さ 収束する位置を見極めるため、世代数を200,000にして実行 並列台数が多いほど 収束が早まる！
台数効果の検証方法 より最適解に近い経路を見つけ出すことができるか 収束の早さ プログラムの実行時間はどれぐらい長くなるのか
プログラムの実行時間 並列する台数とプログラム実行時間の間には 依存関係がないように見える 台数 timeコマンドにより計測した時間 1 00:53.0 00:55.4 00:55.0 00:50.7 2 00:42.1 00:41.1 00:41.7 00:42.2 4 00:40.6 00:42.9 00:39.8 00:43.1 8 00:58.4 00:43.4 00:40.8 16 00:46.7 00:39.9 00:39.7 00:45.0 並列する台数とプログラム実行時間の間には 依存関係がないように見える なぜか1台の時が最も時間がかかった
おまけ 世代ごとの平均をとったグラフ
まとめ 並列計算をする端末数を増やすと、より最適解に近い経路を出す可能性が高まる 経路のクロスが少ないほうが最適解に近づく 増やせば確実にいい経路が出るとは限らない 少ない端末数でいい経路が出ることもある 経路のクロスが少ないほうが最適解に近づく 今回はクロスがない経路を求めることができなかった 経路がクロスしているかどうかは、プログラムのほうで判断できない