Информационных технологий и программирования




Скачать 282.5 Kb.
НазваниеИнформационных технологий и программирования
страница5/6
Дата публикации23.06.2013
Размер282.5 Kb.
ТипПояснительная записка
lit-yaz.ru > Информатика > Пояснительная записка
1   2   3   4   5   6
^

2.2. Математическая модель робота-футболиста

2.2.1. Автоматное представление


Для управления роботом-футболистом, являющимся объектом управления в игре «Виртуальный футбол», был использован конечный автомат Милли (рис. 4), состоящий из четырех состояний. Автомат – это математическая модель, представляющая собой дискретный преобразователь информации, на вход которого поступают входные последовательности сигналов. Он формирует выходные последовательности сигналов на основании своих внутренних состояний и входной последовательности сигналов. Формально, автомат Милли – это система шести объектов :

  • – конечное множество состояний;

  • – начальное состояние автомата;

  • – конечное множество входных воздействий;

  • – конечное множество выходных воздействий;

  • – функция переходов;

  • – функция выходных воздействий (действий).



Рис. . Пример диаграммы переходов автомата Мили из трех состояний

Будем иметь в виду две ключевые абстракции:

  1. Автомат функционирует в абстрактном времени.

  2. Все переходы происходят мгновенно.

При этом элементы множеств , и связаны в абстрактном времени следующими соотношениями:



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

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

2.2.2. Деревья решений


Как было сказано выше, модель управления роботом-футболистом представляет собой конечный автомат Мили. На вход ему подается набор значений входных переменных, закодированных в битовую строку. Каждое состояние представляет собой дерево решений, в листьях которого хранятся переходы автомата. Переход автомата представляет собой совокупность значения функции переходов и значения функции выходного воздействия .

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

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

















0

1

2

0

1

0

1

2

Рис. . Пример дерева решений



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

2.2.3. Генетические операции


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

  • Случайная генерация автомата, выполняемая на шаге инициализации. В каждом состоянии создается случайное дерево решений.

  • Скрещивание автоматов. Скрещиваются деревья решений в соответствующих состояниях.

  • Мутация автомата. В случайном дереве решений выполняется мутация.

Теперь рассмотрим операции над собственно самими деревьями решений:

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

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

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

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

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

2.2.4. Входные и выходные воздействия


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

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

  • относительные;

  • абсолютные.

К первой группе относятся переменные, являющиеся производными от двух и более векторов, задающих положение или скорости мяча и игроков. Из них в представление входных воздействий исходной модели автомата вошли следующие:

  • Скорость игрока относительно положения мяча (рис. 8). Значение данной переменной определяется исходя из попадания вектора скорости игрока в одну из равных областей, образованных опорным вектором, являющимся разностью радиус векторов мяча и игрока ().

0

1

2

3






Рис. . Скорость игрока относительно положения мяча



  • Скорость мяча относительно скорости игрока

0

1







Рис. . Скорость мяча относительно скорости игрока




  • Положение мяча, относительно робота-футболиста (рис. 10). Рассматриваются 4 квадранта плоскости, в качестве осей координат которой выступают прямые, параллельные сторонам поля, и проходящие через центр круга, представляющий робота. Значением данной переменной является номер квадранта, в котором расположен центр мяча.

0

1

2

3

x

y

Рис. . Положение мяча относительно положения игрока



1   2   3   4   5   6

Похожие:

Информационных технологий и программирования iconКафедра информационных технологий Краткая инструкция
На экзамены выносятся три вопроса по разным базовым областям специальности: основы информационных технологий (теория систем, дискретная...

Информационных технологий и программирования iconИнформационных технологий и программирования
Применение генетических алгоритмов для построения управляющих автоматов 14

Информационных технологий и программирования iconИнформационных технологий и программирования
Класс StatusEvent 11 Глава Применение генетических алгоритмов для построения управляющих автоматов 12

Информационных технологий и программирования iconКонтрольная работа не является рефератом или распечаткой материалов...
Интернет и использованию информационных технологий для поиска и обработки информации

Информационных технологий и программирования iconУчебная программа курса или дисциплины «Основы программирования»
В частности, в курсе рассматриваются основные конструкции языков программирования, анализируются основные типы и структуры данных,...

Информационных технологий и программирования iconБурное развитие информационных технологий оказало существенное влияние...
Сегодня влияние информационных технологий на банковский бизнес увеличилось настолько, что автоматизация, подобно финансовой политике...

Информационных технологий и программирования iconТема : «Достижение устойчивых изменений в работе школы по применению...
Необходим качественно усовершенствованный и активный переход на новый уровень в использовании компьютерной техники и информационных...

Информационных технологий и программирования iconИспользование современных информационных технологий в образовательном...
Чества образования. Внедрение информационных технологий в учебный процесс призвана повысить эффективность проведения урока, освободить...

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

Информационных технологий и программирования iconВэй Чуньлэй Применение информационных технологий в исследованиях...
Применение информационных технологий в исследованиях по Исследованию состава биологически активных соединений кемпферии галанга и...



Образовательный материал



При копировании материала укажите ссылку © 2013
контакты
lit-yaz.ru
главная страница