Лекция: Метод взвешенных метрик Чебышева

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

Как известно, метрики характеризуют расстояние между двумя точками в многомерном пространстве. В рассмотренном методе они измеряют расстояние в критериальном m-мерном пространстве между недостижимым вектором критериев и множеством достижимости G. Чтобы исключить случаи нулевых расстояний (неединственность критериального вектора с максимальным значением i-го критерия, принадлежность идеального вектора множеству G), в методе используется не идеальный вектор, а такой вектор, что

,

где, а, как и раньше, — максимальное значение i-й целевой функции на ХD. Таким образом, всегда и геометрически соответствующая точка в многокритериальном пространстве расположена правее и выше множества G.

Метрика Чебышева – это одна из семейства Lp-метрик, в которых расстояние в Rm задается в виде

(10.29)

Наиболее применяемые значения р:1,2 и. Метрика и называется чебышевской. Для нее выражение (10.29) принимает вид

. (10.30)

Если координатам придать неотрицательные веса, то получим взвешенные Lp-метрики ( ):

(10.31)

и в частности:

(10.32)

Очевидно, что при равенстве весов форма линий уровня не зависит от абсолютных значений. При неравных линии вытягиваются в направлении наименьших весов (рис. 10. 19).

Объединение метрик и L1 дает расширенную взвешенную метрику Чебышева :

(10.33)

где — малое положительное число. Здесь опущены знаки модуля, т.к. для YG всегда. Как при этом изменяются линии уровня показано на рис.10.20.

Минимизация расстояния между и множеством G, представленного в одной из метрик, позволяет получить, по крайней мере, слабо эффективное решение (см. теорему 5). В случае взвешенной метрики Чебышева эта задача имеет вид

. (10.34)

Введя новую переменную v, преобразуем ее к стандартной задаче минимизации:

(10.35)

В случае неединственности решения задачи (10.35) возможно получение доминируемых (слабо эффективных) критериальных векторов. Так на рис.10.21 результатом решения задачи (10.35) при некоторых может быть любая точка на отрезке ВС, но только точка С дает недоминируемый вектор Y. Для исключения таких ситуаций предложено два способа.

Первый состоит в использовании расширенной взвешенной метрики. Благодаря наклону линий (поверхностей) уровня этой метрики исключается получение слабо эффективных решений. На том же множестве G, что и на рис.10.21, минимизация расстояния в расширенной метрике дает только недоминируемую точку С (рис.10.22). Очевидно, что чем меньше, тем меньше изменяется наклон линий уровня по сравнению с взвешенной метрикой. Значения рекомендуется брать

По аналогии с (10.34) и (10.35) минимизация расстояния в расширенной взвешенной метрике (10.33) сводится к решению следующей задачи

(10.36)

Опираясь на теорему 5, можно доказать, что в случаях, когда D – конечное дискретное множество или выпуклый многогранник, задача (10.36) всегда дает недоминируемый критериальный вектор и каждый недоминируемый (паретовский) вектор может быть получен в результате решения (10.36) единственным образом. Однако при других D (нелинейных или дискретных с бесконечным числом точек) отдельные недоминируемые векторы нельзя получить из задачи (10.36). Такие случаи интересны в основном теоретически, так как на практике встречаются редко.

Второй способ, обеспечивающий получение недоминируемого вектора критериев, заключается в переходе к лексикографической оптимизации. Вместо одноэтапной минимизации расстояния в расширенной взвешенной метрике сначала решается задача (10.35) и, если она дает неединственное решение, то на втором этапе минимизируется расстояние в метрике L1, то е.сть. ищется

при тех же условиях, что и в (10.35) или (10.36). При таком подходе отпадает необходимость в выборе значения, а лексикографическая оптимизация гарантирует получение эффективных решений независимо от свойств множества D и все недоминируемые векторы критериев могут быть вычислены единственным образом.

Теперь остановимся на определении значений, используемых при отыскании паретовских решений. Первоначально множество весовых векторов формируется случайным образом из диапазона [0,1]. После выбора ЛПР предпочтительного критериального вектора пересчитывается соответствующий ему вектор весов. Дело в том, что один и тот же недоминируемый вектор может быть получен при разных весах, например, как в случае, показанном на рис.10.23. В алгоритме в качестве вектора весов, порождающего, рассматривается такой, который дает линию уровня, касающуюся G (в точке ) своей вершиной (рис.10.23, б). При этом компоненты вектора весов удовлетворяют следующему соотношению:

(10.37)

В алгоритме используется целый ряд эвристических параметров. Их значения можно выбирать исходя из следующих рекомендаций. Величину, входящую в формулу для, можно брать от 1 до 10% от или диапазона на G. При этом желательно получать целые. Объем выборки Р и число итераций t могут быть того же порядка, что и число критериев m. Коэффициент r сжатия множества выбирается по соотношению

где w — ширина минимального интервала [ ] может быть взята примерно равной 1/m.

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

Теперь опишем сам алгоритм, предложенный Штойером и Чу.

Шаг I. Определить недостижимый критериальный вектор .

Шаг 2. Положить номер итерации l=0, а начальный интервал весов [ ] =[0.1] для всех i.

Шаг 3. Принять l=l+1 и построить множество

.

Шаг 4. Случайным образом сгенерировать 50m весовых векторов из .

Шаг 5. Из полученного множества весовых векторов выбрать 2P наиболее различающихся.

Шаг 6. Используя выбранные веса, решить 2P соответствующих задач минимизации расстояний (в расширенной взвешенной метрике – (10.36) или лексикографически). Результат – множество недомини­руемых критериальных векторов.

Шаг 7. Из полученного множества выбрать Р наиболее различающихся критериальных векторов.

Шаг 8. Выбранные векторы предъявить ЛПР, который должен выделить из них наиболее предпочтительный – Y(l).

Шаг 9. Пересчитать :

Шаг 10. Определить новые (более узкие) интервалы весов:

=[0,rl], если ;

, если ;

= в остальных случаях.

Здесь rl означает 1-ю степень r.

Шаг 11. Если l<t и ЛПР желает продолжить поиск, перейти к шагу

3, иначе — к шагу 12.

Шаг 12. Остановиться, если ЛПР согласен приняnm за окончательное

решение векторы (Y(l),X(l)). Иначе вернуться на шаг 3.

В приведенном алгоритме не уточняется способ фильтрации, используемый для отбора наиболее различающихся векторов. Один из возможных приемов – кластерный анализ с заданным числом клас­теров, равным количеству требуемых объектов, с последующим оставлением одного представителя от каждого кластера. Следует заметить, что выбор способа фильтрации не имеет существенного значения. Важно лишь в качестве начальной точки фильтрации на шаге принимать вектор, выбранный ЛПР на предыдущей итерации. Тогда среди новых Р векторов не будет близких к Y(i) и, следовательно, выборка будет наиболее информативной.

При реализации алгоритма могут быть полезны следующие практические советы.

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

Чем больше число решений предъявляется ЛПР на одной итерации, тем быстрее сходится алгоритм. Но не следует забывать об информационных возможностях ЛПР, которые во многих работах оцениваются формулой «семь плюс-минус два». Конкретное число определяется с учетом опыта и характера ЛПР.

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