Головна

Алгоритм відпалу.

  1.  алгоритм
  2.  АЛГОРИТМ
  3.  алгоритм
  4.  алгоритм
  5.  АЛГОРИТМ
  6.  алгоритм
  7.  АЛГОРИТМ

Для будь-якого алгоритму зі сходженням до вершини, який ніколи не виконує руху "вниз по схилу", до станів з більш низькою оцінкою (або більш високою вартістю), гарантується, що він виявиться неповним, оскільки такий алгоритм завжди здатний зайти в глухий кут, досягнувши локального максимуму. На відміну від цього алгоритм з чисто випадковим блуканням (тобто з переміщенням до наступника, обирається на рівних правах випадковим чином з безлічі наступників) є повним, але надзвичайно неефективним. Тому видається розумною спроба скомбінувати якимось чином сходження до вершини з випадковим блуканням, що дозволить забезпечити і ефективність, і повноту.

У цьому розділі ми розглянемо метод оптимізації, який називається відпалом, або симуляцією відновлення(Simulated annealing). Як зрозуміло з назви, метод пошуку моделює процес відновлення. Відновлення - це фізичний процес, який полягає в нагріванні і наступному контрольованому охолодженні субстанції. В результаті виходить міцна кристалічна структура, яка відрізняється від структури з дефектами, що утворюється при швидкому безладному охолодженні. Структура тут є кодоване рішення, температура використовується для. того, щоб вказати, як і коли будуть прийматися нові рішення.

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

Найбільш внутрішній цикл алгоритму з емуляцією відпалу (рис. 10.31) повністю аналогічний циклу алгоритму зі сходженням до вершини, але в ньому замість найкращого ходу виконується випадково обраний хід. Якщо цей хід покращує ситуацію, то завжди приймається. В іншому випадку алгоритм приймає даний хід з певною ймовірністю, меншою 1. Ця ймовірність зменшується експоненціально з "погіршенням" ходу - в залежності від величини DE, на яку погіршується його оцінка. Крім того, ця ймовірність зменшується в міру зниження "температури" Т тобто. "Погані" ходи швидше за все можуть бути дозволені на початку, коли температура висока, але стають менш імовірними в міру зниження Т.

На перших порах, на початку 1980-х років, пошук з емуляцією відпалу широко використовувався для вирішення завдань компонування НВІС. Крім того, цей алгоритм знайшов широке застосування при вирішенні задач планування виробництва та інших великомасштабних завдань оптимізації.


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



 Алгоритм пошуку зі сходженням до вершини |  Модифікація робочого рішення.

 Евристичний пошук. |  Лекція 29 |  Ігрові моделі і їх класифікація. |  Ігри з повною інформацією і двома учасниками. |  Оптимальні стратегії. |  Мінімаксний алгоритм. |  Альфа-бета алгоритм. |  Програми гри в шахи. |  Сучасні ігрові програми. |  Локальний пошук. |

© um.co.ua - учбові матеріали та реферати