«Методы построения конечных автоматов на основе эволюционных алгоритмов ...»

edits(s’, s’’) обозначено редакционное расстояние между строками s’ и s’’, которое равно минимальному числу операций вставки, замены или удаления символа, которые необходимо выполнить, для того чтобы преобразовать строку s’ в строку s’’. Отметим, что значения всех трех указанных функций приспособленности находятся в отрезке от 0 до 1, при этом меньшее значение соответствует большему соответствию выходной строки эталону.

Экспериментальное исследование алгоритмов проводилось на задаче построения конечного преобразователя для преобразования представления двумерного изображения из цепного кода для четырех направлений в цепной код для восьми направлений. Применялись два набора данных. В «простом» наборе было достаточно много коротких строк, а в «сложном» – их доля была намного меньше.

Результаты экспериментов показали, что наилучшие результаты на «сложном» наборе данных достигаются при использовании функции приспособленности, основанной на редакционном расстоянии. Второй по эффективности является функция, основанная на расстоянии Хэмминга, а третьей – основанная на строгом сравнении. На «простом» наборе ситуация примерно такая же, только функции строгого сравнения и вычисления расстояния Хэмминга меняются местами.

1.3.3. Методы, использующие верификацию при вычислении Известна только одна работа [80], посвященная построению взаимодействующих конечных автоматов с использованием генетического программирования с функцией приспособленности, при вычислении которой применяется верификация моделей [9]. Верификация моделей – это набор методов и алгоритмов, которые позволяют определять, соответствует ли программа некоторому множеству требований. При этом требования выражаются на языке темпоральной логики – записываются утверждения о поведении программы во времени.

В рассматриваемой работе применяется темпоральная логика CTL (Computation Tree Logic – логика деревьев вычислений), а для верификации используется система SMV (http://www.cs.cmu.edu/~modelcheck/smv.html).

В рассматриваемой работе решается задача построения системы взаимодействующих конечных автоматов. Это означает, что автоматы, входящие в систему, имеют общие глобальные переменные и каналы связи, по которым могут передаваться сообщения.

приспособленности используется описание системы автоматов, а также набор темпоральных формул, которые требуется проверить. Результатом вычисления функции приспособленности является число верных для системы автоматов формул.

В качестве эволюционного алгоритма в рассматриваемой работе применяется (1+)-эволюционная стратегия. Возможные варианты выполнения операции мутации таковы:

с вероятностью 0.4 добавляется новое состояние;

всегда (с вероятностью 1.0) добавляется новое состояние со случайно выбранной пометкой;

с вероятностью 0.3 удаляется случайно выбранный переход;

с вероятностью 0.1 изменяется пометка одного из состояний;

Экспериментальное исследование разработанного алгоритма проводилось на задаче построения автомата управления кофе-машиной.

Применялось два набора входных данных. Первый из них содержал восемь темпоральных формул, а второй – 17. Второй набор описывал кофемашину, которая обладает большей функциональностью, чем описываемая первым набором. Задача состояла в нахождении системы из двух автоматов, один из которых описывал поведение пользователя, а второй – кофе-машины.

Вычислительные эксперименты проводились следующим образом:

выполнялось 30 запусков эволюционного алгоритма, в каждом из которых проводилось 20 итераций эволюционного алгоритма. На первом наборе данных в 25 из 30 запусков была найдена система автоматов, удовлетворяющая всем восьми формулам, а в пяти оставшихся – удовлетворяющая семи.

На втором наборе данных в каждом запуске выполнялось итераций эволюционного алгоритма. Ни в одном из запусков не была найдена система автоматов, удовлетворяющая всем темпоральным формулам. При этом в семи запусках была найдена система автоматов, для которой выполняются 16 из 17 формул.

1.3.4. Анализ эволюционных алгоритмов построения автоматов Обобщим материал разделов 1.3.1 – 1.3.3, проведя сравнение рассмотренных эволюционных алгоритмов построения автоматов (табл. 1).

Сравнение алгоритмов проводится по следующим параметрам:

Тип конечных автоматов.

Тип эволюционного алгоритма.

Метод представления особей в эволюционном алгоритме.

Метод вычисления функции приспособленности.

алгоритмов построения автоматов Artificial Intelligence through Simulated Evolution [53] The Genesys System:

Evolution as a Theme in Artificial Life Evolutionary Module Acquisition генетических конечный программирование переходов моделирования построения автоматов с минимальным числом состояний для задачи «Умный муравей»

генетического конечные программирование переходов и моделирования большим числом входных переменных представления конечные программирование переходов и моделирования использования генетическом программиров ании [5] применение конечные программирование значений моделирования управления беспилотным летательным аппаратом Evolving Finite-State Machine Strategies for Protecting Resources Learning DFA:

Evolution Evidence Drive State Merging Learning Deterministic Automata with a Smart State Labeling Algorithm [89] A Genetic Algorithm for Finite State Automata Induction with Application to Phonotactics Genetic Inference of Finite State Machines [115] Evolving Finite-State Transducers:

';

Some Initial Explorations Genetic Programming with Fitness based on Model Checking [80] На основании проведенного обзора можно сделать следующие выводы:

главное отличие управляющих конечных автоматов от других типов конечных автоматов (конечных преобразователей и входят булевы формулы, зависящие от входных переменных;

для построения управляющих конечных автоматов ранее применялись только методы, использующие вычисление функции приспособленности на основе моделирования;

в работах, использующих эволюционную стратегию и метод спуска (в частности, в работах [80, 89]) выбор этих методов практически нет работ, в которых проводится сравнение основанных на алгоритмах поисковой оптимизации. Это подтверждается работой [69], в которой упоминается, что в области поисковой инженерии ПО наблюдается такая же автоматов с вычислением функции приспособленности на

1.4. ЗАДАЧИ, РЕШАЕМЫЕ В ДИССЕРТАЦИОННОЙ РАБОТЕ

Из выполненного обзора следует, что существующие методы построения управляющих конечных автоматов используют вычисление функции приспособленности на основе моделирования и обладают следующими недостатками:

приспособленности, что может быть весьма трудоемким;

моделированием поведения автомата в некоторой внешней На основании проведенного обзора сформулируем задачи, решаемые в диссертационной работе:

автоматов по обучающим примерам на основе эволюционных 2. Разработать метод выполнения операции скрещивания для генетических алгоритмов, учитывающий поведение автоматов 4. Разработать технологию построения управляющих конечных 5. Разработать инструментальное средство для автоматизации построения управляющих конечных автоматов.

6. Внедрить разработанные методы при построении автомата управления моделью беспилотного самолета и в учебный процесс.

ВЫВОДЫ ПО ГЛАВЕ

1. Приведены результаты обзора работ, посвященных автоматному программированию и поисковой инженерии программного обеспечения.

2. Приведен обзор методов построения конечных автоматов на основе эволюционных алгоритмов.

3. Сформулированы основные недостатки существующих методов построения управляющих конечных автоматов на основе эволюционных алгоритмов.

4. Сформулированы задачи, решаемые в диссертационной работе.

ГЛАВА 2. МЕТОДЫ ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ КОНЕЧНЫХ

АВТОМАТОВ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ ПО

ОБУЧАЮЩИМ ПРИМЕРАМ И ТЕМПОРАЛЬНЫМ ФОРМУЛАМ

Настоящая глава посвящена методам построения управляющих конечных автоматов на основе эволюционных алгоритмов:

методу построения управляющих конечных автоматов по обучающим примерам на основе эволюционных алгоритмов;

поведения автоматов на обучающих примерах;

методу построения управляющих конечных автоматов по обучающим примерам и темпоральным формулам на основе эволюционных алгоритмов и верификации.

2.1. МЕТОД ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ КОНЕЧНЫХ АВТОМАТОВ

ПО ОБУЧАЮЩИМ ПРИМЕРАМ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ

АЛГОРИТМОВ

В настоящем разделе описывается разработанный метод построения управляющих конечных автоматов по обучающим примерам (тестам) на основе эволюционных алгоритмов [133, 150, 160, 161].

управления системой со сложным поведением являются:

множество входных переменных X;

множество выходных воздействий Z;

множество тестов Tests (число тестов в дальнейшем будет максимальное число состояний в искомом автомате k.

Элементами входной последовательности являются пары (e, f), где e – некоторое событие из множества E, а f – логическая формула от входных переменных, задающая условие перехода.

2.1.1.1. Предварительная обработка входных данных предварительная обработка входных данных. Создается список всех условий, входящих во входные последовательности тестов: f1, f2, …, fl.

Далее строятся две таблицы, содержащие логические значения:

areEquivalent[i, j] – верно ли, что fi и fj эквивалентны;

haveCommon[i, j] – верно ли, что fi и fj имеют общую Для построения этих таблиц перебираются все пары охранных условий (fi, fj), i j, и для каждой из них строится таблица истинности для формул (fi fj) и !(fi & fj). Если первая из них является тавтологией, то в «истина», если вторая формула всегда ложна, то в ячейку таблицы haveCommon[i, j] записывается значение «истина».

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

Время работы алгоритма построения этих таблиц – O(22r’·l2), где, как и раньше, r’ – максимальное число входных переменных, от которых зависит некоторое условие перехода. На практике, как уже отмечалось выше, значение r’ не превышает пяти, что позволяет говорить о том, что время, требуемое на предварительную обработку данных пропорционально квадрату суммарного размера входных последовательностей.

Выходные данные должны представлять собой описание автомата, содержащего не более k состояний, удовлетворяющего каждому тесту из множества Tests и обладающего свойством непротиворечивости.

Test = (Input, Answer), последовательности Input при старте из начального состояния автомата совпадает с последовательностью Answer.

Результат обработки входной последовательности Input при начале из состояния s определяется рекурсивно:

обработки также является пустой последовательностью;

если последовательность Input не пуста, а ее первый элемент имеет вид (e, f), то результат обработки последовательности Input конкатенация двух последовательностей – результата обработки элемента входной последовательности (e, f) в состоянии s и результата обработки оставшейся части последовательности Input при начале из состояния, в которое ведет переход из s по событию e и условию, эквивалентному f.

последовательности Input не определен, то и результат обработки последовательности также не определен.

Результатом обработки элемента входной последовательности (e, f) в состоянии s является последовательность выходных воздействий, соответствующая переходу, который помечен событием e и условием, эквивалентным f. Если же такого перехода из состояния s нет или таких переходов несколько, то результат обработки указанного элемента не определен.

Например, для автомата управления часами с будильником, граф переходов которого приведен на рис. 6, результат обработки элемента входной последовательности (H, true) в состоянии «1. Будильник выключен» является последовательность, содержащее одно выходное последовательности (A, true) в состоянии «2. Установка времени будильника» – пустая последовательность, результат обработки элемента входной последовательности (T, !x2&x1) в состоянии «3. Будильник включен» – последовательность из двух элементов z5, z6, а результат обработки элемента (T, x2&x1) в состоянии «3. Будильник включен» не определен.

Результат обработки входной последовательности (A, true), (M, true) при начале из состояния «1. Будильник выключен» – последовательность из одного элемента z4, а результат обработки входной последовательности (A, true), (A, true), (T, x2&x1) при начале из того же состояния не определен.

2.1.3. Представление управляющего конечного автомата в виде Конечный автомат в эволюционных алгоритмах предлагается представлять в виде объекта, который содержит описания переходов для каждого из состояний. Во всех автоматах, рассматриваемых в процессе работы эволюционных алгоритмов, номер начального состояния равен нулю. Для каждого из состояний хранится список переходов. Каждый переход описывается событием, при поступлении которого этот переход выполняется, условием перехода и числом выходных воздействий, которые должны быть сгенерированы при выборе этого перехода. При этом в встречающиеся во входных последовательностях тестов. На рис. эволюционного алгоритма.

{2, {{A, x, 1, 0}, {T, !x, 1, 1}}, {{T, true, 1, 1}, Рис. 19. Представление конечного автомата в виде особи Для построения автоматов в настоящей работе существующие эволюционные алгоритмы предлагается модифицировать, добавив перед дополнительный шаг – расстановку выходных воздействий. Он необходим, так как особь в эволюционном алгоритме представляет собой «каркас»

получившегося в результате автомата было максимальным или близким к нему.

2.1.4. Алгоритм расстановки выходных воздействий дискретных воздействий. Как было сказано выше, для каждого перехода в особи эволюционного алгоритма записано, сколько выходных воздействий должно вырабатываться при его выборе.

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

A, T, T, M, H, T, T соответствует выходная последовательность z5, z5, z4, z3, z5, z5, и при обработке входной последовательности выполняются следующие переходы: 1 2 2 2 3 4 2 2. Пусть при этом на первом из переходов не должно выполняться ни одно выходное воздействие, а на каждом из остальных – должно выполняться одно (рис. 20).

Рис. 20. Некоторые переходы «каркаса» автомата На рис. 20 для каждого из переходов, кроме события, при возникновении которого он выполняется, указано число выходных воздействий, которые ему соответствуют.

Тогда на основании этого теста можно сделать вывод о том, что на переходе по событию T из второго состояния в себя должно вырабатываться выходное воздействие z5, на переходе по событию M из второго состояния в третье должно вырабатываться выходное воздействие z4, на переходе по событию H из третьего состояния в четверное должно вырабатываться z5, а на переходе по событию T из четвертого состояния во второе – z3 (рис. 21).

Рис. 21. Помеченные на основании теста переходы автомата Таким образом, на основании одного теста можно расставить выходные воздействия на части переходов автомата. Если тестов больше одного, то возможны различные ситуации:

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

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

В первом случае ситуация аналогична ситуации с одним тестом. Во втором случае этот переход помечается тем выходным воздействием, которое чаще всего вырабатывается на нем в тестах.

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

Для каждого перехода T и каждой последовательности выходных воздействий zs вычисляется величина C[T][zs] – число раз, когда при обработке входной последовательности, соответствующей одному из тестов, на переходе T должны быть выработаны выходные воздействия, образующие последовательность zs. Далее, каждый переход помечается той последовательностью zs0, для которой величина C[T][zs0] максимальна.

2.1.5. Вычисление функции приспособленности Функция приспособленности в этом случае основывается на редакционном расстоянии. Для ее вычисления выполняются следующие действия: на вход автомату подается каждая из последовательностей воздействий, которую сгенерировал автомат при входе Input[i]. После ED(A, B) – редакционное расстояние между последовательностями A и B.

Отметим, что значение этой величины лежит в пределах от 0 до 1. При этом, чем «лучше» автомат соответствует тестам, тем больше ее значение.

Функция приспособленности зависит не только от того, насколько «хорошо» автомат работает на тестах, но и от числа переходов, которые он содержит. Она вычисляется по формуле: FF где M – число, заведомо большее числа переходов в автомате (в экспериментах M выбиралось равным 100), а cnt – число переходов в автомате, кодируемом рассматриваемой особью.

Учет числа переходов в функции приспособленности необходим по двум причинам. Во-первых, минимизация числа переходов приводит к тому, что в результирующем автомате отсутствуют не используемые в тестах переходы. Во-вторых, чем меньше в автомате переходов, тем более «общее» поведение он задает. Таким образом, решается проблема переобучения (overfitting), состоящая в том, что автомат демонстрирует правильное поведение только на входных последовательностях, соответствующих набору тестов.

Оценим время вычисления функции приспособленности. Для пропорционально произведению длин последовательностей, для которых последовательности A = A1…A|A| и B = B1…B|B|. Он основан на заполнении таблицы ED, которая определяется следующим образом: элемент ED[i, j] равен редакционному расстоянию между последовательностями A1…Ai и B=B1…Bj.

Таким образом, время вычисления функции приспособленности составляет O( | Output[i] | | Answer[i] |). Заметим также, что добавление в набор тестов их префиксов не увеличивает времени вычисления функции приспособленности, так как достаточно вычислить редакционное расстояние только для «самых больших» тестов, а для префиксов редакционное расстояние взять из таблицы, вычисляемой алгоритмом динамического программирования.

2.1.6. Операция мутации, использующаяся в методе спуска на основе случайных мутаций и в генетическом алгоритме При выполнении операции мутации с заданной вероятностью (по умолчанию, она равна 0.05) выполняется одно из действий: изменение описания каждого из переходов и удаление или добавление перехода для каждого состояния.

выполняется одно из следующих действий:

Изменение состояния, в которое ведет переход (изменяется на Изменение события, по которому выполняется переход (изменяется на случайно выбранное).

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

Изменение условия (изменяется на случайно выбранное из числа тех, которые встречаются в тестах вместе с событием, которым помечен переход).

2.1.7. Операция удаления дублированных и противоречивых Обозначим Lin список переходов, поступающих на вход операции удаления дублированных и противоречивых переходов, а список переходов, получающийся в результате этой операции, – Lout. Для его формирования выполняются следующие операции:

по очереди рассматриваются переходы, входящие в список Lin;

очередной переход t добавляется в Lout, если в нем еще нет перехода, помеченного тем же событием, что и t, и охранным условием, имеющим общую выполняющую подстановку с охранным условием перехода t.

2.1.8. Операция мутации, использующаяся в эволюционной Так как в эволюционной стратегии операции мутации должна быть устроена таким образом, чтобы в ее результате мог получиться любой элемент пространства поиска, то она выполняется следующим образом.

Выбирается случайным образом число x из геометрического распределения с вероятностью успеха, равной 0.5. После этого к поступившей на вход особи (x + 1) раз применяется мутация, использующаяся в методе спуска и эволюционной стратегии.

В настоящем разделе описывается генетический алгоритм, предложенный в настоящей работе для построения управляющих конечных автоматов по тестам.

2.1.9.1. Генерация начального поколения Начальное поколение заполняется автоматами, сгенерированными случайным образом. При этом все автоматы содержат одинаковое число состояний, из каждого их которых число переходов определяется случайным образом в диапазоне от нуля до числа событий, которые присутствуют в рассматриваемой системе со сложным поведением.

2.1.9.2. Формирование следующего поколения В качестве основной стратегии формирования следующего поколения используется элитизм [2]. При обработке текущего поколения отбрасываются все особи, кроме нескольких наиболее приспособленных.

Доля выживающих особей постоянна для каждого поколения и является одним из параметров алгоритма.

Эти особи переходят в следующее поколение. После этого оно дополняется до требуемого размера следующим образом: пока оно не заполнено выбираются две особи из текущего поколения, и они с некоторой вероятностью скрещиваются или мутируют. Обе особи, полученные в результате мутации или скрещивания, добавляются в новое поколение.

Кроме этого, если на протяжении достаточно большого числа поколений не происходит увеличения приспособленности, то применяются «малая» и «большая» мутации поколения. При «малой» мутации `поколения ко всем особям, кроме 10% лучших, применяется оператор мутации. При «большой» мутации каждая особь либо мутирует, либо заменяется на случайно сгенерированную.

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

Скрещивание особей производится следующим образом. Обозначим как P1 и P2 «родительские» особи, а как S1 и S2 – особи-«потомки».

Начальные состояния S1.is и S2.is имеют номер ноль. Как было отмечено выше, у всех особей нулевое состояние является начальным.

Опишем, как устроены переходы автоматов S1 и S2. Скрещивание описаний автоматов производится отдельно для каждого состояния.

Обозначим список переходов из состояния номер i автомата P1 как P1.T[i], а список переходов из состояния номер i автомата P2 как P2.T[i].

При использовании традиционного метода скрещивания списки переходов S1.T[i] и S2.T[i] строятся следующим образом:

1. Строится общий список переходов, в который помещаются переходы, входящие как в P1.T[i], так и в P2.T[i].

2. К полученному списку применяется случайная перестановка.

3. Далее возможны два равновероятных варианта:

К получившимся в результате скрещивания автоматам S1 и S применяется операция удаления дублированных и противоречивых переходов.

2.1.11. Совместное использование генетического алгоритма, эволюционной стратегии и метода спуска на описанными выше алгоритмами была замечена следующая особенность эволюционной стратегии и метода спуска на основе случайных мутаций – в ряде запусков целевое значение функции приспособленности достигалось очень быстро – в процессе работы алгоритм рассматривал не более 10 000 особей. Как правило, это происходило тогда, когда сгенерированное случайным образом начальное решение обладало достаточно высоким значением функции приспособленности.

В то же время алгоритм генетического программирования в каждом приспособленности. Это объясняется тем, что даже если у лучшей особи в поколении значение функции приспособленности близко к целевому, то в процессе ее «доведения» до оптимума будет проведено достаточно много вычислений функции приспособленности, так как она будет вычисляться не только для этой особи, но и для всех других особей, входящих в поколение.

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

2.2. МЕТОД ВЫПОЛНЕНИЯ ОПЕРАЦИИ СКРЕЩИВАНИЯ С УЧЕТОМ

ПОВЕДЕНИЯ АВТОМАТОВ НА ОБУЧАЮЩИХ ПРИМЕРАХ

Как и ранее, обозначим как P1 и P2 «родительские» особи, а как S1 и S2 – особи-«потомки». Начальные состояния S1.is и S2.is имеют номер ноль – как было отмечено выше, у всех особей нулевое состояние является начальным.

Опишем, как устроены переходы автоматов S1 и S2. Скрещивание описаний автоматов производится отдельно для каждого состояния.

Обозначим список переходов из состояния номер i автомата P1 как P1.T[i], а список переходов из состояния номер i автомата P2 как P2.T[i].

При использовании предлагаемого в настоящей диссертации метода примерах [170] списки переходов S1.T[i] и S2.T[i] строятся следующим образом:

1. В автоматах P1 и P2 помечаются те переходы, которые выполняются при обработке 10% тестов, для которых нормированное редакционное расстояние между «правильным ответом» Answer и последовательностью Output выходных 2. Список переходов S1.T[i] формируется следующим образом:

сначала в него копируются помеченные переходы из P1.T[i], затем помеченные переходы из P2.T[i], а затем непомеченные 3. Список переходов S2.T[i] формируется следующим образом:

сначала в него копируются помеченные переходы из P2.T[i], затем помеченные переходы из P1.T[i], а затем непомеченные К получившимся в результате скрещивания автоматам S1 и S применяется операция удаления дублированных и противоречивых переходов.

2.3. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ МЕТОДОВ

ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ АВТОМАТОВ ПО ОБУЧАЮЩИМ

ПРИМЕРАМ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ

В настоящем разделе описываются результаты экспериментального исследования эволюционных алгоритмов для построения управляющих конечных автоматов [170]. Рассматриваются шесть алгоритмов:

генетический алгоритм, в котором используется только традиционный метод выполнения операции скрещивания метод спуска на основе случайных мутаций (МС);

(1+1)-эволюционная стратегия (ЭС);

генетический алгоритм, в котором используется только операция скрещивания на основе тестов (ГА-2);

алгоритм, использующий совместно ГА-2 и метод спуска на основе случайных мутаций (ГА-2 + МС);

алгоритм, использующий совместно ГА-2 и метод спуска на основе случайных мутаций (ГА-2 + ЭС).

2.3.1. Построение автомата управления часами с будильником В настоящем разделе описывается результаты экспериментального исследования указанных эволюционных алгоритмов на задаче построения автомата управления часами с будильником, описанной в разд. 1.1.3.

В систему тестов для построения автомата управления часами с будильником включены тесты, описывающие его работу во всех трех режимах. Тесты, описывающие поведение часов с будильником в режиме работы «Будильник выключен», приведены в табл. 2. В этой таблице, если во входной последовательности для некоторого события не указано условие перехода, считается, что условием является тождественно истинная формула.

Таблица 2. Тесты для режима работы «Будильник выключен»

Answer: z5, z5, z5, z Answer: z1, z1, z1, z Answer: z2, z2, z2, z Input: T, M, H, T, T, T, M, Answer: z5, z2, z1, z5, z5, z5, Input: A, A, A, T, T, T, T Answer: z7, z5, z5, z5, z Input: A, A, A, H, H, H, H Answer: z7, z1, z1, z1, z Input: A, A, A, M, M, M, M После трех нажатий кнопки «A» часы должны Answer: z7, z2, z2, z2, z Тесты, описывающие поведение часов с будильником в режиме работы «Настройка будильника», приведены в табл. 3.

Таблица 3. Тесты для режима работы «Настройка будильника»

Answer: z5, z5, z5, z Answer: z3, z3, z3, z Input: A, M, M, M, M Answer: z4, z4, z4, z Input: A, T, M, H, T, T, T, Answer: z5, z4, z3, z5, z5, z5, Input: A, A, A, A, T, T, T, T Answer: z7, z5, z5, z5, z Input: A, A, A, A, H, Answer: z7, z3, z3, z3, z Input: A, A, A, A, M Input: A, A, A, A, M, Answer: z7, z4, z4, z4, z Тесты, описывающие поведение часов с будильником в режиме работы «Будильник включен», приведены в табл. 4.

Таблица 4. Тесты для режима работы «Будильник включен»

Input: A, A, H, H, H, H Answer: z1, z1, z1, z Input: A, A, M, M, M, M Answer: z2, z2, z2, z Input: A, A, T [!x1 & !x2] Input: A, A, T [!x1 & !x2], T [!x1 & !x2], T [!x1 & !x2] Input: A, A, T [!x1 & !x2], T [x1 & !x2], T [x2 & !x1] Answer: z5, z5, z6, z5, z Input: A, A, T [!x1 & !x2], Input: A, A, T [!x1 & !x2], T [x1 & !x2], T [x2 & !x1], H Answer: z5, z5, z6, z5, z7, z Input: A, A, T [!x1 & !x2], T [x1 & !x2], T [x2 & !x1], M Answer: z5, z5, z6, z5, z7, z Input: A, A, T [!x1 & !x2], T [x1 & !x2], T [x2 & !x1], Answer: z5, z5, z6, z5, z7, z Input: A, A, T [x1 & !x2] Input: A, A, T [x2 & !x1] Input: A, A, T [x1 & !x2], Answer: z5, z6, z5, z Input: A, A, T [!x1 & !x2], M, T [!x1 & !x2], T [!x1 & !x2], M, T [!x1 & !x2], H, H, Answer: z5, z2, z1, z5, z5, z5, Кроме тестов, описывающих поведение автомата в каждом из трех режимов, в набор тестов включены тесты, описывающие поведение автомата сразу в нескольких режимах. Эти тесты приведены в табл. 5.

Таблица 5. Тесты, описывающие поведение автомата в нескольких режимах Input: A, A, T [!x1 & !x2], T [x1 & !x2], T [x2 & !x1], A, H Answer: z5, z5, z6, z5, z7, z7, z Input: A, A, T [!x1 & !x2], T [x1 & !x2], T [x2 & !x1], A, M Answer: z5, z5, z6, z5, z7, z7, z Input: A, A, T [!x1 & !x2], T [x1 & !x2], T [x2 & !x1], A, T Answer: z5, z5, z6, z5, z7, z7, z Input: A, A, T [!x1 & !x2], T [x1 & !x2], T [x2 & !x1], A, A, H Answer: z5, z5, z6, z5, z7, z7, z Input: A, A, T [!x1 & !x2], T [x1 & !x2], T [x2 & !x1], A, A, M Answer: z5, z5, z6, z5, z7, z7, z Input: A, A, T [!x1 & !x2], T [x1 & !x2], T [x2 & !x1], A, A, T Answer: z5, z5, z6, z5, z7, z7, z Input: A, A, T [!x1 & !x2], Answer: z5, z5, z6, z7, z 2.3.1.2. Описание вычислительных экспериментов Для каждого алгоритма было проведено 1000 запусков со следующими параметрами алгоритмов:

генетический алгоритм:

o доля «элиты» – наиболее приспособленных особей, o число поколений до малой «мутации поколения» – o число поколений до большой «мутации поколения» – эволюционная стратегия и метод спуска – перезапуск производился, если в течение 300 000 итераций не было улучшения значения функции приспособленности.

Цель в каждом из запусков каждого из алгоритмов состояла в том, чтобы построить автомат, содержащий 14 переходов и соответствующий всем тестам (значение функции приспособленности – 20.86). При этом в процессе работы каждого из алгоритмов рассматривались автоматы из четырех состояний.

Для каждого алгоритма было проведено 1000 запусков. Для каждого запуска каждого из алгоритмов записывалось число вычислений функции приспособленности.

2.3.1.3. Результаты вычислительных экспериментов Приведем распределения времени работы алгоритмов, полученные в результате вычислительных экспериментов. В эволюционных алгоритмах время работы измеряется числом запусков функции приспособленности, так как, как правило, ее вычисление является более трудоемким, чем выполнение операций мутации и скрещивания. Для анализа результатов программирования R [147].

В результате каждого запуска каждого из алгоритмов был построен автомат, граф переходов изображен на рис. 22. Отметим, что этот граф переходов изоморфен приведенному в разд. 1.1.3.

Рис. 22. Граф переходов автомата управления часами с будильником, построенного с помощью эволюционных алгоритмов На рис. 23 приведена гистограмма распределения времени работы алгоритма ГА-1. Она была построена следующим образом: полученные в результаты вычислительных экспериментов значения были распределены по 30 корзинам одинакового размера. В каждой из них на гистограмме соответствует один столбец, высота которого пропорциональна числу элементов, попавших в эту корзину. Гистограммы, приведенные далее, построены по такому же принципу.

Рис. 23. Распределение времени работы алгоритма ГА- На рис. 24 приведена гистограмма распределения времен работы алгоритма МС.

Рис. 24. Распределение времени работы алгоритма МС На рис. 25 приведена гистограмма распределения времен работы алгоритма ЭС.

Рис. 25. Распределение времени работы алгоритма ЭС На рис. 26 приведена гистограмма распределения времен работы алгоритма ГА-2.

Рис. 26. Распределение времени работы алгоритма ГА- На рис. 27 приведена гистограмма распределения времен работы алгоритма ГА-2 + МС.

Рис. 27. Распределение времени работы алгоритма ГА-2 + МС На рис. 28 приведена гистограмма распределения времен работы алгоритма ГА-2 + ЭС.

Рис. 28. Распределение времени работы алгоритма ГА-2 + ЭС В табл. 6 приведены минимальные, максимальные, средние и медианные значения числа вычислений функции приспособленности для каждого из алгоритмов.

Таблица 6. Результаты вычислительных экспериментов Для каждой пары алгоритмов был проведен статистический тест ANOVA [142]. Результаты этого теста приведены в табл. 7. В ней для использованием указанного теста вероятность того, что среднее число вычислений функции приспособленности одинаково для соответствующей пары алгоритмов). Если эта вероятность меньше 0.05, то можно сделать вывод о том, что время работы соответствующих алгоритмов на рассматриваемой задаче существенно различается.

Таблица 7. Результаты статистического теста 0 -> 0 -> 0 -> 1 -> 1 -> 2 e3 [not x3] 0 0 0.00000 -0.00274 -0.00202 0. 1 -> 2 e9 [not x9] 0 0 0.00000 -0.00993 -0.06966 0. 1 -> 3 e5 [not x5] 0 0 0.00000 -0.03879 -0.09682 0. 1 -> 2 -> 2 -> 2 -> 3 -> 3 -> 3 -> Отметим, что для каждого состояния могут быть определены 2r переходов, где r – число входных переменных (в рассматриваемом случае оно равно 13). Однако ни одно из четырех состояний не содержит их все.

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

Перед осуществлением «мертвой петли» двигатель включен.

Поэтому в ходе ее выполнения в использовании стартера нет необходимости – столбец «стартер» содержит только нули. Этот орган управления не был исключен при генерации автоматов, так как возможны дополнительные обучающие примеры, в которых требуется переключение стартера (например, если двигатель может заглохнуть). Последний столбец также оказался нулевым, но и соответствующий ему орган управления может быть использован при применении других обучающим примеров.

В процессе наблюдения за ходом выполнения «мертвом петли» под управлением лучшего автомата было установлено, что в зависимости от параметров среды и самолета при запуске автомата возможны три варианта выполнения «петли»:

1. В большинстве случаев модель самолета, как и при управлении вручную, выполняет одну «мертвую петлю» и летит дальше.

2. Иногда модель самолета может выполнить несколько «мертвых петель» с некоторым интервалом. Это происходит в случае, когда значения параметров модели самолета в конце выполнения «мертвой петли» схожи со значениями параметров в начале ее выполнения.

Это приводит к тому, что если автомат после осуществления «петли»

находится в том же состоянии, в котором был в начале, то поведение модели зацикливается. В ходе экспериментов авторы неоднократно наблюдали выполнение двух «мертвых петель» подряд. Выполнение большего числа «петель» не наблюдалось.

3. Модель может вообще не выполнить «мертвую петлю», так как автомат не справляется с управлением, что, правда, бывает крайне Приведем ссылки на видеозаписи трех вариантов реализации «мертвой петли» под управлением лучшего автомата: выполнение «мертвой петли», близкое к «идеальному» (http://www.youtube.com/watch?v=TzrLoJjjVTA);

выполнение «мертвой петли» с заваливанием на левый борт с последующим выравниванием (http://www.youtube.com/watch?v=C6WV7x2bqE8);

(http://www.youtube.com/watch?v=yFiG4yz67Ks).

На рис. 37, а – л приведены 11 кадров первой из этих видеозаписей.

Рис. 37. Кадры видеозаписи выполнения «мертвой петли» под

4.2. ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ В УЧЕБНЫЙ ПРОЦЕСС

Для внедрения результатов работы в учебный процесс были разработаны две виртуальные лаборатории (на языках программирования Java и C#) для обучения построению конечных автоматов на основе эволюционных алгоритмов.

4.2.1. Виртуальная лаборатория на языке Java Первая из разработанных виртуальных лабораторий реализована на языке программирования Java [168]. Она имеет модульную архитектуру – содержит ядро, предоставляющее базовую функциональность, которая может быть расширена за счет подключаемых модулей (плагинов).

сохранять в виде файлов графики зависимости значений некоторых функций (например, максимального, минимального и среднего значения функции приспособленности особей поколения) от номера поколения.

Кроме этого поддерживается возможность визуализации особей и их сохранения в текстовом формате. Также ядро программы поддерживает подключение плагинов «на лету» (во время работы программы).

В качестве подключаемых модулей выступают:

решаемые задачи;

функции, графики которых строятся ядром программы;

реализации различных алгоритмов генетического программирования;

реализации различных представлений особей и операций скрещивания и мутации для алгоритмов генетического программирования;

визуализаторы особей (автоматов) и управляемых ими объектов (они зависят от конкретной задачи и от конкретного представления особи).

При этом отметим, что алгоритмы генетического программирования и особи в некотором смысле независимы – предполагается, что любой представлением особи.

Решаемая задача формулируется в виде текстового описания задачи и программная реализация. Задача оформляется в виде плагина к виртуальной лаборатории.

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

Далее задаются параметры особи, например, число состояний автомата, и операторы скрещивания и мутации. Каждый оператор оформляется в виде отдельного плагина.

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

Алгоритм оформляется в виде плагина.

Далее осуществляется запуск алгоритма. В результате его работы пользователю представляются графики, например, график зависимости максимального значения функции приспособленности от номера поколения (рис. 38).

Рис. 38. Статистика работы генетического алгоритма При необходимости работа алгоритма может быть приостановлена.

В этом случае становится доступен выбор для просмотра любой особи из текущего поколения, а также лучших особей из каждого поколения (рис. 39).

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

4.2.1.1. Структура виртуальной лаборатории Ядро программы включает в себя три модуля.

common.jar – содержит интерфейсы, необходимые для разработки плагинов;

core.jar – ядро системы и пользовательский интерфейс;

util.jar – содержит реализацию вспомогательных классов.

В состав виртуальной лаборатории входят следующие плагины:

algorithms/simple.jar – генетический алгоритм;

functors/max.jar – плагин для отображения графика зависимости максимального значения функции приспособленности от номера поколения;

functors/mean.jar – плагин для отображения графика зависимости среднего значения функции приспособленности от номера поколения;

описывающая конечный автомат Мили.

4.2.1.2. Правила написания плагинов к виртуальной Как было сказано выше, виртуальная лаборатория имеет модульную функциональность, которая расширяется за счет подключаемых модулей (плагинов).

Отметим, что все упоминаемые ниже интерфейсы содержатся в файле common.jar, некоторые необязательные, но, возможно, полезные, при написании собственного модуля классы, содержатся в файле util.jar.

Создание плагина состоит в реализации соответствующего интерфейса и сборке jar-архива.

4.2.1.3. Плагин, содержащий представление особи В рассматриваемой виртуальной лаборатории особь – это экземпляр класса, реализующего интерфейс Individual:

public interface Individual extends Comparable public double fitness();

public Individual mutate(Random r);

public Individual[] crossover(Individual p, Random r);

Метод toString() используется при сохранении особи в файл.

Для подключения модуля к ядру виртуальной лаборатории JARархив с реализацией особи должен быть помещен в директорию individuals. Этот JAR-архив должен содержать файл MANIFEST.MF, в котором должны быть определены следующие параметры: Main-Class, Extension-Name, Comment. Параметр Main-Class задает имя класса, реализующего интерфейс Loader. Параметр Extension-Name содержит имя особи, отображаемое в диалоге выбора особи. Параметр Comment должен иметь вид «arg1 arg2 ||| комментарий, отображаемый в диалоге выбора особи». Здесь arg1 и arg2 – параметры, необходимые для отображения графиков – максимальное значение и число знаков после десятичной точки, отображаемых в значении функции приспособленности.

4.2.1.4. Плагин, содержащий генетический алгоритм Генетический алгоритм в виртуальной лаборатории – это экземпляр класса, реализующего интерфейс GA:

public interface GA { public List getGeneration();

public void nextGeneration();

public void bigMutation();

public Individual getBest();

Приведем описание методов, входящих в этот интерфейс:

getGeneration – возвращает текущее поколение;

nextGeneration – переход к следующему поколению;

bigMutation – вызов большой мутации поколения;

getBest – возвращает лучшую особь на данный момент.

Для подключения модуля к ядру виртуальной лаборатории JAR-файл с реализацией генетического алгоритма должен быть помещен в директорию gas. Этот JAR-архив должен содержать файл MANIFEST.MF, в котором должны быть определены следующие параметры: MainClass, Extension-Name, Comment.

Параметр Main-Class – это имя класса, реализующего интерфейс отображаться в диалоге выбора алгоритма.

4.2.1.5. Плагин, содержащий визуализатор особи Визуализатор особи – это экземпляр класса java.awt.Frame. Для подключения модуля к ядру виртуальной лаборатории JAR-файл с реализацией визуализатора должен быть помещен в директорию emulators.

Этот JAR-архив должен содержать файл MANIFEST.MF, в котором должны быть определены следующие параметры: Main-Class, Extension-Name, Comment. Параметр Main-Class – имя класса, реализующего интерфейс Loader. В данном случае метод load будет принимать одни параметр – возвращаемое значение метода getAttributes() экземпляра Visualizable.

public interface Visualizable extends Individual { public Object[] getAttributes();

комментарий, отображаемый в диалоге выбора визуализатора». Параметр Extension-Name также используются при отображении в диалоге выбора визуализатора.

4.2.2. Виртуальная лаборатория на языке C# Виртуальная лаборатория GlOpt [169] реализована на языке программирования С# на платформе Microsoft.NET. На эту виртуальную лабораторию было получено свидетельство о регистрации программы для ЭВМ (третье свидетельство в Приложении 1).

Она состоит из ядра и подключаемых модулей (плагинов), которые реализуют конкретные задачи и методы их решения. Ядро представлено классом Brain, который ответственен за загрузку основных сущностей программного комплекса: задач, методов поисковой оптимизации и визуализаторов, а также выполняет функции распределения ресурсов между работающими алгоритмами.

4.2.2.1. Структура виртуальной лаборатории Для описания задач используются абстрактные классы Problem и Individual, от которых наследуются классы, описывающие конкретные задачи, например задачу «Умный муравей».

Класс Problem содержит метод OptimizationDirection, возвращающий информацию о направления оптимизации (минимизация или максимизация) и метод EvaluateIndividual, предназначенный для вычисления функции приспособленности у конкретной особи.

Наследники этого класса должны реализовывать эти методы, а также методы, обеспечивающие доступ к базовой информации о задаче: названии и ее кратком описании.

SearchOperator, от которых, в свою очередь, наследуются классы, реализующие конкретные методы поисковой оптимизации, например, метод спуска на основе случайных мутаций или генетический алгоритм.

Класс SearchOperator необходим для организации требуемых в задаче операций над объектами класса Individual. Он обеспечивает универсальность в применении методов решения к различным задачам.

Общая структура изображена на рис. 40.

-Current Individuals +Create() +Evaluate Individual() +Initialize() +Next Iteration() +Terminated() Рис. 40. Структура виртуальной лаборатории Таким образом, в виртуальной лаборатории существует пять типов плагинов:

Problem);

алгоритмы поисковой оптимизации (наследуется от абстрактного класса Algorithm);

методы, адаптирующие алгоритмы к конкретным задачам (наследуется от абстрактного класса SearchOperator);

визуализаторы для задач (пример внешнего вида визуализатора приведен на рис. 41);

текстовые описания задач и алгоритмов.

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

В состав виртуальной лаборатории входят следующие плагины:

задачи: построение автомата по тестам, «Умный муравей», «Умный муравей-3»;

методы поисковой оптимизации: генетический алгоритм, (1+1)эволюционная стратегия;

визуализатор для задачи «Умный муравей»;

средства построения графиков зависимости значения функции приспособленности от номера поколения;

документация, в том числе html-описания решаемых задач и используемых для их решения методов.

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

Основные этапы при реализации новой задачи в виртуальной лаборатории GLOpt.

1. Реализация класса-наследника от абстрактного класса Individual, определяющего объект к которому в дальнейшем применяется алгоритм оптимизации. Так, например, в задаче о расстановке ферзей таким объектом выступает шахматная доска с расставленными на ней ферзями.

2. Реализация класса-наследника от абстрактного класса Problem. В данном классе должен быть определен метод OptimizationDirection.

Также необходимо определить метод EvaluateIndividual, возвращающий значение типа double – значение целевой функции для данного индивида.

3. Для реализации компоненты визуализации текущего решения требуется IndividualViewer, ViewIndividual, вызывающий графическую форму, либо представляющий данные о решении в любом другом удобном для пользователя виде.

Приведем основные этапы разработки подключаемого модуля, определяющего алгоритм.

1. Реализация алгоритма поиска оптимального решения – класса, наследованного от абстрактного класса Algorithm. Данный класс должен определять следующие методы.

OptimizationDirection – возвращает одну из двух именованных констант: OptimizationDirection.Minimize или OptimizationDirection.Maximize.

Initialize – описывает начальное состояние в алгоритме NextIteration – описывает действия, происходящие на очередной итерации алгоритма.

В переменной BestIndividual типа Individual должна Individual c лучшей на данной итерации алгоритма целевой функцией.

2. Реализация интерфейса SearchOperator, наследованного от интерфейса ICreateOperator. В данном интерфейсе должен быть определен метод Create, возвращающий объект класса Individual (абстрактный класс, для каждой задачи используется своя реализация).

Также в SearchOperator реализуются все необходимые методы для работы с объектами Individual – например, операции мутации и скрещивания.

4.2.3. Применение виртуальных лабораторий в учебном программирование» проводятся лекционные занятия и лабораторные работы по методам применения эволюционных алгоритмов для построения управляющих конечных автоматов.

Для проведения лабораторных работ используются описанные выше виртуальные лаборатории. При этом виртуальная лаборатория на языке программирования C# – с 2009 г.

Целью лабораторных работ является изучение методов построения конечных автоматов на основе эволюционных алгоритмов. В задании на лабораторную работу формулируется задача, для которой необходимо построить конечный автомат, а также требования к используемому эволюционному алгоритму, методу представления особи, выполнения операций скрещивания и мутации, в том числе, и предложенные в настоящей работе.

Каждая лабораторная работа должна выполняться одним студентом.

В рамках работы студент реализует подключаемые модули к виртуальной лаборатории на соответствующем языке программирования (Java или C#), а также выполняет несколько вычислительных экспериментов по построению управляющих конечных автоматов. По результатам выполнения лабораторной работы студент оформляет отчет. Пример отчета приведен в Приложении 2.

За время использования виртуальных лабораторий в учебном процессе лабораторные работы были выполнены более чем 150 студентами кафедры «Компьютерные технологии» НИУ ИТМО. Часть отчетов по лабораторным работам опубликована на сайте http://is.ifmo.ru/labs/.

ВЫВОДЫ ПО ГЛАВЕ

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

2. Разработанные методы построения управляющих конечных автоматов внедрены в учебный процесс в рамках дисциплин «Компьютерные технологии» НИУ ИТМО.

ЗАКЛЮЧЕНИЕ

В результате диссертационного исследования получены следующие результаты:

1. Разработан метод построения управляющих конечных автоматов по обучающим примерам на основе эволюционных алгоритмов.

эволюционные алгоритмы добавлен новый шаг «Расстановка вычислением функции приспособленности.

2. Разработан метод выполнения операции скрещивания для генетических алгоритмов, учитывающий поведение автоматов на обучающих примерах. Показано, что генетический алгоритм, использующий разработанный метод выполнения операции скрещивания, осуществляет построение автоматов по обучающим примерам быстрее, чем генетический алгоритм, использующий традиционный метод выполнения операции скрещивания, эволюционная стратегия и метод спуска на основе случайных 3. Разработан метод построения автоматов по обучающим примерам и темпоральным формулам на основе эволюционных алгоритмов и верификации. Его основное отличие от известных методов состоит в том, что для вычисления функции приспособленности совместно применяются обучающие примеры и верификация.

4. Разработана технология построения автоматов по обучающим примерам и темпоральным формулам.

5. Разработано инструментальное средство для автоматизации построения автоматов.

6. Разработанные методы использованы при построении автомата управления моделью беспилотного самолета и внедрены в учебный процесс. Для внедрения в учебный процесс были разработаны две виртуальные лаборатории. С их использованием лабораторные работы были выполнены более чем 150 студентами кафедры «Компьютерные технологии» НИУ ИТМО.

СПИСОК ИСТОЧНИКОВ

ПЕЧАТНЫЕ ИЗДАНИЯ НА РУССКОМ ЯЗЫКЕ

1. Букатова И. Л. Эволюционное моделирование и его приложения. М.:

Наука, 1979.

2. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. М.: Физматлит, 2006.

3. Гуров В. С., Мазин М. А., Нарвский А. С., Шалыто А. А. UML.

SWITCH-технология.

системы. 2004. № 6, c. 12 – 17. http://is.ifmo.ru/works/uml-switch-eclipse/ 4. Вельдер С. Э., Лукин М. А., Шалыто А. А., Яминов Б. Р. Верификация http://is.ifmo.ru/verification/velder_verification_posobie_nauka.pdf 5. Данилов В. Р. Метод представления автоматов деревьями решений для использования в генетическом программировании //Научнотехнический вестник СПбГУ ИТМО. 2008. Выпуск 53. Автоматное программирование, с. 103 – 108. http://is.ifmo.ru/works/2008/Vestnik/53/08genetic-automata-decision-tree-method.pdf 6. Егоров К. В., Шалыто А. А. Методика верификации автоматных программ // Информационно-управляющие системы. 2008. № 5, с. 15 – 21. http://is.ifmo.ru/works/_egorov.pdf 7. Емельянов В. В., Курейчик В. М., Курейчик В. В. Теория и практика эволюционного моделирования. М.: Физматлит, 2003.

8. Заикин А. К. Разработка методов построения конечных автоматов с использованием алгоритма имитации отжига на примере игры «Война за ресурсы» // Научно-технический вестник СПбГУ ИТМО.

2011. № 2, с. 49 – 54. http://is.ifmo.ru/works/_egorov.pdf 9. Кларк Э., Грамберг О., Пелед Д. Верификация моделей программ. М.:

МЦНМО, 2002.

10. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы.

Построение и анализ. М.: Вильямс, 2005.

11. Курейчик В.М. Генетические алгоритмы. Состояние, проблемы, перспективы // Известия РАН. Теория и системы управления. 1999. № 1, с. 144 – 160.

12. Курейчик В.В., Курейчик В.М., Сороколетов П.В. Анализ и обзор моделей эволюции // Известия РАН. Теория и системы управления.

2007. № 5, с. 114 – 126.

13. Левенштейн В. И. Двоичные коды с исправлением выпадений, вставок и замещений символов. Доклады Академии наук СССР. 1965.

14. Лобанов П. Г., Шалыто А. А. Использование генетических алгоритмов для автоматического построения конечных автоматов в задаче о «Флибах» / Сборник докладов 4-й Всероссийской научной конференции «Управление и информационные технологии» (УИТСПбГЭТУ «ЛЭТИ». 2006, с.144 – 149. http://is.ifmo.ru/works/flib 15. Лобанов П. Г. Использование генетических алгоритмов для генерации конечных автоматов. Диссертация на соискание ученой http://is.ifmo.ru/disser/lobanov_disser.pdf 16. Люгер Дж. Искусственный интеллект: стратегии и методы решения сложных проблем. М: Вильямс, 2003.

17. Мандриков Е.А., Кулев В.А. Разработка инструментального средства для генерации конечных автоматов с использованием генетических алгоритмов //Научно-технический вестник СПбГУ ИТМО. 2008.

http://is.ifmo.ru/works/2008/Vestnik/53/07-genetic-automata-tool.pdf 18. Непейвода Н. Н. Стили и методы программирования. М.: ИнтернетУниверситет Информационных технологий, 2005.

19. Николенко С. И., Тулупьев А. Л. Самообучающиеся системы.

М.: МЦНМО, 2009.

20. Норенков И. П., Арутюнян Н. М. Метагенетический алгоритм // Информационные технологии. 2007. № 3, с. 10 – 13.

21. Паращенко Д. А., Царев Ф. Н., Шалыто А. А. Технология моделирования одного класса мультиагентных систем на основе автоматного программирования на примере игры «Соревнование летающих тарелок». Проектная документация. СПбГУ ИТМО. 2006.

http://is.ifmo.ru/unimod-projects/plates/ 22. Поликарпова Н. И., Шалыто А. А. Автоматное программирование.

СПб.: Питер, 2009. http://is.ifmo.ru/books/_book.pdf 23. Поликарпова Н. И., Точилин В. Н., Шалыто А. А. Метод сокращенных таблиц для генерации автоматов с большим числом входных переменных на основе генетического программирования // Известия РАН. Теория и системы управления. 2010. № 2, 100 – 117.

http://is.ifmo.ru/works/_polikarpova_samolet.pdf мышление. СПб.: Политехника, 2012.

25. Рассел С., Норвиг П. Искусственный интеллект. Современный подход. М.: Вильямс. 2006.

26. Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002.

http://cmm.ipu.ru/proc/%D0%A8%D0%B0%D0%BB%D1%8B%D1% %D0%BE%20%D0%90.%D0%90.%20.pdf программирование задач логического управления. СПб.: Наука, 1998.

http://is.ifmo.ru/books/switch/ 29. Шалыто А. А. Логическое управление. Методы аппаратной и программной реализации. СПб.: Наука, 2000.

http://is.ifmo.ru/books/log_upr/

ПЕЧАТНЫЕ ИЗДАНИЯ НА АНГЛИЙСКОМ ЯЗЫКЕ

30. Afzal W., Torkar R., Feldt R. A Systematic Review of Search-Based Testing for Non-Functional System Properties // Information and Software Technology. 2009. Vol. 51. № 6, pp. 957 – 976.

31. Alba E., Chicano F. ACOhg: Dealing with Huge Graphs / Proceedings of the 9th annual Conference on Genetic and Evolutionary Computation (GECCO ’07). NY. : ACM. 2007, pp. 10 – 17.

32. Alba E., Chicano F. Ant Colony Optimization for Model Checking / Proceedings of the 11th International Conference on Computer Aided Systems Theory (EUROCAST 2007), pp. 523 – 530.

33. Alba E., Chicano F. Finding Safety Errors with ACO / Proceedings of the 9th annual Conference on Genetic and Evolutionary Computation (GECCO ’07). NY. : ACM. 2007, pp. 1066 – 1073.

34. Ali S., Briand L., Hemmati H., Panesar-Walawege R. K. A Systematic Review of the Application and Empirical Investigation of Search-Based TestCase Generation // IEEE Transactions of Software Engineering. 2010.

Vol. 36, № 6, pp. 742 – 762.

35. Angeline P., Pollack J. Evolutionary Module Acquisition / Proceedings of http://www.demo.cs.brandeis.edu/papers/ep93.pdf 36. Back T. Evolutionary Algorithms in Theory and Practice. Oxford University Press, 1996.

37. Bagnall A.J., Rayward-Smith V.J., Whittley I.M. The Next Release Problem // Information and Software Technology. Dec. 2001, pp. 883 – 890.

38. Belz A., Eskikaya B. A Genetic Algorithm for Finite State Automata Induction with Application to Phonotactics / Proceedings of the ESSLLIWorkshop on Automated Acquisition of Syntax and Parsing.

Saarbruecken. 1998, pp. 9 – 17.

http://www.itri.brighton.ac.uk/~Anja.Belz/Publications/A_GA_for_FSA_i nduction_with_an_application_to_phonotactics.ps 39. Benson K. Evolving Finite State Machines with Embedded Genetic Programming for Automatic Target Detection / Proceedings of the Congress on Evolutionary Computation. 2000. Vol. 2, pp. 1543 – 1549.

http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber= 40. Beyer H. G. The Theory of Evolution Strategies. Natural Computing Series. Berlin. NY: Springer-Verlag, 2001.

41. Brave S. Evolving Deterministic Finite Automata Using Cellular Encoding / Proceeding of First Annual Conference on Genetic Programming. 1996, pp. 39 44. http://citeseer.ist.psu.edu/131538.html 42. Bryant R. E. Graph-based algorithms for boolean function manipulation / IEEE Transactions on Computers. 1986, Vol. 35, pp. 677 – 691.

43. Chambers L. Practical Handbook of Genetic Algorithms. Complex Coding Systems. Volumes I. II, III. CRC Press, 1999.

44. Courcoubetis C., Vardi M., Wolper P., Yannakakis M. Memory-Efficient Algorithms for the Verification of Temporal Properties / Formal Methods in System Design. 1992, pp. 275 – 288.

45. Clark J., Dolado J. J., Harman M., Hierons R., Jones B., Lumkin M., Mitchell B., Mancoridis S., Rees K., Roper M., Shepperd M.

Reformulating Software Engineering as a Search Problem. IEEE Proceedings-Software. 2003. Vol. 150. № 3, pp. 161 – 175.

46. Das R., Mitchell M., Crutchfield J. P. A genetic algorithm discovers particle-based computation in cellular automata // Lecture Notes in www.santafe.edu/research/publications/workingpapers/94-03-015.pdf 47. De Castro L., Timmis J. Artificial Immune Systems: A New Computational Intelligence Approach. Springer, 2002.

48. De Jong K. Evolutionary computation: a unified approach. MIT Press, Cambridge. MA, 2006.

49. Dorigo M., Stutzle T. Ant Colony Optimization. The MIT Press, 2004.

50. Eisenstein J. Evolving robot tank fighters. Technical Report AIM-2003AI Lab. MIT, 2003.

51. Ferrante N. Cotta C., Moscato P. Handbook of Memetic Algorithms. Berlin, NY: Springer-Verlag, 2012.

52. Fogel L. Autonomous Automata // Industrial Research. 1962. V.4, 53. Fogel L., Owens A., Walsh M. Artificial Intelligence through Simulated Evolution. NY: Wiley, 1966.

54. Frey C., Leugering G. Evolving Strategies for Global Optimization – A Finite State Machine Approach /Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001). Morgan Kaufmann. 2001, pp. 27 – 33. http://citeseer.ist.psu.edu/456373.html 55. Gastin P., Oddoux D. Fast LTL to Bchi Automata Translation / 13th Conference on Computer Aided Verification (CAV'01). 2001, pp. 53 – 65.

56. Gerth R., Peled D., Vardi M. Y.,Wolper P. Simple On-the-fly Automatic Verification of Linear Temporal Logic / Proc. of the 15th Workshop on Protocol Specification. Testing and Verification. Warsaw. 1995, 57. Ghnemat R., Khatatneh K., Oqeili S., Bertelle C., Duchamp G. Automatabased adaptive behavior for economic modeling using game theory. 2005.

http://arxiv.org/abs/cs/ 58. Glover F. Tabu search: A tutorial //Interfaces. 1990. Vol. 20, pp. 74 – 94.

59. Glover F., Laguna M., Mart R. Fundamentals of Scatter Search and Path Relinking // Control and Cybernetics, 2000. № 29 (3), pp. 653 – 60. Godefroid P. Model Checking for Programming Languages using Verisoft / Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages, pp. 174 – 186.

61. Gold E. M. Complexity of automaton identification from given data. // Information and Control. 1978. № 37, pp. 302 320.

62. Goldberg D. A Note on Boltzmann Tournament Selection for Genetic Algorithms and Population-Oriented Simulated Annealing // Complex Systems. 1990. Vol. 4, pp. 445 460.

63. Goldsby H. J., Cheng B. H. Avida-MDE: a digital evolution approach to generating models of adaptive software behavior / Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation (GECCO’08), pp. 1751 – 1758.

64. Hamming R. Error detecting and error correcting codes // Bell System Technical Journal 29 (2), pp. 147 – 160.

65. Harel D., Pnueli A. On the development of reactive systems / In «Logic and Models of Concurrent Systems». NATO Advanced Study Institute on Logic and Models for Verification and Specification of Concurrent Systems. Springer Verlag, 1985. pp. 477 – 498.

66. Harman M., Hierons R., Proctor M. A new representation and crossover operator for search-based optimization of software modularization / In GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference (NY, 2002). Morgan Kauffman Publishers, pp. 1351 – 1358.

67. Harman M. Automated Test Data Generation Using Search-Based Software Engineering / Proceedings of 2nd International Workshop Automation of Software Test (AST 07). IEEE CS Press, 2007, p. 2.

68. Harman M., Tratt L. Pareto Optimal Search-Based Refactoring at the Design Level / Proceedings of 9th Annual Conference on Genetic and Evolutionary Computation (GECCO 07). ACM Press. 2007, pp. 1106 – 1113.

69. Harman M., Mansouri A., Zhang Y. Search-Based Software Engineering:

A Comprehensive Analysis and Review of Trends, Techniques, and Applications. Tech. report TR-09-03. Dept. of Computer Science. King’s College London, 2009.

70. Harman M. Why the Virtual Nature of Software Makes It Ideal for Search-Based Optimization / Proceeding of 13th International Conference Fundamental Approaches to Software Engineering (FASE 10). IEEE CS Press. 2010, pp. 1 – 12.

71. Harman M. Software Engineering Meets Evolutionary Computation // Computer. 2011. Vol. 44. № 11, pp. 31 – 39.

72. Harman M., Clark J. Metrics are fitness functions too / Proceedings of 10th International Symposium on Software Metrics. 2004, pp. 58 – 69.

73. Hoffman L. Talking Model-Checking Technology // Communications of the ACM. 2008. V. 51. № 7, pp. 110 – 112.

74. Holland J. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975.

75. Holland J. ECHO: Explorations of Evolution in a Miniature World / Proceedings of the Second Conference on Artificial Life. Redwood City.

CA: Addison-Wesley, 1990.

76. Holzmann G. J. The Model Checker SPIN // IEEE Transactions on software engineering. 1997. Vol. 23. Issue 5, pp. 279 – 295.

77. Horihan J., Yung-Hsiang Lu. Improving FSM evolution with progressive fitness functions / GLSVLSI '04: Proceedings of the 14th ACM Great Lakes symposium on VLSI. NY: ACM Press. 2004, pp. 123 126.

78. Huang D. MS Thesis Preproposal: Adaptive Incremental Fitness http://www.cs.rit.edu/~dxh6185/downloads/MS_Thesis/Documents/Prese ntation.pdf 79. Jefferson D., Collins R., Cooper C., Dyer M., Flowers M., Korf R., Taylor C., Wang A. The Genesys System: Evolution as a Theme in Artificial Life www.cs.ucla.edu/~dyer/Papers/AlifeTracker/Alife91Jefferson.html 80. Johnson C. Genetic Programming with Fitness based on Model Checking.

Lecture Notes in Computer Science. Springer Berlin / Heidelberg. 2007.

Volume 4445/2007, pp. 114 – 124.

81. Juillie H., Pollack J. Coevolving the «Ideal» Trainer: Application to the http://citeseer.ist.psu.edu/16712.html 82. Kennedy J., Eberhart R. C. Swarm Intelligence. Morgan Kaufmann. 2001.

83. Kirsopp C., Shepperd M., Hart J. Search heuristic, case-based reasoning and software project effort prediction / GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference. NY: 2002, pp. 1367 – 84. Koza J. Genetic programming. On the Programming of Computers by Means of Natural Selection. MA: The MIT Press, 1998.

85. Koza J. Genetic Evolution and Co-Evolution of Computer Programs / Proceedings of Second Conference on Artificial Life. Redwood City, CA:

Addison-Wesley. 1992. pp. 603 629. http://citeseer.ist.psu.edu/177879.html 86. Larranaga P., Lozano J. A. Estimation of distribution algorithms: A new tool for evolutionary computation. Kluwer Academic Publishers. Boston, 87. Levy S. Artificial Life: The Quest for a New Creation. NY: Pantheon, 88. Lucas S., Reynolds J. Learning DFA: Evolution versus Evidence Driven State Merging / The 2003 Congress on Evolutionary Computation (CEC '03). Vol. 1, pp. 351 – 358.

89. Lucas S., Reynolds J. Learning Deterministic Finite Automata with a Smart State Labeling Algorithm // IEEE Transactions on Pattern Analysis and Machine Intelligence. 2005. Vol. 27. № 7, pp. 1063 – 1074.

90. Lucas S. Evolving Finite-State Transducers: Some Initial Explorations.

Lecture Notes in Computer Science. Springer Berlin / Heidelberg. Volume 2610/2003, pp. 241 – 257. http://www.springerlink.com/content/41a34vg70fp1hltb/ 91. Mancoridis S., Mitchell B. S., Rorres C., Chen Y., Gansner E. R. Using Automatic Clustering to Produce High-Level System Organizations of Source Code / Proceedings of the 6th International Workshop on Program Comprehension (IWPC ’98), pp. 45 – 52.

92. McMillan K. L. Symbolic model checking: an approach to the state explosion problem. PhD thesis. SCS. Carnegie Mellon University, 1992.

93. McMinn P. Search-Based Software Test Data Generation: A Survey // Software Testing, Verification and Reliability. 2004. Vol. 14.

94. Metropolis N., Rosenbluth A., Rosenbluth M., Teller A., Teller E. Equation of state calculations by fast computing machines. Journal of Chemical Physics. 1953. Vol. 21, pp. 1087 – 1092.

95. Miller J. The Coevolution of Automata in the Repeated Prisoner's Dilemma. Working Paper. Santa Fe Institute. 1989 // Journal of Economic Behavior & Organization. 1996. Vol. 29. Issue 1, pp. 87 – 112.

96. Mitchell B. S. A Heuristic Search Approach to Solving the Software Clustering Problem. PhD Thesis. Drexel University, Philadelphia.

97. Mitchell B. S., Mancordis S. Using heuristic search techniques to extract design abstractions from source code / GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference (NY, 2002), 98. Mitchell M. An Introduction to Genetic Algorithms. MA: The MIT Press, 99. Mitchell M., Crutchfield J. P., Hraber P. T. Evolving cellular automata to perform computations. Physica D. 1993. Vol. 75, pp. 361 – 391.

http://web.cecs.pdx.edu/~mm/mech-imped.pdf 100. Mitchell M., Holland J., Forrest S. When Will a Genetic Outperform Hill Climbing? / Advances in Neural Information Processing Systems 6. San Mateo. CA: Morgan Kaufmann, 1994.

101. Moonjoo K., Viswanathan M., Ben-Abdallah H., Kannan S., Lee I., Sokolsky O. Formally specified monitoring of temporal properties / Proceedings of the 11th Euromicro Conference on Real-Time Systems, 102. Naidoo A., Pillay N. The Induction of Finite Transducers Using Genetic Programming / Proceedings of the 10th European conference on Genetic programming, pp. 371 – 380. http://saturn.cs.unp.ac.za/~nelishiap/papers/eurogp07.pdf 103. Nedjah N., Mourelle L. Mealy Finite State Machines: An Evolutionary Approach // International Journal of Innovative Computing, Information and Control. 2006. Vol. 2. Issue 4, pp. 789 – 806.

104. Niebert P., Peled D., Pnueli A. Discriminative Model Checking. Lecture Notes In Computer Science. Springer Berlin / Heidelberg. 2008. Vol.

5123/2008, pp. 504 – 516.

105. Nocedal J., Wright S. Numerical Optimization. 2006. Berlin, NY:

Springer-Verlag.

Maintenance / Proceedings of Conference on Software Maintenance and Reengineering (CSMR 06). IEEE CS Press. 2006, pp. 249 – 260.

107. Petrovic P. Simulated evolution of distributed FSA behaviour-based arbitration. Poster at The Eighth Scandinavian Conference on Artificial Intelligence (SCAI'03). 2003.

http://www.idi.ntnu.no/grupper/ai/eval/incremental/scai03-posterpetrovic.pdf 108. Petrovic P. Evolving automatons for distributed behavior arbitration.

Technical Report. Norwegian University of Science and Technology, 2005. http://www.idi.ntnu.no/~petrovic/shortpaper.pdf 109. Petrovic P. Comparing Finite-State Automata Representation with GPtrees. Technical Report. Norwegian University of Science and Technology, 2006. http://www.idi.ntnu.no/~petrovic/fsatr/fsatr.pdf 110. Rih O. A Survey on Search-Based Software Design //Computer Science Rev. 2010. Vol. 4. № 4, pp. 203 – 249.

111. Ray T. An Approach to the Synthesis of Life / In Artificial Life II. MA:

Addison-Wesley. 1992, pp. 371 408.

112. Reynolds C. W. Competition, Coevolution and the Game of Tag / Proceedings of Artificial Life IV. Cambridge. MA: MIT Press. 1994, pp. 59 69. http://www.red3d.com/cwr/papers/1994/alife4.html 113. Schrijver A. Theory of linear and integer programming. John Wiley and Sons, 1998.

114. Spears W., Gordon D. Evolving Finite-State Machine Strategies for Protecting Resources. Lecture Notes in Computer Science. Springer Berlin / Heidelberg. Volume 1932/2009, pp. 5 – 28.

115. Spichakova M. Genetic Inference of Finite State Machines. Masters thesis.

Tallinn, 2007. http://s-ma-u-g.googlecode.com/files/thesis.pdf 116. Tomita M. Dynamic construction of finite automata from examples using hill climbing / Proceedings of the 4th Annual Cognitive Science Conference (USA, 1982), pp. 105 – 108.

117. Tu M., Wolff E., Lamersdorf W. Genetic Algorithms for Automated Negotiations: A FSM-based Application Approach /Proceedings of the 11th International Conference on Database and Expert Systems, 2000.

http://ieeexplore.ieee.org/iel5/7035/18943/00875153.pdf 118. Von Neumann J., Burks A. The Theory of Self-reproducing Automata.

Urbana. Univ. of Illinois Press, 1966.

119. Wegener J., Baresel A., Sthamer H. Evolutionary test environment for automatic structural testing // Information and Software Technology Special Issue on Software Engineering using Metaheuristic Innovative Algorithms. 2001. Vol. 43. Issue 14, pp. 841 – 854.

120. Whitley D. The GENITOR Algorithm and Selective Pressure / Proceedings of the 3rd International Conference on Genetic Algorithms.

http://www.genalgo.com/index.php?option=com_content&task=view&id= 80&Itemid= 121. Zhang Y., Finkelstein A., Harman M. Search-Based Requirements Optimisation: Existing Work and Challenges / Proceedings of Internationall Working Conference on Requirements Engineering:

Foundation for Software Quality (REFSQ 08). LNCS 5025. Springer.

122. Zomorodian A. Context-free Language Induction by Evolution of Deterministic Push-Down Automata Using Genetic Programming.

http://www.cs.dartmouth.edu/~afra/papers/aaai96/aaai96.pdf

РЕСУРСЫ СЕТИ ИНТЕРНЕТ

123. Бедный Ю. Д., Шалыто А. А. Применение генетических алгоритмов для построения автоматов в задаче «Умный муравей». СПбГУ ИТМО, 2007. http://is.ifmo.ru/works/ant 124. Государственный контракт «Применение методов искусственного интеллекта в разработке управляющих программных систем».

http://is.ifmo.ru/science/_nk-408-15-2.pdf 125. Государственный контракт «Разработка технологии верификации управляющих программ со сложным поведением, построенных на основе автоматного подхода». Промежуточный отчет по I этапу «Выбор направления исследований и базовых компонентов». СПбГУ ИТМО, 2007. http://is.ifmo.ru/verification/_2007_01_reportverification.pdf 126. Государственный контракт «Разработка технологии верификации управляющих программ со сложным поведением, построенных на основе автоматного подхода». Промежуточный отчет по II этапу «Теоретические исследования поставленных перед НИР задач».

СПбГУ ИТМО, 2007. http://is.ifmo.ru/verification/_2007_02_reportverification.pdf 127. Государственный контракт «Разработка технологии верификации управляющих программ со сложным поведением, построенных на основе автоматного подхода». Промежуточный отчет по III этапу «Экспериментальные исследования поставленных перед НИР задач».

СПбГУ ИТМО, 2007. http://is.ifmo.ru/verification/_2007_02_reportverification.pdf 128. Государственный контракт «Разработка технологии верификации управляющих программ со сложным поведением, построенных на основе автоматного подхода». Заключительный отчет по IV этапу «Обобщение и оценка результатов исследований». СПбГУ ИТМО, 2007. http://is.ifmo.ru/verification/_2007_02_report-verification.pdf 129. Государственный контракт «Технология генетического программирования для генерации автоматов управления системами со сложным поведением». Промежуточный отчет по этапу I «Выбор направлений исследований и базовых компонентов». СПбГУ ИТМО, 2007. http://is.ifmo.ru/genalg/_2007_01_report-genetic.pdf 130. Государственный контракт «Технология генетического программирования для генерации автоматов управления системами со сложным поведением». Промежуточный отчет по этапу II «Теоретические исследования поставленных перед НИР задач».

СПбГУ ИТМО, 2007. http://is.ifmo.ru/genalg/_2007_02_reportgenetic.pdf 131. Государственный контракт «Технология генетического программирования для генерации автоматов управления системами со сложным поведением». Промежуточный отчет по этапу III «Экспериментальные исследования поставленных перед НИР задач».

СПбГУ ИТМО, 2007. http://is.ifmo.ru/genalg/_2007_03_reportgenetic.pdf 132. Государственный контракт «Технология генетического программирования для генерации автоматов управления системами со сложным поведением». Промежуточный отчет по этапу IV «Обобщение и оценка результатов исследований». СПбГУ ИТМО, 2007. http://is.ifmo.ru/genalg/_2007_04_report-genetic.pdf 133. Государственный контракт «Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов». Промежуточный отчет по этапу I. СПбГУ ИТМО, 2009. http://is.ifmo.ru/science/_nk-385-1-1.pdf 134. Данилов В. Р. Технология генетического программирования для генерации автоматов управления системами со сложным поведением.

http://is.ifmo.ru/download/danilov\_bachelor.pdf 135. Данилов В. Р. Методы представления функции переходов при генерации автоматов управления на основе генетического программирования. Магистерская диссертация. СПбГУ ИТМО, 2009.

http://is.ifmo.ru/papers/_2010_02_25_danilov.pdf 136. Заочный тур всесибирской олимпиады 2005 по информатике.

http://olimpic.nsu.ru/widesiberia/archive/wso6/2005/rus/1tour/problem/pr oblem.html 137. Колыхматов И. И., Рыбак О. О., Шалыто А. А. Моделирование устройства для продажи газированной воды на инструментальном средстве UniMod. Проектная документация. СПбГУ ИТМО. 2006.

http://is.ifmo.ru/download/vending-machine-ru.pdf 138. Николенко С. И. Лекции по генетическим алгоритмам.

http://logic.pdmi.ras.ru/~sergey/teaching/ml/04-genetic.pdf 139. Сайт www.genetic-programming.com 140. Сайт http://www.flightgear.org/ 141. Яминов Б. Р. Генетические алгоритмы.

http://rain.ifmo.ru/cat/view.php/theory/unsorted/genetic-2005/ 142. Analysis of variance (ANOVA).

http://www.csse.monash.edu.au/~smarkham/resources/anova.htm 143. Bogor. Software Model Checking Framework.

http://bogor.projects.cis.ksu.edu/ 144. Learning DFS from Noisy Samples. A contest from GECCO 2004.

http://cswww.essex.ac.uk/staff/sml/gecco/NoisyDFA.html 145. Levent A. H., Mericli C., Mericli T. и др. Cerberus’08 Team Report.

http://www.tzi.de/spl/pub/Website/Teams2008/Cerberus.pdf 146. LTL2BA project. http://www.lsv.ens-cachan.fr/~gastin/ltl2ba/ 147. The R Project for Statistical Computing. http://www.r-project.org/

ПУБЛИКАЦИИ АВТОРА

148. Царев Ф. Н. Совместное применение генетического программирования, конечных автоматов и искусственных нейронных сетей для построения системы управления беспилотным летательным аппаратом http://is.ifmo.ru/works/2008/Vestnik/53/03-genetic-neuro-automata-flying-plates.pdf 149. Царев Ф. Н., Давыдов А. А., Соколов Д. О. Применение генетического программирования и методов сокращенных таблиц переходов и деревьев решений для построения автоматов управления моделью беспилотного летательного аппарата //Научно-технический вестник СПбГУ ИТМО. 2008. Вып. 53. Автоматное программирование, с. 60 – 79. http://is.ifmo.ru/works/2008/Vestnik/53/04-genetic-automataredused-transition-table-flying.pdf 150. Царев Ф. Н. Метод построения управляющих конечных автоматов на основе тестовых примеров с помощью генетического программирования // Информационно-управляющие системы. 2010. № 5, с. 31 – 36. http://is.ifmo.ru/works/_zarev.pdf 151. Царев Ф. Н., Егоров К. В., Шалыто А. А. Применение генетического программирования для построения автоматов управления системами со сложным поведением на основе обучающих примеров и спецификации // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики http://is.ifmo.ru/works/_2010_10_13_egorov.pdf 152. Царев Ф. Н., Александров А. В., Казаков С. В. Сергушичев А. А., Шалыто А. А. Генерация конечных автоматов для управления моделью беспилотного самолета // Научно-технический вестник СПбГУ ИТМО. 2011. № 2, с. 3 – 11. http://is.ifmo.ru/works/2011/Vestnik/72-2/01Aleksandrov-Kazakov-Tsarev-Shalyto.pdf 153. Царев Ф. Н., Егоров К. В., Шалыто А. А. Совместное применение генетического программирования и верификации для построения автоматов управления системами со сложным поведением // Труды СПИИРАН. 2010. Вып. 15, с. 123 – 135.

Материалы конференций с участием автора 154. Царев Ф. Н., Шалыто А. А. Применение генетического программирования для построения мультиагентной системы одного класса /Международная научно-техническая мультиконференция «Проблемы информационно-компьютерных технологий и мехатроники». Материалы международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы»

(МВУС`2007). Таганрог: НИИМВС. Т. 2, с. 46 – 51.

155. Царев Ф. Н., Шалыто А. А. Применение генетического программирования для генерации автоматов в задаче об «Умном муравье»

/Сборник научных трудов. IV-я Международная научнопрактическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте». М.: Физматлит. 2007, с. 590 – 597. http://is.ifmo.ru/genalg/_ant_ga.pdf 156. Царев Ф. Н., Шалыто А. А. О построении автоматов с минимальным числом состояний для задачи об «Умном муравье» //Сборник докладов X международной конференции по мягким вычислениям и измерениям. СПбГЭТУ «ЛЭТИ». Т.2. 2007, с. – http://is.ifmo.ru/download/ant_ga_min_number_of_state.pdf 157. Царев Ф. Н., Шалыто А. А. Применение генетических алгоритмов для построения автоматов с минимальным числом состояний для задачи об «Умном муравье» / Тезисы научно-технической конференции «Научно-программное обеспечение в образовании и научных исследованиях». СПбГПУ. 2008, с. 209 – 215.

http://is.ifmo.ru/download/2008-02-25_tsarev_shalyto.pdf 158. Tsarev F., Davydov A., Sokolov D. Application of Genetic Algorithms for Construction of Moore Automation and Systems of Interacting Mealy Automata in «Artificical Ant» Problem / Proceeding of the Second Spring http://is.ifmo.ru/genalg/_2008_07_03_ant.pdf 159. Tsarev F., Davydov A., Sokolov D., Shalyto A. Application of Genetic Programming for Generation of Controllers represented by Automata / Preprints of the 13th IFAC Symposium on Information Control Problems http://is.ifmo.ru/articles_en/_ifac-2009.pdf 160. Царев Ф. Н. Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования /Сборник докладов международной конференции по мягким вычислениям и измерениям (SCM`2009). СПбГЭТУ «ЛЭТИ».

Т. 1, с. 231 – 234. http://is.ifmo.ru/works/_scm-2010_tsarev.pdf 161. Царев Ф. Н. Метод построения автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования / Материалы Международной научной конференции «Компьютерные науки и информационные технологии». Саратов: СГУ. 2009, с. 216 – 219.

162. Tsarev F., Alexandrov A., Sergushichev A., Kazakov S. Genetic Algorithm for Induction of Finite Automation with Continuous and Discrete Output Actions / Proceedings of the 2011 GECCO Conference Companion on Genetic and Evolutionary Computation. NY. : ACM. 2011, pp. 775 – 778.

http://is.ifmo.ru/articles_en/2011/GECCO2011-Alexandrov-KazakovSergushichev-Tsarev.pdf 163. Царев Ф. Н., Егоров К. В. Совместное применение генетического программирования и верификации моделей для построения автоматов управления системами со сложным поведением /Сборник трудов конференции «Информационные технологии и системы» (ИТИС`09).

М.: Институт проблем передачи информации им. А. А. Харкевича http://is.ifmo.ru/genalg/_2010_01_14_egorov_tsarev.pdf 164. Царев Ф. Н., Александров А. В., Казаков С. В., Сергушичев А. А. Генетическое программирование на основе обучающих примеров для построения конечных автоматов управления моделью беспилотного самолета /Сборник докладов международной конференции по мягким вычислениям и измерениям (SCM`2010). СПбГЭТУ «ЛЭТИ». Т. 1, с. 263 – 267. http://is.ifmo.ru/works/_scm-2010_autopilot.pdf 165. Царев Ф. Н., Егоров К. В., Парфенов В. Г. Совместное применение генетического программирования и верификации моделей для построения автоматов управления системами со сложным поведением /Труды XVII Всероссийской научно-методической конференции «Телематика`2010». Т. 2. СПбГУ ИТМО. 2010, с. 344, 345.

166. Царев Ф. Н., Егоров К. В. Применение генетического программирования для построения автоматов управления системами со сложным поведением на основе верификации моделей и обучающих примеров / Сборник «Список-2011». Материалы второй межвузовской научной конференции по проблемам информатики». СПб.: ВВМ. 2011, с. 343 – 350. http://is.ifmo.ru/works/2011/SPISOK/07-Egorov-Tsarev.pdf 167. Tsarev F., Egorov K. Finite State Machine Induction using Genetic Programming Based on Testing and Model Checking / Proceedings of the http://is.ifmo.ru/articles_en/2011/GECCO2011-Tsarev-Egorov-FSM-induction.pdf 168. Царев Ф. Н., Давыдов А. А., Соколов Д. О., Шалыто А. А. Виртуальная лаборатория обучения генетическому программированию для генерации управляющих конечных автоматов / Сборник докладов III Международной научно-практической конференции «Современные информационные технологии и ИТ-образование». ВМК МГУ. М.:

http://is.ifmo.ru/works/_2_93_davidov_sokolov.pdf 169. Царев Ф. Н., Тяхти А. С., Чебатуркин А. А., Шалыто А. А. Виртуальная лаборатория для обучения методам искусственного интеллекта для генерации управляющих конечных автоматов / Сборник докладов IV Международной научно-практической конференции «Современные информационные технологии и ИТ-образовние». М.:

ИНТУИТ.РУ, МГУ. 2009, с. 222 – 227. http://is.ifmo.ru/works/_2010tjahti.pdf 170. Tsarev F., Chivilikhin D., Ulyantsev V. Test-Based Extended Finite-State Machines Induction with Evolutionary Algorithms and Ant Colony Optimization / Proceedings of the 2012 GECCO Conference Companion on Genetic and Evolutionary Computation. NY. : ACM. 2012, pp. 603 – 606.

http://is.ifmo.ru/articles_en/2012/GECCO12-Chivilikhin-UlyantsevTsarev.pdf

ПРИЛОЖЕНИЕ 1. СВИДЕТЕЛЬСТВА О РЕГИСТРАЦИИ

ПРОГРАММ ДЛЯ ЭВМ

ПРИЛОЖЕНИЕ 2. ПРИМЕР ОТЧЕТА ПО ЛАБОРАТОРНОЙ РАБОТЕ

Отчет по лабораторной работе «Построение управляющих конечных автоматов с помощью эволюционных алгоритмов»

Цель данной лабораторной работы – применение эволюционной стратегии для построения по тестам конечного автомата управления часами с будильником.

При выполнении работы использовался язык программирования Java.

Цель данной лабораторной работы – построение по тестам конечного автомата управления часами с будильником. В систему тестов для построения автомата управления часами с будильником включены тесты, описывающие его работу во всех трех режимах. Набор из 38 тестов взят из работы [1].

Конечный автомат при использовании эволюционной стратегии представляется в виде объекта, содержащего множество состояний. Будем считать, что начальным состоянием автомата считается состояние с номером ноль, поэтому номер начального состояния в явном виде хранить не требуется. Каждое состояние описывается множеством переходов, инцидентных ему, и числом выходных воздействий, совершаемых при входе в данное состояние. Каждый переход описывается номером состояния, в которое переходит автомат, и числом выходных воздействий, совершаемых на переходе.

Выбор представления графа переходов автомата с помощью списков ребер (в отличие от работы [2], в которой применялись полные таблицы переходов) обоснован тем, что, как правило, в автоматах управления системами со сложным поведением не в каждом состоянии определена реакция на каждое событие (граф переходов конечного автомата разрежен).

Параметром особи является максимальное число действий, совершаемых на переходах.

Рассматриваемый управляющий автомат является автоматом Мили), так как выходные воздействия вырабатываются только на переходах.

Заметим, что автоматы Мура и Мили являются частным случаем автомата смешанного типа. При значении максимального числа действий, совершаемых на переходах автомата, равным нулю получим автомат Мура. При значении числа действий, совершаемых при входе в состояния, равным нулю получим автомат Мили.

В особи кодируется только «скелет» управляющего конечного автомата, а конкретные выходные воздействия, вырабатываемые на переходах и в состояниях, определяются с помощью алгоритма расстановки выходных воздействий (рис. 1).

Рис. 1. Пример графа переходов управляющего автомата после применения алгоритма расстановки выходных воздействий При выполнении операции мутации с заданной вероятностью (по умолчанию, она равна 0.1) выполняется каждое из действий:

изменение описания каждого из переходов (рис. 2);

удаление или добавление перехода для каждого из состояний При изменении описания перехода с некоторой вероятностью выполняется одно из следующих действий:

изменение состояния, в которое ведет переход, – оно изменяется на случайно выбранное;

изменение числа выходных воздействий, вырабатываемых на этом переходе, – с равной вероятностью изменяется на максимально допустимого числа действий, совершаемых на переходах (предварительно заданная величина, по умолчанию При изменении описания состояния выполняется изменение числа выходных воздействий, вырабатываемых при входе в вершину, – с равной вероятностью изменяется на случайно выбранное число в диапазоне от нуля до максимально допустимого числа действий, совершаемых при входе в вершину (предварительно заданная величина, по умолчанию равная трем).

образом. Обозначим как P1 и P2 «родительские» особи, а как S1 и S2 – отдельно для каждого состояния.

Обозначим список переходов из состояния номер i автомата P1 как P1.T[i], а список переходов из состояния номер i автомата P2 как P2.T[i].

Для выполнения «скрещивания состояний» с равной вероятностью может быть выбран один из двух методов.

При использовании традиционного метода скрещивания (рис. 4) списки переходов S1.T[i] и S2.T[i] строятся следующим образом:

распределяются случайным образом между списками распределяются случайным образом между списками присутствует соответствующий переход (из списка P1.T[i]), то переход добавляется в список переходов Действия в самих состояниях распределяются также случайным образом.

Рис. 4. Пример традиционного метода скрещивания для состояний При использовании метода скрещивания с учетом тестов скрещивание производится аналогичным образом, за тем исключением, «родительских» особей в особи-«потомки». Данные переходы и состояния определяются тестами (по умолчанию десятой частью всех тестов), на которых автоматы показали результат «лучше», чем на остальных тестах.

Функция приспособленности основана на редакционном расстоянии.

Для ее вычисления выполняются следующие действия: на вход автомату автомат на входе Input[i] как Output[i]. После этого для каждого теста вычисляется величина где ED(A, B) – редакционное расстояние между строками A и B. Отметим, что значения этой функции лежат в пределах от 0 до 1, при этом, чем «лучше» автомат соответствует тесту, тем больше значение функции приспособленности.

Функция приспособленности особи зависит не только от того, насколько «хорошо» автомат работает на тестах, но и числа переходов, FF (FFi (| Output[i] | | Answer[i] |)), где как cnt обозначено число переходов в автомате. Эта функция приспособленности устроена таким образом, что при одинаковом уровне прохождения тестов преимущество имеет автомат, содержащий меньше переходов. Кроме этого, автомат, который хоть немного лучше проходит тесты, оценивается выше, чем автомат, проходящий тесты хуже, пусть даже и имеющий меньшее число переходов.

Построение конечного автомата управления часами с будильником проводилось при следующих параметрах эволюционной стратегии:

размер параметра устанавливался в значения 1, 100, 1000;

максимальное допустимое число действий в состояниях равно максимальное допустимое число действий на переходах равно число состояний автомата равно четырем;

В результате работы эволюционной стратегии на одном из запусков был построен автомат, в котором из начального достижимы только три состояния из четырех. Если удалить недостижимое состояние, то этот граф переходов будет изоморфен построенному вручную.

График зависимости значения функции приспособленности от времени приведен на рис. 5 при одном из запусков алгоритма.