• Задача поиска
• Постановка задачи
• Символьная модель
• Геометрическая интерпретация символьной модели
• Алгоритм

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

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

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

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

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

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

e: O -> S

Для o из O и s из S запись s=e(o) будет обозначать то, что s является представлением o. В общем случае e(o) может описывать целое множество представлений, однако этот случай нами не рассматривается. Обратное отношение будем записывать как e^-1 (функция декодирования)

e^-1: S -> O

обратное отношение используется тогда, когда по новому представлению s' из S, полученному в результате поиска, требуется восстановить соответствующее ему решение o' из O. e^-1(o) может представлять множество объектов из O. Если e(o') - не пустое множество, то будем говорить, что o' представлен. Если e^-1(s') - пустое множество, то s' - недопустимое представление.

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

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

f: O -> R

такая, чтобы для любых двух o₁,o₂ из O, если f(o₁)>f(o₂), то o₁ считается решением лучше, чем o₂. R - множество вещественных чисел. Очевидно, что об оптимальности того или иного решения можно говорить лишь тогда, когда исследовано все пространство представлений S.

Для реализации алгоритма поиска в пространстве представлений можно ввести функцию оценки представлений, аналогично функции f, определенной на элементах из множества O. Определим ее как

m: S -> R

Где R - множество вещественных чисел.

С помощью m можно определить порядок в S таким образом, чтобы представителям лучших объектов в смысле f соответствовало большее значение m. Т.е. если для любых двух объектов o₁, o₂ из O в S определены различными представителями s₁=e(o₁) и s₂=e(o₂), s₁ не равно s₂ и если f(o₁)>f(o₂), то m(s₁)>m(s₂). В общем случае функцией m(s) может быть любая функция M, удовлетворяющая этому условию.

m(s) = M(f(e^-1(s)))

Однако, как правило, вполне достаточно сделать

m(s) = f(e^-1(s))

Иногда, в зависимости от конкретных операторов алгоритма поиска, бывает необходимо, что функция m(s) принимала положительные значения.

Представленные рассуждения позволяют сформулировать задачу поиска наилучшего объекта o* из множества O следующим образом

o* = argmax f(e^-1(s))
s из S

Ее решение осуществляется поиском в пространстве S оптимального представления s*:

s* = argmax m(s)
s из S

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

1. пространство потенциальных решений O,
2. пространство представлений S,
3. функцию кодирования e и декодирования e^-1,
4. функцию цели f,
5. функция оценки представлений m.

к началу

Нами будет рассматриваться общая задача непрерывной оптимизации

f(x) - максимизируемая (целевая) скалярная многопараметрическая функция, которая может иметь несколько глобальных экстремумов, прямоугольная область D - область поиска, D - подмножество R^N.

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

Под решение задачи (1) будем понимать вектор x = (x₁, x₂, :, x_N).

Оптимальным решением задачи (1) будем считать вектор x*, при котором целевая функция f(x) принимает максимальное значение. Исходя из предположения о возможной многоэкстремальности f(x), оптимальное решение может быть не единственным.

В принятых ранее обозначениях под объектом будем понимать точку x в многопараметрическом пространстве O=D в R^N. Роль функции цели будет играть максимизируемая функция f(x).

к началу

Для того, чтобы построить пространство представлений под генетический алгоритм для задачи непрерывной оптимизации, нужно помнить, что начиная с 1975 - публикации первого издания книги Голланда - ГА-мы использовались при решении комбинаторных задачам оптимизации. Использование аппарата для решения дискретных задач применительно к задачам непрерывной оптимизации допускалось путем дискретизации пространства параметров скалярной функции f(x), для которой предстояло найти оптимальное решение.

Параметры x обычно кодируются бинарной строкой s. Используя целевую функцию f(x) можно построить функцию m(s) - функцию пригодности или, как она называется в генетических алгоритмах, функция приспособленности, отобразив, когда это необходимо, f на положительную полуось. Это делается для того, чтобы гарантировать прямое соотношение между значение целевой функции и приспособленностью решения, и затем такая модифицированная целевая функция рассматривается как функция приспособленности ГА. Таким образом, каждое возможное решение s, имеющее соответствующую приспособленность m(s), представляет решение x.

Обычно, переход из пространства параметров в хемминингово пространство бинарных строк осуществляется кодированием переменных x₁, x₂, :, x_N в двоичные целочисленные строки достаточной длины - достаточной для того, чтобы обеспечить желаемую точность. Желаемая точность в этом случае и будет тем отправным условием, которое определяет длину бинарных строк. Для этого пространство параметров должно быть дискретизировано таким образом, чтобы расстояние между узлами дискретизации соответствовало требуемой точности. Предположим, по условию задачи с функцией от двух переменных x₁ и x₂, определенной на прямоугольной области D = {0 <x₁<1; 0<x₂<1}, требуется локализовать решение x* с точностью по каждому из параметров 10^-6. Для достижения такой точности пространство параметров дискретизуется равномерной сеткой с (b_i-a_i)/(10^-6)= 1/10^-6 = 1000000 узлами по каждой координате. Закодировать такое количество узлов можно l = 20 битами, где l определяется из условия 10⁶ < 2^l+1. Вот и получается, что общая длина бинарной строки кодировки для двумерной задачи составит 2X20 = 40 бит.

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

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

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

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

Каждый интервал [a_i, b_i] разбиваем на k отрезков равной длины:

h_i = (b_i - a_i) / k,  i = 1, 2, :N.

Этом самым покроем i-ый интервал [a_i, b_i] сетью s_i из (k+1) узла с постоянным шагом h_i.

x_i,j = a_i + j^.h_i,  j = 0, 1, : k.

Используя двоичный алфавит {0,1} каждому узлу сетки s_i можно присвоить уникальный бинарный код длины q. Длина кода q выбирается таким образом, чтобы k < 2^q. Наиболее целесообразно и экономично использовать сетку с k = 2^q-1.

Тогда символьная запись j-ого узла по i-ой координатной оси в двоичном коде можно представить в виде следующей бинарной конструкции

Проведя дискретизацию по всем N координатным осям, получим в N-мерном параллелепипеде D пространственную решетку S с (k+1)^N узлом, где каждый узел s можно представить в виде линейной последовательности таких записей (хромосом).

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

ГА оперирует строками фиксированной длины.

Чтобы применять ГА к задаче, сначала выбирается метод кодирование решений в виде строки. Фиксированная длина (l-бит, l=q*N) двоичной кодировки означает, что любая из 2^l возможных бинарных строк представляет возможное решение задачи.

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

Идея ГА состоит в том, чтобы манипулируя имеющейся совокупностью бинарных представлений, с помощью ряда генетических операторов получать новые строки, т.е. перемещаться в новые гиперкубики. Получив бинарную комбинацию для нового решения, формируется вектор (операция декодирования e^-1), со значениями из соответствующего гиперкуба, используя равномерное распределение.

Таким образом, каждое решение генетического алгоритма будет иметь следующую структуру:

1. Точка в пространстве параметров (фенотип):
   x = (x₁, x₂, : x_N) принадлежит D из R^N;
2. Бинарная строка s фиксированной длины, однозначно идентифицирующая гиперкуб разбиения пространства параметров (генотип):
   

   s = (b₁, b₂, :, b_l) принадлежит S,

   где S - пространство представлений - бинарных строк длины l.
3. Скалярная величина m, соответствующая значению целевой функции в точке х (приспособленность):
   m = f(x).

В терминологии, принятой в теории ГА, такую структуру принято называть особью. Предлагаемая модель обязательно включает в себя вектор со значениями из гиперкуба пространства параметров. Совокупность особей принято называть популяцией.

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

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

к началу

Итак, мы определись с тем, каким образом будет осуществляться переход из евклидова пространства параметров в пространство представлений (бинарных строк). Давайте рассмотрим эту процедуру на конкретном примере простой одномерной функции f(x).

f(x) = 10 + x sin(x),

определенной на отрезке [0, 10].

Пусть кодирование будет осуществляться бинарными строками длины 3. Т.е. отрезок [0,10] нужно разбить на 2³ = 8 подинтервалов, каждому из которых будет соответствовать уникальная двоичная комбинация, получаемая переводом номера подинтервала, считая слева направо, в двоичную системы. Длина каждого такого интервала будет h=10:8=1.25.

Рисунок 1: Построение символьной модели для одномерной задачи, используя трехбитовое представление.

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

Рисунок 2: Пространство поиска для трехбитового представления.

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

к началу

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

НАЧАЛО /* генетический алгоритм */

Прежде всего отличие от классических ГА-мов состоит в сохранении вещественных векторов решений. Вторым важным отличием является порядок реализации основных генетических операторов. Вначале проходит стадия "воспроизводства" новых решений, включающая в себя три элемента:

1. Выбор элементов a_i^t и a_j^t (брачная пара), используя правило B/breeding/.
2. Генерация новых решений с помощью оператора "кроссовер" C /crossover/
3. Локальные изменения большого числа решений с помощью оператора "мутации" M /mutation/.

И лишь затем осуществляется процедура построения совокупность решений для следующей итерации ("поколения") из всего множества доступных к тому моменту решений - оператор S.

В-третьих, представленный алгоритм, относится скорее к так называемым "поколенческим" (термин ДеЯнга) эволюционным алгоритмам, в которых эволюция идет от одной итерации к другой, допуская появление k>>1 новых решений, накапливаемых в репродукционном множестве, прежде, чем включится процесс отбора, отбрасывающий лишние k решений.

Поскольку алгоритм построен таким образом, что решения, получаемые в результате кроссовера, не заменяют собой "родителей" (как в традиционном ГА), то такой параметр как Pc - вероятность кроссовера - в данном случае не нужен (или всегда равен 1.0). Вместо него мы пользуемся параметром, описывающим число брачных пар. Управлять количеством вычислений целевой функции, т.е. количеством генерируемых решений предпочтительнее этим детерминированным параметром.

На каждом из этапов предлагаются альтернативные генетические операторы. Некоторые из них уже известны и описаны в литературе (Mitchell, 1996), появление других обусловлено новизной символьной модели. Все они по-разному влияют на поведение ГА. Подробнее к этому вопросу мы еще вернемся. А пока, я еще раз остановлюсь на списке основных параметров ГА:

1. мощность множества решений P^t(численность популяции),
2. длина бинарных кодировок s(длина генотипов),
3. количество решений, генерируемых на каждой итерации,
4. вероятность применения оператора локального изменения решений (мутации) M,
5. правило B выбора двух решений,
6. тип используемого оператора глобального поиска (кроссовера) С,
7. тип используемой оператора локального изменения (мутации) М,
8. процедура отбора S.

Почти все из них (кроме численности популяции) могут динамически изменяться от итерации к итерации.

Очевидно, что восемь параметров - это достаточно много для алгоритма. То, насколько удачным окажется применение ГА при решении той или иной задачи, во многом будет определяться их удачной настройкой. Вообще говоря, строгих правил, универсальных для всех задач, нет и быть не может (по теореме "не бывает бесплатных обедов" /"no free lunch" theorem, Wolpert & McReady, 1995/), однако в данной работе мы постараемся сформулировать некоторые рекомендации по настройке параметров для решения определенного класса задач.

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