43. Алгоритм поиска с запретами (Дима)

Алгоритм подъёма очень прост алгоритмически и может быть реализо­ван буквально в нескольких строках на любом высокоуровневом языке. Он практически не требует для работы памяти и хорошо подходит для оптими­зации «на лету». С учётом сравнительно неплохих показателей эффективно­сти алгоритм подъёма — это идеальный первый выбор при решении неслож­ных задач оптимизации.

Результатом простоты алгоритма, однако, являются его очевидные недос­татки, главный из которых — преждевременная сходимость. Алгоритм подъёма очень легко «застревает» в субоптимальных решениях, вследствие чего его можно рассматривать только как быстрый алгоритм локального поиска, но не как метод глобальной оптимизации. Поиск с запретами (Tabu Search), предло­женный Фредом Гловером (Fred Glover) в 1986 г. [3], можно считать модифика­цией алгоритма подъёма, в некоторой степени свободной от этой проблемы.

Как и алгоритм подъёма, алгоритм поиска с запретами является метаэври- стическим алгоритмом Монте-Карло. Основана на использовании информации только о полученных ранее результатах, без учёта каких-либо характеристик поискового пространства и других особен­ностей задачи. Это уменьшает его эффективность по сравнению со специализи­рованными алгоритмами, однако благодаря этому метод поиска с запретами мо­жет быть использован для решения достаточно широкого круга задач, так как по­зволяет работать с анализируемой системой как с «чёрным ящиком».

Стратегия поиска, положенная в основу рассматриваемого метода, до­вольно проста. Как и алгоритм подъёма, алгоритм поиска с запретами двигает­ся по пространству решений от точки к точке. Из каждой точки он переходит в наиболее удачную из его окрестности, т. е. из множества точек, которые могут быть получены применением операции мутации к исходной.

Избежать «застревания» в локальных оптимумах удается благодаря то­му, что переходы в уже посещенные точки запрещены, т. е. являются «табу». Такое ограничение гарантирует, что алгоритм не зациклится в окрестностях некоторого субоптимального решения, а продолжит исследование простран­ства поиска. С точки зрения искусственного интеллекта, такое поведение яв­ляется естественным: отклонение от уже проверенной стратегии поведения, иногда рассматриваемое как ошибка, может привести к получению лучшего результата. Этот механизм является крайне важным - даже фундаменталь­ным - для человека, он представляет собой не что иное, как «изобретатель­ность» и «находчивость».

На каждом шаге работы алгоритм поиска с запретами исследует окрест- . ности текущей точки и выбирает из возможных вариантов для перехода наи­лучший. Однако, если выбранная точка уже посещалась и находится в списке запретов, алгоритм переходит в наиболее удачную из точек, не включенных в этот список. Перейдя к новому решению, алгоритм заносит предыдущее в список запретов. Список запретов должен хранить пройденные алгоритмом решения, чтобы избежать их повторного посещения. Однако хранить все пройденные точки, естественно, неразумно, а во многих случаях - невозмож­но. Проще всего решить эту проблему с помощью циклического списка: по­сле накопления порогового числа элементов в списке при добавлении каждо­го нового элемента из него удаляется первый элемент. Таким образом, спи­сок всегда хранит некоторое количество последних посещённых решений.

Простейшим вариантом выбора критерия останова является использова­ние ограничения на число итераций алгоритма. Кроме того, может быть огра­ничено число итераций без улучшения значения целевой функции либо оста-

новка может происходить при достижении этим значением определённого - заданного заранее - уровня. В более сложных схемах используют комбинацию всех трёх критериев.

Алгоритм поиска с запретами является метаэвристическим, поэтому об­ласть его применения крайне широка. К ней относится, в первую очередь, комбинаторная оптимизация. Кроме того, алгоритм применяется в сфере ма­шинного обучения, сетевых технологий и телекоммуникаций, в биохимии, исследовании операций и др. В последние годы наблюдается увеличение числа публикаций, посвящённых применению алгоритма в непривычных для него сферах, например в непрерывных областях, стохастическом программи­ровании и многокритериальной оптимизации.

С учетом алгоритмической простоты метод поиска с запретами является крайне успешным подходом. Он широко применяется для решения сложных комбинаторных проблем. Главной сложностью при его использовании является необходимость детальной информации о предметной области задачи: для при­менения алгоритма требуется знать характеристики поискового пространства, а также правильно выбрать способ определения окрестностей точки в нём.