«Многокритериальная оптимизация в ио» (стр. 2 из 4)
Задача многокритериального математического программирования имеет вид: [1, c. 41-43]
max{f1(x)=F1},
max{f2(x)=F2},
...
max{fk(x)=Fk}, при xєX, где
X – множество допустимых значений переменных х;
k – число целевых функций (критериев);
Fi – значение i-го критерия (целевой функции),
“max” – означает, что данный критерий нужно максимизировать.
Заметим, что по существу многокритериальная задача отличается от обычной задачи оптимизации только наличием нескольких целевых функций вместо одной.
При наличии в многокритериальной задаче критериев с разной размерностью с целью устранения данной проблемы используют нормализацию критериев. Способы нормализации представлены в таблице 1.1.
Таблица 1.1.
Способы нормализации
В данной таблице y – элемент пространства G. G – пространство элементов произвольной природы, называемых целевыми термами (в конкретных интерпретациях это совокупность, перечень или нумерация качественных свойств) элементов xєX.
Сверткой компонент многоцелевого показателя fєF называется отображение gє{F->R1}, которое преобразует совокупность компонент многоцелевого показателя f, соответствующих целевым термам yєY, в скалярный целевой показатель g(f(x|y)= g[{f(x|y}yєY]єR1. Основными видами сверток являются линейные, минимизационные, максимизационные, произведения и функции Кобба-Дугласа вида:
…
…
Проблемы получения и обоснования выбора сверток составляют основное направление теории полезности.
К настоящему времени сформулированы основные принципы выбора, приведенные в таблице 1.2. (приложение 1)
В задачах выбора решения, формализуемых в виде модели векторной оптимизации, первым естественным шагом следует считать выделение области компромиссов (или решений, оптимальных по Парето).
Вектор называется оптимальным по Парето решением, если не существует хєХ такого, что выполнены неравенства
…
…
Областью компромиссов Гх называется подмножество допустимого множества решений Х, обладающего тем свойством, что все принадлежащие ему решения не могут быть улучшены одновременно по всем локальным критериям — компонентам вектора эффективности. Следовательно, для любых двух решений, принадлежащих области Гх(х', x''єГх ), обязательно имеет место противоречие хотя бы с одним из локальных критериев. Это автоматически приводит к необходимости проводить выбор решения в Гх на основе некоторой схемы компромисса, что и послужило причиной для названия этого подмножества областью компромиссов.
Оптимальное решение, выбираемое на основе многокритериального подхода независимо от …
… областью компромиссов Гх, которая, как правило, значительно уже всей области возможных решений Х. Рассмотрим теперь некоторые методы многокритериальной оптимизации.
Глава 2. Некоторые методы многокритериальной оптимизации
2.1. Принцип справедливого компромисса
Пусть все локальные критерии, образующие вектор эффективности, имеют одинаковую важность.
Справедливым будем считать такой компромисс, при котором относительный уровень снижения качества по одному или нескольким критериям не превосходит относительного уровня повышения качества по остальным критериям (меньше или равен).
Этому принципу можно дать следующую математическую интерпретацию. [6] Пусть в области компромиссов Гх даны два решения х’ и х’’, качество которых оценивается критериями F1(х) и F2(х). Решение х' превосходит решение х’’ по критерию F1, но уступает ему по критерию F2. Необходимо сравнить эти решения и выбрать наилучшие на основе принципа справедливого компромисса. Для сравнения этих решений на основе принципа справедливого компромисса введем меру относительного снижения качества решения по каждому из критериев – цену уступки x:
…
… (1)
где DF1 и DF2 — абсолютные снижения уровня критериев при переходе от решения х' к решению х'' (для критерия F1) и при обратном переходе (для критерия F2).
Если относительное снижение критерия F1 больше, чем критерия F2, то следует отдать предпочтение решению х'. Это следует из сравнения цены уступки по каждому критерию.
Алгоритм решения задачи векторной оптимизации, основанный на принципе справедливого компромисса, включает следующие шаги.
Шаг 0. Выбираем х' и х’’є Dx.
Шаг 1. Вычисляем по формулам (1) х1 и х2.
Шаг 2. …
Шаг 3. Если не существует вектора хєX предпочтительнее xI или xII, то решение останавливается, иначе выбираем новый вектор xIII и переходим к шагу 1.
Модель определения области компромиссов, а также модель …
… нормализацию критериев, т. е. искусственно приводить их к единой мере.
Большинство принципов нормализации основывается на введении идеального решения, т. е. решения, обладающего идеальным вектором эффективности Fи. Это идеальное решение можно априорно предположить исходя из информации об объекте, а можно решить задачу оптимизации для каждого локального критерия и соответствующее этим решениям значение вектора эффективности принять за идеальный вектор эффективности Fи. Тогда выбор оптимального решения становится равнозначным наилучшему приближению к этому идеальному вектору Fи = (Fи , … , Fиn) В этом случае вместо действительного значения критериев рассматриваются или их отклонение от идеального значения
… (2)
или их безразмерное относительное значение
… (3)
При решении данной проблемы используются оба способа нормализации. Таким образом, успешное решение проблемы нормализации во многом зависит от того, насколько точно и объективно удается определить идеальное качество решения.
После нормализации критериев эффективности задача выбора решения приобретает …
… Это дает возможность проводить обоснованный выбор принципов оптимальности и выявлять их логический смысл.
Итак, для данного случая принцип оптимальности идентичен принципу приближения, а обобщенный скалярный критерий оптимизации – критерию приближения, являющемуся некоторой функцией отклонения от идеальной функции.
2.2. Принцип слабой оптимальности по Парето
Вектор х1єХ называется слабо оптимальным по Парето решением (оптимальным по Слейтеру), если не существует вектора х1єХ, такого, что
…
Пусть xoj (i=1,m) есть оптимальные решения для обычных скалярных оптимизационных задач, каждая из которых максимизирует компоненту Fi(х) вектора F (х):
… (4)
Если они являются максимальными решениями для каждой i, то считаем, что Fj(xoj) >Fi(xj) (i=1,m), где xoj — оптимальное решение задачи (4).
Положим, что Soj изображает множество решений, каждое из которых соответствует компоненту Fj, и Soj = … (5)
где aj представляет допустимое количество ограничений соответствующей области по отношению к Fj. Тогда оптимальное достаточное решение это такое решение, при котором минимальный компонент (наихудший компонент) максимизируется на множестве, удовлетворяющем достаточному условию хєХ и хєSo1nSo2n…,Som. Оно может быть сформулировано как
… (6)
х, z при
… (7)
… (8)
хєХ. (9)
Здесь задача (6) – (9) неразрешима, если аj не настолько велико, что пересечение {S°j} непусто. Величины аj должны быть определены на основе значений Fj(xoj) или анализа точности. Можно доказать, что оптимальное решение задачи (6) – (9) есть оптимальное решение по Парето.
Алгоритм решения задачи имеет следующие этапы.
Шаг 1. Полагаем l=1 и решаем задачу
max z (10)
х, z при
Fj(x)>=z;
Fi(x)>=Fj(x)oj—aj, i=1,m; хєХ.
Вызываем исходное решение x1 и оцениваем целевую функцию F(x1).
Шаг 2. Когда хl задано, разлагаем F(хl) на удовлетворительные и неудовлетворительные компоненты. Обозначим их соответственно через Sl и Sl. 
Если Sl, тогда эта задача считается неразрешимой, а если Sl ºÆ, то х1 — оптимальное, отвечающее требованиям решение. Если S <> Æ и Sl <> Æ, то для jєSl определяется аlj>0, допустимое по отношению к Fj(xl) [аlj=0 означает, что j-я целевая функция fj(x) не может принимать значение, отличное от fj (xl)].Ш а г 3. Решаем задачу
max z
х, z
при условии
Fj(x)єz, jє Sl;Fi(x)>=Fj(x)oj—aj, jєSl; хєХ.
Вызываем исходное решение xl+l. Если xl+1=xl, то задача будет неразрешимой; если xl+1<>xl, то полагаем 1 = 1+1 и возвращаемся к шагу 2. При этом алгоритм заканчивается.
2.3. Принцип приближения по всем локальным критериям к идеальному решению
В основу данного подхода положена идея приближения по всем критериям. [7]
Пусть дана задача многокритериального программирования
max{f1(x)=F1},
max{f2(x)=F2}, (11)
:
max{fk(x)=Fk}, xєX,
…