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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определение грузооборота брутто на отделении
Расчет тонно-километров брутто производится в табл. 2.1. отдельно для груженых и порожних вагонов. Для расчета используются данные о величине тонно-километров нетто пробега груженых и порожних вагонов, а также среднем весе тары вагона (22т). Т-км тары груженого вагона рассчитываются как произведени ...

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

ООО «Модуль» на Российском транспортном рынке контейнерных грузоперевозок
Российский транспортный рынок в данный момент находится на стадии развития и становления, поэтому требует организации, по крайней мере частичной. Иностранные грузовладельцы, даже в большей степени, чем отечественные, стремятся найти такого участника перевозочного процесса, который возьмет на себя к ...