Генетические алгоритмы: объяснение

Эволюция создала глаза, крылья и мозг без всякого конструктора, просто сохраняя то, что работает, и изменяя это. Генетический алгоритм заимствует эту идею для решения задач на компьютере. Ему не нужно понимать задачу — достаточно отличать лучший ответ от худшего, и это делает его мощным инструментом, когда пространство возможных ответов слишком велико и слишком причудливо, чтобы искать в нём каким-либо другим способом.

Ракеты летят снизу поля в обход стены к зелёной цели; лучший полёт показан пунктирной линией
Ракеты летят снизу поля в обход стены к зелёной цели; лучший полёт показан пунктирной линией

Идея

В 1960-х и 1970-х годах Джон Холланд из Мичиганского университета превратил теорию Дарвина в алгоритм и описал его в книге «Adaptation in Natural and Artificial Systems» 1975 года. Примерно в то же время Инго Рехенберг и Ханс-Пауль Швефель в Германии разработали эволюционные стратегии для инженерного проектирования. Общий рецепт таков: поддерживать популяцию вариантов решения, оценивать их, позволять лучшим размножаться с изменениями и повторять это на протяжении многих поколений.

Джон Холланд, описавший генетические алгоритмы в книге Adaptation in Natural and Artificial Systems 1975 года.
Джон Холланд, описавший генетические алгоритмы в книге Adaptation in Natural and Artificial Systems 1975 года.

Гены и популяция

Каждый вариант описывается хромосомой — списком генов. В песочнице гены ракеты — это её толчки, по одному на каждый момент полёта; в других задачах это могут быть биты числа, порядок городов на маршруте или размеры деталей конструкции. Первое поколение случайно: оно широко охватывает пространство ответов, но хороших ответов среди них почти нет.

Функция приспособленности

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

Отбор

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

Скрещивание и мутация

Скрещивание объединяет двух родителей: здесь потомок берёт первую часть генов от одного родителя, а остальное — от другого, так что ранние манёвры одной ракеты могут встретиться с поздними манёврами другой. Мутация случайно заменяет несколько генов. Скрещивание перекомбинирует то, что в популяции уже есть; мутация приносит то, чего в ней никогда не было. Теорема о схемах Холланда описывает, как короткие строительные блоки из хороших генов распространяются по популяции при таком сочетании отбора и рекомбинации.

Элитизм, исследование и эксплуатация

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

Локальные оптимумы

Генетический алгоритм следует только приспособленности, поэтому его можно обмануть. Когда путь к лучшему ответу сначала ведёт через худшие, популяция взбирается на ближайший холм и остаётся там: это локальный оптимум. За ступенчатыми стенами в песочнице ракеты, разбивающиеся под целью, получают более высокую оценку, чем ракеты, которые сворачивают в сторону, чтобы найти проём, поэтому популяция скапливается у стены. Помогают более крупные популяции, более частые мутации, поддержание разнообразия популяции и прежде всего более удачная функция приспособленности.

Попробуйте сами

Откройте песочницу генетического алгоритма и наблюдайте эволюцию ракет, облетающих одну стену, проём, столбы, ступенчатые стены или стены, нарисованные вами. Меняйте популяцию, частоту мутаций, время жизни и способ отбора, включайте и выключайте элитизм и следите на графике, как быстро растёт доля ракет, достигающих цели, — или почему она не растёт.

Часто задаваемые вопросы

Является ли генетический алгоритм разновидностью искусственного интеллекта?

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

Всегда ли генетический алгоритм находит лучший ответ?

Нет. Это эвристика: обычно он находит хорошие ответы на трудные задачи, но не гарантирует нахождения лучшего и не доказывает, насколько близко к нему подошёл. Для задач, где точный метод достаточно быстр, лучше использовать этот метод.

Чем генетический алгоритм отличается от эволюционных стратегий?

Оба относятся к эволюционным алгоритмам. Классические генетические алгоритмы делают упор на скрещивание строкоподобных хромосом; эволюционные стратегии работают в основном с мутациями вещественных чисел и часто по ходу дела подстраивают величину собственных мутаций. Современные методы сочетают идеи обоих подходов.

Почему поначалу ракеты такие неуклюжие?

Их первые гены — совершенно случайные толчки, поэтому в среднем они гасят друг друга, и ракеты просто дрейфуют. Согласованные полёты появляются только после того, как отбор сохранит редкие ракеты, которые случайно толкали себя примерно в нужную сторону, а скрещивание объединит их удачные участки.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Открыть песочницу генетического алгоритма