Поисковые методы решения многофакторных оптимизационных задач

В таких оптимизационных задачах F(x₁, x₂, …, x_n) – целевая функция двух и более аргументов.

F(x₁, x₂, …, x_n) → min.

Рассмотрим Y=F(x₁;x₂). В этом случае пространство переменных есть плоскость.

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

Нужно найти такие х₁ и х₂, при которых Y → min.

Необходимо предварительно установить точность решения ( ). Точность решения оптимизационной задачи определяется тем, как в последующем будут использованы результаты решения. Оптимальные значения технологических параметров, найденные в результате решения оптимизационной задачи, необходимо поддерживать при проведении технологического процесса. Для этого служат регуляторы соответствующих параметров: температуры, объемных и массовых расходов и т.п. Регуляторы позволяют измерять и поддерживать значения параметров с некоторой точностью, составляющей обычно от 0.5% до 5% диапазона измерения. Поэтому нет смысла задавать точность решения оптимизационной задачи более жестко, поскольку регулятор впоследствии не позволит поддерживать значение параметра с высокой точностью.

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

Система ограничений дает возможность в пространстве переменных построить область, внутри которой и на границах выполняются совместно все ограничения задачи. Такая область называется областью допустимых решений (ОДР). Для целевой функции двух переменных пространство переменных представляет собой плоскость, а область допустимых решений – часть плоскости, ограниченная прямыми. В случае трех переменных пространство становится объемным, а область допустимых решений является многогранником, ограниченным плоскостями. Для четырех и более переменных привычных геометрических образов нет, говорят о гиперпространстве переменных и области допустимых решений, ограниченных гиперплоскостями.

%

%

а₁≤x₁≤b₁

a₂≤x₂≤b₂

N = n₁ ∙ n₂

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

Пусть целевая функция имеет три оптимизирующих фактора. Используя метод сплошного поиска, мы могли бы построить и исследовать область допустимых решений. В нашем случае такая область представляет собой параллелепипед. Предположим, нас интересует точность решения в 1% от диапазона изменения каждого фактора. Мы могли бы разбить интервал каждого фактора на сто шагов, что привело бы к пространственной сетке, содержащей сто плоских слоев, в каждом из которых количество узлов составило бы десять тысяч. Таким образом, общее число узлов на области допустимых решений составило бы миллион. Далее следовало бы вычислить (и запомнить значения) целевую функцию в каждом узле, отсортировать полученные значения и найти экстремум. Значения факторов в точке экстремума и были бы решением оптимизационной задачи. Однако для получения решения таким путем потребовалось бы слишком много времени, поскольку вычисление целевой функции каждый раз требует некоторых затрат времени. К тому же требуется время на сортировку и поиск оптимального решения, а также огромный объем памяти для хранения результатов вычислений. А если число оптимизирующих факторов (аргументов целевой функции) больше трех, то легко показать, что задача вообще не может быть решена за приемлемое время - пока мы занимаемся ее решением, условия технологического процесса изменятся. Поэтому усилия специалистов в области прикладной математики были сосредоточены в направлении разработки «быстрых» методов решения многофакторных оптимизационных задач. В настоящее время создано несколько групп методов для решения таких задач.

Математиками разработаны следующие методы для решения многофакторных оптимизационных задач:

· Метод координатного спуска.

· Градиентные методы.

· Симплексные методы.

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

Общие требования:

1. Целевая функция должна быть вычислима (задана аналитически, либо известен алгоритм вычислений, либо имеется таблица табулированных значений).

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

Наряду с общими поисковые методы отличаются элементами стратегии поиска, к которым относятся:

1. Начальная точка поиска.

2. Направление поиска.

3. Величина начального шага.

4. Способ сокращения начального шага и коэффициент сокращения.

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

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

Направление поиска – выбирается в каждом методе, исходя из особенностей метода.

Начальный шаг. Идея поисковых методов – движение по области допустимых  решений, причём направление и размер шага зависят от результатов решения, полученных на предыдущем шаге. При этом, для более быстрого получения решения (за меньшее число вычислений) следует выбирать начальный шаг достаточно большим: величина начального шага 20…25% от интервала изменения фактора.

Способ и коэффициент сокращения шага. Двигаясь по ОДР начальным шагом, можно решить задачу с точностью, равной величине начального шага, для практических целей этого не достаточно. Для достижения заданной точности решения требуется продолжить поиск, исследуя область допустимых решений шагами меньшей величины. Последующая величина шагов получается делением начального шага на коэффициент сокращения. Коэффициент сокращения шага обычно от 2-х до 5-ти.

Метод координатного спуска

В этом методе направление поиска совпадает с направлением координат (осями факторов). На любом шаге решения можно менять только один фактор, а все остальные остаются без изменения.

Поиск решения начинается в начальной точке 1 (см. рис.), где вычисляется значение целевой функции. Затем начинаем движение по пространству переменных в пределах области допустимых решений. Это означает, что увеличив координату на величину начального шага вдоль х₁, и оставив без изменения х₂, мы переместимся в новую точку 2. Вычислим значение целевой функции в этой точке и сравним его с предыдущим. Если при поиске минимума значение функции в точке 2 меньше, чем в точке 1, то такой шаг следует считать удачным. В этом случае поиск продолжается в выбранном направлении. Двигаясь вдоль х₁ и вычисляя на каждом шаге значение целевой функции, мы рано или поздно можем убедиться в том, что последующее значение станет больше предыдущего. Такой шаг является неудачным. Если очередной шаг решения оказался неудачным, направление поиска изменяется. Для этого координату последней удачной точки по х₁ фиксируют, и начинают движение в направлении х₂, используя величину начального шага. Вблизи области минимума движение начальным шагом во всех разрешенных направлениях не приводит к улучшению значения целевой функции. При этом одна из точек окажется наилучшей, в ней значение целевой функции наименьшее. Однако задача еще не решена, поскольку величина начального шага выбирается заведомо больше интересующей нас точности решения. Фактически задача пришла к исходной – имеется начальная точка поиска (наилучшая), и требуется путем движения по пространству переменных найти такую точку, в которой значение целевой функции еще меньше. Для этого последующий поиск надо проводить, двигаясь шагом уменьшенной величины. Такой шаг получают делением начального шага на коэффициент сокращения шага, обычно его выбирают равным от 2 до 5. Разделив начальные шаги на соответствующие коэффициенты сокращения продолжают поиск, пока одна из точек вновь не станет наилучшей и т.д. Критерием завершения поиска является  достижение заданной точности решения.

Градиентные методы

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

Направление поиска в случае мини-мизации целевой функции совпадает с на-правлением антиградиента. Пусть имеется Y=F(x₁;x₂), тогда

,

где Н₁ и Н₂ - единичные направляющие векторы (орты), направление которых совпадает с направлением осей факторов х₁ и х₂, а модуль равен единице; - частная производная целевой функции F по ее аргументу х₁;  - частная производная целевой функции F по ее аргументу х₂.

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

.

Для вычисления приращений функции в направлении осей ее аргументов построим две дополнительные точки N и P, лежащие вблизи начальной точки поиска М на расстояниях ε₁ и ε₂ сответственно. Вычислив значения целевой функции в этих точках, а затем вычислим приращения в направлении аргументов.

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

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

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

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

Симплексные методы

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

Поиск решения осуществляется с использованием симплекса.

Симплекс – геометрический комплекс, имеющий n+1 вершину; где n – число факторов оптимизационной задачи. Для функции двух переменных n=2, а симплекс представляет собой треугольник на плоском пространстве переменных. Если этот треугольник равносторонний, то метод поиска называется методом регулярного симплекса. Когда начальный размер симплекса известен и равен R, координаты всех его вершин легко определить, если заданы координаты любой вершины, кА это показано в таблице. Пусть вершина А является начальной точкой поиска. Начиная поиск, определим координаты двух других вершин симплекса и вычислим значения целевой функции во всех трех вершинах. Сравним значения функции между собой и определим наихудшее (при поиске минимума – наибольшее, при поиске максимума – наименьшее). Дальнейший поиск следует предпринимать в направлении, противоположном той вершине, в которой наблюдается наихудшее значение функции. Для этого используется процедура отражения: ищем точку, зеркально отражая наихудшую вершину через противоположную сторону симплекса. Получаем новый симплекс, две из трех вершин которого принадлежат старому. Рассчитываем значение целевой функции в новой вершине и сравниваем его со значениями в двух других вершинах нового симплекса (эти значения были рассчитаны на предыдущем шаге решения). Вновь определяем наихудшее значение функции на новом симплексе, проводим процедуру отражения и ищем вершину следующего симплекса. Продолжая движение таким способом, мы неизбежно придем в область экстремума целевой функции, где при использовании процедуры отражения начнется вращение симплекса вокруг одной из его вершин. Если симплекс начал вращение и совершил (путем последовательных отражений вершин) полный оборот, то улучшить значение функции при движении симплекса начального размера уже не удастся. Необходимо уменьшить размер симплекса, разделив начальный размер на коэффициент сокращения, и продолжить решение задачи до достижения заданной точности.

y=F(x₁;x₂), R – начальный размер симплекса.

	Х1	Х2
А В С	Х10 Х10+R/2 X10+R	X20 X20+ X20

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

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

Y(M₂) < Y(M₁)

^{глоб.                лок.}

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