焼きなまし法のソースを表示

{{otheruses|確率的メタアルゴリズム|金属の熱処理|焼きなまし}}
'''焼きなまし法'''（やきなましほう、{{lang-en-short|Simulated Annealing}}、SAと略記、'''疑似アニーリング法'''、擬似焼きなまし法、シミュレーティド・アニーリングともいう）は、大域的[[最適化問題]]への汎用の[[乱択アルゴリズム]]である。広大な[[探索]]空間内の与えられた[[関数 (数学)|関数]]の大域的最適解に対して、よい近似を与える。 S. Kirkpatrick、C. D. Gelatt、M. P. Vecchiらが[[1983年]]に考案し<ref>{{cite journal 
 |jstor=1690046 
 |pages=671–680 
 |last1=Kirkpatrick 
 |first1=S. 
 |last2=Gelatt Jr 
 |first2=C. D. 
 |last3=Vecchi 
 |first3=M. P. 
 |title=Optimization by Simulated Annealing 
 |volume=220 
 |issue=4598 
 |journal=Science 
 |year=1983 
 |pmid=17813860 
 |doi=10.1126/science.220.4598.671
 |bibcode=1983Sci...220..671K }}</ref>、1985年に V. Cerny が再発見した<ref>{{cite journal
 |doi=10.1007/BF00940812
 |title=Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm
 |year=1985
 |last1=Černý
 |first1=V.
 |journal=Journal of Optimization Theory and Applications
 |volume=45
 |pages=41–51}}</ref>。

その名称は、[[金属工学]]における[[焼きなまし]]から来ている。焼きなましは、金属材料を熱した後で徐々に冷やし、[[結晶]]を成長させてその欠陥を減らす作業である。熱によって[[原子]]は初期の位置（[[内部エネルギー]]がローカルな極小状態）から離され、よりエネルギーの高い状態をうろつく。ゆっくり冷却することで、原子は初期状態よりも内部エネルギーがさらに極小な状態を得る可能性が多くなる。

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' ''&minus;''e'' の値が増大する際には確率を減らす値を返すように設定される。つまり、ちょっとしたエネルギー上昇の向こうに極小がある可能性の方が、どんどん上昇している場合よりも高いという考え方である。しかし、この条件は必ずしも必須ではなく、上記の必須条件が満たされていればよい。

これらの特性により、状態 ''s'' の変化は温度 ''T'' に大きく依存する。大まかに言えば、''s''の変化は ''T'' が大きいときには劇的に変化し、''T'' が小さくなるとゆるやかに変化する。

===焼きなましスケジュール===
焼きなまし法のもうひとつの本質的な機能は、シミュレーションが進むにつれて、温度が徐々に下がっていく点である。最初''T''は高い（あるいは無限大の）値に設定され、何らかの「焼きなましスケジュール」に従って、ステップを経るにつれて減少していく。そのスケジュールは、ユーザーが指定する場合もあるが、予定された時間には ''T'' =0 になって終わらなければならない。このようにすると、システムは最初のうちはエネルギー関数の小さな変化を無視して最適解を求めて探索空間の広い領域をさまよい、徐々にエネルギーの低い領域に向かって探索範囲を狭めていき、最終的に[[最急降下法]]のヒューリスティックに従って最もエネルギーの低い状態に降りていくのである。

==最適解への収束==
任意の有限な問題に焼きなまし法を適用する場合、焼きなましスケジュールを調整してやれば、グローバルな最適解を得る確率が 1 に近づくことが知られている。しかし、理論上どうであれ、焼きなまし法で意味のある結果を得るには、解空間を十分に探索するための時間が必要ということである。

==パラメータ選択==
焼きなまし法を特定の問題に適用するために、状態空間、近傍選択方法（次の状態 ''s' ''の候補の列挙方法）、遷移確率関数、焼きなましスケジュールなどを指定しなければならない。これらの選択はこの方法の有効性に大きく影響する。あいにく、すべての問題に最善の選択というものは無い。このことは、[[ノーフリーランチ定理]]としてしられている。また、与えられた問題に最善の選択を見つける一般的方法も存在しない。焼きなまし法を適用することは、科学というよりも技能と言えるものであることが観察されている。

===状態近傍===
近傍の選択方法は、特に重要である。「探索[[グラフ理論|グラフ]]」としてモデル化できる場合もある。状態を点とし、近傍となる点との間に線が引かれる。概して、初期状態からこのグラフ上の相対的に短いパスを通って「十分によい」状態となる可能性は極めて高く、そのようなパスを焼きなまし法の繰り返しで辿ることもほぼ間違いない。

実際には、''s'' の近傍に ''s'' とほぼ同じエネルギーの状態群を置く様に探索グラフを作成し、この手法を適用する場合を考える。したがって、巡回セールスマン問題なら、経路上隣接する2つの都市の順序を入れ替えることで近傍を生成した方が、任意の都市を入れ替えた経路を生成するよりもエネルギーの変化が小さい。''n''-1 回、任意の都市を入れ替えることで最適解が見つかるとすれば、隣接都市の入れ替えでは ''n''(''n''-1)/2 回の入れ替えを必要とする。しかし、任意の都市入れ替えを適用した場合、ほぼ確実にエネルギーの大幅な増加となるだろう。一方、隣接都市入れ替えではエネルギーの変化は小さい。<!--must conclude the argument...--><!-- 結論が書かれていない（訳者）-->

===遷移確率===
遷移確率関数 ''P'' は、上述の条件を満たしている限り、状態近傍グラフほど重要ではない。確率は温度 ''T'' に依存するが、実際には同じ確率関数をどんな問題にも適用し、焼きなましスケジュールで問題固有の調整を行うことが多い。

Kirkpatrickらが定式化した本来の手法では、遷移確率 ''P''(''e'', ''e' '', ''T'') は ''e' ''< ''e'' の時に 1 を返すよう定義されている（すなわち下りの移動は必ず実行される）。そうでない場合の確率はexp((''e''&minus;''e' '')/T) と定義されている。

この数式は、ガスの分子のエネルギー配布を表す[[マクスウェル分布]]からサンプルを生成するために使われた[[メトロポリス法]]から出てきたものといわれている。しかし、焼きなまし法でこの特定の数式を使うという数学的正当性はまったくない。物理的な相似さえ誤解を招く。焼きなまし法において近傍は逐次評価されるので、焼きなまし法で状態 ''s'' から状態 ''s' ''に遷移する実際の確率はその式とは全く関係ない。

===焼きなましスケジュール===
焼きなましスケジュールは、近傍関数ほど重要ではないが、注意して選択する必要がある。初期温度は、上りと下りの遷移確率をほぼ同じにする程度に大きく設定しなければならない。そのため、事前にランダムな状態とその近傍との差 ''e' ''&minus;''e'' がどうなるかを予測しておく必要がある。

温度は、その後最終的に 0 になるまで減少していく。一般的には、指数関数的に減少するようスケジュールする。その場合、温度はステップ毎に 1 より小さい固定の数 &alpha; を掛けることで減少させる。

==擬似コード==
以下の[[擬似コード]]は、焼きなまし法を実装したもので、これまで述べたように、状態 ''startState'' から開始して ''maxIter'' を上限としてステップを繰り返し、エネルギー状態が ''goalE'' 以下になる解が見つかるまで動作する。
;EVAL(state)
:状態 ''state'' の評価値（エネルギー状態）。
;NEIGHBOUR(state)
:状態 ''state'' の近傍をランダムに1つ生成する。
;TEMPERATURE(r)
:焼きなましスケジュール。使用すべき温度を返す。ここではある定数 <math>\alpha</math> のべき乗としている。<math>0 < \alpha < 1</math> 。
;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''' <math>e^{\frac{e1 - e2}{t}}</math>

 '''function''' TEMPERATURE(r)
     '''return''' <math>\alpha^r</math>

==関連手法 ==
*[[タブーサーチ]] (TS) は焼きなまし法に似ていて、どちらも現在の解の近傍を探索する手法である。タブーサーチでは、探索が堂々巡りにならないように既に評価した解をタブーリストで管理して、それらの解への移動は抑制される。
*[[蟻コロニー最適化]] (ACO) は、多数の蟻（またはエージェント）を解空間に配置して最適解の探索を行う。
*[[遺伝的アルゴリズム]] (GA) は、ひとつの解ではなく、複数の解のプールを管理する。新たな解は、「突然変異」や「交叉」によって生成される。焼きなまし法のような確率的手法が「選択」と呼ばれていて、突然変異や交叉で生成された候補を選別し、選別されなかった解は捨てられる。

== 脚注 ==
{{脚注ヘルプ}}
{{reflist}}

== 関連文献 ==
* Peter Salamon, Paolo Sibani, and Richard Frost: ''Facts, Conjectures, and Improvements for Simulated Annealing'', SIAM, ISBN 0-89871-508-3 (2002).

==関連項目==
* [[量子焼きなまし法]]
* [[最適化問題]]
* [[マルコフ連鎖]]
* [[組合せ最適化]] 
* [[遺伝的アルゴリズム]]
* [[シミュレーティド・エボリューション]]
* [[タブーサーチ]]
* [[蟻コロニー最適化]]
* [[自動ラベル配置]]
* [[複合領域最適化]]
<!-- * [[Place and route]] 適当な訳語が見つからない、意訳すれば「配置と経路の最適化設計」なんだが -->
* [[巡回セールスマン問題]]
<!-- * [[Reactive search]] 訳語不明 -->

==外部リンク==
* [http://www.hermetic.ch/misc/ts3/ts3demo.htm The Travelling Salesman Problem(英語)] 巡回セールスマン問題への焼きなまし法の適用についてのサイト。
* [http://www.heatonresearch.com/articles/64/page1.html Simulated Annealing(英語)] 焼きなまし法を使った巡回セールスマン問題を解くJavaアプレットがある。

{{最適化アルゴリズム}}

{{DEFAULTSORT:やきなましほう}}
[[Category:最適化アルゴリズムとメソッド]]
[[Category:メタヒューリスティクス]]
[[Category:モンテカルロ法]]
[[Category:数学に関する記事]]