シミュレーテッドアニーリングにおける 重要温度領域に関する考察

Presentation on theme: "シミュレーテッドアニーリングにおける 重要温度領域に関する考察"— Presentation transcript:

1 シミュレーテッドアニーリングにおける 重要温度領域に関する考察
同志社大学工学部　三木光範 同志社大学工学部　廣安知之 ○同志社大学大学院　米澤　基

2 最適化とは 最適化： ある制約条件のもとで，目的となる関数の 最小値(最大値)を求めること 最適化問題 連続最適化問題
タンパク質の立体構造予測 エネルギーが最も安定する状態 タンパク質の構造予測 組合せ最適化問題 LSI配置問題 巡回セールスマン問題 最短の経路 低コスト，高性能化 LSI配置問題 近年，最適化問題はさまざまな場面で注目されています．最適化とはある条件の下で与えられた問題を最適なものを求めることをいいます．その最適化問題には大きく分けて2つの種類があります．ひとつは扱う変数が離散値である組合せ最適化問題，もうひとつは連続値である連続最適化問題です．今回は組合せ最適化問題を対象とします． 一般に最適化問題を特には厳密解法とヒューリスティック探索法があります．厳密解法は最適解を求めるための方法ですが領域をくまなく探索するため計算コストが膨大となり，実際には不可能です．ヒューリスティック探索とは最適解に近い解を実用的な計算コストで求める方法です．これにはSA,GA,NNなどがあり多くの研究がされています．今回はSAについて発表します． 点在する都市を巡回するうえで最短な経路を求める巡回セールスマン問題 巡回セールスマン問題

3 研究背景 組合せ最適化問題とは ヒューリスティック探索 50都市があれば‥ 62 (50-1)!/2 = 3×10 移動距離 の巡回路
旅行代金 (50-1)!/2 = 3×10 　　　 　の巡回路 50都市があれば‥ 62 現実的に不可能 ヒューリスティック探索 例えば，世界を巡る旅行を考えたときにこのようにランダムなルートを選択しますと，移動距離や，旅行代金がおおくなります．そこでこのようなルートを選択することが望まれます．しかしながら，わずか50都市あっただけで，49の階乗割る2の巡回路があり，これらをくまなく探索して最適解を得るのは計算コストがかかりすぎ不可能です． 最適解に近い解を実用的な計算コストで探索する技法 シミュレーテッドアニーリング：金属の物理現象を模倣 遺伝的アルゴリズム：生物の進化を模倣 ニューラルネット：脳の計算機能を模倣

4 Simulated Annealing (SA)
組合せ最適化問題に有効な近似解法 金属を溶融状態から緩慢に冷却する「焼き鈍し」を模倣 改悪方向への推移を確率的に認めるため局所解に陥りにくい 低温の場合 高温の場合 次の解 温度スケジュール： 　SA試行中の温度Tの推移 現在の解 金属を溶融状態からゆっくり冷却するとよい結晶が得られるという焼きなましをシミュレートする手法です． アルゴリズムですがまず生成という操作を行います．生成とはこのように現在の解から次の解を生成することをいいます．次に受理判定を行います．このようにエネルギーが減少する方向つまり改良方向に解を生成した場合にはかならず受理します．そして受理されると推移という操作を行い現在の解から次の解へと移ります．一方このように改悪方向に次の解が生成された場合にはこちらに示したメトロポリス基準によって受理するか否かを決定します．もし受理されなかった場合には推移は行いません．これらの3つのステップを十分な回数繰り返した後，クーリングという操作で温度というパラメータを下げてやります．SAではこの4つの操作を終了条件をみたすまで繰り返します．SAでは受理判定にMetropolis基準を用いているため，高温では多くの改悪を受理します．したがってこのように解は大きくうごきまわることになります．逆に低温ではほとんどの改悪を認めないため，山登り法と同等の探索を行うことになります．したがって，SAにおいては温度の推移，一般に温度スケジュールと呼ばれますが，温度スケジュールが解探索能力に密接に関係することになります． 受理判定 推移 温度スケジュールとSAの解探索能力が密接に関係

5 温度スケジュール 高い温度から緩慢に冷却する方法が一般的 特定の温度のみ探索するSA 良好な解が得られる
一般的な 温度スケジュール 特定の温度のみ 探索を行うSA 高い温度から緩慢に冷却する方法が一般的 特定の温度のみ探索するSA SAにおける温度スケジュールについて説明します．こちらの図はSAを行う時の温度の移り変わりを示しています．横軸に解探索ステップ縦軸に温度を示しており，この図からわかるようにSAでは解探索初期から温度が徐々に下がっていきます．この温度スケジュールに関して多くの研究が行われていますが，高い温度から緩慢に冷却するの方法が一般的です．しかし，探索初期の高温では大きな改悪も受理するため解が収束せず，生成した解が初期解と同等となり，また温度が低すぎるとほとんど改悪を受理しないため山登り法と同等になります．つまり良好な解探索は温度スケジュールの途中で行われると報告されています． そして近年，特定の一定温度のみの探索で良好な解が得られることが報告されています．SAの解探索においてこのような温度領域について考察することは非常に重要だと考えられます．そこでこのような温度領域が存在するのか確かめるため温度パラメータに関する検証を行いました． [Connolly 1990, Mark 2000] 良好な解が得られる この温度領域はSAの解探索おいて非常に重要

6 重要な温度領域の検証 一定温度の解探索で良好な解を得ることができる 高温から低温まで等比的に分割 各温度で一定温度の探索
[Connolly 1990, Mark 2000] 高温から低温まで等比的に分割 各温度で一定温度の探索 得られた解と各温度の関係 対象問題：巡回セールスマン問題(TSP) そこで本研究では，こちらの図のように高温から低温まで各温度で一定温度でSAを行ない，それぞれの温度で得られる解の精度から，温度パラメータとその温度が解に与える影響を検証したいと思います．対象問題としてはこちらの巡回セールス問題を用います．この問題は代表的な組合わせ最適化問題であり，点在するいくつかの都市を一巡する最短の経路長を発見するという問題です．例えば50都市のTSPなら，組合わせとしては49の階乗となり，そこから最も最短な経路長をみつけるのは非常に難しい問題です．対象問題としてはTSPLIBというベンチマーク集から5つを選びました． 全ての都市を巡回する最短の経路長を探索 代表的な組合せ最適化問題 対象TSP：TSPLIBより [eil51, eil76, pr144, berlin52, st70]

7 重要温度領域の確認 (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 pr144 144 15.6 ～ 92.8 誤差1% 重要温度領域 誤差1% それでは実験結果です．これはeil51のものです．横軸に温度，縦軸に経路長を示します．TSPは短い経路長ほどいい結果ですので下に行くほど良いことになります．この結果を見てわかりますように，各温度によって解がことなっているのがわかります．また，この部分を拡大するとこちらになるのですが，特定の温度で良好な解を得ることができています．本研究は一定温度のSAで得られた最も良好な解から誤差1%の解が得られた温度の範囲を重要温度領域と定義します．こちらにその他の問題の重要温度領域を示します．これから，問題によって重要温度領域の値，範囲が問題によって異なることがわかります．次にこの重要温度領域を用いた実験を行いました． 問題によって重要温度領域の値， 範囲が異なる

8 重要温度のみの探索を行うSAと逐次SA 重要温度のみの探索を行う単一温度SA 高温から低温まで探索を行う逐次SA 解の精度の比較 パラメータ
最高温度 最大の改悪となる推移を50%の確率で受理される温度 重要温度 最低温度 最小の改悪となる推移がクーリング周期内の解探索で最低1回は受理される温度 クーリング周期 都市数×20 アニーリングステップ 都市数×3200 試行回数 30 対象問題 [eil51], [eil76], [berlin52], [st70], [pr144] つぎに重要温度のみの探索を行うSA，このことを単一温度SAと呼びます．これと一般的な高温から低温まで探索するSA，これを逐次SAとします．この2つをTSPに適用し，解の精度の比較を行いました．これがその結果です．横軸に問題，縦軸に最適解との誤差をしめします．下に行くほど良好な解が得られていることになります．この図を見てわかりますようにpr144のみが逐次SAのほうが良好な解がえられました． そこで重要温度領域に関して詳細な検証を行い，このような問題にも適切な温度スケジュールを考察することが私の研究目的です．

9 研究目的 研究目的 : 重要温度領域に関して詳細な検証を行い， なぜこのような結果が得られたか考察する pr144のみ重要温度で
最適解との誤差 pr144のみ重要温度で 良好な解が得られない 問題名 研究目的 : 重要温度領域に関して詳細な検証を行い， なぜこのような結果が得られたか考察する

10 pr144の都市配置 pr144の都市配置 eil51の都市配置 均一な構成 疎密な構成 疎密な構成では重要な温度が複数ある
単一温度SAで良好な解が得られなかった 単一温度SAで良好な解が得られた pr144の都市配置 eil51の都市配置 均一な構成 疎密な構成 そこでpr144の都市配置をみてみたところ，単一温度SAで良好な解がえられたeil51と比較してあきらかに疎密な構成であることがわかりました．ここでこのような疎密な構成の問題では重要温度のみでは良好な解が得られないと考えました．そこで，重要温度についてより詳細な検証を行いました． 疎密な構成では重要な温度が複数ある 単一温度のみの探索で良好な解が得られない 重要温度領域が複数存在する問題の作成

11 重要温度領域と平均都市間距離 ∝ 問題の平均都市間距離(最適解／都市数) TSPにおける重要温度領域 83.5 平均都市間距離：8.4
　∝　問題の平均都市間距離(最適解／都市数) [三木ら 2001] 10倍に拡大 平均都市間距離：8.4 83.5 8.2 [eil51-10] [eil51] 格子型に隣接 TSPにおける重要温度領域はその問題の平均経路長に比例することが報告されています．このことを検証するために次の実験を行いました．eil51を10倍に拡大した問題と，eil51をこのように格子型に4個隣接させた問題を作成し，重要温度領域がどのような値になるか実験を行いました．これらの問題の名前はそれぞれ，eil51-10，eil51*4とさせていただきます．こちらは模式的にあらわしていますが，実際にはこのような経路をとることになります．これらの問題の平均経路長はそれぞれ，～のようになります．Eil51の重要温度領域は温度1.5付近に存在するので，平均経路長が約10倍になっているeil51-10では重要温度領域も10倍になり，温度15付近に，また，eil51*4では，平均経路長がほぼ変わらないので重要温度も変化せず温度1.5付近に存在することが期待されます．これらの問題に先ほどと同様の一定温度SAを適用し，重要温度領域に関して検証を行いました． 温度1.5付近 [eil51*4]

12 重要温度領域と平均都市間距離 [eil51*4]の重要温度領域 [eil51-10]の重要温度領域
温度1.5付近 温度15付近 それでは実験結果です．横軸が温度，縦軸がそれぞれ，eil51-10の経路長，eil51*4の経路長を示します．赤がeil51*4の，黒がeil51-10の結果です．これをみてわかりますように，eil51*4では温度1.5付近に，eil51-10では温度15付近に重要温度領域が存在します． これらの結果より，重要温度領域が平均経路長に比例することが確かめられました．このことより，平均経路長が異なる問題を組合せることで，各平均経路長に比例した位置に重要温度領域が存在する問題を作成できると考えました． 重要温度領域が平均都市間距離に比例することが確かめられた

13 重要温度領域が複数存在する問題の作成 eil51を対象としてスケールを拡大して組合せる 作成した問題 eil51を4つ隣接
そこで，eil51を対象としてスケールを拡大し，平均都市間距離が異なる問題が組合さって構成されるTSPを作成しました．ここに示したものはスケールを1000倍に拡大したeil51の，この都市のみがこのようなeil51を4つ隣接させた問題で構成される問題で，254都市問題となります．先ほどと同じく，これも実際にはこのような経路をとることになります．この問題の名前を～とさせていただきます．そのほかにもスケールや，隣接するeil51の数を変えて組合せ，これら8個の問題を作成いたしました． eil51を4つ隣接 eil51を1000倍に拡大 254都市問題 問題名：eil51*4-1000

14 複数の重要温度領域を確認 [eil51*4-100] [eil51*9-1000] [eil51*4-1000] [eil51*4-800]
(×104) (×105) 重要温度領域が1つ存在する それぞれの影響は見られるが重要温度 領域はスケールの小さい問題のもの [eil51*1-1000] [eil51*4-10] [eil51* ] [eil51* ] Distance Distance Temperature Temperature [eil51*4-100] [eil51*9-1000] (×105) (×105) それぞれの影響は見られるが重要温度 領域はスケールの大きい問題のもの 重要温度領域が2つ存在する Distance Distance そしてこれらの問題に対し先ほどと同様の一定温度のSAを適用し，重要温度領域に関して検証を行いました．その結果，重要温度領域に4つのパターンが存在することがわかりました．これを問題をあげて1つずつ説明します．まずeil51*4-100ですが，・・・・ そしてeil51*4-800では重要温度領域を複数確認できます．ここに挙げたこれらの問題以外の問題もこの4つのパターンに当てはまり，このように分類できます． -----卒論------ そして先ほどと同様の一定温度SAを適用しました．結果を示します．このブルーのラインは最も良好な解から誤差1%以内の範囲を示したものです．これらをみてわかりますように，これら3つでは重要温度領域をひとつしか確認できませんが，このeil51*4-800では重要温度領域を2つ確認できます．これらの結果に関して説明します．まずこれは重要温度領域を1つのみ確認できる問題です．これはこのあたりにスケールの大きい問題の重要温度領域の影響が見受けられますが重要温度領域としては小さい問題のものとっています．逆にこれは大きい問題のものとなっています．そしてeil51*4-800では小さい問題と大きい問題のスケールが等しく重要温度領域を2つ確認できました．実際にはこれらの問題のほかにもさまざまなスケールを組合せて実験したのですが，結果はこの4つのどれかに分類できることがわかりました． Temperature Temperature [eil51*4-1000] [eil51*4-800]

15 逐次SAと単一温度SAの比較 pr144と同様に単一温度SAで良好な解が得られない スケールが異なる問題が組合さって構成される問題は
温度1.5 eil51*4-800は 重要温度領域が 2つあるため両方 の重要温度 温度1.5 温度1200 温度1500 近似解との誤差 eil51*4-100 eil51*4-1000 eil51*4-800 先ほど逐次SAと単一温度SAの実験行い，スケールの異なる問題から構成されるpr144では逐次SAのほうが良好な解が得られた．この実験を先ほど作成した問題に対しても行いました．結果がこの図です．Eil51*4-800は重要温度領域が2つあるため両方の温度で探索を行いました．この図をみてわかるように，逐次SAで良好な解が得られておりpr144と同様の結果となっています．このことより，スケールの異なる問題で構成される問題は単一温度で良好な解が得られないことがわかりました．次にこの逐次SAにおける最高温度に関する実験を行いました． 問題名 pr144と同様に単一温度SAで良好な解が得られない スケールが異なる問題が組合さって構成される問題は 単一温度で良好な解が得られない

16 逐次SAにおける最高温度と解精度の関係 逐次SAの最高温度を様々な値に設定し，アニーリングを 行い得られる解が劣化する最高温度について検証
パラメータ 最高温度 100000～0.1まで等比的に32分割 最低温度 0.01 アニーリングステップ 都市数×3200 クーリング周期 都市数×20 試行回数 300 対象問題 [eil51], [eil51*4-800], [eil51*4-100], [eil51*4-1000] 良好な解を得るために 必要不可欠な温度領域 こちらに，その実験の温度スケジュールを示しています．最低温度を固定し，最高温度をこのように様々な値に設定し逐次SAを行い解の劣化する最高温度を検証しました．最低温度は固定です．対象問題はeil51，．．です．

17 実験結果 [eil51] [eil51*4-800] [eil51*4-100] [eil51*4-1000] [eil51*4]
に拡大した問題 の重要温度領域 [eil51] [eil51*4-800] [eil51*4] [eil51*4] [eil51]を 1000倍に 拡大した問題 [eil51]を100倍に 拡大した問題 ピンクの領域は先ほどと同じようにこの問題，つまりeil51*4-800の重要温度領域を示しています．また，このオレンジの領域はそれぞれ，スケールの小さい問題，大きい問題を個別に見た場合に重要温度領域をしめしています．つまり，この問題ですと，eil51と800倍のeil51を組合せた問題ですので，それぞれ，eil51の重要温度領域，eil51を800倍に拡大した問題の重要温度領域を示してます． [eil51*4-100] [eil51*4-1000]

18 最高温度と解の精度に関するまとめ 重要温度領域が1つしか存在しない問題 重要温度領域が複数存在する問題
重要温度領域を探索する温度スケジュールを適用することで良好な解が得られる． eil51*4-100のようにスケールの異なる問題が組合わさって構成される問題 大きい問題の重要温度領域も探索する必要 重要温度領域が複数存在する問題 ここで，先ほどの実験結果からわかることをまとめさせていただきます． 全ての重要温度領域を探索する温度スケジュールを適用することで良好な解が得られる．

19 両方の重要温度領域を探索するSA eil51*4-800には重要温度領域が2つ存在する 両方の重要温度領域を探索するSAを適用
両方の重要温度領域を探索する温度スケジュール スケールの大きい問題の 重要温度領域 次に，これら明らかになった知見を元に，重要温度領域を複数持つ問題に適切な温度スケジュールの考察を行いました．両方の重要温度領域を探索SAを適用し、逐次SAとの比較実験を行いました。こちらにその温度スケジュールを示します。横軸に時間、縦軸に温度を示します｡ピンクの領域は上から、スケールの大きい問題の重要温度領域、小さい問題の重要温度領域を示します。この青のラインが逐次SAの温度スケジュールです。赤のラインが本実験で用いる両方の重要温度領域を探索する温度スケジュールです。 スケールの小さい問題の 重要温度領域

20 逐次SAとの比較結果 両方の重要温度領域を探索する ことで良好な解が得られている 重要温度領域が2つ存在する問題で良好な解を得るためには
近似解との誤差 両方の重要温度領域を探索する ことで良好な解が得られている 問題名 重要温度領域が2つ存在する問題で良好な解を得るためには 　　　　2つの重要温度領域を重点的に探索する

21 まとめ TSPには重要温度領域が存在する． 重要温度領域での探索で良好な解が得られるとされている が，そうでない問題も存在する．
重要温度領域が2つ存在する場合がある．そのため，単一 温度SAで良好な解が得られない． 重要温度領域が2つ存在する問題で良好な解を得るために は両方の重要温度領域を重点的に探索する必要がある． それでは本研究のまとめさせていただきます． 問題の構造がわからないものは逐次SAを適用するしかないのですが，問題の構造が明確なものは，適切な温度スケジュールを決定することができます． 問題の構造によって適切な温度スケジュールが異なる 問題の構造が明確なものは，適切な温度スケジュールを決定することができる．

22 Thank you for your kind attention.

23 質疑応答

24 単一温度SAで得られる解 [eil51*4-1000] 温度1.5で探索 経路長：464000 温度1500で探索 経路長：446000
良い形 良くない形 温度1.5で探索 経路長：464000 収束していない 良い形 温度1500で探索 経路長：446000

25 2つの重要温度領域を探索するSA 近似解(最適解)との誤差 問題名 重要温度を両方探索することで良好な解が得られている

26 重要温度での解探索の振舞い 目的関数値 アニーリングステップ 重要温度での解探索の振舞い： 局所解から脱出するが，最適解からも脱出する

27 スケールの異なる問題が組合さって構成される場合
重要温度領域に関する結論 スケールの異なる問題が組合さって構成される場合 スケールの拡大率が小さい スケールの拡大率が大きい バランスよく組合さっている スケールの小さい問題の重要温度領域が 強く現れる スケールの大きい問題の重要温度領域が強く現れる これらの結果よりスケールのことなる問題が組み合わさっている問題の重要温度領域に関する結論です． スケールの大きい問題および小さい問題の 重要温度領域がそれぞれ現れる

28 最高温度と解の精度の関係(結果2) 良好な解を得るためには2つの重要温度領域を 両方とも探索する必要がある スケールの小さい問題の
スケールの大きい問題の 重要温度領域 Distance Maximum temperature 良好な解を得るためには2つの重要温度領域を 両方とも探索する必要がある

29 円型の都市配置の問題 円型の都市配置 改悪を受理しない探索でも最適解が得られる

30 格子型の都市配置の問題 格子型の都市配置 改悪を受理しない探索でもほぼ最適解が得られる

31 都市間距離 [ei51] [eil76] [eil51*4-100] [pr144]