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

Рисунок 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 Случай нахождения максимума для функции с локальными максимумами

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

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

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

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

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

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

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

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

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

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

Особенности перевозок
К управлению автотранспортом допускаются лица, прошедшие спецподготовку, вводный инструктаж, инструктаж по пожарной безопасности, первичный инструктаж на рабочем месте, инструктаж по электробезопасности на рабочем месте. Особенностью перевозок в МУП САХ является то, что на всех «Мусоровозах» устано ...

Расчетно-технологическая часть
КамАЗ - 44108 МАЗ - 543203 1. Рассчитаем периодичность ТО и КР Периодичность ТО-1 L1= L1н ∙К1∙К3 (Л-1), где L1н – норма периодичности ТО-1 (км) К1 – коэффициент, учитывающий условия эксплуатации К3 – коэффициент, учитывающий климатические условия Периодичность ТО-2 L2= L2н ∙К1W ...