<<
>>

5.2. Описание алгоритма ЦИКЛ


Формальная постановка задачи порядковой классификации многокритериальных альтернатив приведена в разделе 4.3. Введем на множестве векторных оценок У метрику /э(х, у), определенную как
N
р(х> у) = IХ<1 ~Уя і ¦
(,=1
Для векторов х,у€ Y таких, что (х, у)є Р, рассмотрим множество векторов, доминирующих у и доминируемых вектором х по отношению Q, заданному выражением (4.1):
Л(х, У) = {V Є У I (х, V) Є Q, (v, у) Є Q}.
(5.1)
Обозначим у' = (1,1, ...,1), у" = (Si,S2, ...,Sjv)- Легко заметить, что множество Л(у/,у") совпадает с множеством У. Назовем индексом ||у|| вектора у Є У число /э(у',у), т. е. сумму всех его компонент, уменьшенных на 1. Введем также множество векторов из Л(х, у), «равноудаленных» от х и у:
L(x,y) = {veA(x,y) |||V|| = M±M}. (5.2)
Здесь и далее деление производится нацело.
93
5.2. ОПИСАНИЕ АЛГОРИТМА ЦИКЛ
Введем определенные на множестве У числовые функции CUіу) и CL(y), равные, соответственно, максимальному и минимальному номерам классов, допустимых для векторной оценки у, т. е. классов, при отнесении вектора у к которым не нарушается условие (4.5) непротиворечивости классификации. Будем считать вектор у классифицированным и отнесенным к классу Ct, если для него выполняется условие:
CL( у) = Си( у) = к.
Первоначально для каждого вектора у, принадлежащего множеству Уа С У векторных оценок допустимых объектов (обозначения из раздела 4.3), полагается С^(у)=1, Си (у)~М. Для удобства будем считать, что для вектора z, принадлежащего множеству Уь = У\Уа векторных оценок недопустимых объектов, выполняется условие CL(z)=Cu(z) = 0.
Определим процедуру распространения по доминированию S(y). Она состоит в косвенной классификации векторов, связанных с вектором у отношением доминирования Р, если известна классификация вектора у. Предполагается, что вектор у клас-сифицирован, например, отнесен к классу Ск, а, значит, у Є Ук и CL(y) Си(у)=~-к. Тогда для всех векторов хЄ Уа таких, что (х, у)Є Ри Сь(х.)-'к, функция CL(x) переопределяется так, чтобы CL(x) к. Аналогично, для всех векторов zG Уа таких, что (z, у)Є Р и Си(z) >к, функция Си(z) переопределяется так, чтобы С'!{z) к.
Рассмотрим основной механизм алгоритма ЦИКЛ — рекурсивную процедуру классификации D(а, Ь) на множестве А(а, Ь). Предполагается, что (а, Ь) Є P,CL(а) = Си(а) = к, CL(b) = С' (b) = I. Выполняются следующие действия:
Для всех векторов хЄ L(a,b) поочередно выполняются шаги 2 ", 3 4
". Если класс принадлежности вектора х неизвестен (то есть С/у(х)- Си(х)), то вектор х предъявляется ЛПР для классификации. Пусть ЛПР относит вектор х к классу Сг и х€ Yr. Выполняется процедура распространения по доминированию S(x). Проверяется условие непротиворечивости (4.5). Если оно нарушено, то выполняется указанная ниже процедура устранения противоречий В..
". Если (г = 0 или г > к) и (а, х) Є Р, то выполнить D(а, х).
". Если (г—0 или г /) и (х,Ь)є Р, то выполнить D(x., b).
При классификации вектора х на шаге 2 ° ЛПР может допустить ошибку, и тогда появится пара векторов х,у Є У, нарушающих условие непротиворечивости (4.5). Процедура R устранения противоречий состоит в следующем. Обозначим через У' множество непосредственно классифицированных экспертом векторов. Тогда, пока в множестве Уе существует пара векторов, нарушающих свойство непротиворечивости (4.5), такая пара предъявляется эксперту с предложением изменить класс принадлежности одного или обоих векторов. После чего функции Си (¦) и CL{-) переопределяются до их начального состояния, и проводится распространение по доминированию S(v), исходя из каждого вектора VG Ye.
Вообще говоря, параметры алгоритма, в том числе и число обращений к эксперту, зависят от способа выбора вектора х на шаге 1 Предлагается следующая эвристика: среди всех еще неклассифицированных векторов множества L(а, Ь) выбирается вектор, непосредственно доминирующий наибольшее число неклассифицированных векторов, т. е., выбирается вектор х*:
х* = arg шах у Є Y | (х, у) Є Р или (у, х) € Р,
xeL(a.b) 1р(х,у) = 1, CL(y)На самом верхнем уровне алгоритм ЦИКЛ выглядит следующим образом.
Для всех векторов у€ Y" устанавливается CL(у) = 1 и Си(у) -М, для всех векторов ує Yb устанавливается CL{y) — Си( у) = 0.
ЛПР предъявляются для классификации векторы у' и у". Выполняется распространение по доминированию S(y') и S(y").
Если классы принадлежности у' и S(у") различаются, то выполняется процедура классификации D{у',у").
<< | >>
Источник: Ларичев О.И.. Вербальный анализ решений. 2006

Еще по теме 5.2. Описание алгоритма ЦИКЛ:

  1. 5.3. Свойства алгоритма ЦИКЛ
  2. 5.5. Компьютерная реализация алгоритма ЦИКЛ
  3. 3.1. Алгоритм компьютерной программы прогнозированияисторических рядов(Алгоритм построен с использованием методовтригонометрического анализа)
  4. ОПИСАНИЕ, дескрипция (англ. description - описание
  5. ГЛАВА 4. ГАРМОНИЗИРОВАННАЯ СИСТЕМА ОПИСАНИЯ И КОДИРОВАНИЯ ТОВАРОВ. 4.1. ЦЕЛЬ И ПРЕДПОСЫЛКИ СОЗДАНИЯ ГАРМОНИЗИРОВАННОЙ СИСТЕМЫ ОПИСАНИЯ И КОДИРОВАНИЯ ТОВАРОВ
  6. 5.6. Сравнение алгоритмов классификации
  7. 5.7. Особенности метода ЦИКЛ
  8. АЛГОРИТМ
  9. АЛГОРИТМ
  10. Алгоритм знакомства