Найти min Z =
при условии аj ≤ xj ≤ bj; j = 1 ÷ n,
где – выпуклая функция.
1. Выписываем область допустимых значений ω(аj ≤ xj ≤ bj); где j=1÷n.
2. Подготавливаем начальный вектор (а1, а2,..., аn) = (x1нижняя граница, x2нижняя граница,…,xnнижняя граница) = (x10, x20,..., xn0), координатами служат нижние границы измерения координат из области допустимых решений ω.
3. Вводим целевую функцию Z = .
4. Вычисляем целевую функцию при = , Z = f().
5. Вводим счетчик неудачных испытаний S = 0, N = 1000 – контрольное число.
6. Формируем массив случайных чисел λ.
7. Формируем случайный вектор , где Î w, координаты которого вычисляются по правилу xj1 = xjнижняя граница +λj ּxjверхняя граница = аj + λj ּbj.
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 = (x1 - 2)2+(x2 - 1)2
при условиях
0 ≤ x1 ≤ 3,
0 ≤ x2 ≤ 2.
I итерация.
1. Выписываем область допустимых решений ω:
ω 0 ≤ x1 ≤ 3,
0 ≤ x2 ≤ 2.
2. Подготавливаем начальный вектор (x1нижняя граница, x2нижняя граница), (0,0).
3. Вводим целевую функцию Z= (x1 - 2)2+(x2 - 1)2
4. Вычисляем целевую функцию при = , Z =f() = + = 5
Вводим счетчик неудавшихся испытаний S = 0.
5. Формируем массив случайных чисел
λ (0,11; 0,17; 0,20; 0,09; 0,15; 0,71; …)
6. Формируем случайный вектор
= xj нижняя граница + λj ּ xj верхняя граница
= 0 +0,11*3 = 0,33
= 0 +0,17*2 = 0,34
= (0,33; 0,34) Î ω
Схема алгоритма случайного поиска на минимум целевой функции
7. Вычисляем целевую функцию при = ; Z = f(); Z = f() = (x1 - 2)2+(x2 - 1)2= + = (1,67)2 + (0,66)2 = 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)2 + (0,82)2 = 1,96 + 0,67 = 2,63
3. Сравним f() и f()
2,63 < 3,23, испытание удачное.
4. = (0,60; 0,18)
Z=f() = f() = 2,63
и т. д.