Рис. 24. Построение включающег гиперпараллелепипеда (А, В – границы параллелепипеда)

Различают направленный и ненаправленный случайный поиск.

6.2. Ненаправленный случайный поиск

Все случайные испытания строят совершенно независимо от результатов предыдущих. Скорость сходимости такого поиска очень мала, но имеется важное преимущество: возможность решать многоэкстремальные задачи (искать глобальный экстремум). Примером является рассмотренный выше простой случайный поиск.

6.3. Направленный случайный поиск

В этом случае отдельные испытания связаны между собой. Результаты проведенных испытаний используются для формирования последующих. Скорость ходимости таких методов, как правило, выше, но сами методы обычно приводят к локальным экстремумам.

Приведем простейшие алгоритмы направленного случайного поиска.

6.3.1.Алгоритм парной пробы

Вданном алгоритме четко разделены пробный и рабочий шаги. Пусть xk – найденное на k -м шаге наименьшее значение минимизируемой функции f (x).

По равномерному закону генерируется случайный единичный вектор ξ и по обе стороны от исходной точки xk делаются две пробы: проводят вычисление

функции в точках x1,2k = xk ± g ξ , где g -величина пробного шага (рис. 25). Рабочий шаг делается в направлении наименьшего значения целевой функция. Очередное приближение определяется соотношением

xk+1 = xk + ∆xk = xk +a ξ sign (f (xk − gξ) − f (xk + gξ)),

45

1, x ≥ 0,

где sign(x) =

−1, x < 0.

Рис. 25. К алгоритму парной пробы

Особенностью данного алгоритма является его повышенная тенденция к «блужданию». Даже найдя экстремум, алгоритм уводит систему в сторону.

6.3.2. Алгоритм наилучшей пробы

На k -м шаге мы имеем точку xk . Генерируется m случайных единичных

векторов ξ1, ..., ξm .			Делаются пробные шаги в направлениях g ξ1, ..., g ξm и в
точках xk + g ξ , ...,			xk + g ξ	m	вычисляются значения функции (рис. 26). Выби-
	1
рается тот	шаг,	который приводит к наибольшему уменьшению функции:
ξ* = arg min	f (xk	+ g ξi ). В данном направлении делается шаг ∆xk = λ ξ . Па-
i=1,m

раметр λ может определяться как результат минимизации по определенному направлению или выбирается по определенному закону.

С увеличением числа проб выбранное направление приближается к направлению антиградиента − f (x).

Если функция f (x) близка к линейной, то есть возможность ускорить по-

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

Рис. 26. К алгоритму наилучшей пробы

46

6.3.3. Метод статистического градиента

Из исходного состояния xk делается m независимых проб g ξ1 ,..., g ξm и

вычисляются соответствующие значения минимизируемой функции в этих точках (рис. 27). Для каждой пробы запоминются приращения функции

∆f j = f (xk + g ξj )− f (xk ).

m

После этого формируют векторную сумму ∆f = ∑ξj ∆f j . В пределе при

j=1

m → ∞ она совпадает с направлением градиента целевой функции. При конечном m вектор ∆f представляет собой статистическую оценку направления гра-

диента. Рабочий шаг делается в направлении ∆f . Очередное приближение определяется соотношением

xk+1 = xk −λ ∆∆ff .

При выборе оптимального значения λ, которое минимизирует функцию в заданном направлении, получают случайный вариант метода наискорейшего спуска. Существенным преимуществом перед детерминированными алгоритмами является возможность принятия решения о направлении рабочего шага при m < n . При m = n и неслучайных ортогональных рабочих шагах, направленных вдоль осей координат, алгоритм вырождается в градиентный метод.

Рис. 27. К алгоритму статистического градиента

6.3.4. Алгоритм наилучшей пробы с направляющим гиперквадратом

Внутри допустимой области строится гиперквадрат. В этом гиперквадрате случайным образом разбрасывается m точек x1, ..., xm , в которых вычисляются

значения функции (рис. 28). Среди построенных точек выбирают наилучшую. Опираясь на эту точку, строят новый гиперквадрат. Точка, в которой достигается минимум функции на k -м этапе, берется в качестве центра нового гиперквадрата на (k +1) -м этапе. Координаты вершин гиперквадрата на (k +1) -м этапе

определяются соотношениями

aik+1 = xik+1 − bik −2 aik , bik+1 = xik+1 + bik −2 aik ,

где xk – наилучшая точка в гиперквадрате на k -м этапе.

47