Многокритериальная оптимизация в ИО

      … 
 
 

      …           (1)

      где  DF₁ и DF₂ — абсолютные снижения уровня критериев при переходе от решения х' к решению х'' (для критерия 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,

     и заданы граничные условия

     …        

                       (13)

    …           (14)

    Среди решений системы (11) – (14) требуется  отыскать такое значение вектора  х*(х*1, … , х*n), при котором локальные  критерии примут по возможности максимальное (минимальное) значение одновременно.

    Рассмотрим  каждую отдельную функцию fi(x) и допустим, что для каждого фиксированного i (i=1,m) решена задача максимизации. Пусть соответствующие оптимальные планы характеризуются векторами

    … i=1,m           (15)

    На  этих оптимальных планах определим  значения критериев соответственно

    …            (16)

    Естественно, что векторы (15), определяющие векторы  точки в пространстве переменных (x1, x2,…, xn)є W, будут разными: некоторые из них могут совпадать друг с другом.

    Рассмотрим  вектор F(х) с компонентами F(x)|Foi из (15) и составим квадрат евклидовой нормы

    …           (17)

     вектора F(x) - Fo, определенного для всех xєW .

    Заметим, что Fo будет представлять собой единичный  вектор в пространстве вектора F(x). Назовем его идеальным значением вектора F(x). Поставленная задача теперь сформулируется так: дана система целевых функций (11) и даны условия задачи (12) – (14). Требуется определить точку xєW, в которой функция R(x) достигает минимума.

    Таким образом, отыскание векторно-оптимального плана xєW в данной задаче сведено к оптимизации выражения (17) на решениях системы линейных неравенств (12) – (14). Поскольку выражение (17) представляет собой квадратичную функцию переменных х1, …, хп, то задача отыскания векторно-оптимального плана свелась к задаче выпуклого программирования:

    Задана  выпуклая функция R(x), определенная на множестве xєW. Требуется отыскать точку xєW, обеспечивающую выполнение условия R(x*) = minR(x), xєW.

    Таким образом, алгоритм решения задачи (11) – (14) состоит из двух основных этапов:

    этап 1: maxFi(x), i=1, m;

    этап 2: min R(x).

2.4. Метод квазиоптимизации  локальных критериев  (метод последовательных уступок)

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

    Вначале производится качественный анализ относительной  важности критериев; на основании такого анализа критерии располагаются  и нумеруются в порядке убывания важности, так что главным считается критерий F1, менее важен F2, затем следуют остальные локальные критерии F3, F4,.. ., Fm. Максимизируется первый по важности критерий F1 и определяется его наибольшее значение M1. Затем назначается … 
 

    …           (18)

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

    После этого находим наибольшее значение М2 второго критерия F2 на множестве X(1), т. е. при условии, что значение первого критерия должно быть не меньше, чем M1-d1. Снова назначается значение уступки d2>=0, но уже по второму критерию, которое вместе с первым используется при нахождении условного максимума третьего критерия, и т. д. Наконец, максимизируется последний по важности критерий Fm при условии, что значение каждого критерия Fr из m—1 предыдущих должно быть не меньше соответствующей величины Мr - dг; получаемые стратегии считаются оптимальными:

    …

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

1. найти M1= …
2. найти M2= …          (19)
3. …

m) найти  Mm= …

    Если  критерий Fm на множестве стратегий, удовлетворяющих ограничениям задачи m) из (19) не достигает своего наибольшего значения Мm, то решением многокритериальной задачи считают максимизирующую последовательность {xk} из последовательности множеств

Xm-1ÌXm-2Ì … ÌX1Ì X

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

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

    Шаг 1. Пусть х01 — решение задачи (19)

    max Fl(x), xєX

    Шаг 2. Пусть xok - решение задачи

    max Fk(x), xєX(k-1)

    где Xk определяется из (19).

    Шаг 3. Если k<m, то устанавливаем k=k+1 и повторяем шаг 2. Если k = m, то

    хom считаем оптимальным решением.