Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов




Скачать 417.18 Kb.
НазваниеЦарев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов
страница1/11
Дата18.01.2013
Размер417.18 Kb.
ТипДокументы
  1   2   3   4   5   6   7   8   9   10   11


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

Факультет информационных технологий и программирования

Кафедра компьютерных технологий


Царев Федор Николаевич


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


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


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

2007



Глава 1.Оглавление


Глава 1. Оглавление 4

Введение 5

Глава 2. Общие концепции генетического и автоматного программирования 8

Глава 3. Задача об «Умном муравье» 15

Глава 4. Задача «Летающие тарелки» 25

Заключение 55

Список источников 57


Введение


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

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

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

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

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

Рассматриваемые в работе задачи выбраны не случайно. Задача об «Умном муравье» достаточно хорошо изучена. Сравнение результатов применения разработанного в настоящей работе алгоритма генетического программирования позволяет установить его эффективность – с его помощью построен решающий эту задачу автомат, содержащий меньшее, чем известные ранее автоматы, количество состояний. Задача-игра «Летающие тарелки» предлагалась на заочном туре Всесибирской олимпиады по информатике 2005 года. Она представляет собой пример задачи, в которой необходимо построить несколько автоматов, управляющих агентами. Кроме этого, существуют построенные вручную решения этой задачи, с которыми можно сравнить построенное автоматически.

В заключение работы анализируются ее результаты, и приводится ряд открытых вопросов и направлений для дальнейших исследований в этой области.
  1   2   3   4   5   6   7   8   9   10   11

Похожие:

Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов icon1 разработка метода представления управляющего конечного автомата с помощью линейных бинарных графов
Разработка методов совместного применения генетического и автоматного программирования для построения систем управления беспилотными...
Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов iconРазработка методов совместного применения генетического и автоматного программирования
Санкт-Петербургский государственный университет информационных технологий, механики и оптики
Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов iconА. А. Давыдов, Д. О. Соколов, Ф. Н. Царев, А. А. Шалыто
В докладе описывается виртуальная лаборатория, предназначенная для обучения генетическому программированию для построения управляющих...
Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов icon1. Цели и задачи учебной дисциплины, ее место в учебном процессе
Целью дисциплины является изучение элементов теории конечных автоматов, основных этапов абстрактного и структурного синтеза конечных...
Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов iconТема работы: «Применение деревьев принятия решений для прогнозирования результатов футбольных матчей»
Научный Царёв Фёдор Николаевич, преподаватель факультатива «Олимпиадное программирование» в Гимназии №261
Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов icon1. Наименование дисциплины
Исследование характеристик конечных автоматов. Описание функционирования вероятностного конечного автомата, конечных автоматов Мили...
Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов iconРазработка и исследование алгоритмов синтеза конечных автоматов для автономных эволюционных аппаратных средств

Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов iconМетод представления функции переходов деревьями решений для генерации автоматов с помощью генетического программирования*
Санкт-Петербургский государственный университет информационных технологий, механики и оптики
Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов iconФедеральное агентство по образованию
Целью данной дисциплины является ознакомление студентов технических специальностей с арифметическими и логическими основами проектирования...
Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов iconФедеральное агентство по образованию
Целью данной дисциплины является ознакомление студентов технических специальностей с арифметическими и логическими основами проектирования...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница