Табу поиск в Python

Табу поиск в Python

Применение одного из самых популярных алгоритмов метаэвристики под названием Tabu Search для решения известной NP-трудной задачи планирования с использованием Python.

Мы находим оптимизацию во всех сферах жизни вокруг нас, от инженерного проектирования и промышленного производства до выбора ужина из меню или планирования поездки, и в целом мы всегда стараемся оптимизировать цели, связанные с проблемой, такие как прибыль, производительность. , стоимость, качество, удовольствие и т. д. В информатике, искусственном интеллекте и математической оптимизации метаэвристика - это метод, предназначенный для решения проблем с приближенным решением, когда классические методы не могут найти точное решение в разумное количество времени (NP-сложные задачи). Tabu Search (TS) - один из этих метаэвристических методов, и он является одним из самых известных из-за его способности эффективно решать самые разные проблемы.

В этой статье мы рассмотрим и узнаем, как работает TS, применяя его для решения проблемы общей взвешенной задержки на одной машине (SMTWTP), которая является NP-сложной проблемой. (Чтобы увидеть полный Python, перейдите в конец статьи)

Проблема общего взвешенного опоздания для отдельной машины

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

Каждое задание i ∈ N требует целочисленного времени обработки P i и имеет положительный вес W i указывает на важность задания и срок выполнения d i. Если предположить, что машина становится доступной для обработки в нулевой момент времени, мы можем указать время завершения задания i как C i, а задержку выполнения задания можно рассчитать как T i = max {C i - d i , 0}, поэтому, если задание обрабатывается до срока выполнения C i ≤ d i, опозданий не будет T = 0.

Цель состоит в том, чтобы упорядочить N заданий таким образом, чтобы свести к минимуму общую взвешенную задержку всего процесса, т. Е. Min ∑ W i T i, обратите внимание, что если работа имеет больший вес, штраф за опоздание будет выше.

Чтобы лучше понять проблему, возьмем следующий пример и начнем создавать наш код Python. (Дополнительные примеры проблем см. Здесь)

В импортированном нами экземпляре проблемы нужно запланировать 10 заданий. Затем нам нужно представить целевую функцию, которую мы хотим оптимизировать (min ∑ W i T i), функция должна возвращать один значение, представляющее пригодность (качество) данного решения.

Предположим, что одно решение распределяет задания случайным образом как [1,2,5,6,8,9,10,3,4,7], а другое решение как [2,3,5,10,6,8,9, 4,7,1], мы можем использовать Objfun, чтобы увидеть, какое решение лучше:

Обратите внимание, что решение 2 имеет лучшее значение целевой функции (минимизация). Таким образом, мы рассматриваем это как лучшее решение нашей проблемы.

Базовый алгоритм поиска табу

Впервые TS была предложена Гловером в 1986 году, а также параллельно разрабатывалась Хансеном, с тех пор TS успешно применялась для решения многих задач оптимизации. Вкратце, TS пытается найти наилучшее допустимое решение в окрестности текущего решения на каждой итерации, рассматривая недавние решения как «Tabu», чтобы предотвратить зацикливание.

Начнем с общих шагов по созданию алгоритма:

Шаг 0: Первым шагом является создание начального решения, чтобы алгоритм мог перебирать его и находить лучшее. Первоначальное решение можно рассматривать как отправную точку алгоритма, в большинстве случаев это начальное решение назначается случайным образом, однако, если вы лучше понимаете проблему, вы можете разработать конкретный алгоритм для построения начального решения. Для SMTWTP здесь мы случайным образом создадим начальное решение следующим образом:

Шаг 1: Теперь, когда у нас есть начальное решение, следующим шагом будет создание списка возможных решений из текущего решения 𝕊 (начальное решение на итерации 0), мы назовем эти решения соседями или окрестностью. Чтобы найти соседние решения из текущего решения 𝕊, нам нужно определить так называемую функцию соседства, при которой каждое решение 𝕊 имеет ассоциированное подмножество решений. Предположим, что текущее решение в SMTWTP - 𝕊 = [3, 8, 10, 4, 1, 6, 2, 5, 9, 7], и мы определили нашу функцию соседства как swap move N ( 𝕊 , Swap), т. е. заменить порядок двух заданий, таким образом, одно решение для соседства будет [ 8, 3, 10, 4, 1, 6, 2, 5, 9, 7], где задания 8 и 3 меняются местами, другим будет [8, 3, 5, 4, 1, 6, 2, 10, 9, 7 ], меняя местами 5 и 10. В заключение, количество решений соседства из 𝕊, выполняющих перестановку, равно (n-2) для каждого из n заданий, в нотации Big-O это O (n2).

Шаг 2: из списка решений для соседства, созданного на шаге 1, мы выбираем наилучшее допустимое (не являющееся запретным или отвечающее критериям стремления) решение, проверяя каждое решение, как показано на диаграмме. ниже:

Прежде чем перейти к следующему шагу, давайте взглянем на список табу и критерии стремления, упомянутые на диаграмме выше. Эти две концепции делают алгоритм TS таким мощным и уникальным алгоритмом:

Список табу

Это список, который TS использует для записи недавних решений и предотвращает их повторное появление в течение определенного количества итераций, что помогает уйти от поиска ранее посещенных решений, тем самым выполняя более обширное исследование.

• Срок действия табу: определяет размер списка табу, т. е. для того, сколько итераций компонент решения сохраняется как табу. В нашей задаче, например, мы можем предположить, что срок действия табу равен 2, в итерации-1 список табу пуст, список табу = {}, давайте предположим, что наилучшее допустимое решение, найденное на итерации-1, - [8, 3, 5 , 4, 1, 6, 2, 10, 9, 7] (согласно шагу 1 и 2), таким образом, список табу становится {[8, 3, 5, 4, 1, 6, 2, 10, 9, 7]}, на второй итерации лучшим решением остается [8, 3, 5, 4, 1, 6, 2, 10, 9, 7], однако, это недопустимо, потому что это Табу, поэтому мы берем следующее лучшее решение, допустим, это [8, 3, 5, 4, 1, 6, 2, 10, 7,9], сейчас список табу равно {[8, 3, 5, 4, 1, 6, 2, 10, 9, 7], [8, 3, 5, 4, 1, 6, 2, 10, 7,9]}. На итерации-3 [8, 3, 5, 4, 1, 6, 2, 10, 9, 7] решение выходит из списка Tabu, а следующее наилучшее допустимое решение попадает в список (поскольку размер списка равен 2) , и так далее. Обратите внимание, что Tabu Tenure оказывает большое влияние на производительность TS, и мы можем сказать, что чем меньше срок пребывания, тем выше вероятность переключения. В общем, не существует простого правила установки срока владения табу, это сильно зависит от проблемы, которую вы пытаетесь решить.
• Атрибут табу: Как вы могли заметить, если у нас большой срок владения табу и большие проблемы, такие как 10000 заданий в нашей проблеме вместо 10, запись часто посещаемых решений в список запретов будет очень трудоемкой. и дорого. Вместо этого мы сохраняем выполненные действия, а не все решение. Атрибуты табу определяют компонент решения, который хранится в списке табу. Из примера, описанного в Tabu Tenure выше, мы могли бы сохранить задания, которые были поменяны местами, Tabu list = {(8,3), (7,9)}, что означает, что не менять местами задания (8,3) или ( 7,9) для следующих двух итераций.

Критерии стремления

Если решение, найденное в текущей итерации, имеет значение (значение целевой функции) лучше, чем значение известного на данный момент лучшего решения, но ход (например, не заменять задание 3 на 1) составляет Табу, мы можем использовать Критерии стремления, чтобы переопределить запретное состояние этого движения, тем самым включая исключенное иначе решение в разрешенный набор.

Вернемся к основным шагам алгоритма.

Шаг 3: проверьте определенные критерии остановки, это может быть максимальное количество достигнутых итераций или время выполнения; если критерии остановки не соблюдены, перейдите к шаг 4, если выполняются критерии остановки, завершить и вернуть лучшее решение.

Шаг 4: обновите список табу, критерии стремления и перейдите к шагу 1

Теперь, когда мы понимаем все основные этапы алгоритма, мы можем объединить все это в один унифицированный код:

Note: The TS algorithm explained here only involves short-term memory, it can sometimes successfully solve difficult problems, but in most cases, we need additional elements in our search strategy such as Intensification and Diversification to better search the solution space and find the best solution possible.

You can check the TS with long-memory code Here