Сведение задачи с ограничениями к безусловно экстремальной форме.




Поисковые методы отыскания экстремума в задачах с явным учётом ограничений являются инструментом очень тонким и расточительным в смысле вычислительных ресурсов. С другой стороны, методы, разработанные для безусловной оптимизации, обладают высоким быстродействием, требуют относительно небольшой памяти и позволяют решать практические задачи в автоматическом режиме без каких-либо настроек алгоритмов [3].

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

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

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

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

f(X) = (x1 - 3)2 + (х2 - 2)2

при ограничении

h (X) = х1 + х2 - 4 = 0.

Прибавим h2(X) к целевой функции f(X), в результате чего получим новую целевую функцию

Р(X) = (x1 - 3)2 + 2 - 2)2 + (х1 + х2 - 4)2,

значения которой будем считать свободными от каких-либо ограничений (h2 (X) здесь выступает в роли «штрафа»). В процессе минимизации Р(X) «штрафная добавка» к f(X) способствует тому, чтобы вектор X в некоторой степени удовлетворял исходному ограничивающему условию h (X) = 0. Совершенно очевидно, что, пока условие h (X) = 0 удовлетворяется (в пределах установленного допуска), значение штрафного члена пренебрежимо мало, и Р (X *) → f(X*) при XX *. Преимущество, которое мы получаем за счет перехода от задачи минимизации при наличии ограничений к задаче минимизации в отсутствие ограничений, состоит в том, что в последнем случае минимизация может осуществляться с помощью гораздо более простых (по сравнению с первым случаем) алгоритмов. При использовании методов штрафных функций получается максимальный оптимизирующий эффект за счет постоянного компромисса между необходимостью удовлетворения ограничений и процессом минимизации f(X), который достигается путем присвоения надлежащих весов целевой функции и функциям, задающим ограничения.

На рис. 13 графически представлена преобразованная целевая функция, полученная путем добавления к f(X) штрафной функции (с весовым коэффициентом, равным единице). Отметим, что точка минимума X * у обеих функций одинакова.

Методы штрафных функций можно разделить на два класса: 1) параметрические и 2) непараметрические методы.

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

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

Параметрические методы распадаются на три категории: 1) методы внутреннего штрафа; 2) методы внешнего штрафа и 3) комбинированные методы.

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

Рис. 13. Линии уровней исходной а) и преобразованной б) задачи.

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

Формулировка большинства технических задач содержит только ограничения-неравенства; в организационно-экономических задачах часто имеют место ограничения-равенства, например, нужно оптимальным образом потратить определённый ресурс, - однако равенства легко преобразуются в ограничения-неравенства путем задания небольшого допуска:

, (23)

где - величина допуска нарушения ограничения . С учетом этого, будем считать, что имеем дело только с ограничениями-неравенствами, то есть формулировку задачи нелинейного программирования (9), (10), (11) сокращаем, модифицируем и применяем в виде, характерным для технических задач:

минимизировать (24)

при р линейных и (или) нелинейных ограничениях в виде неравенств

(25)

Метод внешнего штрафа.

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

. (26)

На рис. 14 показано как формируется расширенная (штрафная) функция для функции одной переменной и одном геометрическом ограничении x ≤ a.

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

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

Для технических задач, связанных с ограничениями по прочности, жёсткости, динамическим характеристикам и т.п. приемлемую точность дают коэффициенты kj = 104. Это очень сильное требование и в этом случае компьютерная программа реализации поискового алгоритма должна оперировать числами с двойной точностью (64 бита или 16 десятичных цифр мантиссы).

Рис. 14. Внешняя штрафная функция



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-09-19 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: