Везде
Модификация метода пометок для задач многокритериальной оптимизации на графах
Оглавление
Аннотация Оценить Содержание публикации
Библиография Комментарии
Поделиться
QR
Метрика
Модификация метода пометок для задач многокритериальной оптимизации на графах
Аннотация
Код статьи
S042473880008559-3-1
DOI
10.31857/S042473880008559-3
Тип публикации
Статья
Статус публикации
Опубликовано
Авторы
Заславский Алексей Александрович 
Должность: старший научный сотрудник
Аффилиация: ЦЭМИ РАН
Адрес: Москва, Российская Федерация
Белова Алина Михайловна
Должность: студентка
Аффилиация: Национальный исследовательский университет "МЭИ"
Адрес: Российская Федерация
Выпуск
Том 56 Номер 1
Страницы
95-99
Аннотация

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

Ключевые слова
граф, метод пометок, многокритериальная оптимизация, оптимальность по Парето
Классификатор
Получено
05.03.2020
Дата публикации
20.03.2020
Всего подписок
41
Всего просмотров
1864
Оценка читателей
0.0 (0 голосов)
Цитировать   Скачать pdf
1 Метод пометок (МП) (Ху, 1974, гл.10) позволяет решить следующую задачу. Дан ориентированный граф, каждому ребру которого приписано положительное число (длина ребра). Требуется найти кратчайший путь от вершины S до вершины F. В алгоритме метода вершинам графа последовательно, начиная с вершины S, присваиваются пометки, показывающие длину кратчайшего из построенных на данный момент путей, ведущих из S в данную вершину. Пометки могут быть двух видов: постоянные и временные. Если вершина получает постоянную пометку, значит, построенный путь является кратчайшим среди всех возможных путей в эту вершину. Алгоритм заканчивает работу, когда постоянную пометку получает вершина F.
2 Приведем формальное описание алгоритма.
3 Шаг 0. Присвоим вершине S постоянную пометку, равную нулю, а остальным вершинам временные пометки, равные бесконечности.
4 Шаг 1. Пусть V— последняя вершина, получившая постоянную пометку D. Для каждой вершины i, в которую ведет ребро из V, вычислим величину D+di, где di — длина ребра, между V и i. Если вычисленная величина меньше временной пометки вершины i, заменим на нее эту пометку.
5 Шаг 2. Среди всех временных пометок найдем наименьшую и сделаем ее постоянной. Если соответствующая вершина совпадает с F, построим обратным ходом искомый кратчайший путь (для каждой пометки запоминается, из какой вершины она получена), иначе вернемся к шагу 1.
6 Пусть теперь каждое ребро графа характеризуется не одной, а несколькими величинами, например временем пути и его стоимостью. В этом случае невозможно однозначно указать наилучший путь из S в F, поскольку у разных лиц, принимающих решения (ЛПР), могут быть разные представления о сравнительной важности критериев. На этот момент можно лишь требовать, чтобы найденный путь был оптимальным по Парето, т.е. не существовало пути, лучшего по всем критериям (Подиновский, Ногин, 1982, гл.1). Однако построить все множество оптимальных по Парето путей не представляется возможным, поскольку оно может оказаться очень большим. Поэтому нужно поставить задачу построения достаточно представительного множества Парето-оптимальных путей, из которого ЛПР сможет выбрать устраивающий его путь. Строить такое множество целесообразно с помощью интерактивной процедуры, постепенно уточняя требования ЛПР. Приводимый ниже алгоритм может стать основой для такой процедуры.
7 Опишем предложенный алгоритм.
8 Предположим для простоты, что каждое ребро графа характеризуется двумя величинами — временем t и стоимостью c. Пусть ЛПР задает ограничение для одного из критериев, например для стоимости. Будем искать минимальный по времени путь, стоимость C которого не превосходит заданного ЛПР значения C0.
9 В отличие от классического алгоритма МП вершина графа может получить не одну, а несколько пометок (T1,C1),…,(Tk,Ck), где T1Ck. Кроме того, пометки могут не только добавляться, но и удаляться.
10 Приведем формальное описание алгоритма.
11 Шаг 0. Присвоим вершине S постоянную пометку (0,0), а остальным вершинам временные бесконечные пометки.
12 Шаг 1. Пусть V— последняя вершина, получившая постоянную пометку (T,C). Для каждой вершины i, в которую ведет ребро из V, вычислим величины T’i=T+ti, Ci' =C+ci, где ti, ci — время и стоимость, соответствующие ребру V – i.
13 Шаг 2. Если все >C0, удаляем пометку (T,C) и переходим к шагу 4.
14 Шаг 3. Сравниваем вектор (,) со всеми пометками (Tj,Cj), присвоенными вершине i. Если для некоторых jTjи Cj ≤ , то новая пометка не записывается. В противном случае записываем новую пометку и удаляем все пометки (Tj,Cj) с Tjи Cj.
15 Шаг 4. Если не существует ни одной временной пометки с C ≤ C0, то алгоритм заканчивает работу (т.е. не существует пути, удовлетворяющего заданному ограничению по стоимости). В противном случае находим пометку с наименьшим T и делаем ее постоянной.
16 Шаг 5. Если вершина, получившая постоянную пометку, совпадает с F, строим обратным ходом искомый путь. Иначе возвращаемся к шагу 1.
17 Очевидно, что построенный путь является Парето-оптимальным. Если он не устраивает ЛПР, тот задает новые ограничения и процедура повторяется. Аналогично, при числе критериев, большем двух, ЛПР выбирает основной критерий, который минимизируется при заданных ЛПР ограничениях на значения остальных критериев.
18 Пример. Рассмотрим работу алгоритма на примере графа, приведенного на рис. 1. Ребра ориентированы от вершин с меньшими номерами к большим. Требуется построить путь от вершин 0 к вершине 9, удовлетворяющий условию C ≤ 13. Присвоим вершине 0 постоянную пометку (0,0), а вершинам 1, 2, 3 временные пометки (2,3), (1,5), (4,1) соответственно. Пометку (1, 5) вершины 2 сделаем постоянной (рис. 2).
19
Рис. 1 Рис. 2
20 Присвоим вершинам 4 и 5 временные пометки (1+2, 5+1)=(3,6) и (1+3, 5+1)=(4,6) соответственно.
21 Пометку (2,3) вершины 1 сделаем постоянной (рис. 3). Присвоим вершине 4 пометку (5, 5).
22 Пометку (3, 6) вершины 4 сделаем постоянной (рис. 4). Присвоим вершинам 7 и 8 временные пометки (7, 8) и (8, 8) соответственно.
23
Рис. 3 Рис. 4
24 Пометку (4, 1) вершины 3 сделаем постоянной (рис. 5). Присвоим вершинам 5 и 6 временные пометки (6, 3) и (7, 4) соответственно.
25 Пометку (4, 6) вершины 5 сделаем постоянной (рис. 6). Присвоим временную пометку (5, 11) вершине 8.
26
Рис. 5 Рис. 6
27 Пометку (5, 5) вершины 4 сделаем постоянной (рис. 7). Присвоим вершинам 7 и 8 временные пометки (9, 7) и (10, 7) соответственно.
28 Пометку (5, 11) вершины 8 сделаем постоянной (рис. 8). Удалим пометку (5, 11) вершины 8, поскольку из нее нельзя образовать пометки с C ≤ 13.
29
Рис. 7 Рис. 8
Пометку (6, 3) вершины 5 сделаем постоянной. Присвоим временную пометку (7, 8) вершине 8, удалим пометку (8, 8).
30 Пометку (7, 4) вершины 6 сделаем постоянной (рис. 9). Присвоим временные пометки (9, 6) и (11, 9) вершинам 8 и 9 соответственно. Удалим пометку (10, 7) вершины 8.
31 Сделаем пометку (7, 8) вершины 8 постоянной (рис. 10). Присвоим временную пометку (9, 13) вершине 9.
32
Рис. 9 Рис. 10
33 Сделаем пометку (7, 8) вершины 7 постоянной (рис. 11). Пометка (11, 9) вершине 9 не присваивается, поскольку есть такая же пометка. Сделаем пометку (9, 6) вершины 8 постоянной.
34 Пометка (11, 11) вершине 9 не присваивается, поскольку есть лучшая пометка (9, 9). Сделаем пометку (9, 7) вершины 7 постоянной. Присвоим временную пометку (13, 8) вершине 9.
35 Сделаем постоянной пометку (9, 13) вершины 9 (рис. 12). Поскольку вершина 9 получила постоянную пометку, алгоритм заканчивает работу. Обратным ходом строится искомый путь 0—3—5—8—9 (рис. 13)
36
Рис. 11 Рис. 12
Рис. 13
37 Проверка предложенного алгоритма на небольших примерах позволяет сделать предположение о его работоспособности в задачах многокритериальной оптимизации на графах. Тем не менее эффективность алгоритма может быть подтверждена только масштабной серией вычислительных экспериментов. В настоящее время ведется подготовка к проведению такой серии.
38 Еще одно возможное направление дальнейших исследований связано с заменой метода пометок методом поиска кратчайшего пути в графе, например алгоритма Беллмана–Форда (Bellman, 1958;Moore, 1957), алгоритма Флойда–Уоршелла (Галкина, 2003, гл.4; Cherkassky et al., 1996). В частности, перспективным представляется модифицировать для многокритериальных задач метод двусторонняя очередь, показавший свою эффективность (Левит, Лившиц, 1972, § 17).

Библиография

1. Bellman R. (1958). On a routing problem (неопр.) // Quarterly of Applied Mathematics. — 1958. — Т. 16. — С. 87—90

2. Moore E.F. (1957) The shortest path through a maze// Proceedings of an International Symposium on the Theory of Switching 1957 — Harvard University Press, 1959. — Vol. 2. — P. 285–292. — 345 p. — Annals of the Computation Laboratory of Harvard University. V.30.

3. Галкина В.А. (2003). Построение кратчайших путей в ориентированном графе //Дискретная математика. Комбинаторная оптимизация на графах. — Москва: Издательство "Гелиос АРВ", 2003. — С. 75—94. — 232 с.

4. Левит Б.Ю., Лившиц В.Н. (1972). Нелинейные сетевые транспортные задачи. М.: Изд-во «Транспорт». 144 с.

5. Подиновский В.В., Ногин В.Д. (1982). Парето-оптимальные решения многокритериальных задач. М.: Наука. 256 с.

6. Ху Т. (1974). Целочисленное программирование и потоки в сетях. М.: Мир. 520с.

7. Черкасский и др. (1996), Cherkassky B.V., Goldberg A.V., Radzik T. Shortest past algorithms. // Math.Prog. — Springer Science+Business Media 1996. — Vol. 73, Iss. 2. — P. 129–174.

Комментарии

Сообщения не найдены

Написать отзыв
Перевести