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

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

Страница 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разработка технологического процесса и технологии ремонта по смене автосцепки при текущем отцепочном ремонте
1) Подача вагона на рем.путь 2) Контрольный обмер шаблонами 3) Подтверждение выявленных дефектов 4) Ремонт 5) Снятие неисправной автосцепки 6) Постановка исправной автосцепки 7) Испытание автосцепки и ее механизма 8) Приемка Конструкция автосцепки СА-З Автосцепка СА-З (рис.2) является тягово-ударно ...

Порядок разработки графика движения поездов
Вначале на графике движения поездов прокладываются пассажирские и пригородные поезда согласно заданному расписанию и заданному размеру движения. Рис. 13. Диаграмма следования пассажирских поездов. Скорые поезда следуют без остановок на промежуточных станциях, а на технической станции Е стоянка 10 м ...

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

Навигация

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