УМК (1013374), страница 7
Текст из файла (страница 7)
Задать начальную точку x 0 , число ε > 0 для остановки алгоритма,начальные величины шагов по координатным направлениям Δ1 , … , Δ n ≥ ε , ускоряющиймножитель λ > 0 , коэффициент уменьшения шага α > 1 . Положитьy 1 = x 0 , i = 1, k = 0 .Шаг 2. Oсуществить исследующий поиск по выбранному координатномунаправлению:а) если f ( y i + Δ i d i ) < f ( y i ) , т.е.f ( y1i ,…, y ii + Δ i ,…, y ni ) < f ( y1i ,…, y ii ,…, y ni ) ,шаг считается удачным.
В этом случае следует положить y i +1 = y i + Δ i d i иперейти к шагу 3;б) если в п. “а” шаг неудачен, то делается шаг в противоположном направлении.Если f ( y i − Δ i d i ) < f ( y i ) , т.е. f ( y1i ,…, y ii − Δ i ,…, y ni ) < f ( y1i ,…, y ii ,…, y ni ) , шагсчитается удачным. В этом случае следует положить y i +1 = y i − Δ i d i иперейти к шагу 3;в) если в пп. “а” и “б” шаги неудачны, положить y i +1 = y i .Шаг 3.
Проверить условия:а) если i < n , то положить i = i + 1 и перейти к шагу 2 (продолжитьисследующий поиск по оставшимся направлениям);б) если i = n , проверить успешность исследующего поиска:35• если f ( y n +1) < f ( x k ) , перейти к шагу 4;• если f ( y n +1) ≥ f ( x k ) , перейти к шагу 5.Шаг 4. Провести поиск по образцу.
Положитьx k +1 = y n +1 , y 1 = x k +1 + λ ( x k +1 − x k ) ,и перейти к шагу 2.Шаг 5. Проверить условие окончания:а) если все Δ i ≤ ε , то поиск закончить: x ∗ ≅ x k ;i = 1, k = k + 1б) для тех i , для которых Δ i > ε , уменьшить величину шага: Δ i =Δiα. Положитьy 1 = x k , x k +1 = x k , k = k + 1, i = 1 и перейти к шагу 2.З а м е ч а н и е. В алгоритме можно использовать одинаковую величину шага покоординатным направлениям, т.е. вместо Δ 1 , Δ 2 , … , Δ n применять Δ .В. МЕТОД ДЕФОРМИРУЕМОГО МНОГОГРАННИКАПостановка задачиТребуется найти безусловный минимум функции f ( x) многих переменных, т.е.найти такую точку x ∗ ∈ R n , что f ( x ∗ ) = min f ( x) .x∈R nСтратегия поискаВ основу метода деформируемого многогранника, или метода Нелдера–Мида(Nelder–Mead), положено построение последовательности систем n + 1 точекx i (k ), i = 1,...
, n + 1 , которые являются вершинами выпуклого многогранника. Точкисистемы x i (k + 1), i = 1,... , n + 1 , на ( k + 1 )-й итерации совпадают с точками системыx i (k ), i = 1,... , n + 1 ,кромеx i (k ), i = 1,... , n + 1 , т.е.i = h,где точкаx h (k )– наихудшая в системеf (x h (k )) = max f (x i (k )) . Точка x h (k ) заменяется на1 ≤ i ≤ n +1другую точку по специальным правилам, описанным ниже. В результате многогранникидеформируются в зависимости от структуры линий уровня целевой функции,вытягиваясь вдоль длинных наклонных плоскостей, изменяя направление в изогнутыхвпадинах и сжимаясь в окрестности минимума.
Построение последовательностимногогранников заканчивается, когда значения функции в вершинах текущегомногогранника отличаются от значения функции в центре тяжести системыx i (k ), i = 1,... , n + 1; i ≠ h , не более чем на величину ε > 0 .АлгоритмШаг 1. Задать координаты вершин многогранника x 1 , … , x n +1 ; параметрыотражения α , сжатия β , растяжения γ ; число ε > 0 для остановки алгоритма. Положитьk = 0 (последующие шаги 2–6 соответствуют текущему номеру k системы точек).36Шаг 2.
Среди вершин найти «наилучшую» x l и «наихудшую» x h ,соответствующие минимальному и максимальному значениям функции:( )f xl =minj = 1,… , n + 1( )( )f xj ;f xh =maxj = 1,… , n + 1( )f xj ,а также точку x s , в которой достигается второе по величине после максимального( )значение функции f x s .Шаг 3. Найти «центр тяжести» всех вершин многогранника, за исключением«наихудшей» x h :⎤ 1 n +11 ⎡ n +1x n+2 = ⎢ ∑ x j − x h ⎥ = ∑ x j .n ⎢⎣ j =1⎥⎦ n j =1j ≠hШаг 4.
Проверить условие окончания:12 ⎫2⎧ 1 n +1⎪⎪jn+2f x − f xа) если σ = ⎨⎬ ≤ ε , процесс поиска можно завершить∑1n+j =1⎪⎩⎪⎭и в качестве приближенного решения взять наилучшую точку текущегомногогранника: x ∗ ≅ x l ;б) если σ > ε , продолжать процесс.[( ) ()]Шаг 5. Выполнить операцию отражения «наихудшей» вершины через центртяжести x n + 2 (рис. 6, а):()x n +3 = x n + 2 + α x n + 2 − x h .Шаг 6. Проверить выполнение условий:() ( )а) если f x n + 3 ≤ f x l , выполнить операцию растяжения (рис. 6, б):()x n + 4 = x n + 2 + γ x n +3 − x n + 2 .Найти вершины нового многогранника:• если() ( )f x n + 4 < f x l , то вершина x h заменяется на x n +4 (приn=2многогранник будет содержать вершины x 1 , x 3 , x 6 ). Затем следует положитьk = k + 1 и перейти к шагу 2;• если() ( )f x n + 4 ≥ f x l , то вершина x h заменяется на x n +3 (приn=2многогранник будет содержать вершины x 1 , x 3 , x 5 ).
Далее следует положитьk = k + 1 и перейти к шагу 2;( ) () ( )б) если f x s < f x n +3 ≤ f x h , то выполнить операцию сжатия (рис. 6, в):()x n +5 = x n + 2 + β x h − x n + 2 .Заменить вершину x h на x n +5 , положить k = k + 1 и перейти к шагу 2 (при n = 2многогранник будет содержать вершины x 1 , x 3 , x 7 );37x2 = xhxn+2 = x 4x2 = xh1x =xx 3 = x n +1 = x sx1 = x ll(x n +3 = x 5xn+2 = x 4(x 3 = x n +1 = x sx n +3 = x 5) ( )f xn+4 ≥ f xl) ( )f xn+4 < f xlx n+4 = x 6абx2 = xhx2 = xhx n +5 = x 7x1 = x lx 3 = x n +1xn+2 = x 4x1 = x l= xsx 3 = x n +1 = x sxn+2 = x 4x n +3 = x 5x n +3 = x 5вгРис.
6( ) () ( )в) если f x l < f x n +3 ≤ f x s , то вершину x h заменить на x n +3 . При этомследует положить k = k + 1 и перейти к шагу 2;() ( )г) если f x n + 3 > f x h , выполнить операцию редукции (рис. 6, г). Формируетсяновый многогранник с уменьшенными вдвое сторонами и вершиной x l :()x j = x l + 0,5 x j − x l , j = 1, … , n + 1 .При этом следует положить k = k + 1 и перейти к шагу 2.З а м е ч а н и е. Нелдер и Мид рекомендуют использовать параметрыα = 1; β = 0,5; γ = 2 ; Павиани (Paviani): α = 1 ; 0,4 ≤ β ≤ 0,6 ; 2,8 ≤ γ ≤ 3 ; Паркинсон иХатчинсон (Parkinson, Hutchinson): α = 2; β = 0,25; γ = 2,5 .
В последнем случае в рамкахоперации отражения фактически выполняется растяжение.Г. МЕТОДЫ СЛУЧАЙНОГО ПОИСКАПостановка задачиТребуется найти безусловный минимум функции f ( x) многих переменных, т.е.найти такую точку x ∗ ∈ R n , что f ( x ∗ ) = min f ( x) .x∈R38nГ.1. Адаптивный метод случайного поискаСтратегия поискаЗадается начальная точка x 0 . Каждая последующая точка находится по формулеx k +1 = x k + t k ξ k ,где t k > 0 – величина шага; ξ k – случайный вектор единичной длины, определяющийнаправление поиска; k – номер итерации. На текущей итерации при помощигенерирования случайных векторов ξ k получаются точки, лежащие на гиперсферерадиуса t k с центром в точке x k (рис.
7). Если значение функции в полученной точкене меньше, чем в центре, шаг считается неудачным (точки y 1 , y 2 при поиске из x 0 ;y 1 , y 3 при поиске из x 1 ). Если число неудачных шагов из текущей точки достигаетнекоторого числа M , дальнейший поиск продолжается из той же точки, но с меньшимшагом до тех пор, пока он не станет меньше заранее заданной величины R .
Если жезначение функции в полученной точке меньше, чем в центре, шаг считается удачным, и внайденном направлении делается увеличенный шаг, играющий роль ускоряющего шага(как при поиске по образцу в методе конфигураций). Если при этом значение функцииснова меньше, чем в центре, направление считается удачным и дальнейший поискпродолжается из этой точки (точки z 3 = x 1 при поиске из x 0 , z 4 = x 2 при поиске изx 1 ). Если же значение функции не стало меньше, чем в центре, направлениесчитается неудачным и поиск продолжается из старого центра (в точке y 2 при поискеиз x 1 функция меньше, чем в x 1 , а в точке z 2 уже не меньше, поэтому направление(z2)− x 1 – неудачное).x2x∗y3z4 = x2z 3 = x1y2y3y14yx0y1z2y2Рис. 739x1АлгоритмШаг 1. Задать начальную точку x 0 , коэффициенты расширения α ≥ 1 и сжатия0 < β < 1 , M – максимальное число неудачно выполненных испытаний на текущейитерации, t 0 = 1 – начальную величину шага, R - минимальную величину шага, N –максимальное число итераций.
Положить k = 0, j = 1 .(Шаг 2. Получить случайный вектор ξ j = ξ1 j , … , ξn jвеличина, равномерно распределенная на интервале [ −1,1] .jkШаг 3. Вычислить y = x + t kξjξj)T, где ξi j – случайная.Шаг 4. Проверить выполнение условий:( ) ( )а) если f y j < f x k , шаг удачный. Положить zj()= xk + α y j − xk иопределить, является ли текущее направление y j − x k удачным:( ) ( )f z j < f xk ,• еслитонаправлениепоискаудачное.Положитьx k +1 = z j , t k +1 = α t k , k = k + 1 и проверить условие окончания.
Еслиk < N , положить j = 1 и перейти к шагу 2. Если k = N , поиск завершить:x∗ ≅ xk ;( ) ( )б) если f ( y ) ≥ f ( x ) , шаг неудачный и перейти к шагу 5.• если f z j ≥ f x k , направление поиска неудачное, перейти к шагу 5;jkШаг 5. Оценить число неудачных шагов из текущей точки:а) если j < M , следует положить j = j + 1 и перейти к шагу 2;б) если j = M , проверить условие окончания:( ) ( )• если t k ≤ R , процесс закончить: x ∗ ≅ x k , f x ∗ ≅ f x k ;• если t k > R , положить t k = β t k , j = 1 и перейти к шагу 2.З а м е ч а н и я.1.
Величина ξi j , равномерно распределенная на интервале [ −1,1] , генерируетсяобычно с помошью датчиков псевдослучайных чисел на ЭВМ. Вырабатываетсяслучайная величина ηij , равномерно распределенная на [ 0,1] , а затем используетсялинейное преобразование: ξij = 2 ηij − 1 .2. Шумер и Стейглиц (Schumer, Steiglitz) рекомендуют следующие параметрыалгоритма: α = 1,618; β = 0,618; M = 3n . При α = 1 точка z j на шаге 4 совпадает с y j ,т.е. аналог поиска по образцу не производится. Начальный шаг t 0 ≥ R можно задатьпроизвольно.3. Если выполнено условие окончания t k ≤ R , то в качестве ответа можноиспользовать любую точку внутри шара с радиусом t k и центром в точке x k .40Г.2.
Метод случайного поиска с возвратом при неудачном шагеСтратегия поискаЗадается начальная точка x 0 . Каждая последующая точка находится по формулеx k +1 = x k + t k ξ k ,где t k > 0 – величина шага; ξ k – случайный вектор единичной длины, определяющийнаправление поиска; k – номер итерации. На текущей итерации при помощигенерирования случайных векторов ξ k получаются точки, лежащие на гиперсферерадиуса t k с центром в точке x k (рис.
8). Если значение функции в полученной точкене меньше, чем в центре, шаг считается неудачным (точки y 1 , y 2 при поиске из x 0 ;y 1 , y 2 , y 3 при поиске из x 1 ), происходит возврат в текущий центр и поискпродолжается. Если число неудачных шагов из текущей точки достигает некоторогочисла M , дальнейший поиск продолжается из той же точки, но с меньшим шагом до техпор, пока он не станет меньше заранее заданной величины R.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
