第51回 月例発表会（2002年7月） 知的システムデザイン研究室 格子型と円型のTSP 米澤 基
1 今月の課題
• 文献調査 • 並列プログラミングの基礎勉強 • 格子型と円型の TSP の温度とエネルギーの関係2 達成状況
2.1 文献調査の内容 さらなる計算スピード の向上を求め，アニーリングプ ロセスの並列化が 10 年ほど 前から研究されている．以 下に 2 つの並列化手法について説明する． 1. 同じ温度で各プロセッサが独立にアニーリングし， クーリング時に解を集め，最も良い解を選択して配 信する．各プロセッサは次の温度でこの共通の解か ら再びアニーリングを始める (Fig. 1 参照)． 2. あるプロセッサが採択すべき次の解を見つけると， その解を他のプロセッサに伝達し，各プロセッサは 受け取った解の近傍で探索を開始する (Fig. 2 参照)． annealingprocessor1 processor3 processor4
ࠢࡦࠣᤨ
processor2
processor2 processor3 processor4 processor1
⸃ ⸃ ⸃
processor1 processor2 processor3 processor4 ᦨ߽⦟⸃
annealing ⸃
Master Slave Slave Slave
Fig. 1 並列化手法 1 processor4 processor3 accept processor1 processor2 processor2 processor3 processor4 processor1 processor1 processor2 processor3 processor4 ⸃ accept ⸃ Fig. 2 並列化手法 2 2.2 並列プログラミングの基礎 Fig. 3 に示す並列 SA を MPI を用いて実装した． 2.3 格子型と円型の TSP 格子型と円型に都市が配置された問題1を作成した．温 度を 1.0e+5 度から 1.0e-3 度まで 32 温度に分割し ，そ 1最短経路長は100 である．都市数は 9，16，25，36，49，64，81， 100 のものを作成した． annealing process0 process n annealing ⚳ੌᤨ process1 process1 process n ⚻〝㐳n ⚻〝㐳 Master process0 file Display ⚻〝㐳 ᦨ⍴࡞࠻ࠍ ᳞ߚID Slave Slave ᦨ⍴⚻〝㐳 ᦨ⍴࡞࠻ Fig. 3 作成した並列 SA のモデル れぞれの温度でアニーリングを行い，温度とエネルギー の関係を調べた．格子型，円型それぞれ 5 回試行平均の 結果を Fig. 4，Fig. 5 に示す． 㪌㪇 㪈㪇㪇 㪈㪌㪇 㪉㪇㪇 㪉㪌㪇 㪈㪅㪜㪄㪇㪊 㪈㪅㪜㪄㪇㪈 㪈㪅㪜㪂㪇㪈 㪈㪅㪜㪂㪇㪊 㪈㪅㪜㪂㪇㪌 㪫㪼㫄㫇㪼㫉㪸㫋㫌㫉㪼 㪛 㫀㫊㫋 㪸㫅 㪺㪼 㪾㫉㫀㪻㪐 㪾㫉㫀㪻㪈㪍 㪾㫉㫀㪻㪉㪌 㪾㫉㫀㪻㪊㪍 㪾㫉㫀㪻㪋㪐 㪾㫉㫀㪻㪍㪋 㪾㫉㫀㪻㪏㪈 㪾㫉㫀㪻㪈㪇㪇 Fig. 4 格子型の TSP における温度とエネルギーの関係 㪌㪇 㪈㪌㪇 㪉㪌㪇 㪊㪌㪇 㪋㪌㪇 㪌㪌㪇 㪍㪌㪇 㪈㪅㪜㪄㪇㪊 㪈㪅㪜㪄㪇㪈 㪈㪅㪜㪂㪇㪈 㪈㪅㪜㪂㪇㪊 㪈㪅㪜㪂㪇㪌 㪫㪼㫄㫇㪼㫉㪸㫋㫌㫉㪼 㪛 㫀㫊㫋 㪸㫅 㪺㪼 㪺㫀㫉㪺㫃㪼㪐 㪺㫀㫉㪺㫃㪼㪈㪍 㪺㫀㫉㪺㫃㪼㪉㪌 㪺㫀㫉㪺㫃㪼㪊㪍 㪺㫀㫉㪺㫃㪼㪋㪐 㪺㫀㫉㪺㫃㪼㪍㪋 㪺㫀㫉㪺㫃㪼㪏㪈 㪺㫀㫉㪺㫃㪼㪈㪇㪇 Fig. 5 円型の TSP における温度とエネルギーの関係 Fig. 4，Fig. 5 より，円型では低温でも最適解に収束 するが，格子型ではエネルギー値がやや増えているのが わかる．そこで格子型の TSP を温度 0 度でアニーリン グしたところ局所解を発見した．Fig. 6 に示す． 㪇 㪌 㪈㪇 㪈㪌 㪉㪇 㪉㪌 㪇 㪌 㪈㪇 㪈㪌 㪉㪇 㪉㪌 㫏 㫐 㪇 㪌 㪈㪇 㪈㪌 㪉㪇 㪉㪌 㪇 㪌 㪈㪇 㪈㪌 㪉㪇 㪉㪌 㫏 㫐 Fig. 6 格子型の TSP に存在する局所解 (都市数 16)
