Содержание к диссертации
Введение
1. Анализ проблемы многокритериального выбора
1.1 Особенности задач многокритериального выбора 10
1.2 Анализ способов представления исходной информации для выбора 12
1.3 Анализ методов принятия решений 19
2. Модель выбора и алгоритмы оптимизации альтернатив на основе обобщённых ранжировок 35
2.1. Формализация описания выбора 35
2.2. Алгоритм ранжирования альтернатив на основе попарного сравнения 38
2.3. Алгоритмы поиска множества парето-оптимальных и слабоэффективных решений 46
2.4. Тестовый пример получения ранжировок альтернатив и поиска парето-оптимальных и слабоэффективных решений 54
3. Алгоритмы сужения множества парето-оптимальных решений 58
3.1. Алгоритм выделения из множества парето решений "близких" к идеальной точке (алгоритм ИТ) 58
3.2 Алгоритм сужения множества Парето на основе последовательного усиления отношения предпочтения (алгоритм АС) 76
4. Программный комплекс многокритериальной оптимизации "матоп" и его применение для решения задач выбора 81
4.1. Программный комплекс многокритериальной оптимизации "МАТОП" 81
4.2. Решение тестовых задач многокритериального выбора с помощью программного комплекса "МАТОП" и анализ результатов 88
4.3. Один из примеров решения практических задач (проектирования управляемого трансформатора) 93
Заключение 99
- Анализ способов представления исходной информации для выбора
- Алгоритмы поиска множества парето-оптимальных и слабоэффективных решений
- Алгоритм сужения множества Парето на основе последовательного усиления отношения предпочтения (алгоритм АС)
- Решение тестовых задач многокритериального выбора с помощью программного комплекса "МАТОП" и анализ результатов
Введение к работе
Актуальность темы. Многокритериальные задачи принятия решений обычно относят [1, 2] к классу слабоструктурированных, так как часть информации, необходимой для полного и однозначного решения задачи, здесь отсутствует в принципе. При этом многокритериальный характер задач осложняется тем, что количество альтернативных решений зачастую является большим, и поэтому решение задачи затруднительно без применения ЭВМ [2]. Кроме того, часто критерии оценки альтернатив являются не количественными, а качественными, причём последние обычно доминируют.
Сведение указанных задач к «жёстким» оптимизационным (только с количественными критериями и с заданными весовыми коэффициентами значимости), обеспечивая возможность использования хорошо развитогс математического аппарата скалярной оптимизации и некоторые другие достоинства, тем не менее, может привносить в постановку задачи заведомо ложную информацию с непредсказуемыми и, может быть, негативными последствиями. При этом используемые методы, как правило, подразумевают введение единой количественной меры и максимизацию соответствующего обобщённого (глобального, скалярного) критерия оптимальности, который часто отождествляется с целью, что может быть неверным, так как критерии характеризуют цель лишь косвенно, иногда лучше, иногда хуже, но всегда. приближённо. Не задав всех необходимых ограничений, можно одновременно с максимизацией указанного обобщённого критерия (как единой функции полезности) получить также непредвиденные и нежелательные сопутствующие эффекты. Кроме того, ряд авторов, например [3], отмечают, что, если даже удаётся получить единственное оптимальное решение, то оно может оказаться очень «хрупким», т.е. незначительные изменения в условиях задачи могут привести к выбору существенно отличающихся альтернатив.
Избежать возможных ошибок, связанных с особенностями рассматриваемых задач, позволяет методология системного анализа, отличительной чертой которой является учёт факторов неопределённости и качественных суждений при выборе цели, разработке и обсуждении альтернатив. Поэтому теория и практика принятия решений опираются на системный подход и, в частности, на его принцип «первого лица», в соответствии с которым предпочтения руководителя, или лица принимающего решение (ЛПР), стали провозглашаться основой окончательного выбора [2-11]. Как указывается в [4], тем самым был сделан принципиально важный шаг, который в разрез с известной методологией исследования операций, состоял в отказе от навязывания руководителю единственно возможного решения многокритериальной задачи выбора. Системный анализ является, по существу, объедине нием общей схемы системного подхода и методов оценки и сравнения многокритериальных альтернатив на основе субъективных суждений и включает следующие процедуры [2]: определить цели и ресурсы; определить альтернативные решения задачи; сравнить между собой альтернативы (с оценкой решений по разным критериям); выбрать предпочтительные альтернативы.
Анализ работ, в которых задача выбора ставится в каком-либо виде [3,6,8,12-15], показывает, что вышеприведенные процедуры системного анализа характерны для самых разных многокритериальных задач принятия решений и требуют своей технологической (математической и компьютерной) поддержки. В направлении их конкретизации можно выделить следующие этапы:
1. Построение множества возможных и допустимых альтернатив, т.е. генерация альтернатив и отсев заведомо неприемлемых альтернатив, в частности, не имеющих никакого физического смысла.
Формирование частных критериев, существенных для оценки альтернатив.
Формализация исходных предпочтений экспертов, или оценивание альтернатив (в количественной форме или в форме отношений предпочтения).
Оптимизация альтернатив.
Прогнозирование последствий выбранного решения и собственно принятие решения.
В диссертации будут рассматриваться только этапы 3, 4 с учётом при этом характерных особенностей и возможностей методов, используемых Б настоящее время для реализации других этапов. Большое количество публикаций, посвященных научно-технологической поддержке этапов 3, 4 [5-10, 16], свидетельствует о том, что эти этапы являются в проблематике многокритериального выбора наиважнейшими и базовыми, а также о высокой практической значимости и актуальности выбранной темы диссертации.
При этом в работе уделяется особое внимание тому общему классу задач принятия решений, которые могут характеризоваться количественными и качественными критериями, причём предполагается, что последние задаются в общей форме - в виде отношений предпочтения (например, не требуется описания качественных критериев градациями интенсивности соответствующей качественной характеристики).
Автор разделяет известную точку зрения, что избавление от качественных критериев и переход к задаче только с количественными критериями с целью использования хорошо развитых разнообразных методов принятия решений зачастую не обеспечены объективной информацией, позволяющей преобразовать общую модель принятия решений в терминах структур порядка в более частную модель в топологических терминах меры близости (метрики, окрестности).
Анализ проблем, возникающих при оценке и оптимизации альтернатив, показывает, что многие из них обусловлены ограниченными возможно- стями человека в обработке информации при принятии решения [2,5,17-19]. Следовательно, необходима такая структуризация процесса целенаправленного выбора компромиссного варианта, чтобы человек мог проникаться промежуточными результатами решения и проявлять своё «я» на основе должной (учитывающей возможности человека) организации человеко-машинной технологии принятия решений.
Цель работы - разработка алгоритмов и комплекса программ для оценки и многокритериальной оптимизации альтернатив на основе обобщённых ранжировок (случай количественных критериев легко сводится к этому).
Для достижения данной цели решаются следующие задачи:
Формализация исходных предпочтений экспертов.
Разработка алгоритмов и программ многокритериальной оптимизации альтернатив (на основе обобщённых ранжировок).
Применение разработанного программного комплекса "МАТОП" в многокритериальных задачах выбора.
Научная новизна работы состоит в том, что разработан оригинальный комплекс алгоритмов и программ многокритериального выбора, обеспечивающий на основе частных обобщённых ранжировок эффективное построение множеств парето-оптимальных и слабоэффективных решений, а также сужение множества парето-оптимальных решений до достаточно узкого на бора альтернатив, предназначенных для окончательного выбора Л ПР.
Личный вклад автора заключается в том, что все включённые в диссертацию алгоритмы и программы разработаны им лично, за исключением алгоритма ранжирования альтернатив, по которому авторство не разделимо с В. Ф. Черновым.
Практическая значимость работы состоит в том, что разработанные е диссертации алгоритмы и комплекс программ "МАТОП" могут быть использованы в разнообразных многокритериальных задачах, встречающихся на практике (проектирование технических систем, оптимизация автотранспортных маршрутов, системы поддержки принятия решений и др.)
Результаты работы использованы при решении следующих задач: проектирование управляемого трансформатора; обоснование структуры авиационного противолодочного комплекса; разработка методики функционального диагностирования системы электроснабжения Ан-124; анализ и составление учебных программ.
Реализация. В рамках данной работы были выполнены заказные (заказчик НТК ВВС) научно - исследовательские работы: «Аттракцион», «Ап-проксимация-96», «Технология-2000», «Классификация».
Доклады и публикации. Материалы работы докладывались на: семинарах адъюнктов и соискателей при Иркутском ВАИИ (1995-1999 г.г.); научно-технических конференциях «Проблемы повышения боевой готовности, боевого применения, технической эксплуатации и обеспечения безопасности полётов летательных аппаратов с учётом климатогеографических условий Сибири, Забайкалья и Дальнего Востока», ИВВАИУ, г. Иркутск, (1995-1999 г.г.); Всероссийской научно-практической конференции «Проблемы оптимизации в человеко-машинных системах», г. Иркутск, 1998 г научно-технической конференции ВАТУ «Проблемы разработки комплексов авиационного оборудования нового поколения», ВАТУ, г. Москва, 1998 г; семинарах «Методы оптимизации и их приложения» при ИДСТУ СО РАН, г. Иркутск (1998 г., 1999 г.), конференции «Ляпуновские чтения», ИДСТУ СО РАН, г. Иркутск, 2001 г.
Основные результаты диссертации опубликованы в 7 печатных работах.
Структура и объем диссертации. Диссертация состоит из 4 разделов, общим объёмом 124 страницы, из них приложение - 20 страниц. В работе содержится 8 таблиц, 25 рисунков, 1 приложение. Список литературы содержит 50 наименований.
Анализ способов представления исходной информации для выбора
Задача многокритериального выбора возникает в ситуациях, когда существуют множество вариантов решения, возможность их сравнения по набору критериев, а также само лицо, принимающее решение.
Так как в слабоструктурированной задаче многокритериального выбора, как правило, могут использоваться разные шкалы, как количественные, так и качественные, сравнение решений по предпочтительности может осуществляться по-разному. Например, при количественном описании альтернатив сравнение обычно выполняется не непосредственно, а при помощи заданных на множестве альтернатив X = {х1,х2,...,хп] вещественно-значных функций fl,f2,...,fm, называемых частными (локальными) критериями к служащих для выражения «интенсивности» существенных свойств (признаков) решений, т - общее количество частных критериев. При этом считается, что предпочтительность каждого решения х полностью характеризуется. В другом случае, сравнение может производиться путём ранжирования альтернатив по предпочтительности, попарным сравнением и т.д. При этом используются отношения порядка: нестрогого предпочтения RJ, строгого предпочтения PJ или эквивалентности Iі. Ясно, что количественное представление критериев (/) однозначно определяет частные отношения предпочтения RJ, j = \,т. Класс слабоструктурированных задач выбора довольно широк. Выделим из них тот подкласс, которому посвящена данная диссертация. Мы не будем рассматривать специально задачи выбора с ограничениями, полагая, что исходное множество альтернатив удовлетворяет этим ограничениям. Мы полагаем также, что выбор является индивидуальным, уникальным (однократным) и реализуется в условиях определённости, т.е. последствия выбора точно известны. Будем считать множество альтернатив конечным, а альтернативы, присутствующие в задаче выбора, заранее заданными и независимыми. Под независимыми понимаются альтернативы, любые действия с которыми (удаление из рассмотрения, выделение в качестве лучшей и т.п.) не оказывают влияния на качество других альтернатив [5]. Кроме того, рассматриваются критерии, независимые по предпочтению от остальных. Более точно [20], критерий FJ независим по предпочтению от остальных т-1 критериев, если бинарное отношение предпочтения на векторных оценках альтернатив с позиций j -го частного критерия FJ. Наконец, будем считать, что в рассматриваемых нами задачах выбора допустимо наличие большого количества, как альтернатив, так и критериев. Принято различать три основные задачи принятия решения: - упорядочивание альтернатив; - распределение альтернатив по ранжированным по предпочтительности классам решений; - выделение лучшей альтернативы. Далее (в этой главе и в целом в диссертации) в качестве конечной цели рассматривается только выделение достаточно узкого набора наиболее предпочтительных альтернатив для их предъявления ЛПР на предмет окончательного выбора. Оценивание альтернатив по качественному критерию означает их сравнение по предпочтительности с точки зрения частного критерия, что формализуется бинарными отношениями RJ, PJ, Iі. Поэтому о качественных критериях говорят как о критериях с порядковыми шкалами. При этом бессмысленно выяснять, во сколько раз или насколько одна альтернатива предпочтительней другой. Критерий с порядковой шкалой естественным образом возникает, например, в тех случаях, когда решения ранжируются. т.е. располагаются по возрастанию или убыванию интенсивности некоторого свойства. Обычно такие ранжирования получаются при субъективных «измерениях», например, отражают мнение индивида / о предпочтительно сти решений. Непосредственная количественная оценка альтернатив является для эксперта крайне сложной задачей, особенно при большом количестве рассматриваемых альтернатив, что не позволяет рассматривать результаты ее как надёжные и достоверные. Поэтому, как правило, производится качественное оценивание альтернатив, и применяются различные способы перехода от качественных оценок к количественным. Например, весьма часто субъективные измерения выполняются в балльных шкалах, занимающих «промежуточное» положение между количественными и качественными критериями. Тем не менее, задача оценивания для эксперта также может оказаться достаточно сложной, как при недостаточном количестве баллов (например, четырёхбалльная система в большинстве учебных заведений). так и при увеличении их количества. Кроме того, используемое количестве баллов жёстко ограничивает количество альтернатив, которые имеет смысл рассматривать (например, при трёх критериях с пятибалльной шкалой, не целесообразно рассматривать более 125 альтернатив). Следовательно, для задач выбора с большим количеством альтернатив необходимо увеличивать количество баллов соответственно рассматриваемому множеству альтернатив, что может фактически привести к количественной оценке.
Достаточно часто переход от порядковых шкал к количественным осуществляется путём приписывания числа некоторому свойству альтернативы таким образом, чтобы большей интенсивности этого свойства соответствовало большее (или, наоборот, меньшее) число. Тем не менее, на наш взгляд, проблема адекватности количественного представления остаётся. Например, можно утверждать, что в случаях, когда эксперт затрудняется оценить расстояние между альтернативами по тому или иному критерию. формальный переход к количественной шкале является неоднозначным, хотя в последующем к полученным числам необоснованно относятся уже как к точным измерениям, т.е. складывают, умножают и т.д. Как справедливе указывается в [21], для анализа и решения практической многокритериальной задачи оптимизации следует применять только те определения и понятия, методы и процедуры, которые приводят к получению адекватных выводов и рекомендаций. Поэтому методы, сильно полагающиеся на количественные оценки ЛПР, крайне чувствительны даже к небольшим человеческим ошибкам. Как отмечается в [6], лучше иметь приближённое решение. но надёжное и проверенное (разбиение альтернатив на классы, частичное ранжирование), чем по форме точное, но по сути - весьма ненадёжное.
Алгоритмы поиска множества парето-оптимальных и слабоэффективных решений
Среди многообразия известных задач выбора в диссертации выделен к рассмотрению класс задач, к характерным особенностям которых (см. п. 1.1) относится большое количество альтернатив и критериев оценивания. Таковыми, например, являются задачи проектирования.
Как уже указывалось, даже после выделения множества решений, оптимальных по Парето или Слейтеру, ЛПР нелегко проанализировать то большое число альтернатив и выбрать наилучшее, с его точки зрения, решение (далее для определённости мы будем рассматривать только Парето-оптимальность). Вполне очевидно, что необходимо сформировать такой принцип оптимальности, который был бы сильнее, чем Парето, к позволил сократить множество альтернатив, передаваемых ЛПР для окончательного выбора (чем сильнее отношение, тем меньше количество альтернатив в полученном после оптимизации множестве). В идеале, получившееся множество должно быть достаточно мало для того, чтобы ЛПР было в состоянии самостоятельно и без существенных ошибок выбрать лучшее решение в соответствии со своими представлениями об оптимальности. Таким образом, будем считать задачу многокритериального выбора решённой, если ЛПР поставлено именно в такие условия выбора. Особо подчеркнём, что свобода и право выбора, на наш взгляд, должны оставаться у ЛПР всегда, и поэтому нежелательно, чтобы ЛПР предлагалось «утвердить» единственное решение.
Основным в известных методах сужения является вопрос обоснованности соображений, исходя из которых, строится более сильное, чем Парето, отношение предпочтения. В известных автору и не требующих количественного оценивания методах сужения множества альтернатив (см. п. 1.2) процедура сужения, как правило, основывается на введении дополнительной информации о важности критериев от ЛПР, что является достаточно сильным требованием как к априорной, так и апостериорной системам предпочтений ЛПР и сопряжено с трудностями, которые рассмотрены в п. 1.2.
Далее мы рассматриваем случай равноценности критериев. Поясним, с чем это связано. Очевидно, что объём необходимой дополнительной информации от ЛПР в этом случае может быть сведён к минимуму, что немаловажно для решения задач выбора с большим количеством альтернатив. Интуитивно ясно, что, когда критерии равноценны, речь может идти только о некотором компромиссе между ними, так как наилучшего по всем критериям решения, как правило, не существует. Такая постановка задачи правомерна во многих случаях, в том числе и при решении задач проектирования. Кроме того, следует отметить, что, имея свободу выбора (ЛПР предлагается не одно решение, а несколько парето-оптимальных, т.е. несравнимых), ЛПР вправе отойти от предположения о равноценности критериев в сторону уточнения относительной значимости критериев «вручную» на множестве альтернатив уже малой мощности. Таким образом, суженное множество альтернатив, полученное в рамках предположения о равноценности критериев может выступать в качестве основы последующего выбора. В дальнейшем, если не уточняется специально, будем считать, что сужение множества альтернатив осуществляется в предположении равноценности критериев.
Достижение компромисса при равноценных критериях может и, пови-димому, должно реализовываться так или иначе с использованием идеальной точки (ИТ), называемой также «фантомной» [16]. Последнее отражает тот факт, что решение, наилучшее по всем критериям, как правило, не существует. Тем не менее, используемый в методе идеальной точки принцип компромисса требует, чтобы выбор осуществлялся среди решений, ближайших к ИТ в смысле некоторой меры расстояния. Наиболее часто применяют евклидово расстояние или равномерную метрику. Вполне очевидно, что для качественных оценок такая «близость» может быть только условной. Поэтому мы будем использовать понятие ИТ только как своего рода ориентир.
Хотя частные обобщённые ранжировки альтернатив носят качественный характер, тем не менее, можно без требования дополнительной информации от ЛПР (в случае равноценности критериев) предложить всё-таки Вполне очевидно, что вариант или несколько вариантов хєіі могут считаться наиболее "близкими" к идеальной точке (ИТ). К сожалению, часто множество U оказывается пустым.
Следует отметить, что в ряде методов принятия решения для введения в рассмотрение отношения предпочтения более сильного, чем Парето, принимается такое представление об эквивалентности решений, согласно кото рому «сколько потеряли по одному критерию, столько же приобрели по другому» (например, метод Подиновского, см. п. 1.2). Рациональность подобного утверждения, как правило, не подвергается сомнению (в предположении равноценности критериев). Для любой альтернативы xt є X, называемой далее базовой, можно получить, хотя бы искусственно, несколько (в зависимости от количества критериев) эквивалентных в указанном смысле решений. Естественно, что такие решения могут оказаться «фиктивными», т.е. несуществующими реально. Далее условимся называть их «двойниками» альтернативы xt и обозначать xfJ k,j = \0m.
При принятии вышеуказанного тезиса об эквивалентности, в случае описания исходной информации в виде частных обобщённых ранжировок «двойники» альтернативы могут быть получены более разнообразными способами, чем при простом обмене количественных оценок по критериям (см. п. 1.2). Можно предложить следующие способы:
Замещение: осуществляет перенос альтернативы х{ в ранжировке SJ,je\,m, назад на а шагов, а в ранжировке Sk, к є 1,т, кФ j, вперёд на Р шагов. После её выполнения альтернативе xt в ранжировках Sj и Sk присваивается вместо порядкового номера % tj новые номера % =% + а и Р соответственно, а для всех альтернатив хг в этих ранжировках с номерами щ. -Ку (т4 7ік %) номеР на единицу уменьшается (увеличивается). При этом если т 2, положение альтернативы х{ в других ранжировках не изменяется.
Алгоритм сужения множества Парето на основе последовательного усиления отношения предпочтения (алгоритм АС)
Исходя из машинных экспериментов, можно сделать вывод, что алго ритм поиска множества Парето г кировках, позволяя использовать как количественную, так и качественную г ліацию, существенно выигрыва ет при увеличении количества парето-ош иьтернатив. Сравнение алгоритмов сужения МНОУІ ; ре провести сложнее, так как традиционно сужение множества Парето юве качественных оценок для больших размерностей обычно не m годится. Кроме того, результаты (выделенное множество решений), получаемые с помощью методов сужения, как правило, различаются, что затрудняет их сравнение. В из вестных автору методах сужения множества альтернатив (см. п. 1.2), не требующих количественного оценивания, процедура сужения, как правило, основана на введении дополнительной информации о важности критериев от ЛПР. Вследствие этого, для применения, например, метода "ЗАПРОС" ЛПР необходимо ответить в худшем случае на 0,25 т(т - \)п(п - \) вопросов (для примеров 1,2 и 3,4 - 688.270.500 и 299.970.000 вопросов соответственно), что вряд ли реализуемо.
Предварительный отбор относительно лидирующего решения, используемый в алгоритмах построения множества Парето и АС (таблица 4.3) значительно позволяет сократить вычислительную трудоёмкость в примерах Зи4.
Алгоритм ИТ тестировался также на примере размерности п = 50000, т = 18, с равномерным распределением. "Компромиссное" решение при обработке на Р2-400 (128 Мб ОЗУ) было получено через 33с.
Главным недостатком современных выпрямительных устройств (ВУ) является отсутствие стабилизации выходного напряжения и, как следствие, их избыточные мощность и масса. Отсутствие стабилизации приводит к увеличению массы компонентов системы распределения и передачи электроэнергии постоянного тока, поскольку расчет сечения проводов производится на максимальный уровень нестабилизированного напряжения.
Использование трансформатора с вращающимся магнитным полем (ТВМП) и имеющего подмагничиваемый шунт в составе ВУ позволяет стабилизировать выходное напряжение ВУ, уменьшить значение коэффициента искажения, а также уменьшить массу компонент системы передачи и распределения электроэнергии.
Проектирование электрической машины - сложная многовариантная задача, при решении которой необходимо учитывать большое количество факторов. В управляемом трансформаторе должны наилучшим образом сочетаться массы меди и стали при заданных ограничениях на его внешние размеры и должны быть выбраны такие значения электромагнитных нагрузок, которые обеспечат компромисс в достижении минимальной массы и требуемых значений КПД и cosg) .
Для генерирования вариантов построения управляемого трансформатора использовалась предложенная в [47] программа расчёта управляемого трансформатора на ПЭВМ. В основе данной программы лежит, так называемый, метод синтеза в направлении от электромагнитных нагрузок к геометрическим размерам [48,49,50]. Этот метод использует в качестве входных величин электромагнитные нагрузки, с помощью которых можно рассчитать требуемые размеры и значения лимитеров для изготовления машины. Входные (расчётные) величины в хорошо спроектированных машинах лежат в достаточно узких пределах; в какой-то мере эти величины позволяют судить о нормальном состоянии электрической машины. Рассчитанные габаритные размеры машины, с использованием электромагнитных нагрузок, несут информацию о массовых характеристиках машины, её стоимости. Главным достоинством метода является то, что использование рациональных электромагнитных нагрузок в качестве входных величин исключает нереалистичный вариант [47].
Таким образом, входными параметрами для программного модуля являются: индукция в первичной обмотке Bql, индукция во вторичной обмотке В2, индукция в зубце Bz, плотность тока в обмотках J, отношение осевой длины первичного ярма к его радиальному размеру Ь. Выходные параметры - геометрические размеры и значения лимитеров.
Из различных критериев оценки эффективности управляемого трансформатора в ходе анализа были выделены четыре важнейших: коэффициент полезного действия КПД, масса трансформатора М s cos q , суммарные потери в стали и меди P=Pst+Pm. На этапе генерирования диссертантом получено 8313 альтернатив, оцененных по четырём вышеуказанным критериям. Потребитель заинтересован в минимизации массы и суммарных потерь и максимизации КПД и cos, (р. С помощью программного комплекса
"МАТОП" из 8313 альтернатив выделено полное множество парето-оптимальных решений в количестве 315 альтернатив, которое в дальнейшем было сужено. Полученные множества предъявлялись для анализа ЛПР, в роли которого выступал специалист по проектированию электрических машин. Так как предъявляемые решения носят компромиссный характер и являются достаточно близкими друг другу, ЛПР решил, что наиболее предпочтительными в этом случае являются варианты с меньшей массой трансформатора. Таким образом, процесс выбора окончательного варианта про ектирования управляемого трансформатора с использованием программного комплекса "МАТОП" выглядит следующим образом.
Альтернатива с идентификационным номером 2108 также содержится в полученном на этом режиме множестве предъявления и уступает по массе альтернативе с идентификационным номером 3480, но ЛПР с учётом других критериев посчитал её более предпочтительной.
Решение тестовых задач многокритериального выбора с помощью программного комплекса "МАТОП" и анализ результатов
С помощью ПК "МАТОП" были проведены исследования алгоритмов оптимизации альтернатив на тестовых примерах большой размерности. При этом случайным образом по каждому критерию формировалась таблица числовых оценок с равномерным и нормальным законами распределения. Для генерирования случайных величин использовались алгоритмы, рассмотренные в [46]. Кроме того, в случае равномерного распределения после получения числовых оценок с помощью генератора случайных чисел и задания диапазонов изменения получаемых значений вводились группы эквивалентных по частным критериям альтернатив. Допускалось максимальное количество групп эквивалентных альтернатив равное 0,007% от общего количества альтернатив с максимальным количеством альтернатив в группе не более 0,005% от общего количества альтернатив.
Рассматривались следующие 4 тестовых примера {п - количество альтернатив, т - количество критериев): Пример 1: п = 3000, т = 18, равномерное распределение (приложение П.1,П.2,П.З,П.4); Пример 2: п = 3000, т = 18, нормальное распределение (приложение П.5,П.6,П.7,П.8,П.9); Пример 3: п = 10000, т = 4 , равномерное распределение (приложение П.10,П.11,П.12,П.13,П.14); Пример 4: п = 10000, т = 4, нормальное распределение (приложение П.15,П.16,П.17,П.18). Во всех тестовых примерах задавались значительно различающиеся диапазоны изменения и плотности расположения числовых оценок на критериальных шкалах (данные указаны в приложении).
Так как частные обобщённые ранжировки формировалась на основе количественных данных, представилась возможность сравнить результаты, полученные с помощью алгоритмов оптимизации на основе частных отношений предпочтения, с результатами численного расчёта евклидова расстояния гх или г2 до ИТ, с применением известных условий нормировки соответственно: где у у - оценка альтернативы xt по j -му критерию, у,-тах, .У/тщ - соответственно максимальное и минимальное значение по j -му критерию, у у -нормированная оценка альтернативы х( по j -му критерию.
Информацию для сравнительного анализа результатов работы трёх алгоритмов ПК "МАТОП" (алгоритм поиска парето-оптимальных решений, алгоритм АС, алгоритм ИТ) содержит таблица В строках «Альтернативы» указаны идентификационные номера первых двух или трёх альтернатив, ближайших к ИТ в смысле г2. Соответственно, если в множестве альтернатив, полученном с помощью этих трёх алгоритмов, содержатся какие-то из указанных альтернатив, то в таблице указываются их идентификационные номера или знак "+" в случае присутствия всех в полученном множестве. В противном случае, знак «-» обозначает, что в полученном множестве ни одного из этих решений нет. Кроме того, в таблице 4.1 для алгоритма АС, который последовательно сужает множество альтернатив, представлены результаты первого прохода. Для тестового примера 3 производился поиск слабоэффективных решений (приложение П. 12). В указанные в таблице 4.1 для алгоритма поиска парето-оптимальных решений число шагов входят также операции по подготовке информации для сужения (формирование новых ранжировок для множества Парето и т.д.)
Как и следовало ожидать, при увеличении количества критериев в тестовых примерах существенно увеличивается количество парето-оптимальных альтернатив (примеры 1 и 2 в сравнении с примерами 3 и 4). Вычислительная сложность поиска множества Парето при полном переборе составляет п -т. В алгоритмах с неполным перебором, которые используют, как правило, количественные оценки, в худшем случае порядок остаётся тот же, но вычислительные затраты зависят от количества парето-оптимальных альтернатив и тем ниже, чем уже множество Парето. Проводилось сравнение с наиболее эффективным алгоритмом, в котором на каждой итерации производится сравнение только с недоминируемыми по Парето альтернативами [22]. Результаты представлены в таблице 4.2.
Исходя из машинных экспериментов, можно сделать вывод, что алго ритм поиска множества Парето кировках, позволяя использовать как количественную, так и качественную г ліацию, существенно выигрыва ет при увеличении количества парето-ош иьтернатив. Сравнение алгоритмов сужения МНОУІ ; ре провести сложнее, так как традиционно сужение множества Парето юве качественных оценок для больших размерностей обычно не m годится. Кроме того, результаты (выделенное множество решений), получаемые с помощью методов сужения, как правило, различаются, что затрудняет их сравнение. В из- вестных автору методах сужения множества альтернатив (см. п. 1.2), не требующих количественного оценивания, процедура сужения, как правило, основана на введении дополнительной информации о важности критериев от ЛПР. Вследствие этого, для применения, например, метода "ЗАПРОС" ЛПР необходимо ответить в худшем случае на 0,25 т(т - \)п(п - \) вопросов (для примеров 1,2 и 3,4 - 688.270.500 и 299.970.000 вопросов соответственно), что вряд ли реализуемо. Предварительный отбор относительно лидирующего решения, используемый в алгоритмах построения множества Парето и АС (таблица 4.3) значительно позволяет сократить вычислительную трудоёмкость в примерах Зи4. Алгоритм ИТ тестировался также на примере размерности п = 50000, т = 18, с равномерным распределением. "Компромиссное" решение при обработке на Р2-400 (128 Мб ОЗУ) было получено через 33с.
