Выбор соседского отношения - Локальный поиск

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

Какие аспекты следует учитывать при выборе соседского отношения? Этот выбор может быть весьма непростым, хотя на высоком уровне альтернатива описывается достаточно тривиально.

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

(ii) Соседское окружение решения не должно быть слишком большим, потому что мы хотим иметь возможность эффективно искать в множестве соседей возможные локальные перемещения.

Если бы первый пункт был единственной проблемой, то все решения можно было бы просто сделать соседями друг друга — тогда локальных оптимумов вообще не будет, а глобальный оптимум всегда будет находиться в одном шаге! Второй пункт выявляет (очевидный) недостаток такого подхода: если бы соседское окружение текущего решения состояло из всех возможных решений, то парадигма локального поиска вообще не приносила никакой пользы и сводилась бы к простому перебору соседского окружения методом “грубой силы”.

Вообще говоря, мы уже встречали один случай, в котором выбор правильного соседского отношения оказывал огромное влияние на разрешимость задачи, хотя этот факт тогда явно не отмечался: речь идет о задаче о двудольном паросочетании. Вероятно, простейшее соседское отношение для паросочетаний выглядит так: M' является соседом M, если M' может быть получено вставкой или удалением одного ребра в M. В соответствии с этим определением мы получаем “поверхности” с множеством зубцов, как и в примерах вершинного покрытия, которые приводились выше; и по этому определению можно получить локально оптимальные паросочетания, имеющие только половину размера максимального сочетания.

Но предположим, мы попытаемся определить более сложное (и даже асимметричное) соседское отношение: M' является соседом M, если при создании соответствующей потоковой сети M' может быть получено из M одним увеличивающим путем. Что можно сказать о паросочетании M, если оно является локальным максимумом с этим соседским отношением? В этом случае увеличивающего пути не существует, поэтому M в действительности должно быть (глобальным) максимальным паросочетанием. Другими словами, с таким соседским отношением единственными локальными максимумами являются глобальные максимумы, так что прямой градиентный подъем приведет к максимальному паросочетанию. Если поразмыслить над тем, что делает алгоритм Форда-Фалкерсона в нашем сведении от двудольного паросочетания к максимальному потоку, это выглядит логично: размер паросочетания строго возрастает на каждом шаге, и нам никогда не приходится “отступать” из локального максимума. Следовательно, тщательно выбирая соседское отношение, мы превратили зазубренную поверхность оптимизации в простую воронку.

Конечно, не стоит ожидать, что всегда все будет так хорошо складываться. Например, так как задача о вершинном покрытии является NР-полной, было бы странно, если бы она допускала соседские отношения, которые одновременно порождают “удобные” поверхности, и соседские окружения с возможностью эффективного поиска. Рассмотрим несколько возможных соседских отношений в контексте задачи о максимальном разрезе из предыдущего раздела. Контрасты между этими соседскими отношениями характерны для проблем, возникающих в общей теме алгоритмов локального поиска для вычислительно сложных задач разбиения графов.

Алгоритмы локального поиска при разбиении графов

В разделе 12.4 был рассмотрен алгоритм переключения состояния для задачи о максимальном разрезе; было показано, что локально оптимальные решения обеспечивают 2-аппроксимацию. Перейдем к соседским отношениям, порождающим соседские окружения большего размера по сравнению с правилом одного переключения и соответственно пытающимся сократить распространенность локальных оптимумов. Возможно, самым естественным обобщением является соседское окружение с k-переключением для k ≥ 1: разбиения (A, B) и (A', B') называются соседними по правилу k-переключения, если (A', B') можно получить из (A, B) перемещением не более k узлов с одной стороны разбиения на другую.

Очевидно, если (A, B) и (A', B') являются соседями по правилу k-переключения, то они также являются соседями по правилу k'-переключения для всех k' > k. Следовательно, если разбиение (A, B) является локальным оптимумом по правилу k'-переключения, то оно также является локальным оптимумом по правилу k-переключения для всех k < k’. Но сокращение множества локальных оптимумов посредством повышения величины к обходится дорого: для просмотра множества соседей (A, B) по правилу k-переключения необходимо рассмотреть все Ө(n^k) способов перемещения до k узлов на другую сторону разбиения. Затраты времени становятся неприемлемыми даже при небольших значениях k.

Керниган и Лин (1970) предложили альтернативный способ генерирования соседних решений; он обладает существенно большей вычислительной эффективностью, но все при этом позволяет выполнять крупномасштабные преобразования решений за один шаг. Их метод, который мы будем называть эвристикой К-Л, определяет соседей разбиения (A, B) по следующей n-фазной процедуре.

♦ В фазе 1 выбирается один узел для переключения — так, чтобы значение полученного решения было как можно больше. Переключение выполняется даже в том случае, если значение решения убывает относительно w(A, B). Узел, изменивший состояние, помечается, а полученное решение обозначается (A₁, B₁).

♦ В начале фазы k для k > 1 мы имеем разбиение (A_k-1, B_k-1), и k - 1 узлов помечены. Один непомеченный узел выбирается для переключения таким образом, что значение полученного решения является максимальным среди всех возможных. (И снова это происходит даже в том случае, если в результате значение решения уменьшится.) Переключенный узел помечается, а полученное решение обозначается (A_k, B_k).

♦ После n фаз каждый узел окажется помеченным; это указывает на то, что он переключался ровно один раз. Соответственно последнее разбиение (A_n, B_n) в действительности является зеркальным отображением исходного разбиения (A, B): A_n = B и B_n = A. Наконец, эвристика К-Л определяет n - 1 разбиений (A₁, B₁), ..., (A_n-1, B_n-1) как соседей (A, B). Следовательно, (A, B) является локальным оптимумом по эвристике К-Л в том, и только в том случае, если w(A, B) ≥ w(A_i, B_i) для 1 ≤ i ≤ n - 1. Итак, мы видим, что эвристика К-Л определяет очень длинную серию переключений, даже если ситуация на первый взгляд ухудшается, в надежде на то, что некоторое разбиение (A_i, B_i), сгенерированное по пути, окажется лучше (A, B). Но даже при том, что она генерирует соседей, очень отличных от (A, B), выполняется только n переключений и на каждое тратится время всего O(n). С вычислительной точки зрения это намного разумнее правила k-переключения для больших значений k. Более того, эвристика К-Л на практике показала отличные результаты несмотря на то, что формальный анализ ее свойств в значительной степени остается открытой проблемой.