Эволюционные алгоритмы – это семейство поисковых алгоритмов, вдохновленных процессом (дарвиновской) эволюции в природе. Общим для всех различных членов семейства является представление о решении проблем путем развития изначально
случайной популяции возможных решений посредством применения
операторов, вдохновленных естественной генетикой и естественным отбором, так что в
> Со временем появляются более подходящие (то есть лучшие) решения проблемы.
Эта область, истоки которой можно проследить до 1950-х и 1960-х годов, за последние два десятилетия добилась успеха в решении многочисленных задач из самых разных областей, включая (упомянем лишь некоторые): оптимизацию, автоматическое программирование, проектирование электронных схем, телекоммуникации, сети, финансы, экономика, анализ изображений, обработка сигналов, музыка и искусство.
Интересно, что исследователи, в том числе и я, обнаружили, что эволюционные алгоритмы можно выгодно сочетать с машинным и глубоким обучением. Подробнее об этом чуть позже.
Вот как выглядит базовый эволюционный алгоритм:
- создать первоначальную популяцию особей, последние из которых являются возможными решениями рассматриваемой проблемы.
- оценить пригодность каждого человека в соответствии с проблемой, решение которой требуется
- покаусловие прекращения не выполнено сделать
-выбратьподходящие особи для воспроизводства
- рекомбинировать (кроссовер) особей
- мутировать особей
- оценивать пригодность модифицированных особей
Давайте подведем итоги основных составляющих эволюционного алгоритма:
Геном (хромосома). Эволюционные алгоритмы по своей сути основаны на популяции. Индивидуум в популяции известен как геном или хромосома. Он может принимать различные формы, включая строки битов, векторы с действительными значениями, кодировки на основе символов, компьютерные программы и многое другое. Разработка представления, подходящего для рассматриваемой проблемы, имеет решающее значение для успеха эволюционного алгоритма.
Фитнес или фитнес-функция. Мера качества решения-кандидата в популяции. Правильное определение этой функции также имеет решающее значение для успеха эволюционного алгоритма.
Поколение. Одна итерация цикла while выше.
Выбор. Оператор, с помощью которого эволюционный алгоритм отбирает (обычно вероятностно) особей с более высокой приспособленностью для передачи генетического (точнее, «генетического») материала следующему поколению.
Кроссовер. Один из двух основных генетическихоператоров, при котором два (или более) решения-кандидата (родителя) объединяются заранее определенным образом для образования потомства.
Мутация. Второй основной генетический оператор, в котором случайно изменяется одно решение-кандидат.
Время для простого примера. Рассмотрим популяцию из 4 особей, которые представляют собой битовые строки (геномы) длиной 10. Значение приспособленности равно
количеству единиц в битовой строке. В реальных приложениях размер популяции и длина генома, конечно, больше.
Вычисление пригодности в этом случае чрезвычайно просто: достаточно подсчитать количество единиц у человека. Для реальных задач нам часто приходится выполнять сложные вычисления, чтобы получить значения пригодности.
Начальная случайная популяция может выглядеть следующим образом (значения приспособленности указаны в скобках): 0000011011 (4), 1110111101 (8), 0010000010 (2), 0011010000 (3).
Затем выбор может выбрать в качестве родительских пар: 1110111101 (8) с 0011010000 (3) и 0000011011 (4) с 1110111101 (8). Обратите внимание, что некоторые люди выбираются чаще, чем другие, а некоторые могут вообще не выбираться — отбор является вероятностным и зависит от пригодности. Чем выше приспособленность, тем выше вероятность быть выбранным в качестве родителя.
Оператор кроссовера меняет местами случайные фрагменты между парой родителей, за которым следует оператор мутации, который случайным образом переворачивает небольшое количество битов.
Как только мы сделали отбор-кроссовер-мутацию, мы получили новое поколение. В нашем случае это может выглядеть так: 1111010000 (5), 0010101101 (5), 0000011011 (4), 1110111111 (9). Ага, немного этого родителя, немного того родителя, немного переделок и вуаля — улучшенное решение с пригодностью 9 (тогда как раньше лучшим было 8).
Что теперь? Просто продолжайте чередовать поколения — отбор-кроссовер-мутация-приспособленность — пока не найдете достаточно хорошее решение. Возможно, даже оптимальный вариант.
Генетическое программирование. Теперь давайте сделаем вещи более интересными. Зачем развивать простые битовые строки? Одна из основных подобластей эволюционных алгоритмов называется генетическое программирование, в ней основное внимание уделяется использованию более сложных представлений. Традиционно это были вычислительные деревья, но с годами было предложено множество других представлений.
Вычислительное дерево выглядит так:
Я эволюционировалэто деревос помощью генетического программирования, и оно на самом деле вычисляет (рекурсивно) эквивалентное математическое выражение: x⁴ + x3 + x² + x + 1. Иногда эволюция дает результат. более сложные деревья, такие как:
Машинное обучение и глубокое обучение. Одно из основных преимуществ эволюционных алгоритмов, как я и другие обнаружили в последние годы, заключается в том, насколько хорошо они «играют» с машинным обучением и глубоким обучением — при разумном использовании.
Например, в условиях машинного обучения я разработал ряд классификаторов на основе эволюции, которые могли конкурировать с XGBoost, LightGBM и глубокой нейронной сетью. Вот полная статья.
В условиях глубокого обучения мы использовали так называемый коэволюционный алгоритм, в котором несколько популяций эволюционируют в тандеме, чтобы развить функции активации для глубоких сетей. Вместо того, чтобы использовать стандартный ReLU, сигмоид или что-то подобное, мы подключили развитые функции активации к глубоким сетям и показали, что их производительность увеличилась. Вот полная статья.
В области состязательного глубокого обучения исследователи изучают уязвимость глубоких моделей к атакам, пытаясь улучшить защиту моделей и разработать новые атаки. Небольшие изменения во входных изображениях, незаметные для нас, могут привести к ошибкам в сети.
В одной работе мы использовали эволюцию для создания физически правдоподобных враждебных патчей, которые являются эффективными и кажутся реалистичными — без использования градиентов. Мы использовали генераторы GAN (генеративно-состязательной сети). Учитывая предварительно обученный генератор, мы искали входной скрытый вектор, соответствующий сгенерированному изображению, который приводит к ошибке детектора объектов. Мы использовали (относительно) небольшую размерность скрытого пространства, аппроксимируя градиенты с помощью алгоритма Эволюционная стратегия, неоднократно обновляя входной скрытый вектор, запрашивая детектор целевого объекта, пока не будет обнаружен соответствующий враждебный патч.
Ниже мой талантливый аспирант Раз Лапид, стоящий рядом со своей второй половинкой, показывает, как развитая заплатка (печатная, то есть физическая) скрывает его от модели глубокого обучения (без ограничивающей рамки). Полная статья здесь.
Вы можете просмотреть мой веб-сайт для получения более подробной информации и полных документов.
Насколько сложно начать работу с эволюционными алгоритмами? Ну, я бы начал с одного из многих отличных пакетов. Я без тени смущения хочу порекомендовать проект, который я инициировал вместе с моими замечательными сотрудниками и аспирантами — EC-KitY:
У нас есть несколько целей для этого проекта, и поэтому EC-KitY:
- Полный набор инструментов для запуска эволюционных алгоритмов;
- Написано на Питоне;
- Может работать с scikit-learn или без него, то есть поддерживает как sklearn-режим, так и не-sklearn-режим;
- Разработан с учетом современной разработки программного обеспечения;
- Разработан для поддержки всех популярных парадигм эволюционных алгоритмов.
Вы можете запустить эволюционный алгоритм всего с 3 строками кода:
algo = SimpleEvolution(Subpopulation(SymbolicRegressionEvaluator()))
algo.evolve()
print(f'algo.execute(x=2,y=3,z=4): {algo.execute(x=2, y=3, z=4)}')
И EC-KitY также совместим с scikit-learn, как вы можете видеть в этом фрагменте кода:
X, y = make_regression(n_samples=100, n_features=3)
terminal_set = create_terminal_set(X)
algo = SimpleEvolution(Subpopulation(creators=FullCreator(terminal_set=terminal_set),
evaluator=RegressionEvaluator()))
regressor = SKRegressor(algo)
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
regressor.fit(X_train, y_train)
print('MAE on test set:', mean_absolute_error(y_test, regressor.predict(X_test)))
Позвольте мне закончить известной цитатой Чарльза Дарвина — заключительными строками книги Происхождение видов:
Есть величие в этом взгляде на жизнь, с ее несколькими силами, изначально вдохнутыми в несколько форм или в одну; и что, в то время как эта планета продолжала вращаться в соответствии с фиксированным законом гравитации, из такого простого начала развились и развиваются бесчисленные формы, самые красивые и самые удивительные.
