1.6 Многопараметрическая оптимизация.

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

(взаимное согласова­ние) критериев оптимальности подсистем в соответствии с их назначением и связями, существующими между подсисте­мами.

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

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

Компромиссные решения

При разработке новых РЭС процес­сов, их аппаратурного оформления и соответствующих систем автоматического управления учитываются многочисленные качественные показатели. Каждый из них стремятся оценить количественно с помощью выбранного частного (локального) критерия оптимальности. Как уже указывалось, в реальных задачах не удается достичь одновременно экстремальных зна­чений всех рассматриваемых критериев оптимальности, по­скольку эти экстремумы соответствуют различным точкам пространства независимых переменных, варьируе­мых в процессе оптимизации. Следовательно, решение задачи многокритериальной оптимизации представляет собой неко­торый компромисс между частными критериями оптималь­ности. Обоснование принципа этого компромисса и составляет одну из основных концептуальных трудностей проблемы век­торной оптимизации. Для наглядного представления компромиссных решений рассмотрим задачу оптимизации с двумя критериями качест­ва f1 и f2. Если каждый из них является непрерывной функ­цией независимых переменных x1,x2,,...,xn,, изменяющихся в некоторой области пространства , то существует не­которая область О соответствующих значений частных кри­териев оптимальности (рис. 1).

Рис. 1. Область возможных решений О и множество компромиссов CD

Каждому набору частных критериев f1 и f2 соответствует определенная точка области Q. Точки области Q делятся на улучшаемые и неулучшаемые.

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

О (см. рис. 1). Очевидно, в точке В оба критерия f1 и f2 имеют большие значения, чем в точке А. Следовательно, ре­шение задачи в точке В лучше, чем решение в точке А. Про­цесс улучшения решений можно продолжить, двигаясь в том же направлении к границе области , где дальнейшее улуч­шение решений прекращается. Максимальные значения кри­териев f1 и f2 достигаются в точках D и С соответственно. Точки, принадлежащие линии CD, обладают особым свой­ством: двигаясь вдоль линии CD, нельзя улучшить значение одного из критериев, не ухудшив при этом значение другого критерия. В силу этого множество точек, образующих линию CD, называют множеством компромиссных решении, или множеством компромиссов. Решения, соответствующие мно­жеству компромиссов, принято называть эффективными. Легко убедиться в том, что множеству компромиссов мо­гут принадлежать лишь точки на границе области возмож­ных решении Q; совокупность критериев, соответствующих любой точке, лежащей внутри этой области, может быть улучшена путем движения к границе.

Рис. 2. Разновидности областей возможных решений и множеств компромиссов

Отсюда следует, что, например, на рис. 2, а отрезок границы между точками А и В не принадлежит множеству компромиссов, поскольку его можно в целом улучшить с по­мощью отрезка граничной кривой между точками С и D.

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

Основные понятия и определения

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

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

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

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

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

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

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

Оптимизация по нескольким параметрам.

Обобщенная целевая функция.

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

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

Здесь -наилучшее значение целевой функции, найденное при решение задачи без компромиссной оптимизации.

весовой коэффициент, учитывающий важность i-го критерия.

При этом .

Существует и другая возможность:

Здесь

. При этом .

Определение коэффициентов веса параметров

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

Непосредственное назначение коэффициентов веса.

При непосредственном назначении коэффициентов веса i-тый эксперт оценивает сравнительную важность рассматриваемых параметров, которые будут входить в целевую функцию. В этом методе каждый i-ый эксперт для каждого k-ro параметра должен назначить коэффициент веса таким образом, чтобы сумма всех коэффициентов веса, назначенных одним экспертом для различных параметров, равнялась единице. Это требование можно записать так:

, где n — число экспертов.

1. Определить число параметров К, которые будут включены в целевую функцию.

2. Сделать таблицу по форме, которую мы будем называть базовой.

Определения ко­эффициента вариабильности = Cреднее квадратичное отклонение/ Среднее значение коэффициента веса . Значение коэффициента вариабильности показывает величину разброса экспертных оценок. При v < 0,2 оценки экспертов можно считать согласованными. В случае v > 0,2 целесообразно провести с экспертами содержательное обсуждение важности оцениваемых параметров, после чего повторить экспертизу. При сохранении величины разброса целесообразно учитывать вероятностный характер экспертных оценок по методам, при­веденным ниже. Как показывает опыт, удовлетворение экспертами требования

, где n — число экспертов при К > 3, вызывает затруднение.

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

Оценка важности параметров в баллах

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

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

Метод парных сравнений.

Если при k > 3 одновременная оценка всех параметров вызыва­ет затруднения, их можно оценивать еще одним методом, ко­торый называется методом парных сравнений. Этот метод реа­лизуется с помощью следующего алгоритма.

1.Определить число оцениваемых параметров k и число экспертов n.

Пусть k = 5; n = 4.

2. Для каждого эксперта составить отдельную таблицу.

В этой таблице эксперт должен ввести оценку парных сравнений, которая заключается в следующем. Если k-ый параметр важнее j-ro, то в ячейке, принадлежащей k-ой строке и j-му столбцу, указывается 1, иначе — 0. Пример заполнения такой таблицы первым экспертом приве­ден ниже, из которой видно, что по оценке этого эксперта параметр А менее важен, чем параметр Б и Д, но более важен, чем В и Г .

Пример заполнения таблицы для 1-го эксперта по этим данным приведен в следующей таблице.

Схемы компромиссов. Принцип равномерности.

В общем случае он состоит в стремлении к равномерному повышению качества оптимизируемого объекта по всем част­ным нормированным критериям .

Этот принцип имеет несколько разновидностей:

а. Принцип равенства нормированных критериев. По этому принципу наилучшим компромиссным решением х* является такое, при котором достигается равенство всех нормированных частных критериев, т. е. f1(х*)= f2(х*)=....= fn(х*)

Иногда этот принцип является чрезмерно «жестким». Он может приводить к ситуациям, когда решение задачи полу­чается вне зоны компромисса или отсутствует.

б. Принцип квазиравенства.

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

дельных нормированных частных критериев отличаются друг от друга не более, чем на е.

в. Принцип «справедливой уступки».

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

2. Принцип последовательной «уступки».

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

точности, с которой известны исходные данные, некоторая «уступка» f1, которую можно допустить для того, чтобы обратить в максимум второй критерий f2.

Далее налагаем на критерий fi ограничение, чтобы он был не меньше, чем (f1( х*)—f1. При этом ограничении ищем решение, обращающее в максимум критерий f2.

Затем назначается уступка для критерия f2, и т,д.При таком способе нахождения компромиссного решения сразу видно, ценой какой «уступки» в одном частном крите­рии приобретается выигрыш в другом. На практике используются и некоторые другие схемы компромиссов.

Использование множителей Лагранжа.

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

fiopt=min fi(x), i=1,k. хX.

Метод е-ограничений [21] предполагает видоизменение постановки этой задачи: f1opt=min f1(x),с учетом ограничений на остальные критерии оптимальности: eifi(x),

где ei — максимальные допустимые (пороговые) значения критериев оптимальности, кроме первого.

Для решения задачи составляется функция Лагранжа

где — неопределенные множители Лагранжа.

Рассмотрим два примера использования этого метода [21].

Пример 1.

В этой задаче используются два критерия оптимальности и две управляемые независимые переменные

Решение.

Первая фаза решения состоит в преобразовании исходной постановки задачи:

с учетом ограничения

Построим функцию Лагранжа:

Подставляя в нее выражения для f ₁ и f₂ получим

здесь —неопределенный множитель Лагранжа.

Найдем частные производные от функции Лагранжа по всем аргументам и приравняем их к нулю:

Решив систему, получим соотношение

Из выражения для получим соот­ношение

2 3 4 5 6 7 -'•t

Рис. З. Неулучшаемые (Парето-оптимальные) решения в пространстве управляемых перемен­ных

Рис. 4. Эффективное множество компромиссов в це­левом пространстве

На рис. 3 изображено множество компромиссов. Оно пред­ставляет собой отрезок прямой линии. Линии постоянного уровня каждого из критериев оптимальности являются окружностями. Отметим, что полученное решение не зависит от введенного ограничения e.

На рис. 4 показано множество компромиссов в целевом пространстве.

Численные результаты решения этой задачи представлены в табл. 1.

Таблица 1

Множитель Лагранжа является функцией f₁ и f_{2 .}Это, в частности, видно на рис. 5.

Рис. 5. Множитель Лагранжа как функция крите­рия оптимальности f₂

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

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

Пример 2.

Математическая формулировка задачи имеет следующий вид:

Решение.

Перепишем задачу в форме е-ограничений: с учетом .Функция Лагранжа имеет следующий вид:

Подставляя сюда выражения для , и ис­пользуя метод неопределенных множителей Лагранжа, по­лучаем:

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

Рассматриваемая задача может быть записана в ином виде, например:

с учетом ограничений ,

Функция Лагранжа для задачи, записанной в этой фор­ме, имеет следующий вид:

Решая эту задачу с помощью метода неопределенных множителей Лагранжа, получим:

Результаты решения рассматриваемой задачи приведены в табл. 2.

Таблица 2

Неулучшаемые решения задачи

На рис. 6 представлено множество неулучшаемых реше­ний (множество Парето) в

пространстве управляемых пере­менных .

6. Постановка задачи динамического программирования

Динамическое программирование – это поэтапное планирование

многошагового процесса, при котором на каждом этапе оптимизируется только

один шаг. Управление на каждом шаге должно выбираться с учетом всех его последствий в будущем. В общем виде постановка задачи ДП сводится к следующему. Имеется некоторая управляемая операция или целенаправленное действие, распадающаяся естественно или искусственно на n шагов. На каждом шаге осуществляется распределение и перераспределение ресурсов, участвующих в операции, с целью улучшения ее результата в целом. Это распределение ДП называется управлением операции и обозначается Y.

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

w(u) = w(u1,u2,…,un).

Управление, при котором показатель достигает максимума, называется оптимальным управлением.

w(u^*) = max w(u)

u

Оптимальное управление многошаговым процессом состоит из совокупности оптимальных пошаговых управлений.

u* = (u₁^*, u₂^*,…,u_n^*)

Задача ДП – определит оптимальное управление на каждом шаге и тем самым оптимальное управление всей операцией в целом.

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

Выделим особенности модели динамического программирования:

- задача оптимизации интерпретируется как n-шаговый процесс управления;

- целевая функция равна сумме целевых функций каждого шага;

- выбор управления на k-м шаге зависит только от состояния системы к этому шагу и не влияет на предшествующие шаги (нет обратной связи);

- состояние s_k после k-го шага управления зависит только от предшествующего состояния s_k-1 и управления Х_k (отсутствие по­следействия);

- на каждом шаге управление Х_k зависит от конечного числа управляющих переменных, а состояние s_k - от конечного числа па­раметров.