Soft constrained optimizationon a discrete set of objects.pdf К задачам оптимизации относят формирование допустимого множества Xsel ипоиск наилучшего решения x* в этом множестве: x*Xsel [1]. Метод оптимизациипо одному критерию, когда для формирования допустимого множества исполь-зуются остальные n-1 критериев, названные в [2] ограничительными, называетсяметодом главного критерия [3]. В более общем случае для поиска наилучшегорешения x* может использоваться m>1 критериев, а остальные n-m критериев иг-рают роль ограничительных. Методы многокритериальной оптимизации, исполь-зующие предварительное отсеивание вариантов по заданным ограничениям, по-лучили название методов условной оптимизации [4].Случаи, когда все n критериев используются либо для формирования допус-тимого множества Xsel, либо для поиска наилучшего решения x* в исходном мно-жестве X, относятся к частным задачам оптимизации. Вероятность полученияпустого допустимого множества Xsel при многих ограничительных критериях вы-сока. Поскольку метод уступок, заключающийся в последовательном ослабленииограничений для получения непустого допустимого множества трудоёмок, в [5]был предложен метод мягких притязаний. Его идея заключается в упорядоченииобъектов относительно обобщённого расстояния от образца, за который принима-ется совокупность заданных ограничений. При этом ни один из объектов не от-брасывается. Аналогичный ему «мягкий» подход может быть применён при ре-шении задачи условной оптимизации. Дело в том, что объекты, бракуемые по не-которому ограничительному критерию, могут оказаться более предпочтительны-ми оставшихся по совокупности целевых критериев. Например, в бытовой задачевыбора квартиры часто ставится требование: «первый и последний этаж не пред-лагать». Однако уютный зелёный двор и достаточные средства безопасности мо-гут сделать квартиру на первом этаже более предпочтительной, чем на промежу-точных этажах, где соседи есть как сверху, так и снизу. В работе рассматриваетсяметод решения такой задачи, названный аналогично методу мягких притязанийметодом мягкой условной оптимизации.1. Функция полезности ограничительного критерияМетод мягкой условной оптимизации основан на применении функций полез-ности не только для целевых, но и ограничительных критериев. Его идея заклю-чается в том, что функция полезности j-го ограничительного критерия принимаетнулевое значение в области запрещённых значений критерия. Таким образом,объекты, не отвечающие ограничению по j-го критерию, не исключаются из ис-ходного множества X, а получают нулевую оценку по этому критерию.В качестве примера будем рассматривать ограничение «снизу» yj ≥ cj, пред-ставляемое двухместным предикатом P ≥ (yj, cj). Область значений j-го показателя[yj,min, cj] является запрещённой, а область [cj, yj,max] - разрешённой. В простейшемслучае за функцию полезности u(yj) j-го показателя принимается предикатP ≥ (yj, cj):, max, min1, если [ , ],( ) ( , )0, если [ , ].j j ij j jj i jy c yu y P y cy y c⎧ = ≥ =⎨⎩ Подчеркнём, что, начиная с граничного значения на всём диапазоне значений[cj, yj,max], функция полезности u(cj)=1. Графически такая функция представляетсяпрямоугольным импульсом с передним фронтом в точке cj. Для фиксированныхдискретных значений j-го показателя, входящих в диапазон [cj, yj,max], значенияфункции полезности(1) выше. Поэтому есть смысл рассматривать конкурентоспособность объектов,нарушающих только одно из ограничений.Пусть объект xi не соответствует l-му ограничительному критерию. Тогдаul(xi) = 0. Отсюда следует условие конкурентоспособности объекта xi по осталь-ным критериям:1 11 1( ) ( ) ( ), , .n nj j i j j k l l kj jw u x w u x w u x k i l j− −= =ƒ ⋅ >ƒ ⋅ + ⋅   (2)Согласно условию (2), объект xi предпочтительнее объекта xk , xi , xk = 1, N,ik, если:1 11 1( ) ( ) ( ), .n nj j i j j k l l kj jw u x w u x w u x l j− −= =ƒ ⋅ −ƒ ⋅ > ⋅  (3)Таким образом, чем меньший вклад в скалярную оценку k-го объекта вноситвеличина wl⋅ul(xk), тем больше шансов у объекта xi опередить остальные объекты.Величина произведения wl⋅ul(xk) определяется величиной его сомножителей. Онауменьшается с уменьшением важности ограничительного критерия и величинойфункции полезности. Поскольку все объекты, кроме xi, выполняют l-е ограниче-ние, следует принимать во внимание только значения ul(xk), определённые на от-резке [cj, yj,max]. На этом отрезке функция полезности ul(xk)>0, а величина ul(xk) за-висит от её формы. Если форма прямоугольная, то величина произведения сво-дится к важности критерия: wl⋅ul(xk)=wl⋅1 = wl. Наименьшее приращение ul(xk) име-ет место для выпуклой функция полезности с наибольшей положительной степе-нью.Итак, общими факторами, которые влияют на скалярные оценки объектов,удовлетворяющих l-му ограничительному критерию, является важность критерияи форма функции полезности. Влияние объекта на величину скалярной оценкипроявляется через значение l-го показателя. Чем оно меньше, тем больше шансовна то, что скалярная оценка xi может оказаться выше остальных. И объект xi, ко-торый мог быть исключён из множества X при применении метода условной оп-тимизации, при использовании мягкой условной оптимизации может оказатьсяпредпочтительнее остальных объектов.3. Пример применения мягкой условной оптимизацииПусть возникла задача выбора квартиры в пятиэтажном доме. Лицо, прини-мающее решение (ЛПР), интересует расположение квартиры в доме. С этой цельюон рассматривает 4 признака: этаж, вид из окон, число соседей (по этажам), подъ-ём на этаж. Для выбора предложено 5 квартир. Их характеристика по выбраннымпризнакам приведена в табл. 1.Т а б л и ц а 1Варианты квартирКвартира Этаж Окна Соседи ПодъёмКв.1 1 5 1 1Кв.2 2 1 2 2Кв.3 3 2 2 3Кв.4 4 3 2 4Кв.5 5 4 1 5Вид из окон закодирован следующими числами: 1 - 3 окна на улицу, 2 - 2 окнана улицу, 3 - 1 окно на улицу, 4 - вид на двор-колодец, 5 - вид на зелёный двор.Промежуточные квартиры имеют двух соседей по этажам, а крайние (1-й и 5-йэтаж) - одних соседей. Трудоёмкость подъёма в квартиру в доме без лифта обрат-но пропорциональна её этажности.Условия выбора представлены в табл. 2.Т а б л и ц а 2Условия выбора квартирПризнак Мин. зн. Макс. зн. Вес Опт. Нижн. гр. Верхн. гр.Этаж 1 5 0,25 Макс 1 5Окна 1 5 0,25 Макс 0 5Соседи 1 2 0,25 Макс 0 2Подъём 1 5 0,25 Мин 1 5Во втором и третьем столбцах представлены границы шкал признаков. В чет-вёртом столбце задан вес признаков (важность критериев), а в пятом столбце -направление оптимизации. Различие шкал и единиц измерения позволяют считатьрассматриваемые признаки неоднородными. При применении скалярной оптими-зации они подлежат нормированию. Результатом нормирования целевых критери-ев являются линейные монотонные функции. Однако их применение без критиче-ского анализа полезности может дать неправильные результаты.Рассмотрим функции полезности признаков, начиная с ограничительного кри-терия «Этаж». Его функция полезности представлена на рис. 1.101,0 5,0Рис. 1. Функция полезности признака «Этаж»Она создана на основе ограничительного критерия «первый и последний этажне предлагать» и имеет нулевые значения для 1-го и 5-го этажей.Функция полезности признака «Окна» представлена на рис. 2.100,0 5,0Рис. 2. Функция полезности признака «Окна»Она монотонно возрастает пропорционально кодам, характеризующим вид изокна. Для того чтобы полезность кода 1 не было нулевой, левая граница шкалысдвинута до нуля.Функция полезности признака «Соседи» представлена на рис. 3. Расширениелевой границы шкалы этого признака не принципиально. Одному соседу по этажуназначена стопроцентная полезность, а двум соседям - 50 %.100,0 2,0Рис. 3. Функция полезности признака «Соседи»Функция полезности признака «Подъём» представлена на рис.4. Полезностьхарактеризует трудоёмкость подъёма и обратно пропорциональна этажностиквартиры. Пятому этажу назначена полезность в 30%.101,0 5,0Рис. 4. Функция полезности признака «Подъём»Если воспользоваться методом условной оптимизации с ограничением поэтажности квартиры («первый и последний этаж не предлагать»), то после исклю-чения вариантов кв.1 и кв.2 для выбора остались бы 3 варианта: кв.2, кв.3, кв.4.Применение метода мягкой условной оптимизации с приведёнными функциямиполезности даёт следующие результаты (см. табл. 3).Т а б л и ц а 3Результаты оптимизации при равной значимости критериевКвартира Этаж Окна Соседи Подъём Оценка РангКв.1 0 1,0 1,0 1,000 0,75 1Кв.2 1 0,2 0,5 0,825 0,63 4Кв.3 1 0,4 0,5 0,650 0,64 3Кв.4 1 0,6 0,5 0,475 0,64 2Кв.5 0 0,8 1,0 0,300 0,53 5Квартира на первом этаже, имеющая нулевую полезность по первому призна-ку, получила наивысшую скалярную оценку за счёт трёх целевых критериев. ЕслиЛПР - пожилой человек или инвалид, для него наиболее важным критерием явля-ется «Подъём». Если ему назначить вес 0,5, а остальным критериям - 0,167, то ва-рианты кв.2 и кв.4 поменяются местами (см. табл. 4).Т а б л и ц а 4Результаты оптимизации при разной значимости критериевКвартира Этаж Окна Соседи Подъём Оценка РангКв. 1 0 1,0 1,0 1,000 0,83 1Кв. 2 1 0,2 0,5 0,825 0,70 2Кв. 3 1 0,4 0,5 0,650 0,64 3Кв. 4 1 0,6 0,5 0,475 0,59 4Кв. 5 0 0,8 1,0 0,300 0,45 5ЗаключениеМетод мягкой условной оптимизации соответствует подходам, применяемым внастоящее время для решения трудно формализуемых («человеческих») проблем.Переход от жёстких оценок «Истина» и «Ложь» породил многозначную, а в пре-деле - нечёткую логику. Частичная истина позволила создать теорию нечёткихмножеств, хорошо моделирующую человеческие оценки явлений и сущностей. Врусле этих подходов находится основная идея метода мягкой условной оптимиза-ции - заменить отсеивание объектов, не удовлетворяющих ограничениям (жёст-кий подход) на оценивание этих объектов по остальным критериям (мягкий под-ход). При этом нередко кандидат на отсеивание может оказаться лучшим средидругих объектов, не подлежавших отсеиванию.Другим, не менее важным, результатом работы является применение обосно-ванных функций полезности. Весьма часто при нормализации неоднородных по-казателей забывают, что для получения скалярных оценок используются линей-ные функции полезности. Однако правомерность их использования требует дока-зательств. В противном случае результаты оптимизации получаются неточными.Создание функций полезности представляет собой достаточно трудоёмкий про-цесс. Однако он окупается получением доказательной базы для обоснования дос-товерности получаемых результатов. В тех случаях, когда результат оптимизациикажется интуитивно правильным («зачем было огород городить?»), вся работа посозданию модели выбора может рассматриваться в качестве обоснования пра-вильности полученных результатов.

Скачать электронную версию публикации