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

Скачать 37.44 Kb.

Название	Разработка методов совместного применения генетического и автоматного программирования
Дата публикации	03.09.2013
Размер	37.44 Kb.
Тип	Документы

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

УДК 004.4’242
Разработка методов совместного применения генетического и автоматного программирования

Ф. Н. ЦАРЕВ, гр. 6538, кафедра КТ
Санкт-Петербургский государственный университет информационных технологий, механики и оптики
Руководитель – заведующий кафедрой ТП, докт. техн. наук, профессор А. А. Шалыто
Генетические алгоритмы [1, 2, 3] являются одним из современных и быстро развивающихся направлений в искусственном интеллекте [4]. Генетическое программирование [5] – разновидность генетических алгоритмов, в которой вместо низкоуровневого представления объектов в виде битовых строк используется высокоуровневое представление: деревья разбора программ, диаграммы переходов конечных автоматов и т.д. Автоматное программирование [6] – парадигма программирования, при использовании которой программу предлагается строить в виде совокупности автоматизированных объектов управления, каждый из которых содержит систему управления (взаимодействующие конечные автоматы) и объект управления.

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

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

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

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

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

совместное применение метода построения автоматов на основе тестов и метода сокращенных таблиц переходов;
совместное применение метода построения автоматов на основе тестов и метода представления автоматов деревьями решений;
изучение возможности применения методов верификации на моделях (Model checking) [7] при вычислении функции приспособленности.

По теме работы сделан доклад на VI межвузовской конференции молодых ученых (14–17 апреля 2009 года, СПбГУ ИТМО) и на научно-практической конференции студентов, аспирантов, молодых ученых и специалистов «Интегрированные модели, мягкие вычисления, вероятностные системы и комплексы программ в искусственном интеллекте» (ИММВИИ-2009, 26–27 мая 2009 года, г. Коломна). Кроме этого, материалы докладов по теме диссертации приняты к публикации в труды XII Международной конференции по мягким вычислениям и измерениям (SCM 2009, 25–27 июня 2009 года, СПбГЭТУ (ЛЭТИ) им. В. И. Ульянова-Ленина, Санкт-Петербург, Россия) и в труды Международной научной конференции «Компьютерные науки и информационные технологии» (Саратовский государственный университет имени Н. Г. Чернышевского, 1–4 июля 2009 года, Саратов).

Литература

Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы. М.: Физматлит. 2006.
Chambers L. Practical Handbook of Genetic Algorithms. Complex Coding Systems. Volumes I. II, III. CRC Press, 1999.
Mitchell M. An Introduction to Genetic Algorithms. MA: The MIT Press, 1996.
Рассел С., Норвиг П. Искусственный интеллект. Современный подход. М.: Вильямс. 2006.
Koza J. Genetic programming. On the Programming of Computers by Means of Natural Selection. MA: The MIT Press, 1998.
Поликарпова Н. И., Шалыто А. А. Автоматное программирование. СПб: Питер, 2009.
Кларк Э., Грамберг О., Пелед Д. Верификация моделей программ: Model Checking. М.: Издательство МЦНМО. 2002.

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

Похожие:

	Разработка методов совместного применения генетического и автоматного программирования Учебник предназначен для студентов технических вузов по специальности 010100 математика. Работа студентов по этому учебнику позволит...		Царев Федор Николаевич Разработка метода совместного применения генетического... История развития географической науки и роль выдающих ученых в формировании системы географических знаний
	Рабочая программа по дисциплине с 3 «Технологии и методы программирования» Цель преподавания дисциплины: Целью изучения дисциплины «Технологии и методы программирования» является изучение современных технологий...		Программа учебной дисциплинЫ «Микропроцессорная техника» Целью дисциплины является формирование знаний студентов по вопросам теории, принципам построения и функционирования основных технических...
	Программа учебной дисциплинЫ «программируемые логические контроллеры» Целью дисциплины является формирование знаний студентов по вопросам теории, принципам построения и функционирования основных технических...		Разработка урока Автор: Целюрик Юлия Петровна Тема: «Знакомство со... Используемые программные приложения из пакета спо: Среда программирования Скретч (Scratch)
	Рабочая программа учебной дисциплины «Проектирование web-страниц» является изучение теоретических основ и принципов прикладного программирования на примере построения...		Методическая разработка «Одномерные массивы» на языке программирования... «Одномерные массивы» на языке программирования pascal в теории и практике школьного курса «Информатика и икт»/ Методическая разработка....
	Отчет о научно-исследовательской работе разработка методов макроэкономической... «Разработка методов макроэкономической оценки расходов федерального бюджета», шифр темы 0111-03-09		Рабочая программа дисциплины «программирование и алгоритмизация» Автоматизация технологических процессов и производств”, с основами алгоритмизации, основными понятиями программирования, несколькими...
	Разработка методов информационной защиты в экономических информационных... Динамическая эквивалентность как способ преодоления различий в национальных картинах мира		Перечень научно-исследовательских, опытно-конструкторских и технологических... Изучение закономерностей дифференцировки стволовых и прогениторных клеток из различных источников в условиях in vitro и in vivo и...
	Отчет о научно-исследовательской работе Целью работы является разработка технических решений повышения эффективности совместного использования вычислительных ресурсов центров...		Сулейманов галем альбкаевич разработка мер борьбы с основными гельминтозами... Разработка методов государственного регулирования процессов рождаемости, смертности, брачности и разводимости
	Тема : 2 Разработка занятия по системе объектно-ориентированного программирования Scratch		Тема урока: среда программирования qbasic цели урока Программы пишут программисты на разных языках программирования. Одним из языков программирования является язык qbasic

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