Методы поиска экстремума функции цели

Скалярное значение функции цели (9.7) в пределах возможного изменения вектора x может иметь несколько или множество локальных минимумов и один глобальный x_опт. Выражение (9.7) для глобального минимума справедливо при всех x, принадлежащих пространству Rⁿ , а для локального – только в части этого пространства.

Сами методы поиска целевой функции, т.е. определение x_опт , классифицируется по нескольким признакам:

· по виду искомого минимума – локальные и глобальные;

· по характерной черте метода – с использованием только значений, принимаемых целевой функцией F_ц (x) (методы прямого поиска), или как значений F_ц (x), так и ее первых и вторых производных (градиентные методы);

· по способу перехода от одной точки к другой на каждом шаге поиска – детерминированные и случайные;

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

Обобщенная структурная схема программы поиска как локального, так и глобального минимума приведена на рис.6.52, в которую включены в виде отдельных модулей все основные процессы поиска.

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

Целевая функция Fц (х)

Варьируемые параметры xn

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

Пространство Rn

Ограничения вида Ψi(x) < 0

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

Рис. 6.52 Обобщенная структурная схема программы поиска локального и глобального минимума

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

Погрупповой метод последовательного поиска. Пусть число переменных параметров есть N и каждый из параметров x_n изменяется с шагом ∆ x_n в пределах от x_n.мин до x_n.макс и принимает M дискретных значений. Тогда при последовательном переборе всех комбинаций множества параметров x_n общее число рассчитываемых вариантов составит Q=M^N . Это число может быть столь большим (например, при M=10 и N=6 значение Q=10⁶), что даже расчет на быстродействующей ЭВМ может оказаться недопустимо длительным. Поголовный перебор всех вариантов можно исключить, если параметры разбить на группы, включающие только взаимозависимые x_n . Далее производится перебор всех x_n только внутри группы с определением набора параметров, соответствующих минимуму целевой функции. Последовательно переходя от одной группы параметров к другой, определяют вектор x_опт, включающий все параметры x_n. Так, например, в приведенном примере из 6-ти параметров при возможности их разбиения на две группы по 3 параметра общее число рассчитываемых вариантов составит Q=2*10³=2000, т.е. почти на три порядка меньше, чем в первом варианте. Однако, воспользоваться таким простым и надежным способом поиска глобального минимума можно только при сильной зависимости параметров внутри одной группы и слабой – между разными.

Покоординатный метод. Здесь сначала дискретно изменяется только параметр x₁ при постоянных значениях всех остальных параметров x_n до тех пор, пока целевая функция не станет минимальной. Полученное значение x₁ фиксируется и в новом цикле начинается изменение параметра x₂ при неизменных значениях остальных параметров и т.д., вплоть до изменения параметра x_n. Подобная процедура повторяется несколько раз, в результате чего определяется вектор x_опт. Как и в предыдущем случае, такой простой алгоритм успешно действует только при слабой зависимости между собой всех параметров x_n.

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

Метод оврагов. Этот метод пригоден для так называемых хорошо организованных функций, при которых переменные параметры x₁,x₂, …, x_n можно разбить на две группы: сильно и слабо влияющие на целевую функцию F_ц. Параметры 1-й группы меняются с относительно большим шагом, 2-й – c малым. После большого шага в рамках 1-й группы параметров производится локальный поиск с малым шагом в рамках 2-й группы параметров. Такая итерационная процедура позволяет относительно быстро продвигаться по так называемому «оврагу» к глобальному минимумy функции цели.

Метод Розенброка или вращающихся координат. Здесь используется специальная итерационная процедура, связанная с вращением направлений поиска по отношению к предыдущему шагу, в результате чего продвижение к минимуму функции цели, как и в предыдущем случае, происходит по «оврагу». Для целенаправленного поиска на каждом последующем шаге используется информация, полученная на предыдущем, что позволяет сравнительно быстро найти локальный минимум целевой функции. Меняя исходную точку поиска или совместив метод Розенброка со «слепым» или иным способом, можно с высокой степенью вероятности найти глобальный минимум функции цели.

Математический пакет программ «Mathcad» предлагает две функции – Maximize и Minimize (обе расположены в категории функций «Решение») – для реализации процедуры оптимизации, связанной с поиском вектора x_опт без вычисления производных функции цели.

С помощью функции Maximize (F, x₁, x₂, …, x_n), где F – функция цели, x₁, x₂, …, x_n – варьируемые параметры объекта оптимизации, осуществляется поиск параметров, соответствующих максимуму функций F.

С помощью функции Minimize (F, x₁, x₂, …, x_n) – минимуму функции F.