|
焼きなまし法（やきなましほう、、SAと略記、疑似アニーリング法、擬似焼きなまし法、シミュレーティド・アニーリングともいう）は、大域的最適化問題への汎用の乱択アルゴリズムである。広大な探索空間内の与えられた関数の大域的最適解に対して、よい近似を与える。 S. Kirkpatrick、C. D. Gelatt、M. P. Vecchiらが1983年に考案し、1985年に V. Cerny が再発見した。 その名称は、金属工学における焼きなましから来ている。焼きなましは、金属材料を熱した後で徐々に冷やし、結晶を成長させてその欠陥を減らす作業である。熱によって原子は初期の位置（内部エネルギーがローカルな極小状態）から離され、よりエネルギーの高い状態をうろつく。ゆっくり冷却することで、原子は初期状態よりも内部エネルギーがさらに極小な状態を得る可能性が多くなる。 SAアルゴリズムは、解を繰り返し求め直すにあたって、現在の解のランダムな近傍の解を求めるのだが、その際に与えられた関数の値とグローバルなパラメータ ''T''（温度を意味する）が影響する。そして、前述の物理過程との相似によって、''T''（温度）の値は徐々に小さくなっていく。このため、最初は''T''が大きいので、解は大胆に変化するが、''T''がゼロに近づくにつれて収束していく。最初は簡単に勾配を上がっていけるので、山登り法で問題となるようなローカルな極小に陥ったときの対処を考える必要がない。 ==概要== 焼きなまし法では、探索空間の各点「s」は物理システムの「状態」に対応し、最小化すべき関数 ''E''(''s'') は物理状態の「内部エネルギー」に対応する。従って、目標はシステムを任意の「初期状態」からできる限りエネルギーが最小の状態にすることである。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「焼きなまし法」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Simulated annealing 」があります。 スポンサード リンク
|