Главная >> Программы

Pages: |

| 2 |

«НАУЧНО-ТЕХНИЧЕСКИЙ НАУЧНООТЧЕТ о выполнении 1 этапа Государственного контракта № П2174 от 09 ноября 2009 г. Исполнитель: Государственное образовательное учреждение высшего профессионального образования ...»

-- [ Страница 1 ] --

Федеральное агентство по образованию

УДК 004.4’242

ГРНТИ 20.01.01, 28.23.29

Инв. № 390163-1

ПРИНЯТО: УТВЕРЖДЕНО:

Приемочная комиссия Государственного заказчика: Государственный заказчик

Федеральное агентство по образованию

От имени Приемочной комиссии От имени Государственного заказчика _/Попова Е.П. / _/Бутко E.Я./

НАУЧНО-ТЕХНИЧЕСКИЙ

НАУЧНООТЧЕТ

о выполнении 1 этапа Государственного контракта № П2174 от 09 ноября 2009 г.

Исполнитель: Государственное образовательное учреждение высшего профессионального образования «Санкт-Петербургский государственный университет информационных технологий, механики и оптики»

Программа (мероприятие): Федеральная целевая программ «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг., в рамках реализации мероприятия № 1.3.2 Проведение научных исследований целевыми аспирантами.

Проект: Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов Руководитель организации: Васильев Владимир Николаевич Руководитель проекта: Царев Федор Николаевич Согласовано:

Управление научных исследований и инновационных программ От имени Заказчика _/Кошкин В.И./ Санкт-Петербург 2009 г.

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

СПИСОК ОСНОВНЫХ ИСПОЛНИТЕЛЕЙ

по Государственному контракту № П2174 от 09 ноября 2009 г.

на выполнение поисковых научно-исследовательских работ для государственных нужд Организация-Исполнитель: Государственное образовательное учреждение высшего профессионального образования государственный университет «Санкт-Петербургский информационных технологий, механики и оптики»

Руководитель темы:

без ученой степени, Царев Ф. Н.

без ученого звания подпись, дата Исполнители темы:

без ученой степени, Егоров К. В.

без ученого звания подпись, дата без ученой степени, Буздалов М. В.

без ученого звания подпись, дата без ученой степени, Соколов Д. О.

без ученого звания подпись, дата без ученой степени, Царев М. Н.

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

РЕФЕРАТ

Отчет 58 с., 4 гл., 17 рис., 5 табл., 56 источников.

Ключевые слова: машинное обучение; конечные автоматы; конечны распознаватели; автомат Мура;

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

В настоящем отчете излагаются результаты выполнения первого этапа поисковых научноисследовательских работ по направлению «Информатика» по проблеме «Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов», выполняемых в рамках государственного контракта, заключенного между Федеральным агентством по образованию и государственным образовательным учреждением высшего информационных технологий, механики и оптики» в соответствии с решением Единой комиссии (протокол от 13 октября 2009 г. № 3/НК-385П) по конкурсу № НК-385П «Проведение поисковых научно-исследовательских работ по направлениям: «Информатика», «Механика», «Радиофизика, акустика и электроника», «География и гидрология суши», «Общая биология и генетика», «Геология.

Горное дело» в рамках мероприятия 1.3.2 Программы» мероприятия 1.3.2 «Проведение научных исследований целевыми аспирантами» по направлению 1 «Стимулирование закрепления молодежи в сфере науки, образования и высоких технологий» федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009 – 2013 годы» федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009–2013 годы, утвержденной постановлением Правительства Российской Федерации от 28 июля 2008 года № «О федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009–2013 годы».

Целями настоящего этапа являются:

1. Выполнение аналитического обзора.

2. Выбор и обоснование оптимального варианта направления исследований.

3. Подготовка плана проведения теоретических и экспериментальных исследований.

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

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

1. Статьи в ведущих зарубежных и российских журналах, монографии и патенты за 2. Результаты автоматического поиска в сети Интернет по ключевым словам и шаблонам.

3. Работы членов коллектива, опубликованные в рамках НИР по схожей тематике.

4. Аналитический обзор, составленный в рамках НИР.

5. Постановление Правительства Российской Федерации от 4 мая 2005 г. № 284 «О государственном учете результатов научно-исследовательских, опытноконструкторских и технологических работ гражданского назначения».

6. Язык программирования Java.

7. Интегрированная среда разработки Eclipse.

8. Персональный компьютер.

9. ГОСТ 7.32-2001 «Отчет о научно-исследовательской работе. Структура и правила Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных Излагаются результаты выполнения аналитического обзора по следующим направлениям:

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

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

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

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

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

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

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

1.2.1.1. Построение конечных распознавателей

1.2.1.2. Построение конечных преобразователей

1.2.2. Построение управляющих конечных автоматов на основе принципа «обучения на собственных ошибках»

1.3. СОВМЕСТНОЕ ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ И ВЕРИФИКАЦИИ

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

1.3.2. Совместное применение генетических алгоритмов и верификации для построения алгоритмов взаимного исключения

1.4. СРАВНЕНИЕ РАССМОТРЕННЫХ АЛГОРИТМОВ МАШИННОГО ОБУЧЕНИЯ

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

2. ВЫБОР И ОБОСНОВАНИЕ ОПТИМАЛЬНОГО ВАРИАНТА НАПРАВЛЕНИЯ

ИССЛЕДОВАНИЙ

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

3. ПЛАН ПРОВЕДЕНИЯ ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

3.1. ПЛАН ПРОВЕДЕНИЯ ПЕРВОГО ЭТАПА ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

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

ИССЛЕДОВАНИЙ

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

4. РАЗРАБОТКА, ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНОЕ

ИССЛЕДОВАНИЕ МЕТОДА МАШИННОГО ОБУЧЕНИЯ НА ОСНОВЕ

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

КОНЕЧНЫХ АВТОМАТОВ МИЛИ НА ОСНОВЕ ТЕСТОВЫХ ПРИМЕРОВ

4.1. ПОСТАНОВКА ЗАДАЧИ

4.2. ОПИСАНИЕ ПРЕДЛАГАЕМОГО МЕТОДА

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

4.2.1.1. Обработка входных переменных

4.2.1.2. Алгоритм расстановки пометок

4.2.1.3. Операция мутации

4.2.1.4. Операция удаления дублирующихся переходов

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

4.2.1.6. Генерация начального поколения

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

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

4.3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

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

4.4.1. Система тестовых примеров

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

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

ЗАКЛЮЧЕНИЕ

ИСТОЧНИКИ

ВВЕДЕНИЕ

Горное дело» в рамках мероприятия 1.3.2 Программы» мероприятия 1.3.2 «Проведение научных исследований целевыми аспирантами» по направлению 1 «Стимулирование закрепления молодежи в сфере науки, образования и высоких технологий» федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009 – 2013 годы» федеральной целевой программы «Научные и научно-педагогические кадры инновационной России» на 2009-2013 годы, утвержденной постановлением Правительства Российской Федерации от 28 июля 2008 года № «О федеральной целевой программе «Научные и научно-педагогические кадры инновационной России» на 2009–2013 годы».

Целями настоящего этапа являются:

1. Выполнение аналитического обзора.

2. Выбор и обоснование оптимального варианта направления исследований.

3. Подготовка плана проведения теоретических и экспериментальных исследований.

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

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

• совместное применение генетических алгоритмов и верификации.

Во второй главе приводится выбор и обоснование оптимального варианта направления исследований.

В третьей главе приводится план проведения теоретических и экспериментальных исследований.

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

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

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

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

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

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

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

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

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

1. АНАЛИТИЧЕСКИЙ ОБЗОР

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

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

• совместное применение генетических алгоритмов и верификации.

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

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

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

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

Скрытая Марковская модель [57] – это статистическая модель, в которой моделируемая система представляется в виде Марковской цепи с ненаблюдаемым состоянием. В отличие от обычных Марковских моделей внешний наблюдатель видит не состояние, а выходной символ, зависящий от состояния. При этом в каждом состоянии задано свое распределение вероятностей появления выходных символов. Скрытая Марковская модель = ( A, B, ) содержит три компонента:

A – матрица вероятностей переходов между состояниями, B – матрица вероятностей генерации выходных символов, – начальное распределение вероятностей.

Обычно рассматривают три задачи, связанные со скрытыми Марковскими моделями:

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

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

Первая задача решается с помощью динамического программирования, вторая – с помощью алгоритма Витерби, а третья – с помощью алгоритма Баума-Велча. Алгоритм Баума-Велча является разновидностью EM-алгоритма [39].

1.1.3. Генетические алгоритмы и эволюционные вычисления В этом разделе приведено краткое описание традиционного генетического алгоритма (conventional genetic algorithm) [51] с одноточечной рекомбинацией и мутацией. В этом алгоритме каждая особь представляет собой битовую строку длины L, а размер популяции равен n.

Шаг 1. Генерации начальной популяции {xi }i =1. Для этого, например, можно сгенерировать n битовых строк, в которых каждый из L битов равен 0 или 1 с одинаковой вероятностью.

Шаг 2. Вычислить функцию приспособленности f(x) для каждой особи из текущей популяции.

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

Шаг 3. Переход к следующему поколению популяции. При создании нового поколения могут использоваться различные стратегии. В качестве примера приведем так называемый метод рулетки (roulette wheel selector) [6].

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

скрещивание (рекомбинация, кроссовер, кроссинговер) родительских особей. В результате образуются их «потомки» – z1 и z2. Происходит это следующим образом: случайно (с равномерным распределением на множестве {1, 2, …, L}) выбирается число k. Хромосомы «потомков» z1 и z2 теперь строятся следующим образом: для z1 – первые k символов совпадают с первыми k символами x, последние (L-k) – с последними (L-k) символами y, для z2 – наоборот. Например, если L=7, x=1001010, y=0001001, k=3, то z1=1001001, z2=0001010. После этого равновероятно выбирается одна из особей z1, либо z2. Выбранную особь обозначим как z.

С некоторой (как правило, порядка 0.01) вероятностью производится мутация особи z – в ней случайно выбирается один бит и изменяется.

Получившаяся в результате особь z добавляется в следующее поколение.

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

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

Генетическое программирование (genetic programming), предложенное J.R. Koza в 1992 году [45], предполагает применение генетических алгоритмов для автоматизированного построения программ.

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

Такой подход позволяет определить генетические операции скрещивания и мутации, которые лучше подходят для решаемой задачи. Например, если каждая особь представляет собой программу, то возможны так называемые операции, изменяющие архитектуру (architecture-altering operations), – например, добавление подпрограммы [23].

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

В настоящем разделе описываются типы автоматных моделей. Абстрактные конечные автоматы принято описывать в следующих терминах. Задано конечное множество символов X, (последовательностей, строк, слов), составленных из символов алфавита X, обозначается X*. Пустая последовательность символов обозначается, X *. Подмножество L множества всех цепочек над алфавитом X, L X * называется языком. Рассматривается следующая проблема: задан язык L X * и цепочка X *. Необходимо определить, принадлежит ли указанная цепочка языку ( L )?

Если абстрактный вычислитель способен решить эту проблему для определенного языка L X и произвольной строки X *, то говорят, что вычислитель распознает язык L. Таким образом, абстрактные автоматы описываются в терминах тех языков, которые они распознают.

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

Детерминированный конечный автомат (ДКА) – это пятерка X, Y,, y0, F, где X – конечный алфавит входных символов, Y – конечное множество состояний, : X Y Y – функция переходов, y0 Y – начальное (стартовое) состояние, F Y – множество допускающих состояний.

Расширенная функция переходов : X * Y Y, сопоставляющая новое состояние текущему состоянию и цепочке символов, определяется индуктивно следующим образом [31]:

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

Множество допускаемых цепочек образует язык L, распознаваемый детерминированным конечным автоматом (ДКА): L = X * | (, y0 ) F.

Класс языков, распознаваемых ДКА, называют регулярными языками. Известно, что он совпадает с классом языков, описываемых регулярными выражениями и автоматными грамматиками [31].

Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных Для того чтобы наделить модель абстрактного конечного автомата способностью не только давать ответ типа «да/нет», но и выполнять какие-то преобразования, в модель добавляют конечный алфавит выходных символов Z и функцию выходов. Если функция выходов имеет вид : X Y Z, то вычислитель называется автоматом Мили, а если : Y Z – автоматом Мура.

Таким образом, рассматривается шестерка X, Y, Z,,, y0. Она определяет автоматное отображение f : X * Z * (преобразование, выполняемое автоматом) следующим образом:

Автоматные отображения – это отображения «без предсказания»: перерабатывая цепочку слева направо, они «не заглядывают вперед». Например, отображение, которое сопоставляет цепочке ее саму, записанную в обратном порядке, не является автоматным.

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

Рис. 1. Автоматы Мура: первого рода (слева) и второго рода (справа) На приведенном рисунке функция переходов и функция выходов вычисляются соответственно схемами КС1 и КС2, а как ЭЗ обозначен элемент задержки. Подобное изображение связано с тем, что первоначально такие автоматы реализовывались аппаратно в виде набора логических схем.

На рис. 2 приведен пример графа переходов автомата Мура.

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

Рис. 3. Автоматы Мили: первого рода (слева) и второго рода (справа) Известно [30], что для любого автомата Мили можно построить эквивалентный ему автомат Мура. Число состояний в таком автомате будет не меньше, чем в исходном.

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

Рис. 4. Автомат Мили последовательного двоичного одноразрядного сумматора На этом рисунке xi и yi – складываемые биты, состояния соответствуют значениям переноса, а значение бита суммы формируется как выходное воздействие на переходах.

Если часть выходных переменных автомата зависит только от состояний, а остальные – также и от входных воздействий, удобно разделить функцию выходов на две составляющие: 1 ( y ) и Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных 2 ( x, y ). В структурную схему автомата в этом случае вводится не один, как в автоматах Мура и Мили, а два выходных преобразователя (рис. 5). Такие автоматы называются смешанными, автоматами Мура-Мили или С-автоматами.

Рис. 5. Смешанные автоматы: первого рода (слева) и второго рода (справа 1.1.5. Совместное применение генетических алгоритмов и скрытых Марковских моделей для тестирования конечных автоматов В работе [3] разрабатывается метод совместного применения генетических алгоритмов и скрытых Марковских моделей для тестирования конечных автоматов. В указанной работе рассматривается поиск ошибок типа «неучтенный переход» в конечных автоматах. Для этого на автомат подаются заранее заданные последовательности, записываются полученные выходные последовательности, и на их основе строится скрытая Марковская модель. При этом рассматриваются только так называемые «сильно детерминированные» модели, в которых из каждого состояния с вероятностью, близкой к единице, выполняется один переход, а вероятности других переходов из этого состояния близки к нулю.

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

Особь в рассматриваемом генетическом алгортме представлялась в виде массива размерностью N на два, каждый элемент которого – целое число от 0 до N–1. Здесь N – число состояний. Таким образом, для каждого состояния записываются два перехода. Первоначально их вероятности принимаются равными. Далее они изменяются в процессе работы алгоритма БаумаВелча.

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

Такой вид отбора называется «rank selection» и подробно описан в работе [51]. Отбор пропорциональный значению приспособленности («roulette wheel selection») также был опробован в этой работе, но дал несколько худшие результаты.

Оператор мутации выполняется стандартным образом – с небольшой вероятностью (в проведенных экспериментах она равнялась 0.1) каждое из чисел хромосомы изменяется на целое число от 0 до N – 1. Новое значение может совпадать с предыдущим.

Скрещивание также осуществляется стандартным образом – применяется одноточечное скрещивание («single-point crossover»), рассмотренное в книге [51]. Единственное отличие состоит в том, что с некоторой вероятностью (в проведенных экспериментах равной 0.3) особи не подвергаются скрещиванию, а случайным образом выбирается одна из них и возвращается как результат скрещивания.

Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных Приспособленность f(x) особи x, задающей некоторую модель = ( A, B, ), определялась как Результаты вычислительных экспериментов показали, что поиск неучтенных переходов выполнялся генетическими алгоритмами, а частота их использования (в ходе работы автомата) определялась алгоритмом Баума-Велша. Следовательно, основная заслуга в успешном построении моделей максимального правдоподобия для рассматриваемого случая принадлежит генетическим алгоритмам.

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

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

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

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

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

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

Однако, в работе [40] показано, что эта задача является NP-трудной.

В работе [47] производится сравнение алгоритмов машинного обучения для построения конечных автоматов-распознавателей. При этом рассматриваются два типа алгоритмов:

эволюционные и основанные на построении префиксного дерева (бора) с дальнейшим объединением состояний на основе свидетельств (Evidence-Driven State Merging – EDSM).

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

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

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

Для сокращения пространства поиска в работе [47] применяется специальный метод определения того, какие состояния автомата являются допускающими, а какие – нет. Для этого предлагается использовать так называемый «алгоритм расстановки пометок на состояниях». Он состоит в следующем. Для каждой строки t из множества обучающих примеров на единицу увеличивается значение h[f(t)][c], где f(t) – номер состояния, в которое приходит рассматриваемый Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных конечный автомат после обработки строки t, а число c равно единице, если строка s должна допускаться автоматом, и равно нулю, если она не должна допускаться. После этого те состояния s, для которых h[s][1] > h[s][0], помечаются как допускающие, а все остальные – как недопускающие. За счет применения описанного алгоритма размер пространства поиска существенно сокращается – его размер становится равным n2n.

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

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

Сравнение эволюционного алгоритма проводилась на двух наборах тестовых примеров.

Первый набор тестовых данных предложен в работах [50, 56]. На этом наборе сравнение проводилось не только с алгоритмом EDSM, но и с алгоритмом генетического программирования, предложенным в работе [50]. Это сравнение показывает, что разработанный алгоритм эволюционного программирования превосходит и алгоритм EDSM, и алгоритм генетического программирования, как по точности построенных автоматов, так и по времени работы. Например, среднее время, которое требуется предложенному в рассматриваемой работе алгоритму для построения конечного автомата, составляет 1.6 миллисекунды, а алгоритму EDSM – в среднем 37 миллисекунд. Вычислительные эксперименты проводились на компьютере с процессором Pentium IV с тактовой 2.4 ГГц для реализаций на языке программирования Java.

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

2. Генерировался случайный ориентированный граф из 5n/4 вершин, в котором каждая 3. Случайным образом выбиралась вершина – начальное состояние.

4. Рассматривались все достижимые из начального состояния.

5. Каждое из состояний с равной вероятностью становилось либо допускающим, либо недопускающим.

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

На этом тестовом наборе разработанный эволюционный алгоритм при n = 4, 8, 16 превосходил алгоритм EDSM, но при n = 32 ему уступал.

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

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

Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных Конечный распознаватель в рассматриваемой работе представляется так же, как и в работе [47] – в хромосому входит таблица переходов, а пометки на состояниях расставляются с помощью специального алгоритма. В качестве эволюционного алгоритма в работе [48] также используется (1+1)-эволюционная стратегия, но операцию мутации предлагается выполнять не так, как в работе [47].

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

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

Для каждого перехода t в автомате вычисляются две величины. Число строк, которые были правильно классифицированы автоматом и при обработке которых использовался переход t, обозначается как c(t). Число строк, неправильно классифицированных автоматом и при обработке которых использовался переход t, обозначается как e(t). После этого вероятность того, что переход t формуле: p(t ) =. При этом считается, что p(t)=0, если e(t)=0. Такой подход к выполнению операции мутации требует выполнения двух проходов для вычисления значения функции приспособленности и указанных вероятностей. На первом из этих проходов неизвестно, какие состояния являются допускающими, а какие – нет, так как он необходим для алгоритма пометки состояний. На втором известно, какие состояния являются допускающими. Поэтому указанные вероятности могут быть вычислены.

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

Для сравнения алгоритмов машинного обучения в рассматриваемой работе применялось два набора тестовых данных. Первый строился так же, как второй набор тестовых данных в работе [47].

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

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

• метода, который не использует алгоритм расстановки пометок (plain);

• метода из работы [47] (smart labeling);

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

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

Результаты вычислительных экспериментов показали, что при восьми состояниях автомата, на основе которого генерировались обучающие наборы, из 50 случаев алгоритм построил автомат в 26, алгоритм smart labeling – в 42, алгоритм sampled – в 47, а алгоритм quick-sampled – в 43. При использовании автомата из 16 состояний результаты были такими: plain – пять из 50, smart – 21 из 50, sampled – 26 из 50, quick-sampled – четыре из 50. Если же в исходном автомате было 32 состояния, то Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных только два алгоритма справились с задачей: smart правильно строил автомат в шести случаях из 50, а sampled – в 12 случаях из 50.

На втором наборе тестовых данных, который содержал зашумленные обучающие наборы. На этом наборе данных сравнение проводилось с алгоритмом EDSM и с другими алгоритмами, участвовавшими в соревновании GECCO 2004 [46]. Результаты вычислительных экспериментов показали, что предлагаемый в рассматриваемой работе эволюционный алгоритм (sampled) превосходит все существующие методы машинного обучения конечных автоматов на этом обучающем наборе по точности построения автоматов. При этом отметим, что предложенный алгоритм эффективен только для построения автоматов из относительно небольшого числа состояний (порядка нескольких десятков), в то время как с помощью алгоритма EDSM могут быть успешно построены автоматы из сотен состояний.

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

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

Переходы, отсутствующие в обоих родителях, генерируются случайно.

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

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

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

В работе [55] также рассматривается задача построения конечных автоматов-распознавателей.

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

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

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

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

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

Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных По построению конечных преобразователей на основе обучающих примеров существует намного меньше работ, чем по построению конечных распознавателей. Одной из них является работа [49]. Автоматы-преобразователи в ходе обработки символов входного слова при выполнении переходов записывают в выходной поток символы выходного алфавита, тем самым осуществляя преобразование слов одного формального языка в слова другого.

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

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

Опишем алгоритм выполнения операции мутации в алгоритме, предложенном в рассматриваемой работе. Выполняется мутация одного из трех типов:

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

• случайное изменение одного перехода.

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

В рассматриваемой работе рассматриваются три варианта функции приспособленности:

• на основе строгого сравнения (strict);

• на основе вычисления расстояния Хэмминга [41] (hamming);

• на основе вычисления редакционного расстояний (расстояния Левенштейна) [14] (edit).

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

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

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

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

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

1.2.2. Построение управляющих конечных автоматов на основе принципа В работе [54] рассматривается задача построения управляющего конечного автомата на основе принципа «обучения на собственных ошибках». В указанной работе рассматривается задача построения автоматов для игры «Соревнование за ресурсы» (Competition for Resources). Игровое поле в этой игре имеет форму тора размером 10 на 10 клеток (тор можно представить в виде квадрата, у которого верхняя сторона склеена с нижней, а правая – с левой). Оно моделирует компьютерную сеть, в которой могут распространяться программные агенты.

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

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

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

Для решения описанной задачи в работе [54] применяется генетический алгоритм. Конечный автомат представляется в виде таблицы значений функции переходов и таблицы значений функции действий. В работе рассматривалось построение автоматов, содержащих от одного до десяти состояний. При построении автомата из n состояний размер таблиц значений указанных функции составляет n80, так как существует 80 комбинаций входных переменных. Это объяняется тем, что имеется четыре переменные, каждая из которых может принимать три возможных значения. При Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных этом ровно одна комбинация (все четыре соседние клетки принадлежат другому агенту) не может встретиться в игре. Это объясняется тем, что клетка, из которой агент пришел в текущую принадлежит ему.

Мутации с некоторой заданной вероятностью подвергалась каждая из ячеек таблицы значений функции переходов и функции действий. При этом с вероятностью p изменялось состояние, в которое ведет переход, а с вероятностью 1 - p – действие, выполняемое на этом переходе. Кроме этого, использовалась операция однородного скрещивания. Для каждой позиции (i, j) в таблицах значений функций переходов и действий производился обмен ячеек между «родителями» с некоторой заданной вероятностью.

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

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

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

Вычислительные эксперименты проводились при значениях n = 1..10. Их результаты показывают, что при решении этой задачи существенное преимущество имеют автоматы, имеющие более двух состояний. Автоматы с числом состояний от трех до десяти показывали примерно одинаковые результаты – около 90% побед. Кроме этого, были проведены эксперименты, в которых в процессе мутации разрешалось добавлять и удалять состояния. В этом случае было замечено, что в построенных автоматах используется меньше половины состояний. На основании результатов экспериментов был сделан вывод о том, что операции добавления и удаления состояний являются слишком «разрушительными» для их применения в эволюционных алгоритмах построения конечных автоматов.

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

Применение такого метода позволило построить систему управления агентом, которая добивалась побед в 96% игр. Описанный метод устранения зацикливания является одной из разновидностей динамической верификации [52].

В рамках исследований по теме «Технология генетического программирования для генерации автоматов управления системами со сложным поведением» на кафедре «Технологии Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных программирования» СПбГУ ИТМО был разработан ряд методов генерации конечных автоматов с помощью генетических алгоритмов [24–27].

Один из этих методов – метод сокращенных таблиц переходов был предложен в работе [20].

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

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

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

Рис. 6. Хромосома состояния: сокращенная таблица (n = 6, m = 3, r = 2, |S| = 3) Число строк таблицы в этом случае 2, однако, константа r обычно невелика. Ее выбор зависит от сложности задачи. Как показывает опыт, для большинства автоматизированных объектов среднее по всем состояниям значение r не больше пяти.

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

• внутренние узлы помечены символами переменных;

• ребра – значениями переменных;

• листья – значениями искомой функции.

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

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

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

Каждое состояние автомата представляется с помощью соответствующего дерева решений.

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

• номер переменной, соответствующей метке узла;

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

• номер состояния, в которое ведет переход из данной вершины (для листьев).

Следовательно, при использовании описываемого метода автомат представляется объектом следующего вида на языке Java:

class TreeAutomata { Tree[] trees;

int startState;

class Tree { Node root;

Третий метод – метод совместного применения конечных автоматов и нейронных сетей был предложен в работах [33, 34]. При использовании этого метода для управления системой со сложным поведением предлагается применять нейронную сеть и конечный автомат, которые совместно строятся генетическим алгоритмом.

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

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

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

Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных Экспериментальное исследование указанных трех методов проводилось на построении автомата для задачи «Умный муравей-3».

Приведем сначала описание классической постановки задачи «Умный муравей» [36, 42].

Используется двумерный тор размером 32 на 32 клетки (рис. 9). На некоторых клетках поля расположены яблоки – черные клетки на рис. 9. Яблоки расположены вдоль некоторой ломаной линии, но не на всех ее клетках. Клетки ломаной, на которых яблок нет – серые. Белые клетки – не принадлежат ломаной и не содержат яблок. Всего на поле 89 яблок.

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

• идет вперед на одну клетку, съедая яблоко, если оно находится перед ним;

• поворачивается вправо;

• поворачивается влево;

Съеденные муравьем яблоки не восполняются. Муравей жив на всем протяжении игры – еда не является необходимым ресурсом для его существования. Никаких других персонажей, кроме муравья, на поле нет. Ломаная строго задана. Муравей может ходить по любым клеткам поля. Игра длится не более 200 ходов, на каждом из которых муравей совершает одно из четырех описанных выше действий. В конце игры подсчитывается число яблок, съеденных муравьем. Это значение – результат игры.

Цель игры – создать муравья, который не более чем за 200 ходов съест как можно больше яблок. Муравьи, съевшие одинаковое число яблок, заканчивают игру с одинаковым результатом вне зависимости от числа ходов, затраченных каждым из них на процесс еды. Однако эта задача может иметь различные модификации, например, такую, в которой при одинаковом числе съеденных яблок, лучшим считается муравей, съевший яблоки за меньшее число ходов. Ниже будет показано, что Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных поведение муравья может быть задано конечным автоматом. При этом может быть поставлена задача о построении автомата с минимальным числом состояний для муравья, съедающего все яблоки, или автомата для муравья, съедающего максимальное число яблок при заданном числе состояний.

Постановка задачи «Умный муравей-3», предложенной в работе [2], содержит несколько существенных отличий.

Во-первых, расширена область обзора муравья – вместо одной клетки он видит восемь. Таким образом, множество значений входных переменных содержит 28 = 256 элементов. На рис. изображена область обзора муравья (клетка, в которой находится муравей, обозначена серым цветом).

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

При этом вероятность того, что яблоко окажется в некоторой клетке, одинакова для всех клеток поля и равна µ.

В этом случае число яблок, съеденных муравьем за 200 ходов, является случайной величиной (определяемой муравьем) на дискретном множестве элементарных исходов – множестве расположений еды – битовых матриц 32 x 32. Каждому исходу i, содержащему k единиц, поставим в соответствие вероятность p(i) = µk(1-µ)n-k, где n = 32 x 32.

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

Экспериментальные исследования, проведенные в работе [27], показали, что при построении автомата для задачи «Умный муравей-3» указанные три метода представления автоматов показали примерно одинаковые результаты – максимальное достигнутое значение функции приспособленности составило примерно 27 для автоматов из 4–16 состояний.

1.3. СОВМЕСТНОЕ ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ И ВЕРИФИКАЦИИ

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

1.3.1. Совместное применение генетических алгоритмов и верификации для построения взаимодействующих конечных автоматов Работа [43] посвящена построению взаимодействующих конечных автоматов с использованием генетического программирования с функцией приспособленности, при вычислении которой используется верификация моделей [13]. Верификация моделей – это набор методов и алгоритмов, которые позволяют определять, соответствует ли программа некоторому множеству требований. При этом требования выражаются на языке темпоральной логики – записываются утверждения о поведении программы во времени.

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

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

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

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

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

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

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

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

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

• с вероятностью 0.2 изменяется пометка перехода.

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

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

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

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

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

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

Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных 1.3.2. Совместное применение генетических алгоритмов и верификации для В работе [44] рассматривается задача автоматизированного построения алгоритмов взаимного исключения. Алгоритмы взаимного исключения играют важную роль в разработке распределенных программ. Цель таких алгоритмов – предовратить одновременный доступ нескольких процессов к общему ресурсу.

Алгоритм взаимного исключения в рассматриваемой работе представляется в виде дерева программы, в которой разрешается использовать операторы if, while и оператор присваивания.

При этом разрешается обращаться к трем общим битовым переменным A[0], A[1] и A[2].

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

• замена случайно выбранного поддерева на случайно сгенерированное;

• удаление случайно выбранного поддерева;

• добавление родительского узла для случайно выбранного узла;

• удаление родительского узла для случайно выбранного узла.

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

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

1.4. СРАВНЕНИЕ РАССМОТРЕННЫХ АЛГОРИТМОВ МАШИННОГО ОБУЧЕНИЯ

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

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

• задача, на которой проводится экспериментальное исследование;

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

• тип эволюционного алгоритма;

• особенности предлагаемого эволюционного алгоритма;

• тип алгоритма машинного обучения.

Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных Таблица 1. Сравнение рассмотренных в обзоре алгоритмов машинного обучения, основанных на эволюционных вычислениях, для построения конечных автоматов Название работы Рассматриваемая Метод Тип Особенности эволюционного Тип алгоритма алгоритмов для генерации автоматов при построении правдоподобия и в задачах управления versus Evidence Drive State Merging (2003) Finite Automata with a Smart State Labeling Algorithm A Genetic Finite State Automata Induction with Application to Phonotactics Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных Genetic Finite State Machines Evolving Finiteстратегия Some Initial Explorations Strategies for Protecting Resources генерации автоматов с входных переменных деревьями решений для использования программирова нии (2008) Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных программирова ния, конечных автоматов и сетей для построения системы управления аппаратом with Fitness Checking Genetic and Model Checking:

Synthesizing New Mutual Exclusion Разработка методов машинного обучения на основе генетических алгоритмов для построения управляющих конечных

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

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

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

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

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

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

2. ВЫБОР И ОБОСНОВАНИЕ ОПТИМАЛЬНОГО ВАРИАНТА НАПРАВЛЕНИЯ

ИССЛЕДОВАНИЙ

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

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

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

Методы, которые разрабатываются в рамках работ по настоящему Государственному контракту, будут основаны на принципах «обучения на примерах» и лишены указанных недостатков.

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

1. Выбрано и обосновано оптимальное направление проведения исследований.

3. ПЛАН ПРОВЕДЕНИЯ ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

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

3.1. ПЛАН ПРОВЕДЕНИЯ ПЕРВОГО ЭТАПА ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

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

• разработка, программная реализация и экспериментальное исследование метода машинного обучения на основе генетических алгоритмов для построения управляющих конечных автоматов Мили на основе тестовых примеров (09.11.2009 – 22.11.2009):

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

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

• научно-технический отчет, содержащий аналитический обзор и описание указанного

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

ИССЛЕДОВАНИЙ

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

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

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

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

o апробация метода на примере построения управляющего автомата для системы • обобщение и оценка результатов исследований (01.05.2010 – 15.07.2010):

o оценка полноты решения задачи и достижения поставленных целей;

o сопоставление и обобщение результатов анализа научно-информационных источников и теоретических и экспериментальных исследований;

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

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

• одна статья в журналах из перечня ВАК;

• свидетельство о регистрации программы для ЭВМ;

• протоколы экспериментов;

• рекомендации по использованию результатов НИР при создании научнообразовательных курсов;

• научно-технический отчет.

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

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

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

4. РАЗРАБОТКА, ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНОЕ

ИССЛЕДОВАНИЕ МЕТОДА МАШИННОГО ОБУЧЕНИЯ НА ОСНОВЕ

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

КОНЕЧНЫХ АВТОМАТОВ МИЛИ НА ОСНОВЕ ТЕСТОВЫХ ПРИМЕРОВ

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

При применении парадигмы автоматного программирования для реализации сущности со сложным поведением выделяется система управления и объект управления. На начальном этапе проектирования программы выделяются события (e1, e2, …), входные переменные (x1, x2, …) и выходные воздействия (z1, z2, …). После этого проектирование программы может идти разными путями. Один из них состоит в написании сценария работы программы, по которому далее эвристически строится автомат. Пример построения автомата таким способом приведен в работе [15].

Другой подход, который практически не применяется для построения автоматных программ, но достаточно широко распространен при разработке традиционных программ, состоит в разработке на основе тестов (test-driven development) [4]. При применении этого метода процесс написания кода на языке программирования идет параллельно с написанием тестов для программы. При этом добавление функциональности в программу выполняется только после того, как создан тест для проверки этой функциональности. Таким образом, функциональность программы описывается набором тестов для нее.

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

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

4.2. ОПИСАНИЕ ПРЕДЛАГАЕМОГО МЕТОДА

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

• список входных переменных;

• список выходных воздействий;

• набор тестов Tests, каждый из которых содержит последовательность Input[i] событий, поступающих на вход конечному автомату, и соответствующую ей эталонную последовательность Answer[i] выходных воздействий.

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

Поэтому естественно в набор тестов включать все префиксы теста.

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

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

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

Отметим, что в общем случае функция переходов и функция действий зависят не только от события, поступившего на вход автомату, но и от значений входных переменных, которые, как правило, имеют логический тип. При построении автомата вручную, например с использованием инструментального средства UniMod [7], переходы обычно помечаются не только событиями, но и так называемыми «охранными условиями» (guard conditions) – логическими формулами, которые задают ограничения на значения входных переменных.

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

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

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

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

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

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

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

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

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

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

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

• изменение начального состояния;

• изменение описания каждого из переходов;

• удаление или добавление перехода для каждого из состояний.

Pages: |

| 2 |

Главная >> Программы

[ СКАЧАТЬ ОРИГИНАЛ ДОКУМЕНТА .pdf ]

Похожие работы:

«УО Мозырский государственный педагогический университет им. И.П. Шамякина УТВЕРЖДАЮ Проректор по учебной работе Н.А.Лебедев (дата) УЧЕБНАЯ ПРОГРАММА ПО ДИСЦИПЛИНЕ ИСТОРИЯ КОРРЕКЦИОННОЙ ПЕДАГОГИКИ (наименование дисциплины) специальности переподготовки 1 – 03 03 71– Логопедия (квалификация: учитель-логопед) (код и наименование специальности и квалификации переподготовки) в соответствии с типовым учебным планом переподготовки, утвержденным (дата утверждения, регистрационный номер) Мозырь,...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФГБОУ ВПО Уральский государственный экономический университет УТВЕРЖДАЮ Проректор по учебной работе Л. М. Капустина _2011 г. МОЛОДЁЖНАЯ ЭКОНОМИЧЕСКАЯ И СОЦИАЛЬНАЯ ПОЛИТИКА Программа учебной дисциплины направление подготовки 080100 Экономика магистерская программа Экономическая и социальная политика Екатеринбург 2011 1. ЦЕЛИ ОСВОЕНИЯ УЧЕБНОЙ ДИСЦИПЛИНЫ Цель дисциплины - формирование у студентов всестороннего целостного представления о...»

«Рыбалка в двух океанах и приключения в Коста-Рике класса люкс, 13 дней / 3 дней рыбалки на карибском и 3 дня на тихоокеанском побережьях. Вариант международного авиаперелета Авиакомпанией Иберия, с транзитной остановкой в Мадриде. IB3143 30APR DMEMAD 0655 1015 IB6313 30APR MADSJO 1140 1440 IB6314 12MAY SJOMAD 1640 1110 +1 IB3142 13MAY MADDME 1015 2310 Подробная программа День 1 Сан Хосе, Коста-Рика 0655 Вылет из Москвы в Сан Хосе, с пересадкой в Мадриде. IB3143 30APR DMEMAD 0655 1015 IB6313...»

«Муниципальное бюджетное общеобразовательное учреждение Средняя общеобразовательная школа № 26 СОГЛАСОВАНО УТВЕРЖДАЮ Председатель Управляющего Совета Директор МБОУ СОШ№26 /Авдеева Т.А./ /Панова Т.В./ Протокол № 1 педагогического совета от 30 августа 2013 Приказ № 95/2 от 25.09.2013 ОБРАЗОВАТЕЛЬНАЯ ПРОГРАММА 2013 – 2014 (4 - 11 классы) Г. МЫТИЩИ Информационно-аналитические данные об образовательном учреждении. 1. Краткая характеристика социального окружения школы и характер его влияния на...»

«МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования Саратовский государственный аграрный университет имени Н.И. Вавилова Утверждаю Директор филиала И.А. Кучеренко 30 августа 2013 г. РАБОЧАЯ ПРОГРАММА ПРОФЕССИОНАЛЬНОГО МОДУЛЯ Профессиональный Выполнение работ по рабочей профессии модуль 18545 Слесарь по ремонту сельскохозяйственных машин и оборудования Специальность 110809.51 Механизация...»

«Государственное образовательное учреждение высшего профессионального образования Московской области Международный университет природы, общества и человека Дубна (университет Дубна) УТВЕРЖДАЮ проректор по учебной работе С.В. Моржухина __2010 г. ПРОГРАММА ДИСЦИПЛИНЫ МЕТРОЛОГИЯ, СТАНДАРТИЗАЦИЯ И СЕРТИФИКАЦИЯ (наименование дисциплины) по направлению 230105 Программное обеспечение вычислительной техники и автоматизированных систем Форма обучения: очная Уровень подготовки: бакалавр (выбрать нужное)...»

«1 2 Рабочая программа составлена на основании: 1. Государственного образовательного стандарта высшего профессионального образования по специальности или направлению подготовки дипломированного специалиста 660300 Агроинженерия утверждённой 05.04.2000 г. (регистрационный номер 312 с/дс). 2. Примерной программы дисциплины Сельскохозяйственные машины утвержденной 27 июня 2001 г. 3. Рабочего учебного плана по специальности 110301.65 Сельскохозяйственные машины, утверждённого 22 апреля 2013 г.,...»

«1 Выпуск № 12 /2013 СОДЕРЖАНИЕ НОМЕРА КОЛОНКА ГЛАВНОГО РЕДАКТОРА.. 3 ДНЕВНИК СОБЫТИЙ:.. 4-13 Аптека – 2013: Презентация Николаевой Н.М. Изменения в законодательстве в сфере обращения ЛС.. 4-7 ААУ СоюзФарма и НП Аптечная Гильдия Нормативное регулирование и ненормативная практика аптечной деятельности.. 8-11 Региональная конференция Ассоциации для аптек Москвы и Московской области.. 11-13 ААУ СОЮЗФАРМА ИНФОРМИРУЕТ:.. 14 Заседание в Общественной палате РФ.. 14 ОБРАЗОВАТЕЛЬНЫЕ ПРОГРАММЫ ААУ...»

«Приложение № 6 к Отчету о деятельности по программе Молодежная секция РНК СИГРЭ за 2013 год Аналитический обзор Молодежные программы в российской электроэнергетике в 2013 году Содержание Введение Молодежное крыло РНК МИРЭС 1. 2. Молодежная программа Инвестируя в будущее в рамках выставки и конференции Russia Power 2013 Благотворительный фонд Надежная смена 3. Молодежная политика ОАО ФСК ЕЭС 4. Международная ассоциация молодых атомщиков 5. Международная энергетическая премия Глобальная энергия...»

«1. Аннотация Программа дисциплины Общая и неорганическая химия разработана на основе программы, рекомендованной УМС по химии УМО по классическому университесткому образованию (авторы программы профессор Л.И. Мартыненко, доцент А.Н. Григорьев, Отв. редактор академик Ю.Д. Третьяков) Тип курса - цикл ОПД, федеральный компонент Год обучения - 1 Семестр – 1, 2 Выписка из ГОС ВПО Общая химия: основы химической термодинамики, растворы, кинетика и механизм химических реакций, строение атома,...»

«1 2 3 РАЗДЕЛ 1. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ ДИСЦИПЛИНЫ Рабочая программа учебной дисциплины Отраслевые социологические теории: социология молодежи составлена на основе следующих документов: - федеральные государственные требования к структуре основной профессиональной образовательной программы послевузовского профессионального образования (аспирантура), утвержденные приказом Минобрнауки РФ от 16.03.2011 г. №1365; - паспорта специальностей научных работников (социологические науки),...»

«ЮГО-ЗАПАДНОЕ ОКРУЖНОЕ УПРАВЛЕНИЕ ОБРАЗОВАНИЯ ДЕПАРТАМЕНТА ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ СРЕДНЯЯ ОБЩЕОБРАЗОВАТЕЛЬНАЯ ШКОЛА № 1372 С УГЛУБЛЁННЫМ ИЗУЧЕНИЕМ ОБЛАСТИ ЗНАНИЙ ИСКУССТВО РАБОЧАЯ ПРОГРАММА по изобразительному искусству в начальной школе НА 2013/14 УЧЕБНЫЙ ГОД искусство ПредметИзобразительное Учитель Гапич Ирина Александровна, Демиденко Александра Евгеньевна, Клещенков Максим Сергеевич_ Количество часов: Всего _135 часов, в неделю1_ час....»

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

«Российский государственный педагогический университет имени А. И. Герцена Психолого-педагогический факультет ПРОГРАММА вступительного испытания в бакалавриат по дисциплине ОБЩАЯ ПЕДАГОГИКА по направлению 44.03.02 Психолого-педагогическое образование квалификация (степень) академический бакалавр Санкт-Петербург 2014 СТРУКТУРА ВСТУПИТЕЛЬНОГО ИСПЫТАНИЯ 1. Цель и задачи вступительного испытания. Экзамен проводится с целью выявления готовности абитуриентов (студентов педагогических колледжей) к...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ БРАТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ; утверж Проректор по научной работе / f /У _ П.М. Огар Ий: 2012 г. — Цьф ||||! | РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ,- г'0РЛ% О?-' ^ fij У /д ОД. А. 04Л ИСТОРИЯ СТРАН ЦЕНТРАЛЬНОЙ ИТОГО-ВОСТОЧНОЙ АЗИИ В НОВЕЙШЕЕ ВРЕМЯ основной образовательной программы послевузовского профессионального образования...»

«ПРОГРАММА СОЦИАЛЬНО-ЭКОНОМИЧЕСКОГО РАЗВИТИЯ ИРКУТСКОЙ ОБЛАСТИ НА 2011 – 2015 ГГ. ПРОГРАММА СОЦИАЛЬНО-ЭКОНОМИЧЕСКОГО РАЗВИТИЯ ИРКУТСКОЙ ОБЛАСТИ НА 2011-2015 ГОДЫ 1 ПРОГРАММА СОЦИАЛЬНО-ЭКОНОМИЧЕСКОГО РАЗВИТИЯ ИРКУТСКОЙ ОБЛАСТИ НА 2011 – 2015 ГГ. ПАСПОРТ ПРОГРАММЫ СОЦИАЛЬНО-ЭКОНОМИЧЕСКОГО РАЗВИТИЯ ИРКУТСКОЙ ОБЛАСТИ НА 2011-2015 ГОДЫ Наименование Программа социально-экономического развития Иркутской программы области на период 2011-2015 гг. Основание для Распоряжение губернатора Иркутской области...»

«МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ МАТЕМАТИКА Программа вступительного экзамена Mосква 2014 ББК 22.1я729 М 34 МАТЕМАТИКА Программа вступительного экзамена Составители: Е.Е. Тимонина А.И. Верченко Э.А. Применко Ответственный редактор А.А. Грушо Программа утверждена на заседании предметной комиссии РГГУ 21 января 2014 г. ©...»

«УТВЕРЖДАЮ Ректор ТОГУ С.Н. Иванченко 201 ОСНОВНАЯ ОБРАЗОВАТЕЛЬНАЯ ПРОГРАММА ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ Направление подготовки 270800 Строительство Приказ № 54 от 18 января 2010 г Профили подготовки Автомобильные дороги Водоснабжение и водоотведение Городское строительство и хозяйство Автодорожные мосты и тоннели Производство строительных материалов, изделий и конструкций Промышленное и гражданское строительство Теплогазоснабжение и вентиляция Квалификация (степень) бакалавр Форма...»

«Мониторинг СМИ в период избирательной кампании по всеобщим местным выборам 5 июня 2011 года Отчет №1 18 апреля – 1 мая 2011 года Отчет подготовлен в рамках проекта „Мониторинг СМИ в предвыборной кампании” при финансовой поддержке Восточно-Европейского фонда за счет ресурсов, предоставленных Шведским агентством развития и международного сотрудничества (Sida/Asdi) и Министерством иностранных дел Дании (DANIDA). Выраженные в нем мнения принадлежат авторам и не обязательно отражают точку зрения...»

«МИНОБРНАУКИ РОССИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ (ФГБОУ ВПО ВГУ) УТВЕРЖДАЮ Заведующий кафедрой финансового права _ Сенцова М. В. 02.09.2013 г. РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ Б.3.Б.14 ФИНАНСОВОЕ ПРАВО 1. Шифр и наименование направления подготовки / специальности: 030900 Юриспруденция 2. Профиль подготовки: Государственное право 3. Квалификация (степень) выпускника: бакалавр 4....»

наверх

<< ГЛАВНАЯ | КОНТАКТЫ

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)

ПРИНЯТО: УТВЕРЖДЕНО:

НАУЧНО-ТЕХНИЧЕСКИЙ

НАУЧНООТЧЕТ

СПИСОК ОСНОВНЫХ ИСПОЛНИТЕЛЕЙ

РЕФЕРАТ

ОГЛАВЛЕНИЕ

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

2. ВЫБОР И ОБОСНОВАНИЕ ОПТИМАЛЬНОГО ВАРИАНТА НАПРАВЛЕНИЯ

3. ПЛАН ПРОВЕДЕНИЯ ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

3.1. ПЛАН ПРОВЕДЕНИЯ ПЕРВОГО ЭТАПА ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

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

4. РАЗРАБОТКА, ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНОЕ

ИССЛЕДОВАНИЕ МЕТОДА МАШИННОГО ОБУЧЕНИЯ НА ОСНОВЕ

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

ВВЕДЕНИЕ

1. АНАЛИТИЧЕСКИЙ ОБЗОР

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

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

1.3. СОВМЕСТНОЕ ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ И ВЕРИФИКАЦИИ

1.4. СРАВНЕНИЕ РАССМОТРЕННЫХ АЛГОРИТМОВ МАШИННОГО ОБУЧЕНИЯ

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

2. ВЫБОР И ОБОСНОВАНИЕ ОПТИМАЛЬНОГО ВАРИАНТА НАПРАВЛЕНИЯ

ИССЛЕДОВАНИЙ

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

3. ПЛАН ПРОВЕДЕНИЯ ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

3.1. ПЛАН ПРОВЕДЕНИЯ ПЕРВОГО ЭТАПА ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

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

ИССЛЕДОВАНИЙ

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

4. РАЗРАБОТКА, ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНОЕ

ИССЛЕДОВАНИЕ МЕТОДА МАШИННОГО ОБУЧЕНИЯ НА ОСНОВЕ

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

КОНЕЧНЫХ АВТОМАТОВ МИЛИ НА ОСНОВЕ ТЕСТОВЫХ ПРИМЕРОВ

4.2. ОПИСАНИЕ ПРЕДЛАГАЕМОГО МЕТОДА

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА (Авторефераты, диссертации, методички, учебные программы, монографии)

ПРИНЯТО: УТВЕРЖДЕНО:

НАУЧНО-ТЕХНИЧЕСКИЙ

НАУЧНООТЧЕТ

СПИСОК ОСНОВНЫХ ИСПОЛНИТЕЛЕЙ

РЕФЕРАТ

ОГЛАВЛЕНИЕ

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

2. ВЫБОР И ОБОСНОВАНИЕ ОПТИМАЛЬНОГО ВАРИАНТА НАПРАВЛЕНИЯ

3. ПЛАН ПРОВЕДЕНИЯ ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

3.1. ПЛАН ПРОВЕДЕНИЯ ПЕРВОГО ЭТАПА ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

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

4. РАЗРАБОТКА, ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНОЕ

ИССЛЕДОВАНИЕ МЕТОДА МАШИННОГО ОБУЧЕНИЯ НА ОСНОВЕ

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

ВВЕДЕНИЕ

1. АНАЛИТИЧЕСКИЙ ОБЗОР

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

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

1.3. СОВМЕСТНОЕ ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ И ВЕРИФИКАЦИИ

1.4. СРАВНЕНИЕ РАССМОТРЕННЫХ АЛГОРИТМОВ МАШИННОГО ОБУЧЕНИЯ

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

2. ВЫБОР И ОБОСНОВАНИЕ ОПТИМАЛЬНОГО ВАРИАНТА НАПРАВЛЕНИЯ

ИССЛЕДОВАНИЙ

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

3. ПЛАН ПРОВЕДЕНИЯ ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

3.1. ПЛАН ПРОВЕДЕНИЯ ПЕРВОГО ЭТАПА ТЕОРЕТИЧЕСКИХ И ЭКСПЕРИМЕНТАЛЬНЫХ

ИССЛЕДОВАНИЙ

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

ИССЛЕДОВАНИЙ

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

4. РАЗРАБОТКА, ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ЭКСПЕРИМЕНТАЛЬНОЕ

ИССЛЕДОВАНИЕ МЕТОДА МАШИННОГО ОБУЧЕНИЯ НА ОСНОВЕ

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

КОНЕЧНЫХ АВТОМАТОВ МИЛИ НА ОСНОВЕ ТЕСТОВЫХ ПРИМЕРОВ

4.2. ОПИСАНИЕ ПРЕДЛАГАЕМОГО МЕТОДА

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА
(Авторефераты, диссертации, методички, учебные программы, монографии)