Создание нового поколения с помощью кроссовера или мутации и рождение потомства
Выбор лучших особей для воспроизведения
Выбор фитнесс-функции и оценки для каждой особи в популяции
Инициализация популяции
На рис.1 показаны этапы генетического алгоритма, которые описываются следующим образом:
Генетический алгоритм техника поиска, позволяющая найти точные или приблизительные решения [3-10]. Она возникла из теории эволюции в природе. В 1975, Джон Х. Холланд разработал генетический алгоритм в книге под названием «Адаптация в Естественных и Искусственных Системах». Генетические алгоритмы широко применяются в различных приложениях, включая генную биологию, экономику, теорию игр, распознавание образов, нейронные сети, теорию нечетких множеств и т.д.
B. Генетический алгоритм
Алгоритм Дейкстры определяет кратчайший путь, когда веса ребер неотрицательны, что применимо к условиям системы навигации маршрута. Мы будем использовать алгоритм Дейкстры для поиска кратчайшего времени движения, когда число вершин не слишком велико. Время выполнения алгоритма Дейкстры, храня вершины в обычном связном списке, O (| V |2 + | E |), где | V | число вершин и | E | число ребер. Время работы становится неприемлемым, когда количество вершины слишком велико. В такой ситуации для нахождения приближенных решений могут быть использованы другие альтернативные методы. Генетический алгоритм один из них.
В теории графов, задача определения кратчайшего пути может быть обобщена как задача определения единственного кратчайшего пути от исходной вершины ко всем другим вершинам в графе. Известные алгоритмы для решения этой задачи: алгоритм Дейкстры и алгоритм Форда-Беллмана.
А. Задача определения кратчайшего пути
Остальная часть статьи организована следующим образом. В разделе 2 приводится справочная информация. В разделе 3 определена проблема определения минимального времени движения. Постановка эксперимента и результаты моделирования представлены в разделе 4. Раздел 5 содержит выводы.
Кратчайший путь, определяемый системами навигации маршрута не обязательно оптимальный путь, поскольку он рассчитывается главным образом по кратчайшему расстоянию, в то время как другие переменные, например, пробки, ограничения скорости, могут оказывать существенное влияние и должны быть включены в вычисления. Учитывая большое число переменных трафика вычислительные затраты могут занять слишком много времени и ресурсов портативных устройств. В общем случае, вычислительная мощность и память портативных устройств ограничена. Один из способов решить эту проблему, производить все расчеты на хост сервере, но связь между портативными устройствами и хост сервером может быть нарушена. Альтернативным методом является использование некоторого алгоритма, который может предоставить приблизительное решение со сравнительно низкими вычислительными затратами. В этой статье мы предлагаем использовать генетический алгоритм для поиска оптимального пути. Поскольку мы принимаем во внимание допустимые скорости движения транспортных средств, системы навигации маршрутов используют кратчайшее время движения, а не кратчайшее расстояние пути.
Стало обычной практикой использовать КПК для указания маршрута [1-2]. Как правило, кратчайший путь определяется системами навигации, чтобы сообщить пользователям, как достигнуть места назначения от исходного пункта. В зависимости от реальной ситуации, включая транспортные скопления, дорожные условия, ограничения скорости, и поведение водителей, на предложенном маршруте время пути может быть сэкономлено или нет.
Ключевые слова: генетический алгоритм, интеллектуальная транспортная система, оптимальный маршрут, портативное устройство, интеллектуальная система навигации
Чтобы решить эту проблему, мы предлагаем использовать генетический алгоритм для уменьшения роста вычислительных затрат. Мы используем генетический алгоритм для определения минимального времени движения с различными сценариями реальных условий дорожного движения и различной скоростью движения транспортного средства. Эффективность генетического алгоритма наглядно демонстрируется в применении на реальной карте современного города с очень большим числом вершин.
Система навигации маршрута, которая предоставляет рекомендации вождения, основанные на транспортной информации о начальной точке и месте назначения, стала очень популярной вместе с продвижением мобильных устройств и глобальной системы позиционирования. Так как точность и эффективность указания маршрута зависит от точности дорожной ситуации, система навигации должна включать в расчет дополнительные переменные, такие, как транспортные потоки в реальном времени и допустимые скорости движения транспортных средств. Поскольку в системе навигации увеличивается количество рассматриваемых переменных, вычислительная стоимость также возрастает. Так как мобильные устройства имеют ограниченные ресурсы, не представляется возможным использовать их для вычисления точного оптимального решения с использованием некоторых известных алгоритмов, таких, как алгоритм Дейкстры, который обычно используется для поиска кратчайшего пути на карте с умеренным числом вершин.
Перевод с английского: Казакова Ю. С.
Авторы: Chu-Hsing Lin, Jui-Ling Yu, Jung-Chun Liu, Chia-Jen Lee
ГЕНЕТИЧЕСКИЙ АЛГОРИТМ ДЛЯ ОПРЕДЕЛЕНИЯ МИНИМАЛЬНОГО ВРЕМЕНИ ПУТИ В ИНТЕЛЛЕКТУАЛЬНЫХ ТРАНСПОРТНЫХ СИСТЕМАХ
Chu-Hsing Lin, Jui-Ling Yu, Jung-Chun Liu, Chia-Jen Lee. Генетический алгоритм для определения минимального времени пути в интеллектуальных транспортных системах
Комментариев нет:
Отправить комментарий