Метод табу-поиска: оптимизация и области применения.
Tabu search
Поиск с запретами (Tabu Search) – метаэвристический метод оптимизации. Преодолевает локальные оптимумы, улучшая результаты локального поиска. Создан Гловером.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Алгоритм локального поиска Табу-поиск (ТП) — это метаэвристический метод поиска, использующий методы локального поиска для математической оптимизации. Он был разработан Фредом Гловером в 1986 году и формализован в 1989 году. Локальные (соседние) поиски берут потенциальное решение задачи и проверяют его непосредственных соседей (то есть решения, которые похожи, за исключением небольшого числа незначительных деталей) в надежде найти улучшенное решение. Методы локального поиска склонны застревать в субоптимальных областях или на плато, где множество решений имеют одинаковую пригодность. Табу-поиск повышает эффективность локального поиска, ослабляя его базовое правило. Во-первых, на каждом шаге могут приниматься ухудшающие ходы, если нет доступных улучшающих ходов (например, когда поиск застрял в строгом локальном минимуме). Кроме того, вводятся запреты (отсюда и термин «табу»), чтобы предотвратить возврат поиска к ранее посещенным решениям. Реализация табу-поиска использует структуры памяти, описывающие посещенные решения или наборы правил, заданные пользователем. Табу-поиск — это метаэвристический алгоритм, который можно использовать для решения задач комбинаторной оптимизации (задач, где требуется оптимальное упорядочение и выбор вариантов). Современные области применения ТП охватывают планирование ресурсов, телекоммуникации, проектирование ВЛСИ, финансовый анализ, составление расписаний, пространственное планирование, распределение энергии, молекулярную инженерию, логистику, классификацию образов, гибкое производство, управление отходами, геологоразведку, биомедицинский анализ, охрану окружающей среды и многие другие. В последние годы журналы в различных областях публикуют учебные статьи и вычислительные исследования, документирующие успехи табу-поиска в расширении границ решаемых задач — предоставляя решения, качество которых часто значительно превосходит результаты, полученные ранее применявшимися методами. Полный список применений, включая краткое описание достижений, полученных в результате практической реализации, можно найти в
Local search algorithmTabu search (TS) is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986 and formalized in 1989. Local (neighborhood) searches take a potential solution to a problem and check its immediate neighbors (that is, solutions that are similar except for very few minor details) in the hope of finding an improved solution. Local search methods have a tendency to become stuck in suboptimal regions or on plateaus where many solutions are equally fit. Tabu search enhances the performance of local search by relaxing its basic rule. First, at each step worsening moves can be accepted if no improving move is available (like when the search is stuck at a strict local minimum). In addition, prohibitions (hence the term tabu) are introduced to discourage the search from coming back to previously visited solutions. The implementation of tabu search uses memory structures that describe the visited solutions or user provided sets of rules. Tabu search is a metaheuristic algorithm that can be used for solving combinatorial optimization problems (problems where an optimal ordering and selection of options is desired). Current applications of TS span the areas of resource planning, telecommunications, VLSI design, financial analysis, scheduling, space planning, energy distribution, molecular engineering, logistics, pattern classification, flexible manufacturing, waste management, mineral exploration, biomedical analysis, environmental conservation and scores of others. In recent years, journals in a wide variety of fields have published tutorial articles and computational studies documenting successes by tabu search in extending the frontier of problems that can be handled effectively — yielding solutions whose quality often significantly surpasses that obtained by methods previously applied. A comprehensive list of applications, including summary descriptions of gains achieved from practical implementations, can be found in
Основное описание
Поиск табу использует процедуру локального или соседнего поиска для итеративного перехода от одного потенциального решения к улучшенному решению в его окрестности, пока не будет выполнен какой-либо критерий остановки (обычно, ограничение на количество попыток или пороговое значение оценки). Процедуры локального поиска часто застревают в областях с плохой оценкой или в областях, где оценка стабилизируется. Чтобы избежать этих проблем и исследовать области пространства поиска, которые остались бы неисследованными другими процедурами локального поиска, поиск табу тщательно исследует окрестность каждого решения по мере продвижения поиска. Решения, допускаемые в новую окрестность, определяются с помощью структур памяти. Используя эти структуры памяти, поиск продвигается путем итеративного перехода от текущего решения к улучшенному решению в.
Tabu search uses a local or neighborhood search procedure to iteratively move from one potential solution to an improved solution in the neighborhood of , until some stopping criterion has been satisfied (generally, an attempt limit or a score threshold). Local search procedures often become stuck in poor scoring areas or areas where scores plateau. In order to avoid these pitfalls and explore regions of the search space that would be left unexplored by other local search procedures, tabu search carefully explores the neighborhood of each solution as the search progresses. The solutions admitted to the new neighborhood, , are determined through the use of memory structures. Using these memory structures, the search progresses by iteratively moving from the current solution to an improved solution in
Поиск табу имеет несколько сходств с имитацией отжига, поскольку оба допускают возможные переходы к худшим решениям. Фактически, имитацию отжига можно рассматривать как частный случай поиска табу, в котором используется "постепенный срок запрета", то есть, переход становится табу с определенной вероятностью. Эти структуры памяти формируют так называемый список табу – набор правил и запрещенных решений, используемых для фильтрации решений, которые будут допущены в окрестность для исследования. В своей простейшей форме список табу представляет собой краткосрочный набор решений, которые были посещены в недавнем прошлом (менее чем итераций назад, где – количество предыдущих решений, которые необходимо сохранить, также называемое сроком запрета). Чаще всего список табу состоит из решений, которые изменились в процессе перехода от одного решения к другому. Для удобства описания полезно понимать, что "решение" кодируется и представляется с помощью определенных атрибутов.
Tabu search has several similarities with simulated annealing, as both involve possible downhill moves. In fact, simulated annealing could be viewed as a special form of TS, whereby we use "graduated tenure", that is, a move becomes tabu with a specified probability. These memory structures form what is known as the tabu list, a set of rules and banned solutions used to filter which solutions will be admitted to the neighborhood to be explored by the search. In its simplest form, a tabu list is a short term set of the solutions that have been visited in the recent past (less than iterations ago, where is the number of previous solutions to be stored — is also called the tabu tenure). More commonly, a tabu list consists of solutions that have changed by the process of moving from one solution to another. It is convenient, for ease of description, to understand a “solution” to be coded and represented by such attributes.