Multicriterial optimization on graphs. Results of calculating experiments

Akhonov, Kamil; Zaslavsky, Aleksey; Kovyrzina, E.V.

doi:10.31857/S042473880028296-4

English

Home>no. 4>Multicriterial optimization on graphs. Results of calculating experiments

Multicriterial optimization on graphs. Results of calculating experiments

Table of contents

Annotation Estimate Publication content

References Comments Additional materials

Multicriterial optimization on graphs. Results of calculating experiments

Annotation

PII

S042473880028296-4-1

DOI

10.31857/S042473880028296-4

Publication type

Article

Status

Published

Authors

Kamil Akhonov Send message

Affiliation: National Research University "Moscow Power Engineering Institute", Moscow
Address: Russian Federation

Aleksey Zaslavsky

Occupation: Senior Research Scholar
Affiliation: Central Economics and Mathematics Institute, Russian Academy of Sciences
Address: Russian Federation

E.V. Kovyrzina

Affiliation: National Research University "Moscow Power Engineering Institute", Moscow
Address: Russian Federation

Edition

Volume 59 no. 4

Pages

126-129

Abstract

The label method (Dejkstra method) allows to find the shortest way between two vertices of a graph with given lengths of edges. If the values of several criteria are given for each vertex, we obtain a multicriterial problem, and we have to construct a Pareto-optimal way corresponding with preferences of decision maker (DM). In 2020 A.M.Belova and A.A.Zaslavsky proposed an approach to this problem based on the optimization of one of criteria with limiting conditions for the remaining criteria. The results of calculating experiments examinating the effectivness of proposed algorythm are given in this paper.

Keywords

graph, label method, multicriterial optimization, Pareto-optimality.

Received

27.10.2023

Date of publication

28.12.2023

Number of purchasers

Views

212

Readers community rating

0.0 (0 votes)

Cite Download pdf

GOST	Akhonov K., Kovyrzina E., Zaslavsky A. Multicriterial optimization on graphs. Results of calculating experiments // Economics and the Mathematical Methods. – 2023. – V. 59. – no. 4 C. 126-129 . URL: https://emm.jes.su/s042473880028296-4-1/. DOI: 10.31857/S042473880028296-4
MLA	Akhonov, Kamil, Kovyrzina, E.V, Zaslavsky, Aleksey "Multicriterial optimization on graphs. Results of calculating experiments." Economics and the Mathematical Methods. 59.4 (2023).:126-129. DOI: 10.31857/S042473880028296-4
APA	Akhonov K., Kovyrzina E., Zaslavsky A. (2023). Multicriterial optimization on graphs. Results of calculating experiments. Economics and the Mathematical Methods. vol. 59, no. 4, pp.126-129 DOI: 10.31857/S042473880028296-4

Additional services access

Additional services for the article

Services benefits

100 RUB / 1.0 SU

Additional services for the issue

Services benefits

910 RUB / 15.0 SU

Additional services for all issues for 2023

Services benefits

2730 RUB / 61.0 SU


1	Метод пометок (МП) или метод Дейкстры (Ху, 1974, гл.10) позволяет решить следующую задачу. Дан ориентированный граф, каждому ребру которого приписано положительное число (длина ребра). Требуется найти кратчайший путь от вершины S до вершины F. Если каждое ребро графа характеризуется не одной, а несколькими величинами, например, временем пути и его стоимостью, то невозможно однозначно указать наилучший путь из S в F, поскольку у разных лиц, принимающих решения (ЛПР), могут быть разные представления о сравнительной важности критериев. При этом необходимо требовать, чтобы найденный путь был оптимальным по Парето, т.е. не существовало пути, лучшего по всем критериям (Подиновский, Ногин, 1982, гл.1). Представляется естественной задача построения достаточно представительного множества Парето-оптимальных путей, из которого ЛПР сможет выбрать устраивающий его путь. Строить такое множество целесообразно с помощью интерактивной процедуры, постепенно уточняя требования ЛПР. В качестве основы для такой процедуры в работе (Белова, Заславский, 2020) был предложен следующий алгоритм. Будем искать путь, минимизирующий один из критериев (назовем этот критерий временем) и удовлетворяющий заданным ЛПР ограничениям для остальных критериев. Пусть для j-го критерия (j=1,…n) ЛПР задал в качестве максимального допустимого значения C_j₀. В отличие от классического алгоритма МП вершина графа может получить не одну, а несколько пометок (T₁,C₁₁_,_…_,C_n₁),…,(T_k,C₁_k,…,C_nk), где T₁<…<T_k . Кроме того, пометки могут не только добавляться, но и удаляться. Приведем формальное описание алгоритма. Шаг 0. Присвоим вершине S постоянную пометку (0,0,…,0), а остальным вершинам временные бесконечные пометки. Шаг 1. Пусть V— последняя вершина, получившая постоянную пометку (T, C₁_,_…_,C_n). Для каждой вершины i, в которую ведет ребро из V, вычислим величины T’_i=T+t_i, C’_ji=C+C_ji,где t_i, c_ji — время и значение j-го критерия, соответствующие ребру V – i. Шаг 2. Если не существует вершины i, для которой C’_ji C_j₀(j=1,…n), удаляем пометку (T,C) и переходим к шагу 4. Шаг 3. Сравниваем вектор ([[[image2]]],C’₁_i,…, C’_ni) со всеми пометками (T_k,C_k₁,…,C_kn), присвоенными вершине i. Если для некоторого k T_k[[[image3]]]и C_k_jC’_ji, новая пометка не записывается. В противном случае записываем новую пометку и удаляем все пометки (T_j,C_j) с T’_i T_kи C’_ji C_k_j Шаг 4. Если не существует ни одной временной пометки с C’_ji C_j₀(j=1,…n), то алгоритм заканчивает работу (т.е. не существует пути, удовлетворяющего заданному ограничению по стоимости). В противном случае находим пометку с наименьшим T и делаем ее постоянной. Шаг 5. Если вершина, получившая постоянную пометку, совпадает с F, строим обратным ходом искомый путь. Иначе возвращаемся к шагу 1.	Метод пометок (МП) или метод Дейкстры (Ху, 1974, гл.10) позволяет решить следующую задачу. Дан ориентированный граф, каждому ребру которого приписано положительное число (длина ребра). Требуется найти кратчайший путь от вершины <em>S</em> до вершины <em>F</em>. Если каждое ребро графа характеризуется не одной, а несколькими величинами, например, временем пути и его стоимостью, то невозможно однозначно указать наилучший путь из <em>S</em> в <em>F</em>, поскольку у разных лиц, принимающих решения (ЛПР), могут быть разные представления о сравнительной важности критериев. При этом необходимо требовать, чтобы найденный путь был оптимальным по Парето, т.е. не существовало пути, лучшего по всем критериям (Подиновский, Ногин, 1982, гл.1). Представляется естественной задача построения достаточно представительного множества Парето-оптимальных путей, из которого ЛПР сможет выбрать устраивающий его путь. Строить такое множество целесообразно с помощью интерактивной процедуры, постепенно уточняя требования ЛПР. В качестве основы для такой процедуры в работе (Белова, Заславский, 2020) был предложен следующий алгоритм. Будем искать путь, минимизирующий один из критериев (назовем этот критерий временем) и удовлетворяющий заданным ЛПР ограничениям для остальных критериев. Пусть для <em>j</em>-го критерия (<em>j</em><em>=</em><em>1,…</em><em>n</em>) ЛПР задал в качестве максимального допустимого значения <em>C</em><sub><em>j</em></sub><sub><em>0</em></sub>. В отличие от классического алгоритма МП вершина графа может получить не одну, а несколько пометок (<em>T</em><sub>1</sub>,<em>C</em><sub><em>11</em></sub><sub>,</sub><sub>…</sub><sub>,</sub><em>C</em><sub><em>n</em></sub><sub><em>1</em></sub>),…,(<em>T</em><sub><em>k</em></sub>,<em>C</em><sub><em>1</em></sub><sub><em>k</em></sub><em>,</em><em>…</em><em>,</em><em>C</em><sub><em>nk</em></sub>), где <em>T</em><sub>1</sub><…<<em>T</em><sub><em>k</em></sub> . Кроме того, пометки могут не только добавляться, но и удаляться. Приведем формальное описание алгоритма. <strong>Шаг 0. </strong>Присвоим вершине <em>S</em> постоянную пометку (0,0,…,0), а остальным вершинам временные бесконечные пометки. <strong>Шаг 1. </strong>Пусть <em>V</em>— последняя вершина, получившая постоянную пометку (<em>T</em>,<em> </em><em>C</em><sub><em>1</em></sub><sub>,</sub><sub>…</sub><sub>,</sub><em>C</em><sub><em>n</em></sub>). Для каждой вершины <em>i</em>, в которую ведет ребро из <em>V</em>, вычислим величины <em>T</em>’<sub><em>i</em></sub>=<em>T</em>+<em>t</em><sub><em>i</em></sub>, C’<sub><em>ji</em></sub><em>=</em><em>C</em><em>+</em><em>C</em><sub><em>ji</em></sub><em>,</em><sub> </sub>где <em>t</em><sub><em>i</em></sub><em>, </em><em>c</em><sub><em>ji</em></sub> — время и значение <em>j</em><em>-</em>го критерия, соответствующие ребру <em>V</em> – <em>i</em>. <strong>Шаг 2. </strong>Если не существует вершины <em>i</em>, для которой C’<sub><em>ji</em></sub><em> </em><em>C</em><sub><em>j</em></sub><sub><em>0</em></sub><sub><em> </em></sub>(<em>j</em><em>=</em><em>1,…</em><em>n</em>), удаляем пометку (<em>T</em>,<em>C</em>) и переходим к шагу 4. <strong>Шаг 3. </strong>Сравниваем вектор ([[[image2]]],C’<sub><em>1</em></sub><sub><em>i</em></sub><em>,</em><em>…</em><em>,</em> C’<sub><em>ni</em></sub>) со всеми пометками (<em>T</em><sub><em>k</em></sub>,<em>C</em><sub><em>k</em></sub><sub><em>1</em></sub><em>,</em><em>…</em><em>,</em><em>C</em><sub><em>kn</em></sub>), присвоенными вершине <em>i</em>. Если для некоторого <em>k</em><em> </em><em>T</em><sub><em>k</em></sub>[[[image3]]]и <em>C</em><sub><em>k</em></sub><sub><em>j</em></sub>C’<sub><em>ji</em></sub>, новая пометка не записывается. В противном случае записываем новую пометку и удаляем все пометки (<em>T</em><sub><em>j</em></sub>,<em>C</em><sub><em>j</em></sub>) с <em>T</em>’<sub><em>i</em></sub><em> </em><em>T</em><sub><em>k</em></sub><sub><em> </em></sub>и C’<sub><em>ji</em></sub><em> </em><em>C</em><sub><em>k</em></sub><sub><em>j</em></sub><sub> </sub> <strong>Шаг 4. </strong>Если не существует ни одной временной пометки с C’<sub><em>ji</em></sub><em> </em><em>C</em><sub><em>j</em></sub><sub><em>0</em></sub><sub><em> </em></sub>(<em>j</em><em>=</em><em>1,…</em><em>n</em>), то алгоритм заканчивает работу (т.е. не существует пути, удовлетворяющего заданному ограничению по стоимости). В противном случае находим пометку с наименьшим <em>T</em> и делаем ее постоянной. <strong>Шаг 5. </strong>Если вершина, получившая постоянную пометку, совпадает с <em>F</em>, строим обратным ходом искомый путь. Иначе возвращаемся к шагу 1. Метод пометок (МП) или метод Дейкстры (Ху, 1974, гл.10) позволяет решить следующую задачу. Дан ориентированный граф, каждому ребру которого приписано положительное число (длина ребра). Требуется найти кратчайший путь от вершины <em>S</em> до вершины <em>F</em>. Если каждое ребро графа характеризуется не одной, а несколькими величинами, например, временем пути и его стоимостью, то невозможно однозначно указать наилучший путь из <em>S</em> в <em>F</em>, поскольку у разных лиц, принимающих решения (ЛПР), могут быть разные представления о сравнительной важности критериев. При этом необходимо требовать, чтобы найденный путь был оптимальным по Парето, т.е. не существовало пути, лучшего по всем критериям (Подиновский, Ногин, 1982, гл.1). Представляется естественной задача построения достаточно представительного множества Парето-оптимальных путей, из которого ЛПР сможет выбрать устраивающий его путь. Строить такое множество целесообразно с помощью интерактивной процедуры, постепенно уточняя требования ЛПР. В качестве основы для такой процедуры в работе (Белова, Заславский, 2020) был предложен следующий алгоритм. Будем искать путь, минимизирующий один из критериев (назовем этот критерий временем) и удовлетворяющий заданным ЛПР ограничениям для остальных критериев. Пусть для <em>j</em>-го критерия (<em>j</em><em>=</em><em>1,…</em><em>n</em>) ЛПР задал в качестве максимального допустимого значения <em>C</em><sub><em>j</em></sub><sub><em>0</em></sub>. В отличие от классического алгоритма МП вершина графа может получить не одну, а несколько пометок (<em>T</em><sub>1</sub>,<em>C</em><sub><em>11</em></sub><sub>,</sub><sub>…</sub><sub>,</sub><em>C</em><sub><em>n</em></sub><sub><em>1</em></sub>),…,(<em>T</em><sub><em>k</em></sub>,<em>C</em><sub><em>1</em></sub><sub><em>k</em></sub><em>,</em><em>…</em><em>,</em><em>C</em><sub><em>nk</em></sub>), где <em>T</em><sub>1</sub><…<<em>T</em><sub><em>k</em></sub> . Кроме того, пометки могут не только добавляться, но и удаляться. Приведем формальное описание алгоритма. <strong>Шаг 0. </strong>Присвоим вершине <em>S</em> постоянную пометку (0,0,…,0), а остальным вершинам временные бесконечные пометки. <strong>Шаг 1. </strong>Пусть <em>V</em>— последняя вершина, получившая постоянную пометку (<em>T</em>,<em> </em><em>C</em><sub><em>1</em></sub><sub>,</sub><sub>…</sub><sub>,</sub><em>C</em><sub><em>n</em></sub>). Для каждой вершины <em>i</em>, в которую ведет ребро из <em>V</em>, вычислим величины <em>T</em>’<sub><em>i</em></sub>=<em>T</em>+<em>t</em><sub><em>i</em></sub>, C’<sub><em>ji</em></sub><em>=</em><em>C</em><em>+</em><em>C</em><sub><em>ji</em></sub><em>,</em><sub> </sub>где <em>t</em><sub><em>i</em></sub><em>, </em><em>c</em><sub><em>ji</em></sub> — время и значение <em>j</em><em>-</em>го критерия, соответствующие ребру <em>V</em> – <em>i</em>. <strong>Шаг 2. </strong>Если не существует вершины <em>i</em>, для которой C’<sub><em>ji</em></sub><em> </em><em>C</em><sub><em>j</em></sub><sub><em>0</em></sub><sub><em> </em></sub>(<em>j</em><em>=</em><em>1,…</em><em>n</em>), удаляем пометку (<em>T</em>,<em>C</em>) и переходим к шагу 4. <strong>Шаг 3. </strong>Сравниваем вектор ([[[image2]]],C’<sub><em>1</em></sub><sub><em>i</em></sub><em>,</em><em>…</em><em>,</em> C’<sub><em>ni</em></sub>) со всеми пометками (<em>T</em><sub><em>k</em></sub>,<em>C</em><sub><em>k</em></sub><sub><em>1</em></sub><em>,</em><em>…</em><em>,</em><em>C</em><sub><em>kn</em></sub>), присвоенными вершине <em>i</em>. Если для некоторого <em>k</em><em> </em><em>T</em><sub><em>k</em></sub>[[[image3]]]и <em>C</em><sub><em>k</em></sub><sub><em>j</em></sub>C’<sub><em>ji</em></sub>, новая пометка не записывается. В противном случае записываем новую пометку и удаляем все пометки (<em>T</em><sub><em>j</em></sub>,<em>C</em><sub><em>j</em></sub>) с <em>T</em>’<sub><em>i</em></sub><em> </em><em>T</em><sub><em>k</em></sub><sub><em> </em></sub>и C’<sub><em>ji</em></sub><em> </em><em>C</em><sub><em>k</em></sub><sub><em>j</em></sub><sub> </sub> <strong>Шаг 4. </strong>Если не существует ни одной временной пометки с C’<sub><em>ji</em></sub><em> </em><em>C</em><sub><em>j</em></sub><sub><em>0</em></sub><sub><em> </em></sub>(<em>j</em><em>=</em><em>1,…</em><em>n</em>), то алгоритм заканчивает работу (т.е. не существует пути, удовлетворяющего заданному ограничению по стоимости). В противном случае находим пометку с наименьшим <em>T</em> и делаем ее постоянной. <strong>Шаг 5. </strong>Если вершина, получившая постоянную пометку, совпадает с <em>F</em>, строим обратным ходом искомый путь. Иначе возвращаемся к шагу 1.

2	Описание вычислительного эксперимента. Для проверки эффективности предложенного алгоритма использовался следующий метод генерации графов. Между вершинами S и F располагаются N уровней по K вершин на каждом, вершины S и F соединяются со всеми вершинами ближайших к ним уровней. Между любыми двумя вершинами, лежащими на соседних уровнях, проводится ребро с вероятностью p₁, а между двумя вершинами, лежащими через уровень, --- с вероятностью p₂. После этого выбираются случайные значения весов ребер. В вычислительных экспериментах исследовалась зависимость эффективности алгоритма от значений N, K, p₁, p₂, а также от наличия положительной или отрицательной корреляции между критериями. Результаты экспериментов. В таблице 1 приведено время работы алгоритма при различных значениях N и K для двух и трех критериев. Из таблицы видно, что для трех критериев алгоритм, как правило, работает дольше, чем для двух. Кроме того, можно сделать вывод, что наиболее существенное влияние на время работы алгоритма оказывает средняя длина N путей между S и F. Например, время при N=5, K=100 и N=100, K=5 отличается примерно в 40 раз для двух и почти в 1000 раз для трех критериев, хотя общее количество вершин в обоих случаях одинаково. В таблице 2 приводится время работы алгоритма для двух критериев при наличии положительной и отрицательной корреляции между ними. Можно сделать вывод, что наличие положительной корреляции существенно уменьшает время работы алгоритма. Это связано с тем, что при отрицательной корреляции количество Парето-оптимальных путей существенно больше, а значит возрастает время проверки выполнения ограничений. В таблице 3 приводится время работы алгоритма в зависимости от вероятностей p₁, p₂наличия ребер между соседними и несоседними уровнями. Видно, что время работы возрастает с ростом каждой из вероятностей. При этом влияние вероятности p₁, оказывается выше. Это связано с ростом средней длины путей между S и F.	<strong>Описание вычислительного эксперимента. </strong>Для проверки эффективности предложенного алгоритма использовался следующий метод генерации графов. Между вершинами <em>S</em><em> </em>и<em> </em><em>F</em><em> </em>располагаются <em>N</em> уровней по <em>K</em><em> </em>вершин на каждом, вершины <em>S</em><em> </em>и<em> </em><em>F</em><em> </em>соединяются со всеми вершинами ближайших к ним уровней. Между любыми двумя вершинами, лежащими на соседних уровнях, проводится ребро с вероятностью <em>p</em><sub><em>1</em></sub><em>, </em>а между двумя вершинами, лежащими через уровень, --- с вероятностью <em>p</em><sub><em>2</em></sub><em>. </em> После этого выбираются случайные значения весов ребер. В вычислительных экспериментах исследовалась зависимость эффективности алгоритма от значений <em>N</em><em>, </em><em>K</em><em>, </em><em>p</em><sub><em>1</em></sub><em>, </em><em>p</em><sub><em>2</em></sub><em>, </em>а также от наличия положительной или отрицательной корреляции между критериями. <strong>Результаты экспериментов</strong><strong>. </strong>В таблице 1 приведено время работы алгоритма при различных значениях <em>N</em><em> </em>и<em> </em><em>K</em><em> </em>для двух и трех критериев. Из таблицы видно, что для трех критериев алгоритм, как правило, работает дольше, чем для двух. Кроме того, можно сделать вывод, что наиболее существенное влияние на время работы алгоритма оказывает средняя длина <em>N</em><em> </em>путей между <em>S</em><em> </em>и <em>F</em><em>. </em>Например, время при <em>N</em><em>=5, </em><em>K</em><em>=100 </em>и <em>N</em><em>=100, </em><em>K</em><em>=5 </em>отличается примерно в 40 раз для двух и почти в 1000 раз для трех критериев, хотя общее количество вершин в обоих случаях одинаково. В таблице 2 приводится время работы алгоритма для двух критериев при наличии положительной и отрицательной корреляции между ними. Можно сделать вывод, что наличие положительной корреляции существенно уменьшает время работы алгоритма. Это связано с тем, что при отрицательной корреляции количество Парето-оптимальных путей существенно больше, а значит возрастает время проверки выполнения ограничений. В таблице 3 приводится время работы алгоритма в зависимости от вероятностей <em>p</em><sub><em>1</em></sub><em>, </em><em>p</em><sub><em>2</em></sub><sub><em> </em></sub>наличия ребер между соседними и несоседними уровнями. Видно, что время работы возрастает с ростом каждой из вероятностей. При этом влияние вероятности <em>p</em><sub><em>1</em></sub><em>, </em>оказывается выше. Это связано с ростом средней длины путей между <em>S</em><em> </em>и <em>F</em><em>.</em> <strong>Описание вычислительного эксперимента. </strong>Для проверки эффективности предложенного алгоритма использовался следующий метод генерации графов. Между вершинами <em>S</em><em> </em>и<em> </em><em>F</em><em> </em>располагаются <em>N</em> уровней по <em>K</em><em> </em>вершин на каждом, вершины <em>S</em><em> </em>и<em> </em><em>F</em><em> </em>соединяются со всеми вершинами ближайших к ним уровней. Между любыми двумя вершинами, лежащими на соседних уровнях, проводится ребро с вероятностью <em>p</em><sub><em>1</em></sub><em>, </em>а между двумя вершинами, лежащими через уровень, --- с вероятностью <em>p</em><sub><em>2</em></sub><em>. </em> После этого выбираются случайные значения весов ребер. В вычислительных экспериментах исследовалась зависимость эффективности алгоритма от значений <em>N</em><em>, </em><em>K</em><em>, </em><em>p</em><sub><em>1</em></sub><em>, </em><em>p</em><sub><em>2</em></sub><em>, </em>а также от наличия положительной или отрицательной корреляции между критериями. <strong>Результаты экспериментов</strong><strong>. </strong>В таблице 1 приведено время работы алгоритма при различных значениях <em>N</em><em> </em>и<em> </em><em>K</em><em> </em>для двух и трех критериев. Из таблицы видно, что для трех критериев алгоритм, как правило, работает дольше, чем для двух. Кроме того, можно сделать вывод, что наиболее существенное влияние на время работы алгоритма оказывает средняя длина <em>N</em><em> </em>путей между <em>S</em><em> </em>и <em>F</em><em>. </em>Например, время при <em>N</em><em>=5, </em><em>K</em><em>=100 </em>и <em>N</em><em>=100, </em><em>K</em><em>=5 </em>отличается примерно в 40 раз для двух и почти в 1000 раз для трех критериев, хотя общее количество вершин в обоих случаях одинаково. В таблице 2 приводится время работы алгоритма для двух критериев при наличии положительной и отрицательной корреляции между ними. Можно сделать вывод, что наличие положительной корреляции существенно уменьшает время работы алгоритма. Это связано с тем, что при отрицательной корреляции количество Парето-оптимальных путей существенно больше, а значит возрастает время проверки выполнения ограничений. В таблице 3 приводится время работы алгоритма в зависимости от вероятностей <em>p</em><sub><em>1</em></sub><em>, </em><em>p</em><sub><em>2</em></sub><sub><em> </em></sub>наличия ребер между соседними и несоседними уровнями. Видно, что время работы возрастает с ростом каждой из вероятностей. При этом влияние вероятности <em>p</em><sub><em>1</em></sub><em>, </em>оказывается выше. Это связано с ростом средней длины путей между <em>S</em><em> </em>и <em>F</em><em>.</em>

References

1. A.M.Belova, A.A.Zaslavsky (2023) Modification of the label method for problems of multicriterial optimization. Economics and Mathematical Methods, 2020, v. 56, № 1, с. 95—99. DOI: 10.31857/S042473880008559-3 (in Russian).

2. Hu T.C. (1974). Tselochislennoe programmirovanie i potoki v setjakh. [Integer Programming and Network flows]. Translated from the English [Hu T.C., Originally published in1970. Addison-Wesley Publishing Company. California-London].Moscow: Mir (in Russian).

3. Podinovskij V.V., Nogin V.D. (1982). Pareto-optimal solutions of multicriterial problems. Moscow: Nauka (in Russian).