Диссертация (Алгоритмы сужения множества Парето на основе информации о предпочтениях ЛПР), страница 11
Описание файла
Файл "Диссертация" внутри архива находится в папке "Алгоритмы сужения множества Парето на основе информации о предпочтениях ЛПР". PDF-файл из архива "Алгоритмы сужения множества Парето на основе информации о предпочтениях ЛПР", который расположен в категории "". Всё это находится в предмете "физико-математические науки" из Аспирантура и докторантура, которые можно найти в файловом архиве СПбГУ. Не смотря на прямую связь этого архива с СПбГУ, его также можно найти и в других разделах. , а ещё этот архив представляет собой кандидатскую диссертацию, поэтому ещё представлен в разделе всех диссертаций на соискание учёной степени кандидата физико-математических наук.
Просмотр PDF-файла онлайн
Текст 11 страницы из PDF
е.степень принадлежности ему варианта x равна α в том и только в том случае,59если x содержится во множестве Парето относительно векторного критерия скомпонентами g i f для i : θi > α, но, если α < 1, не содержится во множествеПарето относительно векторного критерия с компонентами g i для i : θi > α.Наконец, коснёмся вопроса о проверке «квантов» на непротиворечивость.Определение 2.12 [9]. Набор квантов информации u1 , . . . , up с соответствующими степенями уверенности ν1 , .
. . , νp называется противоречивым,если не существует такого нечёткого отношения с функцией принадлежности µ, которое удовлетворяет всем аксиомам разумного выбора и соотношениям µ u1 , 0 > ν1 , . . ., µ (up , 0) > νp .Следующий критерий позволит проверять непротиворечивость «квантов»прямо по ходу работы алгоритма 2.Утверждение 2.16. Набор нечётких «квантов» информации u1 , . . .
, upс соответствующими степенями уверенности ν1 , . . . , νp противоречив в томи только в том случае, если для некоторого номера s = 1, p среди образующих bk нечёткого конуса Ls−1 , двойственного к нечёткой конической оболочке Ks−1 векторов e1 , . . . , em , u1 , .
. . , us−1 с соответствующими степенямипринадлежности 1, . . . , 1, ν 1 , . . . , ν s−1 , нет таких, степень принадлежности которых равна единице и bk us > 0.Доказательство. Достаточность. Предположим, что набор непротиворечив, т. е. существует нечёткое отношение предпочтения с функцией принадлежности µ, удовлетворяющее всем аксиомам и соотношениям µ uk , 0 > νkдля k = 1, s.Рассмотрим ядро нечёткого конуса Ls−1 . Оно является чёткой коническойоболочкой тех его образующих b1 , .
. . , bq , которые имеют степень принадлежности, равную единице. Предположим, что все эти образующие расположеныв неположительном полупространстве, образованном гиперплоскостью с нормалью us : ∀k ⇒ bk us 6 0. Но тогда bk (−us ) > 0, и вектор −us принадлежитконусу, двойственному к ядру конечнопорожденного нечёткого конуса Ls−1 ,который в соответствии с утверждением 2.9 есть не что иное, как суппортнечёткого конечнопорожденного конуса K. Этот конус, в свою очередь, содержится в конусе отношения предпочтения ЛПР.
Следовательно, конус отношения предпочтения не является острым, т. к. он с ненулевыми степенямипринадлежности содержит векторы us и −us . Другими словами, µ (us , 0) > 0и µ (−us , 0) = µ (0, us ) > 0. Но это противоречит иррефлексивности отноше60ния предпочтения. Следовательно, предположение несостоятельно, и наборквантов противоречив.Необходимость. Предположим противное: пусть для каждого s средиобразующих bk конуса Ls−1 найдётся хотя бы одна такая, что её степень принадлежности равна единице и bk us > 0.Рассмотрим конусное нечёткое отношение µ с конусом Kp — нечёткой конической оболочкой векторов e1 , .
. . , em , u1 , . . . , up со степенями принадлежности 1, . . . , 1, ν 1 , . . . , ν p . Так как среди образующих этого конуса есть всекванты uk , то µ uk , 0 > νk . Поскольку образующими также являются ортыпространства, µ ek , 0 = 1 для всех индексов k. Отсюда с учётом конусности следует выполнение третьей аксиомы. Конусность же этого отношениявлечёт справедливость четвёртой аксиомы.
Транзитивность этого отношениянапрямую следует из выпуклости конечнопорожденного конуса Kp .Рассмотрим конус Ls−1 и обозначим его образующие за bk , k = 1, q. Покажем, что если для некоторого s ранг набора образующих конуса Ls−1 с единичными степенями принадлежности равен m и хотя бы одна из них удовлетворяет bk us > 0, то ранг набора образующих конуса Ls с единичными степенями принадлежности также равен m. С учётом утверждения 2.11 образующими конуса Ls с единичными степенями принадлежностью являются те векторы bk , для которых bk us > 0, и us bi bj − us bj bi для bi , bj : bi us > 0 > bj us .Предположим, что ранг этих векторов меньше m. Тогда есть ненулевой вектор v, ортогональный им всем.
Среди них есть образующая bi : bi us > 0. Т. к.vbi = 0, то для всех j : bj us < 0 справедливоvbj =v us bi bj − us bj bi + us bj vbi= 0.us biСледовательно, все образующие bk ортогональны вектору v, и их ранг неможет быть равен m, что противоречит предположению.Рассмотрим векторы x, y ∈ Rm : µ (x, y) > 0.
Тогда вектор x − y имеет ненулевую степень принадлежности конусу Kp . Предположим, что векторy − x также имеет ненулевую степень принадлежности этому конусу. Тогдадвойственное к суппорту Kp ядро конуса Lp лежит в гиперплоскости, ортогональной вектору x − y. Следовательно, ранг образующих конуса Lp с единичной степенью принадлежности меньше m. Однако ранг образующих ко61нуса L0 с единичной степенью принадлежности — ортов пространства Rm —равен m.
Но по предположению при каждом s группа образующих из положительного полупространства относительно us содержала образующие сединичной степенью принадлежности, следовательно, ранг образующих конуса Lp с единичной степенью принадлежности должен быть равен m. Этопротиворечие показывает, что вектор y − x не может принадлежать конусу Kp . Таким образом, ∀x, y ∈ Rm : µ (x, y) > 0 ⇒ µ (y, x) = 0, и нечёткоеотношение µ иррефлексивно.Таким образом, нечёткое отношение, удовлетворяющее всем аксиомам исоотношениям µ uk , 0 > νk , существует, а следовательно, набор квантовнепротиворечив, что не согласуется с условием утверждения. Следовательно,предположение неверно.Таким образом, для решения задачи сужения множества Парето в случае«квантов» нечёткой информации следует применить алгоритм 2 для нахождения образующих конуса, двойственного к конической оболочке «квантов»и ортов критериального пространства, по ходу его работы проверить непротиворечивость предоставленной информации и воспользоваться утверждением 2.15 для получения оценок степеней принадлежности вариантов множеству выбираемых решений.62Глава 3Программная реализация:пакет ParSetReМетод сужения множества Парето с использованием нечётких квантовинформации об отношении предпочтения ЛПР реализован в программе, получившей название ParSetRe.
Пользователь может задать набор критериев,сформировать список вариантов, ввести информацию о предпочтениях и получить суженное множество альтернатив.Программа представляет собой jar-файл, поэтому для её запуска необходима предустановленная среда исполнения Java (англ. JRE — Java RuntimeEnvironment).Интерфейс программы поддерживает два языка: английский и русский.Выбрать язык можно в меню «Настройки».
При этом даже нет необходимостиперезагружать программу: изменения вступят в силу сразу. Перевод ParSetReна другие языки не является сложной задачей, так как все используемые впрограмме строки собраны в текстовый файл.3.1Решение задачи многокритериальноговыбораПосле запуска программы ParSetRe у пользователя есть возможность либо создать новую задачу принятия решения, либо открыть уже существующую, воспользовавшись стандартным системным диалогом открытия файла.63В обоих случаях в результате появится окно задачи, содержащее нескольковкладок, отображающих различную информацию о ней.Рассмотрим процесс создания новой задачи принятия решения в программе ParSetRe.Прежде всего необходимо составить список критериев, по которым будутоцениваться доступные альтернативы.
Он отображается в таблице на вкладке «Критерии». Введя название в последнюю строку этой таблицы, можнодобавить новый критерий (рис. 3.1). Критерии можно в любой момент переименовывать, добавлять и удалять, хотя с ростом количества вариантовэто может оказаться небыстрой операцией, так что рекомендуется с самогоначала задать все критерии.Рис. 3.1: Добавление критериевДалее составляется список возможных вариантов. Есть несколько способов добавлять их. Можно вводить по одному кнопкой «Добавить вариант»,которая показывает диалог ввода варианта (рис. 3.2). В нём необходимо заполнить оценки варианта по всем критериям, в качестве степени уверенностизаранее поставлена единица.Реализован другой способ добавления вариантов: их можно вставлять избуфера обмена. Таким образом, есть возможность переноса в программу списка вариантов, подготовленного предварительно, например, в Excel.После ввода всех вариантов начинается собственно процесс принятия ре64Рис.
3.2: Добавление вариантовшения. Заведомо неподходящие альтернативы исключаются кнопкой «Сузитьнабор вариантов». Насколько тот или иной вариант подходит, оцениваетсячислом от 0 до 1, которое отображается в колонке «Уверенность».Для получения дополнительной информации о предпочтениях предусмотрен диалог сравнения критериев (рис. 3.3), вызываемый соответствующейкнопкой.
В нём ЛПР может сопоставить два критерия и оценить свою готовность к компромиссу, задавшись вопросом, сколько оно готово пожертвоватьпо одному критерию ради увеличения другого на единицу. Ответ на этотвопрос приводит к появлению кванта информации.Рис. 3.3: Сравнение критериевВся известная информация о предпочтениях отображается на вкладке65«Кванты». Продвинутые пользователи, знакомые с изложенной в данной работе теорией, могут самостоятельно вносить информацию кнопками «Добавить квант» и «Вставить кванты».
Вкладка «Новые критерии» содержитматрицу, которая даёт вектор новых критериев после умножения на векторисходных критериев. Другими словами, каждая её строка описывает новыйкритерий, получаемый суммированием исходных критериев с весами, указанными в этой строке. При этом значимость каждого нового критерия указывается в последнем столбце числом от 0 до 1.Если введённая информация о предпочтениях противоречива, то соответствующее сообщение выводится вместо матрицы коэффициентов на вкладке«Новые кванты» и показывается при попытке сузить набор вариантов, таккак это действие невозможно в случае нарушения аксиом разумного выбора.Если же противоречий не выявлено, кнопка «Сузить набор вариантов» модифицирует степени уверенности альтернатив в соответствии с введённымипредпочтениями (рис.
3.4).Рис. 3.4: Результат3.2Структура программыРассмотрим теперь некоторые детали реализации ParSetRe. Так как дляэтого неизбежно придётся использовать названия классов и другие ссылки на66исходный код, листинги ParSetRe приведены в приложении. Исходные файлысодержат документацию в традиционном для языка Java формате javadoc.В основе ParSetRe лежит ядро, реализующее алгоритм учёта квантов информации в задаче принятия решения. Оно находится в пакете mcdm. Интерфейс ядра спроектирован таким образом, чтобы его можно было легкоиспользовать в других проектах.Главным классом, содержащим в себе всю информацию о конкретной задаче принятия решения: списки критериев, вариантов и квантов, — являетсякласс Problem.
Он предоставляет два конструктора:public Problem ( f i n a l F i l e s a v e F i l e ) throws IOException , ProblemFormatException ;public Problem ( ) ;Первый в качестве параметра принимает файл, из которого следует загрузить сохранённую задачу принятия решения. Если переданный файл не существует, не доступен для чтения или в процессе загрузки происходит какаялибо иная ошибка ввода-вывода, возбуждается исключение IOException. Если содержимое файла не соответствует ожидаемому формату сохранения задачи, выбрасывается ProblemFormatException. В случае успешной загрузкисохранённых данных задачи создаётся объект, описывающий её.Второй конструктор не имеет параметров и используется для созданияновой задачи принятия решения.