Бодянский В.Е., Руденко Г.О. - ИНС архитектура обучение применение (778912), страница 21
Текст из файла (страница 21)
Таким образом алгоритм (4,319) — (4.321) приобретает глобальные свойства. 4.5.3 Генетические алгоритмы Генетические алгоритмы сегодня являются наиболее популярными представителями эволюционных алгоритмов и представляют собой по сути модель размножения биологических организмов, предназначенную для отыскания глобального оптимума многоэкстремальных функций. В основе генетических алгоритмов лежат механизмы натуральной селекции и генетики, реализующие «выживание сильнейших» среди рассматриваемых структур в процессе их эволюции.
Основное отличие процесса оптимизации с помощью генетических алгоритмов состоит в том, что они работают в основном не с параметрами (синаптическими весами), а с закодированным множеством параметров, при этом поиск производится из популяции исходных точек, а для оценки качества используют не приращение целевой функции, а непосредственно ее мгновенное значение, применяя при этом определенные вероятностные правила. Генетические алгоритмы были введены Дж. Холландом 1211, 225~ и с формальной точки зрения представляют собой последовательность операций, моделирующую эволюционные процессы на основе аналогов механизмов генетического наследования и естественного, а иногда и искусственного отбора.
В общем виде генетический алгоритм может быть представлен в виде схемы, приведенной на рис. 4.19. Текущая популяция Репродукция Рис. 4.19 — Схема генетического алгоритма Для описания генетических алгоритмов используется биологическая терминология, где ключевым понятием является хромосома (стринг), представляющая собой вектор (последовательность, цепочку), образованный 127 нулями и единицами, каждая позиция (бит) которого называется геном. Именно в виде хромосом представляется вектор настраиваемых синаптических весов и,. (/с) = (и л(Й), и',,(Й),..., и,.„(/с))', кодируемый либо в двоичном, либо в формате с плавающей точкой. Если для кодирования каждого настраиваемого параметра и „(й) используется М битов, то хромосома, соответствующая вектору синаптических весов ь,.
(Й), имеет пН генов. Алгоритм начинает свою работу с генерации (обычно случайным образом) начальной популяции хромосом И~,. (О) = (, и,'. (О),... „, и,'. (О),...,д в ~ (О)) (здесь р в ~ (О) ( р ил (О) р в ~ (О) р и р~ (О)) — р-я хромосома популяции), размер которой Д часто полагается постоянным. Для каждой из сгенерированных хромосом можно оценить ее приспособленность (тйпеяя), определяемую значением целевой функции Е,( и,(0)) для р-го вектора синаптических весов. Очевидно, что чем меньше значение Е, („и,(0)), тем больше шансов «выжить» в эволюционирующей популяции у р-й хромосомы. Далее начинается процесс репродукции популяции, формируемый генетическими операторами кроссовера, мутации и инверсии и операцией селекции.
Важнейшим генетическим оператором является кроссовер, формирующий хромосомы- потомки путем обмена генетического материала между хромосомами-родителями так, как это показано на рис 4.20. Родители Обмен генами Потомки Рис. 4.20 — Кроссовер Существует множество вариантов кроссовера, простейшим из которых является одноточечный, в котором два случайно выбранных родителя перерезаются в случайно выбранной точке, после чего хромосомы обмениваются своими фрагментами. В задачах обучения искусственных нейронных сетей одноточечный кроссовер представляется малоэффективным, 128 $ $ $ $ $ $ $ 4 ОБУЧЕНИЕ НЕЙРОННЫХ СЕТЕЙ Исходная хромосома Хромосома-мутант Рис.
4.21 — Мутация Как видно, здесь случайно выбранный бит меняет свое состояние на противоположное. Оператор мутации не позволяет процессу обучения «застрять» в локальных экстремумах целевой функции. Оператор инверсии изменяет порядок генов в хромосоме путем их циклической перестановки так, как это показано на рис. 4.22. И хотя в задачах оптимизации инверсия применяется не часто, в обучении ИНС этот оператор позволяет изменять все синаптические веса стринга и,.®).
В результате произошедших скрещиваний, мутаций и инверсий формируется расширенная популяция хромосом, содержащая как исходное множество хромосом-родителей, так и множество потомков. Каждый стринг расширенной популяции оценивается с точки зрения его приспособленности по критерию Е,. (, и,. (О)), р = 1,2,..., Д,..., после чего формируется новая популяция И',(1), содержащая Д(1) хромосом с наименьшими значениями Е,. („и,.).
В этом состоит суть операции селекции. Исходная хромосома Инвертированная хромосома Рис. 4.22 — Инверсия Далее на каждой итерации й процесс репродукции циклически повторяется. Таким образом, генетический алгоритм накапливает удачные решения, «стягивая» популяцию к глобальному экстремуму целевой функции. Схема, приведенная на рис. 4.19, иллюстрирует некую «универсальную» генетическую процедуру, в рамках которой может быть сформировано множество алгоритмов, отличающихся друг от друга параметрами генетических операторов и способами селекции. В качестве важнейших характеристик, определяющих свойства конкретного генетического алгоритма, можно отметить следующие [61: 129 поскольку приводит к изменению только одного синаптического веса „и:,, (1) в стринге „и,.
(й), С тем, чтобы изменить все веса, необходимо использовать и— точечный кроссовер, в котором может участвовать более двух хромосом— родителей. Мутация связана со случайным изменением одного или нескольких генов в хромосоме так, как это показано на рис. 4.21. способ формирования исходной популяции И', (0); количество особей в исходной популяции КО), которое должно быть достаточно большим, чтобы покрыть всю область возможных решений; частота кроссовера, определяемая количеством хромосом в текущей популяции, подвергающимся скрещиванию; вероятность кроссо вера для каждой из хромосом текущей популяции; частота мутаций, определяемая количеством хромосом в текущей популяции подвергающимся изменению; частота инверсий, определяемая количеством хромосом в текущей популяции, подвергающимся циклической перестановке генов; параметр смены поколений 6(/с), определяющий часть текущей популяции Р(1), которая заменяется на каждой итерации, при этом 611) =1 соответствует замене всей популяции в каждом поколении; количество особей в текущей популяции Д(й); стратегия селекции.
Наиболее распространенные модификации генетических алгоритмов основываются, как правило, на управляемом кроссовере и направленной селекции, имитирующими искусственной отбор. Так в адаптивных генетических алгоритмах [б, 22б~ вероятность кроссовера для каждой хромосомы пропорциональна ее приспособленности, при этом скрещиванию подвергаются только наилучшие стринги.
Таким образом, случайный процесс обучения постепенно превращается в детерминированный, а защитой от «застревания» в локальных экстремумах служат нечастые мутации и инверсии менее приспособленных особей. К адаптивным генетическим алгоритмам достаточно близки процедуры с селекцией на основе элитизма [2271, когда к размножению допускаются только лучшие особи в популяции. Известны и другие формы репродукции, например, имитирующие эволюцию на изолированных островах (1я1апд шос1е1я) [226) с редким обменом генетическим материалом, осуществляющие разбиение пространства параметров и независимый поиск в сформированных подпространствах [228~ и т.п.
И хотя, как отмечается в [48, 227), генетические алгоритмы превосходят по скорости случайный поиск, обучение ИНС в реальном времени на основе генетических процедур наталкивается на существенные трудности, определяемые наличием в каждый момент времени множества векторовстрингов синаптических весов. В связи с этим в [229~ описан генетический алгоритм, предназначенный для работы в реальном времени и обладающий повышенной скоростью сходимости.
В этом алгоритме используется только один генетический оператор — кроссовер, причем все особи популяции могут скрещиваться только с одной хромосомой-«королевой» с минимальным значением Е,.(,ь,.(й)). Естественно, что на каждой итерации й «королева» может меняться и именно ее генетический код используется в качестве текущего вектора синаптических весов. 130 4 ОБУЧЕНИЕ НЕЙРОННЫХ СЕТЕЙ Генетические алгоритмы в общем случае могут оперировать не только с векторами-хромосомами, но и с более сложными объектами типа таблиц, списков и графов [6, 2271. Эта способность позволила успешно применить генетические методы не только для обучения параметров ИНС, но и архитектур в целом [230), Дж. Коза предложил подход, получивший название генетическое программирование, в котором популяция образуется не векторами- параметрами, а архитектурами нейронных сетей, представленными в форме потоковых графов.
В процессе мутации графов при сохранении входных и выходных размерностей формируется оптимальная архитектура сети, наилучшим образом приспособленная для решения конкретной задачи. К сожалению, вычислительная громоздкость процедур генетического программирования ограничивает их возможности при решении задач большой размерности в реальном времени. 4.6 Алгоритмы обучения на основе обратного распространения ошибок Рассмотренные выше алгоритмы обучения предназначены либо для настройки синаптических весов единичного нейрона, либо — однослойной нейронной сети.
В задаче обучения многослойных сетей возникают трудности с настройкой весов скрытых слоев, которые могут быть преодолены с помощью специальной процедуры, получившей название алгоритма обратного распространения ошибок или обобщенного дельта правила. Алгоритм обратного распространения впервые был предложен П, Вербосом [23 Ц, но оставался практически неизвестным до его переоткрытия Д. Румельхартом, Дж. Хинтоном и Р. Виллиамсом [23~. Необходимо отметить, что именно отсутствие подходящей процедуры обучения не позволило многослойным сетям получить широкое распространение и затормозило развитие этого направления на много лет. Здесь мы рассмотрим использование концепции обратного распространения применительно к многослойному персептрону, рассмотренному в подразделе 2.3, в задачах, связанных с нелинейным отображением пространства входов, таких, как классификация, диагностика, распознавание образов, адаптивное управление, идентификация и т.д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
