В качестве примера, в котором автоматическое построение логики сущности со сложным поведением имеет решающее значение, рассмотрим одну из классических задач из области совместного использования генетических алгоритмов и конечных автоматов — задачу об «Умном муравье» Муравей «живет» на поверхности тора размером 32 на 32 клетки (рис. 4.4). В нескольких клетках (обозначены на рис. 4.4 черным цветом) находится еда. Она расположена вдоль некоторой ломаной, но не во всех ее клетках. Клетки ломаной, в которых нет еды, обозначены серым цветом. Белые клетки не содержат еду и не принадлежат ломаной. Всего на поле 89 клеток с едой.
В клетке, помеченной меткой Start, в начале игры находится муравей. Он занимает одну клетку и смотрит в одном из четырех направлений (север, юг, запад, восток). В начале игры муравей смотрит на восток. Муравей умеет определять, находится ли непосредственно перед ним еда. За один игровой ход муравей может совершить одно из четырех действий: сделать шаг вперед, съедая еду, если она там находится; повернуть налево; повернуть направо; ничего не делать. Съеденная муравьем еда не восполняется, муравей жив на протяжении всей игры, еда не является необходимым ресурсом для его жизни. Ломаная не случайна, а строго фиксирована. Муравей может ходить по любым клеткам поля.
Игра длится 200 ходов, на каждом из которых муравей совершает одно из четырех действий. По истечении 200 ходов подсчитывается количество еды, съеденной муравьем. Это значение и есть результат игры. Цель игры — создать муравья, который за 200 ходов съест как можно больше еды (желательно, все 89 единиц).Один из способов описания поведения муравья — автомат Мили, у которого имеется одна входная переменная (находится ли еда перед муравьем), а множество выходных воздействий состоит из четырех упомянутых выше элементов. Схема связей этого автомата приведена на рис. 4.5.Автомат, решающий описанную задачу, крайне трудно построить вручную. Например, эвристически построенный автомат Мили с пятью состояниями из работы , граф переходов которого изображен на рис. 4.6, задачу не решает — он описывает поведение муравья, который съедает всего 81 единицу еды за 200 ходов, а всю еду — только за 314 ходов. Эта задача была решена с применением генетических алгоритмов. При этом был построен автомат с восьмью состояниями. Ниже описывается алгоритм, предложенный в работе , который позволил построить для решения рассматриваемой задачи автомат с семью состояниями. Пусть представление автомата в виде особи состоит из номера начального состояния и описания каждого состояния. Описание (в терминах генетического программирования — хромосома) состояния содержит описания двух переходов, соответствующих двум значениям входной переменной. Описание перехода состоит из номера состояния, в которое он ведет, и действия, выполняемого на этом переходе. Начальное поколение содержит фиксированное число случайно сгенерированных автоматов. Все автоматы в поколении имеют одинаковое, наперед заданное число состояний. Теперь опишем генетические операторы мутации и скрещивания в терминах предложенного представления автоматов. При мутации случайно выбирается один из четырех равновероятных вариантов: изменение начального состояния — в этом случае новое начальное состояние выбирается случайно и равновероятно; изменение действия на переходе — случайно и равновероятно выбирается переход, и действие на нем изменяется на случайное; изменение состояния, в которое ведет переход,— случайно и равновероятно выбирается переход, после этого целевое состояние перехода изменяется на случайно выбранное; изменение условия на переходе — случайно и равновероятно выбирается состояние, после этого переходы из этого состояния, соответствующие различным значениям входной переменной, меняются местами. Оператор скрещивания принимает на вход две родительские особи, а результатом также являются две особи. При этом первый ребенок может наследовать начальное состояние от первого родителя, а второй — от второго, или наоборот. Что касается переходов из заданного состояния, каждый ребенок может наследовать как переход по значению входной переменной «истина», так и переход по значению «ложь» равновероятно от обоих родителей, но оба ребенка не могут наследовать один и тот же переход. Схема скрещивания изображена на рис. 4.7.где A — суммарное количество еды, съеденной муравьем за игру, T — номер хода, на котором муравей съедает последнюю единицу еды. С использованием приведенных выше генетических операторов и функции приспособленности удалось построить автомат с семью состояниями, который позволяет муравью съесть все 89 единиц еды за 190 ходов. Граф переходов этого автомата приведен на рис. 4.8. Для того чтобы найти этот автомат, потребовалось перебрать 130 000 поколений и 160 миллионов особей, что немного по сравнению с общим числом автоматов с семью состояниями, одной входной и четырьмя выходными переменными. Еще один автомат с семью состояниями был построен после перебора 250 миллионов особей, что также представляет незначительный процент от общего количества автоматов рассматриваемого вида. В работе приведено решение задачи об «Умном муравье» с помощью автомата Мура и системы из двух автоматов Мили. Еще одна интересная задача, решаемая простым автоматом, который генерируется с помощью генетического алгоритма, описана в работе
4.4.2. Методы генерации автоматов с большим числом входных переменных