Введение
Игра жизни Конвея - это клеточный автомат, у которого есть пара простых правил:
- Любая живая клетка с менее чем двумя живыми соседями умирает, как если бы она была недостаточной.
- Любая живая клетка с двумя или тремя живыми соседями доживает до следующего поколения.
- Любая живая клетка с более чем тремя живыми соседями умирает, как будто от перенаселения.
- Любая мертвая клетка с ровно тремя живыми соседями становится живой клеткой, как бы в результате размножения.
Эти, казалось бы, простые рекомендации могут привести к общему сложному эмерджентному поведению.
Пару лет назад Kaggle запустил соревнование, целью которого было перевернуть стрелу времени в Game of Life. Вам дается крайняя доска 20x20, и вас просят предсказать начальную доску, которая при развитии будет максимально напоминать состояние конечной доски. Метрика, используемая для оценки, - Средняя абсолютная ошибка: для каждой доски количество правильно угаданных состояний ячеек делится на общее количество ячеек. Хотя некоторые люди изучали эту проблему, неизвестно, насколько сложно это будет, а также какие успешные подходы к этой проблеме.
Как вы уже, наверное, догадались, мы будем использовать Генетический алгоритм. Это метаэвристика для решения задач оптимизации и поиска. Чтобы использовать его, необходимо выполнить два основных требования:
- Домен решения должен иметь генетическое представление (т. Е. Можно определять мутацию, кроссовер и другие операторы для возможных решений)
- Функция пригодности должна быть определена для оценки возможных решений
Ниже мы рассмотрим детали реализации нашего решения GA.
Генетический алгоритм
Написанный псевдокодом, весь алгоритм выглядит так:
Прежде чем двигаться дальше, нам нужно написать функцию, которая будет выполнять «шаг вперед» в соответствии с правилами Game of Life:
Инициализация популяции
Каждый человек представляет собой доску размером 20x20 пикселей, представляющую кандидатную стартовую конфигурацию. Каждая ячейка имеет равные шансы быть «живой», и мы продвигаем всю доску на пять итераций (известных в документации по испытаниям как «шаги разогрева»), чтобы соответствовать распределению конкурентов.
Игрушечная проблема
Для оценки кандидатов нам нужна актуальная проблема. Этот фрагмент кода сгенерирует доску с парой планеров, жабой и двумя маяками. Затем мы продвигаемся на три шага вперед и будем искать решение для получившейся конечной платы.
Фитнес-функция
Затем мы определяем функцию приспособленности для оценки индивидуального решения и функцию оценки совокупности для оценки совокупности в целом.
Давайте определим экземпляр начальной популяции как таковой: population = generate_population(10, random_state=42). Для нашей проблемы с игрушкой score_population вернет [0.7825, 0.775, 0.745, 0.7025, 0.755, 0.82, 0.74, 0.845, 0.835, 0.775].
Выбор
Оператор отбора отвечает за отбор лучших людей для перехода в следующее поколение. Чтобы больше походить на естественный отбор, мы по-прежнему допускаем небольшой шанс для неоптимальных особей продолжать жить и спариваться.
В нашем примере сохраняются только лица с такими оценками: [0.845, 0.835, 0.82, 0.7825, 0.775, 0.775, 0.755, 0.745].
Мутация
Оператор мутации внесет случайную изменчивость в нашу популяцию. Он делает это путем случайного выбора ячеек и переключения их состояния. В сочетании с оператором выбора это заставит наш алгоритм выполнять оптимизацию на подъеме.
Кроссовер
Оператор кроссовера рекомбинирует два гена, моделируя спаривание двух особей. В результате получается двое детей, каждый с половиной генов (состояний клеток) от отца, а другая половина - от матери.
Шаг эволюции
Теперь, когда у нас есть все необходимое для выполнения шага эволюции, давайте объединим его в одну функцию. Он берет популяцию, выполняет отбор, мутацию и кроссовер и возвращает следующую популяцию.
Решать
В качестве последнего шага мы напишем функцию для решения конкретного примера, показывая прогресс в процессе.
Вот пример решения с оценкой пригодности 0.9675, полученной путем выполнения описанного выше алгоритма для 3000 поколений и с population_size=600.
Вывод
Применяя этот алгоритм к test.csv, предоставленному в соревновании Kaggle, мы получаем средний показатель пригодности 0.94 и, следовательно, 0.06 ошибку MAE.
Это поставило бы нас на первое место в таблице лидеров соревнований, с большим отрывом обойдя лучших участников. К сожалению, оптимизированная здесь метрика оценки отличается от метрики, используемой для оценки отправки Kaggle. Если вы знаете, почему это так, свяжитесь с нами, чтобы мы могли улучшить наш подход. Вы можете найти наше полное решение, а также код к этой статье (ga_tutorial.ipynb) в нашем репо.
