авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:   || 2 |
-- [ Страница 1 ] --

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

Ю. Д. Бедный

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

генерации

автоматов при построении модели максимального

правдоподобия и в задачах управления

Магистерская диссертация

Научный руководитель – докт. техн. наук, профессор А. А. Шалыто

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

2008 Оглавление ВВЕДЕНИЕ..................................................................................................................3 ГЛАВА 1. ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ ПОСТРОЕНИЯ АВТОМАТОВ..................................................................5 1.1. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ.......................................................................... 1.2. ИТЕРИРОВАННАЯ ДИЛЕММА УЗНИКА (ТЕОРИЯ ИГР)....................................... 1.3. ВЫБОР ПРАЙМЕРА ДЛЯ ПОЛИМЕРАЗНОЙ ЦЕПНОЙ РЕАКЦИИ (БИОЛОГИЯ)...... 1.4. ИСКУССТВЕННАЯ ЭТОЛОГИЯ (ЗООЛОГИЯ)................................................... 1.5. ЗАДАЧА ОПТИМИЗАЦИИ............................................................................... 1.6. УПРАВЛЕНИЕ ЧЕЛОВЕКОПОДНЫМ РОБОТОМ (РОБОТЕХНИКА)..................... ВЫВОДЫ ПО ГЛАВЕ 1.......................................................................................... ГЛАВА 2. ГЕНЕРАЦИЯ АВТОМАТОВ ПРИ ПОСТРОЕНИИ МОДЕЛИ МАКСИМАЛЬНОГО ПРАВДОПОДОБИЯ.......................................... 2.1. ИДЕЙНОЕ ОПИСАНИЕ ЗАДАЧИ...................................................................... 2.1.1. Пример............................................................................................. 2.2. ПОСТАНОВКА ЗАДАЧИ................................................................................. 2.3. СКРЫТЫЕ МАРКОВСКИЕ МОДЕЛИ................................................................. 2.3.1. Использование алгоритма Баума-Велша..................................... 2.4. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ....................................................................... 2.4.1. Пространство поиска..................................................................... 2.4.2. Структура и параметры алгоритма............................................... 2.4.3. Структура хромосомы................................................................... 2.4.4. Генетические операции................................................................. 2.4.5. Функция приспособленности........................................................ 2.4.6. Генерация последовательностей входных воздействий............ 2.4.7. Результаты эксперимента.............................................................. 2.5. ЗНАЧЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ.................................................... 2.6. СРАВНЕНИЕ С АЛГОРИТМОМ СЛУЧАЙНОГО ПОИСКА................................... 2.7. ОБОБЩЕНИЕ НА ВЕРОЯТНОСТНЫЕ АВТОМАТЫ............................................ ВЫВОДЫ ПО ГЛАВЕ 2.......................................................................................... ГЛАВА 3. РЕШЕНИЕ ЗАДАЧ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ................. 3.1. ПОСТАНОВКА ЗАДАЧИ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ В ОБЩЕМ ВИДЕ....... 3.1.1. Описание задачи управления........................................................ 3.1.2. Формальная постановка задачи управления............................... 3.1.3. Проблемы, возникающие при решении задачи управления...... 3.1.4. Автоматный подход и его недостатки......................................... 3.1.5. Предлагаемый метод...................................................................... 3.1.6. Общая идея...................................................................................... 3.1.7. Представление решения задачи управления в виде хромосомы................................................................................ 3.1.8. Функция приспособленности, генетические операции.............. 3.2. СОЗДАНИЕ СИСТЕМЫ УПРАВЛЕНИЯ ТАНКОМ В ИГРЕ ROBOCODE................. 3.2.1. Обзор................................................................................................ 3.2.2. Постановка задачи.......................................................................... 3.2.3. Построение системы управления без применения автоматов... 3.2.4. Представление в виде хромосомы................................................ 3.2.5. Функция приспособленности........................................................ 3.2.6. Генетические операции................................................................. 3.2.7. Эксперименты................................................................................. 3.2.8. Автоматный подход....................................................................... 3.2.9. Программная поддержка метода.................................................. ВЫВОДЫ ПО ГЛАВЕ 3.......................................................................................... ЗАКЛЮЧЕНИЕ......................................................................................................... НЕКОТОРЫЕ ОТКРЫТЫЕ ВОПРОСЫ И ЗАДАЧИ........................................... ПУБЛИКАЦИИ........................................................................................................ ЛИТЕРАТУРА.......................................................................................................... ПРИЛОЖЕНИЕ........................................................................................................ ВВЕДЕНИЕ Генетические алгоритмы являются одним из бурно развивающихся и перспективных направлений в искусственном интеллекте и программировании.



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

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

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

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

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

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

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

Третья глава посвящена решению задач оптимального управления.

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

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

ГЛАВА 1. ПРИМЕНЕНИЕ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ ПОСТРОЕНИЯ АВТОМАТОВ В начале данной главы приводится краткое описание генетических алгоритмов [1, 2]. Далее рассмотривается ряд задач, в которых применение генетических алгоритмов для автоматизированного построения автоматов [3] позволило улучшить существующие решения или получить решения, сравнимые по эффективности с существующими. Кроме того, следует принять во внимание, что трудозатраты при подходе, базирующемся на генетических алгоритмах, как правило, значительно меньше, чем при эвристическом построении автоматов. Важно отметить и то обстоятельство, что в некоторых случаях автоматизировано построенные автоматы, могут быть изучены, для выявления структуры «хороших» решений задачи.

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

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

В 1966 г. Л. Фогель, А. Оуэнс и М. Уолш предложили схему эволюции автоматов, решающих задачи прогноза. В 1975 г. вышла книга Дж. Холланда “Адаптация в естественных и искусственных системах”, в которой был предложен генетический алгоритм. Эти работы заложили основы эволюционного программирования.

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

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

Более подробное описание генетических алгоритмов и их разновидностей может быть найдено в работах [1 – 5].

Перейдем к рассмотрению задач.

1.2. Итерированная дилемма узника (теория игр) В теории игр известна следующая бескоалиционная матричная игра с ненулевой суммой, обычно называемая «Дилемма узника» («Prisoner’s dilemma»). Двое преступников пойманы и допрашиваются в отдельных камерах. Срок тюремного заключения, который получит каждый из них, зависит как от его показаний, так и от показаний соучастника. В табл. приведены сроки заключения в зависимости от решений, принятых игроками – их стратегий.

Таблица 1. Матрица игры «Дилемма узника»

Сознаться Отрицать Сознаться 3, 3 0, Отрицать 5, 0 1, В данной игре предательство (стратегия «сознаться») строго доминирует над сотрудничеством (стратегией «отрицать»). Единственное равновесие в игре (по Нэшу) – признание обоих преступников, что приведет ситуации (3, 3). При любой зафиксированной стратегии соучастника преступнику выгодно предать.

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

В 1980-ом году Роберт Аксельрод рассмотрел вариант данной игры, названный им «Iterated Prisoner’s Dilemma», в котором между игроками проводится несколько партий и каждый игрок помнит историю трех предыдущих игр. Аксельрод организовал турниры, на которые программу мог прислать любой желающий. В первом турнире участвовало 14 программ, во втором 63. Результат программы в турнире равнялся количеству очков, набранных против остальных участников. Проведенные турниры показали [6], что «жадные» стратегии (предпочитающие сознаться, что являлось оптимальной стратегией в исходной игре «Дилемма узника») имеют низкую результативность. Победителем же обоих турниров стала простая программа, названная Tit for Tat, состоящая всего из 4 строк на языке BASIC, присланная Анатолием Рапопортом, которая первым ходом выбирала стратегию «отрицать», а дальше делала тоже, что оппонент на предыдущем ходу.

В 1987 году Аксельрод изучил возможность эволюционного порождения стратегий с помощью генетических алгоритмов. Стратегия программы кодировалась битовой строкой из 70 символов. В результате была получена стратегия, дающая лучший чуть результат, чем Tit for Tat при фиксированных соперниках. В дальнейшем Аксельрод провел исследование, в котором среда (оппоненты) также эволюционировала. Было замечено, что в ходе первых двух десятков поколений преобладали «жадные» стратегии (сознаться), однако в ходе дальнейшей эволюции они уступали место «кооперирующимся»

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

В 1991 году Д. Фогель провел ряд экспериментов, в которых эволюционное программирование использовалось для вывода автоматов, кодирующих стратегии игроков [7]. На рис. 1 приведен пример автомата, кодирующего стратегию игрока. На данном рисунке действию стратегии «отрицать» соответствует символ C, а стратегии «сознаться» символ D.

Стартовое состояние (состояние 1 на рисунке) выделено стандартным образом.

Каждый переход помечен дугой вида (P1, P2)/A. Здесь P1 – действие (стратегия) игрока на предыдущем ходу (C либо D), P2 – действие оппонента на предыдущем ходу, A – действие игрока на текущем ходу. Стратегия игрока на первом ходу обозначена пунктирной линией.

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

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

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

1.3. Выбор праймера для полимеразной цепной реакции (биология) В работе [8] авторы предлагают новой подход к решению известной в молекулярной биологии задачи выбора праймера для полимеразной цепной реакции (ПЦР) [9]. Естественным способом проверки пригодности праймера является попытка проведения ПЦР, однако в случае неудачи такая реакция приведет к существенным как материальным, так и временным затратам.

Поэтому желательно иметь способ определения пригодности праймера без проведения ПЦР. Существует ряд критериев пригодности праймера для ПЦР, перечисленных в [9], благодаря которым могут быть построены различные эвристические методы проверки праймера.

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

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

Особью генетического алгоритма является конечный автомат с выделенным начальным состоянием. В экспериментах, описываемых авторами, автоматы имеют 64 состояниями. Множество входных воздействий – множество всех подмножеств множества нуклеотидов {A, T, G, C}. Состояния автомата бывают трех типов: хорошие, плохие и промежуточные. На рис. приведен пример автомата описанного вида, с той лишь разницей, что для простоты изображено только пять состояний. Приведенные типы состояний обозначены символами «+», «–» и «?» для хороших, плохих и промежуточных типов состояний соответственно.

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

Рис. 2. Структура автомата, классифицирующего праймеры Для задания функции приспособленности f автомата A используется тренировочное множество T из 695 праймеров, 440 из которых подходят для проведения ПЦР, а 255 не подходят. Пусть p T – некоторый праймер, pi – префикс данного праймера длины i : len( pi ) = i, s ( pi ) – состояние, в которое переходит автомат A, принимая на вход префикс pi, g ( pi ) := g (type( s ( pi )), good (t ) ) – функция, возвращающая некоторое целое число в зависимости от type( s ( pi )) – типа состояния, в которое переходит автомат по префиксу pi, и good (t ) – является ли праймер подходящим для ПЦР. Функция g, используемая в эксперименте, приведена в табл. 2.

Таблица 2. Функция g Тип состояния Праймер + – ?

Подходящий 3 -4 Не подходящий -5 7 Данная функция означает прирост приспособленности при увеличении длины префикса и соответственно переходе автомата в следующее состояние.

len ( p ) При этом функция приспособленности автомата f ( A ) =.

g ( pi ) pT i = В экспериментах, проведенных авторами, использовалась популяция из 600 автоматов. Каждый автомат как особь популяции кодировался битовой строкой. Эволюционный алгоритм содержал 100 поколений. Начальное поколение автоматов создавалось случайным образом. После вычисления функции приспособленности на элементах популяции, она разбивалась случайным образом на группы по четыре особи (автомата). Две наименее приспособленные особи в каждой четверке заменялись особями, полученными в результате рекомбинации двух наиболее приспособленных особей. Для рекомбинации применялась двухточечная рекомбинация строк. После рекомбинации осуществлялась мутация, которая в каждом десятом случае изменяла начальное состояние, в 30% случаев изменяла переход по одному из входных воздействий и в 60% случаев изменяла тип состояния.





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

Для тестирования наилучшего из автоматов, полученных в первой, и во второй серии экспериментов было выбрано тестовое множество, состоящее из 880 подходящих и 471 не подходящих для ПЦР праймеров. Наилучший из автоматов, полученных в результате первой серии экспериментов, показал результаты, приведенные в табл. 3.

Таблица 3. Результаты классификации для наилучшего автомата первой серии экспериментов Результат классификация Праймер + – ?

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

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

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

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

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

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

Состояние локальной среды задается элементов из подмножества натуральных чисел S = [1..8] и определяется случайным процессом, то есть не может быть предсказано. Таким образом, единственным способом узнать состояние локальной среды другого симорга является коммуникация. Сообщение представляется элементом S. Для передачи сообщений между симоргами вводится общая среда, в которую симорг может передавать сообщения и из которой он может принимать сообщения других симоргов. Состояние общей среды (также элемент S) определяется только одним, последним, сообщением, из помещаемых в нее симоргами. Топология среды обитания симоргов приведена на рис. 3.

Рис. 3. Топология среды обитания симоргов Симорг задается простейшим конечным автоматом, содержащим всего одно состояние. Следовательно, у симоргов нет памяти. Множеством входных воздействий автомата является декартово произведение множества состояний общей среды и множества состояний локальной среды (S2). Определены два вида выходных воздействий автомата: сообщение (элемент S) и действие (также элемент S). Выходное воздействие первого вида изменяет состояние общей среды, а второго вида – обеспечивает «выживаемость» симорга. Оно должно быть как можно более «эффективно». Если действие симорга совпадает с состоянием общей среды (которое равно состоянию локальной среды последнего из симоргов отправивших сообщение), то «приз» (одно очко) получает как симорг последним отправивший сообщение, так и симорг, действие которого совпало с этим сообщением.

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

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

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

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

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

Исследователи определили размер популяции равным 100.

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

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

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

1.5. Задача оптимизации В работе [10] предлагается подход, позволяющий свести задачу глобальной оптимизации к задаче управления. Процесс нахождения глобального максимума сводится к перемещению по дискретизированному пространству поиска. Для управления перемещением вводится автомат Мили.

Постановка задачи такова: дано некоторое множество R 2, на нем определена функция : R+. Перемещение объекта управления по пространству описывается следующим образом: xt +1 = xt + f (( xt ), ( xt 1 )), где xt, функция f : R+ R+ {x | xt + x } – стратегия перемещения. Таким образом, перемещение на текущем шаге (в текущий момент времени) зависит от значений функции, исследованных на прошлом и позапрошлом шагах.

Пусть T N, T 1 – время, отведенное на перемещение по пространству.

( ( xT ) + 1) Задачей является максимизация функционала ( f, T ) = + max ( xt ) по max ( xt ) + 1 0 t T 0 t T стратегии перемещения f. Таким образом, производится поиск стратегий, которые с одной стороны должны искать глобальный максимум (этому требованию соответствует второе слагаемое в сумме), а с другой стороны к окончанию поиска текущее положение xT, должно быть «недалеко» от максимального из исследованных (этому требованию соответствует первое слагаемое). Константа в числителе первого слагаемого устанавливает приоритет между первым и вторым требованием.

Функция является функцией приспособленности для ( f, T ) генетического программирования. Стратегия перемещения f представляется в виде изображенном на рис. 5.

Рис. 5. Структура стратегии перемещения Sensor device (преобразователь) переводит непрерывные значения ( xt ), ( xt 1 ) из R+ во множество X дискретных входных воздействий автомата Мили A, реализуя функцию : R+2 X. Данная функция наряду с автоматом A будет выводиться генетическим алгоритмом.

Actor device (устройство перемещения) переводит выходные воздействия автомата в команду по перемещению объекта управления по двумерной сетке, дискретизирующей. Устройство перемещения хранит информацию о текущем и предыдущем положении устройства управления xt и xt 1, а также вектор перемещения d t, который определяет как направление перемещения, так и величину шага, которая может быть равна шагу сетки, либо удвоенному шагу сетки. В зависимости от выходных воздействий автомата устройство перемещения оставляет устройство управления на месте xt +1 = xt, либо перемещает его в одно из четырех ортогональных направлений, при этом шаг перемещения может остаться неизменным, либо удвоиться, либо уменьшиться вдвое. Определяется множество возможных перемещений Y = {F, B, L, R, S,2 F, 1 F }, элементы которого соответствует перемещению вперед, назад, влево, вправо, вперед с удвоением шага, вперед с уменьшением шага вдвое.

(автомат) задается множеством входных Finite state machine A воздействий X, действий Y, состояний S, начальным состоянием s1 S, функцией переходов автомата : X S S и функцией действий автомата : X S Y.

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

cond ::= 0(arith,{rule},{rule}) rule ::= (state,output) | (state,state) | cond arith ::= arith + arith | arith - arith | arith arith | arith % arith | A | B | c R ::= s S state ::= y Y output Дерево параметризуется константами A, B, которые при вычислении заменяются на ( xt ), ( xt 1 ). Корнем дерева является cond выражение. Пример дерева выражений приведен на рис. 6. Для наглядности иллюстрации в данном дереве не отображена функция. Результатом вычисления выражения приведенного вида после подстановки значений ( xt ), ( xt 1 ) являются конечное множество переходов (state,state) и конечное множество выходных воздействий (state,output), которые определяют функции,. Если в множестве переходов (выходных воздействий) присутствуют два различных перехода (действия) из одного состояния (на рис. 6 при A B в множестве переходов есть два перехода из состояния 0: в состояние 1 и в состояние 2) выбирается самый левый из них (в приведенном примере будет выбран переход (0, 1)).

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

Используются три дополнительные генетические операции над вершинами, являющимися списком инструкции (данные вершины обозначены символом {} на рис. 6): удаление поддерева, добавление поддерева, изменение порядка на поддеревьях.

Эксперименты проводились на трех различных функциях, приведенных ниже. Параметр n принимал значение равное двум, v = 10, T = 50, а константы µ i были выбраны таким образом, чтобы i [0, 1]. Пространством поиска являлось множество := [0, 10]2. Автоматы содержали десять состояний.

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

n 1 ( x) := 50 µ1 xi sin 50 xi i = ( ) n 2 ( x) := µ 2 1 xi2 10 cos(xi ) + i = n ( ) +( xi 1) 3 ( x) := µ 3 100 xi + 1 1 x 5 25 i i = Графики функций Ошибка! Объект не может быть создан из кодов полей редактирования. и Ошибка! Объект не может быть создан из кодов полей редактирования. приведены на рис. 7.

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

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

1.6. Управление человекоподным роботом (роботехника) Создание человекоподобных роботов одно из наиболее актуальных и перспективных направлений, как науки, так и технологии. Роботы такого типа могли бы выполнять различные задачи в нашем мире, «приспособленном под человека». Одной из задач роботехники является создание двуногих роботов, способных передвигаться подобно человеку.

В работе [12] предлагается использовать традиционное генетическое программирование для эволюционного построения автомата, осуществляющего управление движением робота Elvina. Данный робот изображен на рис. 8.

Рис. 8. Человекоподобный робот Elvina Каждая из ног робота Elvina имеет 5 степеней свободы (одна из которых пассивная). Голова туловище и руки имеют одну степень свободы. Таким образом, в сумме у робота 14 степеней свободы. Двигатели, изменяющие положение частей тела (ног, рук, головы, туловища), управляются контроллером, выдающим одно из 256 значений 0..255 определяющих положение управляемой части тела. Для управления ходьбой необходимо задать последовательность состояний робота, осуществляющую один цикл ходьбы.

Неподвижное состояние робота задается вектором J P = [ j1, j 2,..., j k ], где k – число его степеней свободы. Тогда пространство W всех состояний робота (включая те, в которых он находится во время перемещения частей тела) есть линейная оболочка векторов J 1, J 2,... J j, где j = 256 k. Некоторые из этих состояний не являются статически устойчивыми – переход в такое состояние приводит к падению работа. Выделяют подпространство G векторов из W, определяющих статически устойчивые положения робота. Для осуществления одного цикла ходьбы достаточно задать m устойчивых состояний P1, P2,..., Pm, в которых последовательно будет находиться робот в процессе движения.

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

Для построения искомой функции используется традиционное генетическое программирование. Вводятся 2k регистров, половина из которых соответствует входным данным j1, j2,..., jk, а половина – выходным j1, j2,..., jk.

Как входные, так и выходные регистры изначально инициализируются значениями j1, j2,..., jk. Особь алгоритма представляет собой набор инструкций, записанных последовательно, осуществляющих операции над содержимым регистров. Каждая инструкция – четверка (k1, k2, op, res). Первые два параметра – номера регистров;

третий параметр – одна из пяти функций, аргументами которой являются первые два параметра;

последний параметр – выходной регистр, в который следует запись результат операции. После выполнения последней инструкции значения выходных регистров копируются в j1, j2,..., jk. Авторы определили пять функций двух аргументов: ADD (сложение), SUB (вычитание), MUL (умножение), DIV (безопасное деление), SINE (синус первого аргумента, второй аргумент отбрасывается).

Функция приспособленности вычислялась путем моделирования поведения робота в течение, примерно, 20 секунд. Записывались начальные координаты частей тела и конечные, затем значение функции принималось h hstart равным fitness = W [1 ] (d left + d right ). Здесь start – отношение начальной hstop hstop высоты положения робота к конечной, а d left + d right – отклонение робота от прямолинейной траектории, W – некоторый постоянный коэффициент. Таким образом, предпочтение отдавалось роботам, способным поддерживать высоту положения (тем более не падать) и как можно меньше отклоняющимся от прямолинейной траектории движения.

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

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

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

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

ГЛАВА 2. ГЕНЕРАЦИЯ АВТОМАТОВ ПРИ ПОСТРОЕНИИ МОДЕЛИ МАКСИМАЛЬНОГО ПРАВДОПОДОБИЯ В настоящей главе проводятся исследования одного класса скрытых марковских моделей [13] – «сильно детерминированных». Выясняется, что для построения модели максимального правдоподобия для таких моделей традиционно используемый алгоритм Баума-Велша [14] не применим. В то же время, использование генетических алгоритмов для выбора начальных параметров позволяет значительно повысить эффективность алгоритма Баума Велша. В действительности демонстрируется, что ключевая роль при построении модели максимального правдоподобия отводится генетическим алгоритмам.

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

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

2.1. Идейное описание задачи В последнее время всё шире применяется автоматное программирование [3]. Так как автоматные программы обычно используются во встроенных системах, то важно обеспечить корректное поведение автоматов.

Это может быть достигнуто за счет верификации [15] и тестирования.

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

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

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

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

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

2.1.1. Пример Приведем пример, поясняющий сказанное (рис. 10).

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

Автомат принимает вход – последовательность входных воздействий e1,e2...,en. Непрерывными дугами изображены переходы, которые должны выполняться на данном входе, а пунктирной дугой – неучтенный переход (выполняемый на первом шаге). Последовательность состояний автомата при выполнении неучтенного перехода 0-3-4-0-1, в то время как ожидаемая (априорная) последовательность состояний 0-1-2-3-4. При этом выход автомата 0,0,1,0,0, в то время как ожидаемый выход 0,0,1,0,1 (последние символы данных последовательностей отличаются).

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

Однако это же справедливо и для перехода (3,0) при последовательности состояний Действительно, последовательность выходных 0-1-2-3-0.

воздействий в обоих случаях имеет вид: 0,0,1,0,0 (рис. 11).

a) б) Рис. 11. Восстановление матрицы переходов Для того чтобы определить, какой из этих переходов более вероятен, рассмотрим ещё один шаг работы автомата, генерирующего за первые пять шагов последовательность выходных воздействий 0,0,1,0,0. Автомат, изображенный на рис. 11 слева, после пятого шага находится в состоянии один, и на шестом шаге переходит в состояние два (0-3-4-0-1-2). Автомат, изображенный справа – после пятого шага находится в состоянии ноль, а на шестом шаге переходит в состояние один (0-3-4-0-1-1). Таким образом, первый автомат на выходе формирует последовательность 0,0,1,0,0,1, в то время как второй – 0,0,1,0,0,0. Следовательно, по шестому элементу выходной последовательности можно сделать вывод о том, добавление какого перехода (3,0) или (0,3) не приведет к модели реального автомата. Если шестой элемент оказался равен нулю, то модель, изображенная на рис. 11, a, не соответствует наблюдаемому выходу, в другом случае – поведение автомата не может описываться моделью, приведенной на рис. 11, б.

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

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

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

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

Обозначим число состояний автомата за N, а матрицу переходов размера N2 за A = (a ij ), где aij – вероятность перехода из состояния i в состояние j. При этом N a для i должно выполняться = 1 – сумма вероятностей переходов из ij j = каждого состояния в другие равна единице.

Пусть, находясь в каждом из состояний, наблюдается некоторое выходное воздействие из конечного алфавита мощности M. Определим матрицу B = (bij ) размера NM, где bij – вероятность наблюдать выходное M b воздействие j, перейдя в состояние i. При этом для i справедливо =1 – ij j = сумма вероятностей получения каждого из выходных воздействий равна единице. Для детерминированных автоматов каждому состоянию i соответствует единственное j, такое что bij = 1.

Пусть начальное состояние автомата имеет номер s. Зададим вектор = ( is ) T, s-ый элемент которого равен единице, а остальные нулю. Определим модель, соответствующую наблюдаемому автомату, как = ( A, B, ).

На рис. 12 приведен пример модели некоторого автомата.

0 1 0. 0. 2 0. 0. 0 0. 4 0. Рис. 12. Пример модели автомата Эта модель = ( A, B, ) задаётся следующим образом:

0.01 0.976 0 0 0.014 0 0 1 0.003 0 0.097 0 0 1 0 0 0, B = 0, = 0.

A= 0 0 1 0 0 0 0.954 0 0 1 0.046 0.908 0.09 0.012 0 0 0 1 0 Выполним K раз Т шагов работы автомата. При этом получим множество последовательностей выходных воздействий O = { O (1), O ( 2),..., O ( K ) }. Каждая из них имеет вид: O (i ) = O1( i ) O2(i ) LOT( i ).

Пусть P(O ( i ) | ) – вероятность того, что автомат, который имеет модель, за T шагов генерирует последовательность выходных воздействий O (i ).

K P (O | ) = P (O (i ) | ) Тогда – вероятность наблюдения множества i = последовательностей (при некотором фиксированном порядке его O элементов).

Задача, рассматриваемая в настоящей главе, состоит в поиске матрицы переходов A, для которой P(O | ) принимает максимальное значение.

Другими словами, необходимо найти A = arg max P(O | ). Модель, полученная A при решении поставленной задачи (модель максимального правдоподобия), выявляет неучтенные переходы, а также показывает, как часто они используются на данном наборе последовательностей входных воздействий.

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

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

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

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

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

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

0 1 0 1 = ( A, B, ), A = 1 0, B = 1 0, =.

Заметим, что указанная модель легко строится человеком, однако при запуске алгоритма Баума-Велша с равномерными начальными параметрами 12 12 1 2, B =, = A = 1 1 1 1 2 2 2 на последовательности 1,0,1,0,1,0,1, она не будет получена. Результатом работы этого алгоритма является модель 0.43 0. 12, B =, =, A = 1 1 0.43 0.57 2 2 которая «улавливает» лишь то свойство последовательности, что единиц в ней чуть больше чем нулей, а правдоподобие данной модели будет малым.

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

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

2.4. Генетические алгоритмы Выбор начальных параметров с помощью генетических алгоритмов применялся при решении задачи предсказания вторичной структуры белков [20]. При этом в указанной статье определён вид матрицы переходов A.

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

Применим генетические алгоритмы для поиска этих переходов. Затем с помощью алгоритма Баума-Велша определим их вероятности.

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

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

Зафиксируем число состояний автомата и число выходных воздействий, положив соответственно N = 12 и M = 3. Данные параметры выбраны произвольным образом, исходя лишь из тех соображений, чтобы задача построения модели максимального правдоподобия не была слишком простой.

2.4.1. Пространство поиска Итак, предметом поиска являются матрицы размера 12 на 12, содержащих в каждой строке не более двух ненулевых элементов и единицу на диагонали соседней с главной (связанность графа) очень велико, а именно (N ) N = 7212 1.94 10 22. В задачах с таким большим пространством поиска, использование генетических алгоритмов, как правило, является более эффективным, нежели применение других методов. Например, в задаче классификации плотности для клеточных автоматов [17, 18, 19] пространство поиска содержало 2128 3.4 10 38 элементов, а наилучший из известных алгоритмов решения данной задачи – генетический алгоритм.

2.4.2. Структура и параметры алгоритма В экспериментах применялись стандартные генетические алгоритмы [1].

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

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

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

2.4.3. Структура хромосомы Хромосома задается массивом размера N на 2, каждый элемент которой – целое число от 0 до N – 1. На рис. 14 изображена структура некоторой хромосомы.

Рис. 14. Структура хромосомы Как видно из приведенного рисунка, по хромосоме непосредственно восстанавливаются состояния, в которые выполняются неучтенные переходы.

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

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

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

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

2.4.5. Функция приспособленности Приспособленность особи задающей некоторую модель f(x) x, = ( A, B, ), определим как f ( x) =, где знаменатель – логарифм ln P (O | ) вероятности пронаблюдать данные O в модели. Определенная таким образом, функция приспособленности пропорциональна вероятности P(O | ).

Можно попробовать определить функцию приспособленности просто как P (O | ). Однако в соответствии с введенным ранее определением, K P (O | ) = P (O (i ) | ), следовательно, необходимо вычислить P (O ( i ) | ) для i = каждого i, а затем перемножить полученные значения. Однако P(O (i ) | ) – очень малые по модулю величины и при их перемножении происходит потеря точности. Поэтому целесообразно перейти к логарифмам:

K K ln P (O | ) = ln P (O ( i ) | ) = ln P (O (i ) | ).

i = i = Для определения вероятности наблюдать некоторый выход при заданной модели P(O (i ) | ), используется «forward-backward procedure» алгоритм, который описан в работе [14]. Данный алгоритм, по сути, является алгоритмом динамического программирования.

2.4.6. Генерация последовательностей входных воздействий Построение модели, генерирующей набор = ( A, B, ) последовательностей выходных воздействий, выполнялось следующим образом. Фиксировалось число состояний автомата N, оно равнялось 12. Также задавалось число возможных выходных воздействий M, оно равнялось трём.

Для каждого состояния i ( i [0.. N 1] ) случайным образом выбирались два целых числа j1, j2 (в диапазоне от 0 до N – 1) и создавались неучтенные переходы (i, j1) и (i, j2), выполняемые с небольшими вероятностями (в экспериментах эти вероятности равнялись 0.05). Матрица B и вектор генерировались случайным образом, с соблюдением условия детерминированности.

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

2.4.7. Результаты эксперимента Для каждой исходной модели *, в результате работы генетического алгоритма получены модели, вероятность наблюдения (правдоподобие) которых примерно равна вероятности наблюдения исходной модели, оптимизированной алгоритмом Баума-Велша. В некоторых случаях правдоподобие найденных моделей даже превосходило правдоподобие оптимизированной исходной модели. В табл. 4 приведены значения логарифмов правдоподобия исходной модели до, и после ln P (O | * ) оптимизации алгоритмом Баума-Велша.

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

Таблица 5. Работа генетического алгоритма (процесс эволюции) Номер Максимальное Среднее значение Время, c.

поколения значение 1 2 858 3 780 4 746 5 725 6 705 7 694 8 685 9 682 10 681 11 680 12 680 13 677 14 677 15 676 16 Для наглядности результатов столбцы таблицы «Максимальное значение» и «Среднее значение» содержат логарифмы правдоподобия моделей ln P (O | ), а не их приспособленности f ( x) =. Числовые значения ln P (O | ) указанных столбцов округлены до ближайшего целого. Среднее значение приспособленности особей популяции на первом шаге положено равным, так как популяция содержала особь с нулевым правдоподобием (вследствие потери точности), а логарифм правдоподобия такой особи равен.

Из экспериментов (и в частности приведенной выше таблицы) можно сделать вывод о том, что генетические алгоритмы обладают высокой эффективностью при решении рассматриваемой задачи. Так в рассмотренном случае полученная модель имеет даже несколько большее правдоподобие ( ln P (O | ) = 675), чем оптимизированная исходная (678). Эффективность также подтверждается тем обстоятельством, что было выполнено всего вычислений функции приспособленности (1000 особей в 16 1000 = популяции, 16 поколений). Таким образом, исследована лишь очень малая часть пространства поиска, содержащего порядка 4.34 10 22 особей.

На рис. 15 приведен график, иллюстрирующий процесс эволюции популяции генетического алгоритма. Данный график построен по данным табл. 5.

- - Приспособленность - - - - - 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Номер поколения Максимальное значение приспособленности Рис. 15. Процесс эволюции популяции 2.5. Значение генетических алгоритмов Интересно было бы выяснить – меняет ли оптимизация модели алгоритмом Баума-Велша вид матрицы переходов (добавляя или удаляя дуги), или только подбирает значения вероятностей для переходов, выполняемых с ненулевой вероятностью (найденных генетическими алгоритмами)? В ходе экспериментов алгоритм Баума-Велша не изменял вид матрицы переходов.

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

2.6. Сравнение с алгоритмом случайного поиска Чтобы проверить, что рассматриваемая задача достаточно трудна и не может быть решена несложным способом, в работе также рассматривается более простой способ выбора начальных параметров для алгоритма Баума Велша, а именно – случайный поиск. В этом случае, для каждой строки матрицы A случайным образом (равномерно) выбираются два целых числа (от до N – 1). Для адекватного сравнения с генетическими алгоритмами, количество вычислений функции приспособленности (а значит и количество различных матриц рассмотренных при переборе) положено равным 100 000. В то же время, как указывалось ранее, пространство поиска содержит 4.34 10 элементов. Поэтому, были основания полагать, что перебор будет малоэффективен при решении данной задачи. Проведенные эксперименты это подтвердили. В табл. 6. приведены результаты работы алгоритмы случайного поиска. Столбец таблицы «Максимальное значение» содержит максимальное значение логарифма правдоподобия рассмотренных моделей.

Таблица 6. Работа генетического алгоритма (процесс эволюции) Количество просмотренных моделей Максимальное значение 812 10 939 40 250 59 432 100 000 Как видно из приведенной таблицы, перебрав сто тысяч моделей, алгоритм случайного поиска нашёл лишь модель с правдоподобием 824, что значительно меньше правдоподобия оптимизированной исходной модели (678). В то же время генетические алгоритмы сгенерировали модель с правдоподобием 675.

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

2.7. Обобщение на вероятностные автоматы В работе проводятся исследования применимости предлагаемого метода для выявления скрытых переходов в вероятностных автоматах с Такого рода автоматы детерминированной матрицей перехода.

рассматриваются, например, в [21] (Y-детерминированный автомат). В автоматах рассматриваемого типа выходное воздействие на переходе определяется вероятностно, в то время как состояние, в которое осуществляется переход, детерминировано.

Для простоты рассматривались автоматы, содержащие всего два выходных воздействия (M = 2). Количество состояний автомата N полагалось равным 15. Исходная модель порождала тренировочное множество O, содержащее 50 последовательностей выходных воздействий. Каждая из таких последовательностей имела длину T, равную 200. Матрица переходов генерировалась тем же алгоритмом, что и в эксперименте с детерминированным автоматом, описанным ранее.

При генерации матрицы выходных воздействий применялся следующий алгоритм. Для каждого состояния i, вероятность наблюдения выходного воздействия j выбиралась случайным образом по следующему закону: bij =| |, * где – с.в. распределенная по стандартном нормальному закону, ~ N (0, 1).

N Затем для каждого i производилась нормировка по всем j: bij = bij / bij. Таким * * j = N b образом, соблюдается условие = 1.

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

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

Таблица 7. Эффективность метода для вероятностных автоматов с детерминированной матрицей переходов Логарифм Модель правдоподобия Исходная Исходная оптимизированная Найденная алгоритмом случайного поиска Построенная предлагаемым методом Выводы по главе В настоящей главе проведен анализ эффективности алгоритма Баума Велша при построении моделей максимального правдоподобия для автоматов определенного вида – «сильно детерминированных». В результате анализа установлено, что в таких случаях алгоритм Баума-Велша неэффективен.

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

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

ГЛАВА 3. РЕШЕНИЕ ЗАДАЧ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ В данной главе предлагается новый метод решения задач оптимального управления. Предлагаемый метод основан на автоматном подходе. В то же время генетические алгоритмы используются для автоматического построения автоматов. Метод успешно опробован на практической задаче – построение системы управления танком для популярной компьютерной игры Robocode [27]. Результаты, которые показал танк в боях с соперниками, подтверждает эффективность предлагаемого метода.

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

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

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

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

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

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

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

На рис. 16 изображены некоторые параметры самолета: крен, тангаж и рыскание.

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

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

На рис. 17 приведена классификация параметров.

Рис. 17. Классификация параметров Итак, зафиксируем некоторое конечное множество существенных для задачи управления параметров. В процессе управления объектом параметры (как объекта, так и среды) изменяются во времени. Таким образом, в результате задачи управления получим фазовую кривую (с учетом дискретезации времени – ломаную) в пространстве всех возможных параметров. Будем полагать, что существует некоторая функция оценки качества решения задачи управления.

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

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

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

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

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

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

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

3.1.2. Формальная постановка задачи управления Задачи оптимального управления изучаются достаточно давно [22, 23].

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

Будем считать, что выделены n N существенных для задачи управления вещественных параметров (как объекта, так и среды). Обозначим множество значений, принимаемых данными параметрами, как Q = R n. Задача управления осуществляется на некотором временном интервале, для простоты поставим ему в соответствие отрезок [0, 1], разделенный на T N минимальных временных интервалов.

Тогда некоторая кривая в пространстве фазовых параметров – элемент множества QT. Обозначим функцию, оценивающую качество управления как g : Q T R. Данная функция принимает в качестве аргумента кривую фазового пространства и возвращает вещественное число. Обозначим фазовую кривую для момента времени t [1..T ] как t, при этом t Q t. тогда = T.

Зависимости, существующие между различными параметрами, определяются средой (как правило, физическими законами среды). Для их формального задания определим функцию h : Q Q. Эта функция по значению параметров в текущий момент времени определяет их значения в следующий момент времени. Будем считать, что сама h во времени не изменяется.

Пусть среди всех параметров существует m N, m n контролируемых параметров объекта. Под функцией управления будем понимать вектор f = [ f1, f 2,..., fT ]T, где координата вектора – функция f t : Q t R m, которая, принимая фазовую кривую для некоторого момента времени t (элемент множества Q t ), возвращает элемент множества R m – действие, которое предпринимается для управления объектом. В дальнейшем будет использовать термин «правило управления» применительно к ft.

Введем для удобства вектор функций F = [ F1, F2,..., FT ]T, Ft : Q t R n.

Координата вектора Ft, принимая на вход фазовую кривую для некоторого момента времени t, оставляет неконтролируемые параметры без изменения, а контролируемые изменяет по правилу, определяемому функцией ft.

Определим значения параметров в начальный момент времени как 0 R n. Тогда при фиксированной функции управления f фазовая кривая в пространстве параметров определяется однозначно следующим образом:

t = h( Ft (t 1 )), t = 1.. T.

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

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

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

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

Кроме того, из формальной постановки задачи следует, что необходимо найти вектор f = [ f1, f 2,..., fT ]T, что в общем случае является сложной задачей.

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



Pages:   || 2 |
 

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





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.