ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 5, с. 127-136
^ ИСКУССТВЕННЫЙ
ИНТЕЛЛЕКТ
УДК 004.8
ИСПОЛЬЗОВАНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ АВТОМАТИЧЕСКОГО ПОСТРОЕНИЯ КОНЕЧНЫХ АВТОМАТОВ
В ЗАДАЧЕ О ФЛИБАХ
© 2007 г. П. Г. Лобанов, А. А. Шалыто
Санкт-Петербург, Санкт-Петербургский государственный ун-т информационных технологий механики
и оптики
Поступила в редакцию 09.01.07 г., после доработки 28.05.07 г.
Предложен новый генетический алгоритм для решения задачи о флибах, которые моделируют поведение простейшего живого существа в простейшей среде. Выполнены вычислительные эксперименты, демонстрирующие эффективность этого алгоритма по сравнению с известным.
Введение. Существуют сложные задачи, которые эффективно решаются с помощью конечных автоматов [1]. В большинстве случаев синтез автоматов в них выполняется эвристически. Поэтому весьма актуально решение проблемы формализации методов построения автоматов, а также автоматизации этих методов. Известен класс задач (например, итерированная дилемма узников [2], "умный" муравей [3], синхронизация [4] и классификация плотности [5] для клеточных автоматов), в которых генетические алгоритмы [6] способны автоматически строить автоматы, решающие эти задачи. В настоящей работе рассматривается еще один представитель этого класса - задача о флибах [7, 8].
1. Задача о флибах. Это моделирование простейшего живого существа, которое способно предсказывать имеющие периодичность изменения простейшей окружающей среды. Живое существо моделируется конечным автоматом, а генетические алгоритмы позволяют автоматически построить автомат, который прогнозирует изменения среды с достаточно высокой точностью. Таким образом, требуется сформировать "устройство" (предсказатель), которое оценивает будущие изменения среды с наибольшей вероятностью. В [8] для решения указанной проблемы используется один из генетических алгоритмов. При этом точность предсказания реализованного автомата является недостаточно высокой. Это во многом связано с методом, применяемым для построения следующего поколения особей (автоматов). Цель статьи - разработка подхода, устраняющего указанный недостаток. Создана программа на языке С#, которая реализует как предлагаемый, так и известный подходы, что позволяет их сравнивать.
2. Постановка задачи. Одна из важнейших способностей живых существ - предсказание изменений окружающей среды. В качестве простейшей модели живого существа можно использовать ко-
нечный автомат. В [8] такие конечноавтоматные модели названы флибами (сокращение от finite living blobs - конечные живые капельки).
На вход флиба подается переменная, которая принимает одно из двух значений - ноль или единица. Эта переменная характеризует состояние окружающей среды в текущий момент времени. Среда настолько проста, что имеет только два состояния. Флиб изменяет свое состояние и формирует значение выходной переменной. Это значение соответствует возможному состоянию среды в следующий момент времени. Задача флиба - предсказать, какое на самом деле состояние окружающей среды наступит в следующий момент времени. Это можно выполнить благодаря периодичности ее изменений. При этом считается, что чем точнее флиб предсказывает изменения среды, тем больше у него шансов выжить и оставить потомство.
3. Схемы работы генетических алгоритмов в задаче о флибах. Приведем схемы работы известного и предлагаемого алгоритмов.
3.1. Известный алгоритм. Для поиска оптимального предсказателя в [8] применяется следующий генетический алгоритм.
1. Создается поколение случайных флибов.
2. Подсчитывается, сколько изменений состояний окружающей среды правильно предсказывает каждый из этих флибов.
3. Определяются худший и лучший предсказатели в поколении.
4. Лучший предсказатель скрещивается с фли-бом, выбранным случайным образом.
5. Случайным образом определяется необходимость применения к полученному флибу оператора мутации. Если это подтверждается, то указанный оператор применяется к флибу.
6. Худший предсказатель в поколении заменяется флибом, полученным в результате скрещивания.
Таблица 1. Флиб с тремя состояниями
Состояния 0 1
A 1, в 0, A
B 0, C 0, A
C 1, a 0, в
После выполненной замены считается, что новое поколение сгенерировано.
7. Если один из флибов достиг уровня предсказания, равного 100%, или пользователь остановил программу, то алгоритм прекращает работу. В противном случае переходим к п. 2.
Алгоритм создания случайных флибов, а также работа операторов одноточечного скрещивания и мутации будут подробно рассмотрены в разд. 4, 7, 8.
3.2. Предлагаемый алгоритм. В настоящей работе для генерации нового поколения используется метод, отличающийся от описанного в разд. 3.1. При этом применяется турнирный отбор [9] и принцип элитизма (в новое поколение добавляется одна или несколько лучших особей из предыдущего поколения) [10]. Число флибов в поколении будем называть размером поколения.
Предлагаемый алгоритм имеет следующий вид.
1. Создается текущее поколение случайных флибов.
2. Подсчитывается, сколько изменений состояний окружающей среды правильно предскажет каждый из этих флибов.
3. Строится новое поколение флибов:
a) создается пустое новое поколение и в него добавляется лучший предсказатель из текущего поколения;
b) случайным образом из текущего поколения выделяются две пары флибов;
c) из каждой пары выбирается лучший предсказатель;
ф лучшие предсказатели из указанных пар скрещиваются;
е) случайным образом определяется целесообразность применения оператора мутации к полученному флибу. Если это необходимо, то указанный оператор применяется к флибу;
1) флиб подвергается новой операции - "Восстановление связей между состояниями автомата";
g) флиб добавляется в новое поколение;
Ь) переход к п. Ь, если размер нового поколения меньше размера текущего поколения.
4. Текущее поколение флибов заменяется новым.
5. Если число поколений меньше заданного пользователем, то возвращаемся к п. 2.
4. Реализация флиба. Опишем известный и предлагаемый методы реализации флиба.
4.1. Известный метод. Поведение флиба задается с помощью таблицы переходов и выходов. В табл. 1 в качестве примера приведен флиб с тремя состояниями: A, B и C. Представим эту таблицу в виде строки: 1B0A0C0A1A0B, которая используется в [8]. Отметим, что число элементов в приведенной строке в 4 раза больше числа состояний флиба. Пронумеруем состояния флиба и элементы строки, задающей его. Первому состоянию и первому элементу строки присвоим номер ноль. Если флиб находится в состоянии с номером s и текущее состояний среды i, то состояние, в которое флиб перейдет, присутствует в элементе строки, задающей флиб. Этот элемент имеет номер 4 s + 2i + 1. Значение выходной переменной, генерируемой флибом, содержится в элементе с номером 4 s + 2i.
Для создания случайного флиба требуется задать значения элементов строки случайным образом. Приведем алгоритм создания случайного флиба, описанного строкой.
1. Цикл по всем элементам строки, задающей флиб:
a) если номер элемента четный, то элементу присваивается одно из возможных состояний среды, выбранное случайным образом;
b) в противном случае элементу присваивается одно из возможных состояний флиба, выбранное случайным образом.
4.2. Предлагаемый метод. В настоящей работе используется другой способ кодирования флиба, реализуемый с помощью трех классов -Flib, State и Branch, которые приведены в Приложении (листинг 1). В качестве главного класса при реализации флиба применяется класс Flib. Классы State и Branch реализуют его состояния и переходы соответственно. В каждом из этих классов имеется метод Clone, предназначенный для создания копий объектов.
Массив _states в классе Flib содержит состояния флиба. Поле _curStateIndex используется для хранения номера текущего состояния флиба в массиве _states. Число правильно предсказанных входных символов размещается в поле _guessCount. Метод Step переводит флиб в новое состояние и, при необходимости, изменяет количество правильно предсказанных символов. Метод Nulling возвращает флиб в начальное состояние и обнуляет число правильно предсказанных символов.
В массив _branches класса State включены дуги переходов из данного состояния. Номер элемента в массиве соответствует входной переменной. Переменные _stateIndex и _output класса Branch содержат номер состояния, в которое переходит флиб по этой дуге, и значение выходной переменной. Константа TARGET_COUNT определяет ко-
личества значений, которые может принимать выходная переменная, генерируемая флибом.
Опишем работу алгоритма создания случайного флиба.
1. Создаются объекты, соответствующие состояниям флиба.
2. Применительно к каждому объекту выполняется следующее:
a) для состояния формируются переходы из него;
b) для каждого перехода случайным образом определяются номер будущего состояния флиба и значение выходной переменной.
5. Генератор входного сигнала. В качестве входного сигнала для флибов (как и в [8]) используется повторяющаяся последовательность битов (битовая маска), задающая изменения состояний среды. Эта маска в программе зациклена. Код класса для генерации входного сигнала приведен в Приложении (листинг 2).
Массив символов, соответствующий битовой строке, передается в конструктор класса Simple-SignalSource. Свойства Input и InputNext возвращают входной символ для текущего и следующего моментов времени соответственно. Для перехода к следующему символу применяется метод DoStep, который необходимо вызвать до начала генерации входного сигнала. Метод Nulling сбрасывает генератор входного сигнала в начальное состояние.
6. Оценочная функция. Лучшим является тот флиб, который наиболее точно предсказывает входной сигнал. В качестве оценочной функции выступает количество правильно угаданных символов (поле _guessCount в классе Flib). После формирования нового поколения все флибы в нем устанавливаются в начальное состояние с помощью метода Nulling. Затем для определения приспособленности флибов каждому из них подается на вход несколько символов (по умолчанию их количество равно 100). После этого м
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.