Метод запретов (табу-поиск)

1.

МЕТОД ЗАПРЕТОВ
(ТАБУ-ПОИСК)
Выполнил: студент группы ИВТ-363 Козякин Андрей.

2.

1.Описание метода
«Поиск с запретами» или «табу-поиск» является мета-алгоритмом поиска,
использующим методы локального поиска, используемые для математической
оптимизации. Алгоритм создал Фред У. Гловер в 1986 г. и формализовал в 1989 г.
Алгоритм основан на улучшении алгоритма «локального поиска». Введен список табу,
позволяющий преодолеть недостатки алгоритма локального поиска, который мог легко
попасть в локальный оптимум. Он обладает способностью глобальной оптимизации.
Тип экстремума – глобальный.

3.

2. Сравнение с локальным поиском
Локальный поиск берёт потенциальное решение задачи и проверяет его
непосредственных соседей (то есть решения, которые похожи, за исключением
нескольких очень малых деталей) в надежде нахождения улучшенного решения.
Методы локального поиска имеют тенденцию «застрять» в подоптимальных областях
или плато, где многие решения равно подходят.
Поиск с запретами улучшает производительность локального поиска путём ослабления
его основного правила. Для начала, на каждом шаге может быть принято «ухудшение»,
если нет никакого улучшения (подобно случаю, когда поиск застревает на локальном
минимуме). Кроме того, запреты (они же табу) вводятся для того, чтобы
воспрепятствовать поиску по уже посещённым решениям.

4.

3.Основная идея
1) Избежание петель в процессе поиска.
2) Принцип только продвижение, а не отступление реализуется через список табу.
3) Неиспользование локального оптимума в качестве критерия остановки.

5.

4.Компоненты
1) Табу-список.
Роль списка запретов: предотвращать циклы
поиска. Точки, направления или целевые
значения, пройденные на предыдущих этапах,
и их возврат запрещен, таблица динамически
обновляется.
2) Длина табу-списка.
Относится к числу последующих циклов,
чтобы отключить правило, создающее
окрестности (запретные объекты).
Чем короче длина, тем больше диапазон
снятия запрета (больше верхняя граница
диапазона поиска). Если длина табу слишком
велика, время расчета будет слишком
длинным.

6.

5.Типы памяти
Краткосрочные: Список недавно
рассмотренных решений. Если
потенциальное решение оказывается в
списке запрещённых, оно не может быть
посещено второй раз, пока не достигнем
истечения срока действия запрета.
Среднесрочные: Правила усиления,
предназначенные для смещения поиска в
сторону перспективных областей
пространства поиска.
Долгосрочные: Правила расширения,
которые ведут поиск в новые области (то
есть относящиеся к сбросу, когда поиск
застревает на плато иди подоптимальном
тупике).
Краткосрочные, среднесрочные и
долгосрочные списки могут перекрываться.

7.

6.Разбор шагов
Строки 1—4 начальные присвоения,
создавая начальное решение как первое
просмотренное. Основной цикл со
строки 5 (поиск оптимального
решения). Соседние решения
проверяются на табу в строке 8. Если
лучший локальный кандидат имеет
более высокое значение функции, то
текущее значение лучшее (строка 12),
оно теперь принимается в качестве
лучшего (строка 13). Локальный
лучший кандидат всегда добавляется в
табу-список (строка 15) и если табусписок полон (строка 16), табу
некоторого элемента считается
истекшим (строка 17). лучшее решение,
встреченное в процессе (строка 20).

8.

Пример: (1 - x1)^2 + 100*(x2 - x1^2)^2