§4. Приближенное решение задач комбинаторной оптимизации. Целью решения задачи комбинаторной оптимизации является
Задача комбинаторной оптимизации
Задача календарного планирования проекта с ограниченными ресурсами (ЗКППОР) рассматривает ресурсы с ограниченной доступностью и мероприятия с известными продолжительностью и потребностью в ресурсах, связанные отношениями предшествования. Задача состоит в нахождении графика выполнения проекта с минимальной продолжительностью путем назначения время начала каждому мероприятию так, чтобы отношения предшествования и ограничения по ресурсам были учтены. Более формально, ЗКППОР может быть определена как задача комбинаторной оптимизации. Задача комбинаторной оптимизации определяется на дискретном пространстве решений и задается подмножеством допустимых решений и целевой функцией . Цель задачи комбинаторной оптимизации состоит в поиске допустимого решения такого, что минимально или максимально. Задача календарного планирования проекта с ограниченными ресурсами – это задача комбинаторной оптимизации, задаваемая кортежем , компоненты которого описаны ниже.
Мероприятия, составляющие проект, задаются множеством . Мероприятие представляет начало графика, а мероприятие ‑ окончание графика. Множество нефиктивных мероприятий обозначено .
Продолжительности представлены вектором в , причем ‑ это продолжительность мероприятия , а .
Отношения предшествования задаются множеством пар таких, что означает, что мероприятие предшествует мероприятию . Строится орграф предшествования «мероприятие-вершина» , в котором вершины соответствуют мероприятиям, а дуги соответствуют отношению предшествования. При этом предполагается, что орграф бесконтурный, иначе отношение предшествования было бы несовместным. Возобновимые ресурсы заданы множеством .
Наличие ресурсов представлено вектором в , причем задает наличие ресурса . Ресурс , для которого , называется унарным или дизъюнктивным ресурсом. В противном случае, если ресурс может использоваться одновременно несколькими мероприятиями, он называется кумулятивным ресурсом.
Потребности мероприятий в ресурсах заданы (n+2)×q –мерной целочисленной матрицей , причем ‑ количество ресурса , используемого в каждый период времени в течение выполнения мероприятия .
Графиком проекта называется точка в , где ‑ время начала выполнения мероприятия . ‑ время завершения мероприятия , причем . ‑ начало проекта. Здесь предполагаем, что . Решение допустимо, если оно удовлетворяет ограничениям предшествования (9.19) и ограничениям по ресурсам (9.20), записанным ниже, причем представляет множество нефиктивных мероприятий в процессе в период .
(9.19)
(9.20)
Время выполнения проекта равно ‑ времени окончания проекта.
Определенное выше множество и ограничения задают, что мероприятие не может быть остановлено, коль уж оно началось. В этом случае говорят, что не разрешены преимущества. ЗКППОР может быть поставлена следующим образом:
Определение 9.1. ЗКППОР – это задача поиска графика без преимущества с минимальным временем выполнения , удовлетворяющего ограничениям предшествования(9.19) и ограничениям по ресурсам (9.20).
Похожие статьи:
poznayka.org
Комбинаторная оптимизационная задача - Большая Энциклопедия Нефти и Газа, статья, страница 1
Комбинаторная оптимизационная задача
Cтраница 1
Комбинаторные оптимизационные задачи, как правило, являются задачами большой размерности. Под размерностью понимаем размерность того комбинаторного пространства, в котором определена задача. Естественно, что количество ограничительных условий также влияет на время решения задачи: может увеличивать или уменьшать время счета. [1]
Комбинаторная оптимизационная задача состоит в отыскании среди конечного множества альтернатив одной, которой отвечает экстремальное значение принятой целевой функции. В самой простой модификации задачи обработки деталей конечное множество альтернатив включает ( n) h допустимых последовательностей обработки п деталей на k станках. [2]
Классическим примером комбинаторной оптимизационной задачи служит задача коммивояжера. Как показывает практика, наиболее эффективными в применении к ней являются алгоритмы, учитывающие ее комбинаторные свойства. Состоит она, как известно, в следующем. [3]
Приведены результаты исследований, касающиеся вопросов формализации комбинаторных оптимизационных задач и методов их решения, а также разработки и использования пакетов программ, ориентированных на решение задач из данной области. Представление комбинаторных оптимизационных задач как задач математического программирования в определенных комбинаторных пространствах позволило систематически изложить ряд новых методов, не охваченных известной монографической литературой. Рассмотрены также схемы основных известных методов, освещенных в литературе и достаточно хорошо зарекомендовавших себя на практике. [4]
Эти задачи составления расписаний попадают в категорию больших комбинаторных оптимизационных задач, многие из которых являются ЛГР-полными и считаются традиционно трудноразрешимыми. Главное внимание в этой главе было уделено получению при заданном количестве вычислительных ресурсов наиболее полезной информации, необходимой для осуществления упорядочения заданий либо в виде оптимального расписания ( когда это возможно), либо в виде расписания с обеспечением заданной точности относительно оптимального. [5]
Так же, как и идеальная, она является комбинаторной оптимизационной задачей. [6]
Таким образом, в настоящей книге речь идет об алгоритмах решения комбинаторных оптимизационных задач и их практическом применении с использованием ЭВМ. Рассматриваются алгоритмы как точные, так и приближенные. Точными алгоритмами на определенном множестве задач называем те алгоритмы, которые дают теоретическую гарантию получения глобального решения оптимизационной задачи из этого множества. Подмножеством приближенных алгоритмов являются алгоритмы, дающие локальное решение задачи. Основным понятием в таких алгоритмах служит понятие окрестности. [7]
Учитывая это, в предметной области пакетов целесообразно выделять из класса комбинаторных оптимизационных задач ряд подклассов, оптимизационный функционал которых определяется на одном из подпространств X. Это позволит при решении задач подкласса отсекать ряд заведомо недопустимых вариантов и тем самым значительно сократить вычислительную работу. [8]
Генетические алгоритмы входят в инструментарий DM & KDD как мощное средство решения комбинаторных и оптимизационных задач. В задачах извлечения знаний применение генетических алгоритмов сопряжено со сложностью оценки статистической значимости полученных решений и с трудностями построения критериев отбора удачных решений. Представителем пакетов из этой категории является GeneHunter фирмы Ward Systems Group. [9]
Мы можем разбить вычггслительные методы, предназначенные для составления расписаний ( или решения других комбинаторных оптимизационных задач), на классы в соответствии с тем, предназначены ли они для определения оптимального решения или только приближенного решения. [10]
В главе 8 содержатся основные данные о пакетах семейства ВЕКТОР, ориентированных на решение комбинаторных оптимизационных задач. Изложение иллюстрировано результатами численных экспериментов, проведенных посредством применения одного из пакетов данного семейства. Глава 9 содержит краткий обзор пакетов программ решения различных классов оптимизационных задач, которые разработаны в последние годы в Институте кибернетики АН УССР и в других организациях страны, тесно сотрудничающих с ним. [11]
Предварительное изучение и апробация МВС показали, что он достаточно универсален, дает хорошие численные результаты и успешно может быть применен как для решения задач размещения, так и для других типов комбинаторных оптимизационных задач. [12]
Понятие комбинаторной оптимизационной задачи разъясняется в первой главе. Здесь отметим только, что оно не противоречит ни интуитивному представлению, ни используемым в литературе понятиям. Существенной особенностью излагаемого материала является то, что он носит практический уклон и интерпретирован описанными в работе пакетами прикладных программ. [14]
Страницы: 1 2
www.ngpedia.ru
Лекция Задачи комбинаторной оптимизации. Алгоритмы и сложность Мотивационный пример
Дискретные задачи принятия решений
НГУ Механико – математический факультет 4 курс
Лектор: Кочетов Юрий Андреевич
http://www.math.nsc.ru/LBRT/k5/tpr.html
Лекция 1.
Задачи комбинаторной оптимизации.
Алгоритмы и сложность
Мотивационный пример
Компания планирует производство и продажу бандерснечей в условиях жесткой конкуренции.
Нужен метод для проверки возможности создания узлов бандерснеча с заданными техническими характеристиками.
Вы отвечаете за разработку алгоритмов.
Мрачная перспектива
Удобный выход
Но доказательство может оказаться слишком сложной задачей,
если это вообще можно доказать.Теория NP-полных задач дает методы доказательства того, что конкретная задача столь же трудна, как и ряд других задач, признанных очень трудными
Достойный выход
- Проверить NP–трудность (полноту) и постараться найти.
- Эффективные алгоритмы для частных случаев.
- Эффективные приближенные алгоритмы.
- Алгоритмы, работающие эффективно в среднем.
- Итерационные методы (метаэвристики), позволяющие в асимптотике находить точное решение задачи.
- Другие идеи, например, искать быстрые алгоритмы, гарантирующие выполнение бóльшей части ограничений задачи.
Под массовой задачей (или просто задачей ) будем понимать некоторый
общий вопрос, на который следует дать ответ:- Есть ли в задаче гамильтонов цикл?
- Существует ли в графе клика мощности не менее K?
- списком всех ее параметров;
- формулировкой свойств, которым должен удовлетворять отвеет
Алгоритмы
Под алгоритмом будем понимать общую, выполняемую шаг за шагом процедуру решения задачи. Для определенности можно считать ее программой на Си или другом языке.
Будем выделять
- точные алгоритмы, которые для любой индивидуальной задачи всегда дают точное решение;
- приближенные алгоритмы с гарантированной оценкой точности;
- аппроксимационные схемы — семейство алгоритмов, позволяющих получать решения с любой наперед заданной точностью > 0, время работы которых растет с ростом величины 1/ ;
- итерационные методы локального поиска (метаэвритстики), для которых вероятность получить точное решение растет с ростом числа итераций;
- быстрые конструктивные эвристики без гарантии получить точное решение или решение с заданной погрешностью.
Время работы алгоритма и требующуюся память выражают в виде функции от «размера» индивидуальной задачи, т. е. объема входных данных.
Входная длина (размер) индивидуальной задачи есть число символов, необходимых для кодирования ее исходных данных.Пример.
Для задачи коммивояжера требуется задать nn матрицу расстояний (cij).
При двоичном кодировании чисел длина входа (размер) не превышает величины .Полиномиальные алгоритмы
Будем говорить, что функция f(n) есть O(g(n)), если существует такая
константа c, что | f(n) | c | g(n) | для всех n 0.Полиномиальным алгоритмом (алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность равна O(p(n)), где p(n) — некоторая полиномиальная функция, а n — длина входа.
Алгоритмы, временная сложность которых не поддается подобной оценке, называются экспоненциальными.
Пример. O(n2) — полиномиальная сложность;
O(nlog n) — экспоненциальная сложность.
Сравнение полиномиальных и экспоненциальных
функций временной сложности
| Функция временной сложности | Размер n | |||||
| 10 | 20 | 30 | 40 | 50 | 60 | |
| n | 0,00001 сек. | 0,00002 сек. | 0,00003 сек. | 0,00004 сек. | 0,00005 сек. | 0,00006 сек. |
| n2 | 0,0001 сек. | 0,0004 сек. | 0,0009 сек. | 0,0016 сек. | 0,0025 сек. | 0,0036 сек. |
| n3 | 0,001 сек. | 0,008 сек. | 0,027 сек. | 0,064 сек. | 0,125 сек. | 0,216 сек. |
| n5 | 0,1 сек. | 3,2 сек. | 24,3 сек. | 1,7 мин. | 5,2 мин. | 13 мин. |
| 2n | 0,001 сек. | 1,0 сек. | 17,9 мин. | 12,7 дней | 35,7 лет | 366 столетий |
| 3n | 0,059 сек. | 58 мин. | 6,5 лет. | 3855 столетий | 2108столетий | 1,31013столетий |
| Функция временной сложности | На современных PC | На ЭВМ, в 100 раз более быстрых | На ЭВМ, в 1000 раз более быстрых |
| n | N1 | 100 N1 | 1000 N1 |
| n2 | N2 | 10 N2 | 31,6 N2 |
| n3 | N3 | 4,64 N3 | 10 N3 |
| n5 | N4 | 2,5 N4 | 3,98 N4 |
| 2n | N5 | N5 + 6,66 | N5 + 9,97 |
| 3n | N6 | N6 + 4,19 | N6 + 6,29 |
Сортировкой называют упорядочение множества объектов по неубыванию или невозрастанию какого-нибудь параметра.
- Алгоритм пузырька (волновой алгоритм) — O(n2).
- Алгоритм Фон–Неймана — O(n log n).
- Пирамидальный алгоритм — O(n log n).
- QuickSort и др.
Л aiaj ?
нет
да емма 1. Бинарное дерево высоты h содержит не более 2h листьев.
Дерево решений:
Лемма 2. Высота любого дерева решений, упорядочивающего последовательность из n различных элементов, не менее log n!.
Доказательство. Так как результатом может быть любая из n! перестановок, то в дереве решений должно быть не менее n! листьев. Тогда по лемме 1 высота дерева не меньше log n!. ∎
Теорема. В любом алгоритме, упорядочивающем с помощью сравнений, на упорядочивание последовательность из n элементов тратится не менее c n log n сравнений при некотором c >0 и достаточно большом n.
Доказательство. При n ≥ 4 имеем
n! ≥ n(n – 1) (n – 2)…( ) ≥ ,
тогда
log n! ≥ () log () ≥ () log n. ∎Алгоритм Фон–Неймана
На вход подается последовательность чисел a(1),…, a(n). Алгоритм работает log2 n итераций. Перед началом итерации с номером k (k = 1, 2, …, log2 n) имеется последовательность a(i (1)), …, a(i (n)) тех же чисел, разбитая на группы по 2k–1 элементов (последняя группа может быть неполной). Внутри каждой группы элементы упорядочены по неубыванию. Итерация состоит в том, что эти группы разбиваются на пары соседних групп, и элементы упорядочиваются внутри этих новых в два раза больших групп. При этом используется то, что внутри исходных групп элементы уже упорядочены.
| слияние за линейное время O(m) |
Пирамидальный алгоритм
Два этапа:
- пa1остроение пирамиды: для каждого i
ai и
- сa4ортировка массива с помощью пирамиды
a2i+1
a8
Первый этап
(
ai i, n)–операция состоит в следующем:Сравниваем a2i и a2i+1,
пa2i
a2i+1усть x — меньшее из них.
Если ai > x, то меняем местами ai и x.
(j, n)–процедура: выполняем (j, n)–операцию; если aj переместилось вниз, скажем, стало a2j+1, то производим (2j +1, n)–операцию и т.д., пока наш элемент aj не остановится.
Первый этап состоит в последовательном выполнении (j, n)–процедуры для j =n/2, n/2 – 1,…, 1.
Упражнение. Доказать, что первый этап требует не более 2n (i, n)–операций.
Второй этап
Нan–j+1
a1а j-й итерации (j – 1) самых малых чисел уже найдены и лежат на «полочке» в нужном порядке. Остальные находятся в пирамиде (ai ≤ min(a2i, a2i +1)). Итерация состоит в том, что элемент a1 из пирамиды кладется на «полку», а на его место ставится элемент an – j +1 из пирамиды и выполняется (1, n–j)–процедура.
После выполнения n-й итерации все числа лежат на полке в полном порядке.
Время — O(n log n).
Замечание. «Полку» можно организовать прямо в пирамиде.
Сбалансированные деревья
Для массива данных требуется
- Найти элемент
- Найти k-й по порядку элемент
- Вставить элемент
- Удалить элемент
Если хранить данные в виде списка, то 3, 4 — O(log n), 1, 2 — O(n).
Сбалансированные деревья требуют O(log n) для 1 – 4.
Определение 1. Высотой дерева называется максимальная длина пути от корня до листа.
Определение 2. Бинарное дерево называется сбалансированным (или AVL–деревом), если для любой его вершины высота правого поддерева отличается от высоты левого поддерева не более чем на единицу.
Теорема. Длина ветвей в n-вершинном сбалансированном дереве заключена между log2n и log2n.
Доказательство.
- Бинарное дерево высоты h не может содержать больше 2h +1вершины, то есть n ≤ 2h + 1 или h + 1 ≥ log2 n.
- Наиболее ассиметричное AVL–дерево Th высоты h имеет наиболее ассиметричное AVL–дерево Th –1 высоты h–1 в качестве одного из своих поддеревьев и наиболее ассиметричное AVL–дерево Th –2 в качестве другого. Обозначим через n(h) число вершин в дереве Th. Тогда
Для h=3,4 можно непосредственно проверить, а затем по индукции доказать, что n(h)> h+1, где = .
Следовательно, n ≥ n(h) > h+1, откуда h+1 ≤ log n / log ≈ 1,44 log n. ∎
Пусть в вершинах AVL–дерева расположены элементы массива так, что для любой вершины в левом ее поддереве расположены элементы не больше чем в данной вершине, а в правом поддереве — не меньше, чем в этой вершине.
ai
aj≥ ai
aj≤ai
Пример. Поиск в AVL–дереве потребует более 25 сравнений, только если дерево состоит из не менее 196 417 вершин.
Случайные деревья
Для сбалансированного дерева длина пути из корня в лист не превышает 1,44 log n.
Для случайного дерева средняя длина пути из корня в лист составляет 1,39 log n, но в худшем случае может оказаться равной n.
Для сбалансированного дерева средняя длина пути составляет c log n,
c ≈1,04.Включение новой вершины в AVL–дерево
При добавлении новой вершины vnew к AVL–дереву мы «скатываем» ее от корня вдоль веток и получаем новый лист (висячую вершину).
Дерево остается бинарным, но баланс может нарушиться. Эти нарушения могут возникнуть только у вершин, лежащих на пути от корня к новой вершине.Будем последовательно подниматься от новой вершины к корню и восстанавливать баланс, если это необходимо.
Пусть v — самая нижняя вершина дисбаланса, то есть наиболее удаленная от корня вершина такая, что ее поддерево с вершиной vnew имеет высоту k+2, а другое поддерево — высоту k:
Будем восстанавливать баланс в v следующим образом. Если первые два шага на (единственном пути) от v к vnew делаются в одном направлении (оба вправо, или оба влево), то применяем правило простого вращения (ППВ).
Если первые два шага делаются в разных направлениях, то
применяем правило двойного вращения (ПДВ):Удаление вершины
На место удаленной вершины v ставим либо самую правую вершину vrL левого поддерева, либо самую левую вершину vLr правого поддерева
Нюанс. Каждая из вершин vrL и vLr может быть либо висячей, либо предвесячей, то есть имеющей в качестве потомков лишь одну вершину (разумеется, висячую):
Если на место удаленной вершины встает предвисячая вершина y, то ее (вершины y) потомок x подключается к ее предку z:
Итак, можно считать, что всегда удаляем лист. Последовательно поднимаемся от удаленной вершины v к корню и исправляем структуру дерева, если необходимо.
Пусть к текущей вершине x на пути от v к корню мы пришли справа по короткой ветке. Тогда возможно три случая:
а) В вершине y высоты поддеревьев равны:
б) В вершине y высота левого поддерева больше высоты правого поддерева:
в) В вершине y высота левого поддерева меньше высоты правого поддерева
Отметим, что устранение дисбаланса в одной из вершин, может нарушить баланс в вышестоящих вершинах. На рисунке показан предельный случай этого явления. При начальном дисбалансе лишь в одной вершине (лежащей непосредственно под v) приходится, тем не менее, производить перестройку дерева во всех вершинах на пути к корню.
Пример. Построить последовательность AVL–деревьев для данных, поступающих в следующем порядке: 29, 19, 9, 1, 4, 14, 39, 18, 36, 24, 15, 12.
Удалить из полученного дерева 24, а затем 19.
Упражнение. Построить последовательность AVL–деревьев для данных, поступающих в следующем порядке: 15, 7, 17, 5, 4, 3, 56, 23, 22, 6, 10, 25, 26.
Удалить из полученного дерева 6 и 10, а затем 15 и 25.
страница 1
Смотрите также:
Лекция Задачи комбинаторной оптимизации. Алгоритмы и сложность Мотивационный пример 155.33kb. 1 стр.
Программа курса «Теория вероятностей» 35.46kb. 1 стр.
Задача для уравнений Навье-Стокса, описывающих движение вязкой несжимаемой жидкости, как базовый пример численного решения задачи. Вопросы существования и единственности в дифференциальном случае 42.96kb. 1 стр.
moglobi.ru
Формулировка в виде задачи дискретной оптимизации — МегаЛекции
Содержание
Введение
Задача о коммивояжере. Определение. История.
Метод полного перебора
Решение задачи коммивояжера при помощи надстройки MS Excel «Поиск решения»
Метод полного перебора
Заключение
Список литературы
Введение
Задача коммивояжера, известная также как задача о сверлильном станке или алгоритм коммивояжера была поставлена в 1934 году. Эта задача является одной из знаменитых задач теории комбинаторики и широко применяется при разработке программного обеспечения.
Целью данной курсовой работы является постановка задачи коммивояжера и ее решение методом полного перебора с использованием надстройки MS Excel «Поиск решения».
Объектом исследования в курсовой работе выступает программа, реализующая один из методов решения задачи коммивояжера - надстройка MS Excel «Поиск решения».
Предмет курсовой работы – сущность задачи коммивояжера, порядок и методы ее решения.
Для достижения поставленной цели необходимо решить следующие задачи:
ü изучить понятие и особенности задачи коммивояжера;
ü ознакомиться с практическим применением задачи коммивояжера;
ü рассмотреть методы решения задачи коммивояжера;
ü получить представление о назначении надстройки MS Excel «Поиск решения»;
ü сформулировать задачу коммивояжера и решить ее при помощи надстройки MS Excel «Поиск решения».
ЗАДАЧА О КОММИВАЯЖОРЕ.ОПРЕДЕЛЕНИЕ. ИСТОРИЯ
Определение
Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр — разъездной сбытовой посредник) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.
Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра.
Общая постановка задачи, впрочем как и большинство её частных случаев, относится к классу NP-полных задач. Задача коммивояжёра относится к числу трансвычислительных: уже при относительно небольшом числе городов (66 и более) она не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет
История
Точно неизвестно, когда проблему коммивояжера исследовали впервые. Однако, известна изданная в 1832 году книга с названием «Коммивояжер — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера» (нем. Der Handlungsreisende – wie er sein soll und was er zu thun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur), в которой описана проблема, но математический аппарат для ее решения не применяется. Зато в ней предложены примеры маршрутов для некоторых регионов Германии и Швейцарии.
Ранним вариантом задачи может рассматриваться англ. Icosian Game Уильяма Гамильтона 19 века, которая заключалась в том, чтобы найти маршруты на графе с 20 узлами. Первые упоминания в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру (нем. Karl Menger), который сформулировал ее на математическом коллоквиуме в 1930 году так: Мы называем проблемой посыльного (поскольку этот вопрос возникает у каждого почтальона, в частности, ее решают многие путешественники) задачу найти кратчайший путь между конечным множеством мест, расстояние между которыми известно.
Вскоре появилось известное сейчас название задача странствующего продавца (англ. Traveling Salesman Problem), которую предложил Гаслер Уитни (англ. Hassler Whitney) из Принстонского университета.
Вместе с простотой определения и сравнительной простотой нахождения хороших решений задача коммивояжера отличается тем, что нахождение действительно оптимального пути является достаточно сложной задачей. Учитывая эти свойства, начиная со второй половины 20-го века, исследование задачи коммивояжера имеет не столько практический смысл, сколько теоретический в качестве модели для разработки новых алгоритмов оптимизации.
Многие современные распространенные методы дискретной оптимизации, такие как метод деления плоскостью, ветвей и границ и различные варианты эвристических алгоритмов, были разработаны на примере задачи коммивояжера.
В 1950-е и 1960-е годы задача коммивояжера привлекла внимание ученых в США и Европе. Важный вклад в исследование задачи принадлежит Джорджу Данцигу, Делберту Рею Фалкерсону (англ. Delbert Ray Fulkerson) и Селмеру Джонсону (англ. Selmer M. Johnson), которые в 1954 году в институте RAND Corportation сформулировали задачу в виде задачи дискретной оптимизации и разработали метод деления плоскостью для ее решения. Используя новый метод, они вычислили путь для отдельного набора узлов с 49 городами и доказали, что не существует короткого пути. В 1960-е и 1970-е годы многочисленные группы исследователей изучали задачу с точки зрения математики и ее применения, например, в информатике, экономике, химии и биологии.
Ричард Карп в 1972 году доказал NP-полноту задачи поиска гамильтоновых путей, из чего, благодаря полиномиальной сводимости, вытекала NP-полнота задачи коммивояжера. На основе этих свойств им было приведено теоретическое обоснование сложности поиска решений задачи на практике.
Больших успехов удалось достичь в конце 1970-х и 1980-х годах, когда Мартин Грётчел (нем. Martin Grötschel), Манфред Падберг (нем. Manfred Padberg) и Гиованни Ринальди (нем. Giovanni Rinaldi) и другие, с применением новых методов деления плоскостью, ветвей и границ вычислили решение для отдельного случая задачи с 2393 городами.
В 1990-е годы Дэвид Аплгейт (англ. David Applegate), Роберт Биксби (англ. Robert Bixby), Вашека Шватал (англ. Vašek Chvátal) и Уильям Кук (англ. William Cook) установили рекорды по программе Конкорд. Герхард Райнельт (нем. Gerhard Reinelt) создал TSPLIB — набор стандартизованных экземпляров задачи коммивояжера различной степени сложности для сравнения результатов работы различных групп исследователей. В марте 2005 года задача с 33 810 узлами была решена программой Конкорд: был вычислен путь длиной в 66 048 945 и доказано отсутствие коротких путей. В апреле 2006 было найдено решение для экземпляра с 85 900 узлами. Используя методы декомпозиции, можно вычислить решения для случаев задачи с миллионами узлов, длина которых менее чем на 1 % больше оптимальной.
Формулировка в виде задачи дискретной оптимизации
Одним из подходом к решению задачи является формулировка ее в виде задачи дискретной оптимизации, при этом решения представляются в виде переменных, а связи — в виде отношений неравенства между ними. Таким образом, возможно несколько вариантов. Например, симметричную задачу можно представить в виде множества ребер V. Каждому ребру {i,j} сопоставляется двоичная переменная , равная 1, если ребро принадлежит маршруту, и 0 — в противном случае. Произвольный маршрут можно представить в виде значений множества переменных принадлежности, но не каждое такое множество определяет маршрут. Условием того, что значения множества переменных определяют маршрут, являются описанные далее линейные неравенства.
Условие кратности: каждая вершина должна иметь одно входное и одно выходное ребро маршрута.
В сумме каждое слагаемое xij равно или 1 (принадлежит маршруту) или 0 (не принадлежит). То есть, полученная сумма равна количеству ребер в маршруте, имеющих вершину i на одном из концов. Она равна 2, так как каждая вершина имеет входное и выходное ребро. В приведенном рядом рисунке вершина i показана с входным и выходными ребрами, а ребра маршрута обозначены толстыми линиями. Рядом с ребрами указаны длины xij, прилагаемые к указанной выше сумме.
Алгоритмическая сложность
Поскольку коммивояжер в каждом из городов встает перед выбором следующего города из тех, что он еще не посетил, существует (n − 1)! маршрутов для асимметричной и (n − 1)! / 2 маршрутов для симметричной задачи коммивояжера. Таким образом, размер пространства поиска зависит экспоненциально от количества городов.
Различные варианты задачи коммивояжера (метрическая, симметричная и асимметричная) NP-эквивалентны. Согласно распространенной, но недоказанной гипотезе о неравенстве классов сложности P и NP, не существует детерминированной машины Тьюринга, способной находить решения экземпляров задачи за полиномиальное время в зависимости от количества городов.
Также известно, что при условии не существует алгоритма, который для некоторого полинома p вычислял бы такие решения задачи коммивояжера, которые отличались бы от оптимального максимум на коэффициент 2p(n).
Однако, существуют алгоритмы поиска приближенных решений для метрической задачи за полиномиальное время и нахождения маршрута максимум вдвое длиннее оптимального. До сих пор не известен ни один алгоритм с полиномиальным временем, который бы гарантировал точность, лучшую чем 1,5 от оптимальной. По предположению , существует (неизвестная) константа c > 0, такая, что ни один алгоритм с полиномиальным временем не может гарантировать точность 1 + c. Как было показано Арора, для евклидовой задачи коммивояжёра существует схема поиска приблизительных решений задачи (PTAS).
Замкнутый и незамкнутый варианты задачи
В замкнутом варианте задачи коммивояжёра требуется посетить все вершины графа, после чего вернуться в исходную вершину. Незамкнутый вариант отличается от замкнутого тем, что в нём не требуется возвращаться в стартовую вершину.
Незамкнутый вариант задачи сводится к замкнутому путём замены весов дуг, входящих в стартовую вершину, на число 0. Оптимальный замкнутый маршрут коммивояжёра в таком графе соответствует оптимальному незамкнутому маршруту в исходном графе.
Чтобы свести замкнутый вариант к незамкнутому, нужно определить число K, строго превосходящее вес любого маршрута коммивояжёра в заданном графе (например, в качестве K можно взять сумму максимальных по весу дуг, выходящих из каждой вершины, увеличенную на 1). Затем нужно добавить к графу новую вершину vn (предполагаем, что вершины исходного графа пронумерованы числами от 0 до n − 1, при этом стартовая вершина имеет номер 0). Стоимости дуг, выходящих и входящих в вершину vn, определяются следующим образом:
cn,i = 3K
c0,n = 3K
ci,n = ci,0 + 2K при i от 1 до n − 1
Оптимальный незамкнутый маршрут коммивояжёра в таком графе соответствует оптимальному замкнутому маршруту коммивояжёра в исходном графе и имеет стоимость на 2K больше.
Рекомендуемые страницы:
Воспользуйтесь поиском по сайту:
megalektsii.ru
§4. Приближенное решение задач комбинаторной оптимизации : Основы оптимизации : Экономико-правовая библиотека
Определение задачи комбинаторной оптимизации и приближенного алгоритма ее решения. Утверждение о разнице между приближенным и точным оптимумом для задачи о рюкзаке. Определение е-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС). Связь между существованием ПППС и псевдополиномиальностью. Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания свойств. Пример задачи о коммивояжере.
Важный класс массовых задач образуют задачи дискретной (комбинаторной) оптимизации. Для оптимизационной постановки задачи П решением каждой индивидуальной задачи 1£П является произвольная реализация оптимума
Optn (Г) = max /п (I, z),
ze£n(I)
т.е. такая точка z*(T) £ 5п(1), для которой /п(1, z*(T)) — Optjj(T). Здесь s'n(I) — область допустимых значений дискретной (целочисленной) переменной z, /п(1, ■) : 5п(1) —► Z — целевая функция индивидуальной задачи I оптимизации, знак max в постановке задачи может быть заменен на min.
Будем обозначать и <ту те компоненты входного слова <т = е(1), определяющего параметры индивидуальной задачи I £ П, которые задают допустимую область (ограничения задачи) и функцию цели соответственно. Например, для ЗР имеем /зр("", z) — (c,z), £зр(о-) - {z - (z1>...,zn)\zj £ {0,1} Vj = l,n и (w,z) < К}, <ts — (n, w, К) и (Tf — с. Здесь и далее знак (■, ■) обозначает скалярное произведение векторов.
Определение 10. Алгоритм А называется приближенным алгоритмом решения массовой задачи П оптимизации, если VI Є П он находит некоторую точку из допустимой области zA(T) Є 5гі(І)! принимаемую за приближенное решение. Значение /п(1, -^a(I)) называется приближенным значением оптимума и обозначается А(Т).
Говорить об абсолютной погрешности приближенного алгоритма решения массовой задачи оптимизации (на классе всевозможных индивидуальных задач) не имеет большого смысла, как показывает
Утверждение 11. Если Р ф NP, то ни для какой константы С > 0 не существует полиномиального приближенного алгоритма А решения ЗР с оценкой \0pt3P(I) - А(Т)\ < С VI Є ЗР.
Доказательство проведем от противного. Пусть найдены такие С и А. Построим алгоритм А' следующим образом: VI Є ЗР домножим все коэффициенты Cj на С + 1 — получим индивидуальную задачу І' Є ЗР, к которой применим алгоритм А и разделим полученный ответ на С + 1, т.е. А'(Т) — А(І')/(С + 1). Очевидно, Орізр(І') = (С + І)Орізр(І) и из полиномиальности алгоритма А вытекает полиномиальность А'. При этом его точность равна |0р*зр(1) - А'(Т)\ = |0р*зр(1') - А(І')\/(С + 1) < С/{С + 1) < 1, т.е. равна нулю (так как все значения целевой функции целые). Получили полиномиальный алгоритм точного решения ЗР. Проверка Орізр(І) > В полиномиальна, значит, построили и полиномиальный алгоритм решения ЗР в постановке распознавания свойств, что с учетом универсальности последней противоречит утверждению 6.
Определение 11. Приближенный алгоритм А решения массовой задачи П оптимизации называется є-приближенным алгоритмом решения П для некоторого є > 0, если
VIen KW)-A(I)|
\Optn(T)\ <£'
т.е. его относительная погрешность не превосходит Є.
Для е-приближенных алгоритмов приведем следующий результат [2, с. 439], доказательство которого основано на методе динамического программирования и в данном курсе опускается.
Теорема 5. Пусть для задачи П оптимизации
1) существует псевдополиномиальный алгоритм ее решения;
2) VIen \Optn(I)\ < Pl(|I|,num(I)) и num(I) < p2(\I\, Optn(I))
23для некоторых полиномов р\(-, ■), рг(-, ■)',
3) V<т — е(1), I Е П: параметры ег?, задающие ограничения, и <т/, задающие целевую функцию, не пересекаются, иУгб ^пС"") функция цели /п(о", -г) линейно зависит от параметров <ту;
тогда Зр(-, ■) — полином: \/е > 0 3 е-приближенный алгоритм А£ решения П с временной сложностью 7ае(|1|) < р(|1|, 1/е).
Теорема 5 справедлива, например, для ЗР (сравните результат с утверждением 11). Набор алгоритмов {А£}, определенный в теореме 5, называется полностью полиномиальной приближенной схемой (ПППС) решения задачи П оптимизации. Наличие ПППС — лучшее, чего можно ожидать при решении КР-трудных задач. К сожалению, в целом ряде случаев на это нельзя рассчитывать, так как имеется
Теорема 6. Если для П оптимизации соответствующая ей П распознавания свойств является сильно КР-полной и Зр'(-) — полином: |Ор£п(1)| < р'(пит(1)) VI Е П, то при условии, что Р ф КР, для П не существует ПППС.
Доказательство проведем от противного. Пусть ПППС существует. Построим алгоритм А' следующим образом. Для любой индивидуальной задачи I А' вызывает А£ с е — 1/(р' (пит(1))-|-1). Тогда по определению е-приближенного алгоритма А£ |0р^п(1) — А'(1)| < |Ор*п(1)|/(р'(шпп(1)) + 1) < р'(пшп(1))/(р'(пшп(1)) + 1) по условию теоремы. Но в левой части полученного неравенства было целое число, которое оказывается равным нулю как неотрицательное, меньшее 1. Таким образом, алгоритм А' точен, причем Та/(|1|) = Тае(|1|) < р(|1|,р'(пшп(1)) + 1) по определению ПППС. Следовательно, алгоритм А' псевдополиномиален, что противоречит теореме 4.
Утверждение 12. Если Р ф КР, то ни для какого е > 0 не существует полиномиального е-приближенного алгоритма решения оптимизационной постановки задачи коммивояжера.
Доказательство см. в [2, с. 440-441].
Для частного случая КМ, в котором функция с?(-, ■) расстояния между городами удовлетворяет неравенству треугольника, известен 0.5-приближенный полиномиальный алгоритм Кристофидеса [2, с. 429-432] (решения КМ оптимизации).
24
www.vuzllib.su
§4. Приближенное решение задач комбинаторной оптимизации : Основы оптимизации : Экономико-правовая библиотека
Определение задачи комбинаторной оптимизации и приближенного алгоритма ее решения. Утверждение о разнице между приближенным и точным оптимумом для задачи о рюкзаке. Определение є-приближенного алгоритма и полностью полиномиальной приближенной схемы (ПППС). Связь между существованием ПППС и псевдополиномиальностью. Теорема об отсутствии ПППС для задач оптимизации, соответствующих сильно NP-полным задачам распознавания свойств. Пример задачи о коммивояжере.
Важный класс массовых задач образуют задачи дискретной (комбинаторной) оптимизации. Для оптимизационной постановки задачи П решением каждой индивидуальной задачи ІЄП является произвольная реализация оптимума
Optn (Г) = max /п (I, z),
т.е. такая точка z*(T) Є 5п(І), Для которой /п(1, z*(I)) = Optjj(T). Здесь S'n(I) — область допустимых значений дискретной (целочисленной) переменной z, /п(1, ■) : 5п(1) —► Z — целевая функция индивидуальной задачи I оптимизации, знак max в постановке задачи может быть заменен на min.
Будем обозначать сг^- и <ту те компоненты входного слова сг = е(1), определяющего параметры индивидуальной задачи І Є П, которые задают допустимую область (ограничения задачи) и функцию цели соответственно. Например, для ЗР имеем /зр("", z) — (c,z), 5"зр(сг) - {z - (z1>...,zn)\zj Є {0,1} Vj = l,n и (w,z) < K}, (TS — (n, w, К) и (Tf — с. Здесь и далее знак (■, ■) обозначает скалярное произведение векторов.
Определение 10. Алгоритм А называется приближенным алгоритмом решения массовой задачи П оптимизации, если VI Є П он находит некоторую точку из допустимой области гА(Т) Є 5гі(І)! принимаемую за приближенное решение. Значение /п(1, -^a(I)) называется приближенным значением оптимума и обозначается А(Т).
Говорить об абсолютной погрешности приближенного алгоритма решения массовой задачи оптимизации (на классе всевозможных индивидуальных задач) не имеет большого смысла, как показывает
Утверждение 11. Если Р ф NP, то ни для какой константы С > 0 не существует полиномиального приближенного алгоритма А решения ЗР с оценкой \0pt3P(I) - А(Т)\ < С VI Є ЗР.
Доказательство проведем от противного. Пусть найдены такие С и А. Построим алгоритм А' следующим образом: VI Є ЗР домножим все коэффициенты Cj на С + 1 — получим индивидуальную задачу І' Є ЗР, к которой применим алгоритм А и разделим полученный ответ на С + 1, т.е. А'(Т) — А(І')/(С + 1). Очевидно, Орізр(І') — (С + І)Орізр(І) и из полиномиальности алгоритма А вытекает полиномиальность А'. При этом его точность равна |0р*ЗР(1) - А'(Т)\ = |0р*ЗР(1') - А(І')\/(С + 1) < С/{С + 1) < 1, т.е. равна нулю (так как все значения целевой функции целые). Получили полиномиальный алгоритм точного решения ЗР. Проверка Орізр(І) > В полиномиальна, значит, построили и полиномиальный алгоритм решения ЗР в постановке распознавания свойств, что с учетом универсальности последней противоречит утверждению 6.
Определение 11. Приближенный алгоритм А решения массовой задачи П оптимизации называется є-приближенным алгоритмом решения П для некоторого є > 0, если
VIen KW)-A(I)|
\Optn(T)\ <£'
т.е. его относительная погрешность не превосходит Є.
Для е-приближенных алгоритмов приведем следующий результат [2, с. 439], доказательство которого основано на методе динамического программирования и в данном курсе опускается.
Теорема 5. Пусть для задачи П оптимизации
1) существует псевдополиномиальный алгоритм ее решения;
2) VIen \Optn(I)\ < Pl(|I|,num(I)) и num(I) < p2(\I\, Optn(I))
для некоторых полиномов pi(-, ■), P2G, ■)',
3) Vcr = е(і), і Є п: параметры its, задающие ограничения, и <Tf, задающие целевую функцию, не пересекаются, и \/z Є Sn(cr) функция цели /n(f, -г) линейно зависит от параметров ;
тогда Зр(-, ■) — полином: Ve > 0 3 е-приближенный алгоритм А£ решения п с временной сложностью 7ає(|і|) < р(|і|, 1/е).
Теорема 5 справедлива, например, для ЗР (сравните результат с утверждением 11). Набор алгоритмов {А£}, определенный в теореме 5, называется полностью полиномиальной приближенной схемой (ПППС) решения задачи п оптимизации. Наличие ПППС — лучшее, чего можно ожидать при решении NP-трудных задач. К сожалению, в целом ряде случаев на это нельзя рассчитывать, так как имеется
Теорема 6. Если для п оптимизации соответствующая ей п распознавания свойств является сильно NP-полной и Зр'(-) — полином: |Оріп(і)| < p'(num(I)) VI Є п, то при условии, что Р ф NP, для п не существует ПППС.
Доказательство проведем от противного. Пусть ПППС существует. Построим алгоритм А' следующим образом. Для любой индивидуальной задачи I А' вызывает А£ с є — 1/(р' (пит(1))+1). Тогда по определению е-приближенного алгоритма А£ \Optjj(T) — A'(I)| < |Opin(I)|/(p'(num(I)) + 1) < p'(mim(I))/(p'(mim(I)) + 1) по условию теоремы. Но в левой части полученного неравенства было целое число, которое оказывается равным нулю как неотрицательное, меньшее 1. Таким образом, алгоритм А' точен, причем TA/(|I|) = TAe(|I|) < p(|I|,p'(num(I)) + 1) по определению ПППС. Следовательно, алгоритм А' псевдополиномиален, что противоречит теореме 4.
Утверждение 12. Если Р ф NP, то ни для какого є > 0 не существует полиномиального е-приближенного алгоритма решения оптимизационной постановки задачи коммивояжера.
Доказательство см. в [2, с. 440-441].
Для частного случая КМ, в котором функция d(-, ■) расстояния между городами удовлетворяет неравенству треугольника, известен 0.5-приближенный полиномиальный алгоритм Кристофидеса [2, с. 429-432] (решения КМ оптимизации).
www.vuzllib.su
Приближенные и эвристические методы решения задач комбинаторной оптимизации
Методы перебора и все их усовершенствования имеют один, но очень серьезный недостаток: время работы, экспоненциально растущее при увеличении размерности задачи. Для решения практических задач это часто бывает неприемлемо. За редкими исключениями, эффективными можно считать только алгоритмы, имеющие не более чем полиномиальные оценки трудоемкости. Ясно, что такие алгоритмы не могут сводиться к полному перебору планов (ввиду того, что количество планов растет экспоненциально). Других же подходов, пригодных сразу для всех задач комбинаторного поиска, не имеется. Значит, можно надеяться только на алгоритмы, учитывающие специфику конкретных задач.
Исследования в области методов дискретной оптимизации позволили найти некоторое количество задач, для которых действительно существуют эффективные (т.е. полиномиальные с невысокой степенью полинома) алгоритмы решения. К ним относятся, например, такие задачи, как отыскание кратчайшего пути между вершинами графа, максимизация потока в сети при заданной пропускной способности ребер и др. Однако для большей части задач, возникающих на практике, неизвестны эффективные алгоритмы точного решения. Поскольку решать задачи все равно надо, а на перебор надежда плохая, очень часто приходится жертвовать точностью определения экстремума ради сокращения времени его определения. Вместо строгого доказательства того, что полученный план будет давать точный минимум или максимум целевой функции, приходится опираться на соображения здравого смысла, которые позволяют считать, что полученный план с достаточно большой вероятностью либо оптимален, либо хотя бы близок к оптимальному. Конечно, это неприятно, ибо противоречит неуемной тяге человеческого духа к совершенству. Но с другой стороны, много ли вещей мы в жизни делаем оптимальным образом? И ничего, живем.
Относительно более приятна ситуация, когда точно известна хотя бы степень возможной неоптимальности. Алгоритмы оптимизации, для которых имеются нетривиальные оценки возможного отклонения решения от оптимума, называются приближенными или субоптимальными.
Хороший пример приближенного алгоритма известен для задачи о многопроцессорном расписании (см. п.1.3.5). Алгоритм прост донельзя: нужно лишь упорядочить задачи по убыванию их длительности, а затем каждую следующую задачу назначать на наименее загруженный процессор. Оказывается, что отношение времени выполнения набора задач, получаемого по этому алгоритму (T), к минимально возможному времени выполнения, которое можно найти в результате перебора (T0), всегда удовлетворяет неравенству: T/T0 £ 4/3 – 1/3n. Например, при n=3 из этого получается оценка: T0 ³ 9/11×T. Если, к примеру, по данному алгоритму получилось время выполнения 220с, то нет гарантии, что это наилучшее возможное распределение, однако можно быть уверенным, что минимальное возможное время не может быть меньше 180с.
К сожалению, далеко не во всех случаях можно подобным образом оценить погрешность. Вполне типична ситуация, когда используемый алгоритм дает достаточно приличные решения, однако нет никаких гарантий, что эти решения всегда близки к оптимальным. Алгоритмы, основанные на нестрогих соображениях «здравого смысла» и не имеющие никаких гарантий близости к оптимальным, называются эвристическими алгоритмами. Некоторые авторы, правда, вообще отказывают им в праве называться алгоритмами (поскольку под сомнением такое важное свойство любого алгоритма, как результативность) и используют вместо этого термин «эвристики».
Не существует универсальных рецептов построения эвристических алгоритмов для любых задач. В то же время имеется несколько хорошо зарекомендовавших себя подходов, которые оказываются полезными для разных типов задач.
Алгоритмы локальной пошаговой оптимизации основываются на следующих соображениях. В большинстве комбинаторных задач построение плана можно организовать как пошаговый процесс. Например, на каждом шаге решения может определяться значение очередной переменной. К сожалению, в большинстве случаев трудно сказать, какое решение нужно принять на очередном шаге, чтобы в конце концов придти к оптимальному плану задачи. Зато очень часто бывает легко выбрать решение, которое выглядит наилучшим для данного шага, без учета отдаленных последствий.
Простейшим видом алгоритмов локальной пошаговой оптимизации являются алгоритмы последовательного выбора.
Рассмотрим в качестве примера задачу о коммивояжере. Произвольно выберем начальный город и зададимся вопросом, в какой город следует ехать в первую очередь. Очевидный ответ – в ближайший. На втором шаге и на последующих шагах по той же логике следует выбирать ближайший из еще не посещенных городов. Конечно, такой алгоритм не гарантирует оптимальность построенного плана, ибо не исключено, что выигрыш на первых шагах приведет к большим потерям на последующих (можно и вообще заехать в тупик, откуда нет дороги). Однако можно аккуратными вероятностными рассуждениями подтвердить и без того очевидный факт: при выборе на каждом шаге ближайшего города ожидаемая длина всего маршрута будет меньше, чем при любом другом выборе.
Для задачи о рюкзаке можно предложить такой алгоритм последовательного выбора: отсортировать товары по убыванию отношения стоимости единицы товара к ее объему, а затем на каждом шаге брать максимальное количество очередного товара, умещающееся в оставшемся объеме.
Можно улучшить качество работы алгоритмов последовательного выбора, если разрешить ограниченный перебор, т.е. выбирать решение на данном шаге, учитывая результаты двух, трех или более шагов. Например, перебрать все варианты двух первых поездок коммивояжера, выбрать из них тот вариант, который имеет минимальную длину, и на основании этого выбора сделать первый шаг. Затем так же перебрать варианты второго и третьего шагов, сделать второй шаг и т.д. Если число перебираемых шагов ограничено, то алгоритм, хотя и будет работать значительно медленнее, все же сохранит полиномиальную сложность. Конечно, в силу ограниченности глубины перебора получение оптимального плана не гарантируется. Не гарантируется даже, что при увеличении глубины перебора качество полученных планов будет всегда возрастать, можно только надеяться на это.
Другим типом алгоритмов локальной пошаговой оптимизации являются алгоритмы последовательного улучшения плана. Предположим, некоторый (не оптимальный) план задачи уже построен тем или иным способом (например, при помощи алгоритма последовательного выбора). Иногда бывает возможно предложить процедуру несложной модификации плана, при которой он остается допустимым планом задачи. Если для модифицированного плана значение целевой функции лучше, чем для исходного, то новый, улучшенный план следует взять вместо исходного и попытаться еще раз применить к нему улучшающую модификацию. Процесс прекратится, когда все возможные модификации будут только ухудшать план.
Рассмотрим, например, некоторый маршрут коммивояжера, проходящий последовательно через города A, B, C, D. В качестве модификации рассмотрим маршрут, в котором те же города посещаются в порядке A, C, B, D. Очевидно, такая перестановка сохраняет допустимость маршрута, а длина нового маршрута может оказаться меньше, чем у исходного.
Основным недостатком алгоритмов локальной оптимизации является то, что они совсем не обязательно приводят к глобально оптимальному плану задачи. В частности, для алгоритмов последовательного улучшения очень важен удачный выбор исходного плана. (Представьте себе альпиниста, который «локально оптимально» выбирает всегда путь, ведущий вверх. В конце концов он доберется до какой-нибудь вершины, но это может быть вершина маленького холмика, а не вершина самой высокой горы). Полезную роль может сыграть использование случайного выбора для построения исходного плана. Случайно выбранный план будет, скорее всего, сам по себе хуже, чем план, построенный по алгоритму последовательного выбора (хотя и не обязательно), но при многократном повторении комбинации «случайный выбор + последовательное улучшение» возрастает вероятность хотя бы раз оказаться «на склоне нужной горы» и придти к глобальному оптимуму.
Интересной разновидностью эвристических алгоритмов являются популярные в последнее время генетические алгоритмы. Они основаны на использовании биологических аналогий, использующих такие понятия, как популяция, ген, мутация, кроссинговер, отбор.
При разработке генетического алгоритма важную роль играет удачный выбор способа кодирования допустимых планов задачи. Каждый план представляется в виде линейной цепочки («хромосомы»), состоящей из некоторых символов или чисел, играющих роль генов. Для хромосом определяются операции мутации (изменения одного или сразу нескольких генов) и кроссинговера (получения новой хромосомы как комбинации двух имеющихся). Важно суметь так определить эти операции, чтобы хромосомы, получающиеся в результате, также кодировали допустимые планы задачи. Дальнейшее понятно: случайным или иным образом выбирается «начальная популяция» хромосом, новые хромосомы образуются с помощью случайных мутаций и кроссинговера, по правилам отбора формируется новое поколение популяции и т.д., смотри учебник биологии.
По сути дела, генетические алгоритмы являются оригинальной разновидностью алгоритмов случайного выбора с последовательным улучшением. Тот факт, что аналогичная схема дала неплохие результаты при эволюции живой природы, дает надежду на достаточную эффективность этих алгоритмов при решении задач комбинаторной оптимизации.
В некоторых случаях эвристический алгоритм производит впечатление настолько естественного для данной задачи, настолько самоочевидного, что неопытному человеку кажется, будто этот алгоритм должен всегда давать оптимальный план задачи. Проверка на двух-трех простых примерах укрепляет уверенность. Однако если нет строгого доказательства оптимальности, алгоритм приходится считать эвристическим. Интуиция в таких случаях не аргумент, она очень часто обманывает.
В качестве иллюстрации сказанного рассмотрим следующий пример. Задача о минимальном доминирующем множестве графа формулируется следующим образом. В данном неориентированном графе G=(V,E)найти минимальное по мощности подмножество вершин V0 такое, что каждая из остальных вершин Gсмежна хотя бы с одной вершиной из V0 .
После небольших размышлений в голову обычно приходит следующий алгоритм решения этой задачи. Упорядочим вершины графа по убыванию их степени (т.е. количества ребер, инцидентных вершине). Будем на каждом шаге включать в множество V0 вершину максимальной степени из тех, которые не смежны ни с одной вершиной из V0 . В случае равенства степеней будем брать вершину с меньшим номером.
Другой напрашивающийся алгоритм выглядит чуть похитрее. После включения вершины с максимальной степенью в множество V0 удалим эту вершину из графа Gвместе с инцидентными ей ребрами, уменьшим на 1 степени смежных ей вершин, найдем максимум степени среди оставшихся вершин и т.д.
Оба алгоритма являются полиномиальными. Но дают ли они точное решение?
Для большинства простых примеров оба алгоритма действительно находят минимальное доминирующее множество. Рассмотрим, однако, простой контрпример, показанный на рис.1.5.
Рис.1.5
В данном случае оба алгоритма включат в доминирующее множество вершину 1, после чего придется включить туда еще как минимум три вершины. В то же время три вершины 2, 3 и 4 образуют минимальное доминирующее множество.
Таким образом, для данной задачи очевидные алгоритмы, как оказалось, не всегда находят оптимальный план. Это не случайная неудача. В следующем разделе курса будут рассмотрены теоретические результаты, из которых следует, что для рассмотренной выше задачи построение точного полиномиального алгоритма явилось бы открытием мирового класса.
studlib.info
