Диссертация (1137100), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

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

Существуют следующие методысужения множества Парето-оптимальных решений Методсправедливыхкомпромиссов(илииспользованиеквантовинформации от ЛПР), разработанный В. Ногин, исследования в этойобласти также проводил В. Подиновский. Экспертные оценки при попарном сравнении Выбор главного критерия ЛПР ИдеяактивногоучастияЛПРвМКОпривелакразработкемногочисленных интерактивных методов, состоящих в чередующихсяпроцедурах выбора и автоматического расчета.

В обзорах литературыуказываются разные базовые методы. Например, стоит упомянуть методыARBDS [21], CONTEXT[22], GUESS[23], NIMBUS (NondifferentiableInteractive Multiobjective Bundle-based optimization System). Этот методразработан в Хельсинском университете (г. Хельсинки, Финляндия) подруководством профессора К. Миеттинен и др. Выбор точек, ближайших к идеалу Метод Электра (позже опишу)Удачное решение проблемы сужения множества Парето осуществляется наоснове так называемых «квантов информации» об отношении предпочтения [2],которые характеризуют готовность ЛПР проявлять определенную гибкость впроцессе принятия решений – уступать по одним критериям ради получениявыигрыша по каким-то другим критериям.

Заметим, что наличие «квантаинформации»может быть охарактеризовано и в терминах относительнойважности критериев.Пусть Y  Rm. Для любых двух векторовy,y’ P(Y)существуют дванепустых непересекающихся множества номеров критериев A,B  {1,2,,…,m} ,таких, что77781) yi > y’i для всех i  A2) y’j > yj для всех j  B3) ys = y’s для всех остальных s (если они найдутся)Самый простой способ сужения множества Парето – это исключение какогото одного вектора из пары Парето-оптимальных векторов после их сравнения;иначе говоря, − предпочтение одного Парето-оптимального вектора другому, т.е.y PY y’,гдеy, y’  P(Y).Будем говорить, что подобное предпочтение составляет некий «квант»информации об отношении строгого предпочтения PY ЛПР.Аксиомы «разумного» выбора1) Исключение доминируемых векторов2) Транзитивность отношения предпочтения3) Согласованность отношения предпочтения с критериями4) Инвариантность отношения предпочтения относительно положительноголинейного преобразованияПри выполнении аксиом 2-4 неизвестное отношение PYстрогогопредпочтения ЛПР является конусным с острым выпуклым конусом.Получение «кванта» информации дает возможность выделить некоторую«часть» отношенияPY, с помощью которой можно построить определеннуюоценку сверху P^(Y) для неизвестного множества выбираемых векторов:C(Y) P^(Y)  P(Y), где P^(Y) = f(Pf^(X)) – полнота конечного набора «квантов»информацииДоказано, что с помощью конечного непротиворечивого набора «квантов»информации можно получить сколь угодно точную оценку сверху длянеизвестного множества недоминируемых векторовNdom(Y) = { y*Y | не существует yY: y Py y* }В общем случае алгоритм учёта набора «квантов» информации для сужениямножества Парето выглядит следующим образом.

Пусть задан набор «квантов»01 , … , 0 0 . Обозначим через = 0 размерность векторного критерия . На7879первом шаге строится матрица 1 , порождённая вектором 01 . Вводится матрица 1= 1 . Если 0 = 1, то других «квантов» нет, и алгоритм завершается. Если 0 > 1,то строятся образы оставшихся «квантов» 1 02 , … , 1 0 0 . Если среди них есть хотябы один вектор 1 0 ≤ 0, алгоритм завершается с предупреждением опротиворечивостиисходногонабора«квантов».Всевекторы1 0 ≥ 0отбрасываются.

Если все векторы оказались отброшены, алгоритм завершается.Если нет, то оставшиеся векторы переобозначаются как 11 , … , 1 1 , и алгоритмпереходит на следующий шаг. Пусть проделано − 1 шагов, построены матрицы размерности × −1 , = ̅̅̅̅̅̅̅̅̅̅1, − 1 и известна текущая матрица −1 .−11Остаются неучтёнными «кванты» −1, … , −1. На -ом шаге строится матрица ,1порождённая вектором −1. Вычисляется = −1 . Если −1 = 1, то«квантов» больше нет, и алгоритм завершает свою работу. Если же −1 > 1, то−12строятся образы «квантов» −1, … , −1. Если среди получившихся векторовесть такие, которые не имеют строго положительных компонент, то алгоритмзавершается с предупреждением о противоречивости исходного набора «квантов».Все векторы, не имеющие отрицательных компонент, удаляются. Оставшиесяпереобозначаются как 1 , … , . Если векторов не осталось, алгоритм завершается.Если ≥ 1, алгоритм переходит к следующему шагу.

Алгоритм конечен, так какна каждом шаге выполняется < −1 , а 0 — конечное число. Отсюда же видно,что алгоритм сделает не более 0 шагов, где 0 — количество исходных «квантов».Метод сужения множества Парето с использованием квантов информации оботношении предпочтения ЛПР реализован в программе, получившей названиеParSetRe, разработанной в Санкт-Петербургском Государственном Университете.Пользователь может задать набор критериев, сформировать список вариантов,ввести информацию о предпочтениях и получить суженное множество альтернатив(рис. 26,27,28). Программа представляет собой jar-файл, поэтому для её запусканеобходима предустановленная среда исполнения Java (англ. JRE — Java RuntimeEnvironment).7980Рисунок 26.

Программа ParSetReРисунок 27. Программа ParSetRe8081Рисунок 28. Программа ParSetRe3.3 Агрегация разработанной имитационной модели с многоагентнымгенетическим алгоритмом и другими подсистемамиИнтеграция модели в PowerSim Studio 8 с MAGAMO была реализована сиспользованием компоненты PowerSim Engine, являющейся SDK-библиотекой.На управляющем процессоре запускается программный модуль MAGAMO,который, в свою очередь, пробуждает агентов (вычислительные процессоры) ипередает и данные.Это позволило управлять вычислениям модели из MAGAMO.

Фрагмент кодаSimEngine = new PsSimEng.SimulationEngine();SimProj =SimEngine.OpenProject("C:\\HSE\\Аспирантура\\MAGAMO\\Experimental.sip", "");Sim = SimProj.OpenDefaultSimulation();for (int i = 0; i < indiv.Length; i++){Sim.Reset();indiv[i].decodeDecisionVariablesValues();foreach (InputVariables iv in inputVariables)8182{for (int j = 0; j < indiv[i].var.Length; j++){if (iv.name == indiv[i].var[j].name) iv.value[indiv[i].var[j].index] =indiv[i].var[j].value;}if (iv.dimension == 1) Sim.Variables.Find(iv.name).Number = iv.value[0];else Sim.Variables.Find(iv.name).Number = iv.value;}indiv[i].objective = new double[3];CurrentTime = StartTime;while (CurrentTime <= StopTime){if (CurrentTime == StopTime) break;Sim.Advance();CurrentTime = CurrentTime + Convert.ToDouble(TimeStep);}for (int j = 0; j < objective.Length; j++){indiv[i].objective[j] = Sim.Variables.Find(objective[j]).Number;}}Интеграция с другими подсистемами проходила с использование импорта иэкспорта данных из таблиц Microsoft Office Excel.3.4 Результаты численных экспериментов с использованиемразработанного программного комплексаПосле демонстрации полученных результатов ЛПР, от него поступиладополнительная информация о предпочтениях, которая была учтена при8283использовании метода справедливых компромиссов для сужения фронта Парето.

Врезультате фронт Парето был сужен с 200 точек, найденных в результате апробацииMAGAMO в 3 главе, до 6 рациональных (рис. 29), из которых ЛПР предстоитокончательно выбрать одну из альтернатив с учетом избранной долгосрочнойстратегии. Также ЛПР далее может воспользоваться Методом анализа иерархий,экспериментируя с тем, при каком соотношении оценок важности критериев,какую из альтернатив предложит выбрать метод.Рисунок 29. Сужение найденного фронта Парето до 6 Парето-оптимальныхрешенийОтдельное исследование было проведено на выявление оптимальногозначения вероятности мутации. Так, наилучшей скорости схождения удалосьдобиться при вероятность мутации в диапазоне [0.005 ; 0.02], При этом мутацииподвергаются max(1, % 100) генов, которые выбираются случайным образом.Исследование оптимального числа особей в популяции показало, что онодолжно составлять 15 0,1 .

Другое исследование показало, что начальнуюпопуляцию следует создавать с как можно более вариативным набором хромосом,что рекомендуется и для обычного ГА.8384За счет исходного распределения пространства поиска между агентами сучетомэкспертныхоценокистатистическогоисследования(выявлениезависимостей между переменными) удалось улучшить качество работы алгоритмана 30%.3.5 ВыводыВ третьей главе диссертации описан разработанный оригинальный комплекспрограмм для поиска рациональных решений с использованием спроектированнойимитационной модели, подсистемы поиска подмножества Парето на основеMAGAMO, визуализации фронта Парето, сужения фронта Парето. В результатепроизведено принципиальное расширение функционала системы имитационногомоделирования в виде нового оптимизационного модуля.В тексте также описывается используемое средство визуализации и сужениямножества Парето-оптимальных решений.В заключении третий главы приводятся численные эксперименты сиспользованием разработанного программного комплекса.

Характеристики

Список файлов диссертации