Алгоритм методов штрафных функций

Шаг 1. Задать значения N, J, K, e₁, e₂, e₃, x^o, R^o,

где

e₁, e₂, e₃ - соответственно параметры окончания процедур одномерного и многомерного поиска безусловной оптимизации, а также работы алгоритма штрафных функций;

x^o - начальное приближение для x^*;

R^o - начальный выбор штрафных параметров.

Шаг 2. Построить P(x,R) = W(x) + W(R,g(x),h(x)).

Шаг 3. Найти x^t+1 минимизирующее значение P(x^t+1,R^t) при фиксированном R^t. В качестве начальной точки использовать x^t, а в качестве параметра окончания шага - константу e₂ (возможно и e₁).

Шаг 4. Проверить, выполняется ли условие |P(x^t+1,R^t)-P(x^t,R^t-1)|£e₃.

· если “да” - положить x^t+1=x^T и закончить процесс решения;

· если “нет” - перейти к следующему шагу.

Шаг 5. Положить R^t+1=R^t+DR^t в соответствии с используемым правилом пересчета, после чего вернуться к шагу 2.

13.4.3. Методы прямого поиска

Алгоритм:

Заданы границы значений всех переменных x_i^L, x_i^U, i=1,2,..., N (размерность задачи), допустимая точка x^o, параметр отображения a (рекомендуется a=1,3) и параметры окончания вычислений e и d.

Шаг 1. Построение начального комплекса, состоящего из P допустимых точек(рекомендуется P=2N). Для каждой точки p = 1, 2,...,P-1:

a) случайным образом определить координаты x^p;

b) если x^p - недопустимая точка, то найти центр тяжести x_цт уже найденных точек и положить x^p = x^p + 0.5 (x_цт - x^p); повторять процедуру до тех пор, пока x^p не станет допустимой;

c) если x^p - допустимая точка, повторять a) до тех пор, пока p=P;

d) вычислить W(x^p) для p=0,1,...,P-1.

Шаг 2. Отражение комплекса:

a) выбрать точку x^R, для которой W(x^R) = max W(x^p) = W_max (решается задача минимизации);

b) найти центр тяжести x_цт и новую точку x^m = x_цт + a (x_цт - x^R);

c) если x^m - допустимая точка и W(x^m)³W_max, то уменьшить в два раза расстояние между x^m и центром тяжести x_цт, продолжать поиск, пока W(x^m)<W_max;

d) если x^m - допустимая точка и W(x^m)<W_max, то перейти к шагу 4;

e) если x^m - недопустимая точка, то перейти к шагу 3.

Шаг 3. Корректировка для обеспечения допустимости:

a) если x_i^m < x_i^L(нижняя граница допускаемой области), то положить x_i^m = x_i^L; если x_i^m > x_i^U(верхняя граница допускаемой области), то положить x_i^m = x_i^U;

b) если x^m - недопустимая точка, то уменьшить в два раза расстояние до центра тяжести; продолжать до тех пор, пока x^m не станет допустимой точкой.

Шаг 4. Проверка условий окончания вычислений:

a) положить и ;

b) если и , то вычисления прекратить; в противном случае перейти к шагу 2a.

Методы случайного поиска

Наиболее простой процедурой случайного поиска является прямая выборочная процедура, заключающаяся в разыгрывании на ЭВМ последовательности точек с координатами

x_i = x_i^L +r_i (x_i^U - x_i^L), i=1,2,...,N, (13.20)

где

r_i - случайная величина, равномерно распределенная на интервале [0,1].

После проверки каждой точки на допустимость вычисляются значения целевой функции, которые сравниваются с наилучшим значением, полученным к данному моменту. Если текущая точка дает лучшее значение, то она запоминается, в противном случае - отбрасывается. Процесс прекращается после заданного числа итераций N или по исчерпанию заданного машинного времени. Для получения 90% доверительного интервала величиной e_i (x_i^U - x_i^L), где 0<e<1, для переменной x_i совместный случайный поиск требует

испытаний. При N=5, e_i=0,01 число испытаний оценивается в 2,3 10¹⁰, что исключает возможность непосредственного использования метода.

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

Заданы границы значений всех переменных x_i^L, x_i^U, i=1,2,..., N (размерность задачи), начальные допустимая точка x^o и интервал поиска Dx^o = x_i^U - x_i^L, количество серий Q, количество точек в серии P и параметр окончания вычислений e. Для каждой из серий, начиная с q = 1, необходимо выполнить следующие действия:

Шаг 1. Для i = 1,2,...,N вычислить

x_i^p = x_i^q-1 +r_i Dx^q-1,

где

r_i - случайная величина, равномерно распределенная на интервале [-0,5,0,5].

Шаг 2.

· Если x^p - недопустимая точка и p < P, то повторить шаг 1.

· Если x^p - допустимая точка, то запомнить x^p и W(x^p) и

· если p < P, то повторить шаг 1.

· если p = P, то найти среди всех допустимых точек x^p точку с наименьшим значением W(x^p) и положить ее равной x^q.

Шаг 3. Уменьшить интервал поиска, полагая Dx_i^q = e_i Dx_i^q-1.

Шаг 4.

· Если q > Q, то закончить вычисления.

· В противном случае увеличить q = q + 1 и продолжить вычисления, начиная с шага 1.

13.4.4. Методы линеаризации