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

Скачать 417.12 Kb.

Название	Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов
страница	1/11
Дата публикации	07.07.2013
Размер	417.12 Kb.
Тип	Документы

100-bal.ru > Информатика > Документы

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

Добавить документ в свой блог или на сайт

Похожие:

	Разработка методов совместного применения генетического и автоматного программирования Комитета по скалолазанию, тренерского совета и спортсменов-скалолазов, членов сборной команды Украины		Разработка методов совместного применения генетического и автоматного программирования Учебник предназначен для студентов технических вузов по специальности 010100 математика. Работа студентов по этому учебнику позволит...
	Развитие формализма метода подвижных клеточных автоматов для изучения...		Методическая разработка по внедрению проектного метода на уроках географии Данная методическая разработка предполагает проведение уроков по дисциплине География с использованием элементов проектного метода...
	Разработка метода и адаптивных алгоритмов компрессии с гарантированной... Работа выполнена на кафедре «Математического обеспечения и применения эвм» Технологического института Южного федерального университета...		Министерство образования Российской Федерации Санкт Петербургский... Задачи курса: Изучить основные математические результаты и методы, лежащие в основе метода конечных элементов и других вариационных...
	План: Общие понятия об алгоритме Способы записи алгоритмов История... Так, чтобы решить полное квадратное уравнение, необходимо знать конкретные значения коэффициентов а, b и с (начальные условия). В...		Электронные образовательные ресурсы для учащихся Лев Николаевич Толстой (Война и Мир), Федор Михайлович Достоевский (Преступление и наказание, Идиот). Большое собрание стихотворений...
	Разработка урока Автор: Целюрик Юлия Петровна Тема: «Знакомство со... Используемые программные приложения из пакета спо: Среда программирования Скретч (Scratch)		Прогнозирование трещиностойкости бетона на основе метода конечных элементов Реальное строение материала и особенности его поведения под нагрузкой отражено в структурных теориях прочности. Однако практическое...
	Урок по алгебре и математическому анализу в 10 классе по теме «Решение... Обучающая цель: Изучить возможности применения метода интервалов для решения тригонометрических неравенств		26. Мельников Федор Михайлович Мельников Федор Михайлович родился 31 июля 1942 года в дер. Остречиха Сандовского района Калининской области
	Программное обеспечение для решения задач линейного программирования... Линейными ограничениями. Основой программы служит алгоритм симплекс метода для неограниченного числа условий и переменных. В алгоритме...		Студента 617 группы фртк давидюка Дмитрия Сергеевича Научный к т.... Поэтому, когда мы измеряем биологические потенциалы, мы видим результат синхронной деятельности совокупности клеток мозга, и эта...
	Доклад ронжина Андрея Леонидовича по диссертационной работе «Разработка... «Разработка адаптивного метода робастного понимания слитной речи на основе интегральной обработки данных», представленной на соискание...		Методическая разработка «Одномерные массивы» на языке программирования... «Одномерные массивы» на языке программирования pascal в теории и практике школьного курса «Информатика и икт»/ Методическая разработка....

Школьные материалы