8.2. Классификация методов оптимизации. Классификация методов оптимизации

Классификация методов оптимизации

( 0 )

F (X(0))= max min{fi (X)}, i=1, n, X={x1,..., xn}.i

Такой принцип выбора X часто называют принципом «гарантированного результата».

В том случае, если частные критерии fi(X) следуетминимизировать, то самым «отстающим» критерием является тот, который принимает максимальное значение. Тогда принцип равномерной компенсации формулируется в видемини-

максной задачи:

F( X ( 0 ) )= min max{fi (X)}, i=1, n, X={x1,..., xn}..

X i

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

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

обратный у целевой функции (рис. 5.5).

Рисунок 5.5 - Изменением знака целевой функции на противоположный задача на поиск максимума превращается в задачуна поиск минимума

Если функция F(x) имеет минимум в точкеx*, то функция- F(x) имеет мак-

симум в той же точке.

При выборе метода оптимизации обычно полагают:

Более эффективным считается метод, позволяющий получить оптимальное решение с заданной точностью ε как можно скорее - с минимальным числом

вычислений целевой функции.

Существующие методы оптимизации классифицируют по следующим ха-

рактерным признакам.

По количеству варьируемых переменных:

Методыодномерного поиска (один проектный параметр).Методымногомерного поиска (несколько проектных параметров).

Рисунок 5.6 - Постоянная штрафная функция - бесконечный барьер

По способу изменения варьируемых переменных:

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

Методыслучайного поиска (методМонте-Карло).

По порядку используемых производных целевой функции:

Методынулевого порядка или методыпрямого поиска3 (без вычисления производных).

Методы первого порядкаили градиентные методы(используются про-

изводные первого порядка).

Методывторого порядка, (используются производные второго порядка).

По отношению к рельефу целевой функции:

Методы поиска локальных экстремумов.

Методы поиска глобальных экстремумов.

Методы поиска оптимума приовражном4 характере целевой функции.

По отношению к ограничениям:

Методы безусловной оптимизации.

Методы, учитывающие ограничения (условной оптимизации).

5.4 Методы барьерных штрафных функций

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

дов барьерных штрафных функ-

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

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

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

3Методы прямого поиска в меньшей степени чувствительны к локальной

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

решении модельных задач, они оказываются наиболее практичными для исполь-

зования совместно с алгоритмами численного анализа, например, методом конечных элементов (для сеточных моделей).

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

незначительный протяженный наклон (частные производные характеризующие

его на порядок меньше).

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

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

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

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

По сути, данный вид штрафа - это сумма абсолютных величин невязок нарушенных ог-

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

Выражение для новой со-

ставной результирующей целевой Рисунок 5.7 - Абсолютная штрафная функцияфункции приобретает вид:

W (X ,ρ)= F(X)+ ρ ∑ci (X),где i I

F(X) - исходное значение целевой функции;

W (X ,ρ) - целевая функция с учетом штрафа;ρ - параметр штрафа;

ci (X ) - вектор нарушенных в точкеX ограничений;I - число нарушенных ограничений.

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

ном или нескольких ограничениях, возможен «небольшой» выход за границы до-

пустимой области.

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

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

ляется своего рода искусством.

studfiles.net

8.2. Классификация методов оптимизации.

Методы оптимизации исторически развивались независимо с

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

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

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

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

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

,j=1,2,…n,

особенно при наличии ограничений на переменные .

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

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

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

Такие задачи составляют круг задач линейного программирования.

Вопросы для самопроверки

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

Рекомендуемая литература.

Аверченков, В.И. Основы математического моделирования технических систем: учеб. пособие / В.И. Аверченков, В.П. Федоров., М.Л. Хейфец – Брянск: Изд-во БГТУ, 2004.
Вентцель, Е.С. Теория вероятностей / Е.С. Вентцель. – М.:Советское радио, 1972.
Вентцель, Е.С. Исследование операций / Е.С. Вентцель. – М.:Наука, Гл. ред. физ.-мат. лит., 1998.

4. Фёдоров, В.П. Математическое моделирование в машиностроении:

учебное пособие. / В.П.Фёдоров – Брянск: БГТУ, 2013.= 112 С.

studfiles.net

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

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

Одномерная оптимизация

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

Многомерная оптимизация

Поиск наилучшего значения целевой функции в n-мерном пространстве X Î Rn (или в ограниченной области XÎ D Ì Rn) называется многомерной или конечномерной оптимизацией. Методы многомерной оптимизации составляют основу аппарата оптимального проектирования, выполняющего поиск оптимального сочетания проектных параметров. К этому классу методов принадлежат большинство существующих программ для ЭВМ и сам термин математическое программирование.

Оптимальное управление

Объектами оптимизации могут быть функции на отрезке [a, b] (XÎ ), например, закон управления, минимизирующий затраты на совершение маневра, форма образующей головной части с минимальным сопротивлением движению в воздухе или прочной преграде. Математические методы решения задач оптимального управления связаны с минимизацией целевого функционала в банаховых и гильбертовых пространствах. Доказательство применимости этих методов (выпуклость функционалов и т.п.) не всегда возможно. Универсальные методы конечномерной численной оптимизации в меньшей степени используют априорные свойства математической модели, их можно применить и для решения бесконечномерных задач после дискретизации разбиением отрезка [a, b] на конечное число интервалов. Еще один способ – сужение класса функций (параболы, полиномы) – сводит задачу поиска оптимальной функции к оптимизации параметров известной функции.

Дискретная и целочисленная оптимизация

Особый класс составляют задачи оптимизации, в которых все или некоторые переменные принимают значения из дискретного ряда XÎ{X1, …, XN}. Как правило, методы, разработанные для решения задач непрерывной оптимизации неприменимы в дискретной оптимизации. Целочисленные задачи математического программирования содержат требования целочисленности, налагаемые на часть переменных: Xi Î Z, i = 1, …, N. Такие переменные могут обозначать количества элементов (число фрагментов разного типа в фракциях, их распределение в зонах разлета). При небольших N может оказаться приемлемым простой перебор вариантов, в множествах вариантов комбинаторной мощности целесообразно сочетать перебор вариантов с исключением заведомо неперспективных решений. Эта идея реализуется методами ветвей и границ: множество допустимых значений разбивают на непересекающиеся подмножества (ветвление), в которых оценивают нижние границы целевой функции. Можно существенно сократить количество анализируемых вариантов, отбирая их по формальному признаку, которому должно удовлетворять оптимальное решение. Выявление такого признака – принципа оптимальности – по математическим свойствам целевой функции требует глубокого понимания задачи и известных способов решения.

Классификация методов оптимизации по структуре оптимизационных задач

По структурным признакам различаются задачи безусловной и условной оптимизации по скалярным и векторным критериям. Структурные различия существенным образом определяют степень сложности задач.

Безусловная оптимизация

При отсутствии ограничений на возможные значения переменных оптимизации решением задачи является значение скалярной или векторной переменной X, доставляющее максимальное (max) или минимальное (min) значение скалярной функции W(X) на всем пространстве En:

. (1)

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

Условная оптимизация

Задачи оптимизации со скалярной целевой функцией, функциональными и прямыми ограничениями можно записать в виде:

min W(X)

Fk(X) ³ Fkтр, k =1, …, m,

ai £ x i £ bi, i=1, …, n,

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

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:

zdamsam.ru

Классификация методов оптимизации

Любой алгоритм отыскания оптимального решения x* для задачи минимизации функции f на множестве X обычно ориентирован на решение определенного класса задач оптимизации с определенными свойствами функции f и множества X. Поэтому более универсальные алгоритмы, ориентированные на решение более широких классов задач, обычно уступают по эффективности специализированным алгоритмам, использующим специфические свойства конкретно решаемой задачи. Этим и объясняется современное непрерывное возрастающее разнообразие алгоритмов оптимизации.

Далее приведены примеры основных оптимизационных методов.

1. Метод полного перебора

Если множество допустимых решений состоит из N элементов иN настолько мало, что имеется практическая возможность вычислить все значения , то сравнением полученных значений найдем наименьшее значениеи одновременно искомое оптимальное решение. Такой метод полного перебора используется довольно редко, потому что множествоX обычно содержит слишком много элементов и практически невозможно вычислить f(x) для каждого x X.

2. Приближенные методы и оптимальные алгоритмы

Среди приближенных методов оптимизации наиболее часто используются:

Методы частичного перебора ислучайного поиска. В этих методах выбирают некоторое достаточное представительное подмножество XN = {x1, x2, ..., xN} X, допускающее возможности использовать метод полного перебора и найденное xi* принимают в качестве приближенного решения исходной задачи оптимизации. Если элементы x1, x2, ..., xN вычислять как реализации некоторой случайной величины с заданной мерой (такой метод называют методом случайного поиска или методом Монте-Карло) или задать в виде некоторой сетки узлов XN X, то получим метод пассивного поиска. В методах активного (или адаптивного) поиска элементы x1, x2, ... вычисляют последовательно и, учитывая текущую информацию о значениях f(x1), f(x2), ... (или производных f), стремятся обеспечить более густую сетку в тех подмножествах XN X, которые становятся более подозрительными (в процессе вычислений f(xi)) на оптимум (т.е. на то, что X* XN).

Методы отсечений. В этих методах находят и “отсекают” от множества X те его подмножества X’, которые заведомо не содержат оптимальных решений, и получают эквивалентную задачу минимизации функции f на меньшем множестве X’’ = X\X’. Последовательными отсечениями иногда удается получить последовательность вложенных подмножеств X1’ X2’ ... Xk ..., что начиная с некоторого k любой элемент xk Xk очевидно является решением задачи оптимизации. Различные эффективные варианты методов отсечений разрабатываются в рамках методов ветвей и границ, методов минорант, методов эллипсоидов (особенно эффективных для решения выпуклых задач) и других методов.

Методы аппроксимаций. В этих методах функцию f и (или) множество X заменяют некоторыми реализуемыми аппроксимациями f’, XN’, допускающими практическую возможность вычислить минимум функции x’ = min(f’). Если (f’, XN’) достаточно близки к (f, X), то можно ожидать что x’* будет близким к x* = min(f*).

Методы локальной оптимизации. Если для заданных xk X, lk>0 множество X заменять “меньшим” множеством X1(xk, lk) = {x X | ||xk - x|| lk} и последовательно вычислять xk+1 = min f(x), x X1(xk, lk), то при весьма общих условиях получим сходимость xk -> X* к локальному решению задачи оптимизации. Поиск локальных решений оказывается особенно эффективным при решении тех задач оптимизации, в которых все локальные решения являются одновременно оптимальными решениями (например, выпуклых задач оптимизации).

Методы последовательных приближений. Так как вычисление xk+1 может оказаться довольно трудной задачей даже при малых lk, то в многочисленных методах проследовательных приближений предлагается вычислять xk+1 как приближенное решение задачи xk+1 = min f(x) , x < Xk, где аппроксимации Fk, Xk, выбираются из соображений упростить вычисление xk+1, сохранив при этом сходимость xk -> x*, k->.

studfiles.net