Построение единой программной среды для решения задач глобальной оптимизации (стр. 2 из 9)

Методы кластеризации

Методы кластеризации (clustering methods) относятся к стохастическим методам. Метод кластеризации стартует с некоторой точки, случайно выбранной из области W, и затем создает группы или кластеры ближайших точек, соответствующих основной области притяжения. Кластер C есть множество точек, которое соответствуют области притяжения и имеет следующие свойства:

· C содержит ровно один локальный минимум x^*.

· Любой алгоритм спуска, стартующий из точки xÎ C, сходится к точке x^*.

· Первые два свойства подразумевают, что C может содержать только одну стационарную точку.

Например, рассмотрим функцию (x² – 1)², которая имеет глобальный минимум в точках x = ±1. Для нее существует два кластера. Первый кластер это {x| -

< x < 0}, и второй кластер это {x| 0< x <

} (см. рис. 1). Любой метод спуска, стартующий в кластере 1, гарантированно сходится к точке x = -1. Аналогично, метод спуска, стартующий в кластере 2, гарантированно сходится к точке x = 1.

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

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

Детерминированные методы

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

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

Метод ветвей и границ

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

Метод ветвей и границ, подобно моделируемому отжигу, первоначально успешно применялся для решения задач целочисленной оптимизации. После этого он был адаптирован для непрерывного случая и для решения задачи поиска min¦(x) при xÎWÍRⁿ принял следующий канонический вид:

Алгоритм 3: Метод ветвей и границ

Инициализация: Установить i = 1, z^* = + infinite, и список = W.

Шаг 1: Извлечь область W_i из списка.

Шаг 2: Если W_i достаточно мала, занести ее в результирующий список и перейти к шагу 1.

Шаг 3: Вычислить z_-, z⁺ такие что z_- £ ¦(x)|_W_i £ z⁺.

Шаг 4: Если z_- > z^* удалить область W_i и перейти к шагу 1.

Шаг 5: Если z⁺ £ z^* установить z^* = z⁺.

Шаг 6: Разбить W_i на k равных частей и добавить их в список.

Шаг 7: Перейти на шаг 1.

Шаг 8: Вернуть список результирующих областей.

Алгоритм 3 разбивает исходную область W на все более и более мелкие части, отбрасывая те, наличие глобального минимума в которых невозможно.

Этот простой алгоритм имеет несколько недостатков. Во-первых, границы значений функции на W_i, вычисленные на шаге 3 потенциально не точны. Если оценка функции проведена с плохой точностью, то алгоритм может потратить большое количество времени, пытаясь отбросить области, не содержащие глобального минимума, на которых целевая функция является достаточно плоской. Во-вторых, на шаге 6, W_i разбивается на k равных частей, причем не принимается в расчет какая-либо информация об локально/глобальном поведении функции на полученных частях. Более интеллектуальный алгоритм должен принять эту информацию во внимание, для определения того, где нужно резать область. Например, возьмем прямоугольник [-1, 1]´[-1, 1] и ¦(x) = x². Этот прямоугольник можно разбить на четыре части, каждая с углом в (0, 0). Это разбиение не очень хорошее, поскольку каждый прямоугольник все еще содержит глобальный минимум функции. В то же время, если прямоугольник разрезать на части

[-e, e]´ [-e, e], [e, 1]´ [-1, 1], [-1, -e]´ [-1, 1], [-e, e]´ [e, 1], [-e, e]´ [-1, -e],

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

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

Канонический метод ветвей и границ позволяет решать задачу глобальной оптимизации также и для случая, когда на переменные задана некоторая система ограничений. Достаточно просто проверить эти ограничения для текущего параллелепипеда и, если они гарантированно не выполнены, то параллелепипед можно выбросить из дальнейшего рассмотрения. Здесь нужно только чтобы ограничения задавали такую область, что при достаточно мелком ее разбиении существовал параллелепипед, целиком лежащий в этой области. Если это условие не выполнено, то данный метод неприменим.

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

Функции ограничения

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

Ограничение, основанное на константах Липшица

Потенциально недорогая, но неточная оценка функции может быть дана следующим выражением

B_L_,_W¦ = ¦(x^*) – Lw(W) £ ¦(x) £ ¦(x^*) + Lw(W) = B^L^,^W¦,