<<
>>

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

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

a) Отсечения

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

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

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

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

a) прямые,

b) непрямые,

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

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

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

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

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

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

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

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

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

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

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

Шаблоном является функцияf(x1, ..., xn, p1, ..., pm), в которой x1, ..., xn- это независимые аргументы, а p1,..., pmявляются параметрами, вместо которых подставляют произвольные функции g1(x1, ..., xn), ..., gm(x1, ..., xn). Такие, как например: 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ι доминирует шаблон f2,при условии, что f1и f2различны, а f2 удовлетворяет fl. К примеру: f1(p1, p2) = p1*sin(p2), f2(p) = p*sin(p), где f доминирует значению f2: f2(p) = f1(p, p).

Пересечение функций или шаблонов g1, ..., gnназывают множество шаблонов, которые как F = {f1, .,fm}, :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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,p3)}, T = {(P1,P1), (p2,P1), (p3,p2)},

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

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

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

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

^1)*^2

<< | >>
Источник: Аль-Бареда Али Яхья Сенан. МОДЕЛИ И АЛГОРИТМЫ СИНТЕЗА ОПТИМАЛЬНОГО УПРАВЛЕНИЯ В БИОТЕХНИЧЕСКИХ СИСТЕМАХ РЕАБИЛИТАЦИОННОГО ТИПА НА ОСНОВЕ ТЕХНОЛОГИЙ НЕЙРОННЫХ СЕТЕЙ. Диссертация на соискание ученой степени кандидата технических наук. МОСКВА - 2018. 2018

Скачать оригинал источника

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

  1.   3.2. Философские проблемы информатики 3.2.1. История становления информатики как междисциплинарного направления во второй половине XX в.  
  2. Оглавление
  3. Введение
  4. Генетические алгоритмы синтеза нейронных сетей для систем управления
  5. Цель и задачи исследования
  6. Выбор структурных решений для нейросетевого управления экзоскелетом
  7. Вариационный генетический алгоритма для синтеза системы управления с одним критерием оптимизации
  8. Выводы третьего раздела
  9. Заключение
  10. Список литературы