Аналитический обзор существующих методов и подходов к планированию групповых действий

Информация » Разработка алгоритмов поиска оптимального маршрута для БЛА при наблюдении им подвижных наземных объектов » Аналитический обзор существующих методов и подходов к планированию групповых действий

Страница 1

Обзор существующих методов поиска оптимального маршрута при одиночном полете БЛА

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

Полный перебор

Полный перебор всех возможных вариантов является самым простым решением задачи. Этот метод решает задачу поиска оптимального маршрута «в лоб». Основой метода полного перебора является составление и расчет всех возможных последовательностей облета объектов. Данный метод всегда дает оптимальное решение задачи, однако требует для выполнения большого количества времени и вычислительных ресурсов БЦВМ. При этом с ростом числа объектов время решения задачи растет экспоненциально, так как количество возможных вариантов равно n!, где n – число объектов (рисунок 1.1.1).

Рисунок 1.1.1 Зависимость времени выполнения алгоритма от числа объектов

Сильные стороны:

простота реализации;

найденное решение всегда оптимально.

Слабые стороны:

Колоссальное время решения задачи.

Необходимость использования больших объемов памяти.

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

Генетические алгоритмы – метод оптимизации, который основан на принципах, наблюдаемых в природе. Они сочетают в себе такие качества, как высокая скорость работы, малая вероятность остановки в локальных минимумах пространства поиска. Работа генетических алгоритмов основана на принципах естественного отбора и использует множество понятий и определений, заимствованных из генетики. Это такие понятия, как хромосома, ген, приспособленность, мутация, отбор, скрещивание и другие.

В начале работы алгоритма генерируется начальная популяция – набор особей, характеризуемых хромосомами. Каждая хромосома представляет собой строку. В этой строке закодирована информация о маршруте полета БЛА. Например, если у нас имеются 4 объекта, которые необходимо облететь, мы можем закодировать хромосому в виде двоичной строки таким образом, что каждые 2 бита будут представлять собой номер объекта в двоичном коде. От выбора кодировки хромосомы зачастую зависит эффективность применения генетического алгоритма. Например, в нашем случае, в результате работы алгоритма мы будем получать множество восьмибитных строк, большинство из которых не будут годиться для решения задачи, так как некоторые объекты будут учтены несколько раз, а некоторые могут быть вообще не учтены. Соответственно такой вариант кодирования можно считать не очень удачным.

После создания начальной популяции (обычно она создается случайным образом) следует отобрать некоторое число особей в качестве родителей для будущих поколений. Существует несколько алгоритмов выбора, однако самым популярным является правило рулетки. Рассмотрим его несколько подробнее.

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

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

Страницы: 1 2 3 4 5 6

Похожие статьи:

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

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

Оценка параметра масштаба закона Вейбулла-Гнеденко
Точечная оценка параметра масштаба закона Вейбулла-Гнеденко, рассчитывается по формуле, тыс.км: , (8) икарус трансмиссия безотказность двигатель где - гамма – функция по аргументу , который берется из табл.7 (Приложение В) в зависимости от коэффициента вариации . Значение гамма – функция определяем ...

Навигация

Copyright © 2019 - All Rights Reserved - www.localtransport.ru