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

Скачать 0.78 Mb.

Название	Разработка методов совместного применения генетического и автоматного программирования
страница	2/12
Дата публикации	30.08.2013
Размер	0.78 Mb.
Тип	Задача

100-bal.ru > Информатика > Задача

1 2 3 4 5 6 7 8 9 ... 12

Глава 1.автоматное и генетическое программирование

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

1.1.Основные концепции автоматного программирования

В настоящем разделе описывается понятие «системы со сложным поведением» и приводятся основные идеи автоматного программирования.

1.1.1. Системы со сложным поведением

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

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

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

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

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

Одна из центральных идей автоматного программирования [17] состоит в отделении описания логики поведения (при каких условиях необходимо выполнить те или иные действия) от описания его семантики (собственно смысла каждого из действий). Кроме того, описание логики при автоматном подходе жестко структурировано. Эти два свойства делают автоматное описание сложного поведения ясным и удобным.

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

Если в системах логического управления [24] в качестве входных воздействий используются опрашиваемые программой двоичные входные переменные и предикаты, соответствующие определенным состояниям автоматов, взаимодействующих с рассматриваемым автоматом, то для «реактивных» систем это понятие расширено. Во-первых, в качестве входных переменных применяются любые подпрограммы (функции), возвращающие двоичные значения, а, во-вторых, введены события, не только обеспечивающие возможность выполнения переходов в автоматах, но и инициирующие запуск автоматов. События могут также инициировать реализацию выходных воздействий в случае, когда состояние автомата не изменяется.

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

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

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

В качестве примера системы со сложным поведением, управляемой автоматами, приведем систему управления дизель-генератором [18]. На Рис. 1. изображена схема взаимодействия автоматов, которые образуют эту систему.

Схема взаимодействия автоматов, управляющих системой со сложным поведением

1.1.2.Автоматное программирование

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

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

1 2 3 4 5 6 7 8 9 ... 12

Похожие:

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

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