Назначение и классификация методов поисковой оптимизации

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

Исходными данными в методах поиска являются требуемая точность метода и начальная точка поиска Х ⁰.

Затем выбирается величина шага поиска h, и по некоторому правилу происходит получение новых точек Х ^k+1 по предыдущей точке Х ^k , при k = 0,1,2,… Получение новых точек продолжают до тех пор, пока не будет выполнено условие прекращения поиска. Последняя точка поиска считается решением задачи оптимизации. Все точки поиска составляют траекторию поиска.

Методы поиска могут отличаться друг от друга процедурой выбора величины шага h (шаг может быть одинаковым на всех итерациях метода или рассчитываться на каждой итерации), алгоритмом получения новой точки и условием прекращения поиска.

Для методов, использующих постоянную величину шага, h следует выбирать значительно меньше точности h » Öe). Если при выбранной величине шага h не удается получить решение с требуемой точностью, то нужно уменьшить величину шага и продолжить поиск из последней точки имеющейся траектории.

В качестве условий прекращения поиска принято использовать следующие:

все соседние точки поиска хуже, чем предыдущая;

çФ(X^k+1 ) - Ф(X ^k)ç£ e, то есть значения целевой функции Ф(Х) в соседних точках (новой и предыдущей) отличаются друг от друга на величину не больше, чем требуемая точность e;

то есть все частные производные в новой точке поиска практически равны 0 или отличаются от 0 на величину, не превышающую заданной точности e.

Алгоритм получения новой точки поиска Х^k+1 по предыдущей точке Х^k свой для каждого из методов поиска, но всякая новая точка поиска должна быть не хуже предыдущей: если задача оптимизации является задачей поиска минимума, то Ф(Х^k+1) £ Ф(Х^k).

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

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

Эффективность поискового метода определяют по числу итераций и по количеству вычислений целевой функции Ф(Х) на каждой итерации метода (N). Рассмотрим наиболее распространенные методы поиска, расположив их в порядке уменьшения числа итераций.

Для методов поиска нулевого порядка справедливо следующее: в методе случайного поиска нельзя заранее предсказать количество вычислений Ф(Х) на одной итерации N, а в методе покоординатного спуска N £ 2×n, где n- количество управляемых параметров X = ( x1, x2.,…,xn).

Для методов поиска первого порядка справедливы следующие оценки: в градиентном методе с постоянным шагом N=2×n; в градиентном методе с дроблением шага N = 2×n + n₁, где n₁ – число вычислений Ф(Х), необходимых для проверки условия дробления шага; в методе наискорейшего спуска N=2×n+n₂, где n₂ – число вычислений Ф(Х), необходимых для расчета оптимальной величины шага; а в методе Давидона – Флетчера - Пауэлла (ДФП) N = 2× n + n₃, где n₃ – число вычислений Ф(Х), необходимых для расчета матрицы, приближающей матрицу Гессе ( для величин n₁, n₂, n₃ справедливо соотношение n₁ < n₂ << n₃ ).

И, наконец, в методе второго порядка - методе Ньютона N = 3×n². При получении данных оценок предполагается приближенное вычисление производных по формулам конечных разностей / 6 /:

то есть для вычисления производной первого порядка нужно знать два значения целевой функции Ф(Х) в соседних точках, а для второй производной – значения функции в трех точках.

На практике широкое применение нашли метод наискорейшего спуска и метод ДФП, как методы с оптимальным соотношением числа итераций и их трудоемкости.