Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 95
Текст из файла (страница 95)
тельности, а получается последовательно следующим образом; !. Вычисляем Р(о) для всех элементов оЕ )г. 2. Выбираем пару а,', Ь; так, чтобы выигрыш д, =0 (а,')+ 0(Ь;) — 2с(,, (19.11) был как можно большим (не обязательно положительным). 3. Обмениваем а,' и Ь) и заново вычисляем значения 0 по формулам Р' (х) = 0 (х) + 2д „вЂ” 2д„„, х Е А —,'а,'), (19.12) 0' (у) = Р (у) -1- 2д — 2д, у Š — (Ь;) (см. задачу 3). 481 19,5.
Зада«а 4» равномерное разбиение графа 4. Повторяем шаги 2 и 3, получая последовательность обмениваемых пар а,',(з'; а,', (з;; ...; а„',(з;,. После того как некоторая пара обменивается, она больше не рассматривается для обмена на шаге 2. В результате получаем последовательность выигрышей ре,...,д„ н соответствующие обмениваемые пары, такие, что в результате обмена множества Х=(а,', ..., а») с множеством У=(Ь;, ...,(з») суммарный выигрыш равен 6 (й) ** 2' кг (19.!3) Заметим, что если /г=и, то это означает, что мы полностью поменяли местами А и В, поэтому 6(л)=0.
Выбираем й так, чтобы 6(О Рис. 19.11, Гипотетическая фуикиия суммарного выигрыша б. 6(й) было максимальным. Если С(й) 0 останавливаемся, Если 6(н))0, обмениваем соответствующие множества Х и У и начинаем процедуру снова с шага 1. В результате получаем следующее. Предположим, что а=12 и последовательность д, порождает функцию 6, изображенную иа рис.
19.11, с максимумом при й=7, В результате мы находим два множества мощности й=7, которые следует переставить. Но эту перестановку было бы трудно найти, рассматривая только один обмен на каждом шаге, так как второй, третий и пятый обмены на самом деле невыгодны (рис, 19.11 показывает, что д„д» и д, отрицательны).
Таким образом, мы в состоянии произвести «глубокий» прорыв иа расстояние семи обменов от точки, в которой мы находимся, без необходимости перебора всех таких последовательностей. Этот метош который мы будем называть поиском переменной глубины, всегда находит одиночный выгодный обмен, если такой существует, поэтому получаемые результаты по крайней мере локально оптимальны для окрестностей относительно обмена йг,. Но действительная мощь этого метода основана на использовании стоимости 16 зв 3032 Гл. !9, Локальныа поиск 482 для нахождения наилучшего выигрыша при каждом выполнении шага 2.
На рис. !9.[2 мы постарались наглядно показать разницу между локальным поиском и поиском переменной глубины. Начал Начало льный тимум Окрести М Окдльиыв оптим ум (б) (а) Рис. )9Л2. а) Схематическое представление обычного локального поиска. б) Схематическое представление поиска переменной глубины. Этот метод оказывается эмпирически очень хорошим для задачи РРГ.
Керниган и Лин [К[.1 сообщают, что вероятность глобальной оптимальности для задач размера а=30 оказывается около 0,5 (в отличие от указанной выше величины О, ! для обычного локального поиска) и в целом для задач, изученных ими, приблизительно р='й игае. Кроме того, сообщается, что, как показывают эксперименты, полное время работы алгоритма поиска переменной глубины есть 0(п"') (см, задачу 6). Описанная основная идея с большим успехом применена к ЗК [1К!, где, однако, появляются дополнительные трудности из-за необходимости следить за допустимостью последовательности замен ребер, Лин и Керниган [!.К1 детально обсуждают соответствующий алгоритм вместе с некоторыми усовершенствованиями, которые либо уменьшают время работы, не сильно жертвуя качеством, либо улучшают качество решений без существенного увеличения времени работы.
е 9.6 Общие аспекты локального поиска Приведенные четыре примера иллюстрируют разнообразие задач, к которым применяется локальный поиск. (Еще несколько приложений указаны в «Комментариях и ссылках».) Каждое такое применение обладает своими особенностями и трудностями, которые надо преодолеть, но при этом имеется нечто сбщее, что мы сейчас и обсудим.
Первый аспект, который обычно возникает, — это выбор окрестности или семейства окрестностей, что тесно связано с понятием «естественного» возмущения допустимого решения. Выбор такого 1э,б. Общие алле«»лм еокольлоео лоиоко возмущения может быть почти вынужденным, подобно обмену в задаче о разбиении графа. Или может быть менее очевидным, подобно Х-замене в задаче о надежной сети.
И может даже потребовать некоторой изобретательности, подобно «с>-оптимальности» в задаче о многопродуктовом потоке (см. (С»г) и (С>Я). Во многих случаях с возмущением связан «порядок> и, как, например, в случае й-замены для ЗК, и получаемые в результате окрестности имеют мощность 0(л>). Далее, как правило, оказывается, что для задач с размером в заданных пределах естественная окрестность разумного размера обладает определенной силой — т. е, локальные оптимумы, получаемые с помощью локального поиска, имеют определенное среднее качество. Эта сила, по-видимому, в большой степени связана с корреляцией между качеством исходных допустимых решений и качеством получаемых локальных оптимумов. Похоже, что сильные окрестности приводят к локальным оптимумам, качество которых очень слабо зависит от качества начальных решений, а слабые окрестности приводят к локальным оптимумам, качество которых сильно связано с качеством начальных решений, Например, 3-замена выглядит сильной для ЗК с размером по крайней мере до 50 городов, поэтому совершенно случайные начальные обходы являются хорошими начальными решениями, так как они дают возможность испытать широкое множество локальных оптимумов.
В противоположность этому было обнаружено, что Х-замена слабее [З(ФК) и требует эвристической конструкции для порождения начальных решений с хорошей средней стоимостью. Следовательно, относительная сила окрестностей определяет, должны ли использоваться некоторые специальные или совершенно случайные начальные решения.
Здесь возникает еще один вопрос: каким образом производить поиск по окрестности? Два крайних способа — это первое улучшение, при котором выгодное изменение производится сразу же, как только оно найдено, без дальнейшего поиска, и наискарейший спуск, при котором производится поиск по всей окрестности и выбирается решение с наименьшей стоимостью. Лишние затраты времени на реализацию наискорейшего спуска часто бывают неоправданны, хотя такие вещи опасно обобщать. Большое преимущество метода первого улучшения состоит в том, что только по заключительной окрестности заведомо приходится производить полный поиск, поэтому локальные оптимумы можно, вообще говоря, найти быстрее.
Метод переменной глубины из работы (КЫ можно рассматривать как разновидность стратегии неполного поиска в применении к расширенному варианту исходной окрестности. Еще один вопрос — это в каком порядке просматривать окрестность. Проще всего обычно использовать некоторый естественный лексикографический порядок, индуцнрованный нумерацией.
Можно также упорядочить окрестность случайным образом. Этот способ 16« Гж 19. Локальямй иоиск обладает тем преимуществом, что даже из одной начальной точки с использованием метода первого улучшения получается набор случайным образом распределенных локальных оптимумов. Эта стратегия может быть полезной, если трудно получать начальные решения. Если используется фиксированное упорядочение окрестности вместе с методом первого улучшения, то поиск по новой окрестности может начинаться с начала этого упорядочения или может продолжаться из той точки, где закончился последний поиск.
(Кроун [Кг) называет эти варианты соответственно А и В.) Последний вариант будем называть круговым поиском. В нем используется счетчик для определения того момента, когда найден локальный оптимум — т. е. когда в некотором решении мы сделаем оборот на 360'. Можно утверждать, что круговой поиск, по-видимому, более эффективен, чем стратегия возвращения к началу, поскольку изменения, которые совсем недавно оказались невыгодными в одной окрестности, скорее всего, останутся невыгодными в следующей.
В каждом данном приложении это нужно проверять экспериментально. Когда приближенный алгоритм типа локального поиска используется для задачи минимизации, то получается верхняя оценка стоимости оптимального решения При этом часто очень желательно иметь также нижнюю границу, так как она дает оценку относительного отклонения приближенного решения от оптимального. Часто нижнюю оценку можно получить с относительно малыми усилиями. Например, в задаче о надежной сети минимальной стоимости каждая вершина ! должна иметь степень по меньшей мере б,=гпахх(з, ), поэтому мы не можем сделать ничего лучшего, чем соединить ее с 6,. ближайшими соседями /г„...,йзп Поэтому нижней оценкой будет (19,14) В качестве другого примера Керниган и Лин (Кц указывают, что в задаче о разбиении графа можно получить нижнюю оценку, используя алгоритм построения максимального потока для нахождения величины минимального разреза (см задачу 4).
В заключение этого параграфа отметим некоторые разработки и усовершенствования, использованные в связи с локальным поиском. Первая естественная идея — получить локальный оптимум обычным способом, а затем попытаться дальше его улучшить. Кроун 1Кг) использовал такой двухэтапный метод для задачи о конвейерном расписании Этап ! находит расписание, локально оптимальное в классе перестановочных расписаний (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
