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

Лекция 11. Детерминированные  методы и модели оптимизации

Вопросы лекции:

1. Сущность и область применения

2. Инфлюентный анализ как метод детерминации.

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

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

Суть инфлюентного анализа состоит в нахождении оценок А(∆х_i влияния ∆x_i,- параметров на величину изменений ∆Y по­казателя.

В этом случае ∆Y представляется в виде алгебраической суммы

∆Y =

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

Составляющие A(∆x_i) разложения приращения ∆Y называ­ются инфлюентами, и задача инфлюентного анализа состоит в их нахождении, для того чтобы затем по значениям инфлюент определять направленность и степень влияния изменения па­раметров ∆х_i = x_i^(I) – x_i⁽⁰⁾ на изменение показателя ∆Y=y⁽¹⁾ - у⁽⁰⁾ . При этом значения {х_i⁽⁰⁾, у⁽⁰⁾ , x_i ⁽¹⁾, у⁽¹⁾} называются терминаль­ными, причем у⁽¹⁾ и x_i⁽¹⁾ рассматриваются как некоторые фак­тические (реальные, существующие), а у⁽⁰⁾ и x_i⁽⁰⁾ — как те, ко­торых надо достичь (например, плановые, номинальные, же­лаемые).

При имеющейся математической модели Y=f(x₁, x₂, ..., х_n) наиболее простым методом является метод цепных подстано­вок, сущность которого заключается в подстановке в функцию Y в определенном порядке номинальных .х_i ⁽⁰⁾ и фактических х_i⁽¹⁾ параметров и вычислении инфлюент по про­стым формулам.

Недостатком метода является отсутствие правила перебора последовательностей индексов i для подстановки параметров (х_i⁽⁰⁾, x_i⁽¹⁾) и, вследствие этого, зависимость инфлюент от вы­бранной последовательности. Этого недостатка лишены более сложные процедуры расчета инфлюент.

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

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

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

Сущность безусловной оптимизации состоит в поиске ми­нимума функции Y = f(x) путем многократных вычислений при различных значениях параметров x = [х^k}, к = О, 1, 2, .... причем на каждом к-м шаге вычислений контролируют вы­полнение условий

f(x^(k+1))≤ f(x^(k))

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

Основные трудности применения заключаются в определе­нии шага изменения параметра х^(k направления этого измене­ния и начального приближения х⁽⁰⁾.

Область применения. Методы безусловной оптимизации используются для однокритериальной оптимизации детерми­нированных функций при отсутствии ограничений на саму функцию или ее параметры. Наиболее употребительными ме­тодами являются: методы первого порядка и методы второго порядка.

Методы и их модификации широко представлены в общем математическом обеспечении ПЭВМ.

Методы нулевого порядка

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

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

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

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

Методы первого порядка

Методы первого порядка используют, если возможно най­ти первую производную исследуемой функции. К данному классу относятся градиентные методы. Их суть заключается в определении лучшего направления и шага поиска минимума функции по значениям первых производных в некоторой точ­ке х^{к) Наибольшее значение производной показывает направ­ление наискорейшего уменьшения функции, и в этом направ­лении рассчитывается следующее приближение функции у = f(x^(k+1)) параметры которой отличаются на величину некоторо­го шага ∆x. В зависимости от способа задания этого шага и производится классификация градиентных методов: градиент­ный спуск; наискорейший спуск; градиентный спуск с посто­янным шагом; градиентный спуск с переменным шагом. Ме­тоды эффективны для функций со слабовыраженной нелиней­ностью.

Методы второго порядка

Методы второго порядка используют, если возможно найти вторую производную исследуемой функции. Их основой явля­ется метод Ньютона, предполагающий аппроксимацию иссле­дуемой функции Y = f(x) квадратичным полиномом в окрест­ностях некоторой точки х^(к) (точки начального приближения). Следующее приближение х^(k+1) определяется путем минимума квадратичной аппроксимации функции F(x), т.е. такой точки в окрестности х^(к), в которой вид функции в наибольшей степени «похож» на квадратичную. Различные модификации метода Ньютона в основном отличаются друг от друга способами расчета вторых производных. Методы второго порядка схо дятся быстрее градиентных, однако требуют вычислений вто­рых производных.

Методы многокритериальной оптимизации

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

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

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

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

Вам также может быть полезна лекция "2 Способы снятия конфликта в семье".

Определено множество показателей эффективности, значе­ния которых могут быть заданы в виде вектора q = {q₁, q₂, .... q_n) или соответствующей точки в n-мерном пространстве. Оп­ределены зависимости qi(μ, ν), i = 1, 2,..., п, каждого i-го пока­зателя от параметров μ  М и условий v  N выбора. Задана модель предпочтений показателей П_д. Требуется найти такие значения параметров выбора μ*, при которых значения пока­зателей эффективности q(μ^*, ν), удовлетворяют заданной мо­дели предпочтений П_д

Особенности использования. Все существующие методы многокритериальной оптимизации делятся на две группы [r]. К первой относятся методы, в которых количественно или ка­чественно оценивается степень важности каждого показателя для достижения предназначения системы управления в целом.

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

Во второй группе методов осуществляется поиск решения на всем пространстве критериев путем сужения области воз­можных решений. Из суженной области возможных решений субъективно выбирается одно.

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

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