Бодянский В.Е., Руденко Г.О. - ИНС архитектура обучение применение (778912), страница 19
Текст из файла (страница 19)
Очевидно, что с уменьшением угла раскрытия конуса, вследствие инерционности такого рода поиска, возможности поворота вектора уменьшаются. Это означает, что при резком изменении направления градиента алгоритм будет некоторое время двигаться в старом направлении, а затем вектор,~ постепенно перестроится на новое правильное направление. 116 4 ОБУЧЕНИЕ НЕЙРОННЫХ СЕТЕЙ ь(2) Рис.
4.16 — Обучение в пространстве параметров ~,. на основе глобального случайного поиска с направляющим конусом Потери на поиск для такого алгоритма при правильном расположении вектора .~ (в направлении оврага или антиградиентном) уменьшаются с уменьшением угла раскрытия конуса. Увеличение угла у приводит к большей мобильности и «верткости» поиска, однако при этом возрастают и потери на поиск.
Очевидно, что оптимальные значения параметров поиска зависят целиком от вида целевой функции Е,. (ь,) и ее особенностей. В задачах, где эта функция ввиду большой сложности имеет много экстремумов, по-видимому, наиболее целесообразным представляется использование глобального случайного поиска с самообучением 12161. 4.5.2 Алгоритмы эволюционного планирования В конце 50-х годов прошлого века известным английским статистиком Дж. Боксом был предложен подход к оптимизации технологических процессов, получивший название эволюционного планирования (ЕЪ'ОР) 12071 и породивший множество алгоритмов оптимизации, не требующих вычисления производных целевой функции и эффективно работающих в условиях сильной «зашумленности» наблюдений.
И хотя в «чистом виде» ЕУОР сегодня практически не применяется (тем более для обучения нейронных сетей), с 117 методологической точки зрения полезно рассмотреть идеи, положенные в его основу. Основная идея состоит в том, что достаточно произвольным образом выбирается некоторый вектор параметров,и,.(й), именуемый базовой точкой, и оценивается значение целевой функции Е,.1„и,.1Й)) в точках, окружающих базовую. Этот набор точек, включая базовую, называется образцом. В двумерном случае (две оптимизируемые переменные) — это квадратный образец, показанный на рис. 4.17.
~и', ® ~ Пробная точка , и,. (й) ° ~~~1 ) ° Базовая точка Рис. 4.17 — Квадратный образец (4.292) ~ и'~ Ж + 1) — г в' ~ Ж) и вокруг нее строится аналогичный образец. Если ни одна из пробных угловых точек не имеет преимуществ перед базовой, размеры образца уменьшаются, после чего поиск оптимума продолжается. В задачах большей размерности вычисление значений целевой функции производится во всех вершинах, а также в центре гиперкуба, т.е. в точках так называемого кубического образца, а количество вычислений целевой функции составляет при этом (4.293) где л — размерность пространства оптимизируемых переменных.
Поэтому несмотря на логическую простоту поиска по кубическому образцу, возникает необходимость использования более эффективных методов. Дальнейшим развитием эволюционного планирования является вращаемое эволюционное планирование (КОДОР) [1901, в котором образец разворачивается вокруг базовой точки и может как увеличивать, так и 118 Затем наилучшая из пяти исследуемых точек „и,.(Й),,и,.(Й),...,,и,.(~с), соответствующая минимальному значению целевой функции Е,.
(„и,. (й))„р = 0,1,...,4 обозначаемая, и,. (/с), выбирается в качестве базовой для следующего шага оптимизации 4 ОБУЧЕНИЕ НЕЙРОННЫХ СЕТЕЙ уменьшать свои размеры. Несмотря на то, что поиск на основе КОЧОР приобретает глобальные свойства, большее количество наблюдений и слабая формализованность ограничивают его применимость. Гораздо более эффективным алгоритмом эволюционного планирования является симплексный поиск, предложенный У. Спендли, Дж. Хекстом и Ф. Химсвортом 12081. Следует отметить, что этот алгоритм не имеет никакого отношения к симплекс-методу линейного программирования, а сходство названий имеет случайный характер. Процедура симплекс ного поиска базируется на том, что экспериментальным образцом, содержащим наименьшее количество точек, является регулярный симплекс.
Симплекс в п-мерном пространстве (далее для сохранения обозначений, традиционно принятых в геометрии симплексов, мы будем полагать, что число настраиваемых параметров равно п) представляет собой многогранник, образованный л+1 равноотстоящими друг от друга точками-вершинами.
Аналитически — это множество точек вида (4.294) где ˄— коэффициенты, подчиняющиеся ограничениям ~Л =1, Л„) О, р =1,2,...,в+1„ (4.295) р=1 119 а и,. =(рил,...,р и,.„,..., ж,,„) — координаты р-й вершины симплекса в пмерном пространстве. Несложно видеть, что в случае двух параметров-переменных симплексом является треугольник, в трехмерном пространстве симплекс — это тетраэдр и т.д.
В алгоритме симплексного поиска используется важное свойство симплексов, согласно которому, новый симплекс можно построить на любой грани начального симплекса путем переноса выбранной вершины на надлежащее расстояние вдоль прямой, проведенной через центр тяжести остальных вершин исходного симплекса. Полученная таким образом точка является вершиной нового симплекса, а выбранная при построении вершина начального симплекса исключается. Таким образом, при переходе к новому симплексу требуется только одно вычисление значения целевой функции. Рис, 4.18 иллюстрирует процедуру построения симплекса на плоскости (л = 2).
Работа алгоритма симплексного поиска начинается с построения регулярного симплекса в пространстве настраиваемых параметров и оценивания значений целевой функции в каждой из вершин. При этом определяется вершина, которой соответствует наибольшее значение целевой функции. Затем эта «наихудшая» вершина проецируется через центр тяжести остальных вершин симплекса в новую точку, которая используется в качестве вершины нового симплекса. Если целевая функция убывает достаточно плавно, 1Иг з 1гг2 а) б) Рис. 4.18 — Построение нового симплекса: а) начальный симплекс, и,, 2112,г 2И,; б) новый симплекс,и..
2и,„,и, В условиях помех симплекс-поиск находит область минимума с точностью до своих размеров и зацикливается вокруг минимума. Если же точка минимума будет дрейфовать, то и симплекс последует за ней, описывая спираль вокруг траектории смещающегося во времени оптимума. Это свойство положено в основу принципа адаптационной оптимизации [2101, на основе которого кроме собственно симплекс-метода было построено достаточно много алгоритмов. Формально симплекс-поиск можно описать следующим образом. Из аналитической геометрии известно, что координаты вершин регулярного симплекса определяются матрицей И', в которой столбцы представляют собой вершины, пронумерованные от 1 до в+1, а строки — координаты от 1 до 12 [215): Иг . 11г . 2 11 ггг-1 г'! гг.г1 /2 , Иг,2 2И/ г [4.296) ОР2Р2...Р, гн-1 2гг 1 11 2гг — (111' ".
„11г '.', 111г ) где р,= " (4п+1+п-1), 12~Г2 (4.297) 120 итерации продолжаются до тех пор, пока симплексом не будет «накрыта» точка минимума, о чем свидетельствует либо циклическое движение вокруг одной вершины, либо повторяющиеся отражения-колебания через одно и то же ребро многогранника. 4 ОБУЧЕНИЕ НЕЙРОННЫХ СЕТЕЙ т~, — параметр, задающий расстояние между вершинами. ПУсть ри,(1с) =(ри,,(/с), и,2(/с),...„~ и,„(/с)) ЯвлЯетсЯ Р-й веРшиной симплекса на 1с -м шаге поиска и пусть Е,( и,. (1с)) — значение целевой функции в этой вершине. Кроме того, отметим те вершины, в которых на 1с -й итерации целевая функция принимает максимальное и минимальное значение: Е,. („и,.
(7с)) = п2ах (Е,. (, и,. (/с)),...,Е,. (р и,. (/с)),..., Е,. („„и,. (/с))), (4.298) Е,.(,и,.(Й)) = ппп (.Е,.(,и,.(Ус)),...,Е,.( и,.(/с)),...,Е,.(„„и,.(й))). р=1,2,...,и+1 Определив центр тяжести всех вершин симплекс а за исключением «наихудшей», и,. (1с) в виде 1 и» „, и,. (Ус) = — ~1 р и,. (1с) — „и,. (Ус) П (4.299) несложно записать алгоритм отражения-движения симплекса в пространстве настраиваемых параметров: (4.300) а+Зир(с) 2и~2и2(с) 6 и/(с) р и2(с+1)' Отраженная точка „„и,, (й) и будет новой вершиной симплекса на (1+ 1) -й итерации поиска.
Алгоритм симплексного поиска характеризуется не только вычислительной простотой, но и высокой эффективностью. Если в качестве меры эффективности рассматривать количество измерений целевой функции на каждом шаге и ошибку определения направления градиента, то качество метода можно оценить с помощью теоремы Брукса (202, 217~, гласящей о том, что максимум критерия 1 Е, = — М(сояО), ~Д (4301) где Д вЂ” количество измерений на каждом шаге; Π— ошибка определения градиента, достигается при Д = и+ 1. Исходя из этого критерия, можно судить о высокой эффективности симплексного поиска, который превосходит случайный поиск в среднем в 1.4 раза (218~. Ускорения поиска можно добиться, отказавшись от регулярности симплекса и управляя его размерами так, как это делается в алгоритме деформируемого многогранника Нелдера-Мида 1209, 2191.
121 В этом алгоритме вместо отражения, задаваемого формулой (4.300), используются следующие операции: отражение — проецирование „и,. (Й) через центр тяжести в соответствии с выражением (4.302) „,„и:,. (Ус) =„„и, (Й) + й(„., и', (Ус) — „и',. (Ус)); растяжение, которое производится в случае, если Е,. („, и,. (1с)) < Е,. (, и,. (/с)), и состоит в том, что вектор „„и,.
(й) — „„, и, (Й) «растягивается» в соответствии с выражением (4.303) ~-~4 и/ ('с) ~н-1 у ( ) У(а+3 у ( ) и+2 у ( ))~ (4.304) Затем „и,.(1с) заменяется на „„и,.(Й) и производится возврат к операции отражения- проецирования для продолжения поиска на (®+1) -м шаге; редукция, которая приводится в случае Е,.(„„и,(/с)) > Е,(„и,(Й)) и состоит в том, что все векторы „и,.(1с) —, и,.(/с), р = 1,2,...,в+1, уменьшаются в два раза с отсчетом от, и,. (й) в соответствии с выражением (4.305) „и,.(1с) =, и',(/с)+0.5(„и',.ф) —, и',.(Ус)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
