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

Найти 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

и т. д.