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

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

Страница 2

Рисунок 1.1.2 Операция скрещивания

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

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

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

Рисунок 1.1.3 Мутация

После проведения всех этих операций заканчивается одно поколение генетического алгоритма и производится проверка на условие останова. Условием останова может быть, например, количество выполненных поколений или очень маленькая изменчивость наилучшего решения в нескольких популяциях. Если условие останова не соблюдено, то все операции генетического алгоритма повторяются заново с текущей популяцией. В противном случае наилучшее решение из текущей популяции принимается в качестве оптимального [1]. Схема работы генетического алгоритма представлена на рисунке 1.1.4.

Рисунок 1.1.4 Схема работы генетического алгоритма

Сильные стороны работы ГА:

практически полная независимость от характеристик пространства поиска;

малая зависимость от характера критерия оптимальности;

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

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

сложность реализации;

большая зависимость от выбора варианта кодирования хромосомы.

Метод восхождения

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

Но у данного алгоритма имеются некоторые недостатки. В первую очередь, алгоритм эффективен только для унимодальных функций, так как при работе этого алгоритма решение всегда «идет» вверх. Таким образом, если пространство поиска простое и содержит лишь один максимум, то мы всегда сможем найти оптимальное решение с помощью данного метода (Рисунок 1.1.5). В любом другом случае велика вероятность того, что алгоритм остановится в локальном минимуме, а глобальный максимум найден не будет (Рисунок 1.1.6). [1]

Рисунок 1.1.5 Случай нахождения максимума для унимодальной функции

Рисунок 1.1.6 Случай нахождения максимума для функции с локальными максимумами

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

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

надежность работы для унимодальных функций.

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

остановка в локальных минимумах, невозможность работы в случае, если пространство поиска имеет несколько минимумов;

неопределенное время поиска.

Динамическое программирование

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

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

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

Организация работ по очистке путей и уборке снега
Снегозаносимые участки пути характеризуются двумя признаками: категорией заносимости, зависящей от поперечного профиля земляного полотна; степенью заносимости, определяемой количеством снега, м3/м пути, приносимого к пути с вероятностью повторения один раз в 15—20 лет. Степень снегозаносимости учас ...

Определение массы и длины пассажирского поезда
Масса пассажирского поезда определяется по формуле: , (2.1) Где – мощность локомотива, л. с.; – масса локомотива в рабочем состоянии, т; – среднеходовая скорость движения пассажирского поезда, км/ч; и – основное удельное сопротивление движению соответственно локомотива и вагонов при заданной средне ...

Определение объемов работ
В данном разделе определяются объемы работ линейного характера (лесорубные, строительство автодороги и строительной связи), а также объемы работ по строительству временных поселков. Ширина полосы отвода принята равной 50 м по всей длине трассы. На первом перегоне протяженность зоны лесорубных работ ...

Навигация

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