Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 94
Текст из файла (страница 94)
Эти результаты типичны для локального поиска, однако для задач большего размера вероятность нахождения глобального оптимума уменьшается и увеличивается разброс стоимостей локальных оптимумов, Исчерпывающим перебором доказано, что решение со стоимостью 242 оптимально, поэтому видно, что вероятностный алгоритм локального поиска с вероятностью около 0,39 дает глобальный оптимум. Следовательно, вероятность нахождения оптимального решения после 100 попыток равна приблизительно 1 — (0,61)ьм он! — 0,34м 10 ", 4У.4.
Задача Зг топология прибрежной системы газопроводов 47Б В итоге можно заключить, что в задаче НСМС критической является стоимость проверки на допустимость, и существование эффективных способов такой проверки делает локальный поиск практическим алгоритмом. 19.4 Задача 3: топология прмбрежной системы газопроаодоа !мГй5К! Рассмотрим теперь задачу, где не допустимость, а вычисление стоимости является критическим. Задача состоит в том, чтобы собрать запасы газа со дна моря и доставить их на находящуюся на берегу очистительную и компрессорную станцию.
На рис. 13,7 верее Рис. !9.7 Прибрежная системз газопроводов. изображена типичная система газопроводов: вершина 1 представляет станцию, расположенную на бере~у, а каждая из вершин 2, 3, ...,!5 представляет буровую платформу над областью газа с установленной ежедневной производительностью. Можно считать, что положения газовых полей длны и что задача состоит в выборе дерева, ребра которого будут представлять газопроводы, по которым газ будет собираться и доставляться на станцию, расположенную на берегу. Теперь нужно объяснить, как определяется стоимость данного дерева. Каждое ребро дерева представляет трубу одного из 7 стандартных диаметров в пределах (в 1968 г.) от 10 '1, дюйма со стоимостью около 70 000 долл. за милю до 30 дюймов со стоимостью около 310 000 долл, за милю.
Поскольку нам известна производительность в каждой вершине. то для данного дерева можно определить скорость потока по каждому ребру. Это позволяет определить падение давления вдоль некоторого ребра для всех возможных диаметров 476 Гл. !9 Лакальныа папок с помощью эмпирической формулы, называемой граничным уравнением. Диаметры труб должны выбираться так, чтобы минимизировать стоимость при следующих ограничениях: !. максимальное давление нигде не превышает заданного Р„,„,; 2.
давление на входе в станцию, расположенную на берегу, должно быть не меныпе заданного Р„„„; 3. давление газа, собираемого в каждой вершине, должно быть не меныпе Р„„я, Задача выбора оптимального множества диаметров труб является, по существу, комбинаторной задачей оптимизации, которая решается с помощью метода, иапо.линающего динамическое программпрова. ние. Это решение требует разумного, но пе тривиальУ1 ного количества машинного Уз времени для каждой тополо- ! гни, скажем около 1 с для I дерева с 20 вершинами. Г!ри этом остается про- блема, как выбрать дере- РНЕ. 1В.В ТРН РЕбРа ПРН "ЕРШННа Л' во минимальной стоимости, определяющие Ь-замену, показаны пункесли стоимость любого конкретного дерева должна определяться с помощью достаточно сложной подпрограммы требующей около 1 с времени Если используется локальный поиск, то нужно быть аккуратным при выборе окрестностей, которые должны быть достаточно малы — в противном случае время работы алгоритма станет непомерно большим.
Наиболее естественно на ум приходит система окрестностей, определяемая элементарным преобразованием дерева, описанным в примере 1.5: по очереди добавляем к дереву всевозможные ребра и по очереди удаляем каждое ребро из полученного цикла Эта система окрестностей является гочной для зада- ЧИ О МИНИМаЛЬНОМ ОСтОВНОМ дЕрЕВЕ, НО ЕЕ раЗМЕр 0(!(У! з), таК КаК нужно рассмотреть !)У1(!)У! — 1)(2 добавляемых ребер, и каждое из них порождает цикл, длина которого может быть !г(!И!).
Однако кажегся естественным, что если улучшения существуют, то найдется улучшение, которое можно обнаружить, соединяя некоторую вершину с географически ближайшей к ней вершиной Это побуждает использовать ограниченные окрестности, называемые А-зилееной, определяемые следующим образом. Для каждой вершины х. нужно найти три ближпйшие вершины у„уе и у„не смежные с вершиной х в дереве. Затем следует рассмотреть элементарные преобразования дерева, определяемые ребрами (х, у,(, !х, у,! и (х, дя! (рис 19.8).
Мощность такой окрестности равна Зп!'к'1, где 1е — средняя длина цикла, получаемого при элементарных преобразованиях !9яп Задича 3? топология прибреяспоа системы газопрпводов 47? Начальная 20.летняя стоимость = НО 970 000 долга Новая 20-летняя стоимость = 109 096 000 долл. [а) 20-летняя стоимость= 101 340 000 долл. (б) Рнс. !9.9. а) Дерево после первой успешной Ь-замены. б) Локальный оптимум после )2 успешныя Л-замен.
дерева, которая существенно меньше, чем ))г), так как добавляются короткие ребра. Как можно догадаться, подпрограмма поиска начального реше. ния представляет собой эвристическую конструкцию, предназначенную для нахождения как можно лучшей исходной допустимой топологии, поскольку система окрестностей относи!тельно Л-замены не очень сильна.
На рис. 19.9 приведен реальный пример из Га. 19. Ловильный воиеи 478 Г«!ГКЗК!, показывающий первую успешную Л-замену, в результате которой 20-летняя стоимость уменьшается с 1!О 970 000 до 109 096 000 долл. На рис. 10.9(б) приведен локальный оптимум с 20-летней стоимостью 101 340 000 долл., полученный после !2 успецшых Л-замен. Потенциальная экономия в 9 630 000 долларов за 20 лет должна, по всей видимости, оправдать большую работу по разработке программы! 4 Р.5 Задача 4: равномерное разбиение графа (КЦ Рассмотрим теперь применение локального поиска к задаче, связанной с проведением соединений в схемах и сегментацией программ. Это приведет нас к описанию метода «переменной глубины» Лина и Кернигана П.К). Рассмотрим вначале простой вариант общей задачи.
Определение 19.4. Пусть дана симметричная матрица стоимостей [»!» 1, определенных на ребрах полного неориентированного графа Рис. !9.!О. Задача о равномерном раабиеиии рафа. 6=()е, Е) с 1'и'1=2п вершинами. Разбиение !»=-А () В называется равномерным, если 1А1=- 1В1. Задача о равномерном розбиеньш графа (РРГ) состоит в нахождении равномерного разбиения р'= =А 0 В, стоимость которого С (А, В) = ~~ »(ы »ад ~«В минимальна среди стоимостей всех равномерных разбиений. ! ) Эту задачу можно представить себе так, как показано на рис. !9.10: можно считать, что требуется разделить некоторую схему на два куска одинакового размера так, чтобы вес проводов, соединяющих эти два куска, был как можно меньше. Прежде чем определить систему окрестностей, сделаем простое замечание.
Пусть А*, В* — оптимальное равномерное разбиение, а мы рассматриваем некоторое разбиение А, В. Пусть К те эле- !9.5. Задача еа равномерное разбиение графа 479 менты из А, которые не входят в А" («неправильные» элементы), и пусть )г аналогично определяется для множества В. Тогда 1Х~= =1)'~ и А* А — Х) 1) 1', В*=( — )г) О Х. (19,2) Е (а) = У, с(еа ~е в (19,4) и внутреннюю стаи»гость ! (а) ~~ «1, ~ел (19,5) (аналогично сопоставим стоимости элементам множества В), Пусть 0(о) =Е1о) — /(о) (19.8) — разность между внешней и внутренней стоимостями для всех о е '»'. Лемма 19.1. Обмен элементами а и Ь приводит к уменьшению стоимости (выигрышу) на величину у(а, Ь) =0 (а)+О (Ь) — 2И„».
(19. 7) Доказательство. Перенесем а из А в В. Внутренняя стоимость элемента а становится внешней, и наоборот, поэтому стоимость уменьшается на Р(а). Новая внешняя стоимость элемента Ь равна Е (Ь) = Е(Ь) с(чь (19.8) и новая внутренняя стоимость элемента Ь равна (Ь) ~ (Ь)+с(чь (19.9) поэтому его новая разность равна 0' (Ь) =Е' (Ь) — 7'(Ь) = 0 (Ь) — 2«Ь, (19.
10) То есть оптимальное равномерное разбиение можно получить, обменивая элементы множества Х на элементы множества )л. Таким образом, нашу задачу в алгоритме локального поиска можно рассматривать в любой момент как задачу поиска последовательности выгодных обменов одним элементом.
Определение 19.5, Пусть даны равномерное разбиение А, В и элементы а ~ А и Ь ~ В, Тогда операция вида А' = (А — (а)) О (Ь), В' = ( — (Ь)) (1 (а) (19.3) называется обменом. Определим теперь эФфект, оказываемый некоторым обменом на стоимость разбиения А, В.
Сопоставим элементу аЕ А внешнюю стоимость Гл. 19. Локалькый коиск Если затем Ь перенести из В в А, то стоимость уменьшается на 0'(Ь), что вместе с Р(а) дает (19.7). Теперь можно очень естественно определить систему окрестностей, используя понятие обмена. Определение 19.6.
Окрестность относительно обмена Ф, для задачи РРГ определяется следующим образом: й),(А, В) =1все равномерные разбиения А', В', которые можно получить из равномерного разбиения А, В с помощью одного обмена). Поиск выгодного обмена можно произвести за время 0(п'), рассматривая выигрыш д(а,Ь) для всех пар аЕА, ЬЕВ. Если обмен действительно производится, то все значения 0 пересчитываются, и поиск продолжается. Керниган и Лин (К(.! сообщают, что локально оптимальные решения относительно Л', для 0-1-матриц расстояний размера 32х х32 примерно в !0%ь случаев оказываются глобально оптимальными и примерно в 75% случаев отлпчжотся от глобального оптимума на 1 или 2.
До сих пор все выглядит так же, как в предыдущих примерах, особенно в ЗК, поскольку нет особых трудностей с проверкой до. пустимости или вычислением стоимости. Можно было бы поддаться искушению исследовать окрестности, определяемые обменом двух элементов из А на два элемента из В, размер которых не превосходит 0(а'). Однако Керниган и Лин предлагают следующую интригующую идею, которая открывает новые возможности для широкого применения локального поиска. Их идея состоит в замене поиска одного выгодного обмена поиском выгодной последовательности обменов с использованием стоимостей из данной конкретной задачи в качестве руководства при поиске. При этом выгодная последовательность Ф обменов находится не рассмотрением окрестности, содержащей все такие последова.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
