Метод моделювання відпалу. Переваги та недоліки

Алгоритм імітації відпалу (англ. Simulated annealing) - загальний алгоритмічний метод розв'язання задачі глобальної оптимізації, особливо дискретної та комбінаторної оптимізації, в якому процедура пошуку глобального розв'язку імітує фізичний процес відпалу.

Алгоритм імітації відпалу[ред. • ред. код]

Алгоритм імітації відпалу - загальний алгоритмічний метод розв'язання задачі глобальної оптимізації, особливо дискретної та комбінаторної оптимізації. У галузі фізики конденсованих середовищ, відпалом називається тепловий процес отримання низьких енергетичних станів тіла в тепловій бані (термостаті). Цей процес складається з двох кроків (Kirkpatrick та ін., 1983):

підвищення температури теплової бані до максимального значення, до твердих розплавів

повільне зниження температури теплової бані, поки частинки не впорядкуються в основний стан тіла

У рідкій фазі частинки розташовуються випадковим чином, а в основному стані твердого тіла всі частинки розташовані в добре структуровані ґратки, для яких відповідна енергія мінімальна. Основний стан твердого тіла отримується тільки тоді, коли максимальне значення температури досить високе і охолодження здійснюється досить повільно. В іншому випадку, тіло застигне в метастабільному стані, а не в істинному стані. Алгоритм грунтується на імітації фізичного процесу, який відбувається при кристалізації речовини з рідкого стану в твердий, у тому числі при відпалі металів. Передбачається, що атоми вже вишикувалися в кристалічну решітку, але ще допустимі переходи окремих атомів з однієї комірки в іншу. Передбачається, що процес протікає при поступовому зниженні температури. Перехід атома з однієї комірки в іншу відбувається з деякою ймовірністю, причому вірогідність зменшується з пониженням температури. Стійка кристалічна решітка відповідає мінімуму енергії атомів, тому атом або переходить в стан з меншим рівнем енергії, або залишається на місці. (Цей алгоритм також називається алгоритмом Метрополіса, за ім'ям його автора).

За допомогою моделювання такого процесу шукається така точка або множина точок, на яких досягається мінімум деякої числової функції.

Повертаючись до імітації відпалу, алгоритм Metropolis може бути використаний для генеруваня послідовності рішень задачі комбінаторної оптимізації, припускаючи еквівалентності між фізичною системою багатьох частинок і завданням комбінаторної оптимізації:

розв'язання задачі комбінаторної оптимізації еквівалентні стану фізичної системи

вартість рішення еквівалентно енергії стану системи.

Крім того, ми вводимо керуючий параметр, який відіграє роль температури. Таким чином Simulated annealing алгоритм, можна розглядати як ітерації алгоритму Metropolis, виконані на зменшення значення керуючого параметра. Значення чотирьох функцій в процедурі SIMULATED_ANNEALING очевидні:

INITIALIZE обчислює і задає початкові значення параметрам c та L

GENERATE вибирає сусідій розв'язок відносно поточного розв'язку

CALCULATE.LENGTH і CALCULATE_CONTROL обчислює нові значення параметрів L та c відповідно

Порівнюючи simulated annealing з ітераційним поліпшенням, очевидно що simulated annealing можна розглядати як узагальнення. Алгоритм імітації відпалу стає ідентичним ітераційному покращенню в разі, коли значення керуючого параметра приймається як нуль. Що стосується порівняння продуктивність обох алгоритмів, для більшості завдань simulated annealing працює швидше, ніж ітераційне покращення.

Підсумковий час реалізації моделювання відпалу виходить шляхом створення послідовності однорідних ланцюжків Маркова обмеженої довжини при низхідному значенні керуючого параметра. Для цього набору параметрів повинно бути зазначено, що визначає збіжність алгоритму. Ці параметри об'єднані в так званий графік охолодження. Графік охолодження визначає скінченну послідовність значень параметра, і скінченне число переходів при кожному значенні керуючого параметра. Точніше, він визначає: • початкове значення параметра контролю c0 • зменшення функції для зниження вартості контрольного параметра • кінцеве значення контрольного параметра, вказаний критерій зупинки, також скінченне значення довжини кожного однорідного ланцюжка Маркова.

Пошук адекватних графіків охолодження був предметом багатьох досліджень протягом останніх років. Відгуки даються Van Laarhoven і Aarts (1987), Collins та ін. (1988), Romeo та Sangiovanni-Vincentelli (1991).

Статичний графік охолодження. Це простий графік, який також називається геометричним графіком. Він походить ще з початку роботи над графіком охолодження. Він і досі використовується в багатьох практичних ситуаціях. Остаточне значення контрольного параметра, тут остаточна величина фіксується і отримує невелике значення, яке може бути пов'язане з найменш можливою різницею у вартості між двома сусідніми розв'язками.

Довжина Марковського ланцюга. Довжина Марковських ланцюгів встановлюється значенням, яке має відношення до величини сусідніх прикладних задач.

27. Метод забороненого пошуку. Переваги та недоліки.