3.1.6. Методы случайного поиска

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

Самая общая итерационная формула методов случайного поиска имеет вид

,

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

1. Норма этой векторной величины должна быть ограниченной, чтобы точка оставалась поблизости от точки.

2. Законы распределения должны зависеть от результатов дальнейших испытаний (адаптация случайного поиска).

К простейшим алгоритмам относятся следующие:

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

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

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

Рассмотрим один из модифицированных методов случайного поиска - случайный поиск на гиперсфере.

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

Рис. 13

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

Пример. Щелкнув по значку, откроется Mathcad документ метода случайного поиска на гиперсфере, в котором можно выполнить вычисления.

Минимизация функции

методом случайного поиска на гиперсфере