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

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

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

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

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

Определение общего пробега локомотива
В общий пробег локомотивов включается линейный пробег и условный пробег, который учитывает маневровую работу и простой локомотивов в рабочем состоянии. Объем маневровой работы и простоя в рабочем состоянии рассчитываются в локомотиво – часах. А затем переводят в локомотиво – километры по соотношени ...

Краткие сведения о хозяйстве ОАО “Племзавод им. М. Горького”
ОАО “Племзавод им. М. Горького” расположено в юго-восточной части Белебеевского района Республики Башкортостан. “Племзавод им. М. Горького” занимает – 6,6% общей площади Белебеевского района. Центр хозяйства расположен в населенном пункте Центральная Усадьба ПЗ имени М.Горького. Расстоние от Центра ...

Навигация

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