Царев Федор Николаевич Разработка метода совместного применения генетического программирования и конечных автоматов
Скачать 417.12 Kb.
|
4.4Предлагаемый подход к решению задачи4.4.1Некоторые проблемы, возникающие при использовании генетического программирования для построения конечных автоматовГенетическое программирование наиболее эффективно в тех случаях, когда оптимизируемый объект (например, конечный автомат) имеет небольшой размер (небольшое количество состояний). В то же время, количество различных вариантов значений входных переменных может быть достаточно большим, а сами переменные могут быть не только логическими, но и числовыми. Например, в рассматриваемой задаче такие входные переменные, как скорость летающей тарелки или ее координаты являются вещественными входными переменными. Используемый для решения задачи об «Умном муравье» в настоящей работе алгоритм разработан для случая входных переменных логического типа. Для того, чтобы применять этот или аналогичный этому алгоритм, необходимо разработать способ перехода от произвольных входных переменных к логическим входным переменным (или хотя бы, к переменным, множество значений которых конечно и содержит небольшое количество элементов). Одним из вариантов решения этой задачи является введение соответствующих переменных вручную. Например, если исходно были две вещественные переменные x и y, то, например, можно ввести две новые логические переменные A := x > 100 и B := y < 200. Второй вариант решения состоит в том, чтобы разбить множество значений входных переменных на несколько областей и использовать в качестве значения входной переменной номер области, в которой лежат текущие значения входных переменных. Таким образом, необходимо будет перед тем, как подавать данные на вход автоматы, определять, в какой из областей лежит набор текущих значений входных переменных. Это – задача классификации. Если для ее решения применять автоматический классификатор (нейронная сеть, дерево принятия решений, и т.д.), то возникает идея настраивать этот классификатор совместно с автоматом, с которым он связан. В настоящей работе реализован второй подход. При этом в качестве классификатора используется искусственная нейронная сеть. Ее настройка и построение автомата производятся с помощью генетического программирования. 4.4.2Структура системы управления летающими тарелкамиСистема управления командой летающих тарелок состоит из двух систем управления летающей тарелкой. Система управления летающей тарелкой состоит из искусственной нейронной сети и конечного автомата. При этом, как и говорилось ранее, нейронная сеть используется для классификации значений вещественных входных переменных и выработки входных переменных для автомата, а автомат – для выработки выходных воздействий на летающую тарелку (рис. 13).  Рис. 13. Общая схема управляющей системы Используемая нейронная сеть имеет следующую структуру (рис. 14).  Рис. 14. Нейронная сеть Символами S на рис. 14 обозначены искусственные нейроны с сигмоидальной функцией активации, символом L – нейроны с пороговой функцией активации. Рядом с нейронами указаны их номера (они используются при описании операции скрещивания нейронных сетей). На каждый из трех выходов нейронной сети поступает число равное 0 или 1. Таким образом, существует восемь вариантов комбинаций выходных сигналов нейронной сети (000, 001, 010, 011, 100, 101, 110, 111). 4.4.3Алгоритм генетического программированияИспользуемый для настройки системы управления летающими тарелками алгоритм генетического программирования во многом аналогичен алгоритму, описанному в разд. 3.3. Отличия состоят в структуре особи, конкретных генетических операторах мутации и скрещивания и в функции приспособленности особи. 4.4.4Структура особиОсобь в описываемом алгоритме генетического программирования состоит из двух систем управления летающими тарелками. Каждая система управления летающими тарелками состоит из нейронной сети и конечного автомата. Описание нейронной сети состоит из четырех нейронов с сигмоидальной функцией активации и трех нейронов с пороговой функцией активации. Каждый из нейронов характеризуется порогом активации и весами связей, которые соединяют другие элементы сети с рассматриваемым. public abstract class Neuron { protected Neuron[] inputs; protected int inputsCnt; protected double[] w; } Описание конечного автомата состоит из номера начального состояния и описания состояний. Описания состояния состоит из описаний восьми переходов, соответствующих восьми вариантам выходных сигналов нейронной сети. Описание каждого перехода состоит из номера состояния, в которое ведет этот переход, и двух действий, которые выполняются при выборе этого перехода – изменения расхода топлива и изменения угла поворота аэродинамических рулей. Каждое из этих действий характеризуется одним вещественным числом – соответственно, новым расходом топлива и углом поворота аэродинамических рулей. public class Individual { protected PlateControlSystem[] pcs; } public class PlateControlSystem { private NeuralNet neuralNet; private Automaton automaton; } 4.4.5Операция мутацииМутация особи. При мутации особи с равной вероятностью мутирует либо одна система управления летающей тарелкой, либо вторая. Мутация системы управления летающей тарелкой. При мутации системы управления летающей тарелкой мутирует либо нейронная сеть, либо конечный автомат. Мутация нейронной сети. При мутации нейронной сети мутирует случайно и равновероятно выбирается один элемент (искусственный нейрон) сети и мутирует. Мутация элемента сети. При мутации элемента сети случайно выбирается один из весов связей, и к нему прибавляется случайное число из отрезка [-0.05; 0.05]. Кроме этого, с вероятностью 0.5 аналогичная операция производится с лимитом активации нейрона. Мутация конечного автомата. При мутации конечного автомата равной вероятностью производится либо изменение начального состояния, либо мутация случайно выбранного перехода. Мутация перехода. При мутации перехода с равной вероятностью происходит либо изменение номера состояния, в которое ведет переход, либо мутация одного из действий, связанных с переходом – может мутировать действие, связанное с изменением расхода топлива (прибавляется случайное число от -0.05 до 0.05) или с изменением угла поворота аэродинамических рулей (уменьшается или увеличивается на 5°). 4.4.6Операция скрещиванияОператор скрещивания получает на вход две особи (P1, P2) и выдает две особи (S1, S2). Пусть X – некоторая особь. Обозначим как X.s1 и X.s2 системы управления летающими тарелками, входящие в эту особь. Пусть s – некоторая система управления летающей тарелкой. Обозначим как s.ns входящую в нее нейронную сеть, а как s.a – входящий в нее автомат. Скрещивание особей. При скрещивании особей происходит скрещивание систем управления летающими тарелками: P1.s1 и P2.s1, P1.s2 и P2.s2. Обозначим системы, получившиеся в результате первого скрещивания как s11 и s12, а в результате второго – как s21 и s22. Тогда для особей-потомков будет справедливо: S1.s1 = s11, S1.s2 = s21, S2.s1 = s21, S2.s2 = s22. Скрещивание систем управления летающей тарелкой. При скрещивании систем управления летающей тарелкой s1 и s2 тарелкой происходит скрещивание автоматов s1.a и s2.a и скрещивание нейронных сетей s1.ns и s2.ns. Обозначим получающиеся в результате описанных скрещиваний автоматы как a1 и a2, а нейронные сети – как ns1 и ns2. В результате скрещивания системы управления летающей тарелкой получаются системы управления s3 и s4, содержащие следующие элементы: s3 содержит a1 и ns1, s4 – a2 и ns2. Скрещивание автоматов. Обозначим автоматы, поступающие на вход оператора скрещивания автоматов как A1 и A2. Начальное состояние некоторого автомата A обозначим как A.is, а переход из состояния i по значению входной переменной j как A(i, j). Обозначим автоматы, получающиеся в результате скрещивания как A3 и A4. Для их начальных состояний будет верно одно из двух:
Опишем переходы автоматов A3 и A4. Скрещивание производится отдельно для каждого состояния i и для каждого значения j входной переменной. В каждом случае возможно два равновероятных варианта:
Скрещивание нейронных сетей. Обозначим нейронные сети, поступающие на вход оператора скрещивания нейронных сетей как NS1 и NS2, а получающиеся в результате его применения – как NS3 и NS4. Опишем их устройство. Обозначим как NS(i) нейрон номер i сети NS (рис. 1). Для нейронов номер NS3(i) и NS4(i) возможны два варианта:
4.4.7Функция приспособленностиФункция приспособленности особи вычисляется с помощью соревнования описываемой особью системы управления командой летающих тарелок с некоторым набором известных систем управления командами. В качестве таких систем в настоящей работе используются системы, реализующие «агрессивную» и «простую» стратегию [17]. Проводилось по пять соревнований с каждой из стратегий при следующих параметрах летающих тарелок: с1 = 0.625; (1) c2 = 0.025; (2) c4 = 3.125; (3) Δt = 0.3 секунды; (4) L = 7. (5) Результатом вычисления функции приспособленности является сумма результатов системы управления командой летающих тарелок, описываемой особью во всех соревнованиях, к которой прибавлено количество побед, деленное на количество соревнований, увеличенное на единицу. |
Похожие:
 | Разработка методов совместного применения генетического и автоматного программирования Комитета по скалолазанию, тренерского совета и спортсменов-скалолазов, членов сборной команды Украины | | Разработка методов совместного применения генетического и автоматного программирования Учебник предназначен для студентов технических вузов по специальности 010100 математика. Работа студентов по этому учебнику позволит... |
| Развитие формализма метода подвижных клеточных автоматов для изучения... | | Методическая разработка по внедрению проектного метода на уроках географии Данная методическая разработка предполагает проведение уроков по дисциплине География с использованием элементов проектного метода... |
| Разработка метода и адаптивных алгоритмов компрессии с гарантированной... Работа выполнена на кафедре «Математического обеспечения и применения эвм» Технологического института Южного федерального университета... | | Министерство образования Российской Федерации Санкт Петербургский... Задачи курса: Изучить основные математические результаты и методы, лежащие в основе метода конечных элементов и других вариационных... |
| План: Общие понятия об алгоритме Способы записи алгоритмов История... Так, чтобы решить полное квадратное уравнение, необходимо знать конкретные значения коэффициентов а, b и с (начальные условия). В... |  | Электронные образовательные ресурсы для учащихся Лев Николаевич Толстой (Война и Мир), Федор Михайлович Достоевский (Преступление и наказание, Идиот). Большое собрание стихотворений... |
| Разработка урока Автор: Целюрик Юлия Петровна Тема: «Знакомство со... Используемые программные приложения из пакета спо: Среда программирования Скретч (Scratch) | | Прогнозирование трещиностойкости бетона на основе метода конечных элементов Реальное строение материала и особенности его поведения под нагрузкой отражено в структурных теориях прочности. Однако практическое... |
| Урок по алгебре и математическому анализу в 10 классе по теме «Решение... Обучающая цель: Изучить возможности применения метода интервалов для решения тригонометрических неравенств | | 26. Мельников Федор Михайлович Мельников Федор Михайлович родился 31 июля 1942 года в дер. Остречиха Сандовского района Калининской области |
| Программное обеспечение для решения задач линейного программирования... Линейными ограничениями. Основой программы служит алгоритм симплекс метода для неограниченного числа условий и переменных. В алгоритме... | | Студента 617 группы фртк давидюка Дмитрия Сергеевича Научный к т.... Поэтому, когда мы измеряем биологические потенциалы, мы видим результат синхронной деятельности совокупности клеток мозга, и эта... |
| Доклад ронжина Андрея Леонидовича по диссертационной работе «Разработка... «Разработка адаптивного метода робастного понимания слитной речи на основе интегральной обработки данных», представленной на соискание... | | Методическая разработка «Одномерные массивы» на языке программирования... «Одномерные массивы» на языке программирования pascal в теории и практике школьного курса «Информатика и икт»/ Методическая разработка.... |
