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

Розглядається клас задач багатокритеріального вибору, в яких кінцева множина альтернатив відома, кількість альтернатив може бути досить великою, вони можуть оцінюватися як кількісно, так і якісно. Інформація про надання переваг подається як узагальнені (із зазначенням рівноцінності) ранжировки аль...

Full description

Saved in:

Bibliographic Details
Published in:	Проблемы управления и информатики
Date:	2006
Main Authors:	Васильев, С.Н., Котлов, Ю.В.
Format:	Article
Language:	Russian
Published:	Інститут кібернетики ім. В.М. Глушкова НАН України 2006
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/206752
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Методы и алгоритмы многокритериальной оптимизации на основе нестрогих ранжировок альтернатив по частным критериям и опыт компьютерной реализации / С.Н. Васильев, Ю.В. Котлов // Проблемы управления и информатики. — 2006. — № 1-2. — С. 28-38. — Бібліогр.: 5 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-206752
record_format	dspace
spelling	Васильев, С.Н. Котлов, Ю.В. 2025-09-22T07:58:20Z 2006 Методы и алгоритмы многокритериальной оптимизации на основе нестрогих ранжировок альтернатив по частным критериям и опыт компьютерной реализации / С.Н. Васильев, Ю.В. Котлов // Проблемы управления и информатики. — 2006. — № 1-2. — С. 28-38. — Бібліогр.: 5 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/206752 004.021 Розглядається клас задач багатокритеріального вибору, в яких кінцева множина альтернатив відома, кількість альтернатив може бути досить великою, вони можуть оцінюватися як кількісно, так і якісно. Інформація про надання переваг подається як узагальнені (із зазначенням рівноцінності) ранжировки альтернатив. Для даного класу задач пропонується комп’ютерна технологія пошуку компромісного розв’язку, що використовує якісні критерії і новий підхід до розв’язку проблем багатокритеріального вибору. A class of multicriteria choice problems is considered in which the finite set of alternatives is known, а number of alternatives can be considerably large, alternatives can be evaluated both numerically and qualitatively. The information about preferences is represented as generalized (with the equivalence indicated) rankings of alternatives. For the considered class of problems, the computer search technology of compromise solution is suggested. One uses the qualitative criteria and new approach for the solution of the problems of multicriteria choice. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Методы и алгоритмы многокритериальной оптимизации на основе нестрогих ранжировок альтернатив по частным критериям и опыт компьютерной реализации Методи і алгоритми багатокритеріальної оптимізації на базі нестрогих ранжувань альтернатив за частинними критеріями і досвід комп’ютерної реалізації Methods and Algorithms of Multicriteria Optimization Based on Non-Strict Rankings of Alternatives According to Individual Criteria and Their Computer Implementations Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Методы и алгоритмы многокритериальной оптимизации на основе нестрогих ранжировок альтернатив по частным критериям и опыт компьютерной реализации
spellingShingle	Методы и алгоритмы многокритериальной оптимизации на основе нестрогих ранжировок альтернатив по частным критериям и опыт компьютерной реализации Васильев, С.Н. Котлов, Ю.В.
title_short	Методы и алгоритмы многокритериальной оптимизации на основе нестрогих ранжировок альтернатив по частным критериям и опыт компьютерной реализации
title_full	Методы и алгоритмы многокритериальной оптимизации на основе нестрогих ранжировок альтернатив по частным критериям и опыт компьютерной реализации
title_fullStr	Методы и алгоритмы многокритериальной оптимизации на основе нестрогих ранжировок альтернатив по частным критериям и опыт компьютерной реализации
title_full_unstemmed	Методы и алгоритмы многокритериальной оптимизации на основе нестрогих ранжировок альтернатив по частным критериям и опыт компьютерной реализации
title_sort	методы и алгоритмы многокритериальной оптимизации на основе нестрогих ранжировок альтернатив по частным критериям и опыт компьютерной реализации
author	Васильев, С.Н. Котлов, Ю.В.
author_facet	Васильев, С.Н. Котлов, Ю.В.
publishDate	2006
language	Russian
container_title	Проблемы управления и информатики
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
format	Article
title_alt	Методи і алгоритми багатокритеріальної оптимізації на базі нестрогих ранжувань альтернатив за частинними критеріями і досвід комп’ютерної реалізації Methods and Algorithms of Multicriteria Optimization Based on Non-Strict Rankings of Alternatives According to Individual Criteria and Their Computer Implementations
description	Розглядається клас задач багатокритеріального вибору, в яких кінцева множина альтернатив відома, кількість альтернатив може бути досить великою, вони можуть оцінюватися як кількісно, так і якісно. Інформація про надання переваг подається як узагальнені (із зазначенням рівноцінності) ранжировки альтернатив. Для даного класу задач пропонується комп’ютерна технологія пошуку компромісного розв’язку, що використовує якісні критерії і новий підхід до розв’язку проблем багатокритеріального вибору. A class of multicriteria choice problems is considered in which the finite set of alternatives is known, а number of alternatives can be considerably large, alternatives can be evaluated both numerically and qualitatively. The information about preferences is represented as generalized (with the equivalence indicated) rankings of alternatives. For the considered class of problems, the computer search technology of compromise solution is suggested. One uses the qualitative criteria and new approach for the solution of the problems of multicriteria choice.
issn	0572-2691
url	https://nasplib.isofts.kiev.ua/handle/123456789/206752
citation_txt	Методы и алгоритмы многокритериальной оптимизации на основе нестрогих ранжировок альтернатив по частным критериям и опыт компьютерной реализации / С.Н. Васильев, Ю.В. Котлов // Проблемы управления и информатики. — 2006. — № 1-2. — С. 28-38. — Бібліогр.: 5 назв. — рос.
work_keys_str_mv	AT vasilʹevsn metodyialgoritmymnogokriterialʹnoioptimizaciinaosnovenestrogihranžirovokalʹternativpočastnymkriteriâmiopytkompʹûternoirealizacii AT kotlovûv metodyialgoritmymnogokriterialʹnoioptimizaciinaosnovenestrogihranžirovokalʹternativpočastnymkriteriâmiopytkompʹûternoirealizacii AT vasilʹevsn metodiíalgoritmibagatokriteríalʹnoíoptimízacíínabazínestrogihranžuvanʹalʹternativzačastinnimikriteríâmiídosvídkompûternoírealízacíí AT kotlovûv metodiíalgoritmibagatokriteríalʹnoíoptimízacíínabazínestrogihranžuvanʹalʹternativzačastinnimikriteríâmiídosvídkompûternoírealízacíí AT vasilʹevsn methodsandalgorithmsofmulticriteriaoptimizationbasedonnonstrictrankingsofalternativesaccordingtoindividualcriteriaandtheircomputerimplementations AT kotlovûv methodsandalgorithmsofmulticriteriaoptimizationbasedonnonstrictrankingsofalternativesaccordingtoindividualcriteriaandtheircomputerimplementations
first_indexed	2025-11-24T16:27:49Z
last_indexed	2025-11-24T16:27:49Z
_version_	1850484298417700864
fulltext	© С.Н. ВАСИЛЬЕВ, Ю.В. КОТЛОВ, 2006 28 ISSN 0572-2691 УДК 004.021 С.Н. Васильев, Ю.В. Котлов МЕТОДЫ И АЛГОРИТМЫ МНОГОКРИТЕРИАЛЬНОЙ ОПТИМИЗАЦИИ НА ОСНОВЕ НЕСТРОГИХ РАНЖИРОВОК АЛЬТЕРНАТИВ ПО ЧАСТНЫМ КРИТЕРИЯМ И ОПЫТ КОМПЬЮТЕРНОЙ РЕАЛИЗАЦИИ Введение. Достаточно распространенными на практике являются задачи многокритериального выбора, в которых конечное множество альтернатив из- вестно, альтернативы могут оцениваться как количественно, так и качественно, причем их количество достаточно велико, что не позволяет осуществить лицу, принимающему решение (ЛПР), выбор самостоятельно. На данный момент согласование качественных и количественных оценок происходит, как правило, с помощью сведéния всех показателей к количествен- ному типу, что может привносить в постановку задачи заведомо ложную инфор- мацию с непредсказуемыми и, может быть, негативными последствиями. Авторы разделяют известную точку зрения [1], что избавление от качествен- ных критериев и переход к задаче только с количественными критериями для ис- пользования развитых разнообразных методов принятия решений зачастую не обеспечены объективной информацией, позволяющей преобразовать общую мо- дель принятия решений в терминах структур порядка в более частную модель в топологических терминах меры близости (метрики, окрестности). Для рассматриваемого класса задач предлагается ориентированная на приме- нение ПЭВМ технология анализа качественных данных, позволяющая осуществ- лять эффективный в смысле вычислительных затрат и трудозатрат ЛПР поиск па- рето-оптимального компромиссного решения. 1. Постановка задачи. Под задачей выбора будем понимать пару ,, 〉〈 FX где }...,,,{ 21 nxxxX = — множество альтернатив ;ix ),,,( 21 mFFFF = — множество частных критериев, заданных нестрогими (с указанием равноценности альтернатив) ранжировками ,1321 321 ni j n j i j i j i j xQQxQxQxS −=  (1) где 1,1 −=α∀ n },,{ jjj IPQ ∈α jP — отношение строгого предпочтения, jI — отношение равноценности (эквивалентности). При этом для отношений строгого предпочтения чем раньше альтернатива в ранжировке, тем она предпочтительнее. Эквивалентные альтернативы записываются первоначально в порядке возраста- ния их идентификационных номеров. Для анализа таких альтернатив в дальней- шем вводятся процедуры 1 и 2, осуществляющие соответственно переупорядоче- ние альтернатив, эквивалентных рассматриваемой альтернативе таким образом, чтобы ее порядковый номер стал максимальным (процедура 1 — перенос в конец группы) или минимальным (процедура 2 — перенос в начало группы). Если ijπ — порядковый номер альтернативы ix в ранжировке ,jS то все множество ранжировок (1) может быть задано матрицами: — ранжировок ,,1 , ,1 ),( mjnqsS qj === где qjs равно идентификацион- ному номеру i альтернативы ix с порядковым номером ijq π= в ранжировке ;jS Проблемы управления и информатики, 2006, № 1–2 29 — эквивалентных альтернатив ,,1 , 1), ( mjn,idD ij === где     = = − .погруппуоднувнивходитнеесли,0 ;входитнекоторуювв,альтернатипоныхэквивалентгруппыномер j i i j ij Fx xFg d Под g далее понимается идентификационный номер группы эквивалентных по какому-либо критерию альтернатив ,0( lg ≤≤ где l — целая часть ;2/n если эквивалентных альтернатив нет, то ).0=l Далее используется также матрица приведенных номеров ),( ijeE = ,,1 ni = ,,1 mj = где ije — номер альтернативы ix в ранжировке ,jS учитывающий наличие в jS альтернатив, эквивалентных альтернативе ix (если ,0≠ijd то ije равен порядковому номеру после применения процедуры 2, в противном случае ).ijije π= Положим, что, по крайней мере, после применения некоторых процедур пред- обработки исходного описания задачи во множестве альтернатив отсутствуют решения, эквивалентные по всем частным критериям, и отношения jQ являются квазипорядками, т.е. рефлексивными, транзитивными и полными (полнота озна- чает ∗∗ ∈∀ xQxXxx j , или ).xQx j∗ Из множества задач выбора выделим те, в которых требуется найти решение, наиболее предпочтительное с точки зрения ЛПР. 2. Алгоритмы выделения множеств Парето и Слейтера. Наиболее объек- тивным этапом решения рассматриваемых задач является поиск множества паре- то-оптимальных решений. Напомним, что это решения, которые не уступают друг другу по частным критериям, или ParXx ∈ Par(X — множество парето-опти- мальных решений во множестве альтернатив X) тогда и только тогда, когда не существует Xx ∈′ такого, что mj ,1=∀ xRx j′ и mj ,10 ∈∃ , 0 xPx j′ где jR — отношение нестрогого предпочтения: .jjj IPR = Вполне естественно, что именно среди таких решений ЛПР ищет наиболее предпочтительное с его точки зрения. Поэтому выделение множества Парето является, как правило, одним из основных этапов при многокритериальном выборе. В ряде задач, в которых первоначальный список частных критериев может быть сокращен в процессе решения задачи (например, при проектировании техни- ческих систем), особый смысл приобретают решения, оптимальные по Слейтеру. Множество SlX таких решений формируется следующим образом: SlXx ∈ ⇔ не верно, что Xx ∈′∃ mj ,1=∀ .xPx j′ Для рассматриваемых задач многокритериального выбора предложены алго- ритмы, позволяющие получить множества Парето и Слейтера с минимальными вычислительными затратами [2]. Введем ряд обозначений. Пусть ],1[)( ixs xX ji j = — подмножество альтер- натив (их идентификационных номеров), расположенных в ранжировке jS меж- ду наилучшей (первой) и альтернативой ix (альтернатива ,1 js порядковый номер которой в ранжировке jS равен 1, — наилучшая альтернатива по j-му критерию), включая последние (т.е. js1 и ).ix Причем если ,kx∃ ,,1 nk ∈ и ,,1 mj ∈∃ для которых ,i j k xIx то перед формированием )( i j xX может применяться для ix 30 ISSN 0572-2691 процедура 1 либо процедура 2, и тогда )( i j xX будет включать соответственно либо всю группу альтернатив, эквивалентных ix по j-му критерию, либо только альтернативу ix из этой группы. Соответствующие множества обозначаются для определенности )(1 i j xX и ).(2 i j xX Решения ∑ = ∗ ∈ =∈ m j l jdf r xX Xx Xx l 1 2 )(minArg (2) с минимальным количеством альтернатив назовем лидирующими: сумма коли- честв альтернатив, которым rx уступает в ранжировках, минимальна. Ранее для построения алгоритмов выделения множеств Парето и Слейтера были сформулированы и доказаны утверждения [2], которые здесь приводятся без доказательств. Утверждение 1. Решения ∗∈ Xx всегда парето-оптимальны. Утверждение 2. Для любой альтернативы ,Xxr ∈ ,2Par rSX ⊆ где =2rS  m j r j xX 1 2 )( = = (на базе множеств ),( r j xX к которым предварительно применена процедура 2). Утверждение 3. Для любой альтернативы ,Xxr ∈ ,1Sl rSX ⊆ где =1rS )(1 1 r j m j xX = = (на базе множеств ),( r j xX к которым предварительно применена процедура 1). Через maxX условимся обозначать множество таких альтернатив, что для каждой из них существует некоторый критерий , 0jF ,,10 mj ∈ по которому эта альтернатива наилучшая и не имеет эквивалентных, а max ~X — множество альтер- натив, наилучших по частным критериям; очевидно, что .~ maxmax XX ⊆ Исходя из (2), для любого лидирующего rx )( ∗∈ Xxr при формировании 2rS )( 1rS от- сеивается наибольшее количество альтернатив, не входящих во множество паре- то-оптимальных (слабоэффективных) решений. С учетом этого свойства лидиру- ющих решений алгоритм поиска парето-оптимальных решений для частных не- строгих ранжировок (1) можно представить следующим образом. Алгоритм поиска множества Парето. Шаг 1. Формируется ∗X по формуле (2) и .maxX Шаг 2. Выбирается одна (любая) альтернатива .∗∈ Xxr Шаг 3. Формируется множество ).(2 1 2 r j m j r xXS  = = Шаг 4. Формируется множество ).(\ max2 ∗= XXSX r   Шаг 5. Строится подмножество ,)( : 1 1         ∅=∈=′ = xXXxX jm j   где =)(1 xX j }.{\)(1 xxX j= Шаг 6. Формируется .maxPar XXXX  ∗′= Проблемы управления и информатики, 2006, № 1–2 31 Подобная процедура используется для выделения решений, оптимальных по Слейтеру. Отличие состоит в различном применении процедур 1 и 2 на шагах 3–5, а также множества .~ maxX Очевидно, что на шаге 5 достаточно получить первое пустое пересечение ,)()(1 ∅=xXxX k ll  },2,1{=l ,2 mk ≤≤ для того чтобы сделать вывод, что ParXx ∈ или SlXx ∈ соответственно. Кроме того, для снижения вычислительных затрат целесообразно на шаге 5 выбирать ),(xX j l },2,1{=l в порядке возраста- ния количества элементов в этих подмножествах. Оба алгоритма завершают работу за один проход и останавливаются за ко- нечное число шагов. Вычислительная сложность алгоритмов равна ++⋅ nmn ,τ′+τ++ m где ,)( 1 r j l m j xX∑ = =τ ∑ ∑ = = =τ′ c i j l k j xX 1 1 )( , ,Xx  ∈ ,Xc  = ,2 mk ≤≤ }.2,1{=l Исследования показали, что алгоритмы имеют высокую эффективность с точки зрения вычислительных затрат. Так алгоритм поиска парето-оптимальных решений оказывается в большинстве задач быстрее других способов выделения множества Парето. Результаты сравнения в двух тестовых задачах с известным и наиболее эффективным алгоритмом, в котором на каждой итерации проводится сравнение только с альтернативами, недоминирующими по Парето [3], представ- лены в табл. 1. Здесь и далее под количеством шагов понимается количество эле- ментарных операций типа сравнения, присвоения, сложения и вычитания. Таблица 1 № п/п Задача Количество шагов Известный алгоритм Предлагаемый алгоритм 1. Количество альтернатив — 3000 Количество критериев — 18 108144491 30956720 2. Количество альтернатив — 10000 Количество критериев — 4 9587667 6362537 К сожалению, после выделения множества Парето число парето-оптималь- ных альтернатив может оказаться достаточно большим, и выделение лучшей аль- тернативы на таком множестве «вручную» остается проблематичным. Вполне очевидна необходимость использования такого принципа оптимальности, кото- рый был бы сильнее, чем Парето, и позволил сократить множество альтернатив, передаваемых ЛПР для окончательного выбора (чем сильнее отношение, тем меньше количество альтернатив в полученном после оптимизации множестве). В идеале получившееся множество должно быть достаточно мало для того, чтобы ЛПР было в состоянии самостоятельно и без существенных ошибок выбрать луч- шее решение в соответствии со своими представлениями об оптимальности. 3. Методы поиска компромиссных парето-оптимальных решений при равноценности частных критериев. Основным в известных методах сужения является вопрос обоснованности соображений, исходя из которых строится более сильное, чем Парето, отношение предпочтения. Процедура сужения, как правило, основывается на введении дополнительной информации о важности критериев от ЛПР, что является достаточно сильным требованием как к априорной, так и к апос- териорной системам предпочтений ЛПР и сопряжено с известными трудностями. При априорно малой информации о важности частных критериев основным (первоначальным предположением), на наш взгляд, является случай равноценно- сти критериев. При этом, имея свободу выбора (ЛПР предлагается не одно реше- ние, а несколько парето-оптимальных), ЛПР вправе отойти от предположения о 32 ISSN 0572-2691 равноценности критериев в сторону уточнения относительной значимости крите- риев «вручную» на множестве альтернатив уже малой мощности. Для многих за- дач на практике этого достаточно. Очевидно, что объем необходимой дополни- тельной информации от ЛПР здесь может быть сведен к минимуму, что немало- важно для решения задач выбора с большим количеством альтернатив. В общем случае суженное множество альтернатив, полученное в рамках предположения о равноценности критериев, может выступать в качестве основы последующего выбора. Для построения отношения предпочтения, более сильного, чем Парето, при- мем известное представление об эквивалентности решений [4], согласно которому «сколько потеряли по одному критерию, столько же приобрели по другому». Ра- циональность подобного утверждения, как правило, не подвергается сомнению (в предположении равноценности критериев). Для любой альтернативы ,Xxi ∈ называемой далее базовой, можно получить, хотя бы искусственно, несколько (в зависимости от количества критериев) эквивалентных в указанном смысле ре- шений. Естественно, что такие решения могут оказаться «фиктивными», т.е. не существующими реально. Далее условимся называть их «двойниками» альтерна- тивы ix и обозначать ,kj ix .,1, mjk = При принятии указанного выше тезиса об эквивалентности, в случае описа- ния исходной информации в виде частных нестрогих ранжировок ,jS «двойни- ки» альтернативы могут быть получены более разнообразными способами, чем при простом обмене количественных оценок по критериям [4]. Замещение: осуществляет перенос альтернативы ix в ранжировке ,jS ∈j ,,1 m∈ назад на α шагов, а в ранжировке ,kS ,,1 mk ∈ ,jk ≠ вперед на β шагов. После ее выполнения альтернативе ix в ранжировках jS и kS присваиваются вместо порядкового номера ijπ новые номера α+π=π′ ijij и β−π=π′ ikik соот- ветственно, а для всех альтернатив rx в этих ранжировках с номерами ijrjij π>π≥π′ )( ikrkik π<ππ′ ≤ номер на единицу уменьшается (увеличивается). При этом, если ,2>m положение альтернативы ix в других ранжировках не из- меняется. Замещение с расширением :jI отличается от первой операции только тем, что после введения в соответствии с указанным выше правилом замещающей фиктивной альтернативы она объявляется эквивалентной предыдущей и соответ- ственно последующей альтернативам в ранжировках jS и .kS Добавление: в отличие от операций замещения добавляет полученную фик- тивную альтернативу kj ix в ранжировки ,vS ,,1 mv = а не замещает базовую, т.е. альтернатива ix остается на прежнем месте, а в ранжировках появляется новая фиктивная альтернатива .kj ix Возможны и комбинированные способы, например, в рамках одной операции применяется замещение ix в ранжировке jS с переносом назад на α шагов, а в ранжировке kS — замещение с расширением jI с переносом ix вперед на β ша- гов, и наоборот. Перенос альтернативы, осуществляемый в паре ранжировок на одинаковое количество шагов ),( β=α будем называть симметричным. Введенные операции позволяют построить следующие методы поиска ком- промиссных решений: ИТ (идеальная точка) и АС (автоматическое сужение). Проблемы управления и информатики, 2006, № 1–2 33 Алгоритм ИТ для поиска компромисса использует «близость» к так называе- мой идеальной точке (ИТ), где под ИТ понимается гипотетическая альтернатива, являющаяся наилучшей по всем частным критериям (считается, что в X не содер- жится альтернативы с такими свойствами). Подобная «близость» для порядковых шкал достаточно условная, поэтому ИТ — скорее некоторый ориентир, а не точка «отсчета расстояний». Алгоритм ИТ основан на построении некоторой «окрест- ности» ИТ с помощью одной из альтернатив, лучшей по частному критерию, и фиктивных альтернатив — «двойников», получаемых из базовой альтернативы путем изменения ее положения в ранжировках, с помощью специальных опера- ций переноса, позволяющих ухудшение качества по одному критерию компенси- ровать улучшением по другому (как правило, алгоритм работает в автоматиче- ском режиме, т.е. используется симметричный перенос альтернатив в ранжиров- ках, но возможна «настройка» операций переноса с помощью ЛПР). Алгоритм ИТ. Шаг 1. Полагается .compr ∅=X Шаг 2. Для альтернатив max ~Xxi ∈ формируется множество Λ пар ),( iij xe для всех ранжировок ,jS отличных от ранжировок ,qS где .1=iqe Шаг 3. В парах Λ∈),( iij xe отыскиваются минимальный (один из мини- мальных) по множеству значений i, j номер mine и соответствующая альтернати- ва rx : ,),( 0 Λ∈rrj xe .min 0 eerj = Шаг 4. Формируется ),( 0 1 r j xX где }.{\)()( 00 11 xxXxX jj = Шаг 5. ).( 0 1 r j xXX =′ Шаг 6. .11 =j Шаг 7. Если ,01 jj ≠ то с помощью операции симметричного переноса аль- тернатива rx замещается альтернативой , 01 jj rx после чего новые приведенные номера станут равными ,01 rjrj ee =′ ;10 rjrj ee =′ при этом если альтернатива, на место которой в ранжировке происходит перенос, имеет эквивалентные себе по данному критерию альтернативы и не является первой в группе, при переносе вперед и последней при переносе назад, то используется замещение с расширени- ем jI (группа эквивалентных альтернатив не разбивается), в противном случае — просто замещение, иначе )( 01 jj = — переход на шаг 12. Шаг 8. Формируется ).( 011 1 jj r j xX Шаг 9. Формируется ).( 011 1 jj r j xXXX ′=′ Шаг 10. Если ,∅=′X то на шаг 13 (пропуск шагов 11, 12). Шаг 11. Проверяется с помощью ЛПР (по его желанию) эквивалентность по- лученного решения («двойника») 01 jj rx базовой альтернативе rx и/или уточняет- ся положение в ранжировке 1jS альтернативы 01 jj rx (несимметричный перенос, ).β≠α Если изменения внесены, то возврат на шаг 8. Шаг 12. Если ,1 mj < то 111 += jj и переход на шаг 7. Шаг 13. ).,(\ 0 rrj xeΛ=Λ 34 ISSN 0572-2691 Шаг 14. Если ,∅=′X то возврат на шаг 3 (проверка результативности ите- рации). Шаг 15. Если ,max ),( 0 rj xe rj ee rrj Λ∈ = то }{comprcompr rxXX = (альтернатива max ~Xxr ∈ входит в ,comprX если использовался ее максимальный в ранжировках приведенный номер). Шаг 16. .comprcompr XXX ′=  Шаг 17. Если ,∅=Λ то переход на шаг 21. Шаг 18. Если ,),( Λ∈∃ iij xe ,0rjij ee = то возврат на шаг 3. Шаг 19. Если ,1compr >X в comprX выделить ,ParXxi ∉∗ =comprX }./{compr ∗= ixX Шаг 20. Анализ ЛПР полученного множества .comprX Если ЛПР считает не- обходимым расширить множество comprX (количество альтернатив в ,comprX с точки зрения ЛПР, малó и ограничивает его свободу выбора), то возврат на шаг 3. Шаг 21. Окончание работы. Таким образом, процедура повторяется с новыми альтернативами из множе- ства max ~X и соответствующими им приведенными номерами, по крайней мере, до тех пор, пока не появится хотя бы одна альтернатива в пересечении. Очевидно, что алгоритм всегда останавливается с выдачей определенного решения. К сожалению, при сужении исходного множества альтернатив X с помощью данного алгоритма парето-оптимальность можно гарантировать только в случае единственности полученного решения. Иначе проверка парето-оптимальности альтернатив comprXxi ∈ (шаг 19) необходима. Алгоритм АС реализует другой способ сужения множества альтернатив, в основе которого лежит предположение о том, что при равноценности критериев эквивалентная «фиктивная» альтернатива получается как результат такого сим- метричного переноса, когда полученный «двойник» kj ix уступит по j-му крите- рию такому количеству альтернатив, которое соответствует количеству альтерна- тив, превосходящих решение ix по k-му критерию, а по k-му критерию уступит такому же количеству альтернатив, которое которое превосходит решение ix по j-му критерию. Таким образом, обеспечивается сохранение суммарного по двум ранжировкам количества альтернатив, которым базовая и «фиктивная» альтерна- тивы проигрывают (выигрывают). Для реализации этого тезиса об эквивалентности в алгоритме сужения необ- ходимо расширить исходное множество альтернатив добавлением всех «фиктив- ных» решений ,kj ix .,1, mjk ∈ Операция добавления применима не только к ,ix но и к полученным .kj ix В результате этого, при желании, с помощью последовательности операций из любого «двойника» kj ix все же будет получена базовая альтернатива .ix Поэтому для формирования указанного выше отношения предпочтения достаточно анало- гично [4] упорядочить по убыванию для каждой Xxi ∈ ее приведенные номера ije и выделить недоминируемые по Парето. Далее невыбранные решения отбра- сываются и формируются новые ранжировки альтернатив, после чего процедура сужения повторяется. Проблемы управления и информатики, 2006, № 1–2 35 Алгоритм АС. Шаг 1. Полагается ,1=t ,SS t = ,DDt = .EEt = Шаг 2. Упорядочиваются приведенные номера в матрице )( ij t eE ,,1 ni = ,,1 mj = по строкам в порядке убывания (формируется матрица )).( t ij t eE Шаг 3. Из множества tX выделяется множество решений },{compr t ixX = для которых не существует tt r Xx ∈ такого, что ,,1 mj =∀ t ij t rj ee ≤ и mj ,10 ∈∃ .00 t ij t rj ee < Шаг 4. Анализ полученного множества comprX ЛПР. Если ЛПР принимает решение о прекращении сужения, то переход на шаг 9. Шаг 5. Проверить для 1>t условие: если получена единственная альтернатива или последовательность стабилизируется tX ),()1( )1( compr −=∨= tt XXX то переход на шаг 9. Шаг 6. .1+= tt Шаг 7. .comprXX t = Шаг 8. Формируются новые матрицы ,tS tD и ;tE переход на шаг 2. Шаг 9. Окончание работы. Алгоритм заканчивает работу за конечное число шагов. В отличие от алго- ритма ИТ, при сужении исходного множества альтернатив X, все полученные пос- ле первого прохода алгоритма АС решения парето-оптимальны. «Настройка» операции переноса для получения действительно эквивалентного с точки зрения ЛПР фиктивного «двойника» здесь практически сложно реализуема и сопряжена с существенными трудозатратами для ЛПР (количество генерируемых двойников может быть достаточно велико). Поэтому алгоритм АС представляет собой в це- лом автоматическую процедуру поиска наиболее предпочтительных по большин- ству частных критериев парето-оптимальных решений. Рассмотренные выше методы поиска парето-оптимальных компромиссных решений реализуют принципиально различные способы сужения множества аль- тернатив при равноценности частных критериев. Алгоритм ИТ формирует перво- начально крайне высокие требования к искомому решению, постепенно ослабляя их в процессе работы. Алгоритм АС, напротив, от итерации к итерации ужесточа- ет правила «выживания». Поэтому на практике наиболее эффективным оказыва- ется рассмотрение результатов, полученных при использовании как того, так и другого способа. Очевидно, что преимущества решений, победивших в обоих случаях, выглядят убедительнее, что позволяет говорить о независимости полу- ченного результата от метода сужения. Основными преимуществами алгоритмов ИТ и АС являются: отсутствие необходимости приведения частных критериев к единой шкале и введения коэф- фициентов важности частных критериев, достаточно высокая степень сужения множества Парето. В качестве недостатка отметим неприменимость в задачах вы- бора с двумя взаимопротиворечивыми критериями. Свойства и вычислительные возможности рассмотренных алгоритмов и ме- тодов изучались на различных тестовых задачах, как правило, больших размерно- стей, в которых нестрогие ранжировки формировались на основе количественных данных, сгенерированных случайным образом (с использованием нормального закона и закона равномерной плотности). Полученные с помощью методов ИТ и АС решения сравнивались с результатами численного расчета евклидова расстоя- ния r до ИТ с применением известного условия нормировки: 36 ISSN 0572-2691 , minmax min jj jij ij yy yy y − − =′ где ,ijy ,max jy jymin — соответственно оценка i-й альтернативы, максимальное и минимальное значения по j-му критерию. В табл. 2 представлены некоторые результаты машинных экспериментов. Сужение множества альтернатив проводилось автоматически в обоих случаях. Для сравнения указаны идентификационные номера первых двух или трех аль- тернатив, ближайших к ИТ в смысле r. Соответственно, если множество предъяв- ления, полученное при сужении, содержит альтернативы, близкие к ИТ (в смыс- ле r), то представлены их идентификационные номера или знак + присутствия всех из них в полученном множестве предъявления. Знак − обозначает, что в по- лученном множестве этих решений нет. Алгоритм ИТ исследовался также на те- стовом примере размерности n = 50000, m = 18. Альтернативы (8 альтернатив), «близкие» к ИТ, получены при обработке на Р2-400 за 33 с. Алгоритмы выделения множеств Парето и Слейтера, ИТ и АС при компью- терной реализации объединены в единый программный комплекс (ПК) многокри- териальной оптимизации МАТОП, который достаточно успешно применялся при решении задач проектирования сложных технических систем, управлении систе- мами природопользования. Таблица 2 Тестовые примеры Характеристика Алгоритм выделения Парето Алгоритм АС Алгоритм ИТ 1-й проход Окончание n = 3000 m = 18 равномерное распределение Количество альтернатив 2970 96 1 1 Количество шагов 31451558 8358541 8881512 3718280 Решения, близкие к ИТ: x1131, x2368, … + + x1131 x2368 n = 3000 m = 18 нормальное распределение Количество альтернатив 2983 219 4 2 Количество шагов 30956720 30303265 35078678 3603702 Решения, близкие к ИТ: x2420, x1841, x781,… + + + x2420, x781 n = 10000 m = 4 равномерное распределение Количество альтернатив 192 31 1 3 Количество шагов 25571387 5297580 5306474 53.915 Решения, близкие к ИТ: x984, x5036, x249,… + + − x5036, x984, x249 n = 10000 m = 4 нормальное распределение Количество альтернатив 131 16 1 1 Количество шагов 6362537 1692559 1698051 26455 Решения, близкие к ИТ: x2275, x6814,… + + − x2275 4. Метод принятия решений на основе человеко-машинной процедуры анализа парето-оптимальных решений. Рассмотренные выше алгоритмы опти- мизации альтернатив использовались при разработке метода принятия решений, предназначенного для решения рассматриваемого класса задач, в том числе и при разной важности частных критериев [5]. Основная идея предлагаемого метода принятия решений состоит в организа- ции управляемого с помощью предпочтений ЛПР «окна» (достаточно узкого под- множества альтернатив) на множестве Парето (иногда в качестве исходного мо- жет использоваться множество слейтеровских решений). При этом первоначально такое «окно» строится, как правило, автоматически (без участия ЛПР) в предпо- ложении о равноценности частных критериев. Далее для уточнения предпочтений ЛПР применяется специальная человеко-машинная процедура (ЧМП), позволяю- щая при последовательном анализе узких множеств парето-оптимальных альтер- натив учесть разную важность частных критериев для ЛПР и принять лучшее Проблемы управления и информатики, 2006, № 1–2 37 с его точки зрения решение. Основные этапы метода принятия решений, входя- щие в функциональный состав нового программного комплекса, представлены на рисунке. Выделение множества Парето (Слейтера) Сужение исходного множества альтернатив при первоначальном предположении о равноценности частных критериев (алгоритмы ИТ и АС) Предъявление ЛПР идеальной альтернативы и достаточно узкого набора парето- оптимальных альтернатив Выбор парето- оптимального (опорного) решения ЛПР Выделение подмножества парето- оптимальных альтернатив, «близких» к опорному решению Решение принято? Окончание Да Нет Выбор ЛПР частных критериев, которые он хотел бы улучшить Анализ возможности улучшения опорного решения одновременно по всем выбранным частным критериям Улучшение возможно? Разработка реализуемых вариантов улучшения опор- ного решения в соответст- вии с предпочтениями ЛПР Нет Да Выбор ЛПР варианта улучшения Формирование нестрогих ранжировок альтернатив ЧМП Основной задачей этапа сужения исходного множества альтернатив является получение достаточно узкого подмножества парето-оптимальных решений, кото- рые служат отправной точкой для ЧМП уточнения предпочтения ЛПР. На рисун- ке показаны все следующие шаги этой ЧМП. Кроме подмножества парето-оптимальных решений, ЛПР на каждой итера- ции предъявляется идеальная альтернатива, полученная с помощью количествен- ных и/или качественных оценок альтернатив, наилучших по частным критериям, что позволяет ЛПР получить представление о решениях, оптимальных по отдель- ным частным критериям. Ключевым для ЧМП является алгоритм выделения подмножества парето- оптимальных альтернатив, «близких» к опорному решению. Под «близкими» здесь понимаются альтернативы, улучшающие опорное решение в соответствии с предпочтениями ЛПР при наименьших потерях по другим частным критериям. Для поиска таких решений предлагается, используя исходные ранжировки S, сформировать ранжировки альтернатив, в которых опорное решение находится на первом месте, а другие альтернативы выстраиваются в порядке следования в ис- ходной ранжировке левее и правее от опорного. При этом сохраняется прежняя эквивалентность альтернатив и вводится эквивалентность альтернатив, находя- щихся по обе стороны от опорного решения и равноудаленных от него в смысле порядкового номера. Далее, при выявленных предпочтениях S ′ с помощью алго- ритмов сужения (ИТ и/или АС) выделяется достаточно узкое подмножество паре- то-оптимальных альтернатив, улучшающих опорное решение в соответствии с пожеланиями ЛПР. Полученные в результате альтернативы (как правило, не- большое количество) предъявляются совместно с идеальным и опорным решени- ями для анализа ЛПР. 38 ISSN 0572-2691 После выбора нового опорного решения начинается следующая итерация, за- тем процедура уточнения предпочтения ЛПР повторяется. Процесс принятия ре- шений заканчивается: 1) по желанию ЛПР; 2) при выборе решения, опорного на предыдущей итерации, и отказе ЛПР его улучшить по каким-либо частным кри- териям. Новый программный комплекс принятия решения включает возможности предшественника (ПК МАТОП) и в целом позволяет (как показывает опыт при- менения в задачах проектирования электрических машин, подбора кадров) для достаточно широкого класса задач индивидуального выбора, без внесения в явном виде дополнительной информации о важности частных критериев и с минималь- ными затратами для ЛПР, найти решение, наиболее предпочтительное с точки зрения ЛПР. С.М. Васильєв, Ю.В. Котлов МЕТОДИ І АЛГОРИТМИ БАГАТОКРИТЕРІАЛЬНОЇ ОПТИМІЗАЦІЇ НА БАЗІ НЕСТРОГИХ РАНЖИРОВОК АЛЬТЕРНАТИВ ЗА ЧАСТИННИМИ КРИТЕРІЯМИ І ДОСВІД КОМП’ЮТЕРНОЇ РЕАЛІЗАЦІЇ Розглядається клас задач багатокритеріального вибору, в яких кінцева множина альтернатив відома, кількість альтернатив може бути досить великою, вони можуть оцінюватися як кількісно, так і якісно. Інформація про надання переваг подається як узагальнені (із зазначенням рівноцінності) ранжировки альтерна- тив. Для даного класу задач пропонується комп’ютерна технологія пошуку компромісного розв’язку, що використовує якісні критерії і новий підхід до розв’язку проблем багатокритеріального вибору. S.N. Vassilyev, Yu.V. Kotlov THE METHODS AND ALGORITHMS OF MULTICRITERIA OPTIMIZATION ON THE BASIS OF UNSTRICT RANKINGS OF ALTERNATIVES ACCORDING TO PARTICULAR CRITERIONS AND EXPERIENCE OF COMPUTER REALIZATION A class of multicriteria choice problems is considered in which the finite set of alter- natives is known, а number of alternatives can be considerably large, alternatives can be evaluated both numerically and qualitatively. The information about preferences is represented as generalized (with the equivalence indicated) rankings of alternatives. For the considered class of problems, the computer search technology of compromise solution is suggested. One uses the qualitative criteria and new approach for the solu- tion of the problems of multicriteria choice. 1. Ларичев О. И. Теория и методы принятия решения. — М. : Логос, 2000. — 392 с. 2. Васильев С.Н., Котлов Ю.В. Свойства некоторых алгоритмов многокритериальной опти- мизации на основе обобщенных ранжировок // Оптимизация, интеллект, управление. — 2002. — № 6. — С. 161–167. 3. Теория выбора и принятия решений / Под ред. И.М. Макарова. — М. : Наука, 1982. — С. 170–171. 4. Подиновский В.В. Многокритериальные задачи с однородными равноценными критерия- ми // Журн. вычисл. математики и мат. физики. — 1975. — 15, № 2. — С. 130–141. 5. Котлов Ю.В., Васильев А.С. Метод принятия решений с малой априорной информацией // Вест. Томск. гос. ун-та. —2004. — № 9(II). — C. 22–27. Получено 30.11.2005

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

Institution

Similar Items