シミュレーテッドアニーリングにおける 重要温度領域に関する考察 同志社大学工学部 三木光範 同志社大学工学部 廣安知之 ○同志社大学大学院 米澤 基 最適化とは 最適化： ある制約条件のもとで，目的となる関数の 最小値(最大値)を求めること 最適化問題 連続最適化問題 タンパク質の立体構造予測 タンパク質の構造予測 エネルギーが最も安定する状態 組合せ最適化問題 LSI配置問題 LSI配置問題 低コスト，高性能化 巡回セールスマン問題 最短の経路 巡回セールスマン問題 研究背景 組合せ最適化問題とは 50都市があれば‥ 62 (50-1)!/2 =移動距離 3×10 の巡回路 旅行代金 現実的に不可能 ヒューリスティック探索 最適解に近い解を実用的な計算コストで探索する技法 シミュレーテッドアニーリング：金属の物理現象を模倣 遺伝的アルゴリズム：生物の進化を模倣 ニューラルネット：脳の計算機能を模倣 Simulated Annealing (SA) 組合せ最適化問題に有効な近似解法 金属を溶融状態から緩慢に冷却する「焼き鈍し」を模倣 改悪方向への推移を確率的に認めるため局所解に陥りにくい 低温の場合 高温の場合 次の解 温度スケジュール： SA試行中の温度Tの推移 温度スケジュールとSAの 解探索能力が密接に関係 現在の解 受理判定 次の解 推移 温度スケジュール 一般的な 温度スケジュール 特定の温度のみ 探索を行うSA 高い温度から緩慢に冷却する方法が一般的 特定の温度のみ探索するSA [Connolly 1990, Mark 2000] 良好な解が得られる この温度領域はSAの解探索おいて非常に重要 重要な温度領域の検証 一定温度の解探索で良好な解を得ることができる [Connolly 1990, Mark 2000] 高温から低温まで等比的に分割 各温度で一定温度の探索 得られた解と各温度の関係 対象問題：巡回セールスマン問題(TSP) 全ての都市を巡回する最短の経路長を探索 代表的な組合せ最適化問題 対象TSP：TSPLIBより [eil51, eil76, pr144, berlin52, st70] 重要温度領域の確認 (eil51での実験結果) 各温度によって解が異なる 特定の温度領域で良好な解 重要温度領域 TSP 重要温度領域 都市数 重要温度領域 eil51 51 1.1 ～ 2.2 eil76 76 0.9 ～ 1.5 berlin52 52 18.0 ～ 38.0 st70 70 1.1 ～ 2.7 144 15.6 ～ 92.8 pr144 誤差1% 問題によって重要温度領域の値， 範囲が異なる 重要温度のみの探索を行うSAと逐次SA 重要温度のみの探索を行う単一温度SA 高温から低温まで探索を行う逐次SA 解の精度の比較 パラメータ 逐次SA 単一温度SA 最高温度 最大の改悪となる推移を50%の 確率で受理される温度 最低温度 最小の改悪となる推移がクーリ ング周期内の解探索で最低1回 は受理される温度 クーリング周期 アニーリングステップ 重要温度 都市数×20 都市数×3200 試行回数 対象問題 30 [eil51], [eil76], [berlin52], [st70], [pr144] 研究目的 5% 逐次SA 単一温度SA 最適解との誤差 4% 3% pr144のみ重要温度で 良好な解が得られない 2% 1% 0% eil51 eil76 berlin52 st70 pr144 問題名 研究目的 : 重要温度領域に関して詳細な検証を行い， なぜこのような結果が得られたか考察する pr144の都市配置 単一温度SAで良好な解が得られなかった 単一温度SAで良好な解が得られた pr144の都市配置 eil51の都市配置 疎密な構成 均一な構成 疎密な構成では重要な温度が複数ある 単一温度のみの探索で良好な解が得られない 重要温度領域が複数存在する問題の作成 重要温度領域と平均都市間距離 TSPにおける重要温度領域 ∝ 問題の平均都市間距離(最適解／都市数) [三木ら 2001] 10倍に拡大 83.5 平均都市間距離：8.4 [eil51] 温度1.5付近 [eil51-10] 格子型に隣接 8.2 [eil51*4] 重要温度領域と平均都市間距離 [eil51*4]の重要温度領域 [eil51-10]の重要温度領域 [eil51-10] [eil51*4] 温度1.5付近 温度15付近 重要温度領域が平均都市間距離に比例することが確かめられた 重要温度領域が複数存在する問題の作成 eil51を対象としてスケールを拡大して組合せる 作成した問題 eil51*1-1000 eil51*4-10 eil51*4-100 eil51*4-800 eil51*4-1000 eil51*4-10000 eil51*9-1000 eil51*16-1000 eil51を4つ隣接 254都市問題 eil51を1000倍に拡大 問題名：eil51*4-1000 複数の重要温度領域を確認 (×104) (×105) [eil51*1-1000] [eil51*4-10] [eil51*4-10000] それぞれの影響は見られるが重要温度 領域はスケールの小さい問題のもの Distance Distance 重要温度領域が1つ存在する Temperature Temperature [eil51*4-100] [eil51*9-1000] (×105) それぞれの影響は見られるが重要温度 領域はスケールの大きい問題のもの Temperature [eil51*4-1000] 重要温度領域が2つ存在する Distance Distance (×105) [eil51*16-1000] Temperature [eil51*4-800] 逐次SAと単一温度SAの比較 近似解との誤差 12% 逐次SA 単一温度SA 温度1.5 10% 温度1.5 8% 温度1500 温度1200 6% eil51*4-800は 重要温度領域が 2つあるため両方 の重要温度 4% 2% 0% eil51*4-100 eil51*4-100 eil51*4-1000 eil51*4-1000 eil51 eil51*4-800eil51 問題名 pr144と同様に単一温度SAで良好な解が得られない スケールが異なる問題が組合さって構成される問題は 単一温度で良好な解が得られない 逐次SAにおける最高温度と解精度の関係 逐次SAの最高温度を様々な値に設定し，アニーリングを 行い得られる解が劣化する最高温度について検証 良好な解を得るために 必要不可欠な温度領域 パラメータ 最高温度 最低温度 アニーリングステップ クーリング周期 試行回数 対象問題 100000～0.1まで等比的 に32分割 0.01 都市数×3200 都市数×20 300 [eil51], [eil51*4-800], [eil51*4-100], [eil51*41000] 実験結果 [eil51]の重要温度領域 [eil51] [eil51*4] [eil51]を800倍 に拡大した問題 の重要温度領域 [eil51*4-800] [eil51*4] [eil51*4] [eil51]を100倍に 拡大した問題 [eil51*4-100] [eil51]を 1000倍に 拡大した問題 [eil51*4-1000] 最高温度と解の精度に関するまとめ 重要温度領域が1つしか存在しない問題 重要温度領域を探索する温度スケジュールを適用することで 良好な解が得られる． eil51*4-100のようにスケールの異なる問題が組合わさって構 成される問題 大きい問題の重要温度領域も探索する必要 重要温度領域が複数存在する問題 全ての重要温度領域を探索する温度スケジュールを適用す ることで良好な解が得られる． 両方の重要温度領域を探索するSA eil51*4-800には重要温度領域が2つ存在する 両方の重要温度領域を探索するSAを適用 逐次SAの温度スケジュール 両方の重要温度領域を探索する温度スケジュール スケールの大きい問題の 重要温度領域 スケールの小さい問題の 重要温度領域 逐次SAとの比較結果 近似解との誤差 8% 逐次SA 両方の重要温度領域を探索するSA 6% 4% 両方の重要温度領域を探索する ことで良好な解が得られている 2% 0% eil51*4-800 問題名 重要温度領域が2つ存在する問題で良好な解を得るためには 2つの重要温度領域を重点的に探索する まとめ TSPには重要温度領域が存在する． 重要温度領域での探索で良好な解が得られるとされている が，そうでない問題も存在する． スケールの異なる問題が組合わさって構成されるTSPでは， 重要温度領域が2つ存在する場合がある．そのため，単一 温度SAで良好な解が得られない． 重要温度領域が2つ存在する問題で良好な解を得るために は両方の重要温度領域を重点的に探索する必要がある． 問題の構造によって適切な温度スケジュールが異なる 問題の構造が明確なものは，適切な温度スケジュールを決 定することができる． Thank you for your kind attention. 質疑応答 単一温度SAで得られる解 [eil51*4-1000] 良い形 良くない形 収束していない 良い形 温度1.5で探索 経路長：464000 温度1500で探索 経路長：446000 近似解(最適解)との誤差 2つの重要温度領域を探索するSA 逐次SA 両方の重要温度を探索するSA 10% 8% 6% 4% 2% 0% eil51*4-100 eil51*4-1000 pr144 問題名 重要温度を両方探索することで良好な解が得られている 目的関数値 重要温度での解探索の振舞い アニーリングステップ 重要温度での解探索の振舞い： 局所解から脱出するが，最適解からも脱出する 重要温度領域に関する結論 スケールの異なる問題が組合さって構成される場合 スケールの拡大率が小さい スケールの小さい問題の重要温度領域が 強く現れる スケールの拡大率が大きい スケールの大きい問題の重要温度領域が 強く現れる バランスよく組合さっている スケールの大きい問題および小さい問題の 重要温度領域がそれぞれ現れる 最高温度と解の精度の関係(結果2) スケールの大きい問題の 重要温度領域 Distance スケールの小さい問題の 重要温度領域 Maximum temperature 良好な解を得るためには2つの重要温度領域を 両方とも探索する必要がある 円型の都市配置の問題 円型の都市配置 改悪を受理しない探索でも最適解が得られる 格子型の都市配置の問題 格子型の都市配置 改悪を受理しない探索でもほぼ最適解が得られる 都市間距離 [ei51] [eil51*4-100] [eil76] [pr144]
© Copyright 2024 ExpyDoc
