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

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

Страница 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

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

Расчет конструктивных элементов
Расчет пружины В основу типового расчета пружины сжатия – растяжения положено допущение, что нагрузка направлена по оси пружины. При этих условиях силы, приводятся к поперечной силе Р, изгибающей вито к моменту Мкр=РD/2, скручивающему виток. Изгиб силой Р играет второстепенную роль, основное значен ...

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

Отказы и неисправности изучаемого агрегата, их признаки, причины и способы устранения
АКПП F4AEL-K является довольно надежным, но дорогостоящим агрегатом. Поэтому долговечность и работоспособность АКПП напрямую зависит от правильной эксплуатации, основанной на своевременном техническом обслуживании данного агрегата. Качество смазки АКПП позволяет судить о характере неисправностей в ...

Навигация

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