WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     || 2 | 3 | 4 | 5 |   ...   | 10 |

«Ю. Д. Бедный Применение генетических алгоритмов для генерации автоматов при построении модели максимального правдоподобия и в задачах управления Магистерская диссертация ...»

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

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

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

Ю. Д. Бедный

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

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

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

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

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

Санкт-Петербург 2008 Оглавление ВВЕДЕНИЕ

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

ПОСТРОЕНИЯ АВТОМАТОВ

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

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

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

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

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

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

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

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

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

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

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

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



Pages:     || 2 | 3 | 4 | 5 |   ...   | 10 |
 



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

«ОТЧЕТ об итогах научной и производственной деятельности ЗА 2010 г. Директор Сиптиц С.О. Ученый секретарь Овчинцева Л.А. Главный бухгалтер _ Солодова М.М. Москва — 2010 СОДЕРЖАНИЕ ВВЕДЕНИЕ 2 1. РЕЗУЛЬТАТЫ НАУЧНЫХ ИССЛЕДОВАНИЙ -3 2. НАУЧНО-ОРГАНИЗАЦИОННАЯ ДЕЯТЕЛЬНОСТЬ 49 3. МАТЕРИАЛЬНО-ТЕХНИЧЕСКАЯ БАЗА И ЕЕ СОВЕРШЕНСТВОВАНИЕ - 51 4. НАУЧНЫЙ ПОТЕНЦИАЛ И ПОДГОТОВКА НАУЧНЫХ КАДРОВ 52 5. МЕЖДУНАРОДНОЕ НАУЧНО-ТЕХНИЧЕСКОЕ СОТРУДНИЧЕСТВО - 52 6. ПРОПАГАНДА И ОСВОЕНИЕ НАУЧНО-ТЕХНИЧЕСКИХ РАЗРАБОТОК -...»

«КОНЦЕПЦИЯ ВРЕМЕНИ В ХИМИИ Проблема “химического” времени В современном естествознании время - одно из ключевых понятий, образующих минимальный словарь (Б. Рассел) любой науки. Конструкции времени как результаты его теоретического освоения в физике, биологии, геологии, географии достаточно хорошо изучены 1, чего нельзя сказать о понятии времени в химии. Складывается впечатление, что в ряду теорий, включающих время в свое предметное поле, отсутствуют химические теории, - по крайней мере, их...»

«Кафедра международной экономики Ярош О.Б. Методические материалы по курсу Европейская экономика для студентов 5 курса дневной формы обучения специальности 7.05010301- международная экономика, отрасли знаний 0305 Экономика и предпринимательство СИМФЕРОПОЛЬ 2011 Рекомендовано к печати решением кафедры международной экономики (протокол № 1 от 09.09.2011 г). Рекомендовано к печати учебно-методическим советом ТНУ (протокол №1 от 6.10.2011 г). 2 СОДЕРЖАНИЕ Тема 1. Европейская экономика, основные...»

«Стратегические перспективы: ведущие державы, Казахстан и центральноазиатский узел Под редакцией Роберта Легволда Мечи и орала: экономика национальной безопасности Беларуси и Украины Под редакцией Роберта Легволда и Селесты А. Уолландер Книжная серия исследований Американской академии по проблемам глобальной безопасности издается Американской академией гумани тарных и точных наук и выпускается издательством Массачусетского технологического института. По всем вопросам, связанным с этой се рией,...»

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

«Примечание РЦПИ! Порядок введения в действие Кодекса РК см. ст. 245. Оглавление Настоящий Кодекс регулирует бюджетные, межбюджетные отношения, устанавливает основные положения, принципы и механизмы функционирования бюджетной системы, образования и использования бюджетных средств, а также формирование и использование Национального фонда Республики Казахстан. ОБЩАЯ ЧАСТЬ РАЗДЕЛ 1. БЮДЖЕТНАЯ СИСТЕМА Глава 1. ОБЩИЕ ПОЛОЖЕНИЯ Статья 1. Бюджетное законодательство Республики Казахстан 1. Бюджетное...»

«МЕДИАТЕКА Класс Фирма-изготовитель Название Краткое описание Кол-во (возрастная группа) ЕГЭ Планета Физика. Механика Презентации с готовыми чертежами к задачам 9-11 кл. 1 (подготовка к ГИА и ЕГЭ 9класс) Новый диск Русский язык Готовимся к ЕГЭ. Версия 2.0 10-11 кл. 2 Сдаем ЕГЭ по русскому языку Варианты. Тренажеры. Нормативные документы. 10-11 кл. 1С 1 Кирилл и Мефодий Виртуальная школа Кирилла Репетитор по географии Кирилла и Мефодия. 10-11 кл. 1 и Мефодия (подготовка к ЕГЭ) Математика...»

«СОДЕРЖАНИЕ ВВЕДЕНИЕ.. ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ИННОВАТИКИ. 1.1.Сущность и роль инноваций в социально-экономическом развитии.. 1.2 Механизм появления инноваций в сценариях социаль-экономического развития.. 1.3.Классификация инноваций. 1.4.Формирование теории инноваций. 1.5.Закономерности развития инновационных процессов. ГЛАВА 2. СУБЪЕКТЫ ИННОВАЦИОННОЙ ДЕЯТЕЛЬНОСТИ. 2.1.Общие положения о субъектах инновационной деятельности.. 2.2.Управление инновационно-активной организацией. 2.3.Анализ...»

«ТЕХНИЧЕСКИЕ СРЕДСТВА ЖЕЛЕЗНЫХ ДОРОГ Утверждено Департаментом кадров и учебных заведений МПС России в качестве учебника для студентов техникумов и колледжей железнодорожного транспорта Москва 2003 1 УДК 629.4+0.75+621.331+0.75+656.2.073.28(0.75) ББК 39.22 Г 948 Гундорова Е.П. Технические средства железных дорог: Учебник для техникумов и колледжей ж.-д. транспорта. — Г 948 М.: Маршрут, 2003. – 496 с. ISBN 5-89035-078-1 Дано описание основных устройств вагонов, электровозов, тепловозов; приведены...»

«Approved on: 24 January 2005 ПРОГРАММА ПО БОРЬБЕ С ОПУСТЫНИВАНИЕМ В РЕСПУБЛИКЕ КАЗАХСТАН НА 2005-2015 ГОДЫ 2 Астана, 2005 Стр. СОДЕРЖАНИЕ 1. Паспорт Программы 3 2. Введение 5 3. Анализ современного состояния проблемы 6 4. Цель и задачи Программы 12 5. Основные направления и механизм реализации Программы 13 5.1. Формирование политики устойчивого использования природных ресурсов 14 5.2. Разработка социально-экономических аспектов сохранения природных ресурсов и борьбы с опустыниванием 15 5.3....»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

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