Вычисление медианы Кемени - Задача исследования итогового ранжирования мнений группы экспертов с помощью медианы кемени
Если ответы экспертов - кластеризованные ранжировки, то вычисление медианы Кемени является задачей целочисленного программирования. Для ее нахождения используют различные алгоритмы дискретной математики, в частности, основанные на методе ветвей и границ, на разных подходах кластерного анализа. В настоящее время неизвестно ни одного точного алгоритма поиска множества всех медиан Кемени для заданного множества перестановок (ранжировок без связей), кроме полного перебора.
Однако существуют алгоритмы, разработанные российскими учеными Б. Г. Литваком [17], В. Н. Жихаревым [18].
Рассмотрим подход В. Н. Жихарева. Для практического использования вместо полного перебора и селекции множества всех медиан в множестве всех кластеризованных ранжировок (как он пишет - перестановок) В. Н. Жихарев предлагает эвристические алгоритмы [18], в которых исследует меньшие по количеству элементов множества - производные от совокупности экспертных ответов - и выделяет в них т. н. псевдомедианы в предположении, что псевдомедианы могут быть медианами. Псевдомедианы ищутся так же как медианы Кемени, только на выделенном множестве перестановок.
Псевдомедианой совокупности E экспертных перестановок в множестве V называется перестановка, pm(E, V), для которой сумма расстояний D(x, E) до элементов совокупности E принимает минимальное значение среди всех перестановок x множества V.
Жихарев использует также следующие понятия в пространстве G кластеризованных ранжировок (перестановок), которое рассматривается как граф (ребрами соединены перестановки, отличающиеся одной инверсией):
Сферой S(X, R) радиуса R с центром в точке (перестановке) X называется множество всех таких вершин (перестановок) y графа G, для которых выполняется условие D(X, y) = R.
Шаром B(X, R) радиуса R с центром в точке (перестановке) X называется множество всех таких вершин (перестановок) y графа G , для которых расстояние D(X, y) не превосходит R.
R - окрестностью B(V, R) множества перестановок V радиуса R называется объединение шаров радиуса R с центрами в точках Y множества V. В частности, B(V, 0) = V.
Границей (R - фронтом) S(V, R) R - окрестности B(V, R) множества перестановок V называется теоретико-множественная разность
B(V, R) - B(V, R - 1),
Причем S(V, 0) = V.
Центром C(V) множества V (центром минимальной окрестности) называется первое непустое по последовательности R = 0, 1, 2, ... пересечение всех шаров B(X, R) радиуса R с центрами во всех точках X множества V, а соответствующее минимальное значение R называется радиусом минимальной окрестности U(C(V), R), включающей в себя все элементы множества V.
Взвешенным (или смещенным) центром Cw(E) совокупности E называется первое непустое по последовательности R = 0, 1, 2, ... пересечение всех шаров B(X, [R/K(X)]) с центрами во всех точках X множества N(E) совокупности E, где K(X) - кратность элемента X в совокупности E, [R/K(X)] - целая часть рационального числа R/K(X).
Окрестность U(Cw(E), R) включает в себя все элементы множества N(E) совокупности E.
Используемые производные множества перестановок Жихарев строит путем нахождения центров множества ответов экспертов, далее алгоритмически специальным образом задаются сферы, шары, окрестности на данном множестве, тем самым ограничивая полный перебор на множестве всех перестановок экспертных ранжировок.
Дадим краткое описание алгоритмов В. Н. Жихарева.
Алгоритм 1.
- 1. Построить центр C(N(E)) множества N(E) совокупности E. 2. Найти множество всех псевдомедиан PM(E, C(N(E))).
Алгоритм 2.
- 1. Построить центр C(N(E)) множества N(E) совокупности E. 2. Построить окрестность U(C(N(E)), R), центра C(N(E)) минимального радиуса R, содержащую все элементы множества N(E). 3. Найти множество всех псевдомедиан PM(E, U(C(N(E)), R)).
Алгоритм 3.
- 1. Построить центр C(N(E)) множества N(E) совокупности E. 2. Построить шаровую окрестность B(E, R), произвольной точки E центра C(N(E)) минимального радиуса R, содержащую все элементы множества N(E). 3. Найти множество всех псевдомедиан PM(E, B(E, R)).
Алгоритм 4.
- 1. Построить смещенный центр Cw(E) совокупности E. 2. Найти множество всех псевдомедиан PM(E, Cw(E)).
Алгоритм 5.
- 1. Построить смещенный центр Cw(E) совокупности E. 2. Построить окрестность U(Cw(E), R) центра Cw(E) минимального радиуса R, содержащую все элементы множества N(E). 3. Найти множество всех псевдомедиан PM(E, U(Cw(E), R)).
Алгоритм 6.
- 1. Построить смещенный центр Cw(E) совокупности E экспертных ответов. 2. Построить шаровую окрестность B(Ew, R) произвольной точки Ew смещенного центра Cw(E) минимального радиуса R, содержащую все элементы множества N(E). 3. Найти множество всех псевдомедиан PM(E, B(Ew, R)).
Алгоритм 7.
- 1. Старт: N = N1 = N(E), R = 3, N(E)- совокупность экспертных ответов. 2. Операция "захвата":
Построить окрестность B(N, R), где R - радиус окрестности, построенной в каждой из точек N.
3. Операция селекции:
Найти множество всех псевдомедиан N1 = PM(E, B(N, R)).
4. Условие остановки. Сравнить N и N1. Если N = N1, то остановка, иначе переход к п.2.
В работе В. Н. Жихарева использовалось несколько моделей ответов экспертов. В наиболее общей модели 1: совокупность экспертных ответов формируется методом случайной неупорядоченной выборки с повторениями, при этом любая перестановка множества X с одинаковой вероятностью может быть выбрана в качестве экспертного ответа. В модели 2: локализованная совокупность экспертных ответов, т. е. все экспертные ответы лежат внутри шара с фиксированным радиусом и равновероятны. |В модели 3: центрированная и локализованная совокупность экспертных ответов, т. е. существует одна "истинная" и наиболее вероятная перестановка - центр шара. Вероятности выбора других перестановок совокупности зависят от расстояния до центра шара.
В результате численных экспериментов В. Н. Жихарев проводит сравнение множества псевдомедиан, найденных с помощью предложенных эвристических алгоритмов, с множеством медиан Кемени, найденным им путем полного перебора (табл. 2). Жирным шрифтом в таблице указано описание серии экспериментов методом Монте-Карло, которое состоит из набора характеристических параметров, а именно:
Номер модели совокупности экспертных ответов,
Количество объектов,
Количество экспертов,
Количество испытаний (тестов).
(Например: 1-5-5-1000).
В первых двух колонках табл. 2 указан порядковый номер и "условный" символ алгоритма, разработанного В. Н. Жихаревым. Используя поочередно каждый из предложенных алгоритмов, автор сравнивает количество найденных псевдомедиан с числом медиан Кемени, вычисленным методом полного перебора на множестве всех перестановок X. В третьей, четвертой и пятой колонках указаны проценты испытаний (тестов) для каждого типа алгоритмов, в которых удалось найти все медианы Кемени, некоторые или ни одной. В последней колонке указаны средние отношения времени работы каждого тестируемого эвристического алгоритма ко времени работы алгоритма полного перебора.
В. Н. Жихарев выделяет один из предложенных им эвристических алгоритмов (номер 7 в таблице) в качестве наиболее эффективного по количеству найденных медиан в условиях наиболее общей модели ответов экспертов (модель 1). Однако, как показывают данные последней колонки табл.2, алгоритм полного перебора в большинстве экспериментов работает более быстро.
Таблица 2. Сводная таблица результатов испытаний поиска медиан Кемени по алгоритмам В. Н.Жихарева
Номер алгоритма |
Символ алгоритма |
Найдены все медианы (% тестов) |
Найдены не все медианы (% тестов) |
Не найдено ни одной медианы (% тестов) |
Относительное быстродействие |
1-5-5-1000 | |||||
1 |
C |
23.7 |
13.7 |
62.6 |
3.9 |
2 |
U(C) |
99.5 |
0.2 |
0.3 |
0.00087 |
3 |
U(Ce) |
98. |
1.2 |
0.8 |
0.001 |
4 |
Cw |
24.7 |
14. |
61.3 |
3.78 |
5 |
U(Cw) |
99.5 |
0.2 |
0.3 |
1.23 |
6 |
U(Cwe) |
98. |
1.2 |
0.8 |
1.46 |
7 |
Move |
100. |
0 |
0 |
1.11 |
1-5-10-1000 | |||||
1 |
C |
7.4 |
38.1 |
54.5 |
1.7 |
2 |
U(C) |
99.3 |
0.7 |
0 |
0.001 |
3 |
U(Ce) |
94.2 |
5.7 |
0.1 |
0.0012 |
4 |
Cw |
7.7 |
38.3 |
54 |
1.6 |
5 |
U(Cw) |
99.3 |
0.7 |
0 |
0.69 |
6 |
U(Cwe) |
94.8 |
5.1 |
0.1 |
0.76 |
7 |
Move |
100. |
0 |
0 |
0.81 |
1-7-5-61 | |||||
1 |
C |
14.7541 |
8.19672 |
77.0492 |
4.02 |
2 |
U(C) |
100 |
0 |
0 |
0.0205 |
3 |
U(Ce) |
98.3607 |
1.63934 |
0 |
0.0257 |
4 |
Cw |
14.7541 |
8.19672 |
77.0492 |
4.04 |
5 |
U(Cw) |
100 |
0 |
0 |
1.43 |
6 |
U(Cwe) |
98.3607 |
1.63934 |
0 |
1.8 |
7 |
Move |
95.082 |
4.91803 |
0 |
11.1 |
1-6-5-500 | |||||
5 |
U(Cw) |
100 |
0 |
0.3 |
1.3 |
7 |
Move |
99.2 |
0.8 |
0 |
2.8 |
1-6-10-500 | |||||
5 |
U(Cw) |
99 |
1 |
0 |
2.63 |
7 |
Move |
100 |
0 |
0 |
3.26 |
2-6-10-500 | |||||
5 |
U(Cw) |
100 |
0 |
0 |
4.4 |
7 |
Move |
100 |
0 |
0 |
2.52 |
3-6-10-500 | |||||
5 |
U(Cw) |
100 |
0 |
0 |
2.3 |
7 |
Move |
100 |
0 |
0 |
2.4 |
В. Н. Жихарев считает, что метод полного перебора на современных компьютерах может быть достаточно эффективно применен для поиска всех медиан Кемени при относительно небольшом количестве экспертов (для числа объектов в перестановке вплоть до восьми и даже девяти). Описанные выше эвристические алгоритмы созданы для решения более сложных задач: выявления каких-либо закономерностей при изучении взаимного расположения медиан по отношению к экспертной совокупности или экспертному множеству.
К недостаткам предложенных методов вычисления медианы Кемени В. Н. Жихарев относит тот факт, что множество, построенное на первом этапе этих алгоритмов, может оказаться слишком большим - сравнимым по размерам (по числу лементов) со множеством всех перестановок, и тогда на втором этапе фактически осуществляется полный перебор перестановок. Это обстоятельство следует иметь в виду прежде всего в том случае, когда имеется сильный разброс в ответах экспертов и они приблизительно могут быть описаны моделью №1. В этом случае может оказаться целесообразным не вычислять медианы, а провести новую экспертизу с другим подбором объектов [18].
В работе Б. Г. Литвака [17] предложены два алгоритма вычисления медианы Кемени: точный и эвристический. Расстояние от произвольного ранжирования P до всех ранжирований P1, ..., Pm определяется как:
,
Где
.
Используется матрица потерь с элементами:
.
Поиск медианы Кемени эквивалентен отысканию упорядочивания строк и столбцов матрицы потерь, обладающей минимальной суммой наддиагональных элементов. Точный алгоритм Литвака строится на теореме о необходимом и достаточном условии транзитивности матрицы потерь, обладающей свойством Кондорсе. Ранжирование P обладает свойством Кондорсе, если любое подмножество альтернатив обладает альтернативой Кондорсе. Пусть матрица потерь построена для единственного ранжирования P. Если в упорядочивании P альтернатива предпочтительнее альтернативы, то. Если в матрице потерь, как только и, такая матрица называется транзитивной. Матрица потерь может быть нетранзитивна в случае непоследовательности ответов экспертов при парных сравнениях. Пусть ранжирования P1, ..., PM обладают альтернативой Кондорсе - это означает, что матрица потерь содержит строку такую, что. Благодаря свойству транзитивности (последовательности экспертов в своих выборах) после удаления некой альтернативы, альтернативой Кондорсе становится.
Точный алгоритм Литвака использует метод ветвей и границ, в нем предполагается последовательное фиксирование расположения части альтернатив (наилучших альтернатив Кондорсе и наименее предпочтительных альтернатив), определение верхней и нижней границ значений целевой функции на уменьшенном таким образом множестве ранжирований и отбрасывание заведомо бесперспективных при поиске медианы Кемени вариантов. Точный алгоритм Б. Г. Литвака, в частности, описан Д. А. Сумкиным (в коллективной монографии [19]).
Если ранжирования P1, ..., Pm не обладают свойством Кондорсе, то Литвак предлагает использовать разработанный им эвристический алгоритм поиска медианы Кемени. В этом алгоритме на первом этапе последовательно находятся минимумы из сумм:
, ,
После чего соответствующую минимальной сумме
Альтернативу ставят на первое место, вычеркивая ее из матрицы потерь. Далее аналогичные действия проводятся с уменьшенной матрицей потерь до тех пор, пока не получится ранжировка: . На втором этапе для полученной ранжировки последовательно проверяются соотношения: . Как только для некоторого K оно нарушено, альтернативы и меняются местами в новом ранжировании. Данный алгоритм описан, например, в работе польских авторов [20].
Недостатком подходов Б. Г. Литвака является то, что предложенные методы поиска могут найти лишь одну медиану из большого множества возможных, поэтому в общем случае они должны быть модифицированы.
В простейшем случае, представляет интерес подсчет итогового мнения комиссии экспертов только среди указанных экспертами ответов ("модифицированная" медиана Кемени, предложенная в [21]).
Похожие статьи
-
В работах [22, 14, 15] приведены результаты изучения свойств медианы Кемени, полученные с помощью расчетов по алгоритмам В. Н. Жихарева [18], описанным...
-
Разработаны разные способы поиска итогового ранжирования мнений группы экспертов, например Метод средних арифметических рангов, В котором каждому объекту...
-
Экспертные процедуры применяются во многих областях деятельности [1 - 3]. К таким областям относятся прежде всего менеджмент (особенно производственный...
-
1. Орлов А. И. Экспертные оценки // Заводская лаборатория. Диагностика материалов. 1996. Т.62. № 1. С.54-60. 2. Орлов А. И. Организационно-экономическое...
-
Пусть имеется конечное число объектов, которые будем обозначать натуральными числами 1, 2, 3, ..., K и называть "носителем". Под кластеризованной...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
Задача поиска маршрутов в графе (путей в орграфе)
Задача поиска маршрутов в графе (путей в орграфе) Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и. Правила. 1) Идя по произвольному...
-
Методы отбора выборок - Основы научных исследований
Известны три метода отборок выборок: случайный, систематический и комбинированный. В результате случайного отбора получается случайная выборка. Выборка...
-
Задание. Рассматривается вычислительная система состоящая из n вычислительных машин. Имеется n задач. Задана матрица T определяющая время решения i-й...
-
Найти при помощи метода ячеек значение интеграла , Где - область, ограниченная функциями . 2. Теоретическая часть Рассмотрим K-мерный интеграл вида: (1)...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ. ПРИМЕРЫ - Задача коммивояжера
Рассмотрим конкретный пример реализации метода ветвей и границ для решения задачи о коммивояжере. Итак, требуется найти легчайший простой основный...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
ПОСТАНОВКА ЗАДАЧИ - Задача коммивояжера
Пусть имеется п городов. Расстояния между любой парой городов (i, j) известны и составляют dij, где i=1, m; j=1, n; i?j. Если прямого маршрута...
-
Все генетические алгоритмы участвовали в двух группах тестов. В каждой группе исследовались различные наборы значений управляющих параметров МГА:...
-
Вывод, Список литературы - Применение матриц при решении экономических задач
Матричный статистика планирование хозрасчет Мы рассмотрели экономические задачи которые решали с помощью матриц. Использование матриц, как в науке, так и...
-
Основные понятия теории экономико-математического моделирования Кибернетический подход к исследованию экономико-математических систем Обычно...
-
Метод дихотомии требует менее всего итераций цикла для получения корней уравнения с заданной точностью. Если расчет ведется без помощи ЭВМ, то это...
-
Иногда необходимо управлять сложными комплексами взаимосвязанных работ, направленных на достижение определенных целей. Примерами таких комплексов в...
-
Планиметрические задачи Задача 1.Написать уравнения касательной и нормали к графику функциив данной точке, если: [3]. Решение. Уравнение касательной...
-
Условие задачи. Пусть имеются n кандидатов для выполнения этих работ. Назначение кандидата i на работу j связано с затратами CIj (i, j = 1,2,..., n)....
-
Ограничение чувствительность задача программирование Вариации правых частей ограничений приводят к изменению области допустимых решений ЗЛП, в действии...
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
-
Вариации коэффициентов целевой функции ЗЛП приводят к изменению направления вектора градиента. Так как при этом не затрагивается допустимое множество, то...
-
Решетки (структуры) - Формационные основы универсальных алгебр
Понятие решетки (пример 11) играет исключительно важную роль в изучении самых общих алгебр. И это, в первую очередь, связано с иным подходом в...
-
Задачи, связанные с поиском гамильтоновых циклов - Гамильтоновы циклы
В ряде отраслей промышленности возникает следующая задача планирования. Нужно произвести n продуктов, используя единственный тип аппаратуры. Аппарат...
-
Требования к современному эксперименту - Основы научных исследований
В данном курсе под физическим экспериментом будем понимать любое взаимодействие с внешними объектами, направленное на получение новой информации. Поэтому...
-
A 25 40 50 30 45 20 7 3 4 8 6 60 5 7 2 3 5 45 1 4 10 2 6 70 3 4 2 7 8 Допустим, стоимость доставки единицы груза из каждого пункта отправления в...
-
Некоторые особенности решения задач нелинейного программирования - Экономико-математические методы
Для решения ЗНП существенно знать: 1) выпукло или не выпукло множество допустимых решений задачи; 2) является ли целевая функция выпуклой или вогнутой...
-
В статье рассматриваются вопросы, связанные с совершенствованием процессов управления непрерывными ХТС. Предлагается возможность такой организации...
-
Задача регрессии. Метод наименьших квадратов Ищу функцию регрессии в виде (1*). Оценки коэффициентов нахожу с помощью Метода Наименьших Квадратов (МКВ),...
-
Генеральная совокупность и выборка - Основы научных исследований
Распределение случайной величины содержит всю информацию о ее статистических свойствах. Много ли нужно знать значений случайной величины, чтобы построить...
-
Как и каждый достаточно ярко выраженный класс экономико-математических моделей, совокупность моделей календарного планирования обладает рядом...
-
Метод наименьших квадратов - Основы научных исследований
Пусть проведен однофакторный эксперимент, в котором исследована зависимость У от Х . Установлено, что основные предпосылки регрессионного анализа...
-
Предмет статистики Многочисленные определения статистики как науки о количественной характеристике общественных и естественных явлений и процессов можно...
-
А) Углерод (С), кремний (Si), германий (Ge), олово (Sn), свинец (РЬ) - элементы 4 группы главной подгруппы ПСЭ. На внешнем электронном слое атомы этих...
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
-
МЕТОД РАНЖИРОВАНИЯ - Основы прогнозирования
Под ранжированием понимается расположения факторов, явлений, событий в порядке убывания или возрастания какого--либо присущего им свойства. Порядковый...
-
МЕТОДЫ ОТБОРА СПЕЦИАЛИСТОВ В ЭКСПЕРТНУЮ ГРУППУ - Основы прогнозирования
Проведение экспертизы начинается с создания специальной группы специалистов-организаторов опроса. Задачами группы являются выбор цели экспертизы,...
-
Второй раздел курсовой работы посвящен особенностям постановки и решения общей задачи линейного программирования, а именно, транспортной задаче (ТЗЛП)....
-
Формирование З -областей в матрице R осуществляется в процессе ее эволюционной модификации. Эволюционная модификация матрицы R производится путем...
Вычисление медианы Кемени - Задача исследования итогового ранжирования мнений группы экспертов с помощью медианы кемени