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

Скачать 417.12 Kb.

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

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

1 2 3 4 5 6 7 8 9 10 11

Несколько задач, в которых генетические алгоритмы применяются для построения автоматов

Приведем список таких задач:

итерированная дилемма заключенного (iterated prisoner’s dilemma) [4, 20];
задача классификации плотности для клеточных автоматов (density classification task for cellular automata) [21, 22];
задача синхронизации для клеточных автоматов (synchronization task for cellular automata) [23];
задача упорядочивания для клеточных автоматов (ordering task for cellular automata) [24];
задача о «Флибах» [25, 26];
задача об «Умном муравье» (artificial ant problem) [3, 27, 28] – одна из задач, рассматриваемых в настоящей работе.

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

3.1Постановка задачи

Приведем описание задачи об «Умном муравье» [27]. Игра происходит на поверхности тора размером 32 на 32 клетки (рис. 3). В некоторых клетках (обозначены на рис. 3 черным цветом) находится еда. Она расположена вдоль некоторой ломаной, но не во всех ее клетках. Клетки ломаной, в которых нет еды, обозначены серым цветом. Белые клетки не содержат еду и не принадлежат ломаной. Всего на поле 89 клеток с едой. Отметим, что рассматриваемое игровое поле называется John-Muir Trail [27].

Рис. 3. Игровое поле

В клетке, помеченной меткой «Start», в начале игры находится муравей. Он занимает одну клетку и смотрит в одном из четырех направлений (север, юг, запад, восток). В начале игры муравей смотрит на восток.

Муравей умеет определять находится ли непосредственно перед ним еда. За один игровой ход муравей может совершить одно из четырех действий:

сделать шаг вперед, съедая еду, если она там находится;
повернуть налево;
повернуть направо;
ничего не делать.

Съеденная муравьем еда не восполняется, муравей жив на протяжении всей игры, еда не является необходимым ресурсом для его жизни. Ломаная не случайна, а строго фиксирована. Муравей может ходить по любым клеткам поля.

Игра длится 200 ходов, на каждом из которых муравей совершает одно из четырех действий. По истечении 200 ходов подсчитывается количество еды, съеденной муравьем. Это значение и есть результат игры.

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

Один из способов описания поведения муравья – конечный автомат с действиями на переходах (автомат Мили), у которого есть одна входная переменная логического типа (находится ли еда перед муравьем), а множество выходных воздействий состоит из четырех упомянутых выше элементов.

Например, эвристически построенный автомат из [27], граф переходов которого изображен на рис. 4, описывает поведение муравья, который съедает 81 единицу еды за 200 ходов, а всю еду – за 314 ходов.

Рис. 4. Эвристически построенный автомат с пятью состояниями

Поясним используемые на рис. 4 обозначения. Пометки на переходах имеют формат условие / действие. Условия обозначаются следующим образом:

F – перед муравьем есть еда;

!F – перед муравьем нет еды.

Действия обозначаются следующим образом:

M – «Сделать шаг вперед»;

L – «Повернуть налево»;

R – «Повернуть направо»;

N – «Ничего не делать».

1 2 3 4 5 6 7 8 9 10 11

Похожие:

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

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