Содержание к диссертации
Введение
1. Анализ методов шогокригериальной оптимизации 7
1.1. Введение 7
1.2. Классификация методов многокритериальной оптимизации 7
1.3. Методы, предполагающие существование функции полезности. II
1.4. Методы, не предполагающие существования функции полезности 16
1.5. Априорные методы оптимизации 18
1.6. Диалоговые методы оптимизации 19
1.7. Порядковые задачи выбора 20
1.8. Использование дополнительной информации при решении многокритериальных задач 21
1.9. Выводы и цель диссертации . 22
2. Порядковые отношения 24
2.1. Введение 24
2.2. Функция выбора и бинарное отношение 25
2.3. Выбор в строгих и нестрогих шкалах 28
2.4. Свойства наследования и монотонности. Обоснование применения графодоминантных функций выбора в задачах оптимизации 29
2.5. Бинарные отношения в fR Порядковые сравнения . 31
2.6. Представление порядковых сравнений верхними конусами 33
2.7. Критерии транзитивности и ацикличности 38
2.8. Представление порядковых сравнений полиномами . 43
- з
2.9. Реализация бинарных отношений порядковыми сравнениями . 45
2.10.Порядковые сравнения Q^ ; . 48
2,11 .Выводы 51
3. Аппроксимация предпочтения ЛПР 53
3.1. Введение 53
3.2. Определения сравнительной важности критериев 54
3.3. Сравнительная важность критериев для порядковых сравнений . 58
3.4. Сравнение некоторых способов упорядочения критериев 62
3.5. Использование информации о важности критериев при идентификации структуры предпочтений ЛПР 65
3.6. Использование информации о важности критериев при аппроксимации структуры предпочтений ЛПР 70
3.7. Выводы 72
4. Математическое ожидание мощности выбора как характеристика точности аппроксимации 74
4.1. Сравнение точности аппроксимации 74
4.2. Математическое ожидание мощности выбора для порядковых сравнений. Строгие шкалы 76
4.3. Ациклические порядковые сравнения в строгих шкалах. Сравнения &** и J?n 82
4.4. 1 -оптимальность 85
4.5. Сравнение Sn 89
4.6. Нестрогие шкалы 93
4.7. Выводы 96
5. Методика решения порядковых многокритериальных задач 97
5.1. Алгоритмы выявления структуры предпочтений ЛИР. 97
5.1.1. Идентификация на основе попарного сравнения вариантов 98
5.1.2. Аппроксимация на основе информации об упорядочении критериев по важности ют
5.2. Методика. Ю4
5.3. Выбор проекта технологической линии для производства белково-витаминных концентратов юб
5.4. Формирование оптимального плана технической подготовки инструментального производства модели автомобиля BA3-2I07 НО
5.5. Выводы ИЗ
- Использование дополнительной информации при решении многокритериальных задач
- Бинарные отношения в fR Порядковые сравнения
- Использование информации о важности критериев при идентификации структуры предпочтений ЛПР
- Математическое ожидание мощности выбора для порядковых сравнений. Строгие шкалы
Введение к работе
Внедрение систем автоматизированного проектирования позволяет в настоящее время значительно сократить затраты времени разработчиков и одновременно повышает качество проектных решений. Этапу детального проектирования нового объекта предшествует этап выработки технического задания, или этап предварительного проектирования. На этом этапе задача проектировщика заключается в том, чтобы сформировать общий облик изделия, выяснить его основные параметры и критерии его оценки.
На стадии предпроектной проработки лицу, принимающему решения (ЛИР), приходится иметь дело с большим числом вариантов проекта. Как правило, это число бывает настолько велико, что превосходит возможности ЖР по сопоставлению альтернативных вариантов. Необходимость учета не одного, а одновременно нескольких критериев оценки качества проекта еще больше усложняет задачу проектировщика. В этих условиях ЛПР часто не в состоянии формализовать свое представление об оптимальности проекта, это может привести к тому, что для детального проектирования выбирается нелучший вариант.
Задачи выбора, в которых приходится учитывать одновременно несколько, как правило, противоречивых критериев оптимальности, в большинстве случаев не могут быть решены классическими методами оптимизации. Для решения таких задач используются методы многокритериальной оптимизации, интенсивно развивающиеся в последние годы.
Существующие методы многокритериальной оптимизации основаны на предположениях о существовании ряда жестких ограничений на структуру предпочтений ЛПР, вплоть до предположения о существовании функции полезности или конкретного вида модели оптимизации. Однако осуществить проверку этих предположений обычно не представляется возможным. Использование диалоговых процедур оптимизации позволяет разрабатывать методы, свободные от жестких априорных ограничений на структуру предпочтений ЛПР.
Целью диссертационной работы является разработка диалогового метода многокритериальной оптимизации, позволяющего повысить качество и сократить сроки принятия предпроектных решений.
Работа состоит из пяти глав и заключения.
В первой главе приводится классификация существующих методов многокритериальной оптимизации и производится их анализ. Делается вывод о том, что для решения широкого класса задач предварительного проектирования методы оптимизации развиты неудовлетворительно.
Во второй главе с целью разработки методов решения порядковых задач выбора (т.е. таких задач, в которых информация о сравниваемых вариантах выражается их рангами по отдельным критериям) исследуются модели выбора по бинарным отношениям. Вводится в рассмотрение класс порядковых бинарных отношений, исследуются его свойства.
Третья глава посвящена формализации и использованию качественной информации о сравнительной важности критериев при решении задач многокритериальной оптимизации.
В четвертой главе производится оценка точности аппроксимации структуры предпочтения ЛПР для любых порядковых моделей выбора.
В пятой главе излагается методика решения многокритериальных задач. Приводятся различные алгоритмы выявления структуры предпочтения ЛПР. Методика используется для решения практических задач предварительного проектирования.
В заключении излагаются основные результаты дис -сертационной работы. Список литературы состоит из 71 наименования.
Использование дополнительной информации при решении многокритериальных задач
Развитие вычислительной техники в последние годы предопределило появление работ по диалоговым методам оптимизации, в которых предполагается получение от ЛПР дополнительной информации о задаче в процессе ее решения. В качестве такой информации часто используется сравнительная важность критериев. Эта информация, с одной стороны, достаточно содержательна для понимания ЛПР, а с другой стороны, может быть эффективно использована в методах оптимизации.
Первым из известных нам формально введенным понятием сравнительной важности является лексикографический порядок 30,38 , который основан на качественной информации о критериях, получаемых от ЛПР. Однако серьезным недостатком лексикографических моделей являются чрезвычайно жесткие предположения. Практически не существует задач, в которых важность одного критерия превышала бы важность всех других. В большинстве работ по методам мно 22 гокритериальной оптимизации ЦЗ, 47, 54, 55, 59, 63, 64] важность критерия представляет собой его числовую характеристику - весовой коэффициент. В некоторых случаях эти коэффициенты удается рассчитать после анализа задачи, но чаще всего они устанавливаются исходя из интуитивных соображений весьма произвольно. Анализ методов оптимизации позволяет сделать вывод, что ЛПР, как правило, в состоянии сообщить лишь качественную информацию о важности критериев. Так, в ЦЗ] ЛПР сообщает, что "критерий К\ важнее (гораздо важнее) критерия Кг.", в.[411 ЛПР может заключить, что "критерии Кл и Кг. , рассматриваемые совместно, имеют большую важность, чем критерий Ks ". Подобная качественная информация в этих и других методах многокритериальной оптимизации в значительной степени произвольно преобразуется в количественную, иными словами, определяются весовые коэффициенты. Необоснованность такого преобразования приводит к неверному решению задачи.
Проведенный в главе анализ задач предварительного проектирования и существующих методов многокритериальной оптимизации позволил сделать следующие выводы.
I. Методы многокритериальной оптимизации, в которых не используются жесткие предположения о структуре предпочтений ЛПР, разработаны неудовлетворительно. Развитие средств вычислительной техники открывает возможность для разработки высокоэффективных человеко-машинных методов оптимизации со слабыми предположениями о структуре предпочтений ЛПР.
2. На стадии предварительного проектирования у разработчиков отсутствует детальная информация об альтернативных вариантах проекта. Задачу выбора приходится решать на основании информации о рангах вариантов проекта по отдельным критериям (задачи с информацией такого вида называются порядковыми).
3. Порядковые задачи составляют обширный практически значимый класс задач многокритериальной оптимизации. Для их решения представляется целесообразным использовать диалоговые методы.
4. В качестве дополнительной информации в диалоговых методах оптимизации удобно учитывать представления ЛПР о сравнительной важности критериев. Однако, понятие "важность критериев" в различных методах оптимизации допускает произвольные толкования. Поэтому необходима формализация этого понятия.
Целью диссертационной работы является разработка диалогового метода многокритериальной оптимизации для решения порядковых задач выбора, позволяющих повысить качество и сократить сроки принятия предпроектных решений.
В первой главе был введен в рассмотрение класс задач многокритериальной оптимизации, в которых информация о сравниваемых вариантах задана в виде их рангов по отдельным критериям (такие задачи называются порядковыми). Для решения порядковых задач создан ряд моделей оптимизации. Однако эти модели обладают существенными недостатками. Выбор по Парето, например, часто не позволяет сузить исходное множество вариантов до желаемых размеров, лексикографический выбор основывается на жестких предположениях о структуре предпочтений ЛПР, и т.п.
В настоящей главе для решения порядковых задач многокритериальной оптимизации вводится новый класс отношений - порядковые бинарные отношения - включающий в себя многие известные отношения предпочтения. Исследуются свойства порядковых отношений, приводятся критерии транзитивности и ацикличности. Исследование проводится с позиций общей теории выбора, центральным понятием которой является функция выбора - формализация содержательного понятия "структура предпочтений ЛПР".
Бинарные отношения в fR Порядковые сравнения
Существует ряд методов оптимизации, в которых оптимальность по Парето является одним из принципов рационального выбора .44] и постулируется необходимым условием оптимальности найденного решения. Необоснованность такого подхода в ряде случаев наглядно продемонстрирована в [I-] , где приведены примеры функций выбора, вполне разумных, но не обязательно базирующихся на попарном сравнении вариантов. Тем не менее, графодоминантные функции выбора представляют определенный интерес для методов многокритериальной оптимизации. Это связано с тем, что сравнить между собой два варианта обычно гораздо проще, чем произвести выбор среди большего числа вариантов. Особенно это относится к диалоговым методам оптимизации, в которых задача сравнения возлагается на ЖЕР. Возникает естественный вопрос: в каких случаях исследователь имеет право производить выбор на основании попар -30-ных сравнений вариантов. Другими словами, при каких условиях существует некоторое бинарное отношение доминирования $. , что выбор ЖГР С (А) принадлежит подмножеству максимальных элементов по этому отношению Иахт А Обоснование применения бинарных отношений в многокритериальной оптимизации содержится в [_4] и основано на таких свойствах функций выбора, как свойство наследования [I] и свойство монотонности [ 4] выбора.
Напомним, что функция выбора С(А3 0 обладает свойством
1) наследования (Н), если т.е. вариант, выбираемый в некотором множестве, выбирается и в любом его подмножестве, этот вариант содержащем;
2) монотонности (М), если т.е. мощность выбора на подмножестве не превосходит мощности выбора на всем множестве.
В [ 4 ] доказана следующая теорема.
Теорема Пусть функция выбора С Д. ЭС") обладает свойствами (Н) и (М). Пусть
Следствие . Пусть С (А,Х ) - функция выбора, обладающая свойствами (Н) и (М). Тогда существует бинарное отношение & такое, что С(А) -C Mcxrs: 1\), - ЗІ -Действительно, пусть у$1 х. = уё СС{ »у\). Тогда C(A C(A Y = ССНах А)
Следствие утверждает, что свойств (Н) и (М) достаточно, чтобы при оптимизации обоснованно пользоваться графодоминантными функциями выбора. Если в результате диалога с ЛПР удастся построить некоторое бинарное отношение предпочтения 5 , описывающее его структуру предпочтений, то результирующий выбор ЛПР не изменится, если вместо исходного множества Я ему будет предъявлено подмножество Ma Q А.
В связи с этим исследование бинарных отношений предпочтения, их роли в моделях многокритериальной оптимизации приобретает особенно важное значение. Здесь будут рассмотрены бинарные отношения в пространстве критериев и наиболее подробно - класс порядковых бинарных отношений.
Использование информации о важности критериев при идентификации структуры предпочтений ЛПР
Основным свойством класса порядковых сравнений является его конечность. Верхний конус такого сравнения может содержать любой из 2 квадрантов пространства ІЯ в случае строгих шкал, и любой из Ъл в случае нестрогих шкал. Соответственно число порядковых сравнений в пространстве размерности П- в первом случае равно A/ (h)= 5. (штрих означает здесь и далее строгие шкалы), во втором - ЫС") - 2} .
Такое большое число порядковых сравнений, разумеется, затрудняет их аппроксимацию. Лишь задав ЛПР 2 (или ) вопросов относительно принадлежности каждого квадранта верхнему конусу сравнения, можно его идентифицировать.
Для облегчения этой задачи предлагается использовать информацию о сравнительной важности критериев, определение которой было дано в п.3.3. Приведем наглядный пример, подтверждающий такую возможность. Для пары критериев существует 16 различных порядковых сравнений в строгих шкалах. Предположим, что имеется информация о том, что критерии I важнее критерия 2 (1 2). Легко проверить, что лишь для четырех сравнений из 16 упорядочение критериев имеет такой вид (рис. 3.5).
Приведем более общие результаты.
Утверждение 3.1. Число сравнений & V , для которых равноправны два фиксированных критерия, равно
Доказательство . Верхний конус таких сравнений имеет ось симметрии. ЕГО проекция на плоскость равноправных критериев имеет один из видов, изображенных на рис. 3.6. Очевидно, что ровно три квадранта (1,П,Ш или 1,Ш,1У) полностью определяют вид проекции. Остальные n-а. критерия образуют 2.п квадрантов, следовательно, число квадрантов, однозначно определяющих п-г. сравнение, равно 3-2 . Отсюда следует справедливость утверждения 3.1.
Доказательство . Рассмотрим пространство IR равноправных критериев. Квадранты, имеющие одинаковое число положительных координат, либо не принадлежат верхнему конусу SC$ либо все принадлежат. Значит достаточно выбрать по одному представителю из такой группы квадрантов (а таких групп всего к+4 ), чтобы однозначно определить проекцию верхнего конуса на подпространство IR . Остальные n-k критериев образуют 2 " квад-рантов. Таким образом,СК-Ч )2. квадрантов однозначно определяют сравнение Я. . Утверждение доказано.
Следствие 3.1. Число сравнение, для которых равноправны все ГС- критериев, равно
Таким образом, если имеется информация о равноправности всех критериев, то для идентификации этого сравнения достаточно задать ЛПР всего П+А вопрос.
Утверждение 3.3. Число сравнений 9L & V , для которых существует f групп, содержащих соответственно /,..., кр равноправных критериев, равно
А// пач-и) "" а если все множество критериев разбито на такие группы, то
Доказательство этого утверждения во многом повторяет предыдущее и здесь не приводится. Утверждение 3.4. Число сравнений SLe &v , для которых два фиксированных критерия строго упорядочены, равно
Доказательство . Пусть для определенности 1 2. Квадранты, содержащие гиперплоскость oc Xg, могут независимо принадлежать либо не принадлежать верхнему конусу сравнения L . Таких квадрантов 2. и из них может быть составлено 2 е1 на-боров. Пусть из 2 квадрантов таких, что х 0С , только R принадлежат верхнему конусу. Поскольку 1 -2, то квадранты с другой стороны гиперплоскости Х Х могут принадлежать верхнему конусу только вместе с симметричными им квадрантами. Но для фиксированных квадрантов из полупространства Х Хг существует 2. -\ различных наборов квадрантов из полупространства XA X , так что при этом 1 -2. Учитывая, что к принимает значения от I до 2п и что существует С п-г сочетаний по к квадрантов, получаем, что число верхних конусов, образованных квадрантами с различными первыми двумя координатами, равно сумме 2.п_г -г п-8.
Общее число сравнений с учетом оставшихся 2. квадрантов равно 2. ( -2 )» что и требовалось доказать.
В табл. 3.1 приведены числовые результаты для некоторых значений П..
Математическое ожидание мощности выбора для порядковых сравнений. Строгие шкалы
Допустим, что при решении задачи выбора на основании полученной от ЛПР информации были предложены две функции выбора С,(Х)и Сг(ХЛ , аппроксимирующие выбор ЛПР: СА (X)sC,(X) и С (X) Са.(Х) . Можно ли априори, т.е. до получения конкретных выборов, судить о том, какую из них следует принять как решение задачи? Ясно, что предпочтение надо отдать той, которая точнее аппроксимирует выбор ЛПР. Если функции С\ и Са оказались вложенными, то выбрать из них лучшую нетрудно, однако в общем случае вложенности может не быть и тогда сравнить функции выбора на множественном языке не удастся.
Учитывая, что числовой характеристикой выбора является его мощность, предлагается использовать ее и как характеристику точности аппроксимации. Однако может оказаться, что на разных предъявлениях Х и Xs. 1С4(Х \ Сг(Х,,)но СЧСХ \ IC CXa l Поэтому необходимо, чтобы такая характеристика не зависела от конкретного предъявления.
Точность того или иного приближения обычно характеризуется либо максимальной величиной ошибки, либо ее средней величиной. Первый способ в данном случае представляется неприемлемым, так как мощность выбора существенно зависит от предъявления и почти всегда можно указать случай, когда она совпадает с мощностью самого предъявления. На рис. 4.1 приведен случай Сп (X) = X Можно указать и случай, когда при лексикографическом выборе С (Х) = Х (все элементы множества X имеют одинаковые координаты) . Однако вероятность этого выбора, вообще говоря, гораз до меньше, чем вероятность расположения точек на рис. 4.1. Поэтому представляется наиболее обоснованным в качестве характеристики точности аппроксимации использовать математическое ожидание мощности выбора. При этом предполагается конечность предъявлений, и через Эг = {ХЭС: х = \ обозначается множество всех допустимых предъявлений мощности 2 .
Таким образом, задача нахождения математического ожидания сводится к определению вероятности того, что произвольно выбранный вариант хєХ принадлежит СС )
Отметим ряд работ [_ 7, 9, 16, 17, 26, 52, 53] , посвященных исследованию с вероятностных позиций средней величины мощности выбора.
Здесь будут рассматриваться функции выбора в пространстве R . Предполагается, что распределение оценок любого варианта из множества А (А IR ) задается функцией
Если функция распределения fpCx) представима в виде произведения то будем говорить, что выбор производится в независимых шкалах, иначе - в зависимых. Все результаты этой главы получены для независимых шкал. Отметим, что исследования для зависимых шкал проводились в ]_ 16, 26 ] .
