Блох Илья Игоревич, Дураков Андрей Викторович пгниу, ул. Букирева, 15 Аннотация Вданной статье описано решение

Вид материала

Решение

Содержание Поиск маршрута Релевантность объекта Полезность маршрута Генетический алгоритм P – полезность маршрута t Архитектура приложения База данных

Подобный материал:

• Механизм воздействия инфразвука на вариации магнитного поля земли, 48.07kb.
• Вданной статье проведен исторический обзор развития индустрии моды как отрасли производства, 66.81kb.
• И. Г. Митченков Современное философское знание постоянно обращается к проблеме среды, 105.34kb.
• Виртуалтрединг: новая мета-архитектура вычислительных, 19.57kb.
• Ассоциации Эрнста Блоха (Нюрнберг, фрг) и Центра Эрнста Блоха (Людвигсхафен, фрг) Cодержание, 3974.03kb.
• Форточка (приквелл), 1837.09kb.
• «Целуют всегда не тех», 18.07kb.
• Минэкономразвития Андрей Шаров. Мы приняли решение, 15.89kb.
• Касьяненко Андрей Викторович, 24.86kb.
• Степаненко Андрей Викторович депутат Совета депутатов Новосибирского района Новосибирской, 25.13kb.

УДК 004.021+004.81

МОБИЛЬНОЕ ПРИЛОЖЕНИЕ ТУРИСТА НА ОСНОВЕ АЛГОРИТМА ПОСТРОЕНИЯ МАРШРУТА ПО ПАРАМЕТРАМ

Блох Илья Игоревич, Дураков Андрей Викторович

ПГНИУ, ул. Букирева, 15

Аннотация

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

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

Введение

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

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

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

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

Поиск маршрута

Для построения подходящего маршрута необходимо определить те факторы, которые определяют насколько туристический маршрут подходит человеку. Турист всегда имеет ограниченное время, но за это время он хочет посетить как можно больше интересных для него мест. Из этого вытекают два важных фактора, определяющих подходящий маршрут. Первый – это время, необходимое для его прохождения, которое напрямую следует из ограниченности времени туриста

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

Таким образом, возникают следующие задачи:

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

Вычисление релевантности и полезности маршрута

Релевантность объекта

Каждому объекту на карте можно поставить в соответствие набор описывающих тегов, всё множество которых разбито на тематические словари. Пользователь имеет возможность указать несколько интересующих его тегов. Таким образом, вычисление релевантности будет основываться на поиске подходящих объектов при помощи тегов. При этом будет необходимо учитывать как непосредственные совпадения по тегам пользователя и объекта, так и их принадлежность одному словарю.

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

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

1. Является тегом объекта, то есть полное совпадение.
   
2. Не является тегом объекта, однако принадлежит тому же словарю или словарям тегов, что и некоторые из принадлежащих объекту. Данную ситуацию можно рассматривать как косвенную близость, при которой объект тематически пользователю подходит, однако полного совпадения нет.
   
3. Не находится среди тегов объектов и не принадлежит ни одному из словарей, в который входят теги объекта.
   

За каждый случай полного совпадения (ситуация 1) значение близости увеличивается на некоторую величину _, при косвенной близости (ситуация 2) на величину за попадание в один словарь, а в случае ситуации 3 значение близости не увеличивается. Оптимальное значение будет определено уже во время тестирования приложения. Таким образом, если пользователь ввел N тегов, из которых
подходят к случаю 1, к случаю 2 и к случаю 3, при этом для тегов из второго случая имеет место _ попаданий в словари тегов, то значение близости будет равно

(1)

Полезность маршрута

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

Предлагаются следующие варианты расчета полезности P:

1. _ (2)
   

Полезность маршрута равняется самому высокому значению релевантности из входящих в маршрут объектов. Использование формулы (2) будет соответствовать принципу, согласно которому туриста нужно обязательно провести через максимально релевантный для него объект. Однако использование такого способа расчёта является неперспективным, так как согласно нему достаточно включить единственный, самый релевантный объект в маршрут. Поэтому данный способ расчёта полезности применяться не будет.

2. _ (3)
   

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

Генетический алгоритм

Алгоритм, предлагаемый для решения задачи – классический генетический алгоритм [].

Ранее проведённые исследования показали высокую эффективность генетического алгоритма для решения задачи построения маршрута по параметрам [].

Предлагается следующая функция приспособленности в решаемой задаче:



P – полезность маршрута

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

– время, которым ограничен пользователь



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

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

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

Реализация мобильного приложения

Архитектура приложения

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

Во-первых, необходимо хранить информацию об объектах карты, о тегах и словарях тегов, о пользователях приложения, поэтому база данных является неотъемлемой частью приложения.

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

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

Таким образом, для реализации приложения была выбрана клиент-серверная архитектура. Общая схема архитектуры представлена ниже на рис.1



Рис.1. Архитектура приложения

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

База данных

Для построения маршрута в базе данных должна размещаться информация о словарях тегов и самих тегах, а так же об объектах карты. Структура основы базы данных представлена ниже на рис.2



Рис.2. Структура базы данных

Как видно из рис.2, основными характеристиками каждого объекта являются его имя, координаты и время, необходимое для его посещения туристом. Также каждому объекту поставлено в соответствие некоторое количество тегов. Все теги, хранимые в базе данных, разделены на тематические словари.

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

База данных была написана на Microsoft SQL Server 2008. Эта СУБД была выбрана ввиду лёгкости интеграции в среду Microsoft Visual Studio и возможностей автоматической генерации классов из таблиц для последующего использования языка Linq для работы с записями в базе данных.

Сервер

Серверная компонента приложения должна взаимодействовать с базой данных и с клиентом. Архитектура сервера представлена на рис.3:



Рис.3. Архитектура сервера

Ключевые особенности:

• Для взаимодействия с базой данных используется язык запросов Linq.
  
• Для взаимодействия с клиентом на сервере реализован веб-сервис средствами ASP.NET.
  

Реализованный веб-сервис предоставляет единственный веб-метод GetPoints, сигнатура которого описана на рис.3. Этот веб-метод доступен для удалённого вызова. В нём реализован перевод входных данных в формат, необходимый для подачи на вход функциям библиотеки route.dll, вызов этих функций и возврат клиенту результата работы. В библиотеке route.dll, как уже упоминалось ранее, реализован генетический алгоритм построения маршрута и некоторые вспомогательные функции.

Для тестирования работы серверной компоненты приложения, она была размещена на локальном сервере операционной системы Microsoft Windows 7.

Android-клиент

Клиентская компонента была реализована на мобильной платформе Google Android [,,].

Задачами клиентской компоненты является взаимодействие с пользователем и с сервером.

Для взаимодействия с пользователем в состав Android-приложения должны входить компоненты-деятельности, так как именно они используются для отображения графического интерфейса и обработки событий взаимодействия пользователя с ним.

Клиент должен иметь два экрана: один для отображения карты и работы с ней, второй для получения от пользователя информации об его предпочтениях. Из этого следует необходимость включения двух деятельностей в состав приложения.

Для взаимодействия с сервером используется вызов веб-метода.

Архитектура клиентской компоненты представлена ниже:



Рис.4. Архитектура клиента

Клиент использует ряд дополнительных библиотек, необходимых для работы с Google Maps и для организации вызова веб-метода сервера на основе стандарта SOAP.

Заключение

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

Была разработана клиент-серверная архитектура приложения, основными компонентами приложениями которой стали база данных, серверная и клиентская компоненты. Было представлено подробное описание структуры и функций каждой из них.

Все описанные компоненты приложения были запрограммированы, в результате было получено рабочее приложение:



Рис.5. Снимок экрана мобильного приложении, построившего маршрут


Библиографический список

1. Блох И.И. Разработка мобильного приложения туриста на основе алгоритмов подбора маршрутов по параметрам – 2011. – выпускная работа – 45 с.
   
2. Вороновский Г. К., Махотенко К. В., Петрашев С. Н., Сергеев С. А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. – Х.: ОСНОВА, 1997. – 112 с.
   
3. Голощапов А.Л. Google Android: программирование для мобильных устройств.- СПб.: БХВ-Петербург, 2010.- 448 с.: ил.+ CD-ROM – (Профессиональное программирование)
   
4. Mark L.Murphy Beginning Android 2.- 417 с.
   
5. Sayed Y. Hashimi, Satya Komatineni, Dave MacLean Pro Android 2. – 737 c.
   

Mobile application for tourist
based on the algorithm of route construction by parameters

Blokh Ilya Igorevich, Durakov Andrey Victorovich

Perm State University, Bukireva st. 15

Annotation

In this article there was described the solution of the problem of architecture development and programming application which is able to construct the most suitable for the user tourist route based on genetic algorithm.

The algorithm of route construction was described in the article as well as the architecture of the application and results of its development.