Імітаційний відпал!!!
Імітаційний відпал (SA) - це ще один ітеративний алгоритм вдосконалення, в якому включено випадковість для розширення пошукового простору та уникнення впадіння в локальний мінімум. Як випливає з назви, алгоритм імітує процес відпалу.
Відпал являє собою техніку в металопрокатці, де розплавлений метал нагрівається, а потім охолоджується поступовим способом, щоб рівномірно розподілити молекули в кристалічну структуру. Якщо метал охолоджується занадто швидко, це не призводить до кристалічної структури, а металева тверда речовина слабка і крихка (наповнена пухирцями та тріщинами). Якщо охолоджуватися поступово і керованим способом, кристалічна структура утворюється на молекулярному рівні, що призводить до великої структурної цілісності.
Основний алгоритм імітаційного відпалу наведено в нотатці. Почнемо з вихідного кандидата рішення та петлі, а температура перевищує нуль. У цьому циклі ми створюємо рішення сусідніх кандидатів, порушуючи наше поточне рішення. Це змінює рішення сусіднього рішення, але випадковим чином. Потім ми обчислимо енергію дельти між новим (суміжним) рішенням та нашим поточним рішенням. Якщо ця енергія дельти менша за нуль, тоді наше нове рішення краще, ніж старе, і ми приймаємо це (ми переміщуємо нове сусіднє рішення до нашого поточного рішення).
Нотатка: Алгоритм імітаційного відпалу.
simulated_annealing()
{
cur_solution = random()
computeE( cur_solution )
while (Temperature > 0)
adj_solution = perturb_solution( cur_solution )
computeE( adj_solution )
deltaE = adj_solution.energy – cur_solution.energy
/* Is new solution better, then take it */
if (deltaE < 0)
cur_solution = adj_solution
else
p = exp( -deltaE / Temperature )
/* Randomly accept worse solution */
if ( p > RANDOM(0..1) )
cur_solution = adj_solution
end
end
reduce Temperature
end
end simulated_annealing
Виконала Назаренко Валерія
