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

3.4Построение автомата, содержащего семь состояний Описанный генетический алгоритм позволил построить автомат, решающий задачу об «Умном муравье» и содержащий меньше состояний, чем другие известные автоматы для этой задачи. Отметим, что действие «Ничего не делать» бесполезно и, в некотором смысле, подобно ε-переходам в конечных недетерминированных автоматах, используемых для распознания регулярных языков. Поэтому оно может быть устранено из автоматов алгоритмом, подобным алгоритму ε-замыкания [29]. Таким образом, можно считать, что в автоматах используются только три действия (идти вперед, повернуть направо, повернуть налево). С помощью описанного алгоритма генетического программирования был построен автомат из семи состояний (рис. 5), решающий задачу об «Умном муравье» за 193 хода. Этот автомат был построен за 130000 поколений, при этом было проанализировано 160 миллионов автоматов. Процесс построения занял порядка четырех часов на компьютере с процессором Intel Celeron M 1.5 GHz. Рис. 5. Автомат из семи состояний, построенный алгоритмом генетического программирования Отметим, что при повторном запуске алгоритма после анализа 230 миллионов автоматов, содержащих семь состояний, также был найден автомат, решающий задачу об «Умном муравье». Построить автомат, содержащий менее семи состояний не удалось. Наилучший автомат из пяти состояний, который удалось построить, позволяет муравью съесть 83 единицы еды, из шести состояний – 85 единиц еды. Также с помощью разработанного алгоритма было построено семейство автоматов, решающих задачу об «Умном муравье» и содержащих восемь состояний. В табл. 1 приведена краткая сводка применения описанного алгоритма к построению автоматов из восьми состояний. Таблица 1. Результаты применения алгоритма для построения автомата из восьми состояний Размер поколения Доля особей, переходящих в следующее поколение Время до «малой» мутации поколения Время до «большой» мутации поколения Количество вычислений функции приспособленности 1000 0.3 100 150 1370300 1000 0.4 100 150 1235700 1000 0.5 100 150 4055200 1000 0.4 100 150 2992300 1000 0.4 100 150 1418300 1000 0.4 100 150 189400 1000 0.4 100 150 220300 1000 0.3 100 150 1948400 2000 0.5 100 150 1540000 Отметим также, что вопрос о существовании автоматов, позволяющих муравью съесть всю еду и содержащих при этом менее семи состояний, остается открытым.

Похожие:

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