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

Скачать 0.78 Mb.

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

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

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

Выводы по главе 1

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

Глава 2.Метод представления автоматов с помощью конечных распознавателей

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

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

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

2.1.Задача «Умный муравей–3»

В разделе 1.3.2 приведено описание задачи «Умный муравей». Постановка задачи «Умный муравей–3», предложенной в работе [1], содержит несколько существенных отличий.

Во-первых, расширена область обзора муравья – вместо одной клетки он видит восемь. Таким образом, множество значений входных переменных содержит 2⁸ = 256 элементов. На Рис. 19. изображена область обзора муравья (клетка, в которой находится муравей, обозначена серым цветом).

Область видимости муравья

Во-вторых, расположение еды на поле не фиксировано, а генерируется случайным образом. При этом вероятность того, что яблоко окажется в некоторой клетке, одинакова для всех клеток поля и равна μ.

В этом случае число яблок, съеденных муравьем за 200 ходов, есть случайная величина ξ (определяемая муравьем) на дискретном множестве элементарных исходов Ω – множестве расположений еды – битовых матриц 32 x 32. Каждому исходу ω_i, содержащему kединиц поставим в соответствие вероятность p(ω_i) = μ^k(1-μ)ⁿ^-^k, где n = 32 x× 32.

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

2.2.Решение задачи без применения конечных автоматов

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

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

Результаты вычислительных экспериментов для параметра μ, равного 0.01, 0.02, 0.03 и 0.04, приведены в табл. Таблица 2..

Результаты вычислительного эксперимента для решения задачи «Умный муравей–3» без применения конечных автоматов
Значение параметра μ	Результат
0.01	2.8125
0.02	7.823
0.03	14.119
0.04	20.343

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

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