лекции по моде

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

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

Для получения решения:

а) задаем способ вычисления целевой функции: y = f (x) → min.

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

в) выбирается интервал допустимых значений: a≤x≤b.

Метод перебора (сплошного поиска).

Разбиваем ось аргументов на конечное число шагов решения, которое определяется интересующей нас точностью: . При точности 1% от интервала изменения фактора это будет соответствовать разбиению интервала на 100 шагов, при точности 5% потребуется разбить интервал на 20 шагов и т.д.

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

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

Метод дихотомии (половинного деления).

Исходно требуется то же, что и в предыдущем методе. Разбиваем интервал значений аргумента пополам:

. Строим две дополнительные узловые точки с координатами:

и вычисляем значения целевой функции в этих точках.

y₁ = f (x₁)

y₂ = f (x₂).

Представим, что функция имеет один минимум на отрезке от a до b. Ординаты у₁ и у₂ вычислены в точках, лежащих достаточно близко друг к другу, на расстоянии удвоенной точности решения. Если у₂>у₁, поиск минимума на левой половине интервала теряет смысл, и ее можно отбросить. На этом первая итерация решения заканчивается, и после сокращения интервала вдвое задача вновь возвращается к исходной.

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

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

Поскольку сокращение интервала на каждой итерации происходит вдвое, то совершив 7 итераций, например, мы уменьшим первоначальный интервал в 128 раз, достигнув точности решения менее 1% от первоначального интервала.

Поскольку на каждой итерации целевая функция вычисляется дважды, общее количество ее вычислений будет равно 14. При этом нет необходимости запоминать результаты вычислений, в отличие от метода сплошного поиска. К тому же, решая задачу по методу сплошного поиска с точностью 1%, мы были бы вынуждены выполнить 100 вычислений целевой функции, и при этом все результаты вычислений надо было бы сохранить. При повышении точности решения различия методов становятся еще больше: при точности 0.5% метод дихотомии требует 16 вычислений функции, а метод сплошного поиска – 200 вычислений, при точности 0.1% - 20 и 1000 вычислений соответственно!

7 шагов

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

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

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

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

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

Метод координатного спуска.
Градиентные методы.
Симплексные методы.

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

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

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

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

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

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

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

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

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

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

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

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

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

Критерий завершения поиска – достижение заданной точности.

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

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

Градиент – это вектор, направление которого является направлением наиско-рейшего возрастания функции из заданной точки.

Антиградиент – направлен противо-положно вектору градиента.

меняет своё направление в каждой точке.

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

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

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

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

Симплекс – геометрический комплекс, имеющий n+1 вершину; n – число факторов оптимизационной задачи.

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

Х₁

Х₂

Х₁₀

Х₁₀+R/2

X₁₀+R

X₂₀

X₂₀+

X₂₀

Задав координаты вершин, рассчитываем целевую функцию решений симплекса.

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

На следующем шаге решения рассчитываем значение в новой вершине и сравниваем значения в новом симплексе и ищем наихудшую. Путём последующего отражения оказываемся в точке 3.

Существует метод деформируемого симплекса (можно изменять форму).

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

Y(M₂) < Y(M₁)

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

То, какой из типов мы обнаружим, зависит от выбора начальной точки

Содержание