где Ax,+ , =! " "Р" (.+ ) < (0; (11

а - величина шага смеш,ения; Ej+i - случайный единичный

вектор; Е = (i, ..... е„)-

На рис. И.9 представлена блок-схема алгоритма (П.40). В начальный момент система делает шаг Ax+j в случайном направлении из исходного состояния х,, причем в памяти уже находится значение функции качества J (х,) для этого состояния. Затем определяется новое значение функции качества J (Xi+i), которое сравнивается с запомненным J (х,). В случае уменьшения функции качества (АУ -< 0) вновь делается случайный шаг Ax+g и запоминаются его компоненты. В случае увеличения функции качества (АУ > 0) система делает обратный шаг- Ax+j, компоненты которого были запомнены раньше. Функция качества в этом состоянии У (х,) определяется вновь и запоминается, после чего делается новый шаг в случайном направлении. Алгоритм эффективен даже в случае нестационарных функций качества, изменяющихся во времени по тем или иным причинам.

Локальный случайный поиск с пересчетом. Этот метод поиска отличается от предыдущего тем, что система не возвращается при неудачном шаге назад в исходное состояние, а делает «пересчитанный» случайный шаг в новое состояние, при котором учитывается исходное состояние.

Алгоритм поиска записывается в виде следующей рекуррентной формулы:

Ах,+ =

аЕ,1 при У (Xi)<y; ,;

- AXj + й Е,- +1 при

У (xi)>y;+,;

(11.41)

Определение

Сравнение

Запоминание

Обратный шаг

Определение

где У/ = min У (х,) - наи-/=1. 2..... i

меньшее значение функции

качества за / предыдущих

Пересчет пВратнпгп шага

Рис. 11.10

Этот алгоритм используется в основном для случаев стационарной функции качества или при отсутствии помех. Поиск с пересчетом сокращает количество измерений функции качества, что оправдано при отсутствии помех.

Блок-схема поиска представлена на рис. П. 10. Из схемы видно, что в процедуре поиска отсутствует определение J (лг;) после неудачного шага, а устройство памяти / (л:) освобождается от дополнительной информации.

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

В соответствии с методом из исходного состояния Xj делается m случайных пробных шагов аE/+i, aEf+1, oEji. В полученных смещенных точках x,-+i = л:,-+ aE{+i, где /- 1, 2, т, производится вычисление значений функции качества /(x-i) и запоминается состояние, которое привело К минимальному значению:

У*(х{.) = тшУ(л;,. -fflE/j),/= I,2,...,m. (11.42)

Далее производится рабочий шаг в этом выбранном направлении:

Дх.-+,=йЕ!,, (11.43)

где E/+I - случайный единичный вектор наилучшей пробы.

с увеличением числа пробных шагов т случайно выбранное направление поиска все больше приближается к направлению, обратному градиенту.

Алгоритм поиска (11.42) имеет недостаток, связанный с возможностью попадания в такую зону, когда рабочий шаг делается в сторону увеличения функции качества, например если все пробные шаги привели к увеличению функции качества.

Модификация в этом случае осуществляется таким образом:

, . при J* (х{,Л > J (xi)\

при /*(х/,)<У(хО. »

В соответствии с (11.44) система сделает рабочий шаг вдоль наилучшей пробы только тогда, когда минимальное значение J* (Хг+ ) из всех проб не превышает исходного значения J (Xj). Если это условие не выполняется, тогда повторяется цикл из т пробных случайных шагов.

Локальный случайньй поиск по статистическому градиенту. Данный метод поиска используется в тех случаях, когда функцию качества J (х) нельзя представить в регулярном виде и она определяется в зависимости от регулярных параметров (Xj, Хг, х„), а также от случайных параметров (е,, ej,

8п,). Такая ситуация возможна, например, при поиске экстремума в условиях действия помех.

Так как случайный поиск по статистическому градиенту близок по своей сущности к методам стохастической аппроксимации, то рассмотрим предварительно некоторые процедуры стохастической аппроксимации.

При наличии случайных параметров (8j, 82, 8m) регулярную функцию качества J (х) представим в виде случайной функции

Я (х, е)=Я (xi, Ха,..., х„, ei, 82.....ej, (11.45)

где X = (Xj, Х2, .... Xn) - вектор состояний поиска; е = 82, 8„,) - вектор случайных помех. Зная вероятностные характеристики параметров (81, 83, .... е„), например плотность распределения р (е), можно ос-реднить функцию Н (х, е) по этим параметрам и перейти вновь к осредненной регулярной функции качества

J(x) = H{x,z)p{z)dz, (11.46)