lopt4 (Лекционный курс), страница 2

Если при этом значение функцииснова меньше, чем в центре, направление считается удачным и дальнейший поискпродолжается из этой точки (точки 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. Если же значение функциив полученной точке меньше, чем в центре, шаг считается удачным и дальнейший поискпродолжается из этой точки.x2x∗y4 = x2y3y 3 = x1y2y1x0y1y2x1Рис. 841Г.3.

Метод наилучшей пробыСтратегия поискаЗадается начальная точка x 0 . Каждая последующая точка находится по формулеx k +1 = x k + t k ξ k ,где t k > 0 – величина шага; ξ k – случайный вектор единичной длины, определяющийнаправление поиска; k – номер итерации. На текущей итерации при помощигенерирования случайных векторов ξ k получается M точек y 1 ,..., y M , лежащих нагиперсфере радиуса t k с центром в точке x k (рис. 9). Среди полученных точеквыбирается точка y m , в которой значение функции наименьшее. Если в выбранной точкезначение функции меньше, чем в центре, то дальнейший поиск продолжается из этойточки. Иначе поиск продолжается из старого центра, но с меньшим шагом до тех пор,пока он не станет меньше заранее заданной величины R .x2yMx∗ymy3x0y M −1y1y2x1Рис. 942.