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

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

a) Отсечения

b) Комбинаторные

c) Приближенные.

Генетические алгоритмы (ГА) относят - к третьему типу.

a) прямые,

b) непрямые,

c) отображающие.

Схема ГА представлена на рисунке 1.9.

Рисунок 1.9 - Схема генетического алгоритма

Хорошо зарекомендовали себя в решении различного рода задач оптимизации адаптивные свойства ГА. У ГА имеется свойство неявного параллелизма, что позволяет ему динамически, как отыскивать, так и исследовать области, которые содержат либо локальные, либо глобальные оптимумы. Данные свойства Г позволяют при его работе в динамически изменяющейся среде оптимизировать функционал Q(x).

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

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

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

3. Кроме этого, возможно, что области допустимых решений несвязны и не выпуклы. Меру близости решений указать затруднительно, так как у «близких» значений x₁χ₂?Gмогут иметься сколь угодно далеких значений Q(x₁)и Q(x₂). Чтобы определить близость решения в этих задачах используют различные техники, которые в основном зависят от вида задач.

Чтобы преодолеть эти трудности, предложены различные модификации Г , которые довольно успешно справляются с решением задач такого класса. Одна из этих модификаций - алгоритм генетического программирования (ГП) [28, 41].

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

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

Шаблоном является функцияf(x₁, ..., x_n, p₁, ..., p_m), в которой x₁, ..., x_n- это независимые аргументы, а p₁,..., p_mявляются параметрами, вместо которых подставляют произвольные функции g₁(x₁, ..., x_n), ..., g_m(x₁, ..., x_n). Такие, как например: f(x, p) = x + p*sin(p), f(x, x*x) = x + x*x*sin(x*x).

Функция может удовлетворять некоторому шаблону, если в ней будут такие параметры, когда при их подстановке в шаблон может получиться тождественная функция. Шаблон с такими параметрами называют переводом в функцию. К примеру, функцией g(x) = x*x*sin(x*x) удовлетворяется шаблон f(p) = p*sin(p), а fx*x) - перевод fв g.

Шаблон fι доминирует шаблон f₂,при условии, что f₁и f₂различны, а f₂ удовлетворяет fl. К примеру: f₁(p₁, p₂) = p1*sin(p2), f2(p) = p*sin(p), где f доминирует значению f₂: f₂(p) = f₁(p, p).

Пересечение функций или шаблонов g₁, ..., g_nназывают множество шаблонов, которые как F = {f₁, .,f_m}, :

1. показателем g_iудовлетворяется fдля всех i, j;

2. нет таких iили j, что fдоминируетfj;

3. нет шаблонаfкоторый бы удовлетворялся g_iи доминировался бы каким- нибудь шаблоном из F.

Рассмотрим алгоритм поиска шаблонов. Для алгоритма исходная информация - это множество выражений, либо деревьев. На основе данного множества составляем список уникальных поддеревьев, который упорядочен по возрастанию глубины. Например, множество подвыражений: x₂+x₃, x₁*x₂, x₁*(x₂+x₃), sin(x₂+x₃), exp(x₁*x₂) или множество выражений: x₁*(x₂+x₃), sin(x₂+x₃), exp(x1*x2)∙

Целью алгоритма является поиск шаблона, который удовлетворяет эти поддеревья. Причём осуществляется поиск в соответствии с такими правилами, как:

1. Каждому шаблону должно удовлетворять хоть бы два подвыражения.

2. Если у f₁доминируется f₂и нет подвыражения, которым удовлетворяется f₁,но не удовлетворяется f₂,тоf₁нужно отбросить.

В процессе выполнения алгоритма идет перебор в глубину всех сочетаний поддеревьев.

Если каким-либо сочетанием образуется пустое пересечение, то не рассматриваются другие сочетания, «содержащие» это пересечение.

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

Этапы процесса нахождения пересечения функций:

1. Процесс определение комплементарных операндов.

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

3. Этап составление шаблона и назначение параметров для всех комбинаций.

4. Процесс по удалению дублирующих шаблонов.

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

6. Этап удаления доминирующих шаблонов.

7. Процесс составления переводов в функции полученных шаблонов, участвующих в пересечении.

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

Допускаем, что операнды а и bподдеревьев - это функции, и они удовлетворяют множеству шаблонов F₁,а операнд b- F₂.В этом случае пересечением а и bбудет подмножество F₁∩F₂, из которого исключили доминирующие шаблоны.

При ситуации, когда операнд а шаблона - это перевод некого шаблона f, операнд bподдерева - это функция, и он удовлетворяет множеству шаблонов F, F₁ - подмножество F, поэтому fудовлетворяет всему объему элементов F₁. Тогда пересечением а и bбудет множество F₁, из которого исключаются доминирующие шаблоны.

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

f1 = t1(a11, a12, ...) * t2(b11, b12, ...) * ... * C1 * C2 * ... * d11 * d12* ...

f2 = t1(a21, a22, ...) * t2(b21, b22, ...) * ... * C1 * C2 * ... * d21 * d22 * ...,

где значение t - является шаблонами пересечения операндов, значение C - это переменные, значение d - это некомплементарные операнды.

Основу шаблона составляют комплементарные операнды (tи C), а остальные операнды заменяют параметрами:

f3 = t1(p11, P12, ...) * t2(p21, P22, ∙∙∙) * ∙∙∙ * C1 * C2 * ... * p31 * P32 *∙∙∙

Шаги процесса замены операндов исходных поддеревьев параметрами: Определение уникальных операндов. Например,

1. f = t1(x1, x1)*t2(x1, x1+x2)*x1*(x2+x3)*(x2+x3), f = t1(p1, p1)*t2(p1, P2)*P1*P3*P3 .

2. Сравнение соответствующих операндов шаблону t, например,

R = {(P1,P1), (P1,P2), (P1,P2), (P2,p₃)}, T = {(P1,P1), (p2,P1), (p3,p2)},

P = {1, 2, 2, 3}.

3. Сравнение с элементами множества Tпар некомплементарных операндов, полученного на шаге № 2.

4. Назначение параметров операндам, которые не образовали пары на шагах №2 и №3.

аждое из поддеревьев на первом шаге рассматривают по отдельности, производят сравнение аргументов шаблонов, а также других операндов между собой и замену их параметрами. Далее производят аналогичную операцию, но рассматривают уже пары, которые соответствуют аргументам шаблонов. На шаге №3 назначают параметры некомплементарным операндам, чьи пары совпадают с элементами множества, которое полученное на шаге №2. В этом случае возможно создание нескольких вариантов назначения параметров. Сопоставление остальных операндов функций производится на последнем шаге с учётом того, сколько раз они повторяются. Например, если исходные функции: f₁=t₁(x₁,

^1)*^2