Оптимального управления 13 страница

В случае нелинейной зависимости Y2(YX) (кривая 2) нельзя каждому кванту qu поставить в соответствие один квант q2j (рис. 3.29). При этом какому-либо кванту qVi может соответствовать: либо один полный квант q2j, либо один неполный квант q2j, либо два и более полных кванта q2j, q2j+l, либо один или несколько полных кванта q2j, q2k и один или несколько неполных кванта q2hV q2hfl и т. д. (табл. 3.2). При этом, если такие нелинейные зависимости типа 2 отображать, как и прежде, только системой логических уравнений, т. е. без учета степени принадлежности какого- либо кванта q2j кванту д]р то будет вводиться большая погрешность отображения, зависящая от вида кривой 2. Улучшить эту ситуацию можно путем введения либо вероятности P{X{~>X2j =1}, либо функции принадлежности ^(У) (Y<=> Х1Г>Ху), вычисляемых подобно вероятности в уравнении (3.19) и приведенных в табл. 3.2 (в знаменателях). Например, Р{Х.2^Х2Ъ - 1} = \х(Х]2-^Х23) = 0,5. 

Таблица 3. 2

^22 ^23 ^24 %25 %26 *27 ^28 %29

*11 1/1 1/1 1/0,5 0 0 0 0 0 0

0 0 1/0,5 1/1 1/0,2 0 0 0 0

0 0 0 0 1/0,8 1/0,4 I 0 0 0

Х\4 0 0 0 0 0 1/0,6 1/0,5 0 0

Х.5 0 0 0 0 0 0 1/0,6 1/0,1 0

0 0 0 0 0 0 0 1/0,8 0

Х17 0 0 0 0 0 0 0 1/0,1 1/0,5

^18 0 0 0 0 0 0 0 0 1/07

^19 0 0 0 0 0 0 0 0 1/0,1

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

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

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

При отборе данных для НС необходимо учитывать следующие факты:

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

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

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

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

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

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

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

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

Обозначим % показатель значимости р~го параметра; w°p —

текущее значение р-го параметра; w* — ближайшее выделенное

значение для р-го параметра. Используя введенные обозначения, процедуру отбора можно записать следующим образом:

1. Вычисляем показатели значимости.

2. Находим минимальный среди показателей значимости — %*р.

3. Заменим соответствующий этому показателю значимости параметр wp* на w*p и исключим его из процедуры обучения.

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

5. Обучаем полученную сеть. Если сеть обучилась безошибочному решению задачи, то переходим к п. 1 процедуры, в противном случае переходим к п. 6.

6. Восстанавливаем сеть в состояние до предшествующего выполнению п. 3. Если в ходе выполнения п. 2—5 был удален хотя бы один параметр (число обучаемых параметров изменилось), го переходим к п. 1. Если ни один параметр не был удален, то получена минимальная сеть.

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

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

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

Таким образом, обучение многослойной НС можно представить двумя этапами:

• предъявление НС обучающего множества примеров до тех пор, пока не будет выполнено условие останова обучения:

а) вычисляемая ошибка сети Е становится меньше заданной или перестает изменяться в течение определенного числа итераций ("эпох");

б) по истечении заданного числа итераций;

• проверка правильности работы сети на тестовом множестве: если ошибка обобщения Ео6о6щ> 8 (8— заданная ошибка обобщения) — проводится увеличение числа итераций, либо числа обучающих примеров, либо происходит модификация архитектуры НС.

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

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

Рассмотрим наиболее известный алгоритм обучения многослойной НС (Back Propagation — BP) и определим условия повышения эффективности процедуры обучения. BP — это итеративный градиентный алгоритм обучения многослойных НС без обратных связей. В такой сети на каждый нейрон первого слоя подаются все компоненты входного вектора. Все выходы скрытого слоя т подаются на слой m+ 1 и т. д., т. е. сеть является полносвязной.

Последовательность действий, составляющих суть градиентных методов, используемых в стандартном BP: вычисление градиента, вычисление направления движения, связанного с градиентом и шага вдоль этого направления. Различные градиентные методы поиска минимума функционала отличаются выбором направления движения и шага [8].

При обучении ставится задача минимизации ошибки НС, которая определяется методом наименьших квадратов:

E{W) = \/2 ±(yj-dj)\

№

где у — значение у-го выхода НС; d. — желаемое значение у-го выхода; р — число нейронов в выходном слое.

Обучение НС осуществляется методом градиентного спуска, т. е. на каждой итерации изменение веса производится по формуле

Щ. = ~~ h(dE)/(dw0),

где h — параметр, определяющий скорость обучения, а

(Э £)/0w.) = (Э£)/(Э(3.25)

здесь у. —- значение выхода j-го нейрона; S — взвешенная сумма входных сигналов. При этом множитель (^5.)/(9w.) = хр где х. — значение /-го выхода нейрона.

Определим первый множитель формулы (3.25):

к

к

где к — число нейронов в слое п + 1.

Введем вспомогательную переменную

Ь^ = (dE)/(dyi)(dyi)/(dSj). 

Тогда можно определить рекурсивную формулу для определения л-го слоя, если известно значение этой переменной следующего (п + /)-го слоя:

5У

д

(ЭЛ)/(Э5,). (3.26)

Нахождение для последнего слоя НС не представляет

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

W = 021)

В результате всех преобразований получим следующее выражение для вычисления приращения весов связи в НС:

дн^. =~Ц'7)х;. (3.28)

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

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

2. Рассчитать по формуле (3.27) и Aw., по формуле (3.28) для выходного слоя НС.

3. Рассчитать 5р и Aw., по формулам (3.27) и (3.28) для остальных слоев НС.

4. Скорректировать все веса НС: (t) = (/-!) + Aw^ (/),

где t — номер текущей итерации.

5. Если ошибка существенна, то вернуться к п. 1, в противном случае — конец.

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

В стандартном алгоритме BP, основанном на методе градиентного спуска, предполагается такая последовательность дей-

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

Еще одна из возможных стратегий состоит в следующем — НС обучается при помощи стратегии усреднения лишь некоторому множеству примеров, в которое по мере обучения сети постепенно включаются все новые и новые примеры. Такая стратегия в среднем в 1,5™2 раза быстрее стратегии усреднения, однако в этом случае процесс обучения зависит от взаимного рас-положения задач в обучающей выборке. Максимальное ускорение обучения достигается, если "типовые" задачи расположены ближе к началу обучающей выборки.

Выбор величины шага имеет ключевое значение для успешной работы обучающего алгоритма, так как от значения шага А зависит скорость сходимости алгоритма. Так как к моменту выбора шага для следующей итерации градиент ошибки в методе BP уже вычислен, то можно интерпретировать функцию ошибки как функцию шага Е{И). Тогда, учитывая, что значение Е(И0) вычислено на предыдущем шаге, можно записать следующий алгоритм А1:

1 Сделать пробный шаг А и вычислить Е(И);

2, Если E{h)> E(h0), то A:= А/4 ("наказание"); переход к п. 1;

3. Если E(h)< ДА0), то А: - 2А ("поощрение").

Приведенный алгоритм А1 является оптимальным для стратегии, при которой НС обучается на множестве примеров поочередно. Для повышения качества алгоритма А1 при обучении по стратегии усреднения может быть использован алгоритм А2:

1. См. п. 1 в А1.

2. Если ДА) > ДА0), то:

й,:= А/2;

если E(hj > £(А0), то А: = А,, переход к п. 2. I;

если E(h{) < E(h0), то переход к п. 4.

3. Если ДА) < ДА0), то:

A,: = A, A: = 2A,;

если ДА) < ДА,), то переход к п. 3. 1;

если ДА) > ДА,), то переход к п. 4.

4. По значениям А0, А, А,, ДА0), ДА),ДА,) строим параболу и находим ее вершину Ар (из-за выбора точек А, и А парабола всегда будет выпуклой вниз).

5. Если E(hp)<ДА,}, то искомый шаг — А;, иначе — hp.

Алгоритм А2 позволяет повысить скорость обучения примерно в 2-3 раза, однако при его использовании возникают сложности с выводом сети из локальных минимумов.

При обучении НС могут использоваться и не градиентные методы обучения.

Идея метода покоординатного спуска состоит в том, что если в задаче сложно или долго вычислять градиент, то можно построить вектор, обладающий приблизительно теми же свойствами, что и градиент. Для этого дадим малое положительное приращение первой координате вектора. Если оценка is при этом увеличилась, то пробуем отрицательное приращение. Далее таким же образом поступаем со всеми остальными координатами. В результате получаем вектор, в направлении которого оценка убывает. Для вычисления этого вектора потребуется, как минимум, столько вычислений функции оценки, сколько координат у вектора (в худшем случае число вычислений в 2 раза больше числа координат). Время, используемое для вычисления градиента при использовании алгоритма BP, обычно оценивается как время двух-трех вычислений функции оценки. Учитывая этот факт, можно констатировать, что метод покоординатного спуска нецелесообразно применять в обучении НС.

Метод Нелдера-Мида является наиболее быстрым неградиентным методом многомерной оптимизации. Идея метода состоит в следующем. В пространстве оптимизируемых параметров генерируется случайная точка. Затем строится «-мерный симплекс с центром в этой же точке и длиной стороны /. Далее в каждой из вершин симплекса вычисляется значение критерия оптимизации. Выбирается вершина с наибольшим значением критерия. Вычисляется центр тяжести остальных п вершин. Про-водится оптимизация шага в направлении от наихудшей верши- ны к центру тяжести остальных вершин. Такая процедура повторяется до тех пор, пока не окажется, что положения вершин не меняются. Затем выбирается вершина с наилучшей оценкой и вокруг нее снова строится симплекс с меньшими размерами (например, 1/2). Процедура продолжается до тех пор, пока размер симплекса, который необходимо построить, не окажется меньше заданной величины.

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

Метод случайного поиска сводится к генерации случайного вектора вместо градиента. Метод использует одномерную оптимизацию для подбора шага. Подбор оптимального шага h состоит в том, что при наличии направления, в котором производится спуск задача многомерной оптимизации в пространстве параметров сводится к одномерной —- подбору шага.

Пусть заданы начальный шаг h и случайное направление спуска. Вычисляем величину оценки Ест как оценку в текущей точке пространства параметров. Изменив параметры на вектор направления, умноженный на величину пробного шага, вычислим значение оценки в новой точке. Если Et < Е. то уве-

^ нов нов ст' J

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

Если после первого пробного шага Енов > Ест, то уменьшаем шаг до тех пор, пока не получим Еть< Ест. После этого производим квадратичную оптимизацию.

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

В настоящее время в процедуре обучения многослойной НС широко используется один из методов эвристической оптимизации — генетический алгоритм (ГА), моделирующий процессы природной эволюции и относящийся к так называемым эволюционным методам поиска.

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

Основные отличия ГА от стандартных локальных (например, градиентных) и глобальных (например, случайных) алгоритмов оптимизации:

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

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

• для оценки "пригодности" решения и последующего эволюционного развития наряду с использованием целевой функции дополнительно моделируются "правила выживания", которые расширяют разнообразие множества решений и определяют эволюционное развитие;

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

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

Схема простого генетического алгоритма представлена на рис. 3.32.

Генетическим алгоритмом называется следующий объект:

ГА(P\r, I, si, Fit, cr, т, ot),

где ГА — генетический алгоритм; Р°— исходная популяция; г — количество элементов популяции; /— длина битовой строки, кодирующей решение; si — оператор селекции; Fit-- функция

Рис. 3.32. Схема простого генетического алгоритма

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

Будем считать, что область поиска решения D задачи одно- критериального выбора является конечным множеством решений, в котором каждое допустимое решение XeD является «-мерным вектором Х = (х,, х2,..., хп).

Наименьшей неделимой единицей биологического вида, подверженной действию факторов эволюции, является особь

Н[ (к— номер особи, t — момент времени эволюционного процесса). В качестве аналога особи в задаче оптимизации принимается произвольное допустимое решение XeD, которому присвоено имя Н[. Действительно, вектор X— это наименьшая неделимая единица, характеризующая в экстремальной задаче внутренние параметры объекта оптимизации на каждом t-м шаге поиска оптимального решения, которые изменяют свои значения в процессе минимизации некоторого критерия оптимальности J(X).

Качественные признаки особи Н[ определяются как соответствующие точке Хс именем Н[ (в простейшем случае битовой строке). Интерпретация этих признаков проводится в терминах хромосомной наследственности. В качестве гена — единицы наследственного материала, ответственного за формирование альтернативных признаков особи, — принимается бинарная комбинация А, которая определяет фиксированное значение параметра х. в двоичном коде. Некоторая особь Н{ будет характери-зоваться п генами, каждый из которых отвечает за формирование целочисленного кода соответствующей переменной. Тогда структуру битовой строки можно интерпретировать хромосомой, содержащей п сцепленных между собой генов. Местоположение /-го гена в хромосоме — локус, значение — алпель h.

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

об особи Н[. Конечное множество всех допустимых генотипов называют генофондом. В частности, хромосомы, соответствующие генофонду, содержащему оптимальное управление, могут быть сформированы следующим образом.

Требуется найти хромосому, соответствующую некоторому управлению ыэ U, где U — множество всех возможных значений и (рис. 3.33). Тогда, если количество генов N в хромосоме определить исходя из шага дискретизации td: N = tu/td, где tu — максимально допустимое время управления, tj=tp и t — время преобразования ЦАП и АЦП в системе управления, а код гена определять исходя их шага квантования q = UJ2", где Um — максимально допустимая величина управляющего воздействия, п — число разрядов ЦАП и АЦП системы управления, то генофонд будет образовываться из хромосом вида, показанного на рис. 3.34.

и

и.

max

U

Я

Рис. 3.33. Множество управляющих воздействий

/00001/01000/00011/ /11111/

N

Рис. 3.34. Вид хромосомы

При взаимодействии особи с внешней средой ее генотип Н[

порождает фенотип F {В[ который можно оценить количественно с помощью функции приспособленности (функции фитнее- са) к внешней среде. Фитнесс Fit(Н[) кажд,ой особи Н[ равен численному значению функции /(X), вычисленной для допустимого решения Хе D с его именем Н[. Чем больше значение функции финтесса при решении задачи нахождения max /(X), тем лучше особь приспособлена к внешней среде.

Формирование популяции. Совокупность особей (Н{,..., Н'г) образуют популяцию Р' (численностью г). Эволюция популяции Р' рассматривается как чередование поколений (рис. 3.35). Номер поколения отождествляется с моментом времени t = 0,1,..., Г, где Т— жизненный цикл популяции, определяющий период ее эволюции. Совокупность генотипов всех особей Нк* образует хромосомный набор, который полностью содержит в себе генетическую информацию.

В настоящее время наиболее известными являются три стратегии создания начального множества решений:

1) формирование полной популяции;

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

3) генерация множества решений, включающего разновидности одного решения.

Рис. 3.35. Формирование популяции решения

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

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

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

Хромосома А Хромосома В

IV

Потомок А Потомок В

Эффективность ГА, качество получаемого решения и успех дальнейшего развития эволюции во многом определяются структурой и качеством начальной популяции. Наиболее целесообразным представляется подход, основанный на комбинировании второй и третьей стратегии: путем предварительного анализа решаемой задачи выявляются подобласти в области поиска D, в которых могут находиться оптимальные решения, т. е. определяются особи с высоким значением фитнесса, а затем случайным образом формируются стартовые ре-шения в этих подобластях.

Выделяют два основных способа генерации новых решений (рис. 3.36 и 3.37):

Рис. 3.36. Одноточечный

1) путем перекомпоновки (скрещивания) двух родительских решений (оператор скрещивания или кроссинговер сг); кроссинговер 

Мутация

Мутация Результат

потомка А мутации

V V

■а2 а\

а>

ь< К

А. А.

Рис. 3.37. Оператор мутации

2) путем случайной перестройки отдельных решений (оператор мутации т).

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

Рассмотрим одноточечный оператор кроссинговера Холлан- да, который реализуется следующим образом. Сначала случайным образом определяется точка скрещивания. Затем цепочка генов, ограниченная точкой скрещивания одной хромосомы, меняется местами с аналогичной частью генов второй хромосомы (см. рис. 3.36), т. е. путем перекомпоновки двух родительских решений генерируются два качественно новых решения (потомки). Помимо одноточечного применяются и многоточечные крос- синговеры. В результате применения сг могут появиться повторяющиеся кодовые комбинации хромосом. Поэтому для использования генетического алгоритма в задачах оптимизации необходимо разрабатывать новые типы операторов сг.

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

Значительное улучшение качества и скорости сходимости ГА дает комбинирование ГА с классическими детерминирован-

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

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

1) случайный выбор пар;

2) предпочтительный выбор на основе функции фитнесса.

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

• формирование репродукционной группы из всех решений, образовавшихся в популяции Р'\

• естественный отбор решений в следующую Р*1 популяцию.

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

Дата добавления: 2015-04-29