logo
ГА / ГА / Построение КА с помощью ГА

1.3.5.Работы в сПбГу итмо

В рамках исследований по теме «Технология генетического программирования для генерации автоматов управления системами со сложным поведением» на кафедре «Технологии программирования» СПбГУ ИТМО был разработан ряд методов генерации конечных автоматов с помощью генетических алгоритмов. Один из этих методов – метод сокращенных таблиц переходов был предложен Н. Поликарповой и В. Точилиным в работе []. Этот метод позволяет решить проблему экспоненциального роста размера описания автомата, которая возникает при использовании полных таблиц переходов – число строк в таблице есть , где– число предикатов. Опыт показывает, что в реальных задачах управляющие автоматы, построенные вручную, имеют гораздо меньше переходов, чем(здесь как |S| обозначено размер множества состояний автомата). Причина этого состоит в том, что в большинстве задач предикаты имеют «локальную природу» по отношению к управляющим состояниям. В каждом состояниизначимым является лишь определенный, небольшой поднабор предикатов, остальные же не влияют на значение управляющей функции. Именно это свойство позволяет существенно сократить размер описания состояний. Кроме того, использование этого свойства в процессе оптимизации позволяет получить результат, более похожий на автомат, построенный вручную, а следовательно, и более понятный человеку. Свойство локальности предикатов можно применять для сокращения описания управляющего состояния разными способами. При разработке метода сокращенных таблиц был выбран один из подходов, при котором число значимых в состоянии предикатов ограничивается некоторой константой . К таблице, задающей сужение управляющей функции на данное состояние, в этом случае добавляется битовый вектор, описывающий множество значимых предикатов (1.3.5).

  1. Хромосома состояния: сокращенная таблица (n = 6, m = 3, r = 2, |S| = 3)

Число строк таблицы в этом случае , однако, константаобычно невелика. Ее выбор зависит от сложности задачи. Как показывает опыт, для большинства автоматизированных объектов среднее по всем состояниям значениене больше пяти. Второй метод – метод представления автоматов деревьями решений предложен В. Даниловым в работах [, ]. Дерево решений является удобным способом задания дискретной функции, зависящей от конечного числа логических переменных. Оно представляет собой помеченное дерево, метки в котором расставлены по следующему правилу:

Для определения значения функции по значениям переменных необходимо спуститься от корня до листа, и сформировать значение, которым помечен полученный лист. При этом из вершины, помеченной переменной x, переход производится по тому ребру, которое помечено тем же значением, что и значение переменной x. Метод представления автомата с помощью деревьев решений заключается в следующем: функции переходов и выходов автомата выражаются с помощью деревьев решений. Более формально: зададим для каждого состояния функцию, такую чтодля. Здесь– множество состояний автомата,– множество входных воздействий,– множество выходных воздействий,– функция переходов,– функция выхода. Каждая из этих функций может быть определена собственным деревом решений.Таким образом, автомат в целом может быть представлен упорядоченным набором деревьев решений и стартовым состоянием.  Каждое состояние автомата представляется с помощью соответствующего дерева решений. Деревья решений состоят из узлов, среди которых выделяется корень. Каждый узел представляется следующим образом:

Следовательно, при использовании описываемого метода автомат представляется объектом следующего вида на языке Java: class TreeAutomata {  Tree[] trees;  int startState;  }  class Tree {  Node root;  private class Node {  Node left;  Node right;  int transState;  int action;  } } Третий метод – метод совместного применения конечных автоматов и нейронных сетей был предложен автором настоящей диссертации в работах [, ]. При использовании этого метода для управления системой со сложным поведением предлагается совместно применять нейронную сеть и конечный автомат, которые совместно строятся генетическим алгоритмом.  При этом, как отмечалось выше, нейронная сеть используется для классификации значений вещественных входных переменных и выработки входных логических переменных для автомата, а автомат – для выработки выходных воздействий на систему со сложным поведением (1.3.5).

  1. Структурная схема системы управления при использовании метода совместного применения конечных автоматов и нейронных сетей

Одна из возможных структур нейронной сети и способ ее взаимодействия с конечным автоматом показаны на 1.3.5. Отметим, что для решения других задач структура нейронной сети может быть изменена. 

  1. Возможная структура нейронной сеть и ее взаимодействие с конечным автоматом

Символами S на 1.3.5 обозначены нейроны с сигмоидальной функцией активации, символом L – нейроны с пороговой функцией активации. Рядом с нейронами указаны их номера (они используются при описании операции скрещивания нейронных сетей). На каждый из трех выходов нейронной сети поступает число равное нулю или единице. Таким образом, существует восемь вариантов комбинаций выходных сигналов нейронной сети (000, 001, 010, 011, 100, 101, 110, 111), подаваемых на вход конечного автомата. Указанные методы применялись для построения конечных автоматов управления моделью беспилотного летательного аппарата. При этом в ряде случаев построенные автоматы были более эффективными, чем построенные вручную [].