Применение обобщенного логического критерия для аппроксимации области эффективности в многокритериальных задачах оптимизации

Размещено на http://www.allbest.ru/

Применение обобщенного логического критерия для аппроксимации области эффективности в многокритериальных задачах оптимизации

Д.Е. Шапошников, И.В. Костина

Нижегородский государственный университет им. Н.И. Лобачевского

Нижегородский государственный технический университет

им. Р.Е. Алексеева

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

Ключевые слова: Принятие решений, многокритериальный выбор, область эффективных решений, качественная информация о предпочтениях, аппроксимация области решений, оптимальных по Парето.

Задачи многокритериального выбора широко распространены в различных отраслях деятельности, и, следовательно, в различных предметных областях [1-5]. При этом под задачей выбора понимается ситуация необходимости одной (наиболее подходящей) альтернативы из множества возможных (допустимых) вариантов. Большинство таких задач являются многокритериальными (задачи многокритериального выбора - МКВ), то есть имеющиеся альтернативы оцениваются сразу по нескольким критериям [6-8].

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

Существуют подходы к задаче многокритериального выбора, учитывающие качественную информацию о предпочтениях ЛПР [10]. Основным недостатком этих методов является требование к ЛПР о вводе достаточно большого объема дополнительных параметров, отсутствие (хотя бы, частичное) которых ставит под вопрос применимость этих методов. Описанная методика предполагает использование ровно того количества информации, которое ЛПР готово предоставить (в частном случае, вообще отсутствие такой информации).

Одним из наиболее распространенных способов решения задач МКВ является применение обобщенного критерия оптимальности, в состав которого входят весовые коэффициенты важности , отражающие представление лица, принимающего решение (ЛПР) об относительной важности частных критериев оптимальности. При этом важность критериев здесь понимается в смысле аксиоматической теории важности [11], что позволяет считать: если известна дополнительная информация вида "-й критерий не менее важен, чем j-й критерий (), то для весовых коэффициентов и справедливо соотношение:

. (1)

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

Весовые коэффициенты могут быть назначены ЛПР различными способами [10, 13, 14]. Но все известные методы требуют полных ответов (чаще всего, с числовыми оценками) на вопросы, которые выбранный метод задает.

В ряде работ [10, 12] был предложен и развит подход, при котором весовые коэффициенты важности частных критериев являются неконтролируемыми факторами, их значения могут быть различными для различных вариантов выбора, и значения их могут быть вычислены по принципу гарантированного результата:

. (2)

В качестве обобщенного критерия оптимальности могут быть использованы различные функции [10], в частности, аддитивный и среднестепенной обобщенные критерии. Особое место среди них занимает обобщенный логический критерий максимизации, который можно, с некоторым приближением, назвать «обобщенным критерием максимального риска при расчете весовых коэффициентов»:

. (3)

Таким образом, исходная задача (2) при использовании данного обобщенного логического критерия формулируется так:

. (4)

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

. (5)

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

Можно предположить, что от ЛПР получена дополнительная качественная информация, устанавливающая для некоторых L пар частных критериев (необязательно для всех ) предпочтение i-го критерия над j-м критерием на всем множестве D допустимых вариантов:

. (6)

Информация (6) является качественной, так как из нее следует, что i-й критерий важнее j-го критерия, но нельзя сказать, во сколько раз. Тогда качественная информация (6) в соответствии с соотношением (1) позволяет уточнить определение области допустимых значений (5) весовых коэффициентов следующим образом:

.

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

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

. (8)

Будем считать, что дополнительная качественная информация (6) является непротиворечивой, если область не пуста.

Для данного типа обобщенного критерия и приведенной области допустимых значений может быть получено аналитическое решение задачи вычисления весовых коэффициентов важности частных критериев оптимальности по принципу гарантированного результата [15]:

, (9)

, (10)

а область допустимых значений определяется выражением (8).

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

Введем дополнительные обозначения:

, - множество вершин графа , из которых имеется путь в вершину , включая ее саму;

- мощность множества ;

-- произвольный путь в графе :,

где -- дуга, входящая в путь, -- число дуг в пути ;

- множество всех путей из вершины в вершину ;

для всех (11)

где - уточняющий коэффициент для соответствующей дуги графа ;

. (12)

Учитывая введенные обозначения, можно сформулировать следующую теорему.

Теорема.

Оптимальным решением задачи (8)-(10) является вектор с компонентами, определяемыми выражениями

(13)

, (14)

величины и определяются из соотношений (11) и (12) соответственно, а индекс определяется из соотношения

, (15)

. (16)

Доказательство теоремы.

Доказательство проведем индукцией по слоям.

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

. (17)

Поскольку информация о предпочтениях отсутствует, для всех . Из (13) видно, что сформулированная теорема справедлива:

2. Пусть теорема справедлива для слоев, то есть для любой вершины из слоев имеем соотношение:

 для всех ,

где - множество вершин, расположенных на первых слоях графа предпочтений, - количество вершин на первых слоях графа, вычисляются по формулам (13)-(16).

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

,

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

Оценим значение обобщенного критерия :

. (18)

Для первого значения можем применить сформулированную теорему, положив

.

Тогда для выражения (21) можем записать:

,

.

Рассмотрим два возможных случая.

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

. (19)

Выражение (19) линейно относительно и достигает максимального значения, когда . Тогда

. (20)

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

. (21)

Выражение (21) получается подстановкой значения в (16).

Таким образом, учитывая выражения (20) и (21), получаем

.

Если , то условие (14) выполняется для первых слоев графа предпочтений, следовательно, соотношения (13)-(16) справедливы и для слоя.

Если , то в качестве индекса принимаем индекс -той вершины. В этом случае выражение (13) имеет место, так как для всех выполняется

,

,

а величины определяются из соотношений (14) и (12) соответственно.

Теорема доказана.

Следствие 1.

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

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

(22)

, (23)

а индекс определяется из соотношения

, (24)

. (25)

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

.

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

(26)

где индекс определяется из соотношения

, (27)

. (28)

Выражения (26)-(28) могут быть получены из выражений (13)-(16), если положить все величины и , определяемые формулами (11) и (12) соответственно, равными единице. Выражения для весовых коэффициентов (26)-(28) аналогичны выражениям, полученным в [10].

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

.

Тогда оптимальным решением задачи (9) является вектор весовых коэффициентов с компонентами

(29)

где индекс определяется из соотношения

, (30)

. (31)

Выражения (29)-(31) могут быть получены из выражений (22)-(25), если положить все величины , определяемые формулой (11), равными единице. Аналогичный результат приведен в [10].

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

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

К настоящему времени сформировались несколько основных подходов к аппроксимации границы Парето [16-19]: покрытие допустимого множества решений шарами переменного радиуса; применение полиэдральной аппроксимации на основе построения последовательностей аппроксимирующих многогранников с растущим числом вершин; свертывание частных критериев в обобщенный параметрический критерий оптимизации; методы, основанные на случайном поиске и другие.

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

Схема построения аппроксимации подобласти эффективности:

- задаются начальные значения для уточняющих коэффициентов: ;

- выбирается шаг сетки , (например );

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

- для каждого набора вычисляются весовые коэффициенты важности , и для них находится значение обобщенного логического критерия;

- находится точка критериального пространства , являющаяся оптимальной при вычисленном наборе весовых коэффициентов ;

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

Основные характеристики предложенной схемы:

- количество частных критериев оптимальности ограничено;

- строится аппроксимация подобласти области Парето (определяется предпочтениями ЛПР);

- предпочтения ЛПР определяются по описанной выше методике;

- для аппроксимации применяется схема параметрического использования уточняющих коэффициентов ;

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

Приведем пример построения схемы аппроксимации в стандартной тестовой задаче многокритериальной оптимизации DTLZ 4.

В общем виде задача формулируется следующим образом:

(32)

(33)

- задаваемый параметр степени,

- область допустимых значений варьируемых параметров, - число варьируемых пара метров.

Рассмотрим данную задачу для параметров степени и количества варьируемых параметров .

Были получены результаты аппроксимации области эффективности задачи для разных вариантов доминирования.

Задача 1.

Пусть ЛПР задало свои предпочтения на множестве частных критериев следующим образом:

. (34)

Граф предпочтений для данного случая представлен на рис.1.

Дополнительные коэффициенты и вычисляются с учетом выражений (11) и (12) соответственно. Результаты вычислений приведены в таблице 1.

Размещено на http://www.allbest.ru/

Рисунок 1. - Граф предпочтений для (34)

Таблица №1

Вычисление величин и для (34)

	,
1
2	-	1
3	-	1

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

Аппроксимация, полученная для задачи (32)-(33) при наличии дополнительной качественной информации от ЛПР (34) представлена на рис.2.

Рис. 2. - Аппроксимация области эффективности задачи (32)-(33) при наличии отношений предпочтения (34)

Задача 2. Пусть ЛПР задало свои предпочтения на множестве частных критериев следующим образом:

. (35)

Граф предпочтений для данного случая представлен на рис.3.

Размещено на http://www.allbest.ru/

Рис. 3 - Граф предпочтений для (35)

Дополнительные коэффициенты и вычисляются аналогично первой задаче. Результаты вычислений приведены в таблице 2.

Таблица №2

Вычисление величин и для (35)

	,
1	-	1
2
3	-	1

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

Аппроксимация, полученная для задачи (32)-(33) при наличии дополнительной качественной информации от ЛПР (35) представлена на рис.4.



Рис. 4 - Аппроксимация области эффективности задачи (32)-(33) при наличии отношений предпочтения (35)

Задача 3. Пусть ЛПР задало свои предпочтения на множестве частных критериев следующим образом:

. (36)

Граф предпочтений для данного случая представлен на рис.5.

Размещено на http://www.allbest.ru/

Рис. 5 - Граф предпочтений для (36)

Дополнительные коэффициенты и вычисляются аналогично предыдущим задачам. Результаты вычислений приведены в таблице 3.

Таблица №3

Вычисление величин и для (36)

	,
1	-	1
2	-	1
3

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

Аппроксимация, полученная для задачи (32)-(33) при наличии дополнительной качественной информации от ЛПР (36) представлена на рис.6.

Рис. 6 - Аппроксимация области эффективности задачи (32)-(33) при наличии отношений предпочтения (36).

Литература

1. Батищев Д.И. Поисковые методы оптимального проектирования. - М.: Советское радио, 1975. 286 с.

2. Батищев Д.И. Методы оптимального проектирования. М.: Радио и связь, 1984. 248 с.

3. Батищев Д.И., Шапошников Д.Е. Многокритериальный выбор с учетом индивидуальных предпочтений. ИПФ РАН. Нижний Новгород, 1994. 92 с.

4. Batishchev D.I., Anuchin V.F., Shaposhnikov D.E. The Use of the Qualitative Information on the Importance of Particular Criteria for the Computation of Weighting Coefficients. // Multiobjective Problems of Mathematical Programming / Lecture Notes in Economic and Mathematical Systems, v.35. Springer-Verlag, 1991. P. 2-7

5. Касимова (Костина) И.В., Шапошников Д.Е. Использование обобщенного критерия максимального риска для вычисления весовых коэффициентов важности при решении многокритериальных задач // Материалы XVIII международной научно-технической конференции «Информационные системы и технологии ИСТ-2012». Нижний Новгород, изд-во Нижегородского государственного технического университета, 2012. С. 78-79.

6. Бронштейн Е.М. Аппроксимация выпуклых множеств многогранниками // Современная математика. Фундаментальные направления. Т22, 2007. С. 5-37.

7. Гермейер Ю.Б. Введение в теорию исследования операций. М.: Наука, 1971. 384 с.

8. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972. 368 с.

9. Подиновский В.В., Ногин В.Д. Парето-оптимальные решения многокритериальных задач. М.: Наука, 1982. 256 с.

10. Многокритериальная оптимизация: Математические аспекты / Березовский Б.А., Барышников Ю.М., Борзенко В.И., Кемпнер Л.М. М.: Наука, 1989. 128 с.

11. Подиновский В.В. Об относительной важности критериев в многокритериальных задачах принятия решений // Многокритериальные задачи принятия решений. М.: Машиностроение, 1978. С. 48-92

12. Каменев Г.К., Лотов А.В., Рябиков А.И. Использование параллельных вычислений при аппроксимации многомерной границы Парето в задачах многокритериальной оптимизации // Доклады Пятой Международной конференции «Параллельные вычисления и задачи управления». М.: ИПУ РАН, 2010. С. 241-264.

13. Климова О.Н., Ногин В.Д. Учет взаимно зависимой информации об относительной важности критериев в процессе принятия решений // Журнал вычислительной математики и математической физики, т. 46, №12. СПб., 2006. С. 2179-2191

14. Березкин В.Е, Каменев Г.К., Лотов А.В. Гибридные адаптивные методы аппроксимации невыпуклой многомерной границы Парето // Журнал вычислительной математики и математической физики, 2006, т. 46, №11. - С. 2009-2023

15. Лоскутов А.Б., Солнцев Е.Б., Петрицкий С.А., Терентьев П.В. Методика интегральной оценки уровня энергоэффективности непромышленных объектов // Инженерный вестник Дона, 2014, №3. URL: ivdon.ru/ru/magazine/archive/n3y2014/2477.

16. Земцов А.Н., Болгов Н.В., Божко С.Н. Многокритериальный выбор оптимальной системы управления базы данных с помощью метода анализа иерархий // Инженерный вестник Дона, 2014, №2. URL: ivdon.ru/ru/magazine/archive/n2y2014/2360

17. Лотов В.А., Поспелова И.И. Многокритериальные задачи принятия решений: учебное пособие. М: МАКС Пресс, 2008. 197 с.

18. Nelyubin A.., Podinovskiy V. Algorithmic decision rule using ordinal criteria importance coefficients with a first ordinal metric scale // Comput. Math. Math. Phys. 2012. № 1. P. 43-59.

19. Podinovskiy V. Using interval information on relative criteria tradeoffs in analyzing multicriterial decision making problems // Autom. Remote Control. 2010. Т. 71. № 8. P. 1648-1660.

20. Лазарев Е.А., Мисевич П.В., Шапошников Д.Е. Бикритериальная модель сети передачи данных // Системы Управления И Информационные Технологии. 2011. № 3.2 (45). С. 255-258.

Размещено на Allbest.ru

...