Симулирано закаляване

Симулираното закаляване (на английски: simulated annealing, SA) е вероятностна техника за апроксимиране на глобалния оптимум на дадена функция. По-конкретно, това е метаевристичен метод за апроксимиране на глобална оптимизация в голямо пространство на търсенето. Често се използва когато пространството на търсенето е дискретно (например, всички маршрути, по които дадено множество градове могат да бъдат обходени в задачата за търговския пътник). За задачи, при които за фиксирано време откриването на приблизителен глобален оптимум е по-важно от откриването на точен локален оптимум, методът на симулираното закаляване може да се окаже за предпочитане пред алтернативни методи като метода на градиентното спускане.

Названието и оригиналната метафора за тази метаевристика идват от областта на металургията, от техниката на закаляване, която включва нагряване и контролирано охлаждане на материала с цел повишаване размерите на неговите кристали и намаляване на дефектите им. Нагряването и охлаждането на материала повлиява както температурата, така и термодинамичната свободна енергия. Симулираното закаляване е формулирано за първи път от Армен Хачатурян, Светлана Семеновская и Борис Вайнщайн през 1979 г. и отново от същия колектив през 1981 г. Авторите са използвали компютърна симулация, имитираща загряване и охлаждане на система с цел откриване на глобалния ѝ минимум.

Идеята за бавното охлаждане е внедрена в алгоритъма на симулираното закаляване като бавно намаляване на вероятността за приемане на по-лоши кандидат-решения при претърсването на пространството на решенията. Приемането на по-лоши решения е фундаментално свойство на метаевристичните методи, тъй като то позволява по-изчерпателното претърсване на пространството на оптимално решение и помага за избягването на „забиването“ в локални оптимуми. Симулацията може да се извърши или с решаване на кинетични уравнения за функции на плътност, или с използване на метода на стохастичното универсално семплиране, който е описан независимо от три групи изследователи: Скот Къркпатрик, С. Даниъл Джелат и Марио П. Веки през 1983 г., Владо Черни през 1985 г. и от Светлана Семеновская, Карен Хачатурян и Армен Хачатурян през 1985 г. Методът е адаптация на алгоритъма на Метрополис-Хейстингс, вид Монте Карло метод, който генерира примерни състояния на една термодинамична система, измислен от М. Н. Розенблут и публикуван от Н. Метрополис и съавтори през 1953 г.

Обща постановка

Нека знаем термодинамичното състояние на някоя физическа система. Функцията E(s), която трябва да се минимизира, е аналог на вътрешната енергия на системата в това състояние. Целта е системата да се доведе от произволно начално състояние до състояние с минимална възможна енергия.

Симулирано закаляване над задача за търсене на максимум. Целта тук е да се открие максималната стойност, но не е достатъчно да се използва прост алгоритъм за изкачване поради наличието на множество локални максимуми. С постепенното намаляване на температурата глобалният максимум бива открит.

Тази страница частично или изцяло представлява превод на страницата Simulate annealing в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​