適応的近傍を持つ シミュレーテッドアニーリングの性能 Performance of Simulated Annealing with Adaptive Neighborhood 同志社大学工学部知識工学科 知的システムデザイン研究室 三木　光範 廣安　知之 小野　景子

研究背景 ヒューリスティック探索法 シミュレーテッドアニーリング(SA) シミュレーテッドアニーリング(SA) 遺伝的アルゴリズム(GA) など ニューラルネットワーク(NN)

Simulated Annealing (SA)とは(1) 加熱 冷却 原子の様子 エネルギー小 エネルギー大 物理現象(金属の焼きなまし)にヒントを得る 最小エネルギーを得る この現象をコンピュータ上で模倣

Simulated Annealing (SA)とは(2) 高温時は悪い状態を受理しやすく，低温時は受理しにくい 大域的最適解を見つける事が出来る 山を登る

研究目的 Coranaの手法を検証 問題に依存しない近傍設計 組み合わせ最適化問題 SA 連続最適化問題 連続最適化問題 近傍が解の精度に大きく依存する TSP 近傍の設計法 固定近傍 可変近傍 適応的近傍･･･ Coranaの手法 連続関数 Coranaの手法を検証 問題に依存しない近傍設計

温度に対する近傍幅の調節 高温時 大域的探索 近傍幅が大きくならなくてはならない 低温時 局所的探索 近傍幅が小さくならなくてはならない 設計空間

近傍の選択 適応的近傍が有効 固定近傍 温度を考慮していない 最適な近傍幅を見つける事が大変 可変近傍 目的関数のランドスケープを考慮していない 適応的近傍が有効

Corana(受理率を0.5に保つ)の手法 1：1 次状態への推移割合 各温度での摂動の受理率と却下率を元に近傍幅を調節する 受理：却下 受理が多い 却下が多い 近傍幅を大きく 近傍幅を小さく 設計空間

Coranaの手法の定式化 m, m’: 近傍幅 g(p) : 近傍幅の拡大率 p : 摂動の受理率 p = n / N 受理率0.5に保つ近傍拡大率 otherwise p g c , 1 ) ( 6 . if 4 = > - + < ø ö ç è æ m, m’: 近傍幅 g(p) : 近傍幅の拡大率 p : 摂動の受理率 p = n / N n : 受理された摂動回数 N : 近傍幅の調節間隔 本研究では，経験的に c=2，N = 8.

受理率0.5とする適応近傍の結果 Rastrigin関数 近傍幅:1

Coranaの手法の問題点 近傍が小さくなりすぎる 局所解から脱出できない 近傍を大きくする必要がある 一定に保つ受理率を下げる 受理率0.5の近傍拡大率 一定に保つ受理率を下げる

Coranaの手法の改良 一定に保つ受理率を小さくする 近傍を拡大する確率を上げる 近傍幅を大きくすることで局所から脱出可能 近傍拡大率 一定に保つ受理率を小さくする Coranaの改良 近傍を拡大する確率を上げる Corana 近傍幅を大きくすることで局所から脱出可能

Coranaの手法の改良の結果 受理率0.27程度の受理率になる 近傍が大きくならない 近傍の拡大率を大きくする必要がある 受理率0.1

But 適応的近傍拡大率の必要性 Coranaの手法 Coranaの手法の改良 受理率を下げる 近傍拡大率を局所解から脱出可能程度大きくする必要がある But 拡大率は問題に依存する 問題に依存しない適応的拡大率をもつ 近傍設計が必要

提案手法の特徴 ＋ Coranaの手法 受理率による近傍幅調節 提案手法 受理率による近傍幅調節 受理率による近傍拡大率調節 問題に依存しない適応的拡大率 を持つ近傍設計

提案する適応的近傍設計アルゴリズム 受理率が高い 拡大率自体を上げる 受理率が低い 拡大率自体を下げる

提案する適応的近傍設計 Corana 拡大率固定 拡大率を適応変化 受理率0.5 受理率を下げる

提案する適応的近傍設計の定式化 m’=m×g(p) g(p)=H0(p’) g(p)=0.5 g(p)=1.0 H0=H0×H1 if p>p２ g(p)=0.5 if p>p１ g(p)=1.0 otherwise H0=H0×H1 H1=2.0 H1=0.5 H1=1.0 if p’>p’２ m, m’: 近傍幅 g(p) : 近傍幅の調節のため の係数 p ’: 摂動の受理率 p ’= n’ / N’ if p’>p’１ otherwise n ’: 受理された摂動回数 N’ : 近傍拡大率の調節間隔 H0:　近傍拡大率の係数

対象問題

パラメータ設定 Function Rastrigin Griewank 10 20 0.01 0.001 10000 30000 0.8 Max.(Initial) Temperature 10 20 Min.(Final) 0.01 0.001 Markov Length 10000 30000 Cooling rate 0.8 0.7 Neighborhood Adjustment interval 50 Neighborhood range’s Parameter adjustment interval 200

実験結果(受理率) 目的の低い受理率を保つ事が可能に

実験結果（エネルギー） 受理率0.1の時が最も効率よくアニーリングができる

考察（近傍幅）-Rastrigin関数- Corana 局所解からの脱出に必要な近傍幅を維持している

考察(近傍幅)　-Griwank関数-

結論 従来の受理率を0.5に保つ方法では，近傍幅が小さすぎるため局所解に陥る 一定に保つ受理率を下げる必要がある 近傍の拡大率は問題に依存する 近傍の拡大率自体を適応的に変化させる 低い受理率を実現することが可能に 局所解からの脱出に必要な近傍幅を保つことでき，局所から脱出可能に 従来の方法より，良質な解が得られた

固定近傍と適応的近傍(Rastrigin)

固定近傍と適応的近傍(Griewank)

3次元での結果 3次元でも，受理率0.1で良好な解を得た

アニーリングステップ数を増やした結果 Rastrigin(2次元)

アニーリングステップ数を増やした結果 Rastrigin(3次元)

適応的近傍の設計 m:近傍幅を決定するパラメータ x’I=xi+rm m’=m×g(p) g(p)=H0(p’) if p>p1 近傍拡大率 m’=m×g(p) g(p)=H0(p’) if p>p1 g(p)=0.5 if p<p2 g(p)=1.0 otherwise 拡大率自体の見直し H0=H0×H1 H1=2.0 if p’>p1 H1=0.5 if p’<p2 H1=1.0 otherwise xi:現在の設計変数 m:近傍幅を決定するパラメータ

拡大率1の範囲 p1 p2 受理率0.4 0.3 0.5 受理率0.3 0.2 0.4 受理率0.2 0.1 受理率0.1 0.05 0.15 受理率0.05 0.025 0.075 受理率0.01 0.005 0.015

適応的近傍のアルゴリズム

受理率を低くする理由 局所に陥る 受理率が高くなる 大域的探索 受理率が低くなる

Coranaの手法 受理率0.5に保つ近傍拡大率 エネルギー関数 拡大 縮小