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

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

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

Для многих задач автоматы удается строить эвристически, однако существуют задачи, для которых такое построение затруднительно или невозможно. Известны задачи (например, итерированная дилемма узников [2] и задача о «флибах» [3, 4]), в которых применение генетических алгоритмов (направленного перебора) позволяет генерировать автоматы. Это повышает уровень автоматизации автоматных программ и является одним из первых шагов к автоматическому построению программ.

Генетические алгоритмы [5] применяются при решении широкого круга задач. Однако при использовании классических генетических алгоритмов для генерации автоматов часто требуются большие вычислительные ресурсы, для того чтобы получить решение с необходимым уровнем качества.

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

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

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

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

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

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

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

4. Исследование эффективности генетических алгоритмов при построении двух разнотипных автоматов для одной из рассмотренных задач.

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

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

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

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

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

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

Результаты диссертации получены в ходе работ по государственному контракту «Технология генетического программирования для генерации автоматов управления системами со сложным поведением» (шифр «2007;4−14−18−01−033»), проводимых СПбГУИТМО в 2007;2008 гг. в рамках Федеральной целевой программы.

Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России" на 2007 — 2012 гг.

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

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

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

Апробация диссертации. Основные положения диссертационной работы докладывались на 4-й Всероссийской научной конференции «Управление и информационные технологии» СПбГЭТУ «ЛЭТИ» (2006), XXXVI научной и учебно-методической конференции профессорско-преподавательского и научного состава СПбГУ ИТМО (2007), IV межвузовской конференции молодых ученых СПбГУ ИТМО (2007), XIV Всероссийской научно-методической конференции «Телематика-2007» (Санкт-Петербург), XXXVII научной и учебно-методической конференции СПбГУ ИТМО (2008), V Всероссийской межвузовской конференции молодых ученых СПбГУ ИТМО (2008), XV международной научно-методической конференции «Высокие интеллектуальные технологии и инновации в образовании и науке» (Санкт-Петербургский государственный политехнический университет, 2008).

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

Структура диссертации. Диссертация изложена на 114 страницах и состоит из введения, четырех глав и заключения.

Список литературы

содержит 32 наименования. Работа содержит 42 рисунков и 15 таблиц.

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

В работах [23, 28] автором предложены новый оператор мутации «восстановления связей между состояниями» и модификация генетического алгоритма для решения задачи о флибах.

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

В работе [31] автором для задачи о флибах выполнено сравнение эффективности генетических алгоритмов, которые позволяют генерировать автоматы Мили и автоматы Мили с флагами.

В работе [32] автором предложен генетический алгоритм, использующий оператор мутации «сортировка состояний в порядке использования», для построения автопилота для упрощенной модели вертолета.

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

Результаты, полученные в диссертации, используются на практике в компании Транзас при разработке тренажера вертолета и в учебном процессе в СПбГУ ИТМО. Акты внедрения прилагаются.