Поиск с запретами

Поиск с запретами или табу-поиск является мета-алгоритмом поиска, использующим методы локального поиска, используемые для математической оптимизации. Алгоритм создал Фред У. Гловер в 1986[1] и формализовал в 1989[2][3]

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

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

Реализация поиска с запретами использует структуры, которые описывают посещённые решения или пользовательские наборы правил[2]. Если потенциальное решение было посещено во время некоторого короткого срока или оно нарушает правило, его помечают как «табу», так что алгоритм не будет рассматривать решение повторно.

Слово табу происходит от тонганского слова, означающего вещи, которые нельзя трогать, поскольку они священны[4].

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

Текущие приложения поиска с запретами распространяется на такие области, как планирования ресурсов, телекоммуникации, разработка СБИС, финансовый анализ, составление расписаний, пространственное планирование, распределение энергии, молекулярная инженерия, логистика, классификация образов, гибкое производство, утилизация отходов, поиск полезных ископаемых, биомедицинский анализ, защита окружающей среды и многие другие. В последние годы журналы во многих областях науки публиковали учебные статьи и вычислительные исследования, показывающие успех поиска с запретами в расширении границ задач, которые могут быть решены эффективно, давая решения, качество которых часто существенно превосходило решения, полученные применяемыми до этих пор методами. Обширный список приложений, включая итоговое описание полученного результата от практического применения, можно найти в статье Гловера и Лагуны[5]. Современные разработки по поиску с запретами и приложения можно найти в статье Tabu Search Vignettes.

Основы

Поиск с запретами использует процедуру локального поиска или поиска по соседям, чтобы итеративно продвигаться от одного потенциального решения ${\displaystyle x}$ к улучшенному решению ${\displaystyle x'}$ в окрестности ${\displaystyle x}$, пока не достигнем выполнения некоторого остановочного критерия (обычно это количество итераций или порог целевой оценки). Процедуры локального поиска часто застревают в областях с плохими целевыми оценками или в областях, где оценка образует плато (ровную горизонтальную поверхность). Чтобы избежать этих ловушек и исследовать области пространства поиска, которые остались бы нерассмотренными другими процедурами поиска, поиск с запретами тщательно исследует соседство каждого решения в процессе поиска. Решения, признанные новыми соседями, ${\displaystyle N^{*}(x)}$, определяются с помощью структур в памяти. Используя эти структуры, поиск прогрессирует путём итеративного перехода от текущего решения ${\displaystyle x}$ к улучшенному решению ${\displaystyle x'}$ из списка ${\displaystyle N^{*}(x)}$.

Эти структуры образуют так называемые табу-списки, множество правил и помеченных решений, используемых для фильтрации, какие решения из соседей ${\displaystyle N^{*}(x)}$ обрабатывать при поиске. В простейшей форме табу-список является краткосрочным набором решений, которые были посещены за последние итерации (менее чем за ${\displaystyle n}$ итераций, где ${\displaystyle n}$ равно числу запоминаемых решений и это число называется сроком действия табу). Более часто табу-лист состоит из решений, которые были изменены в процессе перехода от одного решения к другому. Удобно для простоты изложения понимать «решение» закодированным и представленным некоторыми атрибутами.

Типы памяти

Структуры памяти, используемые в поиске с запретами, можно грубо разбить на три категории[6]:

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

Краткосрочные, среднесрочные и долгосрочные списки могут перекрываться. Внутри этих категорий память может далее дифференцироваться по критериям, таким как частота и воздействие сделанных изменений. Одним из примеров среднесрочной структуры является запрет или поощрение решений, которые содержат некоторые атрибуты (например, решения, которые включают нежелательные или желательные значения некоторых определённых переменных) или структура памяти, которая предотвращает или порождает некоторые движения (например, основываясь на частоте встречающихся признаков в перспективных и неперспективных решения, найденных ранее). В краткосрочной памяти выбранные атрибуты в недавно посещённых решениях помечаются «табу-активными». Использование решений с табу-активными элементами запрещается. Для изменения статуса табу решения используется критерий удаления, включая исключённые решения в разрешённый список (решение «достаточно хорошо» согласно мере качества или различия). Простым и обычно используемым критерием удаления является разрешение использования решений, которые лучше известного на данный момент лучшего решения.

Краткосрочная память одна может оказаться достаточной для получения решения, превосходящего найденное обычными методами локального поиска, но среднесрочные и долгосрочные структуры часто необходимы для решения более сложных задач[7]. Поиск с запретами часто сравнивается с другими мета-алгоритмическими методами — такими как алгоритм имитации отжига, генетические алгоритмы, муравьиные алгоритмы, реагирующий поиск, управляемый локальный поиск или жадный адаптивный случайный поиск^[англ.]. Кроме того, поиск с запретами иногда комбинируется с другими мета-алгоритмами для создания гибридных методов. Наиболее частый гибрид поиска с запретами возникает путём соединения его с разбросанным поиском (англ. Scatter Search)[8][9], классом процедур, которые имеют общие корни с поиском с запретами и которые часто применяются для решения нелинейных оптимизационных задач большого размера.

Псевдокод

Следующий псевдокод представляет упрощённую версию алгоритма поиска с запретами, как описано выше. Эта реализация имеет простейший вариант краткосрочной памяти и не содержит среднесрочных или долгосрочных структур. Термин "fitness" относится к вычислению целевой функции для кандидата в решения.

sBest ← s0
bestCandidate ← s0
tabuList ← []
tabuList.push(s0)
while (not stoppingCondition())
	sNeighborhood ← getNeighbors(bestCandidate)
	for (sCandidate in sNeighborhood)
		if ( (not tabuList.contains(sCandidate)) and (fitness(sCandidate) > fitness(bestCandidate)) )
			bestCandidate ← sCandidate
		end
	end
	if (fitness(bestCandidate) > fitness(sBest))
		sBest ← bestCandidate
	end
	tabuList.push(bestCandidate)
	if (tabuList.size > maxTabuSize)
		tabuList.removeFirst()
	end
end
return sBest

Строки 1—4 делают начальные присвоения, создавая начальное решение (возможно, полученное методами случайного поиска), устанавливают полученное решение как первое просмотренное и инициализируют табу-список этим решением. В этом примере табу-список является просто краткосрочной структурой, которая содержит записи посещённых элементов.

Основной цикл начинается со строки 5. Этот цикл продолжает поиск оптимального решения, пока не получит заданного пользователем критерия останова (двумя примерами такого критерия являются просто ограничение по времени или порог оценки годности (fitness score)). Соседние решения проверяются на табу в строке 8. Кроме того, алгоритм хранит лучшие незапрещённые решения по соседям.

Целевая функция fitness обычно является математической функцией, которая возвращает целевую оценку или критерий — например, целевым критерием может считаться нахождение нового пространства поиска[4]. Если лучший локальный кандидат имеет более высокое значение функции fitness, то текущее значение лучшее (строка 12), оно теперь принимается в качестве лучшего (строка 13). Локальный лучший кандидат всегда добавляется в табу-список (строка 15) и если табу-список полон (строка 16), табу некоторого элемента считается истекшим (строка 17). Обычно элементы удаляются из списка в порядке их занесения в него. Процедура выбирает лучшего локального кандидата (хотя он имеет значение fitness хуже, чем sBest), чтобы выскочить из локального оптимума.

Этот процесс продолжается, пока не получим определённый пользователем критерий останова, и в этот момент возвращается лучшее решение, встреченное в процессе (строка 20).

Пример: задача коммивояжёра

Задача коммивояжёра иногда используется, чтобы показать работу поиска с запретами[7]. Эта задача спрашивает, если дан список городов, каков кратчайший маршрут для посещения всех городов? Например, если город A и город B находятся близко друг от друга, а город C отстоит о них далеко, общая длина маршрута будет короче, если мы сначала посетим A и B, а затем отправимся в город C. Поскольку нахождение оптимального решения NP-трудно, для получения близкого к оптимальному решения полезны основанные на эвристике приближённые методы (такие как локальный поиск). Для получения хороших решений задачи коммивояжёра важно исследовать структуру графа. Значение исследования структуры задачи является повторяющейся темой в мета-алгоритмических методах, а поиск с запретами хорошо подходит для этого. Класс стратегий, связанный с поиском с запретами и называемый методами извлечения цепочек (англ. ejection chain methods), дают возможность получить высококачественные решения задачи коммивояжёра эффективно[10].

С другой стороны, простой поиск с запретами может быть использован для поиска удовлетворительного^[англ.] решения для задачи коммивояжёра (то есть решения, удовлетворяющего критерию пригодности, хотя и невысокого качества, которое получается после исследования структуры графа). Поиск начинается с начального решения, которое может быть получено случайным образом или согласно некоего рода алгоритму поиска ближайшего соседа. Чтобы создать новые решения, порядок, в котором города посещаются, в потенциальном решении обмениваются местами. Полное расстояние маршрута между всеми городами используется для сравнения, насколько лучше одно решение другого. Чтобы предотвратить зацикливание, то есть повторного получения определённого набора решений, и застревание в локальном оптимуме, решение добавляется в список запрещённых решений, если оно принято при поиске среди соседей, ${\displaystyle N^{*}(x)}$.

Новые решения создаются, пока не достигнем некоторого критерия остановки, такого как число итераций. Как только простой поиск с запретами останавливается, он возвращает лучшее решение, найденное при выполнении.

Примечания

1. Glover, 1986, с. 533–549.
2. Glover, 1989, с. 190–206.
3. Glover, 1990, с. 4–32.
4. Courses | Fuzzy-Neural Group | NC State ISE  (неопр.). Дата обращения: 16 января 2019. Архивировано 12 января 2014 года.
5. Glover, Laguna, 1997.
6. Glover/A Tutorial, 1990.
7. Malek, Huruswamy, Owens, Pandya, 1989.
8. Glover, Laguna, Marti, 2000, с. 653–684.
9. Laguna, Marti, 2003.
10. Gamboa, Rego, Glover, 2005, с. 154–171.

Литература

• Fred Glover. Future Paths for Integer Programming and Links to Artificial Intelligence // Computers and Operations Research. — 1986. — Т. 13, вып. 5. — doi:10.1016/0305-0548(86)90048-1.
• Fred Glover. Tabu Search – Part 1 // ORSA Journal on Computing. — 1989. — Т. 1, вып. 2. — doi:10.1287/ijoc.1.3.190.
• Fred Glover. Tabu Search – Part 2 // ORSA Journal on Computing. — 1990. — Т. 2, вып. 1. — doi:10.1287/ijoc.2.1.4.
• Gamboa D., Rego C., Glover F. Data Structures and Ejection Chains for Solving Large Scale Traveling Salesman Problems // European Journal of Operational Research. — 2005. — Т. 160, вып. 1. — doi:10.1016/j.ejor.2004.04.023.
• Glover F., Laguna M. Tabu Search. — Kluwer Academic Publishers. — 1997.
• Fred Glover. Tabu Search: A Tutorial // Interfaces. — 1990.
• Malek M., Huruswamy M., Owens H., Pandya M. Serial and parallel search techniques for the traveling salesman problem. — Annals of OR: Linkages with Artificial Intelligence. — 1989.
• Glover F., Laguna M., Marti R. Fundamentals of Scatter Search and Path Relinking. — Control and Cybernetics. — 2000. — Т. 29. — С. 653–684.
• Laguna M., Marti R. Scatter Search: Methodology and Implementations in C. — Kluwer Academic Publishers, Boston. — 2003.

Ссылки

• Visualization of the Tabu search algorithm (Applet)
• Metaheuristic International Conference (MIC 2011) – Udine
• The Reactive Search Community
• LION Conference on Learning and Intelligent Optimization techniques
• [1] (недоступная ссылка)