MPIを用いた並列処理～GAによるTSPの解法～

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

Download Report