Введение 5
1 АНАЛИЗ ТЕХНОЛОГИЙ ПОИСКА КРАТЧАЙШЕГО ПУТИ 7
1.1 Описание исследуемой задачи 7
1.2 Анализ существующих решений 11
2 ПРОЕКТИРОВАНИЕ АЛГОРИТМА ДЛЯ ПОИСКА КРАТЧАЙШЕГО ПУТИ 20
2.1 Анализ и выбор алгоритма 20
2.2 Общая структура алгоритма 21
2.3 Анализ реализованного алгоритма 35
3 АНАЛИЗ И ВЕРИФИКАЦИЯ ПОЛУЧЕННЫХ ДАННЫХ 55
3.1 Проведение вычислительного эксперимента 55
3.2 Корректировка разработанного алгоритма 56
Заключение 59
Список используемой литературы и источников 61
Приложение А Листинг программы
В современных городах, особенно в крупных, чтобы добраться из одной точки в другую, можно воспользоваться несколькими вариантами маршрута. Если человеку некуда спешить, то можно выбрать любой из них, а что, если наоборот: ему необходимо добраться до назначенного пункта как можно быстрее или выбрать наиболее дешевый маршрут? В таком случае ему предстоит просмотреть несколько маршрутов вручную и выбрать наиболее подходящий вариант.
Для решения таких транспортных задач используются приложения, которые автоматически строят маршрут до указанного места. Однако они чаще всего предоставляют своим пользователям самые короткие маршруты, но это не значит, что они самые быстрые или же менее затратные.
Просчет маршрута с учетом не только расстояния, но и затраченного на него времени, а также средств - это труднореализуемая чисто математическая задача. Для решения такого рода задач часто применяют эволюционные алгоритмы [15][13].
Эволюционные вычисления основаны на идеи применения дарвинской эволюции к компьютерной программе, концепция выживания которой заключается в том, что выживает наиболее приспособленная особь. Задачей эволюции является с помощью случайных мутаций в результате прийти к решению задачи с нужной точностью [1][14][12].
Эволюционные алгоритмы разделены на несколько видов:
- генетические алгоритмы;
- эволюционное программирование;
- программирование экспрессии генов;
- дифференциальная эволюция;
- нейроэволюция.
Все они используют базовые эволюционные этапы - отбор, скрещивание и мутации. Поведение особи (агента) определяется окружающей средой в результате чего определяется его пригодность к ней. Особи с подходящей приспособленностью участвуют в размножении, формируя следующее поколение (популяцию). Такие алгоритмы относятся к адаптивным поисковым механизмам [24].
Эволюционные алгоритмы используются при поиске оптимального решения задачи в конечном множестве решений, например при решении NP- трудных задач, таких как задача коммивояжера, задача упаковки ранца и зарисовка графов. NP-трудные задачи - это задачи, оптимальное решение которых невозможно вычислить за разумное время никакими способами и методами, но с помощью эволюционных алгоритмов стало возможным получение приблизительного оптимального решения. Обычно оптимальность полученного результата оценивается приспособленностью, которая должна быть не ниже установленного значения. Наглядным примером успешности работы эволюционных вычислений является космическая антенна NASA. Задача состояла в определении формы антенны такой, чтобы передаваемый ею сигнал был как можно лучше. Ее пытались решить точными методами, но только эволюционный алгоритм смог найти оптимальную форму [17].
Объект исследования - поиск оптимального маршрута.
Предмет - разработка алгоритма поиска оптимального городского маршрута с использованием эволюционных вычислений.
Целью данной выпускной квалификационной работы является проектирование и разработка алгоритма маршрутизации в городских условиях с использованием эволюционных вычислений.
Для решения задач маршрутизации используют различные алгоритмы, которые наиболее всего подходят к поставленной задаче. Известно, что эволюционные алгоритмы используются в решении NP-сложных задач, включая задачи маршрутизации. А в поиске кратчайшего пути активно используют модифицированный алгоритм Дейкстры. В литературе можно найти сильные и слабые стороны этих алгоритмов, но нигде не приводятся результаты сравнения в их производительности на одинаковых задачах - обычно эволюционные алгоритмы сравниваются только между собой. Среди эволюционных алгоритмов мною был выбран генетический и на задаче поиска кратчайшего пути его производительность сравнивалась с активно используемым в решении таких задач алгоритмом Дейкстры.
Генетический алгоритм, как было выяснено в результате исследований, сильно зависит от параметров и даже небольшое изменение одного из них может привести как к сильному ухудшению, так и к улучшению полученных решений. Влияние начальных параметров хорошо заметно на популяциях, полученных в результате имитации эволюции начальной популяции, которая в моей работе генерировалась случайными значениями, где каждая особь популяции хранила в себе лучшие, по ее мнению, маршруты, хранящиеся у нее в хромосоме. На основе этих хромосом выбирались лучшие, т. е. более приспособленные по мнению алгоритма особи, которые с заданной вероятностью могли скрещиваться, а затем с некоторой вероятностью могла происходить мутация полученных новых особей. Вероятности мутации и скрещивания также сильно влияют на результирующий ответ. Чем больше популяций и особей в них, тем больше вероятность получения хорошего результата. Тем не менее, если задача состоит в поиске оптимального пути для, например, 20 и более городов, то возникает задача коммивояжера, с решением которой генетический алгоритм покажется себя лучше Дейкстры.
На основе полученных в результате тестирования оценки производительности генетического алгоритма в дальнейшем можно будет его усовершенствовать, чтобы ускорить его работу с сохранением точности полученных решений. Например, можно будет добавить в программу многопоточность, чтобы оказалось возможным обрабатывать несколько переменных (особей в популяции) за раз. Еще одним вариантом его усовершенствования можно быть внедрение в него частей других алгоритмов (гибридизация) и внесение в него модификаций, как было сделано с алгоритмом Дейкстры в таких приложениях как Google Maps, Apple maps, OpenStreetMap, Яндекс.Карты и многих других. Возможно, добавление сильной стороны генетического алгоритма в алгоритм Дейкстры в качестве модификации поможет ускорить его еще больше, особенно в тех моментах, когда решение задачи может быть не очевидным (т. е. невозможно получить точный ответ), либо же ее расчет займет настолько много времени, что достаточным будет получение приблизительно оптимального решения.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
