解探索空間構成法を用いた二次割当問題のための多出発シミュレーテッドアニーリング

カテゴリ: 部門大会

論文No: PS3-11

グループ名: 【C】平成30年電気学会電子・情報・システム部門大会プログラム

発行日: 2018/09/05

タイトル(英語): Modified Search Space of Quadratic Assignment Problem for Multi-start Simulated Annealing

著者名: 田島 良記(千葉大学),小圷 成一(千葉大学),岡本 卓(SENSY),下馬場 朋禄(千葉大学),伊藤 智義(千葉大学)

著者名(英語): Yoshiki Tajima|Seiichi Koakutsu|Takashi Okamoto|Tomoyoshi Shimobaba|Tomoyoshi Ito

キーワード: シミュレーテッドアニーリング|二次割当問題|多出発シミュレーテッドアニーリング|相関係数|Simulted Annealing|Quadratic Assignment Problem|Multi-start Simulated Annealing|Correlation coefficient

要約(日本語): Simultaed Annealing(SA) は，冷却スケジュールに従って温度を降下させ,探索点の更新を繰り返すことで探索空間の中で良い解を確率的に探索する手法である。SA はある過程の下，十分に時間をかけて探索を行えば大域的最適解が得られることが証明されている。現実的にはそのような探索を行うことは難しく，近年SA における解の探索空間に関する議論が報告されている。また，SA は最終的に到達する状態が初期状態に依存しやすいことが指摘されている。これに対し，複数の状態系列を並列化させて探索を行うMulti-start SA (MSA) が存在する。本研究では，二次割当問題(Quadratic Assignment Problem: QAP) における解探索空間調整法と相関係数を用いたSAに対し，MSA を適用し，解探索性能の向上を検討する。計算機実験の結果，相関係数を最大にし，直径を適切な値にすることにより ランダムな初期状態を生成した場合のMSA に対し最適解到達率の改善が確認された。

PDFファイルサイズ: 187 Kバイト