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

□03447836

На праваХ/^укописи

Лобанов Павел Геннадьевич

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

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

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

Санкт-Петербург ^ ^ ОКТ -008

2008

003447836

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

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

доктор технических наук, профессор Шалыто Анатолий Абрамович

Официальные оппоненты

доктор технических наук, профессор Тимофеев Адиль Васильевич

кандидат технических наук Шопырин Данил Геннадьевич

Ведущая организация

Санкт-Петербургский государственный университет аэрокосмического приборостроения

Защита диссертации состоится «22» октября 2008 года в 16 часов на заседании диссертационного совета Д 212 227 06 в Санкт-Петербургском государственном университете информационных технологий, механики и оптики, 197101, Санкт-Петербург, Кронверкский проспект, д 49, СПбГУ ИТМО.

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

Автореферат разослан 19 сентября 2008 г

совета Д 212 227 06, доктор технических наук, профессор

Ученый секретарь ^^ * Тарлыков Владимир Алексеевич

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Структура диссертации. Диссертация изложена на 114 страницах и состоит из введения, четырех глав и заключения Список литературы содержит 32 наименования. Работа содержит 42 рисунков и 15 таблиц

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

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

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

• построение простейшего предсказателя (эксперименты Л Фогеля),

• оптимизация функций,

• автоматические переговоры,

• распознавание нерегулярных языков,

• проектирование логических схем для автоматов Мили

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

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

• Эволюционные алгоритмы (по Л Фогелю), в которых новые особи появляются только за счет операторов мутации Алгоритмы данного класса не требуют много памяти, однако работают они довольно медленно и легко могут «застрять» в локальном экстремуме

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

• Генетическое программирование является подклассом генетических алгоритмов, в котором особи кодируются с помощью деревьев решений

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

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

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

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

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

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

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

Предлагаемый алгоритм построен на основе классического генетического алгоритма и учитывает специфику решаемой задачи Он имеет следующий вид

1 Создается текущее поколение случайных флибов

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

3. Строится новое поколение флибов

а Создается пустое новое поколение, и в него добавляется лучший предсказатель из текущего поколения

Ь Случайным образом из текущего поколения выбираются две пары флибов с Из каждой пары флибов выбирается лучший предсказатель с1 Лучшие предсказатели из указанных пар скрещиваются е Случайным образом определяется необходимость применения оператора мутации к полученному флибу Если это необходимо, то указанный оператор применяется к флибу £ К флибу применяется новый оператор мутации - «восстановление связей

между состояниями автомата.» g Флиб добавляется в новое поколение

Ь Переходим к пункту Ь, если размер нового поколения меньше размера текущего поколения

4 Текущее поколение флибов заменяется новым

5 Если число поколений меньше заданного пользова гелем, то переходим к пункту 2

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

Опишем алгоритм реализации предлагаемого оператора мутации

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

2 Выполняется цикл по всем состояниям Если текущее состояние не входит в число доступных состояний, то для него выполняются следующие операции

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

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

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

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

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

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

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

Пусть х и F = (£,, , fn) - значение параметра, формируемого средой, и вектор флаговых переменных в текущий момент времени, соответственно Тогда вектор флаговых переменных для следующего момента времени будет иметь вид F' = (f/ = х, fj = fj,. , = :£_,_,) При программной реализации флаговые переменные можно хранить в массиве В этом случае переход от Р к F' осуществляется с помощью удаления последнего элемента массива и вставки в начало массива текущего значения х

Введение каждой флаговой переменной увеличивает число переходов из каждого состояния флиба вдвое При п флаговых переменных число переходов из каждого состояния флиба будет равно 2ntl Номер перехода, который должен использоваться в текущий момент времени, можно вычислить по формуле х + 2'f, + 22f2 + + 2n4

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

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

На тороидальном поле размером 32 на 32 вдоль определенной ломаной линии («тропы») расположено 89 ячеек с едой Расположение ячеек с едой на «тропе» фиксировано На рис 1 приведено пример «тропы», называемый в литературе «тропой Джона Мьюра» (John Muir Trail), которая образована черными и серыми ячейками При этом каждая черная ячейка содержит одну единицу еды

г

9

Рис. 1. Тропа Джона Мыора

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

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

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

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

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

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

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

1 Текущее поколение решений заполняется случайным решениями

2 Из текущего поколения решений отбирается группа лучших решений

3 Формируется новое поколение решений

а Создается пустое новое поколение решений

Ь Из группы лучших решений случайным образом выбирается пара решений

с Формируется новое решение с помощью применения и-точечного

оператора скрещивания к двум выбранным решениям с1 К новому решению применяются операторы мутации («-точечный

оператор мутации и новый оператор мутации) е Новое решение добавляется в новое поколение решений Г Если размер нового поколения меньше размера текущего поколения, то переходим к пункту Ь

4 Новое поколение становится текущим

5 Если число созданных поколений меньше заданного пользователем, переходим к пункту 2

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

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

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

Опишем алгоритм реализации нового оператора мутации - сортировка состояний в порядке использования

1 Создается пустой словарь пар номеров [«старый номер состояния» - «новый номер состояния»]

2 Моделируется работа автомата Перед каждым переходом выполняется следующее если в словаре нет пары, в которой первый элемент равен текущему номеру состояния, то в него добавляется пара [текущий номер состояния - число пар в словаре]

3. Выполняется цикл по всем состояниям автомата Для каждого из них если в словаре нет пары, в которой первый элемент равен номеру состояния, то в него добавляется пара [номер состояния - число пар в словаре] 4 Согласно словарю, изменяется порядок состояний и номера состояний, в

которые ведут переходы Состояния, для которых в словарь добавляются пары в пункте 2 - используемые состояния Состояния, для которых в словарь добавляются пары в пункте 3 -неиспользуемые состояния

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

---, где useful_state_count - число

1 + useful_state _ count

используемых состояний

Так как это соотношение всегда меньше единицы, то наиболее приспособленными будут те муравьи, которые съедают больше еды за 200 ходов

Все эксперименты, о которых идет речь ниже, проводились при размере поколения 10000 и пороге отсечения 2000 Вероятность применения «-точечного оператора скрещивания к элементу автомата' выбрана равной 0 04, а вероятность ~ применения и-точечного оператора мутации - 0 02 Число состояний автомата было ограничено двадцатью Эксперименты проводились на компьютере с процессором AMD Athlon 3800+

В табл 1 приведены результаты экспериментов, в которых использовалась предложенная в работе функция приспособленности Число поколений в экспериментах, проводившихся с «-точечным и предложенным в работе операторами мутации, было ограничено числом 100 Число поколений в экспериментах, в которых использовался только л-точечный оператор мутации, не превышало 200 Лучшим результатом считался муравей, съедающий максимальное число единиц еды Каждый эксперимент без нового операторов мутации и с известной функцией приспособленности длился примерно 320 с - время построения двухсот поколений Продолжительность каждого эксперимента с новым оператором мутации и измененной функцией приспособленности составила около 290 с, - время построения ста поколений

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

Номер эксперимента Номер поколения Результат Число используемых состояний Время поиска

Без применения оператора «сортировка состояний в порядке использования» и новой функции приспособленности 1 137 87 15 225

2 180 88 15 218

3 73 88 12 137

4 72 86 12 114

5 68 89 12 104

С применением оператора «сортировка состояний в порядке использования» и новой функции приспособленности 1 61 89 10 161

2 85 89 10 263

3 70 89 10 227

4 63 89 10 176

5 96 89 9 269

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

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

Решаемая задача формулируется следующим образом Требуется построить автопилот для вертолета, перемещающегося на плоскости За один шаг вертолет может повернуть на некоторый фиксированный угол и изменить скорость движения (ускориться или замедлиться) Минимальная скорость, с которой может перемещаться вертолет Ут1П= 10"4, максимальная - Утах = 2 и ускорение а = 0 1 (все величины в настоящей главе, в том числе и на осях графиков, приведены в условных единицах) Требуется построить автопилот, который за отведенное время полета, проведет вертолет в определенном порядке через максимальное число заранее заданных меток Метки нумеруются, а вертолет их проходит в порядке возрастания номеров При этом вертолет не может пропускать метки, но, так как время полета ограничено, то возможна ситуация, что он может не успеть пройти их все Считается, что вертолет прошел метку, если он оказался от нее на расстоянии не более 0 5

Входные данные (воздействия) (рис 2) автопилота представляют собой единственную переменную (номер сектора обзора) положение текущей метки

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

' текущая метка находится ч в секторе №3 ^ относительно вертолета

ш

Г

О-Ь-

! \

\

' \

ш / ш

а) Угол между направлением движения и

направлением на метку соответствует сектору № 3

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

Рис 2 Входные данные автопилота

При решении этой задачи в качестве стратегии отбора особей для построения следующего поколения используется отбор отсечением При применении такой стратегии родительские решения выбираются из группы лучших решений текущего поколения Размер этой группы (порог отсечения) выбран равным 30% от размера поколения Все автоматы из группы лучших решений имеют одинаковые шансы быть выбранными в качестве родительских особей

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

Все эксперименты проводились при размере поколения 300 При этом порог отсечения равен 90 Максимальное число поколений - 200 Вероятность применения «-точечного оператора скрещивания - 0 04, а вероятность применения «-точечного оператора мутации - 0 02 Число состояний автомата не больше 15 Время полета -200 На рис 3 изображены двадцать меток, пронумерованных в том порядке, в котором через них должен пролететь вертолет Точка с координатами (0, 0) является исходной В начале движения вертолет ориентирован вправо и движется в этом направлении с минимальной скоростью

2 3 4 10 11 12 18 19 "20

1 < < 1 9 < >13 < 17

- 1—► 1 1 »16

% °7

5 10 <3 2В 5 м эг »в 5

Рис 3 Метки, проходимые вертолетом

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

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

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

Число секторов обзора Новый оператор мутации Результат

худший средний лучший

4 Нет 12 14 1 16

Есть 12 14 7 17

6 Нет 11 15 6 18

Есть 14 166 18

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

На рис 4 изображена траектория полета вертолета, управляемого лучшим из встроенных автопилотов

Рис 4 Траектория полета лучшего вертолета

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

С помощью предложенного генетического алгоритма был построен автопилот с 12 состояниями, который проводит вертолет через первые 18 меток из 20 за отведенное ремя. Установлено, что при увеличении времени полета на 33 условных единицы, юлученный автопилот обеспечит прохождение всех 20 меток

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

Заключение

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

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

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

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

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

Список публикаций

1. Лобанов П. Г., Шалыто А. А. Использование генетических алгоритмов для автоматического построения конечных автоматов в задаче о флибах / Материалы 1-й Российской мультиконференции по проблемам управления Сборник докладов 4-й Всероссийской научной конференции «Управление и информационные технологии» СПбГЭТУ «ЛЭТИ» 2006, с 144-149

2. Лобанов П. Г. Использование генетических алгоритмов для решения задачи об умном муравье // Научно-технический вестник СПбГУ ИТМО Вып 39 Исследования в области информационных технологий Труды молодых ученых 2007, с 215-221

3 Лобанов П. Г., Шалыто А. А. Использование генетических алгоритмов для автоматического построения конечных автоматов в задаче о флибах // Известия РАН. Теория и системы управления 2007 №5, с 127-136

4. Лобанов П. Г., Шалыто А А. Использование автоматов с флагами для решения задачи о флибах // Научно-технический вестник СПбГУ ИТМО Вып 42. Фундаментальные и прикладные исследования информационных систем и техночогий 2007, с 67-74

5 Лобанов П. Г., Шалыто А. А. Использование генетических алгоритмов для решения задачи об умном муравье / XIV Всероссийская научно-методическая конференция «Телематика-2007» СПб 2007 Т 2, с 426, 427

6 Лобанов П. Г., Сытник С. А. Использование генетических алгоритмов для построения автопилота для простейшего вертолета / Материалы XV международной научно-методической конференции «Высокие интеллектуальные технологии в образовании и науке» Санкт-Петербургский государственный политехнический университет. 2008 Т1,с 298

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Кронверкский проспект, д 49 Тел (812) 233 46 69 Тираж 100 экз

Введение.

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

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

1.2. Эксперименты Фогеля (регрессия).

1.3. Задача оптимизации функций.

1.4. Автоматические переговоры.

1.5. Распознавание нерегулярных языков.

1.6. Проектирование логических схем для автоматов Мили.

1.6.1. Задача кодирования состояний.

1.7. Обзор методов генерации автоматов с помощью генетических алгоритмов.

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

Глава 2. Генерация автоматов для решения задачи о флибах.

2.1. Постановка задачи.

2.2. Схемы работы генетических алгоритмов в задаче о флибах.

2.2.1. Известный алгоритм.

2.2.2. Предлагаемая модификация алгоритма.

2.3. Реализация флиба.

2.3.1. Известный метод.

2.3.2. Предлагаемый метод.

2.4. Генератор значений входной переменной.

2.5. Функция приспособленности.

2.6. Оператор одноточечного скрещивания.

2.6.1. Известный алгоритм.

2.6.2. Предлагаемый алгоритм.

2.7. Оператор мутации.

2.7.1. Известный алгоритм.

2.7.2. Предлагаемый алгоритм.

2.8. Алгоритм восстановления связей между состояниями.

2.8.1. Программа для проведения экспериментов на флибах.

2.8.2. Эксперименты по применению алгоритма восстановления связей между состояниями.

2.9. Использование автоматов с флагами.

2.9.1. Эксперименты по использованию автоматов с флагами.

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

Глава 3. Генерация автоматов для задачи об умном муравье.

3.1. Постановка задачи.

3.2. Известный генетический алгоритм.

3.2.1. Стратегия отбора.

3.2.2. Оператор скрещивания.

3.2.3. Оператор мутации.

3.3. Предложенные модификации алгоритма.

3.3.1. Сортировка состояний в порядке использования.

3.3.2. Оператор мутации «всегда вперед, если впереди еда».

3.3.3. Уменьшение числа состояний.

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

3.5. Эксперименты.

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

Глава 4. Генерация автоматов для задачи построения автопилота для упрощенной модели вертолета.

4.1. Постановка задачи.

4.2. Модель вертолета.

4.3. Модель окружающей среды.

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

4.5. Общая схема генетического алгоритма.

4.6. Описание программы.

4.7. Эксперименты.

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

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

Актуальность проблемы. В последнее время все шире применяется автоматное программирование, в рамках которого поведение программ описывается с помощью конечных детерминированных автоматов (в дальнейшем автоматов [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. При решении задачи о флибах выполнено сравнение эффективности генетических алгоритмов, которые позволяют генерировать автоматы Мили и автоматы Мили с флагами. Показано, что точность предсказания флибом, который моделируется автоматом с флагами, выше.

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

1. Шалыто А. А. Технология автоматного программирования / Труды первой Всероссийской конференции "Методы и средства обработки информации". МГУ. 2003, с. 150-152. http://is.ifmo.ru/works/tech aut prog

2. Mitchell М. An Introduction to Genetic Algorithms. MA: The MIT Press, 1996.

3. Fogel L., Owens A., Walsh M. Artificial Intelligence through Simulated Evolution. NY: Wiley. 1966. (Фогель Л., Оуэне А., Уолш M. Искусственный интеллект и эволюционное моделирование. М.: Мир, 1969).

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

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

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

7. Hill is W. Co-Evolving Parasites Improve Simulated Evolution as an Optimization Procedure / In Artificial Life II. MA: Addison-Wesley, 1992. pp. 313-324.

8. Whitley, D. A Genetic Algorithm Tutorial, Technical Report CS-93-103, Colorado State University, 1993.

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

10. Шалыто A. A. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998.

11. Naidoo A., PillayN. The Induction of Finite Transducers Using Genetic Programming / Proceedings of Euro GP. Springer. 2007. http://saturn.cs.unp.ac.za/~nelishiap/papers/eurogp07.pdf

12. Ахо А., Сети P., Ульман Дж. Компиляторы: принципы, техника реализации и инструменты. М.: Вильяме, 2001.

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

14. Zomorodian A. Context-free Language Induction by Evolution of Deterministic PushDown Automata Using Genetic Programming. http://www.cs.dartmouth.edu/~afra/papers/aaai96/aaai96.pdf

15. Воронин О., Дьюдни А. Дарвинизм в программировании // Мой компьютер. 2004. № 35, с. 18-21. http://www.mycomp.kiev.ua/text/7458

16. Miller В., Goldberg M Genetic algorithms, tournament selection, and the effects of noise // Complex Systems. 1995. 3, pp. 193-212.

17. De Jong K. An analysis of the behavior of a class of genetic adaptive systems. PhD thesis. Univ. Michigan. Ann Arbor, 1975.

18. Jefferson D., Collins R., Cooper С., Dyer M., Flowers M., KorfR., Taylor С., Wang A. The Genesys System: Evolution as a Theme in Artificial Life. 1992. www.cs.ucla.edu/~dyer/Papers/AlifeTracker/Alife91 Jefferson.html

19. Miller В., Goldberg M. Genetic algorithms, tournament selection, and the effects of noise // Complex Systems. 1995. V. 9. № 3, pp. 193-212.

20. Angeline P. J., Pollack J. Evolutionary Module Acquisition / Proceedings of the Second Annual Conference on Evolutionary Programming. 2003. http://www.demo.cs.brandeis.edu/papers/ep93.pdf

21. Chambers L. Practical handbook of genetic algorithms. Boca Raton. CRC Press, 1995.

22. Лобанов П. Г., Шалыто А. А. Использование генетических алгоритмов для автоматического построения конечных автоматов в задаче о флибах // Известия РАН. Теория и системы управления. 2007. № 5, с. 127-136.

23. Лобанов П. Г. Использование генетических алгоритмов для решения задачи об умном муравье // Научно-технический вестник СПбГУ ИТМО. Вып. 39. Исследования в области информационных технологий. Труды молодых ученых. 2007,с. 215-221.

24. Лобанов П. Г., Шалыто А. А. Использование генетических алгоритмов для решения задачи об умном муравье / XIV Всероссийская научно-методическая конференция «Телематика-2007». СПб. 2007. Т.2, с. 426, 427.

25. Лобанов П. Г., Шалыто А. А. Использование автоматов с флагами для решения задачи о флибах // Научно-технический вестник СПбГУ ИТМО. Вып. 42. Фундаментальные и прикладные исследования информационных систем и технологий. 2007, с. 67-74.