ВВЕДЕНИЕ 4
Введение
1. Обзор актуальных методов 7
1.1. Решение задачи о кратчайшем пути со скалярным критерием 7
1.1.1. Алгоритм Дейкстры поиска кратчайших путей в графе 8
1.2. Решение задачи выбора оптимального пути с векторным критерием.. 9
2. Постановка задачи 15
3. Решение задачи 20
3.1. Решение задачи 1 20
3.2. Решение задачи 2 22
3.3. Решение задачи 3 24
3.4. Вспомогательные алгоритмы 27
3.4.1. Линейная свертка критериев 27
3.4.2. Стабилизация динамической системы 27
3.4.3. Алгоритм исследования влияния распределения вектора значимости
критериев на решение задачи 1 28
3.4.4. Алгоритм исследования устойчивости парето-оптимального множества
решений к возмущениям 30
3.4.5. Алгоритм построения графа заданного размера 31
3.4.6. Алгоритм исследования влияния дополнительных параметров на
решение задач 2 и 3 32
3.4.7. Алгоритм исследования влияния порядка и размера графа на время
решения задачи 34
4. Разработка программного обеспечения 35
5. Экспериментальные исследования 39
5.1. Исследование устойчивости парето-оптимального множества решений к возмущениям 39
5.2. Исследования влияния порядка и размера графа на время решения задачи
5.3. Исследование влияния прочих параметров на решение
двухкритериальной задачи выбора пути 46
ЗАКЛЮЧЕНИЕ 51
СПИСОК ЛИТЕРАТУРЫ 53
ПРИЛОЖЕНИЕ 55
Данная работа посвящена исследованию и решению двухкритериальной задачи выбора путей в графе при неточных данных.
Задача поиска оптимальных путей является одной из самых важных задач теории графов и в последнее время изучается довольно интенсивно в самых разных постановках. Это объясняется широким кругом приложения данной задачи в различных областях повседневной жизни, а именно: в беспроводных сетях с переменной топологией, в системах автопилотирования, e-navigation для планирования и контроля судовождения, в GPS-навигаторах, картографических сервисах, при решении проблем спутникового планирования, а также различных задач маршрутизации в компьютерных сетях и планирования поездок.
На сегодняшний день существует множество алгоритмов решения задачи выбора оптимальных путей. Однако, несмотря на востребованность алгоритмов маршрутизации, остаются некоторые вопросы, которые слабо исследованы либо используют локальные особенности определенной задачи и не могут быть применены в общем случае. Как показывает практика, довольно часто методы, используемые при решении классической задачи о кратчайшем пути, оказываются неприменимыми в следствие особенностей решаемой задачи.
В качестве примера рассмотрим сеть, в которой каждой дуге назначены несколько параметров: время, стоимость, надежность, пропускная способность, безопасность, удобство и т.д. Очевидно, что если мы будем искать кратчайший путь, учитывая лишь физическое расстояние между узлами сети, то он может оказаться слишком дорогим для использования, небезопасным и т.д. То есть в данном случае одной целевой функции недостаточно для описания практической проблемы.
Таким образом, возникает ситуация, когда необходимо построить оптимальный маршрут между объектами, основываясь сразу на нескольких критериях поиска. Такие задачи называются BSP (двухкритериальная задача о кратчайшем пути) и MSP (многокритериальная задача о кратчайшем пути).
Другой, не менее важной особенностью является наличие неточности в исходных данных. Узлы сети могут менять свое местоположение с течением времени, а соединения между ними - периодически пропадать под влиянием каких-либо внешних факторов (помех на линии связи). Постепенное удаление узлов сети друг от друга с течением времени также может привести к ухудшению качества связи. Это приводит к тому, что исходные данные неточные и могут варьироваться по определенному закону или же случайным образом. Для достижения цели управления подобными системами целесообразно принимать решения последовательно либо применять методы, которые позволили бы стабилизировать систему.
Целью данной работы является разработка алгоритмов и соответствующего программного обеспечения для выбора оптимальных маршрутов в графах в условиях двухкритериальности и динамичности системы, то есть когда веса дуг являются векторными и неточными, а вершины могут быть мобильными. Задача заключается в том, чтобы проверить устойчивость парето-оптимального множества решений к небольшим возмущениям.
В работе рассматриваются следующие алгоритмы:
1) Алгоритм выбора путей в графе по нескольким критериям с использованием линейной свертки критериев. В данном случае критерии аддитивны и минимизируются. Задача состоит в том, чтобы исследовать влияние распределения вектора значимости критериев на решение двухкритериальной задачи.
2) Алгоритм выбора путей в графе по двум критериям (стоимости и пропускной способности) при неточных данных по принципу максимина. В данном случае первый критерий аддитивный и минимизируется, а второй критерий неаддитивный и максимизируется.
3) Алгоритм выбора путей в графе при неточных данных по двум критериям - стоимости и надежности, когда надежность дуги представлена как вероятность ее существования в графе. В данном случае оба критерия аддитивные, при этом первый минимизируется, а второй максимизируется.
Для ситуации, когда исходные данные варьируются случайным образом и известна соответствующая вероятностная матрица, реализован метод стабилизации системы для последующего выбора оптимального маршрута с помощью одного из предложенных алгоритмов.
Также в работе проводятся исследования, позволяющие отследить влияние порядка, размера графа и других дополнительных параметров, зависящих от выбранного алгоритма, на решение задачи.
В ходе написания данной работы был проведен анализ предметной области и обзор литературы по направлению исследования, выявлены основные существующие на сегодняшний день подходы к решению двухкритериальной и многокритериальной задач в статических и динамических системах. Сформулирована постановка задачи. Проведен комплексный анализ проблемы поиска оптимальных путей в графах с неточными данными с векторным критерием.
Для решения поставленной задачи был применен математический аппарат теории графов. Реализовано несколько алгоритмов для решения задачи выбора пути в графе по двум критериям при неточных данных.
В качестве алгоритма поиска кратчайшего пути использован алгоритм Дейкстры. Задача была решена комбинацией методов линейной свертки критериев (оба критерия аддитивны и минимизируются) и стабилизации динамической системы, а также с помощью алгоритма на основе принципа максимина по двум критериям: стоимости и пропускной способности (первый критерий аддитивный и минимизируется, а второй критерий неаддитивный и максимизируется), и алгоритма решения задачи по двум критериям: стоимости и надежности, когда надежность дуги представлена в виде вероятности ее существования в графе (оба критерия аддитивные, при этом первый минимизируется, а второй максимизируется).
На основе разработанной архитектуры системы было создано программное обеспечение, решающее поставленную задачу с использованием обозначенных выше алгоритмов. Приложение написано на языке программирования C# в среде разработки Visual Studio версии 2017 от компании Microsoft с использованием методологии объектноориентированного программирования.
Проведено исследование влияния на решение задачи порядка и размера графа, а также других параметров, в зависимости от типа решаемой задачи и, соответственно, выбранного алгоритма.
Исследование влияния распределения вектора значимости критериев на решение двухкритериальной задачи показало, что в случае, когда с изменением распределения вектора значимости критериев вес оптимального пути между заданной парой вершин меняется согласно линейному закону, решение устойчиво, то есть маршрут между заданной парой вершин является постоянным.
Проведено исследование устойчивости парето-оптимального множества решений возмущениям. Сделан вывод, что оно устойчиво к малым возмущениям в системе. Проведенные эксперименты подтверждают предположение, что для достижения цели управления динамическими системами решения целесообразнее принимать последовательно, а не однократно. Сделан вывод, что эффективнее решать задачу выбора пути в подобных системах путем их стабилизации.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
