Разработка алгоритмов построения маршрута по параметрам

Блох Илья Игоревич – магистрант Пермского государственного национального исследовательского университета. (ПГНИУ, г.Пермь)

Дураков Андрей Викторович - старший преподаватель, заведующий лабораторией кафедры Математического обеспечения вычислительных систем Механико-математического факультета Пермского государственного национального исследовательского университета. (ПГНИУ, г.Пермь)

Аннотация: В статье рассматривается проблема составления наиболее подходящего пешего городского маршрута для туриста. Были определены свойства и способ построения подходящего маршрута. Далее предлагается несколько алгоритмов, составляющих маршрут: алгоритм на основе решения задачи коммивояжера и два генетических алгоритма, различающихся способом кодирования хромосом, а также критерии их оценки. Был сделан вывод о наиболее подходящем алгоритме для решения поставленной задачи на основе выбранных критериев.

Ключевые слова: Генетический алгоритм, маршрут, задача коммивояжера.

В наше время всё больше людей отправляется в туристические поездки в различные города мира, и часто перед ними встаёт вопрос о выборе подходящего для них пешего туристического маршрута по городу.

Задача выбора подходящего маршрута очень актуальна, как ввиду широкого круга заинтересованных в её решении лиц, так и ввиду отсутствия действующих приложений, способных эту задачу решить.

Современные способы построения туристических маршрутов имеют различные недостатки: недостаточный учет индивидуальных интересов туриста, низкая гибкость, дороговизна.

Были предложены различные методы построения наиболее подходящего для человека пешего туристического маршрута по городу[3].

Для нахождения подходящего маршрута последовательно решаются следующие задачи:
1. Предлагается способ вычисления релевантности каждого отдельного объекта города. Под релевантностью понимается численное выражение соответствия пожеланиям человека. Перед началом работы алгоритма интересы пользователя выражаются при помощи ключевых слов. На основе этих данных вычисляется релевантность для каждого объекта города как взвешенная сумма частот попадания ключевых слов в описание объекта:

2. Предлагается способ определения полезности маршрута. Полезность маршрута – некоторое численное выражение его содержания, основанное на совокупности релевантностей входящих в него объектов. Полезность маршрута полагается как сумма релевантностей вошедших в него объектов.

3. Предлагаются и сравниваются алгоритмы нахождения подходящего маршрута. Алгоритм, основанный на решении задачи коммивояжера [2], простой в реализации, показал хорошие результаты для тестов с небольшим объемом исходных данных. Однако если использовать данные, приближенные к реальным, лучшие результаты демонстрирует генетический алгоритм [1] со следующей функцией приспособленности в решаемой задаче:
,

где P- полезность маршрута
t – время, необходимое для прохода маршрута. Вычисляется при помощи жадного алгоритма решения задачи коммивояжера
tmax - время, которым ограничен пользователь

ε>0, ε≈0

Способ кодирования решения предлагается следующий: каждая особь кодирует набор объектов, которые содержатся в маршруте. Таким образом, количество генов совпадает с числом всех рассматриваемых объектов. Ген, стоящий на позиции с номером i в хромосоме может принимать значения 0 или 1. 0 означает, что объект с номером i не включен в маршрут, а 1 означает, что объект с номером i в маршрут включен.

Для сравнения алгоритмов использовались следующие критерии:
1. Итоговая полезность маршрута. Чем выше полезность маршрута, тем считается лучше работает алгоритм.
2. Разница между временем, заданным пользователем и временем, вычисленным алгоритмом. Эта разница должна быть как можно ближе к 0.
Было проведено несколько сравнительных тестов на основе базы данных достопримечательностей города Перми. В каждом из них фиксировались данные, получаемые от пользователя, и выбирались различные параметры алгоритмов. За каждый тест алгоритм решал задачу построения маршрута по городу фиксированное число раз.

Лучшие результаты показал генетический алгоритм со специальным способом кодирования хромосом, который устраняет проблему одноточечного кроссовера [3]. Разработанный алгоритм имеет сложность

,

где P – число особей в популяции,
G – число поколений, сменившихся за время работы алгоритма,
N – длина хромосомы,
M – количество объектов карты,
и следующие параметры: численность популяции 400 особей, вероятность мутации 0,3%, вероятность скрещивания 70%.

Список литературы:

1. Вороновский Г. К., Махотенко К. В., Петрашев С. Н., Сергеев С. А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. – Х.: ОСНОВА, 1997. – 112 с.
2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ / Пер. с англ. под ред. Шеня А. – М.: МЦНМО: БИНОМ. Лаборатория знаний, 2004. – 2-е изд., стереотип. – 960 с.
3. Блох И.И., Дураков А.В. Генетическии? алгоритм решения задачи построения маршрута по параметрам. Актуальные проблемы механики, математики, информатики: сб. тез. науч.-практ. конф. (Пермь, 30 октября – 1 ноября 2012 г.) / гл. ред. В.И. Яковлев; Перм. гос. нац. исслед. ун-т. – Пермь, 2012. – 195 с.

Интересная статья? Поделись ей с другими: