[ЗАСТАВКА] Настало время познакомиться с
еще одним семейством методов оптимизации, а именно — с генетическими алгоритмами.
Генетические алгоритмы моделируют процесс эволюции, поэтому содержат в себе
стадии генерации популяции и повторяемые стадии мутации, скрещивания и отбора.
Порядок стадий может варьироваться.
Давайте рассмотрим для начала дифференциальную эволюцию — это алгоритм,
который используется для оптимизации функции от вещественных переменных.
Для начала сгенерируем n случайных векторов и будем называть их в дальнейшем
«популяцией».
Теперь выберем какой-то вектор из популяции и выберем еще три случайных
вектора из популяции.
Два из этих случайных используем, чтобы посчитать между ними разность и в
направлении этой разности сдвинуться от третьего,
получив таким образом некоторый итоговый вектор, называемый «мутантным вектором».
Эта операция называется «операция мутации».
Дальше будем выполнять операцию скрещивания мутантного вектора и вектора,
который мы выбрали изначально.
Потомок должен обладать свойствами обоих родителей,
поэтому операция скрещивания может выполняться, например,
следующим образом: давайте пройдемся по всем координатам и с некоторой
фиксированной вероятностью p будем брать первого родителя и брать его координату,
а с вероятностью 1 − p будем брать координату от второго родителя.
После этого наступает стадия отбора.
Здесь у нас есть много вариантов, как ее провести.
Например, первый вариант — мы можем смотреть, стал ли сын лучше родителя.
То есть, стало ли значение функции меньше оттого,
что мы подставляем в нее вместо родителя — сына.
Если сын действительно лучше, то удаляем родителя из популяции и используем сына.
Второй вариант — это пройти по всем векторам из популяции,
применить скрещивание и мутации, сгенерировать еще
n объектов для популяции и потом уже из 2n объектов выбрать N лучших.
Походя по всей популяции,
выполняя стадии мутации, скрещивания и отбора,
и повторяя это до сходимости мы получаем метод оптимизации, который
находит какие-то достаточно хорошие значения функции, ну то есть те значения,
в которых она будет меньше, чем в начальных приближениях.
Теперь рассмотрим другой пример: если мы оптимизируем
функцию от векторов из ноликов и единичек.
В этом случае операция мутации из дифференциальной эволюции может
быть не очень хороша.
Ну хотя бы потому,
что у нас может получиться не вектор из ноликов и единичек.
Поэтому можно ее изменить: можно просто пройтись по всем
координатам и для каждой координаты с некоторой вероятностью делать изменения.
То есть вместо нолика сделать единичку, вместо единички сделать нолик.
Операция скрещивания остается без изменений.
Иногда применяются некоторые трюки для того,
чтобы методы основанные на эволюционных идеях, работали лучше.
Например, можно создавать несколько «островков» из разных популяций
и применять алгоритм для каждой популяции.
С ростом числа координат метод начинает работать резко медленней.
Это тоже нужно учитывать и не пытаться его применять в очень многомерных
пространствах.
Кроме того, стоит помнить, что операторы мутации и скрещивания бывают разными,
на эту тему есть много экспериментов и много статей,
которые может быть полезно изучать.
В Python можно использовать дифференциальную эволюцию в библиотеке
Scipy, в модуле optimize, а именно метод differential evolution.
Подведем итог.
Генетические алгоритмы — это методы оптимизации,
вдохновленные процессом эволюции.
Эти алгоритмы имеют множество вариаций, в зависимости от последовательности
стадий и от того, как реализовывать операции скрещивания, мутации и отбора.
Генетические алгоритмы можно использовать для задачи глобальной оптимизации,
и они не требовательны к гладкости функции.
Evgeniy Riabenko
Evgeny Sokolov
Victor Kantor
Emeli Dral
