авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Pages:     | 1 ||

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ Ю. Д. Бедный Применение генетических алгоритмов для ...»

-- [ Страница 2 ] --

Наконец, поставленная задача управления осложняется тем, что каждая из координат вектора f – функция большого числа аргументов. Например, для задачи управления самолетом необходимо выделить как минимум десять параметров (для построения реалистичной модели значительно больше, возможно несколько сотен). Тогда область определения функции, принимающей решение об изменении контролируемых параметров на 85-ой минуте, есть R 856010 = R 51000.

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

Например, способ управления самолетом вряд ли изменяется каждую секунду.

В этом случае некоторая координата осуществляет управление объектом на протяжении интервала времени, который превосходит минимальный. В предельном случае будем искать решение задачи не в виде вектора f = [ f1, f 2,..., fT ]T, а в виде единственной функции f * : QT R m, которая управляет объектом в каждый момент времени t [1.. T ]. Тогда решение задачи – функция управления f = [ f *, f *,..., f * ]T.

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

В предельном случае приведенных упрощений – одно правило управления для всех моментов времени, принимающее в качестве аргумента только значения параметров в настоящий момент времени – решение оптимизационной задачи искать значительно проще. Однако наилучшее из решений такого вида может не удовлетворять заданным критериям оптимальности управления объектом, потому что пространство поиска сильно сужено. Поэтому важной представляется задача нахождения компромисса между ограниченностью пространства, в котором осуществляется поиск решения и сложностью решения задачи оптимизации. Далее будет предложено решение этой задачи, которое основано на автоматном подходе [3].

3.1.4. Автоматный подход и его недостатки Как правило, при решении задачи управления можно выделить состояния, в которых может находиться объект управления. При управлении самолетом такими состояниями, например, являются: «получено разрешение на взлет», «разбег», «отрыв от земли», «заход на курс», «следование курсом», «переход на автоматическое удержание курса», «отказ двигателя», «приближение к аэродрому назначения», «полет с экономным расходом топлива в случае неблагоприятных для посадки условий», «заход на посадку», «торможение» и т.д.

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

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

1. Количество различных координат функции управления полагается равным количеству состояний автомата. Таким образом, для каждого состояния автомата определяется свое правило управления объектом (координата искомой функции управления). Тогда одно и тоже правило может управлять объектом в различные моменты времени – функция управления декомпозируется по состояниям.

2. Координата функции управления, сопоставленная каждому состоянию, управляет объектом исходя только из значений параметров в настоящий момент времени. Область ее определения – множество Q.

Данный подход имеет и существенные недостатки. Во-первых, задача определения множества входных и выходных воздействий конечного достаточно трудна, потому что отсутствует разумный критерий качества ее решения. Так при определении множества входных воздействий некоторым образом производится дискретизация множества Q. Например, в работе [25] для задачи управления самолетом выделяются, следующие входные и выходные воздействия:

• «x1: самолет движется – принимает истинное значение при скорости воздушного потока более пяти узлов»;

• «x5: у поверхности земли – принимает истинное значение при высоте над землей менее пятнадцати футов»;

• «z13: половина газа – устанавливает дроссель в среднее положение»;



• «z16: взлетное положение закрылков – устанавливает требуемое положение закрылков на уровень 0.3, рекомендуемый для взлета».

Из данного описания следует, что дискретизация осуществляется по некоторым пороговым значениям («пяти», «пятнадцати», «половина», «0.3»).

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

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

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

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

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

3.1.5. Предлагаемый метод В этом разделе будет предложен метод решения задачи управления основанный на автоматном подходе, однако, лишенный перечисленных недостатков. Основной идеей предлагаемого метода является использование разновидности генетических алгоритмов – программирования с экспрессией генов [3]. Примеры применения данного метода для решения задач приведены в [25].

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

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

Схема работы генетических алгоритмов приведена на рис. 13 (вторая глава).

3.1.7. Представление решения задачи управления в виде хромосомы Опишем способ, в котором решение задачи управления представляется в виде хромосомы. Зафиксируем N – число состояний автомата, построение которого будет выполняться в дальнейшем. Это число определяет «сложность»

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

Для каждого состояния определим некоторое правило управления f i : Q R m, i = 1..N. Для каждой пары различных состояний с номерами (i, j) зададим функцию перехода fij : Q R. Таким образом, будет определен полный граф, в вершинах которого находятся правила управления, а на ребрах – функции перехода. Как именно определяются правила управления и функции перехода будет рассмотрено далее.

При управлении объектом в каждый момент времени, находясь в состоянии i, последовательно выполняются следующие действия:

• вычисляются значения функций f ij для всех j, i j. Как только одно из вычисленных значений оказывается больше нуля ( f ij 0), выполняется переход в состояние j. Если же все f ij 0, то состояние не изменяется;

• определяется значение правила управления f i, и выполняется действие, соответствующее найденному значению.

На рис. 18 приведен пример автомата с тремя состояниями, решающего некоторую задачу управления.

F F F F F F F F F Рис. 18. Пример автомата Функция управления может быть представлена как набор из N ( N 1) функций перехода и N правил управления. Напомним, что функция перехода – это функция, отображающая из множества значений параметров Q = R n во множество вещественных чисел. Правило перехода – функция, R отображающая из Q в R m. Предлагается правило управления рассматривать как набор из m функций отображающих из Q в R. Тогда хромосома, соответствующая решению задачи управления, может быть представлена как набор из N ( N 1) + m N функций, каждая из которых отображает из R n в R. Таким образом, задача представления решения в виде хромосомы свелась к представлению функции из R n в R в виде к омпоненты хромосомы.

Ограничим класс искомых отображений из R n в R функциями, которые являются композицией некоторых базовых функций нескольких аргументов (от одного до n). Выбор базовых функций, как правило, определяется конкретной задачей. Требования, предъявляемые к набору базовых функций, таковы – набор должен быть достаточно полным, для того чтобы выразить необходимые зависимости, и не слишком избыточным, для того чтобы работа алгоритма поиска функции управления была эффективной.





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

Например, в качестве базисных функций можно выбрать следующие:

+(x, y) = x + y, ++(x, y, z) = x + y + z, n(x) = –x, *(x, y) = xy, **(x, y, z) = xyz, min, sin, cos, exp, log, |x|, s( x) =, if (x, y, z, w) = x y ? z : w, random[ 0..1].

1 + e x В качестве терминалов выступают значения параметров в текущий момент времени. Для задачи управления самолетом, терминалами, например, будут являться: v – скорость самолета, h – высота полета, e – запас топлива, t – время полета,,, – углы Эйлера самолета и т.д. Кроме того, набор терминалов дополняется константами, например: 0,.5, 1, 100,.

Определив набор терминалов и базовых функций, достаточно воспользоваться разновидностью генетических алгоритмов, обладающей высокой эффективностью – программированием с экспрессией генов (Gene Expression Programming) [3]. Программирование с экспрессией генов ищет функцию в виде, так называемых, Karva-деревьев. На рис. 19 приведен пример такого дерева.

Рис. 19. Пример представления функции из R в R в виде Karva-дерева n Итак, хромосома – набор N ( N 1) + m N функций, каждая из которых представима в виде Karva – дерева.

3.1.8. Функция приспособленности, генетические операции Для определения приспособленности хромосомы (в виде которой представлена некоторая функция управления) достаточно получить автоматное представление функции управления, что выполняется однозначно. Затем, промоделировав процесс управления объектом, управляемым автоматом, получим фазовую кривую, для оценки которой определена функция g.

Критерий остановки процесса эволюции определяется спецификой задачи и функцией качества решения – g. Например, если для задачи управления самолетом функция g возвращает число, обратное максимальной перегрузке за все время полета, а величина допустимой перегрузки – 4, то разумно остановить процесс эволюции при значении функции приспособленности равном 0.25.

Для управления игровыми объектами (например, футболистами в виртуальном футболе или танком в игре Robocode) естественно останавливать процесс эволюции по достижении игровым объектом желаемого результата, например, победы над соперником с заданной вероятностью.

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

3.2. Создание системы управления танком в игре Robocode В данном разделе производится апробация предложенного метода решения задач управления при создании системы управления танком для популярной компьютерной игры Robocode. Этот метод позволяет на основе использования генетических алгоритмов строить достаточно простые системы управления танком.

Отметим, что не ставится цель создать танк, способнй побеждать танки, построенные вручную, которые являются наилучшими из известных на сегодняшний день (например, танк Алгоритмы, voidious.Dookious).

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

Танки, создаваемые предлагаемым методом, должны побеждать в индивидуальном сражении каждого заранее выбранного соперника из тестового набора, который включает в себя танки, поставляемые вместе с игрой, а также танк newCynic.Cynical [28]. Выбор последнего был связан с тем, что этот танк (как и прототип, на основе которого он построен [29]), в отличие от многих других танков, был предварительно спроектирован и для него существует достаточно подробная открытая проектная документация. Для каждого танка из тестового набора с помощью предлагаемого метода генерируется танк, который его побеждает. Модификация предлагаемого метода позволяет генерировать танки, системы управления которых, построены и без применения автоматного подхода (можно рассматривать этот случай и как автоматный, для автомата с одним состоянием). При этом если автоматы не используются, то система управления описывается только одной функцией, формирующей выходные воздействия на объект управления. При автоматном подходе для каждого состояния автомата определена соответствующая функция управления, согласно описанию метода в предыдущем разделе.

На рис. 20 в качестве примера приведен внешний вид среды игры Robocode во время одного из боев. На этом рисунке разработанный танк назван EvolvedTank.

Рис. 20. Пример боя в игре Robocode 3.2.1. Обзор Известно большое число танков для рассматриваемой игры [30].

Наиболее простые из них реализованы всего несколькими строками кода, а программы, реализующие наиболее сложные танки, как отмечалось выше, занимают сотни килобайт. Большинство танков создано вручную. Существуют также работы [31, 32], в которых танки строятся не вручную, а автоматически – с применением методов искусственного интеллекта.

В работе [31] использовано несколько таких методов (обучение с подкреплением, нейронные сети и генетические алгоритмы) для управления различными системами танка (радаром, системой движения и пушкой).

Генетические алгоритмы в работе [31] применялись для создания систем управления радаром и движением танка. Однако их использование не привело к желаемому результату – система управления радаром осуществляла его поворот на 360 градусов, а система передвижения задавала перемещение танка по кругу.

В работе [32] используется сравнительно сложный способ представления системы управления в виде особи генетического алгоритма – программы на языке TableRex. При этом длина программы составила 7776 бит.

3.2.2. Постановка задачи Устройство танка схематично показано на рис. 21. Необходимо управлять следующими устройствами: радаром (Radar), пушкой (Gun) и системой движения (Body).

Рис. 21. Схематичное изображение танка Управление танком осуществляется следующим образом. В каждый момент времени анализируется текущая ситуация (положение танка, его скорость и т.д.). На основе этой информации формируются четыре действия:

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

Перейдем к формальной постановке задачи. Обозначим текущее время в игре как t N, а максимальное время, которое возможно для данной игры – M.

Обозначим множество позиций как S, а множество действий танка как A.

Позиция – элемент некоторого множества всех возможных ситуаций в игре в выбранный момент времени. Позиция включает в себя положение каждого танка, его скорость, направление, угол поворота пушки и радара, энергию, информацию о танке соперника и т. д. Задача управления для рассматриваемой игры в общем случае состоит в задании для каждого момента времени t функции управления f t : S t A, которая на основании информации о позициях во все предыдущие моменты времени (получаемой из среды Robocode) определяет действие на объект управления в текущий момент времени. Таким образом, решение задачи управления танком – вектор [ f1, f 2,K, f M ]T.

Упростим задачу управления. Пусть:

1. Действие танка в текущий момент времени зависит только от позиции в этот момент времени.

2. Зафиксирован алгоритм управления радаром – вращение по кругу.

3. При выборе действия анализируется лишь упрощенная позиция – элемент S = { x, y, dr, tr, w, dh, GH, h, d, e, E }. Здесь:

множества • x, y – координаты танка соперника относительно нашего танка;

• dr – расстояние, которое осталось “доехать” нашему танку (после вызова метода AdvancedRobot.setAhead);

• tr – угол, на который осталось повернуться нашему танку;

• w – расстояние от нашего танка до края поля;

• dh – угол между направлением на танк соперника и пушкой нашего танка;

• GH – угол поворота пушки нашего танка;

• h – направление движения танка соперника;

• d – расстояние между нашим танком и танком соперника;

• e – энергия танка соперника;

• E – энергия нашего танка;

• множество действий A = {g, p, d, h}, где g – угол поворота пушки, p – энергия снаряда (неположительные значения означают, что выстрел не производится), d – расстояние, на которое перемещается танк, h – угол поворота танка.

Учитывая изложенное, задача построения системы управления танком сведена к заданию функции f : S A. Эту функцию будем искать автоматически с использованием программирования с экспрессией генов. В отличие как от стандартных генетических алгоритмов, использующих строки фиксированной длины, так и от генетического программирования [5], использующего деревья, хромосомы в генетическом программировании с экспрессией генов представляются в виде строк фиксированной длины, которые преобразуются в, так называемые, Karva-деревья. Генетические операции с такими деревьями (в отличие от генетического программирования) За счет этого, при использовании корректны по определению.

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

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

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

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

Общая схема генетических алгоритмов. Схема одного шага работы генетических алгоритмов приведена на рис. 13.

3.2.4. Представление в виде хромосомы Для представления в виде особи генетического алгоритма искомой функции управления f : S A предлагается представлять ее в виде четырех функций f i, каждая из которых возвращает вещественное число: f1 – угол поворота пушки, – энергия снаряда, – расстояние, на которое f2 f перемещается танк, f 4 – угол поворота танка.

В свою очередь, функция f i представляется в виде Karva-дерева – стандартного способа представления для программирования с экспрессией генов. Таким образом, хромосома состоит из четырех строк – линеаризованных Karva-деревьев, для представления которых применяются описываемые ниже функции и терминалы.

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

Предлагается использовать следующий набор базовых функций:

+(x, y) = x + y, ++(x, y, z) = x + y + z, n(x) = –x, *(x, y) = xy, **(x, y, z) = xyz, min,, if (x, y, z, w) = x y ? z : w.

s( x) = 1 + e x Набор терминалов (координаты танка (x, y), его энергия (e) и т.д.) строится исходя из определения позиции (элемента множества S ). Кроме того, этот набор необходимо дополнить некоторым множеством констант. В настоящей работе были выбраны следующие константы: 0,.5, 1, 2, 10.

В табл. 8 приведен пример сгенерированной хромосомы, а в табл. 9 – соответствующая этой хромосоме функция управления f = ( f1, f 2, f 3, f 4 ), представленная через базовые функции.

Таблица 8. Представление функции в виде хромосомы Линеаризованные Karva-деревья f1 4 0 7 1 17 4 5 2 4 1 18 9 10 13 12 10 13 22 23 11 17 21 8 15 16 14 21 13 16 18 22 10 16 19 13 8 21 13 10 8 f2 6 4 5 8 0 2 7 0 5 0 20 15 8 19 19 18 8 11 15 16 13 22 23 22 12 20 22 19 13 19 23 15 15 22 11 22 11 14 8 17 f3 7 2 1 3 6 5 6 0 6 7 21 16 22 19 21 17 19 23 9 13 17 13 14 15 9 21 12 16 21 14 16 23 16 15 23 16 8 21 15 14 f4 2 4 5 0 2 7 1 3 4 1 19 8 15 17 17 9 18 13 13 18 18 21 17 17 17 15 8 9 18 22 17 23 19 21 10 10 11 20 13 19 Таблица 9. Функции, соответствующие хромосоме Функция f = ( f1, f 2, f 3, f 4 ) f1 = *(s[n(*(.5, e))], if[10, *(n(E), dh), *(y, dr,.5), +(w, dr)]) f2 = min(*[x, s(*(x, tr, 1))], *[+(s(2), h, if(1, x, GH, GH), s(dh)]) f3 = if(+[*(GH, d, 10), min(GH, E)], n[s(y)], +[min(.5, 10), if(.5, 0, 1, y), d], min[2, e]) f4 = +(*[s(*(dh, dh)), +(n(d), GH)], *[if(x, 1, 10, 10), n(y), +(dh,.5,.5)]) На рис. 22 приведен пример Karva-дерева для функции f1 из табл. 9.

Рис. 22. Karva-дерево функции f1 из табл. 3.2.5. Функция приспособленности Опишем, как была выбрана функция приспособленности. Она отражает результат поединков против выбранного соперника. При этом отметим, что, так как результат поединка существенно зависит от начального положения танков, то проводится не один поединок, а несколько (двадцать). Увеличение числа сражений позволило бы получить более точный результат, однако это было бы связано с возрастанием времени вычисления функции приспособленности, которое и так велико.

Для того чтобы уравнять шансы соперников, выбор начальных положений танков производится следующим образом. Создается случайный набор пар координат ((x1, y1), (x2, y2)). После этого для каждой из них проводится два поединка, в первом из которых танк соперника имеет начальные координаты (x1, y1), а во втором – (x2, y2). Обозначим число очков, набранных нашим танком в бою (состоящим из 20 раундов) как s, а число очков, набранных его соперником, как se. При этом приспособленность танка s будем вычислять следующим образом: f = 100.

s + se Процесс эволюции продолжается до тех пор, пока максимальное значение функции приспособленности для элементов популяции не превзойдет некоторого порогового значения. Например, пороговое значение, равное 70, означает, что танк в среднем «научился» побеждать своего соперника. При этом отметим, что значение функции приспособленности, равное 50, означает, что наилучший из танков текущей популяции в ходе двадцати раундов при случайном начальном положении танков, выигрывает половину раундов.

3.2.6. Генетические операции Для реализации генетического алгоритма в настоящем разделе используются стандартные генетические операции: отбор, мутация и скрещивание. Отбор осуществляется по методу рулетки. Скрещивание хромосом (как наборов из четырех строк, например, приведенных в табл. 8) производится поэлементно. При этом для каждой пары строк с вероятностью p в качестве i-го элемента результатом скрещивания выбирается i-й элемент либо первой, либо второй хромосомы, а с вероятностью (1 – p) – скрещивание производится стандартным образом с использованием метода битовой маски.

Аналогично скрещиванию, мутация выполняется поэлементно. При этом каждый из символов строки с некоторой вероятностью заменяется некоторым другим. Более подробное описание указанных операций приведено в работе [1].

3.2.7. Эксперименты При реализации генетического алгоритма число особей в популяции было выбрано равным 50. Один шаг эволюции (скрещивание, мутация, отбор, вычисление функции приспособленности) в популяции такого размера выполняется около пяти минут на компьютере Intel Pentium M 1.86 GHz. При этом практически все время тратится на вычисление функции приспособленности. Данное обстоятельство не позволяет использовать популяции больших размеров. Так, например, даже при указанном числе особей время работы генетического алгоритма может занимать несколько часов.

На рис. 23 приведен пример графика, иллюстрирующего работу генетического алгоритма для генерации танка против соперника sample.Walls.

По оси абсцисс отложен номер поколения, а по оси ординат – значение функции приспособленности (Max – максимальное значение среди особей популяции, а Avg – среднее значение).

Приспособленность 40 Max Avg 1 3 5 7 9 11 13 15 17 19 21 Поколение Рис. 23. Процесс эволюционного построения танка Из рассмотрения графика максимального значения функции приспособленности (Max) следует, что уже на 11-ом поколении эволюцию можно было остановить, так как максимальное значение функции приспособленности превысило пороговое значение 70. Однако процесс был остановлен после 23-го поколения, так как значение функции приспособленности перестало изменяться существенно.

Таким образом строится каждый танк в результате сражений с одним из танков тестового набора. В табл. 10 приведены описания систем управления, которые сгенерированы в ходе сражений с танками соперников newCynic.Cynical и sample.Walls. Эти танки использовались и в сражениях, результаты которых перечислены в табл. 4, так как указанные танки являются наиболее сильными в тестовом наборе.

Таблица 10. Представление функции управления сгенерированных танков Соперник Описание функции 0 2 1 6 3 6 0 6 13 19 14 13 23 10 28 18 13 17 18 13 19 newCynic.Cynical 17 23 15 13 18 9 29 30 15 14 0 7 2 0 4 6 1 7 9 22 23 11 23 22 16 23 18 27 10 22 27 16 13 15 21 24 29 14 17 16 20 3 4 8 1 6 0 0 5 14 17 21 24 21 17 19 11 19 11 24 18 28 23 15 10 24 16 22 14 30 26 14 7 3 3 1 8 0 1 2 18 23 29 15 26 29 16 25 30 25 16 23 26 27 17 18 26 19 25 15 10 19 28 7 0 6 8 2 3 8 6 0 5 23 13 18 9 12 20 23 14 20 27 29 12 sample.Walls 26 14 10 13 26 10 17 22 26 21 18 14 30 14 21 20 23 4 4 4 4 1 6 1 2 2 2 9 22 19 19 29 25 21 26 17 17 14 27 14 21 16 22 30 23 21 29 14 21 19 15 9 9 19 22 9 24 0 3 2 1 5 7 1 2 1 16 11 21 15 25 18 25 30 18 17 21 9 19 26 10 28 28 13 12 11 28 28 18 14 14 14 26 11 30 2 5 6 6 5 13 6 5 8 12 23 11 28 22 21 14 16 15 21 15 29 19 23 14 20 24 27 14 14 22 26 26 10 12 26 15 28 10 15 После генерации каждого танка, для оценки его эффективности были проведены бои с тем же соперником, против которого он выводился. Бои состояли из 100 раундов. В табл. 4 приведены результаты этих боев. В этой таблице в столбце “Счет” первое значение – число очков набранных нашим танком, а второе – танком соперника. В общем случае, как отмечалось выше, увеличение числа раундов приводит к более объективным результатам.

Таблица 11. Результаты поединков (100 раундов) Соперник Счет 10933 : newCynic.Cynical 9559 : sample.Walls 11414 : sample.SpinBot 11964 : sample.MyFirstRobot 18086 : sample.Corners 10797 : sample.Crazy 17610 : sample.Fire 18642 : sample.Tracker 16269 : sample.TrackFire 17968 : sample.Target 18572 : sample.RamFire 3.2.8. Автоматный подход Эвристическое построение автоматов, управляющих танком, применялось в работе [28, 29]. В тоже время попыток автоматически построить автоматы для управления танком ранее не предпринималось.

В рассмотренном выше подходе, управление танком в любой момент времени осуществляется единственной функцией. При f : S A использовании автоматов эта функция декомпозируется с помощью состояний согласно подходу, предлагаемому в данной главе и описанному в предыдущем разделе. В каждом состоянии автомата определим функцию f i : S A, где i – номер рассматриваемого состояния. Для каждой пары различных состояний с номерами (i, j) зададим функцию перехода f ij : S R. Построение функций переходов выполняется с помощью генетических алгоритмов, сами функции представляются в виде Karva-деревьев.

Табл. 12 иллюстрирует процесс эволюционного построения танка с автоматной структурой.

Таблица 12. Работа генетического алгоритма (процесс эволюции) Максимальное Среднее значение Номер Время, c значение функции функции поколения приспособленности приспособленности 0 31.15 15.70 1 36.71 26.42 2 34.93 28.91 3 40.30 32.96 … … … … 9 52.25 43.74 10 55.53 41.15 … … … … 21 64.49 59.14 22 69.44 60.18 23 91.38 62.55 24 89.45 72.68 … … … … 36 93.73 91.48 Эволюция была остановлена на 36-ом поколении, так как рост максимального значения функции приспособленности практически остановился.

В табл. 13 приведен пример описания автомата из двух состояний в виде особи генетического алгоритма. Это описание содержит десять строк: восемь (f – f8) определяются состояниями и две (f9, f10) – переходами. Данный автомат выводился в результате боёв с танком sample.Walls.

Таблица 13. Представление функции управления сгенерированных танков Описание автомата 5 2 2 5 6 7 6 1 4 4 8 20 9 8 12 23 22 22 16 13 14 10 12 9 14 16 9 18 11 11 23 f 19 18 23 13 15 16 16 22 3 16 2 5 1 2 0 6 3 5 15 8 17 12 22 14 21 11 10 12 13 21 14 14 8 19 11 20 17 f 23 14 22 18 8 10 9 21 20 18 3 7 14 3 7 5 4 16 4 1 17 16 9 20 16 22 12 10 17 9 11 8 19 19 16 12 11 8 15 20 f 23 20 19 18 10 19 21 13 10 1 7 14 6 2 4 7 6 4 6 9 8 12 21 17 10 13 16 23 18 17 14 15 15 19 17 18 14 21 9 f 17 12 19 11 8 13 9 23 10 4 0 7 1 17 4 5 2 4 1 18 9 10 13 12 10 13 22 23 11 17 21 8 15 16 14 21 13 16 f 22 10 16 19 13 8 21 13 10 8 6 4 5 8 0 2 7 0 5 0 20 15 8 19 19 18 8 11 15 16 13 22 23 22 12 20 22 19 13 19 f 15 15 22 11 22 11 14 8 17 7 2 1 3 6 5 6 0 6 7 21 16 22 19 21 17 19 23 9 13 17 13 14 15 9 21 12 16 21 14 f 23 16 15 23 16 8 21 15 14 2 4 5 0 2 7 1 3 4 1 19 8 15 17 17 9 18 13 13 18 18 21 17 17 17 15 8 9 18 22 17 f 19 21 10 10 11 20 13 19 20 6 4 3 5 5 3 0 6 2 11 8 22 15 15 19 23 14 20 10 23 17 18 20 17 13 11 20 20 f 18 15 11 10 12 11 8 8 13 21 3 7 0 4 1 4 5 1 4 16 22 15 8 14 22 19 18 17 22 10 11 15 21 13 9 13 11 8 8 13 f 11 14 8 10 23 8 23 9 17 Сгенерированный танк в 1000 раундах побеждает танк соперника со счетом 180168 на 28278. Таким образом, в среднем наш танк побеждает противника с вероятностью около 86%. Это несколько меньше, чем полученное в табл. 12 максимальное значение функции приспособленности – 93.73. Данное обстоятельство объясняется тем, что результат боя из 20 раундов имеет большую погрешность из-за сравнительно небольшого числа экспериментов.

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

3.2.9. Программная поддержка метода Управление танком может осуществляться либо синхронно, либо асинхронно. В первом случае главный класс программы наследуется от библиотечного класса Robot, а во втором – от библиотечного класса AdvancedRobot [27]. В данной работе был выбран второй вариант. Таким образом, приведенный в приложении код, принадлежит классу, который наследуется от класса AdvancedRobot.

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

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

• среда Robocode;

• система управления, которая по входным воздействиям, получаемым из среды, формирует выходные воздействия на объект управления;

• объект управления (танк), содержащий систему движения и пушку.

Радар реализован тривиально, и поэтому в отдельный класс не выделен.

Эта программа является главной и содержит обращение к некоторым классам, исходный код которых не приведен в приложении. Обе программы написаны на языке Java.

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

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

ЗАКЛЮЧЕНИЕ 1. Установлена неприменимость алгоритма Баума-Велша при построении моделей максимального правдоподобия некоторого класса скрытых марковских моделей.

2. Для указанного класса показана эффективность метода построения модели максимального правдоподобия, основанного на использовании генетических алгоритмов для выбора начальных параметров.

3. Предложена и решена задача поиска ошибок в автоматах. При этом рассматривается один тип ошибок – неучтенные переходы между состояниями автомата.

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

5. Предложенный метод опробован для построения системы управления танком в игре Robocode. Построенные танки показали эффективность предлагаемого метода.

НЕКОТОРЫЕ ОТКРЫТЫЕ ВОПРОСЫ И ЗАДАЧИ 1. Привести математически строгое определение понятия «сильной детерминированности», используемого во второй главе.

2. Исследовать зависимость успешности построения моделей максимального правдоподобия от «детерминированности» скрытых марковских моделей.

3. Обобщить метод тестирования автоматов на ошибки других типов кроме неучтенных переходов.

4. Исследовать эффективность метода автоматического построения автоматных систем управления на других задачах кроме Robocode.

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

ПУБЛИКАЦИИ 1. Государственный контракт: «Технология генетического программирования для генерации автоматов управления системами со сложным поведением».

2. Труды V Межвузовской конференции молодых ученых, 2008.

3. Труды XII Всероссийской конференции «Фундаментальные исследования и инновации в технических Университетах», 2008.

4. XI Международной конференции по мягким вычислениям и измерениям, 2008.

5. IV Международная конференция по проблемам управления, 2009.

6. На рецензию в журнал «Известия РАН. Теория и системы управления».

7. Конкурс грантов 2008 года для студентов и аспирантов ВУЗов и академических институтов.

8. XV Всероссийская научно-методическая конференция «Телематика'2008».

ЛИТЕРАТУРА 1. Mitchell M. An Introduction to Genetic Algorithms. MA: The MIT Press, 1996.

2. Гладков Л. А., Курейчик В. В., Курейчик В. М. Генетические алгоритмы.

М. Физматлит. 2006.

3. Шалыто A. A. SWITCH-технология. Алгоритмизация и программирование задач. СПб.: Наука, 1998.

http://is.ifmo.ru/books/switch/ 4. Ferreira C. Gene Expression Programming: A New Adaptive Algorithm for S olving Problems // Complex Systems, 2001. V. 13. № 2. P. 87–129.

www.gene-expression-programming.com/webpapers/GEP.pdf 5. Koza J.R. Genetic programming. On the Programming of Computers by Means of Natural Selection. MA. The MIT Press. 1998.

6. Axelrod R. The Evolution of Cooperation. NY: Basic Books, 1984.

7. Fogel. D. The evolution of intelligent decision making in gaming // Cybernetics and Systems. 2001. V. 22, pp. 223-236.

8. Ashlock D., Wittrock A., Tsui-Jung W. Training finite state machines to improve PCR primer design / Proceedings of the Congress on Evolutionary Computation CEC’02. DC: IEEE Computer Society. 2002. V.1, pp. 13-18.

http://ieeexplore.ieee.org/iel5/9601/30334/01393953.pdf 9. Полимеразная цепная реакция.

http://en.wikipedia.org/wiki/Polymerase_chain_reaction 10. MacLennan B. Synthetic Ethology: An Approach to the Study of Communication / Proceedings of Artificial Life II: The Second Workshop on the Synthesis and Simulation of Living. CA: Addison Wesley. 1992. V. X, pp. 631-658. http://www.cs.utk.edu/~mclennan/papers/SEASC.pdf 11. Frey C., Leugering G. Evolving Strategies for Global Optimization – A Finite State Machine Approach / Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001). Morgan Kaufmann. 2001. pp. 27 33. http://citeseer.ist.psu.edu/456373.html 12. Wolff K., Nordin P. An Evolutionary Based Approach for Control Programming of Humanoids / Proceedings of the 3rd International Conference on Humanoid Robots (Humanoids'03). Karlsruhe: VDI/VDE GMA. 2003. http://citeseer.ist.psu.edu/641298.html 13. Николенко С. И. Скрытые марковские модели.

http://logic.pdmi.ras.ru/~sergey/teaching/mlbayes/07-hmm2.pdf 14. Rabiner L. R. A tutorial on hidden markov models and selected applications in speech recognition / Proceedings of the IEEE. 1989, vol. 77, no. 2, pp.

257 – 286.

http://ieeexplore.ieee.org/iel5/5/698/00018626.pdf?arnumber= 15. Кларк Э., Грамберг О., Пелед Д. Верификация моделей программ.

М.:МЦНМО, 2002.

16. Dempster A. P., Laird N. M., Rubin D. B. Maximum likelihood from incomplete data via the EM algorithm // Stat. Soc. 1977, vol. 39, no 1, pp. 1 – 38.

17. Бедный Ю.Д. Применение генетических алгоритмов для построения клеточных автоматов. Бакалаврская работа. 2006.

http://is.ifmo.ru/papers/genalgcelaut/ 18. Гач П., Курдюмов Г.Л., Левин Л.А. Одномерные однородные среды, размывающие конечные острова // Проблемы передачи информации.

1976. 14, 3.

19. Ferreira C. Discovery of the Boolean Functions to the Best Density Classification Rules Using Gene Expression Programming // Lecture Notes in Computer Science. 2002. Vol. 2278, pp. 51-60. www.gene-expression programming.com/webpapers/ferreira-EuroGP02.pdf 20. Won K., Hamelryck T., Prugel-Bennett A., Krogh A. Evolving Hidden Markov Models for Protein Secondary Structure Prediction / Proceedings of the IEEE (Evolutionary Computation). 2005, vol. 1, pp. 33 – 40.

http://modem.ucsd.edu/won/77.pdf 21. Поспелов Д. А. Вероятностные автоматы. М.: Энергия, 1970.

22. Понтрягин Л. С., Болтянский В. Г., Гамкрелидзе Р. В., Мищенко Е. Ф.

Математическая теория оптимальных процессов. М., 1969.

23. Красовский Н. Н., Теория управления движением, М., 1968.

24. Задача оптимального управления. Wikipedia.

http://en.wikipedia.org/wiki/Optimal_Control.

25. Технология генетического программирования для генерации автоматов управления системами со сложным поведением. Промежуточный отчет по этапу III. 2008.

26. Технология генетического программирования для генерации автоматов управления системами со сложным поведением. Промежуточный отчет по этапу I. 2007. http://is.ifmo.ru/genalg/_2007_01_report-genetic.pdf 27. Официальный сайт игры Robocode. http://robocode.sourceforge.net/ 28. Кузнецов Д. В., Шалыто А. А. Система управления танком для игры "Robocode". Вариант 2. СПбГУ ИТМО. 2003.

http://is.ifmo.ru/projects/robocode2/ 29. Туккель Н. И., Шалыто А. А. Система управления танком для игры "Robocode". Вариант 1. Проектная документация. СПбГУ ИТМО. 2003.

http://is.ifmo.ru/projects/tanks/ 30. История игры Robocode. http://robowiki.net/cgi-bin/robowiki?History 31. Gade M., Knudsen M., et al. Applying Machine Learning to Robocode. www.csc.calpoly.edu/~team14fk/F04/dat3_report.pdf 32. Eisenstein J. Evolving robot tank fighters. Technical Report AIM-2003-023, AI Lab, MIT. 2003.

http://www.ai.mit.edu/people/jacobe/research/robocode/genetic_tanks.pdf ПРИЛОЖЕНИЕ Листинг 1. Реализация автоматизированного танка package my.robocode.all;

import my.robocode.TankControlSystem;

import my.robocode.Environment;

import robocode.AdvancedRobot;

import robocode.HitByBulletEvent;

import robocode.ScannedRobotEvent;

import robocode.util.Utils;

public class SimpleTank extends AdvancedRobot { private static final double RADAR_ANG_STEP = Math.PI / 4;

private long t, tHit;

private double x, y, h, v, e;

// Интерпретатор символического описания системы управления private TankControlSystem control;

// Составляющие объекта управления private Driver driver = new Driver();

private Gun gun = new Gun();

public void run() { setAdjustRadarForGunTurn(true);

x = y = h = v = e = 0;

t = tHit = -1;

control.newRound();

// Реализация шага работы среды Robocode while (true) { if (getRadarTurnRemainingRadians() == 0) { setTurnRadarRightRadians(RADAR_ANG_STEP);

} if (t == -1) { // enemy doesn't 'locked' yet doNothing();

continue;

} // Входные воздействия, получаемые из среды Robocode Environment env = new Environment(x - getX(), y - getY(), v, h, getTime() - t, getX(), getY(), getVelocity(), getHeadingRadians(), getGunHeadingRadians(), getEnergy(), e, getTime() - tHit, minWall(), getDistanceRemaining(), getTurnRemainingRadians());

// Система управления по входным воздействиям формирует четыре // выходных воздействия (act[]) на объекты управления (gun, driver) double[] act = control.execute(env.values());

// Передача сформированных системой управления выходных воздействий // на объект управления gun.turn(this, act[0]);

if (getGunHeat() == 0 && act[1] 0) { gun.fire(this, act[1]);

} driver.go(this, act[2]);

driver.turn(this, act[3]);

execute();

} } // Обработка события – “Обнаружен танк соперника” public void onScannedRobot(ScannedRobotEvent event) { double d = event.getDistance();

double a = Utils.normalAbsoluteAngle(getHeadingRadians() + event.getBearingRadians());

x = d * Math.sin(a) + getX();

y = d * Math.cos(a) + getY();

t = event.getTime();

v = event.getVelocity();

h = event.getHeadingRadians();

e = event.getEnergy();

} // Обработка события – “Попадание снаряда” public void onHitByBullet(HitByBulletEvent e) { tHit = e.getTime();

} // Вспомогательная функция – вычисление расстояния до края поля private double minWall() { return Math.min(Math.min(getX(), getBattleFieldWidth() - getX()), Math.min(getY(), getBattleFieldHeight() - getY()));

} } // Объект управления “Танк” // Система движения class Driver { // Движение public void go(AdvancedRobot tank, double dist) { tank.setAhead(dist);

} // Поворот public void turn(AdvancedRobot tank, double ang) { tank.setTurnRightRadians(ang);

} } // Пушка class Gun { // Стрельба public void fire(AdvancedRobot tank, double energy) { tank.setFire(energy);

} // Поворот public void turn(AdvancedRobot tank, double ang) { tank.setTurnGunRightRadians(ang);

} }

Pages:     | 1 ||
 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.