Лекция 4
Статистические методы поиска

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

Это объясняется в первую очередь тем, что с ростом размерности задач резко снижается эффективность регулярных методов поиска (детерминированных), так называемое “проклятие размерности”.

Во-вторых, зачастую информация об оптимизируемом объекте слишком мала для того, чтобы можно было применить детерминированные методы.

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

Статистические методы наиболее эффективны при решении задач большой размерности или при поиске глобального экстремума.

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

Статистические алгоритмы обладают рядом достоинств:

простота реализации и отладки программ;
надежность и помехоустойчивость;
универсальность;
возможность введения операций обучения;
возможность введения операций прогнозирования оптимальной точки.

Основными недостатками являются большое количество вычислений минимизируемой функции, медленная сходимость в районе экстремума.

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

Простой случайный поиск

Пусть нам необходимо решить задачу минимизации функции при условии, что . В этой области по равномерному закону выбираем случайную точку и вычисляем в ней значение функции . Затем выбираем таким же образом случайную точку и вычисляем . Запоминаем минимальное из этих значений и точку, в которой значение функции минимально. Далее генерируем новую точку. Делаем N экспериментов, после чего лучшую точку берем в качестве решения задачи (в которой функция имеет минимальное значение) среди всех случайно сгенерированных.

Пусть n - размерность вектора переменных. Объем n-мерного прямоугольника, в котором ведется поиск минимума: .

Если необходимо найти решение с точностью ε_i, i = 1, ..., n, по каждой из переменных, то мы должны попасть в окрестность оптимальной точки с объемом .

Вероятность попадания в эту окрестность при одном испытании равна P_ε = V_ε / V. Вероятность не попадания равна 1 - P_ε.

Испытания независимы, поэтому вероятность не попадания за N экспериментов равна (1 - P_ε)^N. Вероятность того, что мы найдем решение за N испытаний: P = 1 - (1 - P_ε)^N. Нетрудно получить оценку для необходимого числа испытаний N для определения минимума с требуемой точностью:

Опираясь на заданную точность ε_i, i = 1, ..., n, величину V, можно определить P_ε и, задаваясь вероятностью P, посмотреть, как меняется требуемое количество экспериментов N в зависимости от P_ε и P (см. табл.).

P P_ε	0.8	0.9	0.95	0.99	0.999
0.1	16	22	29	444	66
0.025	64	91	119	182	273
0.01	161	230	299	459	688
0.005	322	460	598	919	1379
0.001	1609	2302	2995	4603	6905

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

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

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

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

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

В данном алгоритме четко разделены пробный и рабочий шаги.

Пусть – найденное на k-м шаге наименьшее значение минимизируемой функции . По равномерному закону генерируется случайный единичный вектор и по обе стороны от исходной точки делаются две пробы: проводим вычисление функции в точках , где g - величина пробного шага.

Рабочий шаг делается в направлении наименьшего значения целевой функция. Очередное приближение определяется соотношением

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

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

На k-м шаге мы имеем точку . Генерируется m случайных единичных векторов . Делаются пробные шаги в направлениях и в точках вычисляются значения функции. Выбирается тот шаг, который приводит к наибольшему уменьшению функции: . И в данном направлении делается шаг . Параметр λ может определяться как результат минимизации по определенному направлению или выбирается по определенному закону.

С увеличением числа проб выбранное направление приближается к направлению .

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

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

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

После этого формируем векторную сумму . В пределе при она совпадает с направлением градиента целевой функции. При конечном m вектор представляет собой статистическую оценку направления градиента. Рабочий шаг делается в направлении . Очередное приближение определяется соотношением

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

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

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

Координаты вершин гиперквадрата на (k+1)-м этапе определяются соотношениями:

, ,

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

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

Таким образом на I этапе координаты случайных точек удовлетворяют неравенствам , и – точка с минимальным значением целевой функции.

В алгоритме с обучением стороны гиперквадрата могут регулироваться в соответствии с изменением параметра α по некоторому правилу. В этом случае координаты вершин гиперквадрата на (k+1)-м этапе будут определяться соотношениями

, .

Хорошо выбранное правило регулировки стороны гиперквадрата приводит к достаточно эффективному алгоритму поиска.

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

Алгоритмы глобального поиска

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

Алгоритм 1

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

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

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

Алгоритм 2

Пусть получена некоторая точка локального экстремума

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

такой, что

Из точки с помощью детерминированного алгоритма или направленного случайного поиска получаем точку локального экстремума , в которой заведомо выполняется неравенство .

Далее с помощью случайного поиска определяем новую точку , для которой справедливо неравенство , и снова спуск в точку локального экстремума и т.д.

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

Алгоритм 3

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

Если , точка забывается и ее место занимает точка . Если , то возвращаемся в точку и движемся из нее в новом случайном направлении.

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

Этот метод позволяет найти глобальный экстремум в случае многосвязных допустимых областей.

Алгоритм 4

В допустимой области D разбрасываем m случайных точек и выбираем из них наилучшую, то есть ту, в которой значение функции минимально. Из выбранной точки осуществляем локальный спуск. А далее вокруг траектории спуска образуем запретную область.

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

Поиск прекращается, если в течение заданного числа попыток не удается найти лучшего локального экстремума.

Замечание

Комбинация случайного поиска с детерминированными методами применяется не только для решения многоэкстремальных задач. Часто к такой комбинации прибегают в ситуациях, когда детерминированные методы сталкиваются с теми или иными трудностями (застревают на дне узкого оврага, в седловой точке и т.д.). Шаг в случайном направлении порой позволяет преодолеть такую тупиковую ситуацию для детерминированного алгоритма.

Лекция 4 Статистические методы поиска