Алгоритм нелокального случайного поиска на минимум целевой функции

Найти min Z =

при условии а_j ≤ x_j ≤ b_j; j = 1 ÷ n,

где – выпуклая функция.

1. Выписываем область допустимых значений ω( а_j ≤ x_j ≤ b_j ); где j=1÷n.

2. Подготавливаем начальный вектор (а₁, а₂, ..., а_n) = (x_{1нижняя граница}, x_{2нижняя граница},…, x_{nнижняя граница}) = ( x₁⁰, x₂⁰, ..., x_n⁰ ), координатами служат нижние границы измерения координат из области допустимых решений ω.

3. Вводим целевую функцию Z = .

4. Вычисляем целевую функцию при = , Z = f( ).

5. Вводим счетчик неудачных испытаний S = 0, N = 1000 – контрольное число.

6. Формируем массив случайных чисел λ.

7. Формируем случайный вектор , где  , координаты которого вычисляются по правилу x_j¹ = x_{jнижняя граница} + λ_j ּx_{jверхняя граница} = а_j + λ_j ּb_j.

8. Вычисляем целевую функцию при = , Z = f( ).

9. Сравниваем f( ) и f( ).

10. Если испытание удачное, то есть если f( ) <f( ), то переход к пункту 11, иначе переход к пункту 12.

11. = и Z =f( ) = f( ).

12. Переход к пункту 7.

13. Если f( ) ≥ f( ), то ведем счет неудачных испытаний S = S + 1.

14. Сравниваем S с N, где N – контрольное число неудачных испытаний. Если S ≤ N, то переходим к пункту 7, иначе переход к пункту 15.

15. Конец вычислений. Запись ответа Z =f( ) и .

Пример 18

Найти minZ = (x₁ - 2)²+(x₂ - 1)²

при условиях

0 ≤ x₁ ≤ 3,

0 ≤ x₂ ≤ 2.

I итерация.

1. В ыписываем область допустимых решений ω:

ω 0 ≤ x₁ ≤ 3,

0 ≤ x₂ ≤ 2.

2. Подготавливаем начальный вектор (x_{1нижняя граница}, x_{2нижняя граница}), (0,0).

3. Вводим целевую функцию Z= (x₁ - 2)²+(x₂ - 1)²

4. Вычисляем целевую функцию при = , Z =f( ) = + = 5

Вводим счетчик неудавшихся испытаний S = 0.

5. Формируем массив случайных чисел

λ (0,11; 0,17; 0,20; 0,09; 0,15; 0,71; … )

6. Формируем случайный вектор

= x_{j нижняя граница} + λ_j ּ x_{j верхняя граница}

= 0 +0,11*3 = 0,33

= 0 +0,17*2 = 0,34

= (0,33; 0,34)  ω

Схема алгоритма случайного поиска на минимум целевой функции

7. Вычисляем целевую функцию при = ; Z = f( ); Z = f( ) = (x₁ - 2)²+(x₂ - 1)²= + = (1,67)² + (0,66)² = 2,79 + 0,44 = 3,23

8. Сравниваем f( ) и f( ), 3,23 < 5, испытание удачное.

9. = (0,33; 0,34); Z =f( ) =f( ) = 3,23

II итерация

1. Формируем случайный вектор

= 0 + 0,20*3 = 0,60

= 0 + 0,09*2 = 0,18

( 0,60; 0,18)  ω

2. Вычисляем Z =f( ) = + = (1,40)² + (0,82)² = 1,96 + 0,67 = 2,63

3. Сравним f( ) и f( )

2,63 < 3,23, испытание удачное.

4. = (0,60; 0,18)

Z=f( ) = f( ) = 2,63

и т. д.

Индивидуальные задания 8

Решить задачи 1-15 методом нелокального случайного поиска, в четных номерах находить максимум целевой функции, а в нечетных – минимум.

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

Особенности метода локального случайного поиска

Отличие алгоритма локального случайного поиска от алгоритма нелокального случайного поиска только в формировании случайного вектора . Координаты вектора случайных чисел вычисляются по формуле: = x_j⁰ +P_j , где - заданное для данной задачи число, например,

=1, т. е. = + · 1.

Вектор сам является случайным вектором, координаты которого принадлежат какому-то заданному интервалу, ≤ P_j ≤ . Например, интервалу [-1, 1]. Координаты вектора формируются по формуле P_j =A+ λ_jּB, где λ_j - число из массива случайных чисел λ.

Следовательно, = x_j⁰ + (A+ λ_jּB) · .

В этой задаче можно значение менять по формуле = до какого-то заданного предела .