Введение
На разработку методов прямого поиска для определения минимума функций и переменных было затрачено много усилий . Методы прямого поиска являются методами, в которых используются только значения функции. Практика показала, что этот метод эффективен и применим для широкого числа приложений. Рассмотрим функцию двух переменных. Ее линии постоянного уровня на рис. 1,
а минимум лежит в точке $(x_{1}^{*},x_{2}^{*})$. Простейшим методом поиска является метод покоординатного спуска. Из точки А мы производим поиск минимума вдоль направления оси и , таким образом, находим точку В, в которой касательная к линии постоянного уровня параллельна оси . Затем, производя поиск из точки В в направлении оси , получаем точку С, производя поиск параллельно оси , получаем точку D, и т. д. Таким образом, мы приходим к оптимальной точке. Очевидным образом эту идую можно применить для функций n-переменных.
Теоретически данный метод эффективен в случае единственного минимума функции. Но на практике он оказывается слишком медленным. Поэтому были разработаны более сложные методы, использующие больше информации на основании уже полученных значений функции.
Метод Хука-Дживса
Метод Хука-Дживса был разработан в 1961 году, но до сих пор является весьма эффективным и оригинальным. Поиск состоит из последовательности шагов исследующего поиска вокруг базисной точки , за которой в случае успеха следует поиск по образцу. Он применяется для решения задачи минимизирования функции без учета ограничений .
Описание этой процедуры представлено ниже:
А. Выбрать начальную базисную точку $b_{1}$ и шаг длиной $h_{1$} для каждой переменной $x_{j}, j = 1, 2,…, n$. В приведенной ниже программе для каждой переменной используется шаг h, однако указанная выше модификация тоже может оказаться полезной.
Б. Вычислить $f(х)$ в базисной точке $b_{1}$ с целью получения сведений о локальном поведении функции $f(x)$. Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция $f(x)$ в базисной точке $b_{1}$, находится следующим образом:
1. Вычисляется значение функции $f(b_{1})$ в базисной точке $b_{1}$.
2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции $f (b_{1}+h_{1}e_{1})$, где $e_{1}$ – единичный вектор в направлении оси $x_{1}$. Если это приводит к уменьшению значения функции, то $b_{1}$ заменяется на $b_{1}+h_{1}e_{1}$. В противном случае вычисляется значение функции $f (b_{1}-h_{1}e_{1})$, и если ее значение уменьшилось, то $b_{1}$ заменяем на $b_{1}-h_{1}e_{1}$. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка $b_{1 }$ остается неизменной и рассматриваются изменения в направлении оси $х_{2}$, т. е. находится значение функции $f (b_{1}+h_{2}e_{2})$ и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку $b_{2}$.
3. Если $b_{2}=b_{1}$, т. е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки $b_{1}$, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.
4. Если $b_{2} \ne b_{1}$, то производится поиск по образцу.
В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:
1. Разумно двигаться из базисной точки $b_{2}$ в направлении $b_{2}-b_{1}$, поскольку поиск в этом направлении уже привел к уменьшению значения функции. Поэтому вычислим функцию в точке образца
$P_{1}=b_{1}+2(b_{2}-b_{1})$ . В общем случае $P_{i}=b_{i}+2(b_{i+1}-b_{i})$ .2. Затем исследование следует продолжать вокруг точки $Р_{1} (Р_{i})$ .
3. Если наименьшее значение на шаге В, 2 меньше значения в базисной точке $b_{2}$ (в общем случае $b_{i+1}$), то получают новую базисную точку $b_{3 }(b_{i+2}$), после чего следует повторить шаг В, 1. В противном случае не производить поиск по образцу из точки $b_{2 }(b_{i+1}$), а продолжить исследования в точке $b_{2 }(b_{i+1}$).
Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.
Модифицированный метод Хука-Дживса
Этот метод нетрудно модифицировать и для учета ограничений .Было выдвинуто предложение , что для этого будет вполне достаточно при решении задачи минимизации присвоить целевой функции очень большое значение там,где ограничения нарушаются .К тому же такую идею просто реализовать с помощью програмирования.
Нужно проверить, каждая ли точка, полученная в процессе поиска, принадлежит области ограничений .Если каждая, то целевая функция вычисляется обычным путем. Если нет, то целевой функции присваивается очень большое значение. Таким образом, поиск будет осуществляться снова в допустимой области в направлении к минимальной точке внутри этой области.
