Оптимизация

Определение генетического алгоритма

Когда мы обсуждали, как можно оптимизировать сиБоты, мы упоминали, что сиБоты можно улучшать с помощью метода генетического алгоритма. В этом руководстве мы объясним, что это такое и как это работает.

Метод генетического алгоритма основан на теории естественного отбора. Эта теория утверждает, что только наиболее приспособленные особи выживают для последующего размножения.

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

Для работы генетическому алгоритму необходима начальная популяция. Чтобы создать ее, оптимизатор выполнит несколько различных прогонов со случайными параметрами. После создания начальной популяции алгоритм начнет процесс поиска наиболее приспособленного прогона оптимизации. Этот процесс продолжается до тех пор, пока показатели приспособленности дочерних прогонов не начнут стагнировать и сходиться. В этот момент алгоритм останавливается.

Этапы генетического алгоритма

Любой генетический алгоритм имеет следующие этапы.

graph TB
  B([Отбор]) ==> C([Скрещивание]);
  C ==> D([Мутация]);
  D ==> B;

Этапы объясняются следующим образом.

Отбор

На этом этапе алгоритм находит два наиболее приспособленных прогона оптимизации, используя их соответствующие показатели приспособленности.

Скрещивание

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

Мутация

На этом этапе алгоритм мутирует потомственные прогоны, случайным образом изменяя одно или несколько значений параметров.

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

В противном случае алгоритм увеличит свой счетчик стагнации. Если счетчик стагнации достигнет значения параметра периода стагнации алгоритма, процесс оптимизации будет автоматически остановлен.

Параметры генетического алгоритма

Генетический алгоритм имеет несколько параметров, которые он использует в течение своего жизненного цикла. Эти параметры нельзя изменить.