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

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

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

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

Определение суточной программы по ТО и диагностированию автомобилей
Суточная производственная программа является критерием выбора метода организации ТО и служит исходным показателем для расчета числа постов и линий ТО. По видам ТО (ЕО, ТО-1, ТО-2) и диагностированию (Д-1, Д-2) суточная производственная программа определяется по формуле: где ∑NiГ. — годовая пр ...

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

Определение норм периодичности выполнения ремонтно-путевых работ
Работы по техническому обслуживанию пути подразделяются на следующие основные виды: капитальный ремонт пути на новых материалах (); сплошная замена рельсов(на отдельных участках- по разрешению ОАО»РЖД»), сопровождаемая работами в объеме среднего ремонта пути ;капитальный ремонт пути на старогодных ...

Навигация

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