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

Найти 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. Формируем случайный вектор , где Î w, координаты которого вычисляются по правилу 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

и т. д.