月別アーカイブ: 2015年9月

Simulated Annealing

担当:奥戸 道子
題目:Simulated Annealing (文献紹介)

概要:
本発表ではSimulated Annealing [1] というアルゴリズムと
そのいくつかの拡張アルゴリズムについて紹介する.
Simulated Annealingは組み合わせ最適化問題に対する汎用近似解法である.
一般的な局所探索法とは違って解の悪化方向への遷移も確率的に認めるのが特徴で,
それによって局所最適解にはまらずに大域最適解を目指すことができる.
Annealing (焼きなまし) とは金属を高温から徐々に冷却することで
エネルギーの低い綺麗な結晶を得る方法のことであるが,
Simulated Annealingはその発想を真似て温度にあたるパラメータを
じわじわと小さくすることで良い解を得ようとする.

参考文献:
[1] S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi: Optimization by Simulated Annealing. Science, vol. 220 (1983), pp. 671–680.