УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»

Использование генетических алгоритмов для автоматического построения конечного автомата в задаче о «флибах»

П.Г. Лобанов, А.А. Шалыто (СПбГУ ИТМО, Санкт-Петербург)

Статья в формате PDF
Исполняемая программа
Исходные тексты

Аннотация

Задача о флибах — это задача моделирования простейшего живого существа, которое способно предсказывать изменения простейшей среды, имеющие периодичность (среда имеет два состояния ноль и единица и задается битовой маской). Данное живое существо моделируется конечным автоматом, а генетические алгоритмы позволяют автоматически построить автомат, который предсказывает изменения среды с достаточно высокой точностью. На вход флибу подается текущее состояние среды. После этого флиб формирует выходную переменную, соответствующую возможному состоянию окружающей среды в следующий момент времени. При решении этой задачи требуется построить наилучший предсказатель.

В работе Воронина  О., Дьюдни  А. Дарвинизм в программировании //Мой компьютер. 2004. № 35 для решения указанной задачи используется один из генетических алгоритмов. При этом построенный автомат правильно предсказывает относительно небольшое число символов. Это во многом связано с подходом, используемым при построении следующего поколения (худший предсказатель в поколении заменяется на результат скрещивания лучшего предсказателя со случайно выбранным флибом). Цель настоящей работы — разработка подхода, устраняющего указанный недостаток. Для этого авторами применяется другой метод генерации нового поколения. Он основан на турнирном отборе и принципе элитизма. Дополнительная оптимизация достигается благодаря применению алгоритма восстановления связей между состояниями автомата.

Используемый в работе подход позволяет построить при одинаковом числе поколений лучший предсказатель, чем известный метод. Так, например, лучший флиб, полученный известным методом, после 400 поколений (при размере одного поколения 200), в среднем правильно предсказывает 81 символ из 100 для среды, изменения которой задаются битовой маской, представленной в виде: 1111010010111101001. При аналогичных условиях, лучший флиб, полученный в настоящей работе, в среднем правильно предсказывает 94 символа из 100.