焼きなまし法
焼きなまし法（やきなましほう、英: Simulated Annealing、SAと略記、疑似アニーリング法、擬似焼きなまし法、シミュレーティド・アニーリングともいう）は、大域的最適化問題への汎用の乱択アルゴリズムである。広大な探索空間内の与えられた関数の大域的最適解に対して、よい近似を与える。 S. Kirkpatrick、C. D. Gelatt、M. P. Vecchiらが1983年に考案し[1]、1985年に V. Cerny が再発見した[2]。
その名称は、金属工学における焼きなましから来ている。焼きなましは、金属材料を熱した後で徐々に冷やし、結晶を成長させてその欠陥を減らす作業である。熱によって原子は初期の位置（内部エネルギーがローカルな極小状態）から離され、よりエネルギーの高い状態をうろつく。ゆっくり冷却することで、原子は初期状態よりも内部エネルギーがさらに極小な状態を得る可能性が多くなる。
SAアルゴリズムは、解を繰り返し求め直すにあたって、現在の解のランダムな近傍の解を求めるのだが、その際に与えられた関数の値とグローバルなパラメータ T（温度を意味する）が影響する。そして、前述の物理過程との相似によって、T（温度）の値は徐々に小さくなっていく。このため、最初はTが大きいので、解は大胆に変化するが、Tがゼロに近づくにつれて収束していく。最初は簡単に勾配を上がっていけるので、山登り法で問題となるようなローカルな極小に陥ったときの対処を考える必要がない。
概要
[編集]焼きなまし法では、探索空間の各点「s」は物理システムの「状態」に対応し、最小化すべき関数 E(s) は物理状態の「内部エネルギー」に対応する。従って、目標はシステムを任意の「初期状態」からできる限りエネルギーが最小の状態にすることである。
基本的反復
[編集]各ステップでは、SAのヒューリスティックは、現在状態 s のいくつかの近傍 s' を検討し、現在状態 s のままがよいか、いずれかの近傍状態に遷移するのがよいかを確率的に決定する。その際、システムが最終的にエネルギーの低い状態へ向かうよう考慮する。このステップは、十分よい結果が得られるまで、あるいは予定された計算時間が尽きるまで繰り返される。
状態近傍
[編集]各状態の近傍は、アプリケーション固有の方法で、通常ユーザーによって指定される。たとえば、巡回セールスマン問題において、個々の状態は、一般に「ツアー」（訪問する都市の順列）と呼ばれる。その場合、近傍とは、都市の順列の中で一箇所だけ都市の順番を入れ替えた順列と考えることができる。
遷移確率
[編集]現在状態 s から新たな状態候補 s' への遷移確率は、二つの状態のエネルギー e = E(s) と e' = E(s' ) の関数 P(e, e' , T) で与えられる。ここで T は「温度」に相当し、時間と共に変化するグローバルなパラメータである。
遷移確率 P の基本的な必須条件として、e' > e のときにゼロでない値を返さなければならないという点があげられる。これは、ときには「悪い」と思われる状態（エネルギーの高い状態）へもシステムが遷移可能であることを意味する。これは「ローカルな極小状態」に張り付いてしまうのを防ぐ機能である。「ローカルな極小状態」とは、そのエネルギーが真の極小には程遠いが、近傍とだけ比べれば極小であるような状態を意味する。
一方で、Tが 0に近くなるにつれて、e' > e であれば P(e, e' , T) の値をゼロに近づけ、e' < e であればその値を大きくする。これにより、Tが十分に小さくなれば、システムは極小に向かい、逆の動きは封じられる。特に T が 0 になると、山登り法を使うことで近傍の極小に確実に向かわせることもできる。
関数 P は e' −e の値が増大する際には確率を減らす値を返すように設定される。つまり、ちょっとしたエネルギー上昇の向こうに極小がある可能性の方が、どんどん上昇している場合よりも高いという考え方である。しかし、この条件は必ずしも必須ではなく、上記の必須条件が満たされていればよい。
これらの特性により、状態 s の変化は温度 T に大きく依存する。大まかに言えば、sの変化は T が大きいときには劇的に変化し、T が小さくなるとゆるやかに変化する。
焼きなましスケジュール
[編集]焼きなまし法のもうひとつの本質的な機能は、シミュレーションが進むにつれて、温度が徐々に下がっていく点である。最初Tは高い（あるいは無限大の）値に設定され、何らかの「焼きなましスケジュール」に従って、ステップを経るにつれて減少していく。そのスケジュールは、ユーザーが指定する場合もあるが、予定された時間には T =0 になって終わらなければならない。このようにすると、システムは最初のうちはエネルギー関数の小さな変化を無視して最適解を求めて探索空間の広い領域をさまよい、徐々にエネルギーの低い領域に向かって探索範囲を狭めていき、最終的に最急降下法のヒューリスティックに従って最もエネルギーの低い状態に降りていくのである。
最適解への収束
[編集]任意の有限な問題に焼きなまし法を適用する場合、焼きなましスケジュールを調整してやれば、グローバルな最適解を得る確率が 1 に近づくことが知られている。しかし、理論上どうであれ、焼きなまし法で意味のある結果を得るには、解空間を十分に探索するための時間が必要ということである。
パラメータ選択
[編集]焼きなまし法を特定の問題に適用するために、状態空間、近傍選択方法（次の状態 s' の候補の列挙方法）、遷移確率関数、焼きなましスケジュールなどを指定しなければならない。これらの選択はこの方法の有効性に大きく影響する。あいにく、すべての問題に最善の選択というものは無い。このことは、ノーフリーランチ定理としてしられている。また、与えられた問題に最善の選択を見つける一般的方法も存在しない。焼きなまし法を適用することは、科学というよりも技能と言えるものであることが観察されている。
状態近傍
[編集]近傍の選択方法は、特に重要である。「探索グラフ」としてモデル化できる場合もある。状態を点とし、近傍となる点との間に線が引かれる。概して、初期状態からこのグラフ上の相対的に短いパスを通って「十分によい」状態となる可能性は極めて高く、そのようなパスを焼きなまし法の繰り返しで辿ることもほぼ間違いない。
実際には、s の近傍に s とほぼ同じエネルギーの状態群を置く様に探索グラフを作成し、この手法を適用する場合を考える。したがって、巡回セールスマン問題なら、経路上隣接する2つの都市の順序を入れ替えることで近傍を生成した方が、任意の都市を入れ替えた経路を生成するよりもエネルギーの変化が小さい。n-1 回、任意の都市を入れ替えることで最適解が見つかるとすれば、隣接都市の入れ替えでは n(n-1)/2 回の入れ替えを必要とする。しかし、任意の都市入れ替えを適用した場合、ほぼ確実にエネルギーの大幅な増加となるだろう。一方、隣接都市入れ替えではエネルギーの変化は小さい。
遷移確率
[編集]遷移確率関数 P は、上述の条件を満たしている限り、状態近傍グラフほど重要ではない。確率は温度 T に依存するが、実際には同じ確率関数をどんな問題にも適用し、焼きなましスケジュールで問題固有の調整を行うことが多い。
Kirkpatrickらが定式化した本来の手法では、遷移確率 P(e, e' , T) は e' < e の時に 1 を返すよう定義されている（すなわち下りの移動は必ず実行される）。そうでない場合の確率はexp((e−e' )/T) と定義されている。
この数式は、ガスの分子のエネルギー配布を表すマクスウェル分布からサンプルを生成するために使われたメトロポリス法から出てきたものといわれている。しかし、焼きなまし法でこの特定の数式を使うという数学的正当性はまったくない。物理的な相似さえ誤解を招く。焼きなまし法において近傍は逐次評価されるので、焼きなまし法で状態 s から状態 s' に遷移する実際の確率はその式とは全く関係ない。
焼きなましスケジュール
[編集]焼きなましスケジュールは、近傍関数ほど重要ではないが、注意して選択する必要がある。初期温度は、上りと下りの遷移確率をほぼ同じにする程度に大きく設定しなければならない。そのため、事前にランダムな状態とその近傍との差 e' −e がどうなるかを予測しておく必要がある。
温度は、その後最終的に 0 になるまで減少していく。一般的には、指数関数的に減少するようスケジュールする。その場合、温度はステップ毎に 1 より小さい固定の数 α を掛けることで減少させる。
擬似コード
[編集]以下の擬似コードは、焼きなまし法を実装したもので、これまで述べたように、状態 startState から開始して maxIter を上限としてステップを繰り返し、エネルギー状態が goalE 以下になる解が見つかるまで動作する。
- EVAL(state)
- 状態 state の評価値（エネルギー状態）。
- NEIGHBOUR(state)
- 状態 state の近傍をランダムに1つ生成する。
- TEMPERATURE(r)
- 焼きなましスケジュール。使用すべき温度を返す。ここではある定数 のべき乗としている。 。
- PROBABILITY(e1, e2, t)
- 温度 t の元 e1 から e2 へ遷移する確率。
- random()
- 0以上1以下の乱数を返す。
function 焼きなまし法(startState, maxIter, goalE)
state = startState
e = EVAL(state)
bestState = state
bestE = e
for (iter = 0; iter < maxIter; iter++)
nextState = NEIGHBOUR(state)
nextE = EVAL(nextState)
if nextE < bestE then
bestState = nextState
bestE = nextE
if bestE <= goalE then
return bestState
if random() <= PROBABILITY(e, nextE, TEMPERATURE(iter / maxIter)) then
state = nextState
e = nextE
return bestState
function PROBABILITY(e1, e2, t)
if e1 >= e2 then
return 1
else
return
function TEMPERATURE(r)
return
関連手法
[編集]- タブーサーチ (TS) は焼きなまし法に似ていて、どちらも現在の解の近傍を探索する手法である。タブーサーチでは、探索が堂々巡りにならないように既に評価した解をタブーリストで管理して、それらの解への移動は抑制される。
- 蟻コロニー最適化 (ACO) は、多数の蟻（またはエージェント）を解空間に配置して最適解の探索を行う。
- 遺伝的アルゴリズム (GA) は、ひとつの解ではなく、複数の解のプールを管理する。新たな解は、「突然変異」や「交叉」によって生成される。焼きなまし法のような確率的手法が「選択」と呼ばれていて、突然変異や交叉で生成された候補を選別し、選別されなかった解は捨てられる。
脚注
[編集]- ^ Kirkpatrick, S.; Gelatt Jr, C. D.; Vecchi, M. P. (1983). “Optimization by Simulated Annealing”. Science 220 (4598): 671–680. Bibcode: 1983Sci...220..671K. doi:10.1126/science.220.4598.671. JSTOR 1690046. PMID 17813860.
- ^ Černý, V. (1985). “Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm”. Journal of Optimization Theory and Applications 45: 41–51. doi:10.1007/BF00940812.
関連項目
[編集]外部リンク
[編集]- The Travelling Salesman Problem(英語) 巡回セールスマン問題への焼きなまし法の適用についてのサイト。
- Simulated Annealing(英語) 焼きなまし法を使った巡回セールスマン問題を解くJavaアプレットがある。
