Аксиома Парето о доминируемости решений

Если , то , где – решение, доминируемое решением .

Тогда решение не может входить в Парето-множество (лежать на Парето-границе). И, соответственно, если такой, что , то . Тогда Парето-множество содержит так называемые Парето - оптимальные решения.

Т.к. сформулировано условие формирования Парето-границы множества допустимых решений , тогда принцип Эджворта – Парето [8,9] определяет способ идентификации множества эффективных решений: выбираемые эффективные решения будут Парето-оптимальными. Т.е. эффективные решения в множестве Х нужно выбирать только среди Парето-оптимальных решений. В результате эффективное решение (множество эффективных решений) будет выбираться (определяться) в множестве Парето-оптимальных решений (эффективное решение будет выбираться на Парето- границе).

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

Решение добавляется в Парето-границу, если нет решений, которые бы его доминировали, и, соответственно, удаляется из границы, если оно доминируется рассматриваемыми на данном шаге алгоритма решениями. Данная формулировка целиком согласуется с формулировкой аксиомы о доминировании (о Парето – границе), приведённой в [9]: если для какой-либо пары решений и выполняется (соответственно ), то .

Тогда доминируемое решением решение не может быть включено в Парето- границу, а для решения выполняется условие: такого, что ,

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

В соответствии с заключениями, приведёнными в [9], при условии, что множество является конечным, множество является непустым. Допустим, что решаемая задача является задачей с конечным и счетным множеством возможных решений , то .

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

1) формирование множества Парето-оптимальных решений (Парето-границы ) множества допустимых решений ;

2) определение на Парето-границе тех эффективных решений, которые позволят максимизировать (в наибольшой степени) все критерии в многокритериальной задаче (в соответствии с аксиомой о предпочтениях ЛПР).

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

Рисунок 1 – Особенности определение решений, входящих в Парето-границу множества допустимых решений

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

1) при формировании решения решение исключается из рассмотрения, т.к. (в результате не может входить в Парето-границу);

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

3) переход от решения к решению обуславливает эквивалентность решений по одному из критериев и доминирование решением решения по другому критерию , в соответствии с этим (по введённому выше понятию отношения предпочтения (доминирования) решений) и решение (в соответствии с аксиомой);

4) при переходе от решения к решению должна быть исследована возможность включения решения в Парето- границу (при условии, что решение исключено из неё); т.к. множество Парето образуют только те решения, которые не сравнимы с использованием отношения , а решение исключено из , тогда должно быть выполнено сравнение решения с решением , входящим в , т.к. (в соответствии с Рис. 1) связывание решений и отношение невозможно, то , также как ;

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

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

Выполненные рассуждения касаются доминирования и не доминирования решений , они позволили сформировать множество Парето в следующем виде:

.

В общем виде при переходе от решения к решению возможны следующие ситуации, определяющие реализацию отношения для них: 1) ; 2) ; 3) и .

Понятно, что в первом случае , во втором – , в третьем – и на рассматриваемом текущем шаге формирования Парето-границы.

Таким образом, в основу формирования множества положена аксиома «о предпочтениях ЛПР» и аксиома «о Парето- границе множества ».

Следует отметить, что вид границы Парето (выпуклость либо вогнутость) не рассматривается, определяется принадлежность (возможность включения) следующего рассматриваемого решения Парето-границе и необходимость исключения предыдущего рассматриваемого решения из этой границы в случае его доминирования. При этом принадлежность решения Парето-границе определяется на основе рассматриваемых условий доминирования и недоминирования решений (условий для отношений предпочтения/ доминирования). Т.к. в соответствии с принципом Эджворта – Парето эффективные решения принадлежат Парето-границе, тогда должен быть сформирован способ определения наиболее эффективного решения (эффективных решений) среди тех, которые принадлежат . В литературе [7-9] изложены различные способы определения эффективных решений, выбор которых будет обеспечивать выполнение аксиомы «о предпочтениях ЛПР» (выбор решения, в наибольшей степени максимизирующего все используемые критерии) [9].

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

В основу первого способа определения эффективного решения в множестве Парето (на Парето-границе) положено понятие идеальной точки (точки утопии) и метрики (расстояния) от текущего рассматриваемого решения до этой идеальной точки (Рис.2.)

Рисунок 2 – Определение эффективных решений на Парето-границе с использованием метода идеальной точки

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

В качестве меры удалённости точки критериального пространства от точки утопии для текущего рассматриваемого решения используется эвклидова метрика в виде:

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

Тогда для задачи определения эффективных решений на Парето-границе при наличии двух критериев (при векторном критерии) разработан алгоритм соответствующей процедуры принятия решений. Для реализации алгоритма принятия решений при двух критериях в рассмотрение введены следующие обозначения:

1) – множество значений критерия для решений (т.е. ); – множество значений критерия для решений (т.е. );

2) – количество элементов в множествах и ;

3) – индекс текущих рассматриваемых элементов в множествах и ;

4) , – i- е текущие рассматриваемые элементы множеств и ;

5) j– индекс рассматриваемого решения из множества Х, принадлежность которого Парето-границе будет исследована на текущем шаге алгоритма;

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

7) - некоторое текущее решение (), для которого исследуется возможность включения его в Парето-границу, решению соответствуют значения критериев и ;

5) – индекс текущего шага алгоритма.

7) n – количество решений в множестве Х (мощность множества решений Х).

Первоначальная инициализация введенных параметров, выполняемых на первом шаге алгоритма (при ) выглядит следующим образом: 1) ; ; 2) .

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

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

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

В этом случае алгоритм определения эффективных решений в множестве Х на основе метода идеальной точки имеет следующую последовательности шагов:

1) значения индекса j решения , возможность добавления которого в Парето-границу исследуется на текущем шаге алгоритма, задается равным 2 (j=2);

2) значение индекса i текущего рассматриваемого решения в множестве P(Х) (т.е. ) задается равным 1 (); для рассматриваемого элемента , значения критериев равны соответственно , ;

3) если для решения значение , тогда решение доминирует решение по критерию , которому соответствует значение ; если условие доминирования решением решения по критерию выполняется, тогда необходимо реализовать проверку условия (); при невыполнении условия требуется осуществить переход к шагу 8;

4) если (), то рассматриваемое решение не может быть сравнимо с использование отношения предпочтения с решением , которому соответствуют значения и (т.е. и ), выполняется переход к шагу 15;

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

;

;

6) смещение элементов массивов и с индексами (i+1),…,kp в позиции с индексами i,…,kp-1 (изменение вида массивов (множеств) и после исключения из них значений и , соответствующих решению , доминируемому решением ); при исключении i -ых элементов из множеств P1 и P2 на их место должны быть размещены значения и , поэтому индекс текущих рассматриваемых элементов в множествах и изменяться не должен;

7) если i=kp, тогда изменение количества решений в Парето-границе (множестве Р(Х)) kp=kp-1 и переход на шаг 15; если i<kp, тогда изменение количества решений в Парето-границе (множестве Р(Х)) kp=kp-1 и переход на шаг 3;

8) если условие () выполняется, то решение доминирует решение по критерию (), должна быть выполнена проверка условия (); если условие выполняется, то реализуется переход к шагу 9; при невыполнении условия реализуется переход к шагу 11;

9) выполняется проверка условия , если это условие выполняется, то решения и не могут быть сравнимы с использованием отношения предпочтения ( и ), выполняется переход к шагу 15;

10) реализуется проверка условия , если условие выполняется, то решение доминирует решение по векторному критерию f (), т.е. рассматриваемое решение не может быть включено в Парето-границу; тогда должно быть определено следующее решение , его значения критериев и , выполнен последующий анализ возможности включения его в Р(Х), для этого реализуется переход на шаг 19;

11) выполняется проверка условия (при реализации перехода на этот шаг данное условие выполняется априори); реализуется проверка условия , если условие () является истинным, то решение доминируется решением (которому соответствует значение ), поэтому решение не может быть включено в Парето-границу, реализуется переход к шагу 19; если , то решение эквивалентно решению (переход к решению не приводит к улучшению значения векторного критерия и анализируемое решение не включается в Парето-границу), выполняется переход к шагу 19;

12) выполняется проверка , если это условие является верным, то по критерию решение доминирует решение (); т.к. по критерию решения и эквивалентны и , то решение доминирует решение по векторному критерию ( или ), следовательно решение должно быть исключено из Парето-границы, а его значения и из множеств Р1 и Р2 соответственно, тогда преобразования этих множеств выполняется с использованием выражений:

;

;

13) смещение элементов массивов и с индексами (i+1),…,n в позиции с индексами i,…,n-1 (изменение вида массивов (множеств) и после исключения из них значений и , соответствующих решению , доминируемому решением ); при исключении i -ых элементов из множеств P1 и P2 на их место должны быть размещены значения и , поэтому индекс текущих рассматриваемых элементов в множествах и изменяться не должен;

14) если i=kp, тогда изменение количества решений в Парето-границе (множестве Р(Х)) kp=kp-1 и переход на шаг 15; если i<kp, тогда изменение количества решений в Парето-границе (множестве Р(Х)) kp=kp-1 и переход на шаг 3;

15) изменение индекса i текущих рассматриваемых элементов и множеств и следующим образом: i=i+1, если , то выполняется переход к шагу 3; если , то выполняется переход на шаг 16;

16) значения критериев и для анализируемого решения добавляются в множества и соответственно (само решение принадлежит Парето-границе ):

;

;

;

17) для решения вычисляется значение расстояния до точки утопии:

;

18) реализуется сравнение полученного значения со значением текущего эффективного решения, если , то: ; (т.е. выполняется сохранение (буферизация) текущего локального эффективного решения);

19) изменение индекса текущего рассматриваемого решения j следующим образом: j=j+1; если , то переход к шагу 2; в противном случае – шаг 20;

20) останов алгоритма (окончание алгоритма).

После окончания алгоритма множества (массивы) P1 и P2 содержат значения всех решений (), которые входят в Парето-границу (множество P(X)), а параметр представляет собой то решение, которое ближе всего находится к точке утопии.

Предложенный алгоритм может быть модифицирован следующим образом:

1) определение координат идеальной точки (координат точки утопии);

2) формирование Парето-границы для множества Х (определение множества P(X) решений и соответствующих им значений критериев f₁и f₂);

3) определение среди элементов множества Р(Х) такого решения , расстояние до идеальной точки для которого будет являться минимальным.

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

1) для точки – уступки по критерию f₁ для получения приращения по критерию f₂;

2) для точки – уступки по критерию f₂ для получения приращения по критерию f₁.

Порядок последовательных уступок по критериям для поиска эффективных решений на Парето-границе комментирует Рис.3.

Рисунок 3– Реализация процедуры метода последовательных уступок

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

1) при переходе от решения с координатами путем выполнения уступки по критерию f₂ получить приращение по критерию f₁;

2) при переходе от решения с координатами путем выполнения уступки по критерию f₁ получить приращение по критерию f₂.

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

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

Уступки по каждому из критериев будут продолжаться до тех пор, пока не будут определена некоторая «общая» точка критериального пространства, достижимая как из точки с координатами , так и из точки с координатами . Если такая точка не может быть найдена (т.е. не может быть выполнено одинакового количества уступок по каждому критерию для определения «общей» точки), тогда по каждому критерию выбираются те повторяющиеся решения, которые уже были выбраны (рассмотрены) до этого при реализации уступок по противоположному критерию, т.е.: 1) при реализации уступки по критерию f₂ определяется решение, которое уже было рассмотрено при выполнении уступок по критерию f₁; 2) при реализации уступки по критерию f₁ выполняется переход к решению, которое уже было рассмотрено при выполнении уступок по критерию f₂. При этом выполнение приведенных выше условий фиксируется одновременно, алгоритм реализации дальнейших уступок останавливается, а в качестве действующего (эффективного) решения может быть выбрано любое из двух решений, на которых алгоритм последовательных уступок был остановлен.

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

1) – множество значений критерия для решений (т.е. ), соответствующее множеству , используемое при реализации уступок по критерию из точки , – множество значений критерия для решений (т.е. ), соответствующее множеству , используемое при реализации уступок по критерию из точки ;

2) – множество значений критерия для решений (т.е. ), соответствующее множеству , используемое при реализации уступок по критерию из точки , – множество значений критерия для решений (т.е. ), соответствующее множеству , используемое при реализации уступок по критерию из точки ;

3) – индекс элементов векторов (множеств) , , при реализации уступок по критерию ;

4) – индекс элементов векторов (множеств) , , при реализации уступок по критерию ;

5) – множество решений , которым соответствуют значения критериев и при реализации уступок по критерию из точки

4) – множество решений , которым соответствуют значения критериев и при реализации уступок по критерию из точки ;

8) delta1 – параметр, определяющий общую величину приращения по критерию при реализации уступок по критерию при переходе из точки ;

9) delta2 – параметр, определяющий общую величину приращения по критерию при реализации уступок по критерию при переходе из точки ;

Первоначальная инициализация значений параметров алгоритма выполняется следующим образом: delta1=0; delta2=0. В соответствии с введенными обозначениями порядок шагов алгоритма метода последовательных уступок следующий (при условии сформированной предварительно Парето-границы и множеств и значений критериев и ):

1) на основе множества решений PX и множеств и значений критериев f₁ и f₂ реализовать инициализацию значений элементов множеств и , и , и следующим образом: , , (множества , , используются для реализации уступок по критерию f₂, множества , , для реализации уступок по критерию f₁);

2) элементы множеств (векторов) сортируются по: убыванию значений критерия f₂ для вектора (множества) , по возрастанию критерия для вектора (множества) ;