В задаче об «Умном муравье» представление автомата в виде особи и реализация генетических операторов не составляли проблемы. Функции переходов и выходов для каждого состояния автомата были представлены в виде полной таблицы переходов и выходов: в этой таблице каждому возможному входному воздействию сопоставляется целевое состояние и выходное воздействие (рис. 4.9).При использовании полных таблиц размер представления автомата растет экспоненциально с увеличением числа входных переменных. Это не позволяет использовать такие таблицы для автоматов с большим числом входных переменных. К счастью, реальные автоматы обладают свойством, отмеченным в параграфе 2.3: обычно только небольшая часть входных переменных является значимой в каждом состоянии. Исходя из этого свойства, можно предложить различные способы упрощения представления автоматов.
В настоящее время известно два способа компактного представления автоматов с большим числом входных переменных: метод сокращенных таблиц и метод деревьев решений Идея метода сокращенных таблиц состоит в том, что число значимых входных переменных в каждом состоянии ограничивается константой. При этом представление функции переходов и выходов для состояния автомата содержит описание множества значимых входных переменных и собственно сокращенную таблицу, в которой каждой комбинации значений выбранных переменных сопоставляется целевое состояние и выходное воздействие (рис. 4.10).Опыт показывает, что даже в системах со сложным поведением, которые содержат несколько десятков входных переменных, число значимых переменных в каждом состоянии обычно не превышает нескольких единиц. Поэтому для сложных задач размер сокращенной таблицы остается небольшим. Операции скрещивания и мутации для сокращенных таблиц несколько сложнее, чем для полных. При мутации измениться может не только сама таблица, но и множество значимых переменных. При этом каждая из таких переменных с некоторой вероятностью заменяется другой, которая не принадлежит множеству. При скрещивании сокращенных таблиц родительские хромосомы состояний могут иметь различные множества значимых переменных. Поэтому сначала необходимо выбрать, какие из этих предикатов будут значимы для хромосом детей. В настоящее время используется вариант, при котором переменные, значимые для обоих родителей, наследуются обоими детьми, а каждая из тех переменных, которые были значимы лишь для одной родительской особи, равновероятно достаются любому из двух детей. После этого скрещиваются сами сокращенные таблицы переходов. При этом на значения каждой строки таблицы ребенка влияют значения нескольких строк родительских таблиц. Конкретное значение, помещаемое в ячейку таблицы ребенка, определяется «голосованием» всех влияющих на нее ячеек таблиц родителей. Для реализации метода сокращенных таблиц была разработана библиотека AutoGen Эта библиотека была успешно использована для генерации автомата верхнего уровня управления самолетом
Перейдем ко второму методу компактного представления автоматов — методу деревьев решений. Дерево решений является удобным способом задания дискретной функции, зависящей от конечного количества дискретных переменных. Оно представляет собой помеченное дерево, метки в котором расставлены по следующему правилу: внутренние узлы помечены символами переменных; ребра — значениями переменных; листья — значениями искомой функции.
Для определения значения функции по значениям переменных необходимо спуститься от корня до листа и сформировать значение, которым помечен полученный лист. При этом из вершины, помеченной переменной x, переход производится по тому ребру, значение на котором совпадает со значением переменной x.Пример дерева решений изображен на рис. 4.11. Это дерево реализует булеву функцию ¬ x1¬ x2?x1x3. Сокращение размера дерева по сравнению с полной таблицей истинности булевой функции достигается за счет использования ее специфики: если первая переменная ложна, то не играет роли значение третьей переменной, а если истинна — то второй. Управляющий автомат можно представить в виде упорядоченного набора деревьев решений, каждое из которых описывает множество переходов из одного конкретного состояния и содержит в листьях не логические значения, а пары <целевое состояние, выходное воздействие>.Определим генетические операции над деревьями решений. При мутации дерева выбирается случайный узел. После этого поддерево с корнем в этом узле изменяется на случайно сгенерированное. При скрещивании деревьев в каждой из родительских особей случайно выбирается по одному узлу. После этого поддерево с корнем в выбранном узле из первого родителя заменяется поддеревом с корнем в выбранном узле из второго родителя. Результатом этой операции скрещивания, в отличие от предыдущих вариантов, является одна новая особь. Этот метод был успешно использован при создании автоматов, управляющих беспилотными летательными объектами. В работе описано решение этой же задачи, в котором компоненты объекта управления не реализуются вручную, а представлены нейронными сетями и оптимизируются вместе с управляющим автоматом. Кроме системы управления беспилотными летательными объектами с помощью генетических алгоритмов были созданы системы управления танком для игры Robocode и моделью вертолета В работе описано инструментальное средство для генерации автоматов с использованием генетических алгоритмов. В частности, это средство позволяет сократить время генерации автоматов за счет использования распределенных вычислений. В заключение раздела отметим, что при использовании генетического программирования для генерации автоматов, применяемых в UniMod-программах, обеспечивается высокий уровень автоматизации построения этого класса программ, так как автоматически генерируются не только автоматы, но и программный код по ним. эксперименты показали, что для рассматриваемого класса программ только 20–30% программного кода пишется вручную.