Метод проектирования градиента

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

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

Метод штрафных функций

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

Метод барьерных функций

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

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

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

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

Случайный механизм выбора направления реализуется с помощью датчика случайных чисел , равномерно распределенных на интервале [-b, b]. Направление задается случайным вектором

 = (₁, ₂, ₃, ..., _n),

компоненты которого вычисляются по формуле

,

где n случайных чисел _i генерируются датчиком. Очевидно, что такой случайный вектор имеет единичную длину и определяет только направление. При этом все направления равновероятны.

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

Алгоритм с возвратом при неудачном шаге

1. Задать начальный шаг h⁰, число проб s  n и точность .

2. Сгенерировать или задать начальную точку X⁰ и вычислить в ней функцию f; положить i=1 (i – счетчик проб).

3. Сгенерировать случайный вектор направления  .

4. На направлении определить точку X^k+1 = X^k + h^k^k и вычислить в ней функцию f.

5. Проверить: а) если f(X^k+1)<f(X^k), положить k=k+1, i=1 и вернуться на 3; б) если f(X^k+1)f(X^k) и i<s, положить i= i+1 и вернуться на 3; в) если f(X^k+1)f(X^k), i=s и h^k >, положить h^k= h^k/2, i=1 и вернуться на 3. г) если f(X^k+1)f(X^k), i=s и h^k, поиск закончить, приняв X^k за точку минимума.▲

Т аким образом, поиск останавливается, если в текущей точке s направлений, сгенерированных подряд, оказались неудачными при шаге, меньшем заданной точности. На рис. 8.38 показан характер движения при поиске по данному алгоритму (жирной линией выделены успешные шаги).