Проверка результатов многокритериального упорядочения объектов на парето-оптимальность

Проблематика транспортных систем

25

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

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

Библиографический список

1. Коренев Б. Г., Резников Л. М. Динамические гасители колебаний: Теория и технические приложения. - М.: Наука, 1988. - 304 с.

2. Поляков С. В., Килимник Л. Ш., Черкашин А. В. Современные методы сейсмозащиты зданий. - М.: Стройиздат, 1989. - 320 с.

3 Никитин А. А., Уздин А. М. Применение динамических гасителей колебаний для сейсмозащиты мостов // Экспресс-информация ВНИИИС. Сер. 14. Сейсмостойкое строительство. - 1986. - Вып. 9. - С. 20-24.

4 Поляков В. С. К вопросу об эффективности динамического гасителя при сейсмических воздействиях // Строительная механика и расчет сооружений. - 1980. - №5. - С. 49-53.

5 Kaynia A. M., Veneriano D., Biggs M. Seismic effectiveness of tuned mass dampers // J. Struct. Div. Proc. ASME. -1981. - V.107, №236. - P. 309-314.

6 Бенин А. В., Богданова Г. А. Численная оценка влияния параметров настройки динамического гасителя колебаний на эффективность его работы при сейсмических воздействиях // Сейсмостойкое строительство. Безопасность сооружений. - 2000. - №2. - С. 11-13.

7 Свид. на полезную модель RU №14593 U1, МПК 7E04 В 1/98. - Динамический гаситель колебаний зданий и сооружений // Т. А. Белаш, А. В. Бенин, Г. А. Богданова, С. В. Елизаров, Ж. В. Иванова - Заяв. №2000103556/20(003456) от 11.02.00. - Опубл. 10.08.2000, Бюл. № 22.

УДК 519.8 Д. П. Бураков

ПРОВЕРКА РЕЗУЛЬТАТОВ МНОГОКРИТЕРИАЛЬНОГО УПОРЯДОЧЕНИЯ ОБЪЕКТОВ НА ПАРЕТО-ОПТИМАЛЬНОСТЬ

ISSN 1815-588 X. Известия ПГУПС

2006/2

26

Проблематика транспортных систем

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

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

Введение

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

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

1 Модель задачи многокритериального выбора

Модель задачи многокритериального выбора представим следующей четверкой [2]:

(X, F, Y, f,

где X - множество оцениваемых объектов, X={xi, ..., Xn}, N >1;

F - множество критериев, выбираемых для оценивания объектов из X;

Y - область значений критериев;

f - асимметричное бинарное отношение, заданное в критериальном пространстве Rn и трактуемое как отношение предпочтения лица, принимающего решения (ЛПР).

Определим на множестве X вектор критериев f = (fi,., fj,---, fn), n >1. Тогда вектор значений критериев y(xi) = (y/i,.,y/j,.,y/n), определенный в базисе f, принадлежит множеству векторов оценок V = {yi,.,yz,.,yN}. Если компонентами векторов являются числовые функции со значениями, измеряемыми в количественной шкале, например шкале отношений или шкале интервалов, то V с Rn.

Задача многокритериального выбора решается путём реализации предпочтений ЛПР на множестве векторов оценок V. В силу однозначного соответствия между выбранными векторами оценок Y§ei и характеризуемыми ими объекта-

2006/2

Proceedings of Petersburg Transport University

Проблематика транспортных систем

27

ми, решением задачи является множество объектов Xsei, называемое множеством выбранных объектов.

2 Выбор парето-оптимальных объектов

Метод многокритериального выбора на основе доминирования векторных оценок объектов был предложен итальянским экономистом В. Парето. Согласно этому принципу, объект Х\ доминирует над объектом Х2 в том случае, когда он по всем критериям не хуже х2, а хотя бы по одному из них - лучше. В этом случае объект х\ называется доминирующим, а Х2 - доминируемым. Если xi не доминирует над Х2 и одновременно Х2 не доминирует над xi, то объекты xi и Х2 считаются несравнимыми или недоминируемыми. Множество, состоящее из недоминируемых объектов, называется множеством Парето.

Условие доминирования объекта Xi над объектом Xt (x2- > Xt) формулируется через условие доминирования представляющих их векторов

У = (Уа,---,Уи,---,Ут) иyt = (Ук1,--;Укр---Ук„)'-

y > yt > если "

В соответствии с определением, множество Парето в пространстве R может быть представлено следующим образом:

P

В связи с тем, что векторы объектов, вошедших в множество Парето, доминируют над векторами остальных объектов из X, то множество Парето всегда расположено на оболочке (границе) множества векторов V, а вошедшие в него объекты называются граничными [3].

С точки зрения ЛПР, оптимальные по Парето объекты заведомо предпочтительнее объектов, не вошедших в это множество. Множество Парето строится в предположении равной важности критериев, поэтому в нём ни один объект не может быть предпочтительнее других без указания важности критериев. Это связано с тем, что каждый объект из этого множества, превосходя другие объекты по одним критериям, уступает им по другим критериям.

Исходя из равной важности критериев и проанализировав структуру множества Парето, можно выявить случаи, когда его состав неоднороден. Так как множество Парето расположено на участке оболочки исходного множества векторных оценок, в случае её невыпуклости оболочка множества Парето также может быть не выпукла, т. е. содержать "впадины". Расположенные на "впадинах" объекты, которые отвечают условиям оптимальности по Парето, назовем условно-оптимальными, поскольку величина их улучшения по одним критериям меньше величины их ухудшения по другим критериям относительно других парето-оптимальных объектов, что недопустимо при равной важности критериев. Этих недостатков лишены объекты множества Парето, расположенные на выпуклой оболочке conv(V) исходного множества векторов:

ISSN 1815-588 X. Известия ПГУПС

2006/2

28

Проблематика транспортных систем

conv

На рисунке 1 представлено два варианта множества Парето, получаемых из множества X = {A, B, C, D, E, F, G, H} при условии f  max, yj = fj(x),

j = 1,2.

Получаем следующие множества Парето: P(X) = {B,C,D} (см. рис. 1, а), P(X') = {B,H,I,D} (см. рис. 1, б). Множество X' на рисунке 1, б получено в результате исключения объекта C из множества X. При этом вектор объекта H, вошедшего в множество Парето P(Xr), не принадлежит выпуклой оболочке conv(P) = {A, B, I, D, E, F, G}, следовательно, объект H является условнооптимальным.

а) б)

D

fy

4

H r

1 Д

- -

-

>

"J

/

/

X E _

_L

У1

Рис. 1. Проблема выпуклости дискретного множества Парето

2006/2

Proceedings of Petersburg Transport University

29

Проблематика транспортных систем

3 Упорядочение объектов

Эта задача решается с применением функций полезности. Они используются для преобразования многокритериальной задачи в однокритериальную

путём свёртки n критериев в один обобщённый суперкритерий. При этом век*

торная оценка у- объекта xj заменяется скалярной оценкой у i=/у-).

Так же как и критериям, суперкритерию придаётся направление оптимиза-

* *

ции (у  max или у  min), что позволяет считать его целевой функцией задачи выбора. Множество выбираемых объектов X§ei применительно к задаче упорядочения формируется из объекта, доставляющего максимум (минимум) супер критерию. Во многих задачах многокритериального упорядочения наибольшее применение получили аддитивная fa и мультипликативная/м функции полезности [3]:

у м

уj - у

J s J ,min

у a=fa(Y) = ^ w j у . - у .  5

j=i j j j ,max s j ,min

1-/м(У)= п

J=1

f \

1уj - уj ,min

- Wj---------—

у J ,max у J ,min j

Коэффициенты Wj, в сумме равные 1, отражают степень значимости каждого из критериев. Они задаются экспертами или ЛПР и являются фактором субъективизма в многокритериальном оценивании объектов. Проанализируем лучшие по упорядочению объекты на парето-оптимальность (недоминируе-мость).

4 Анализ упорядоченных объектов на парето-оптимальность

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

Рассмотрим эту проблему на следующем примере. Пусть дано множество

X = {A, B, C, D, E, F}; / = (/1,/2,/3); /  max; у = /(x), j = 1, 2, 3. Полученные оценки объектов указаны в таблице 1.

При заданных условиях множество Парето P(X) состоит из объектов A, B, C, E, F и G, из которых E, F, G доминируют над объектом D. Векторы этих объектов входят в оболочку множества векторных оценок в пространстве R3, представленную на рисунке 2.

ТАБЛИЦА 1. Оценки объектов

7 \ 3 У1 У2 Уз

ISSN 1815-588 X. Известия ПГУПС

2006/2

30

Проблематика транспортных систем

A 1 1 5

B 5 1 1

C 1 5 1

D 2 2 2

E 3 4.5 4.5

F 3.5 3 3

G 4.5 2 2

Рис. 2. Оболочка множества векторных оценок объектов

Из рисунка 2 видно, что полученная оболочка не выпукла, так как в неё вошёл вектор условно-оптимального объекта F. Сформируем выпуклую оболочку множества векторов оценок: conv(K) = {A,B,C,D,E,G}. По формуле (4) найдем парето-оптимальный участок выпуклой оболочки оценок: COnv(K)p =

conv(K) П P(^) = {A,B,C,E,G}.

2006/2

Proceedings of Petersburg Transport University

Проблематика транспортных систем

31

Каждый из объектов, вошедших в COnv(K)p, является претендентом на максимальную оценку по ФП. Первое место того или иного объекта связано с соотношением значимости критериев. На рисунке 3 в графической форме представлен результат упорядочения объектов в двухмерном подпространстве R3, образуемом критериями fi и fj. Сплошной линией представлен парето-оптимальный фрагмент COnv(K)p выпуклой оболочки множества оценок объектов, пунктирными линиями - проекции этих оценок на градиент функции полезности, использованной для скалярного упорядочения объектов.

При определённом сочетании значимости критериев доминируемый объект Xj может получить более высокую оценку ФП, чем недоминируемый объект Xk, если Xk не доминирует над Xj. Например, на рисунке 3 объект D, не входящий в парето-оптимальное множество, получает более высокую оценку, чем не доминирующий над ним объект B из множества Парето. Более высокие оценки ФП, чем у объекта D, получили доминирующие над ним объекты E, F и G.

Рис. 3. Проекция оценок объектов на градиент ФП

Изменение значимости критериев влияет на наклон градиента функции полезности, что влечёт изменение оценок объектов и, следовательно, изменение их порядка. При этом первыми по результатам упорядочения всегда оказываются объекты, вошедшие в недоминируемый участок выпуклой оболочки множества векторных оценок. В таблице 2 представлены результаты упорядочения объектов для четырех вариантов значимости критериев fi—f в функции полезности (4).

ISSN 1815-588 X. Известия ПГУПС

2006/2

32 Проблематика транспортных систем

ТАБЛИЦА 2. Оценки объектов по ФП при разных значениях весовых коэффициентов

Веса критериев Равные

7 \ 3 yi У2 У3 ФП Ранг ФП Ранг ФП Ранг ФП Ранг ФП Ранг

A 1 1 5 0,330 4 0,185 6 0,050 6 0,050 6 0,900 1

B 5 1 1 0,330 4 0,630 3 0,900 1 0,050 6 0,050 6

C 1 5 1 0,330 4 0,185 6 0,050 6 0,900 1 0,050 6

D 2 2 2 0,250 5 0,250 5 0,250 5 0,250 5 0,250 5

E 3 4.5 4.5 0,750 1 0,639 2 0,538 4 0,856 2 0,856 2

F 3.5 3 3 0,540 2 0,579 4 0,613 3 0,506 3 0,506 3

G 4.5 2 2 0,460 3 0,644 1 0,813 2 0,281 4 0,281 4

Как следует из таблицы 2, при различных сочетаниях весовых коэффициентов первое место в рейтинге объектов всегда занимает объект из недоминируемого участка выпуклой оболочки COnv(K)p. Объект F, который является условно-оптимальным по Парето, не становится первым ни при каких комбинациях значимости критериев. При неравной значимости критериев доминируемый объект D может получить более высокую оценку, чем не доминирующие над ним объекты A, B или C, но всегда уступает доминирующим над ним объектам E, F, G.

Заключение

Анализ лучших по функции полезности объектов на их парето-оптимальность показал:

первое место в рейтинге всегда занимает объект из парето-оптимального участка выпуклой оболочки множества векторов;

условно-оптимальный по Парето объект не становится первым ни при каких комбинациях значимости критериев;

доминируемый объект может получить более высокую оценку ФП по сравнению с не доминирующим над ним объектом из множества Парето.

Анализ лучших по функции полезности объектов на парето-оптимальность производился при помощи системы выбора и ранжирования "Свирь" [5].

Библиографический список

1. Саймон Г. Наука об искусственном. - М.: Мир, 1972.

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

3. Микони С. В. Теория и практика рационального выбора. - М.: Маршрут, 2004.

4. Микони С. В., Бураков Д. П. Парадоксы многокритериального ранжирования объектов // Труды междунар. конф. по мягким вычислениям и измерениям SCM'2003. - Т. 1. -СПб.: - СПбГЭТУ, 2003.

5. www.pgups.ru/nauka/mikoni

2006/2

Proceedings of Petersburg Transport University