ИСПОЛЬЗОВАНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ПОИСКА ОПТИМАЛЬНОЙ ТРАЕКТОРИИ НАБЛЮДАТЕЛЯ

ИСПОЛЬЗОВАНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ПОИСКА …

УДК 681.518.001.33
ИСПОЛЬЗОВАНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ПОИСКА ОПТИМАЛЬНОЙ ТРАЕКТОРИИ НАБЛЮДАТЕЛЯ
Д.В. Степанов, А.А. Шалыто

Предложена модификация генетического алгоритма, предназначенная для поиска оптимальной траектории наблюдателя в задаче оценивания параметров движущейся цели по угловым измерениям (Bearing-Only Target Motion Analysis,
BOTMA). Возникающие проблемы сходимости и попадания в локальные экстремумы, характерные для генетических алгоритмов, решены с помощью идей, заложенных в оптимизационные методы случайного восхождения и имитации отжига. Для ускорения работы алгоритма отбор особей производился на уровне хорошо приспособленных схем. Ключевые слова: генетические алгоритмы, метод случайного восхождения, метод имитации отжига, теорема схем Холланда, гипотеза строительных блоков Гольдберга, расстояние Хэмминга, задача BOTMA.

Введение

В задаче определения параметров движения цели по угловым измерениям BOTMA одной из наиболее важных проблем является выбор движения наблюдателя, приводящего к получению качественных оценок [1, 2]. Параметры движения цели оцениваются с помощью линейных регрессионных моделей. Качество получаемых оценок характеризуется их ковариационной матрицей, выражающейся через матрицу плана регрессионной модели. Элементы матрицы плана, в свою очередь, зависят от параметров движения наблюдателя. Задача планирования эксперимента в случае регрессионной модели может быть сформулирована как задача выбора матрицы плана, доставляющей оценки с минимальной дисперсией. Таким образом, задачу планирования эксперимента в рассматриваемом случае можно представить в виде оптимизационной задачи поиска варианта движения наблюдателя, при котором минимизируется ковариационная матрица регрессионных оценок [3].
Будем рассматривать вариант кусочно-линейного движения наблюдателя с постоянной скоростью. При этом траектория наблюдателя может быть представлена в виде последовательности углов его поворота. Подобную оптимизационную задачу имеет смысл решать с помощью генетического алгоритма (ГА) [3], однако в случае большого числа «изломов» (галсов) траектории проявляется одна из частых проблем ГА, состоящая в попадании решения в локальные экстремумы.
Как показал анализ траекторий [3], в оптимальных многогалсовых траекториях часть галсов «сливается» вместе, и фактическое их число оказывается значительно меньше первоначально заданного. Объяснением данному факту является то, что, помимо осуществления маневров, для получения хороших оценок наблюдатель должен также производить измерения из точек, как можно более далеко разнесенных друг от друга. Траектория, удовлетворяющая данному требованию, не может быть сильно изломана. Оптимальные траектории, построенные из большого числа частично «сливающихся» галсов, имеют одно важное свойство – они могут содержать галсы различной длительности, что в ряде случаев приводит к улучшению оценок.
В настоящей работе предлагается модификация ГА, позволяющая находить оптимальные решения в задаче поиска траекторий наблюдателя с различными по длительности галсами.

Планирование эксперимента в задаче BOTMA

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

наблюдателя Cj  C  MIN , MAX , 0  MIN  MAX  360 , на заданном числе NLEG галсов. При от-
сутствии ограничений на угол поворота на галсе естественно выбрать для рассмотрения

MIN  0, MAX  360 . Формально оптимизационная задача состоит в поиске
arg max  .
 C1 , , CNLEG CNLEG

(1)

Пространство

 N LEG C

представляет собой пространство траекторий. Выбор возможных

Cj

ограничим

дискретным множеством, состоящим из точек вида Cj  j  C , где C – шаг дискретизации. Число раз-

личных вариантов углов поворота наблюдателя определяется как

N ALPH

 MAX  MIN C

. Обозначим число

галсов NLEG . Тогда общее число траекторий, состоящих из NLEG галсов с NALPH вариантами возможных

углов поворота, равно

N NLEG ALPH

.

Каждой

траектории

сопоставим

угол,

рассчитываемый

по

формуле

92 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2012, № 1 (77)

Д.В. Степанов, А.А. Шалыто

   C0 ,...,CNLEG 1

 C0

NLEG
 Ci
i 1



N

i ALPH



 2

N  NLEG ALPH

.

Интерпретируя  как функцию от  , изобразим график функции  (рис. 1).

20 =0
15

y

10

5

0 –20 –15 –10 –5 0
–5
–10
–15 –20

5 10 15 x

Рис. 1. Способ изображения функции  при шаге дискретизации 30º
Сформулируем (1) как задачу поиска угла  , в направлении которого функция  наиболее сильно
удаляется от нуля. Как видно из рис. 1, график функции  имеет NALPH корней. Они соответствуют прямолинейным траекториям наблюдателя, на которых определитель информационной матрицы обнуляется. Корни делят весь график функции  на NALPH сильно изрезанных «лепестков». Каждый из них отвечает выбору первого угла поворота траектории наблюдателя. Лепестки обладают множеством локальных максимумов, многие из которых имеют близкие значения. Рис. 1 дает представление о том, насколько сложной оказывается задача оптимизации (1).
Генетические алгоритмы и гипотеза строительных блоков
ГА представляет собой оптимизационный алгоритм, имитирующий процесс биологической эволюции [4]. Основной теоремой теории ГА, обосновывающей эффективность алгоритма, является теорема схем (шаблонов) Дж. Холланда, доказанная в 1975 г. [5, 6].
Схемой (шаблоном) H называется подмножество множества генотипов, допустимое в данной популяции, заданное в виде хромосомы с зафиксированными значениями некоторых генов. Число «зафиксированных» генов схемы называется порядком, а расстояние между крайними зафиксированными гена-
ми – определяющей длиной. Функцией приспособленности F  H  схемы называется среднее значение
функций приспособленности всех ее генотипов [5, 6]. Схемы с функцией приспособленности выше среднего по популяции, малым порядком и малой определяющей длиной принято называть строительными блоками.
Из теоремы схем следует, что шанс увеличить свое представительство в популяции следующего поколения имеется у схем малого порядка, малой определяющей длины и высокой приспособленности – у строительных блоков. В 1989 г. Д. Гольдбергом [6] была высказана гипотеза строительных блоков, состоящая в том, что ГА ведет поиск решения на множестве строительных блоков [7].
С практической точки зрения гипотеза Д. Гольдберга состоит в том, что наибольшая эффективность от применения ГА ожидается в тех задачах, в которых возможно выделение строительных блоков.
В задаче поиска оптимальной траектории (1) хромосомой длины NVAR  NLEG является последовательность углов поворота наблюдателя в моменты смены галса, например, при NVAR  6 хромосома мо-
жет принять вид C  C0,C1,C2, C3,C4,C5   270,0,180,0,0, 210 . Одна из возможных схем H , ко-
торой принадлежит приведенная выше хромосома, будет задаваться выражением H  ,0,,0,0, . По-
рядок приведенной схемы равен трем, а определяющая длина схемы также равна трем: 5 – 2 = 3. В следующем разделе приводится модификация ГА, обеспечивающая решение оптимизационной
задачи (1), использующая идею гипотезы строительных блоков.

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2012, № 1 (77)

93

ИСПОЛЬЗОВАНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ПОИСКА …

Генетический алгоритм с эмиссией интронов

Сформулируем основные отличия предлагаемого метода от классической реализации ГА.
 Интенсивность применения генетических операторов привязывается к мере разнообразия популяции, меняющейся от поколения к поколению (аналогия с методом имитации отжига).
 Вероятность сохранения изменений, возникающих при применении генетических операторов, ставится в зависимость от наблюдаемого изменения функции приспособленности (аналогия с методом случайного восхождения).
 Выделяется ген (интрон), высокое содержание которого характеризует приспособленные хромосомы. На начальном этапе работы алгоритма осуществляется масштабное искусственное добавление данного гена в хромосомы.
 Производится поиск хорошо приспособленных схем (в согласии с гипотезой Д. Гольдберга) путем анализа расположения интронов в хромосомах – выделения интронных островов и их дополнений – экзонных островов.
 Вводится ряд новых операторов на экзонных островах, реализующих перебор траекторий-кандидатов. Для измерения степени разнообразия популяции будем использовать расстояние Хэмминга

dH  A, B , определяемое как число позиций, в которых соответствующие символы двух строк A и B

одинаковой длины различны. Обозначим через dH  среднее расстояние Хэмминга по популяции  .
Используя идею метода имитации отжига [8], интенсивность применения генетических операторов по-

ставим в зависимость от показателя dH  .
Предполагая, что выпрямленные траектории будут иметь большую приспособленность, чем сильно изломанные, выскажем гипотезу о существовании строительных блоков (или хорошо приспособленных схем), состоящих из последовательностей нулей. При таком рассмотрении нас будет интересовать разделение генов на нулевые (интроны) и все остальные (экзоны).
Сделаем необходимые замечания относительно терминов «интрон» и «экзон». Термин «интрон» заимствован из биологии, где он обозначает некодирующий участок хромосомы, задающий пространственную структуру хромосомы. Термин «экзон» в биологии обозначает кодирующий участок хромосомы. Термин «интрон» используется также в области, родственной ГА – в генетическом программировании, где он обозначает неэффективный фрагмент кода, изменения в котором не влекут изменения в работе программы [9].

Оператор эмиссии интронов Ei создадим по аналогии с оператором мутации. Каждый ген Ck
хромосомы C может мутировать в интрон (соответствующую новую хромосому обозначим C0,k ) с вероятностью pi , зависящей от среднего расстояния Хэмминга по популяции и изменения функции приспособленности. Оператор эмиссии интронов может быть записан в виде

Ei t

 1, Ck

C



 0, Ck

pi Ck , 0 , qi Ck , 0

,

pi  qi  1 ,

где qi  1 pi – вероятность того, что данный ген не будет изменен оператором Ei :

qi

Ck

,

0



 1 



dH 
NVAR

  



IF

CF

C0,k



.

Обозначим через M X , популяционную матрицу, строками которой будут хромосомы особей,

прошедших отбор. Если через NX обозначить число особей, проходящих отбор, то размерность матрицы

M X ,

записывается как

NX  NVAR . Далее, матрице

M X ,

сопоставим матрицу

M ,(i,e) X ,

элементами

кото-

рой являются индикаторы принадлежности к группе интронов «0» или экзонов «1». Отбор строительных

блоков будем производить с помощью матрицы

M (i,e) X ,

.

Введем

еще

одно

определение:

назовем

локусом

loci  j,  позицию гена в хромосоме. Задача отбора блоков состоит в определении локусов, в которых

должны быть расположены интроны. Такие локусы будем называть далее интронными. Рассмотрим

j -й столбец матрицы

M (i,e) X ,

.

Он

содержит

все

варианты

заполнения

локуса

loci  j, 

в текущей попу-

ляции  . Введем в рассмотрение среднее расстояние Хэмминга в локусе j популяции  , характери-

зующее степень определенности относительно того, интрон или экзон должен располагаться в данном локусе:

     dH

j,   NX

1

NX 1

dH
A Bloci j, 

A, B .

94 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2012, № 1 (77)

Д.В. Степанов, А.А. Шалыто

Максимальное значение dH  j,  равно NX 2 и соответствует ситуации, при которой в данном
локусе находится поровну интронов и экзонов («0» и «1»). Минимальное значение dH  j,  равно нулю
и отвечает ситуации, в которой в данном локусе находятся либо только интроны, либо только экзоны.
Введем в рассмотрение расстояние dH, t1  j,  , учитывающее информацию о среднем расстоянии Хэм-
минга в локусе, содержащуюся в предшествующих поколениях:

t  NX  NX 1  dH , t  j,  

dH  A, B

dH , t1  j,  

A Bloci j, 
t 1  NX  NX 1

.

Используем аналогию, подсказанную моделями статистической физики: будем интерпретировать

 dH, t1 j,  как энергию системы частиц, а dH  – как температуру. Обратим внимание на то, что в

рассматриваемой системе с ростом времени (числа поколений) температура dH  (при правильно ра-
ботающем алгоритме) будет снижаться. Наиболее устойчивое состояние системы характеризуется мини-

мумом энергии, что в данном случае соответствует ситуации определенности в распределении интронов

и экзонов в локусах. Дискретизированная энергия системы Ez  dH, t1 j,  (где   – целая часть

числа) в каждом локусе может принимать значения из отрезка 0; NX 2 . Обозначим через Nz число ча-

стиц, находящихся на энергетическом уровне z , тогда значения Nz NX описываются распределением Максвелла-Больцмана:

pMB

z



Nz NX



gz exp  Ez dH  gw exp  Ew dH 

.

w

Будем называть энергетически неустойчивым значение элемента матрицы

M

(i X

,e) ,

(k

,

j)

,

соответ-

ствующее локусу loci  j,  в хромосоме с номером k 1, NX  , если данное значение относится к менее

многочисленному множеству при разбиении на интроны-экзоны. Например, если в локусе loci  j, 

большинство составляют интроны, а

M (i,e) X ,

(k,

j)

является экзоном или наоборот, то

M (i,e) X ,

(k,

j)

является

энергетически неустойчивым значением. Рассматривая последовательно локусы loci  j,  в хромосомах

с номерами

k 1, NX  , будем изменять энергетически неустойчивые значения

M

(i X

,e) ,

(k,

j)

(находящиеся

на энергетическом уровне z ) на противоположные с вероятностью 1 pMB  z  pCF k  , где pCF k  –

дискретное распределение вида

pCF

k



  k





 

NX

  u



1 

.

 u1



(2)

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

вых элементов матрицы

M

(i X

,e) ,

(k

,

j)

,

преобразует

исходную матрицу в некоторую новую матрицу

M (i,e) X ,

(k,

j)

,

с

помощью

которой

далее

будет

построена

маска

m

(вектор размерности

NVAR ) для оценки

интронных локусов:

m



j





0, 1,

 k  1; NX

M (i,e) X ,

(k,

j)



0;

 k  1; NX

:

M

(i X

,e) ,

(k

,

j)



0.

Далее, как только определены интронные острова, поиск оптимального решения будет происхо-

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

ющие изменения:

1. оператор очистки – заменяет одиночный экзон на экзонном острове на интрон;

2. оператор сдвига – сдвигает весь экзонный остров на некоторое случайное число позиций вправо или

влево;

3. оператор склейки – суммирует управляющие воздействия экзонного острова и помещает суммарное

воздействие в один из локусов данного экзонного острова, согласно распределению (2);

4. оператор перемешивания – суммирует управляющие воздействия экзонного острова и распределяет

суммарное воздействие по случайному числу локусов данного экзонного острова, согласно распреде-

лению (2).

После каждого цикла применения операторов 1–4 запускается оператор уборки мусора, который

будет удалять противоположные по направлению управляющие воздействия, например, поворот на 30º и

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2012, № 1 (77)

95

ИСПОЛЬЗОВАНИЕ ГЕНЕТИЧЕСКОГО АЛГОРИТМА ДЛЯ ПОИСКА …

следующий за ним поворот на минус 30º. В отличие от операторов 1–4, действие оператора уборки мусора не ограничивается границами экзонного острова. Изменения, производимые данными операторами, будем сохранять только в том случае, когда это приводит к увеличению приспособленности особи. Для ускорения работы алгоритма будем применять операторы 1–4 с вероятностью, пропорциональной частоте принятых изменений, произведенных соответствующим оператором.
Укажем изменения, которые необходимо внести в алгоритмы работы операторов рекомбинации и мутации, чтобы их действия были согласованы с алгоритмом отбора строительных блоков. В классическом ГА сохранению блоков большего порядка препятствует оператор мутации. Соответственно, чтобы блоки смогли выжить в ранних поколениях, мутация должна быть низкой в начале и может увеличиваться по мере снижения среднего расстояния Хэмминга по популяции. Действительно, при появлении в ней

выживающих из поколения в поколение блоков dH  будет уменьшаться (тем больше, чем выше поря-

док блоков). В более поздних поколениях (в популяциях с малым dH  ) увеличение числа мутаций
может помочь ускорить отбор более приспособленных блоков, правда, при следующем условии: будут разрешены только мутации, приводящие к увеличению значения функции приспособленности особи. Данное условие аналогично принципу, лежащему в основе метода случайного восхождения [8]. Зададим

формулу вероятности мутации особи C (теперь зависящую от времени):

   pm

t 1,C



 1



d

H



 NVAR



 



IFt1

C



Ft

C



.

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

применения оператора рекомбинации. Этот оператор, применяемый совместно с оператором рекомбина-

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

генов в хромосомах. Наиболее приспособленная особь в популяции (после применения генетических

операторов) с большей вероятностью будет содержать искомые строительные блоки. По этой причине

имеется заинтересованность в распространении ее генотипа. Из всех возможных вариантов оператора

выбора пары более всего подходит вариант вожака стада (herd leader breeding [5]), при котором наиболее

приспособленная особь образует пары со всеми остальными. Поскольку при скрещивании желательно не

разрушать уже полученные блоки, выберем одноточечный вариант скрещивания, при котором родитель-

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

Суммируя изложенное выше относительно операторов одноточечного скрещивания X и выпрям-

ления R , приведем формальное описание совместного действия этих операторов:



X,



XR



 

 

R,





att



dH 
NVAR

;





att



dH 
NVAR

,

где  – равномерно распределенная на 0, 1 величина, а att – коэффициент затухания, принимающий
неотрицательные значения. Описанный выше алгоритм будет быстро сходиться к экстремуму, отвечающему найденным бло-
кам с высокой приспособленностью. Для того чтобы увеличить число перебираемых вариантов, реализуем алгоритм как островной [4]. Когда на острове с не самой высокой приспособленностью происходит вырождение, будем удалять популяцию данного острова и переселять наилучшую особь с лучшего острова, а остальные особи будем генерировать случайным образом, оставляя нетронутыми те гены, которые были нулевыми у наилучшей особи. Тем самым будут перенесены на обновленный остров выращенные строительные блоки с лучшего острова, обеспечивая запуск генетического отбора на данном острове с более высокого уровня приспособленности.
Предложенную модификацию ГА будем называть ГА с эмиссией интронов (IEGA – Intron Emission GA). При этом исходный алгоритм ГА будем обозначать GA.

Результаты моделирования

Приведем результаты работы GA и IEGA. На рис. 2 изображены графики функций приспособленности лучших особей (по поколениям) для GA (без мутации и с мутацией) и IEGA, из которых видно, что модифицированный алгоритм попадает на более высокий уровень приспособленности особей. Результаты работы алгоритмов приведены в таблице. Ниже представлено их сравнение:
 IEGA генерирует в качестве оптимальных траектории со значительно меньшим числом галсов, чем GA (4 против 18–19);
 функция приспособленности особей IEGA выше;
 разброс значений функции приспособленности особей IEGA ниже (среднеквадратическое отклонение (СКО) результатов IEGA в три–пять раз ниже, чем у результатов GA);

96 Научно-технический вестник Санкт-Петербургского государственного университета
информационных технологий, механики и оптики, 2012, № 1 (77)

Д.В. Степанов, А.А. Шалыто
 IEGA требует для сходимости в среднем больше поколений, чем GA без мутации. GA с мутацией не сходится за 100 поколений;
 разброс числа различных решений IEGA ниже, чем у GA (16 против 30).

значение функции приспособленности

; номер поколения

;

Рис. 2. Графики функций приспособленности лучших особей для GA и IEGA

Алгоритм
GA (без мутации) GA (частота мутации 0,05)
IEGA

Число галсов
19
18 4

δ
19,95 20,41 21,06

СКО(δ)
0,26 0,15 0,05

Среднее число
поколений
7
100
20

Общее число ре-
шений
30

Число различных решений
30
30
16

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

1. Ince L., Sezen B., Saridogan E., Ince H. An evolutionary computing approach for the target motion analysis (TMA) problem for underwater tracks // Expert Systems with Applications. – 2009. – V. 36. – № 1. – Р. 3866–3879.
2. Cadre J.P., Jauffret C. Discrete-Time Observability and Estimability for Bearings-Only Target Motion Analysis // IEEE Transactions on Aerospace and Electronic Systems. – 1997. – V. 33. – № 1. – Р. 178–201.
3. Степанов Д.В. Использование генетического алгоритма для нахождения оптимального маневра в задаче N-пеленгов // III Всероссийский конкурс молодых ученых. – Миасс, 2011. – 11 с.
4. Haupt R.L., Haupt S.E. Practical genetic algorithms. – John Wiley & Sons, 2004. – 253 р. 5. Reeves C.R., Rowe J.E. Genetic Algorithms: Principles and Perspectives. – Kluwer Academic Publishers,
2003. – 332 р. 6. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning. – Addison-Wesley, 1989.
– 412 с. 7. Spears W.M. Evolutionary Algorithms: The Role of Mutation and Recombination. – Springer, 2000. – 222 р. 8. Russell S.J., Norvig P. Artificial Intelligence: A Modern Approach. – Prentice Hall, 2003. – 1081 р. 9. Brameier M., Banzhaf W. Linear Genetic Programming. – Springer, 2007. – 315 р.

Степанов Денис Вячеславович Шалыто Анатолий Абрамович

– ОАО «Концерн «НПО «Аврора», мл. научный сотрудник,
denis_v_stepanov@hotmail.com – Санкт-Петербургский национальный исследовательский университет ин-
формационных технологий, механики и оптики, доктор технических наук, профессор, зав. кафедрой, shalyto@mail.ifmo.ru

Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики, 2012, № 1 (77)

97