автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы построения конечных автоматов на основе эволюционных алгоритмов

На правах рукописи

Царев Федор Николаевич

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

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 5 НОЯ 2012

Санкт-Петербург - 2012 г.

005054788

005054788

Работа выполнена на кафедре «Компьютерные технологии» Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики (НИУ ИТМО).

Научный руководитель доктор технических наук,

профессор

Шалыто Анатолий Абрамович

Официальные оппоненты Тулупьев Александр Львович, доктор

физико-математических наук, доцент, заведующий лабораторией теоретических и междисциплинарных проблем информатики Санкт-Петербургского института информатики и автоматизации Российской академии наук

Тропченко Александр Ювенальевич, доктор технических наук, профессор, профессор кафедры «Вычислительная техника» НИУ ИТМО

Ведущая организация Институт проблем управления им.

В. А. Трапезникова Российской академии наук

Защита диссертации состоится 29 ноября 2012 года в 17 часов 00 минут на заседании диссертационного совета Д212227.06 при НИУ ИТМО по адресу: 197101, Санкт-Петербург, Кронверкский пр., д. 49, Центр Интернет-образования.

С диссертацией можно ознакомиться в библиотеке НИУ ИТМО.

Автореферат разослан «26» октября 2012 года.

Ученый секретарь диссертационного совета, Л. С. Лисицына

доктор технических наук, профессор С"^г&С^

Общая характеристика работы

Актуальность проблемы. В последнее время при разработке программного обеспечения (ПО) для управляющих систем все шире применяется автоматное программирование - парадигма программирования, при использовании которой программу предлагается строить в виде совокупности автоматизированных объектов управления, каждый из которых содержит систему управления (один или несколько взаимодействующих конечных автоматов, в дальнейшем - автоматов) и объект управления. При этом программы, построенные на основе указанной парадигмы, называются автоматными. Важным достоинством автоматного программирования является то, что при его использовании существенно упрощается верификация программ на основе метода Model Checking, так как построение модели Крипке по автоматной программе и обратный переход могут быть автоматизированы.

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

В последнее десятилетие активно развивается область исследований, называемая поисковой инженерией ПО (Search-Based Software Engineering), в которой для решения задач программной инженерии предлагается применять алгоритмы поисковой оптимизации, в частности, эволюционные алгоритмы (генетические алгоритмы, эволюционные стратегии и метод спуска на основе случайных мутаций).

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

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

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

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

Основные задачи диссертационной работы состоят в следующем:

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

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

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

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

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

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

Научная новизна. В работе получены следующие новые научные результаты, которые выносятся на защиту:

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

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

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

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

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

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

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

Внедрение результатов работы. Результаты диссертации использовались при выполнении научно-исследовательских работ по следующим государственным контрактам: «Технология генетического программирования для генерации автоматов управления системами со сложным поведением» (государственный контракт

№02.514.11.4044 от 18.05.2007 г. по Федеральной целевой программе «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы»), «Разработка методов совместного применения генетического и автоматного программирования для построения систем управления беспилотными летательными аппаратами» (государственный контракт № П1188 от 27.08.2009 г. по Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы), «Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов» (государственный контракт № П2174 от 09.11.2009 г. по Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы), «Применение методов искусственного интеллекта в разработке управляющих программных систем» (государственный контракт № П2236 от 11.11.2009 г. по Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы), в рамках проекта «Подготовка и переподготовка профильных специалистов на базе центров ¡бразования и разработок в сфере информационных технологий в Северо-Западном юдерапьном округе» (Государственный контракт № 07.Р20.11.0028 от 07.09.2011 г.), а акже в учебном процессе на кафедре «Компьютерные технологии» в рамках курса Теория автоматов и программирование».

Апробация результатов работы. Основные положения диссертационной аботы докладывались на следующих научных и научно-практических конференциях: V Международная научно-практическая конференция «Интегрированные модели и ягкие вычисления в искусственном интеллекте» (Коломна, 2007), научно-ехническая конференция «Научное программное обеспечение в образовании и аучных исследованиях» (СПбГПУ, 2008), XII Всероссийская конференция по роблемам науки и высшей школы «Фундаментальные исследования и инновации в ехнических университетах» (СПбГПУ, 2008), Second Spring Young Researchers' lolloquium on Software Engineering (SYRCoSE'2008, SPbSU, 2008), III и IV 1еждународная научно-практическая конференция «Современные информационные зхнологии и ИТ-образование» (ВМК МГУ, 2008, 2009), научно-практическая энференция студентов, аспирантов, молодых ученых и специалистов Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы рограмм в искусственном интеллекте (ИММВИИ-2009)» (Коломна, 2009), VI и VII ежвузовская конференция молодых ученых (СПбГУ ИТМО, 2009, 2010), X, XI и XII [еждународная конференции по мягким вычислениям и измерениям ГПбГЭТУ (ЛЭТИ), 2009, 2010, 2011), Международная научная конференция Компьютерные науки и информационные технологии» памяти А. М. Богомолова Саратовский государственный университет имени Н. Г. Чернышевского, 2009), 32-я энференция молодых ученых и специалистов Института проблем передачи «формации им. А. А. Харкевича РАН «Информационные технологии и 1стемы» (2009), XL научная и учебно-методическая конференция профессорско-эеподавательского и научного состава СПбГУ ИТМО (2011), 14-th Annual Graduate udents Workshop (part of the «Genetic and Evolutionary Computation Conference» ECCO - 2011, Dublin, organized by ACM SIGEVO, 2011), вторая межвузовская

научная конференция по проблемам информатики (СПИСОК, СПбГУ, 2011), ХЫ научная и учебно-методическая конференция НИУ ИТМО (2012), 15-th Annual Graduate Students Workshop (part of the «Genetic and Evolutionary Computation Conference» GECCO - 2012, Philadelphia, organized by ACM SIGEVO, 2012), третья российская конференция с международным участием «Технические и программные средства систем управления, контроля и измерения» (Институт проблем управления имени В. А. Трапезникова РАН, 2012) - пленарный доклад.

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

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

Структура диссертации. Диссертация изложена на 198 страницах и состоит из введения, четырех глав, заключения и двух приложений. Список источников содержит 170 наименований. Работа проиллюстрирована 41 рисунком и 14 таблицами.

Содержание работы

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

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

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

Эволюционные стратегии имеют два отличия от генетических алгоритмов: в них не используется операция скрещивания и, как правило, каждое поколение состоит только из одной особи. Опишем (1+1)-эволюционную стратегию. Процесс поиска начинается со случайно выбранного допустимого решения. На каждой итерации к текущей особи применяется операция мутации. Она устроена так, что в ее результате может получиться (пусть и с малой вероятностью) любое допустимое решение. Если результат этой операции - решение с большим значением функции приспособленности, то оно становится текущим. Работа алгоритма считается оконченной, когда будет достигнуто необходимое значение функции приспособленности.

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

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

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

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

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

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

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

На основе результатов обзора формулируются задачи, решаемые в настоящей ;иссертации.

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

Исходными данными для построения автомата в настоящей работе являются:

• множество событий Е ={еь е2,..., с,,};

• множество входных переменныхX = {хь х2,..., хт};

• множество выходных воздействий Z= {_;, г2,..., г*};

• множество обучающих примеров (тестов) Tests;

• максимальное число состояний в искомом автомате К.

Опишем структуру тестов: /-й из них состоит из двух последовательностей -ходной Input[/'] и выходной Answerj/]. Элементами входной последовательности вляются пары (e,f), где е — некоторое событие из множества Е, а/— булева формула г входных переменных, задающая условие перехода. Выходными данными в задаче остроения управляющего автомата по набору тестов является автомат, содержащий е более К состояний, удовлетворяющий каждому тесту из множества Tests и

обладающий свойством непротиворечивости, либо сообщение о том, что такого автомата не существует. Автомат А удовлетворяет тесту Test = (Input, Answer), если результат обработки входной последовательности Input из начального состояния автомата совпадает с последовательностью Answer.

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

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

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

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

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

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

Опишем алгоритм расстановки выходных воздействий для дискретных воздействий. Для каждого перехода Т и каждой последовательности выходных воздействий zs вычисляется величина C[7][zs] - число раз, когда при обработке входной последовательности, соответствующей одному из тестов, на переходе Г должны быть выработаны выходные воздействия, образующие последовательность zs. Далее, каждый переход помечается той последовательностью zso, для которой величина C[7][zs0] максимальна. На рисунке 1 слева изображена особь эволюционного алгоритма до применения алгоритма расстановки выходных воздействий, а справа -после его применения.

JM/i

T[x2]/z5

Т[х,1/1 М[х,]/1

Н[х2]/1

Рисунок 1 - Пример работы алгоритма расстановки выходных воздействий Предлагается функцию приспособленности вычислять на основе редакционного расстояния. При этом выполняются следующие действия: на вход автомату подается каждая из последовательностей Inputf/]. Обозначим результат обработки входной последовательности Inputf/], как Output[/]. Если этот результат не определен, то будем считать, что Output[i] равен пустой последовательности. После этого вычисляется

Ed"

ED(Output[j], Answer[;]) maxfl Output[i] |, | Answer[7| |)

значение вспомогательной переменной КР, = _тах'1 ОЩриф] |, | Ал5\уег[;] I) где как

п '

ЕО(А, В) обозначено редакционное расстояние между последовательностями А и В. Отметим, что значение И7! лежит в пределах от 0 до 1. При этом чем «лучше» автомат соответствует тестам, тем больше ее значение.

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

вычисляется по формуле: ff2 =

10-FF.+—-(Л/-М

cnt),FF, <1

20 +

Н cnt

г; 1с М - число, большее

(М - cnt), FF, =1

число переходов в автомате, кодируемом

числа переходов в автомате, осматриваемой особью.

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

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

При изменении описания перехода с равной вероятностью выполняется одно из педующих действий: 1. Изменение состояния, в которое ведет переход (изменяется на пучайно выбранное). 2. Изменение события, по которому выполняется переход «меняется на случайно выбранное). 3. Изменение числа выходных воздействий, ырабатываемых на этом переходе (с равной вероятностью это число либо

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

После выполнения операции мутации к каждому состоянию автомата применяется алгоритм удаления дублированных и неоднозначных переходов. Обозначим список переходов, поступающих на вход этого алгоритма как ¿¡„, а список переходов, получающийся в результате его работы, как ЬаШ. Для его формирования выполняются следующие операции: по очереди рассматриваются переходы, входящие в список ¿¡„; очередной переход г добавляется в 1а„„ если в нем еще нет перехода, помеченного тем же событием, что и /, и условием, имеющим общую выполняющую подстановку с условием перехода и

Скрещивание описаний автоматов производится следующим образом. Обозначим как Р1 и Р2 «родительские» особи, а как Б1 и 82 - особи-«потомки». Начальные состояния ЭглБ и БгЛэ имеют номер 0, так как у всех особей нулевое состояние является начальным. Скрещивание описаний автоматов производится отдельно для каждого состояния. Обозначим список переходов из состояния номер / автомата Р1 как Р1. 7р], а список переходов из состояния номер /' автомата Р2 как Р27[|].

При использовании традиционного метода скрещивания списки переходов 81.7])'] и 82.Г|)'] формируются следующим образом:

1. Строится общий список переходов, в который помещаются переходы, входящие как в Р1.7])'], так и в Р2.7[г].

2. К полученному списку применяется случайная перестановка. Далее возможны два равновероятных варианта: либо в 81.7[/] помещаются первые |Р1.7[/']| переходов из полученного списка, а в 82.7]/] - оставшиеся переходы; либо в 81.7[/] помещаются первые 1Р2.7[(]| переходов из полученного списка, а в 52.7])'] - оставшиеся переходы.

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

Перейдем к изложению метода скрещивания с учетом поведения автомата на обучающих примерах. Списки переходов 81.71/'] и 82 Ш строятся следующим образом:

1. В автоматах Р1 и Р2 помечаются те переходы, которые выполняются при

„ „ ________ЕОЮифифХАгачуеф'])

обработке 10% тестов, для которых значение тах(|0и1ри11,.]ИАп5№е[М&

минимально.

2. Список переходов 81.7[г] формируется следующим образом: сначала в него копируются помеченные переходы из Р1.7[г], затем помеченные переходы из Р2.7[/], а затем непомеченные переходы из Р1.7])'].

3. Список переходов 82.7])'] формируется следующим образом: сначала в него копируются помеченные переходы из Р2.7[/], затем помеченные переходы из

• V,-Р1.7у], а затем непомеченные переходы из Р2.7р].

и

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

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

В экспериментах по построению автомата управления часами с будильником входные данные состояли из 38 тестов (суммарная длина входных последовательностей - 242, выходных - 195). Было проведено по 1000 запусков каждого алгоритма, для каждого из которых записывалось время работы. В эволюционных алгоритмах время работы измеряется числом запусков функции приспособленности, так как, как правило, ее вычисление является более трудоемким, чем выполнение операций мутации и скрещивания.

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

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

Алгоритм Минимум Максимум Среднее Медиана

ГА-1 1093938 41794531 6783215 5014202

МС 1387 9710090 1275439 792481

ЭС 1325 9915947 1317674 901615

ГА-2 51977 1196233 205451 142013

ГА-2+МС 46311 780469 127712 103904

ГА-2+ЭС 38458 2714324 129330 84778

Для каждой пары алгоритмов был проведен статистический тест АЫОУЛ. Его результаты приведены в таблице 2. В ней для каждой пары алгоритмов указано р-значение. Если это значение меньше 0.05, то можно сделать вывод о том, что время работы соответствующих алгоритмов на рассматриваемой задаче существенно различается.

Таблица 2 - Результаты статистического теста

ГА-1 МС ЭС ГА-2 ГА-2+МС ГА-2+ЭС

ГА-1 - <3-10-)6 <3-10'16 <3-10"16 <3-10"16 <3-10'16

МС - - 0.5178 <3-1010 <3-10-16 <3-10'№

ЭС - - - <310"16 <3-10'16 <3-10"16

ГА-2 - - - - <3-1016

ГА-2+МС - - - - - 0.7446

ГА-2+ЭС - - - - - -

Для проведения экспериментов по построению управляющих автоматов п обучающим примерам, сгенерированным случайным образом, были сгенерирован] автоматы, содержащие 4, 5, ..., 10 состояний. Далее по каждому из автоматов бы сгенерирован случайным образом набор тестов (при этом суммарная длина входны последовательностей в этих тестах составляла 150£ для автомата из к состояний). Дл каждого алгоритма и каждого набора тестов было проведено 100 запусков. Дл каждого запуска записывалось время работы. В таблице 3 приведено среднее врем работы алгоритмов на случайно сгенерированных тестах.

Таблица 3 - Среднее время работы алгоритмов на тестах, _^_сгенерированных случайным образом

Число состояний ГА-1 МС ЭС ГА-2 ГА-2+МС ГА-2+ЭС

4 25514587 5432560 6017983 875514 629232 460564

5 62124022 10711175 13519507 2032536 1545070 1241844

6 161261630 29291065 36216142 4537179 3721738 2981650

7 376970651 80844608 66850953 10928249 8799660 6815845

8 881025771 144343577 179974240 27500471 20036385 13877897

9 2149301686 350141493 409724265 56380237 41708779 32884793

10 4496075865 830139535 924940477 131551924 108635507 85621418

По результатам выполненных экспериментов алгоритмы можно разбить на четыре группы: ГА-1; МС и ЭС; ГА-2; ГА-2+ЭС и ГА-2+МС. Указанное разбиение на группы обладает тем свойством, что алгоритмы внутри группы имеют статистически неразличимое время работы, а для алгоритмов из разных групп оно существенно различается.

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

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

РИ= РР2 •(!+—). Здесь и2 - общее число темпоральных формул в спецификации, д.щ-

пг

число формул, которые выполняются для рассматриваемого автомата. Операции скрещивания и мутации выполняются так же, как и в методе, описанном выше.

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

алгоритмов, и для каждого из запусков записывалось время работы. Пример автомата,

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

При построении автомата управления дверьми лифта только на основе тестов реднее значение вычислений функции приспособленности оказалось равным .479-104 (минимальное число вычислений - 2.184-104, максимальное - 2.999-105). При спользовании верификации совместно с тестами среднее значение числа вычислений )ункции приспособленности оказалось равным 7.246-105 (минимальное число ычислений - 7.054-104, максимальное - 5.492- 10б). Эксперименты показали, что при остроении автоматов только на основе тестов в девяти случаях из 1000 результатом влялся автомат, который полностью удовлетворяет спецификации.

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

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

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

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

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

Рисунок 3 - Технология построения автоматов на основе эволюционных алгоритмов

Эта технология положена в основу разработанного инструментального средства, исходный код которого размещен в открытом доступе в сети Интернет по адресу: http://code.google.com/p/gabp/. Входные данные для этого инструментального средства описываются в формате XML. Результатом работы инструментального средства является XML-описание графа переходов автомата в формате инструментального средства UniMod. Построенный автомат соответствует обучающим примерам и удовлетворяет темпоральным свойствам, заданным во входном файле.

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

Для построения системы управления моделью беспилотного самолета при исполнении «мертвой петли» метод построения автоматов по обучающим примерам был применен для случая не только дискретных (как в прототипе), но и непрерывных выходных воздействий. В этом случае при предложенном выборе функции приспособленности расстановка непрерывных выходных воздействий осуществляется на основе решения набора систем линейных уравнений. Моделирование беспилотного самолета проводилось с использованием симулятора FlightGear (http://www.flightgear.org).

Для построения автомата были записаны несколько обучающих примеров, каждый из которых соответствовал выполнению «мертвой петли» под управлением пилота-человека. Каждый пример состоял из нескольких тысяч наборов входных и выходных воздействий. Время работы алгоритма составляло около 10 часов для одного набора тестов. Было проведепо 50 запусков генетического алгоритма, в каждом из которых выбирался автомат с наибольшим значением функции приспособленности. Полеты моделей самолетов, управляемых выбранными автоматами, были просмотрены экспертом. В результате был выбран один автомат, который наиболее точно осуществлял управление моделью самолета. Результаты этой части работы составили предмет статьи, принятой в журнал «Известия РАН. Теория и системы управления».

Для внедрения в учебный процесс были разработаны две виртуальные лаборатории (для языков программировании Java и С#) для обучения построению конечных автоматов на основе эволюционных алгоритмов. Обе виртуальные лаборатории имеют модульную архитектуру - содержат ядро, предоставляющее базовую функциональность, которая расширяется с помощью подключаемых модулей (плагинов). Ядро лаборатории позволяет просматривать и сохранять в виде файлов графики зависимости значений некоторых функций (например, максимального, минимального и среднего значения функции приспособленности особей поколения) от юмера поколения. Кроме этого поддерживается возможность визуализации особей и ¡X сохранения в текстовом формате. Также ядро программы поддерживает юдключение плагинов «на лету» (во время работы программы). С использованием тих виртуальных лабораторий с 2008 года проводятся лабораторные работы по курсу Теория автоматов и программирование», которые были выполнены более чем 150 тудентами третьего курса кафедры «Компьютерные технологии» НИУ ИТМО. Часть тчетов по лабораторным работам опубликована на сайте http://is.ifmo.ru/labs/.

Заключение

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

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

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

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

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

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

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

Статьи в журналах из перечня ВАК

1. Царев Ф. Н. Совместное применение генетического программирования, конечных автоматов и искусственных нейронных сетей для построения системы управления беспилотным летательным аппаратом //Научно-технический вестник СПбГУ ИТМО. 2008. Выпуск 53. Автоматное программирование, с. 42-60.

2. Царев Ф. Н., Давыдов А. А., Соколов Д. О. Применение генетического программирования и методов сокращенных таблиц переходов и деревьев решений для построения автоматов управления моделью беспилотного летательного аппарата //Научно-технический вестник СПбГУ ИТМО. 2008. Выпуск 53. Автоматное программирование, с. 60-79.

3. Царев Ф. Н. Метод построения управляющих конечных автоматов на основе тестовых примеров с помощью генетического программирования // Информационно-управляющие системы. 2010. № 5, с. 31—36.

4. Царев Ф. Я, Егоров К. В., ШалытоА. А. Применение генетического программирования для построения автоматов управления системами со сложным поведением на основе обучающих примеров и спецификации // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2010. № 5 (69), с. 81-86.

5. Царев Ф. Н., Александров А. В., Казаков С. В. Сергуишчев А. А., Шалыто А. А. Генерация конечных автоматов для управления моделью беспилотного самолета // Научно-технический вестник СПбГУ ИТМО. 2011. № 2, с. 3-11.

Другие публикации

6. Царев Ф. Н., Егоров К. В., Шалыто А. А. Совместное применение генетического программирования и верификации для построения автоматов управления системами со сложным поведением // Труды СПИИРАН. 2010. Вып. 15, с. 123-135.

7. Царев Ф. Н., Шалыто А. А. Применение генетического программирования для построения мультиагентной системы одного класса /Международная научно-техническая мультиконференция «Проблемы информационно-компьютерных технологий и мехатроники». Материалы международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (МВУС'2007). Таганрог: НИИМВС. Т.2, с. 46-51.

8. Царев Ф. Н., Шалыто А. А. Применение генетического программирования для генерации автоматов в задаче об «умном муравье» /Сборник научных трудов. IV-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте». М.: Физматлит. 2007, с. 590-597.

9. Царев Ф. Н„ Шалыто А. А. О построении автоматов с минимальным числом состояний для задачи об «умном муравье» //Сборник докладов X международной конференции по мягким вычислениям и измерениям. СПбГЭТУ «ЛЭТИ». Т.2. 2007, с. 88-91.

10. Царев Ф. Н„ Шалыто А. А. Применение генетических алгоритмов для построения автоматов с минимальным числом состояний для задачи об «Умном муравье» / Тезисы научно-технической конференции «Научно-программное обеспечение в образовании и научных исследованиях». СПбГПУ. 2008, с. 209-215.

11. Tsarev F„ DavydovA., Sokolov D„ Application of Genetic Algorithms for Construction of Moore Automaton and Systems of Interacting Mealy Automata in "Artificical Ant" Problem /Proceeding of the Second Spring Young Researchers' Colloquium on Software Engineering (SYRCoSE"2008). SPbSU. 2008. Vol.1, pp.51-54.

12. Tsarev /•'.. DavydovA., 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 in Manufacturing. Moscow. 2009 pp. 684-689.

13. Царев Ф. H. Построение автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования /Сборник докладов международной конференции по мягким вычислениям и измерениям

(scm'2009). спбгэту «лэти». т. 1, с. 231-234.

14. Царев Ф. Н. Метод построения автоматов управления системами со сложным поведением на основе тестов с помощью генетического программирования / Материалы Международной научной конференции «Компьютерные науки и информационные технологии» памяти А. М. Богомолова. Саратов: СГУ. 2009 с. 216-219.

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

16. Царев Ф. #., Егоров К. В. Совместное применение генетического программирования и верификации моделей для построения автоматов управления системами со сложным поведением /Сборник трудов конференции «Информационные технологии и системы» (ИТИС'09). М.: Институт проблем передачи информации им. А. А. Харкевича РАН. 2009, с. 77-82.

17. Царев Ф. К, Александров А. В., Казаков С. В., Сергушичев А. А. Генетическое программирование на основе обучающих примеров для построения конечных автоматов управления моделью беспилотного самолета /Сборник докладов международной конференции по мягким вычислениям и измерениям (SCM'2010). СПбГЭТУ «ЛЭТИ». Т. 1, с. 263-267.

18. Царев Ф. Н., Егоров К. В., Парфенов В. Г. Совместное применение генетического программирования и верификации моделей для построения автоматов управления системами со сложным поведением /Труды XVII Всероссийской научно-методической конференции «Телематика'2010». Т. 2. СПбГУ ИТМО. 2010, с. 344,345.

19. Царев Ф. Н., Егоров К. В. Применение генетического программирования для построения автоматов управления системами со сложным поведением на основе верификации моделей и обучающих примеров // Сборник «Список-2011». Материалы второй межвузовской научной конференции по проблемам информатики». МатМех СПбГУ. 2011, с. 343-350.

20. Tsarev F., Egorov К. Finite State Machine Induction using Genetic Programming Based on Testing and Model Checking / Proceedings of the 2011 GECCO Conference

Companion on Genetic and Evolutionary Computation. NY.: ACM. 201 pp. 759-762.

21. Царев Ф. H„ Давыдов А. А., Соколов Д. О., Шалыто А. А. Виртуальная лаборат рия обучения генетическому программированию для генерации управляют! конечных автоматов / Сборник докладов III Международной науч» практической конференции «Современные информационные технологии и Иг образование». ВМК МГУ. М.: МАКС Пресс, 2008, с. 179-183.

22. ТяхтиА. С., Чебатуркин А. А., Царев Ф. Н„ Шалыто А. А. Виртуальная лабор тория для обучения методам искусственного интеллекта для генерации управл: ющих конечных автоматов /Сборник докладов IV Международной научи практической конференции «Современные информационные технологии и ИТ образование». М.: ИНТУИТ.РУ, МГУ. 2009, с. 222-227.

23. Tsarev F„ Chivilikhin II, Ulyantsev V. Test-Based Extended Finite-State Machim Induction with Evolutionary Algorithms and Ant Colony Optimization / Proceeding of the 2012 GECCO Conference Companion on Genetic and Evolutionary Comput; tion. NY.: ACM. 2012, pp. 603-606.

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Саблинская ул., 14 Тел. (812) 233 4669 объем 1 п.л. Тираж 100 экз.

ВВЕДЕНИЕ.

ГЛАВА 1. АВТОМАТНОЕ ПРОГРАММИРОВАНИЕ И ПОИСКОВАЯ ИНЖЕНЕРИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

1.1. Автоматное программирование.

1.1.1. Сущности со сложным поведением.

1.1.2. Парадигма автоматного программирования.

1.1.3. Управляющий конечный автомат.

1.1.4. Верификация автоматных программ на основе метода Model Checking.

1.2. Поисковая инженерия программного обеспечения.

1.2.1. Основные понятия.

1.2.2. Метод спуска.

1.2.3. Эволюционная стратегия.

1.2.4. Генетические алгоритмы.

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

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

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

1.3.3. Методы, использующие верификацию при вычислении функции приспособленности.

1.3.4. Анализ эволюционных алгоритмов построения автоматов.

1.4. Задачи, решаемые в диссертационной работе.

Выводы по главе 1.

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

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

2.1.1. Входные данные.

2.1.2. Выходные данные.

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

2.1.4. Алгоритм расстановки выходных воздействий.

2.1.5. Вычисление функции приспособленности.

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

2.1.7. Операция удаления дублированных и противоречивых переходов.

2.1.8. Операция мутации, использующаяся в эволюционной стратегии.

2.1.9. Генетический алгоритм.

2.1.10. Операция скрещивания.

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

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

2.3. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ МЕТОДОВ ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ АВТОМАТОВ ПО ОБУЧАЮЩИМ ПРИМЕРАМ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ.

2.3.1. Построение автомата управления часами с будильником.

2.3.2. Тесты, сгенерированные случайным образом.

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

2.4.1. Входные данные.

2.4.2. Выходные данные.

2.4.3. Представление конечного автомата в виде хромосомы эволюционного алгоритма.

2.4.4. Вычисление функции приспособленности.

2.4.5. Операции мутации и скрещивания.

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

ВЫВОДЫ ПО главе 2.

ГЛАВА 3. ТЕХНОЛОГИЯ И ИНСТРУМЕНТАЛЬНОЕ СРЕДСТВО ПОСТРОЕНИЯ УПРАВЛЯЮЩИХ КОНЕЧНЫХ АВТОМАТОВ НА ОСНОВЕ ЭВОЛЮЦИОННЫХ АЛГОРИТМОВ И ВЕРИФИКАЦИИ.

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

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

3.2.1. Формат входных данных.

3.2.2. Формат выходных данных.

3.2.3. Структура программной реализации. выводы по главе 3.

ГЛАВА 4. ВНЕДРЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ.

4.1. ВНЕДРЕНИЕ РАЗРАБОТАННЫХ МЕТОДОВ НА ПРИМЕРЕ ПОСТРОЕНИЯ АВТОМАТА УПРАВЛЕНИЯ МОДЕЛЬЮ БЕСПИЛОТНОГО САМОЛЕТА.

4.1.1. Описание объекта управления.

4.1.2. Входные переменные и события.

4.1.3. Набор обучающих примеров.

4.1.4. Вычисление функции приспособленности.

4.1.5. Модифицировнный алгоритм расстановки выходных воздействий.

4.1.6. Результаты построения автомата.

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

4.2.1. Виртуальная лаборатория на языке Java.

4.2.2. Виртуальная лаборатория на языке С#.

4.2.3. Применение виртуальных лабораторий в учебном процессе.

ВЫВОДЫ ПО главе 4.

Актуальность проблемы. В последнее время при разработке программного обеспечения (ПО) для управляющих систем все шире применяется автоматное программирование [22,27] - парадигма программирования, при использовании которой программу предлагается строить как совокупность автоматизированных объектов управления, каждый из которых содержит систему управления (один или несколько взаимодействующих управляющих конечных автоматов) и объект управления.

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

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

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

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

При использовании автоматного программирования существенно упрощается (по сравнению с программами, написанными традиционными методами) верификация программ с использованием метода Model checking [6, 9, 125, 56], так как построение модели Крипке по автоматной программе может быть автоматизировано [125]. Кроме этого, при использовании инструментальных средств для поддержки автоматного программирования таких, как, например, TJniMod [3], до 70% исходного кода автоматной программы может быть сгенерировано автоматически [27, 137]. Уровень автоматизации программирования этого класса программ станет значительно выше, если удастся автоматизировать процесс построения управляющих конечных автоматов, что и является предметом исследования в настоящей работе.

В последнее десятилетие активно развивается область исследований, называемая поисковая инженерия ПО {Search-Based Software Engineering, SBSE) [45, 69 - 71], в рамках которой для решения задач программной инженерии (включая анализ требований [37,121], прогнозирование хода разработки [30], проектирование [110], тестирование [34, 67, 93] и рефакторинг [68, 106]) предлагается применять алгоритмы поисковой оптимизации. В число методов, которые нашли применение в поисковой инженерии ПО [69], входят эволюционные алгоритмы [7] (генетические алгоритмы [2,11,12,43], генетическое программирование [84] и эволюционные стратегии [40]), а также муравьиные алгоритмы [49], метод роя частиц [82], метод имитации отжига [94], метод спуска [66], алгоритмы оценки распределений [86], поиск с запретами [58], меметические алгоритмы [51], метод рассеянного поиска [59], квадратичное программирование [105], целочисленное программирование [113], искусственные иммунные системы [47]. При этом в настоящее время наибольшее распространение получили эволюционные алгоритмы [71].

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

Примерами таких задач являются: управление командой беспилотных летательных аппаратом в соревнованиях с другой командой [21, 136], итерированная дилемма узника [98], задача о «Флибах» [1, 53], задача «Умный муравей» [79]. Полный перебор управляющих конечных автоматов даже при их небольших размерах крайне трудоемок, а эвристическое их построение, как отмечено выше, не всегда дает приемлемые результаты.

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

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

Подобные идеи возникали у ряда исследователей. В 1962 г. Л. Фогель занялся изучением интеллектуального поведения индивида и его развития в процессе эволюции [52]. При этом поведение индивида задавалось конечным автоматом. Продолжая данные исследования, Л. Фогель, А. Оуэне и М. Уолш предложили в 1966 г. схему эволюции конечных автоматов, решающих задачи предсказания [53].

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

Генетические алгоритмы ведут поиск оптимальных решений параллельно в нескольких точках пространства поиска. Вначале случайным образом генерируется некоторое число решений (особей), образующих начальное поколение. Далее, особи этой популяции скрещиваются и мутируют, формируя новое поколение. Скрещивание {кроссовер, рекомбинация) - фундаментальная операция в генетических алгоритмах, позволяющая производить обмен «генетическим материалом» между особями. Мутация - не менее важная составляющая, она позволяет получать новый «генетический материал», а также предотвращать «застревание» в области локального оптимума.

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

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

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

Генетическое программирование - разновидность генетических алгоритмов, в которой вместо низкоуровневого представления объектов в виде битовых строк используется высокоуровневое представление: деревья разбора программ, диаграммы переходов конечных автоматов и т. д. С помощью генетического программирования эффективно решаются задачи автоматического построения программ, конечных автоматов и клеточных автоматов.

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

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

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

В предыдущих работах, связанных с автоматным программированием, рассматривались, прежде всего, методы, использующие моделирование для вычисления функции приспособленности [5,14,15, 17, 35, 53, 73, 76, 79, 95,112,114,129 - 132, 135].

Эти методы обладают следующими недостатками:

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

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

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

В соответствии с паспортом специальности 05.13.11 -«Математическое обеспечение вычислительных машин, комплексов и компьютерных сетей» областями исследования, к которым относится настоящая диссертация, в частности, являются «5. Теория построения программ, пакетов прикладных программ (ППП), программных комплексов (ПК), а также сетевых программ (СП), в том числе, поддерживающих сетевые протоколы» и «9. Модели и методы разработки программных средств обработки данных и знаний в ВМ, ВК и КС».

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

Основные задачи диссертационной работы состоят в следующем:

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

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

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

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

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

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

Научная новизна. В работе получены следующие новые научные результаты, которые выносятся на защиту:

1. Метод построения автоматов по обучающим примерам на основе эволюционных алгоритмов. Его основное отличие от известных состоит в том, что в предлагаемые алгоритмы добавлен новый шаг «Расстановка выходных воздействий», который выполняется перед вычислением функции приспособленности.

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

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

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

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

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

Внедрение результатов работы. Результаты диссертации были получены при выполнении научно-исследовательских работ на кафедрах «Компьютерные технологии» и «Технологии программирования» НИУ ИТМО по следующим государственным контрактам: «Технология генетического программирования для генерации автоматов управления системами со сложным поведением» (государственный контракт №02.514.11.4044 от 18.05.2007 г. по Федеральной целевой программе «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2013 годы»), «Разработка методов совместного применения генетического и автоматного программирования для построения систем управления беспилотными летательными аппаратами» (государственный контракт № П1188 от 27.08.2009 г. по Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы), «Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов» (государственный контракт № П2174 от 09.11.2009 г. по Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы), «Применение методов искусственного интеллекта в разработке управляющих программных систем» (государственный контракт № П2236 от 11.11.2009 г. по Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы), в рамках проекта «Подготовка и переподготовка профильных специалистов на базе центров образования и разработок в сфере информационных технологий в СевероЗападном федеральном округе» (Государственный контракт №07.Р20.11.0028 от 07.09.2011 г.) и были внедрены на примере построения автомата управления моделью беспилотного самолета, а также в учебном процессе на кафедре «Компьютерные технологии» в рамках курса «Теория автоматов и программирование».

Апробация результатов работы. Основные положения диссертационной работы докладывались на следующих научных и научно-практических конференциях: IV Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте» (Коломна, 2007), научно-техническая конференция «Научное программное обеспечение в образовании и научных исследованиях» (СПбГПУ, 2008), XII Всероссийская конференция по проблемам науки и высшей школы «Фундаментальные исследования и инновации в технических университетах» (СПбГПУ, 2008), Second Spring Young Researchers' Colloquium on Software Engineering

SYRCoSE'2008 (SPbSU, 2008), III и IV Международная научно-практическая конференция «Современные информационные технологии и ИТ-образование» (ВМК МГУ, 2008, 2009), научно-практическая конференция студентов, аспирантов, молодых ученых и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте (ИММВИИ-2009)» (Коломна, 2009), VI и VII межвузовская конференция молодых ученых (СПбГУ ИТМО, 2009, 2010), X, XI и XII Международная конференции по мягким вычислениям и измерениям (СПбГЭТУ (ЛЭТИ), 2009, 2010, 2011), Международная научная конференция «Компьютерные науки и информационные технологии» памяти А. М. Богомолова (Саратовский государственный университет имени Н. Г. Чернышевского, 2009), 32-я конференция молодых ученых и специалистов Института проблем передачи информации им. А. А. Харкевича РАН «Информационные технологии и системы» (2009), XL научная и учебно-методическая конференция профессорско-преподавательского и научного состава СПбГУ ИТМО (2011), 14-th Annual Graduate Students Workshop (part of the «Genetic and Evolutionary Computation Conference» GECCO - 2011, Dublin, ACM SIGEVO, 2011), вторая межвузовская научная конференция по проблемам информатики (СПИСОК, СПбГУ, 2011), XLI научная и учебно-методическая конференция НИУ ИТМО (2012), 15-th Annual Graduate Students Workshop (part of the «Genetic and Evolutionary Computation Conference» GECCO - 2012, Philadelphia, ACM SIGEVO, 2012), третья российская конференция с международным участием «Технические и программные средства систем управления, контроля и измерения» (Институт проблем управления имени В. А. Трапезникова РАН, 2012) -пленарный доклад.

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

Свидетельства о регистрации программ для ЭВМ. В рамках диссертационной работы получены три свидетельства о регистрации программ для ЭВМ: № 2010 614197 от 29.06.2010 г. «Программное средство для построения управляющих конечных автоматов на основе обучающих примеров с использованием генетических алгоритмов», №2011 615664 от 19.07.2011 г. «Программное средство для генерации конечных автоматов с дискретными и непрерывными выходными воздействиями», № 2011 616977 от 08.09.2011 г. «Виртуальная лаборатория для обучения методам искусственного интеллекта при построении конечных автоматов».

Структура диссертации. Диссертация изложена на 196 страницах и состоит из введения, четырех глав, заключения и двух приложений. Список источников содержит 170 наименований. Работа проиллюстрирована 41 рисунком и 14 таблицами.

Выводы по главе 4

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

1. Печатные издания на русском языке

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

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

4. Гуров В. С., Мазин М. А., Нарвский А. С., Шалыто A. A. UML. SWITCH-технология. Eclipse //Информационно-управляющие системы. 2004. № 6, с. 12 17. http://is.ifmo.ru/works/uinl-switch-eclipse/

5. Велъдер С. Э., Лукин М. А., Шалыто А. А., Яминов Б. Р. Верификация автоматных программ. СПб.: Наука, 2011. http://is.ifmo.m/verification/velderverification posobienauka.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. №4, с. 845-848.

14. Лобанов П. Г. Использование генетических алгоритмов для генерации конечных автоматов. Диссертация на соискание ученой степени кандидата технических наук. СПбГУ ИТМО. 2008. http://is.ifmo.ru/disser/lobanovdisser.pdf

15. Люгер Дж. Искусственный интеллект: стратегии и методы решения сложных проблем. М: Вильяме, 2003.

16. Непейвода Н. Н. Стили и методы программирования. М.: Интернет-Университет Информационных технологий, 2005.

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

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

19. Поликарпова П. И., Шалыто А. А. Автоматное программирование. СПб.: Питер, 2009. http://is.ifmo.ru/books/ book.pdf

20. Потапов А. С. Искусственный интеллект и универсальное мышление. СПб.: Политехника, 2012.

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

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

23. Шалыто А. А. Switch-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998. http://is.ifmo.ru/books/switch/l

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

25. Печатные издания на английском языке

26. 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.

27. 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.

28. 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.

29. 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.

30. Ali S., Briand L., Hemmati H., Panesar-Walawege R. K. A Systematic Review of the Application and Empirical Investigation of Search-Based Test-Case Generation // IEEE Transactions of Software Engineering. 2010. Vol. 36, №6, pp. 742-762.

31. Angeline P., Pollack J. Evolutionary Module Acquisition / Proceedings of the Second Annual Conference on Evolutionary Programming. Cambridge: MIT Press. 1993, pp. 154 163. http://www.demo.es .brandeis.edu/papers/ep93 .pdf

32. Back T. Evolutionary Algorithms in Theory and Practice. Oxford University Press, 1996.

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

34. Beyer H. G. The Theory of Evolution Strategies. Natural Computing Series. Berlin. NY: Springer-Verlag, 2001.

35. 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

36. Bryant R. E. Graph-based algorithms for boolean function manipulation / IEEE Transactions on Computers. 1986, Vol. 35, pp. 677 691.

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

38. 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.

39. 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.

40. Das R, Mitchell M., Crutchfield J. P. A genetic algorithm discovers particle-based computation in cellular automata // Lecture Notes in Computer Science. 1994. www.santafe.edu/research/publications/workingpapers/94-03-015.pdf

41. De Castro L., Timmis J. Artificial Immune Systems: A New Computational Intelligence Approach. Springer, 2002.

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

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

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

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

46. Fogel L. Autonomous Automata // Industrial Research. 1962. V.4, pp. 14 -19.

47. Fogel L., Owens A., Walsh M. Artificial Intelligence through Simulated Evolution. NY: Wiley, 1966.

48. Gastin P., Oddoux D. Fast LTL to Biichi Automata Translation / 13th Conference on Computer Aided Verification (CAV'01). 2001, pp. 53-65.

49. 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, pp. 3 -18.

50. Ghnemat R, Khatatneh K., Oqeili S., Bertelle C., Duchamp G. Automata-based adaptive behavior for economic modeling using game theory. 2005. http://arxiv.org/abs/cs/0510089

51. Glover F. Tabu search: A tutorial //Interfaces. 1990. Vol. 20, pp. 74 94.

52. Glover F., Laguna M., Marti R. Fundamentals of Scatter Search and Path Relinking // Control and Cybernetics, 2000. № 29 (3), pp. 653 684

53. 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.

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

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

56. 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.

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

58. HarelD., PnueliA. 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.

59. 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.

60. 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.

61. 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.

62. 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.

63. Harman M. Software Engineering Meets Evolutionary Computation I I Computer. 2011. Vol. 44. № 11, pp. 31 39.

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

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

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

67. Holland J. ECHO: Explorations of Evolution in a Miniature World / Proceedings of the Second Conference on Artificial Life. Redwood City. CA: Addison-Wesley, 1990.

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

69. 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.

70. Huang D. MS Thesis Preproposal: Adaptive Incremental Fitness Evaluation in Genetic Algorithms. 2005. NY: Rochester. http://www.cs.rit.edu/~dxh6185/downloads/MS Thesis/Documents/Prese ntation.pdf

71. 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.

72. Juillie H., Pollack J. Coevolving the «Ideal» Trainer: Application to the Discovery of Cellular Automata Rules. 1998. http://citeseer.ist.psu.edu/16712.html

73. Kennedy J., EberhartR. C. Swarm Intelligence. Morgan Kaufmann. 2001.

74. 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 -1374.

75. Koza J. Genetic programming. On the Programming of Computers by Means of Natural Selection. MA: The MIT Press, 1998.

76. 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

77. Larranaga P., Lozano J. A. Estimation of distribution algorithms: A new tool for evolutionary computation. Kluwer Academic Publishers. Boston, 2002.

78. Levy S. Artificial Life: The Quest for a New Creation. NY: Pantheon, 1992.

79. 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.

80. 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.

81. 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/contcnt/41a34vg70fplhltb/

82. 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.

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

84. McMinn P. Search-Based Software Test Data Generation: A Survey // Software Testing, Verification and Reliability. 2004. Vol. 14. № 2, pp. 105 156.

85. 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.

86. 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.

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

88. 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), pp. 1375 -1382.

89. Mitchell M. An Introduction to Genetic Algorithms. MA: The MIT Press, 1996.

90. 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

91. 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.

92. 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, pp. 114-122.

93. 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

94. 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.

95. Niebert P., Peled D., Pnueli A. Discriminative Model Checking. Lecture Notes In Computer Science. Springer Berlin / Heidelberg. 2008. Vol. 5123/2008, pp. 504-516.

96. Nocedal J., Wright S. Numerical Optimization. 2006. Berlin, NY: Springer-Verlag.

97. O'Keeffe M., O'Cinneide M. Search-Based Software Maintenance / Proceedings of Conference on Software Maintenance and Reengineering (CSMR 06). IEEE CS Press. 2006, pp. 249 260.

98. 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-poster-petrovic.pdf

99. 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

100. Petrovic P. Comparing Finite-State Automata Representation with GP-trees. Technical Report. Norwegian University of Science and Technology, 2006. http://www.idi.ntnu.no/~petrovic/fsatr/fsatr.pdf

101. Raiha O. A Survey on Search-Based Software Design //Computer Science Rev. 2010. Vol. 4. № 4, pp. 203 249.

102. Ray T. An Approach to the Synthesis of Life / In Artificial Life II. MA: Addison-Wesley. 1992, pp. 371 408.

103. 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

104. Schrijver A. Theory of linear and integer programming. John Wiley and Sons, 1998.

105. 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.

106. Spichakova M. Genetic Inference of Finite State Machines. Masters thesis. Tallinn, 2007. http://s-ma-u-g.googlecode.com/files/thesis.pdf

107. Tomita M. Dynamic construction of finite automata from examples usingjLhill climbing / Proceedings of the 4 Annual Cognitive Science Conference (USA, 1982), pp. 105 108.

108. Von Neumann J., Burks A. The Theory of Self-reproducing Automata. Urbana. Univ. of Illinois Press, 1966.

109. 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.pdf1. Ресурсы сети Интернет

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

111. Государственный контракт «Применение методов искусственного интеллекта в разработке управляющих программных систем». Промежуточный отчет по II этапу. СПбГУ ИТМО, 2010. Ьир:/ЛзЛАпо.ги/Баепсе/ пк-408-15-2.pdf

112. Государственный контракт «Разработка технологии верификации управляющих программ со сложным поведением, построенных на основе автоматного подхода». Заключительный отчет по IV этапу

113. Обобщение и оценка результатов исследований». СПбГУ ИТМО, 2007. http://is.ifmo.ru/verification/2007 02 report-verification.pdf

114. Государственный контракт «Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов». Промежуточный отчет по этапу I. СПбГУ ИТМО, 2009. http://is.ifmo.ru/science/nk-385-l-l.pdf

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

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

117. Заочный тур всесибирской олимпиады 2005 по информатике. http://olimpic.nsu.ru/widesiberia/archive/wso6/2005/rus/ltour/problem/pr oblem.html

118. Кольгхматов И. И., Рыбак О. О., Шалыто А. А. Моделирование устройства для продажи газированной воды на инструментальном средстве UniMod. Проектная документация. СПбГУ ИТМО. 2006. http://is.ifmo.m/download/vending-machine-ru.pdf

119. Николенко С. И. Лекции по генетическим алгоритмам. http://logic.pdmi.ras.ru/~sergev/teaching/ml/04-genetic.pdf

120. Сайт www.genetic-programming.com

121. Сайт http://www.flightgear.org/

122. Яминов Б. Р. Генетические алгоритмы. http://rain.ifmo.ru/cat/view.php/theorv/unsorted/genetic-2005/

123. Analysis of variance (ANOVA). http://www.csse.monash.edu.au/~smarkham/resources/anova.htm

124. Bogor. Software Model Checking Framework. http://bogor.proiects.cis.ksu.edu/

125. Learning DFS from Noisy Samples. A contest from GECCO 2004. http://cswww.essex.ac.uk/staff/sml/gecco/NoisyDFA.html

126. LeventA. H., Mericli C., Mericli Т. и др. Cerberus'08 Team Report. http://www.tzi.de/spl/pub/Website/Teams2008/Cerberus.pdf

127. LTL2BA project. http://www.1sv.ens-cachan.fr/~gastin/ltl2ba/

128. The R Project for Statistical Computing, http://www.r-proiect.org/1. Публикации автора

129. Статьи в журналах из перечня ВАК

130. Царев Ф. Н. Метод построения управляющих конечных автоматов на основе тестовых примеров с помощью генетического программирования // Информационно-управляющие системы. 2010. № 5, с. 31 36. http://is.ifmo.ru/works/ zarev.pdf

131. Царев Ф. Н., Егоров К. В., Шалыто А. А. Совместное применение генетического программирования и верификации для построения автоматов управления системами со сложным поведением // Труды СПИИРАН. 2010. Вып. 15, с. 123 -135.

132. Материалы конференций с участием автора