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

от Уикипедия, свободната енциклопедия
Направо към навигацията Направо към търсенето

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

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

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

Обща постановка[редактиране | редактиране на кода]

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

Симулирано закаляване над задача за търсене на максимум. Целта тук е да се открие максималната стойност, но не е достатъчно да се използва прост алгоритъм за изкачване, поради наличието на множество локални максимуми. С постепенното намаляване на температурата, глобалният максимум бива открит.
Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „Simulate annealing“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница. Вижте източниците на оригиналната статия, състоянието ѝ при превода, и списъка на съавторите.