Эвристика Лина – Кернигана

Эта статья посвящена эвристике задачи коммивояжера. Информацию об эвристическом алгоритме решения задачи разделения графа см. в разделе «Алгоритм Кернигана – Лина» .

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

Вывод

Для данного экземпляра $(G,c)$ В задаче коммивояжера туры однозначно определяются набором ребер, поэтому мы можем также закодировать их как таковые. В основном цикле локального поиска у нас есть текущий тур. $T\subset \mathrm {E} (G)$ и ищем новый тур $T'\subset \mathrm {E} (G)$ такая, что симметричная разность $F=T\mathbin {\triangle } T'$ не слишком велик, а длина $\sum _{e\in T'}c(e)$ нового тура меньше продолжительности $\sum _{e\in T}c(e)$ текущего тура. С $F$ обычно намного меньше, чем $T$ и $T'$, удобно рассматривать величину

$g(F)=\sum _{e\in F\cap T}c(e)-\sum _{e\in F\setminus T}c(e)\quad$ — выгода от использования $F\subseteq \mathrm {E} (G)$ при переключении с $T$ —

с $g(T\mathbin {\triangle } T')=\sum _{e\in T}c(e)-\sum _{e\in T'}c(e)$: насколько продлится текущий тур $T$ это чем новый тур $T'$. Наивно $k$-opt можно рассматривать как проверку всех $F\subseteq \mathrm {E} (G)$ точно с $2k$ элементы ( $k$ в $T$ но не в $T'$и еще один $k$ в $T'$ но не в $T$) такой, что $T\mathbin {\triangle } F$ это снова тур, поиск такого набора, который имеет $g(F)>0$. Однако проще провести эти тесты в обратном порядке: сначала найдите правдоподобные $F$ с положительным выигрышем и только вторую проверку, если $T\mathbin {\triangle } F$ по сути это тур.

Определите маршрут в $G$ быть чередующимся (по отношению к $T$), если его ребра попеременно находятся в $T$ и не в $T$, соответственно. Поскольку подграфы ${\bigl (}\mathrm {V} (G),T{\bigr )}$ и ${\bigl (}\mathrm {V} (G),T'{\bigr )}$ являются $2$- обычный , подграф $G[T\mathbin {\triangle } T']={\bigl (}\mathrm {V} (G),T\mathbin {\triangle } T'{\bigr )}$ будут иметь вершины степени $0$, $2$, и $4$ только и в каждой вершине имеется столько же ребер, инцидентных из $T$ как есть из $T'$. Отсюда (по сути, по алгоритму Хирхольцера поиска эйлеровых схем ) граф $G[T\mathbin {\triangle } T']$ распадается на замкнутые чередующиеся следы. Наборы $F\subseteq \mathrm {E} (G)$ что может удовлетворить $F=T\mathbin {\triangle } T'$ для какого-то тура $T'$ таким образом, может быть найден путем перебора замкнутых чередующихся маршрутов в $G$, пусть даже не каждая замкнутая попеременная тропа $F$ делает $T\mathbin {\triangle } F$ в тур; альтернативно это может оказаться отключенным $2$-регулярный подграф.

Основная идея

Альтернативные тропы (закрытые или открытые) строятся путем удлинения более короткой чередующейся тропы, поэтому при исследовании окрестностей текущего тура $T$, мы исследуем дерево поиска чередующихся маршрутов. Ключевая идея алгоритма Лина-Кернигана состоит в том, чтобы удалить из этого дерева все чередующиеся маршруты, имеющие коэффициент усиления. $\leq 0$. Это не мешает находить каждый закрытый след с положительным выигрышем благодаря следующей лемме.

Лемма. Если $a_{0},\dotsc ,a_{n-1}$ числа такие, что $\sum _{i=0}^{n-1}a_{i}>0$, то существует циклическая перестановка этих чисел такая, что все частичные суммы также положительны, т. е. существует некоторая $k$ такой, что

$\sum _{i=0}^{r}a_{(k+i){\bmod {n}}}>0$ для всех $r=0,1,\dotsc ,n-1$.

Для закрытой попеременной трассы $F=e_{0}\,e_{1}\,\dots \,e_{n-1}$, можно определить $a_{i}=c(e_{i})$ если $e_{i}\in T$ и $a_{i}=-c(e_{i})$ если $e_{i}\notin T$; сумма $\sum \nolimits _{i=0}^{n-1}a_{i}$ тогда это выигрыш $g(F)$. Здесь из леммы следует, что для каждого замкнутого знакопеременного маршрута с положительным коэффициентом усиления существует хотя бы одна стартовая вершина. $v_{0}$ для которого все выигрыши частичных трасс также положительны, поэтому $F$ будет найден, когда поиск исследует ветвь чередующихся маршрутов, начинающуюся с $v_{0}$. (До этого поиск мог учитывать и другие следы $F$ начиная с других вершин, но отступая, потому что какой-то подканал не соответствует положительному ограничению усиления.) Уменьшение количества исследуемых ветвей напрямую приводит к сокращению времени выполнения, и чем раньше ветвь можно будет обрезать, тем лучше.

Это дает следующий алгоритм для поиска всех замкнутых, чередующихся следов положительного усиления на графике.

Состояние: стопка троек $(u,i,g)$, где $u\in \mathrm {V} (G)$ является вершиной, $i\geq 0$ - текущее количество ребер в следе, а $g$ это текущий коэффициент усиления следа.

1. Для всех $u\in \mathrm {V} (G)$, толкать $(u,0,0)$ в стек.
2. Пока стек непустой:
   1. Поп $(u,i,g)$ сними со стека и позволь $v_{i}:=u$. Текущий альтернативный маршрут теперь $F=\{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i}\}$.
   2. Если $i$ даже тогда:

      Для каждого $u\in \mathrm {V} (G)$ такой, что $v_{i}u\in T\setminus \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i}\}$ (их не более двух), нажмите ${\bigl (}u,i+1,g+c(v_{i}u){\bigr )}$ в стек.

   3. Если вместо этого $i$ тогда странно:
      1. Если $g>c(v_{i}v_{0})$ затем сообщите $\{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i},v_{i}v_{0}\}$ как замкнутый переменный след с усилением $g-c(v_{i}v_{0})>0$.
      2. Для каждого $u\in \mathrm {V} (G)$ такой, что $g>c(v_{i}u)$ и $v_{i}u\notin T\cup \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i}\}$ (может быть $O(n)$ из них, или их не может быть), нажмите ${\bigl (}u,i+1,g-c(v_{i}u){\bigr )}$ в стек.
3. Останавливаться

Как алгоритм перебора он имеет некоторые недостатки, поскольку он может сообщать об одном и том же следе несколько раз с разными отправными точками, но Лина-Кернигана это не волнует, поскольку он обычно прерывает перебор после обнаружения первого совпадения. Однако следует отметить, что:

• Лин-Керниган не удовлетворен тем, что нашел замкнутый альтернативный след. $F$ положительного выигрыша, это дополнительно требует, чтобы $T\mathbin {\triangle } F$ это тур.
• Лин-Керниган также различными способами ограничивает поиск, особенно в отношении глубины поиска (но не только в этом отношении). Вышеупомянутый неограниченный поиск все равно завершается, поскольку при $i=2n$ в нем больше не осталось невыбранного края $T$, но это выходит далеко за рамки того, что практически возможно исследовать.
• В большинстве итераций хочется быстро найти лучший тур. $T'$, поэтому вместо того, чтобы фактически перечислять всех братьев и сестер в дереве поиска перед исследованием первого из них, можно лениво сгенерировать этих братьев и сестер.

Базовый алгоритм Лина – Кернигана

Базовая форма алгоритма Лина-Кернигана не только выполняет локальный поиск, аналог приведенного выше перечисления, но также вводит два параметра, которые сужают поиск.

• Глубина возврата $p_{1}$ — верхняя граница длины переменного следа после возврата; за пределами этой глубины алгоритм исследует не более одного способа расширения чередующегося следа. Стандартное значение заключается в том, что $p_{1}=5$.
• Глубина неосуществимости $p_{2}$ — это переменная длина пути, после которой начинает требоваться, чтобы закрытие текущего следа (независимо от выигрыша от этого) приводило к переходу на новый тур. Стандартное значение заключается в том, что $p_{2}=2$.

Потому что есть $O(n^{\lfloor p_{1}/2\rfloor })$ чередующиеся дорожки длины $p_{1}$, и в последнем раунде алгоритма, возможно, придется проверить их все, прежде чем прийти к выводу, что текущий тур является локально оптимальным, мы получим $\lfloor p_{1}/2\rfloor$ (стандартное значение $2$) как нижнюю границу показателя сложности алгоритма. Отчет Лина и Кернигана $2.2$ как эмпирический показатель $n$ в среднем общем времени работы их алгоритма, но у других разработчиков возникли проблемы с воспроизведением этого результата. Маловероятно, что время работы в худшем случае будет полиномиальным.

С точки зрения стека, как указано выше, алгоритм следующий:

Входные данные: экземпляр $(G,c)$ задачи коммивояжера и экскурсия $T\subset \mathrm {E} (G)$

Результат: локально оптимальный тур.

Переменные:

стопка троек $(u,i,g)$, где $u\in \mathrm {V} (G)$ является вершиной, $i\geq 0$ - текущее количество ребер в следе, а $g$ текущий коэффициент усиления следа,

последовательность $v_{0},v_{1},\dotsc$ вершин в текущем чередующемся маршруте,

лучший набор $F$ ребер обмена, найденных для текущего тура, и соответствующий выигрыш $g^{*}$.

Инициализируйте стек как пустой.

Повторить

Набор $g^{*}:=0$ и $F:=\varnothing$.

Для всех $u\in \mathrm {V} (G)$, толкать $(u,0,0)$ в стек.

Пока стек непустой:

Поп $(u,i,g)$ сними со стека и позволь $v_{i}:=u$.

Если $i$ даже тогда

для каждого $u\in \mathrm {V} (G)$ такой, что $v_{i}u\in T\setminus \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i}\}$,

толкать ${\bigl (}u,i+1,g+c(v_{i}u){\bigr )}$ в стек, если: $i\leq p_{2}$, или $uv_{0}\notin T\cup \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i},v_{i}u\}$ и $T\mathbin {\triangle } \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i},v_{i}u,uv_{0}\}$ тур (проверка гамильтоничности)

еще ( $i$ странно):

Если $g>c(v_{i}v_{0})$, $g-c(v_{i}v_{0})>g^{*}$, и $T\mathbin {\triangle } \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i},v_{i}v_{0}\}$ является туром (проверка гамильтоничности), тогда пусть $F:=\{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i},v_{i}v_{0}\}$ и $g^{*}:=g-c(v_{i}v_{0})$.

Для каждого $u\in \mathrm {V} (G)$ такой, что $g>c(v_{i}u)$ и $v_{i}u\notin T\cup \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{i-1}v_{i}\}$, толкать ${\bigl (}u,i+1,g-c(v_{i}u){\bigr )}$ в стек.

Конец, если.

Позволять $(u,j,g)$ быть верхним элементом стека (просматривать, а не выталкивать). Если $i\leq j$ затем

если $g^{*}>0$ затем

набор $T:=T\mathbin {\triangle } F$ (обновить текущий тур) и очистить стек.

еще если $i>p_{1}$ затем

вытащить все элементы $(u,j,g)$ из стека, у которого есть $j>p_{1}$

конец, если

конец, если

закончиться, пока

до $g^{*}=0$.

Возвращаться $T$

Таким образом, длина рассматриваемых альтернативных маршрутов не ограничена явно, но выходит за пределы глубины обратного отслеживания. $p_{1}$ рассматривается не более одного способа расширения текущего следа, что в принципе не позволяет этим исследованиям повышать показатель сложности во время выполнения.

Ограничения

Все замкнутые чередующиеся следы, найденные описанным выше методом, связаны, но симметричная разность $T\mathbin {\triangle } T'$ двух туров быть не должно, поэтому, как правило, этот метод чередования маршрутов не может исследовать всю окрестность маршрута. $T$. В литературе по эвристике Лина-Кернигана используется термин последовательные обмены для тех, которые описываются одним чередующимся следом. Однако наименьший непоследовательный обмен заменит 4 ребра и будет состоять из двух циклов по 4 ребра в каждом (2 ребра добавлены, 2 удалены), поэтому он длинный по сравнению с типичным обменом Лина-Кернигана, и их немного по сравнению с обменом Лина-Кернигана. полный набор 4-реберных обменов.

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

Для асимметричного TSP идея использования чередующихся маршрутов с положительным выигрышем для поиска выгодных разменов менее полезна, поскольку существует меньше способов перестановки частей тура для получения новых туров, когда невозможно изменить ориентацию фигуры. Две части можно соединить только для воспроизведения оригинального тура. Три части могут быть соединены вместе, чтобы сформировать другой тур только одним способом, и соответствующий чередующийся маршрут не расширяется до закрытого маршрута для перестановки четырех частей в новый тур. Чтобы переставить четыре фигуры, нужен непоследовательный обмен.

Проверка гамильтоновости

Эвристика Лина-Кернигана проверяет достоверность кандидатов на тур. $T\mathbin {\triangle } F$ в двух точках: очевидно, при принятии решения о том, найден ли лучший тур, но также и в качестве ограничения для спуска по дереву поиска, что контролируется глубиной недопустимости. $p_{2}$. Конкретно, на большей глубине при поиске вершины $v_{2k+1}$ добавляется к альтернативному следу только в том случае, если $T\mathbin {\triangle } \{v_{0}v_{1},v_{1}v_{2},\dotsc ,v_{2k}v_{2k+1},v_{2k+1}v_{0}\}$ это тур. По замыслу этот набор ребер представляет собой 2-фактор в $G$, поэтому необходимо определить, состоит ли этот 2-фактор из одного гамильтонова цикла или вместо этого состоит из нескольких циклов.

Если наивно представить эту подзадачу как задание подпрограмме набора $n$ края в качестве входных данных, в итоге получается $O(n)$ как временная сложность этой проверки, поскольку необходимо пройти весь обход, прежде чем определить, что это на самом деле гамильтонов цикл. Это слишком медленно для второго использования этого теста, который выполняется для каждого чередующегося следа с более чем $2$ края от $T$. Если отслеживать дополнительную информацию, тест можно проводить за постоянное время.

Полезная степень свободы здесь заключается в том, что можно выбрать порядок, в котором шаг 2.3.2 перебирает все вершины; в частности, можно проследить за известным туром $T$. После выбора $k$ края от $T$, оставшийся подграф ${\bigl (}\mathrm {V} (G),T\setminus \{v_{0}v_{1},\dotsc ,v_{2k-2}v_{2k-1}\}{\bigr )}$ состоит из $k$ пути. Результаты теста гамильтоновости, проведенного при рассмотрении $(k+1)$й край $v_{2k}v_{2k+1}$ зависит только от того, на каком из этих путей произойдет $v_{2k}$ проживает и есть ли $v_{2k+1}$ это до или после $v_{2k}$. Следовательно, достаточно было бы изучить $2k$ различных случаях в рамках выполнения шага 2.3.2 для $v_{2k-1}$; насколько $v_{2k+1}$ Что касается этого, то результатом этого теста может быть унаследованная информация, а не что-то, что нужно вычислять заново.

Ссылки

• Линь, Шен ; Керниган, BW (1973). «Эффективный эвристический алгоритм решения задачи коммивояжера». Исследование операций . 21 (2): 498–516. дои : 10.1287/опре.21.2.498 .
• К. Хельсгаун (2000). «Эффективная реализация эвристики коммивояжера Лина-Кернигана». Европейский журнал операционных исследований . 126 (1): 106–130. CiteSeerX   10.1.1.180.1798 . дои : 10.1016/S0377-2217(99)00284-2 .
• Джонсон, Дэвид С.; МакГеоч, Лайл А. (1997). «Задача коммивояжера: пример локальной оптимизации» (PDF) . В ЭХЛ Аартс; Дж. К. Ленстра (ред.). Локальный поиск в комбинаторной оптимизации . Лондон: Джон Уайли и сыновья. стр. 215–310.

Внешние ссылки

• реализация ЛКХ
• Реализация Concorde TSP
• LK-эвристика в Python