Помощь студентам в учебе
АГРЕГИРОВАНИЕ ПРЕДПОЧТЕНИЙ НА ОСНОВЕ ТОЧНОГО РЕШЕНИЯ ЗАДАЧИ О РАНЖИРОВАНИИ КЕМЕНИ
|
Введение 4
ГЛАВА 1 Алгоритм точного решения задачи о ранжировании Кемени .... 11
1.1Агрегирование предпочтений 11
1.2 Ранжирование и профиль предпочтений 12
1.2.1 Слабый порядок 13
1.2.2. Профиль предпочтения 16
1.2.3 Взвешенная турнирная матрица 19
1.3 Правила агрегирования предпочтений 20
1.3.1 Правило простого большинства 20
1.3.2 Правило Борда 22
1.3.3 Правило Кондорсе 23
1.3.4 Правило Кемени 26
1.4 Проблемы практического применения правила Кемени 29
1.4.1 АР-трудность задачи о ранжировании Кемени 30
1.4.2 Множественность решений 31
1.5 Т очный алгоритм нахождения всех ранжирований Кемени 33
Выводы к главе 1 41
ГЛАВА 2 Множественность решений задачи о ранжировании Кемени 43
2.1 Причины множественности 43
2.2 Предыдущие исследования множественности 44
2.3 Экспериментальные исследования транзитивности входного профиля50
2.3.1. Критерий транзитивности входного профиля 50
2.3.2. План экспериментов 51
2.3.3. Транзитивность входного профиля при различных m и n 54
2.3.4. Оценка вероятности транзитивного входного профиля 59
2.4 Транзитивность выходного профиля 65
Выводы к главе 2 68
ГЛАВА 3 Преобразование выходного профиля в единственное оптимальное решение 70
3.1 Взвешенный турнир выходного профиля 70
3.1.1 Матрица взвешенного турнира 70
3.1.2 Параметры взвешенного турнира 71
3.2 Построение правила свёртки 77
3.2.1 Характеризация выходного профиля ЗРК 77
3.2.2 Желательные свойства правила свёртки 79
3.2.3 Свёртка на основе выигрышей z{ 81
3.2.4 Свёртка с использованием общих рангов г. 82
3.2.5 Расстояние Кемени и итоговое ранжирование консенсуса 83
Выводы к главе 3 87
ГЛАВА 4 Практические аспекты агрегирования предпочтений на основе
правила Кемени 88
4.1 Две основные парадигмы применения правила Кемени 88
4.1.1 Измерение в многомерной порядковой шкале 88
4.1.2 Комплексирование интервалов агрегированием предпочтений. 89
4.2 Метод комплексирования интервальных данных IF&PA 90
4.2.1 Этапы метода IF&PA 90
4.2.2 Инранжирования 94
4.3 Свойства инранжирований и связанных с ними пространств 97
4.3.1 Пространства инранжирований 97
4.3.2 Мощность классов Ak 102
4.3.3 Порождающие инранжирования множества 103
Выводы к главе 4 107
Заключение 108
Список сокращений и обозначений 110
Список используемой литературы 114
Приложение А. Акты внедрения диссертационной работы 124
ГЛАВА 1 Алгоритм точного решения задачи о ранжировании Кемени .... 11
1.1Агрегирование предпочтений 11
1.2 Ранжирование и профиль предпочтений 12
1.2.1 Слабый порядок 13
1.2.2. Профиль предпочтения 16
1.2.3 Взвешенная турнирная матрица 19
1.3 Правила агрегирования предпочтений 20
1.3.1 Правило простого большинства 20
1.3.2 Правило Борда 22
1.3.3 Правило Кондорсе 23
1.3.4 Правило Кемени 26
1.4 Проблемы практического применения правила Кемени 29
1.4.1 АР-трудность задачи о ранжировании Кемени 30
1.4.2 Множественность решений 31
1.5 Т очный алгоритм нахождения всех ранжирований Кемени 33
Выводы к главе 1 41
ГЛАВА 2 Множественность решений задачи о ранжировании Кемени 43
2.1 Причины множественности 43
2.2 Предыдущие исследования множественности 44
2.3 Экспериментальные исследования транзитивности входного профиля50
2.3.1. Критерий транзитивности входного профиля 50
2.3.2. План экспериментов 51
2.3.3. Транзитивность входного профиля при различных m и n 54
2.3.4. Оценка вероятности транзитивного входного профиля 59
2.4 Транзитивность выходного профиля 65
Выводы к главе 2 68
ГЛАВА 3 Преобразование выходного профиля в единственное оптимальное решение 70
3.1 Взвешенный турнир выходного профиля 70
3.1.1 Матрица взвешенного турнира 70
3.1.2 Параметры взвешенного турнира 71
3.2 Построение правила свёртки 77
3.2.1 Характеризация выходного профиля ЗРК 77
3.2.2 Желательные свойства правила свёртки 79
3.2.3 Свёртка на основе выигрышей z{ 81
3.2.4 Свёртка с использованием общих рангов г. 82
3.2.5 Расстояние Кемени и итоговое ранжирование консенсуса 83
Выводы к главе 3 87
ГЛАВА 4 Практические аспекты агрегирования предпочтений на основе
правила Кемени 88
4.1 Две основные парадигмы применения правила Кемени 88
4.1.1 Измерение в многомерной порядковой шкале 88
4.1.2 Комплексирование интервалов агрегированием предпочтений. 89
4.2 Метод комплексирования интервальных данных IF&PA 90
4.2.1 Этапы метода IF&PA 90
4.2.2 Инранжирования 94
4.3 Свойства инранжирований и связанных с ними пространств 97
4.3.1 Пространства инранжирований 97
4.3.2 Мощность классов Ak 102
4.3.3 Порождающие инранжирования множества 103
Выводы к главе 4 107
Заключение 108
Список сокращений и обозначений 110
Список используемой литературы 114
Приложение А. Акты внедрения диссертационной работы 124
Актуальность темы. Агрегирование предпочтений - это классическая задача определения ранжирования консенсуса для заданного исходного профиля предпочтений, состоящего из m ранжирований, возможно, включая толерантности, n альтернатив (или кандидатов). Эта задача с конца XVIII века исследуется в основном в рамках теории голосования (или социального выбора).
Ранжирование консенсуса должно удовлетворять определенным естественным требованиям (правилам), обычно формулируемым в аксиоматической форме. Различные правила агрегирования предпочтений отличаются друг от друга с учетом их соответствия определенным аксиомам. Одним из наиболее аксиоматически обоснованных правил считается правило Кондорсе, основанное на парном сравнении альтернатив. Однако это правило может приводить к парадоксу н е- транзитивности Кондорсе. Разумным способом преодоления этой трудности является использование правила Кемени, которое позволяет найти такой линейный порядок альтернатив (ранжирование Кемени), что расстояние от него до исходн ого профиля предпочтений будет минимальным. Это расстояние Кемени определяется в терминах числа попарных несоответствий между ранжированиями.
Правило Кемени обладает положительными свойствами правила Кондорсе и не приводит к парадоксу, что позволяет рекомендовать его для применения в различных ситуациях агрегирования предпочтений, например, при многокритериальном (или групповом) принятии решений, в области искусственного интеллекта и, в частности, машинного обучения. Соответствующие методы используются для решения таких проблем, как краудсенсинг/лэйбелинг, анализ настроений, создание мета-поисковых систем и т.п.
Однако, для практического использования правила Кемени существуют два серьезных препятствия: (1) задача о ранжировании Кемени (ЗРК) является NP- трудной и (2) правило Кемени может приводить к множественным ранжированиям консенсуса.
NP-трудность означает, что вряд ли будет существовать алгоритм с полиномиальным временем (пропорциональным размерности n задачи) решения для правила Кемени. Этот факт требует разработки различных подходов для преодоления для нахождения оптимального решения за приемлемое время. Однако известны реализующие правило Кемени алгоритмы, обеспечивающие нахождение точного решения за время порядка нескольких секунд при размерности задачи до n < 20. Эта размерность вполне подходит для практических применений.
Множественность решений ЗРК означает, что ранжирований Кемени может быть слишком много. Хотя эти оптимальные решения, количество которых будем обозначать N, находятся на одном и том же минимальном расстоянии Кемени от т исходных ранжирований, они могут быть довольно далеки друг от друга. При определенных значениях т и n (особенно при малых и четных т > 4) значение N может достигать 107. При этом возникает хаосо-подобная ситуация, когда N >> т, и неопределенность после решения задачи значительно превышает исходную неопределенность.
Применение правила Кемени в агрегировании предпочтений требует пров едения систематических исследований и разработки основанных на них рекомендаций по преодолению указанных выше трудностей.
Целью диссертационной работы является разработка и экспериментальные исследования процедур агрегирования предпочтений на основе точного р е- шения задачи о ранжировании Кемени.
В связи с поставленной целью должны быть решены следующие задачи:
• анализ основных правил агрегирования предпочтений и исследование агрегирования предпочтений в форме правила Кемени и реализующего это правило точного алгоритма;
• проведение экспериментальных исследований транзитивно- сти/нетранзитивности входного профиля предпочтений и его связи с явлением множественности решений ЗРК;
• разработка правил преобразования множества оптимальных решений ЗРК в единственное итоговое оптимальное решение;
• исследование пространства слабых порядков при применении правила Кемени в методе комплексирования интервалов агрегированием предпочтений IF&PA
Методы исследования. Использованы методы теории голосования (социального выбора), математической статистики, комбинаторики, теории измерений и агрегирования предпочтений. Экспериментальные численные исследования проводились с использованием метода Монте-Карло с генерацией наборов индивидуальных входных профилей, состоящих из случайных ранжирований, элементы которых распределены по равномерному закону.
Достоверность полученных результатов диссертационной работы подтверждается совпадением с достаточной точностью аналитических расчетов и результатов численных экспериментов.
Научная новизна
1. Предложена стратегия получения итогового ранжирования консенсуса при применении правила Кемени, заключающаяся в нахождении всех ранжирований консенсуса, являющихся точными оптимальными решениями, достижимыми при размерности задачи п < 20, и нахождении для них единственного подходящего итогового ранжирования консенсуса.
2. Экспериментальные исследования фактора множественности, связанного с проявлением транзитивности/нетранзитивности входного профиля предпочтения, показали, что вероятность транзитивности значительно выше при чётных значениях т, чем при нечётных, и плавно уменьшается с ростом п, тогда как вероятность множественности резко увеличивается при уменьшении чётных значений т, но плавно увеличивается при уменьшении нечётных значений т.
3. Предложено правило свёртки всех N оптимальных решений задачи о ранжировании Кемени в точное единственное итоговое ранжирование: в итоговом ранжировании консенсуса альтернативы располагаются в порядке убывания строковых сумм, вычисленных для N-взвешенной турнирной матрицы выходного профиля; две альтернативы толерантны друг другу, если они имеют одинаковые строковые суммы.
4. При применении правила Кемени в методе комплексирования интервалов агрегированием предпочтений IF&PA введено новое понятие инражирования как слабого порядка, наведенного входными интервалами, которое появляется в результате ограничений, накладываемых на обычные ранжирования интервальным характером исходных данных; показано, что мощность пространства ин- ражирований определяется треугольным числом для заданного числа n дискретных элементов.
Практическая ценность работы. Результаты диссертационной работы могут быть использованы для реализации процедур агрегирования предпочтений и нахождения отношения консенсуса при принятии решений (например, при выборе цветовой модели для цветометрического анализа состава веществ), оценивании качества продукции и услуг, решении многокритериальных задач, и т.п. В задачах комплексирования интервалов агрегированием предпочтений результаты работы могут использоваться для обработки интервальных данных разной природы, в ч а- стности, для организации межлабораторных сличений, для установления значений фундаментальных констант, повышения точности оценок измеряемых величин и т.д.
Реализация и внедрение результатов работы. Результаты исследований использованы при выполнении НИР по гранту 18-19-00203 Российского научного фонда "Агрегирование предпочтений для решения задач обработки многомерных гетероскедастичных измерительных данных", 2018-2020 гг.
Результаты работы также используются: в научно-исследовательской лаборатории "Безопасность и электромагнитная совместимость радиоэлектронных средств" федерального государственного бюджетного образовательного учреждения высшего образования "Томский государственный университет систем управления и радиоэлектроники"; в лаборатории службы релейной защиты и испытаний электрооборудования ООО "Горсети" г. Томска и в учебном процессе в отделении автоматизации и робототехники Инженерной школы информационных технологий и робототехники ТПУ. Акты внедрения приложены к диссертационной работе.
Положения, выносимые на защиту
1. Предложенная стратегия получения итогового ранжирования консенсуса обеспечивает возможность применения правила Кемени для широкого круга практических задач агрегирования предпочтений с максимально возможной точностью.
2. Полученные оценки вероятности появления нетранзитивности входного профиля соответствуют утверждениям, что при нечетных m вероятность появления нетранзитивного профиля всегда больше или равна вероятности парадокса Кондорсе, а при четных m вероятность появления нетранзитивного профиля всегда меньше вероятности парадокса Кондорсе; эти оценки согласуются с известными аналитическими оценками вероятности альтернативы Кондорсе и оценками вероятности появления множественности решений ЗРК.
3. Предложенная процедура свёртки всех N оптимальных решений задачи о ранжировании Кемени в точное единственное итоговое ранжирование посредством вычисления строковых сумм для N-взвешенной турнирной матрицы выходного профиля, имеет естественное обоснование на основе правила Борда.
4. Применение правила Кемени в методе комплексирования интервалов агрегированием предпочтений IF&PA приводит к пространству инражирований, которое является подмножеством пространства всех слабых порядков с единственным символом строгого порядка.
Апробация результатов работы. Основные результаты диссертационной работы докладывались на следующих конференциях: XIV Международная научно-практическая конференция студентов, аспирантов и молодых ученых "Современные техника и технологии", г. Томск, 2008 г.; XV Международная научнопрактическая конференция студентов, аспирантов и молодых учёных "Молодёжь и современные информационные технологии", г. Томск, 2017 г.; XVI Международная научно-практическая конференция студентов, аспирантов и молодых ученых "Молодежь и современные информационные технологии" г. Томск, 2018 г.; II всероссийская научно-практическая конференция с международным участием им. В.В. Губарева "Интеллектуальный анализ сигналов, данных и знаний: методы и средства", г. Новосибирск, 2018 г.; XVII Международная научно-практическая конференция студентов, аспирантов и молодых учёных "Молодежь и современные информационные технологии", г. Томск, 2020 г.; XIV Всероссийская научная конференция молодых ученых "Наука. Технологии. Инновации", г. Новосибирск, 2020 г.; Международный симпозиум ТК1-ТК-7-ТК13-ТК18 ИМЕКО, г. Санкт- Петербург, 2019 г.
Публикации. Основные результаты исследований отражены в 11 публикациях: 5 статей в ведущих научных журналах и изданиях, рекомендуемых ВАК, все проиндексированы в базах данных Scopus и (или) Web of Science, из них две статьи в журналах квартиля Q1; 6 статей в сборниках трудов международных и российских конференций.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 101 наименования. Работа содержит 127 страницы основного текста, включая 33 рисунка и 29 таблиц.
Во введении обоснована актуальность темы диссертации, сформулирована цель исследований, определены решаемые задачи, указаны научная новизна и практическая ценность результатов работы.
В первой главе введены необходимые термины и обозначения, в частности понятия ранжирования (слабого порядка) как формы представления предпочтений; проведен анализ основных правил выбора ранжирования консенсуса для заданных m ранжирований n альтернатив; подробно рассмотрена процедура агрегирования предпочтений в форме правила Кемени, а также свойства матрицы входного профиля предпочтения; дано описание рекурсивного алгоритма ветвей и границ для точного решения задачи о ранжировании Кемени.
Во второй главе рассматриваются причины явления множественности. Обсуждаются результаты экспериментальных численных исследований транзитивности / нетранзитивности входного профиля предпочтения A(m, n) в зависимости от числа ранжирований (избирателей), числа альтернатив (кандидатов) и плотности толерантностей. Рассматриваются случаи нетранзитивности выходного профиля оптимальных решений B(V, n).
В третьей главе детально рассмотрен выходной профиль ЗРК, исследуются свойства взвешенной турнирной матрицы, построенной для выходного профиля; а также соответствующие понятия выигрыша, проигрыша и ранга. Формулируются правила преобразования выходного профиля в единственное оптимальное решение, т.е. правила свёртки. Обсуждаются справедливость и обоснованность предлагаемых правил свёртки на основе счета Борда и понятия отношения "между", заданного на ранжированиях.
В четвертой главе рассмотрены две основные парадигмы применения правила Кемени: (1) измерение в многомерной порядковой шкале и (2) комплексиро- вание интервалов агрегированием предпочтений. Основное внимание уделено рассмотрению процедуры комплексирования интервальных данных агрегиров а- нием предпочтений (IF&PA), которая оперирует "инранжированиями" - слабыми порядками, наведенными входными интервалами. Показано, что мощность пространства инражирований определяется треугольным числом для заданного числа n дискретных элементов. Исследованы мощности смежных подпространств слабых порядков.
Ранжирование консенсуса должно удовлетворять определенным естественным требованиям (правилам), обычно формулируемым в аксиоматической форме. Различные правила агрегирования предпочтений отличаются друг от друга с учетом их соответствия определенным аксиомам. Одним из наиболее аксиоматически обоснованных правил считается правило Кондорсе, основанное на парном сравнении альтернатив. Однако это правило может приводить к парадоксу н е- транзитивности Кондорсе. Разумным способом преодоления этой трудности является использование правила Кемени, которое позволяет найти такой линейный порядок альтернатив (ранжирование Кемени), что расстояние от него до исходн ого профиля предпочтений будет минимальным. Это расстояние Кемени определяется в терминах числа попарных несоответствий между ранжированиями.
Правило Кемени обладает положительными свойствами правила Кондорсе и не приводит к парадоксу, что позволяет рекомендовать его для применения в различных ситуациях агрегирования предпочтений, например, при многокритериальном (или групповом) принятии решений, в области искусственного интеллекта и, в частности, машинного обучения. Соответствующие методы используются для решения таких проблем, как краудсенсинг/лэйбелинг, анализ настроений, создание мета-поисковых систем и т.п.
Однако, для практического использования правила Кемени существуют два серьезных препятствия: (1) задача о ранжировании Кемени (ЗРК) является NP- трудной и (2) правило Кемени может приводить к множественным ранжированиям консенсуса.
NP-трудность означает, что вряд ли будет существовать алгоритм с полиномиальным временем (пропорциональным размерности n задачи) решения для правила Кемени. Этот факт требует разработки различных подходов для преодоления для нахождения оптимального решения за приемлемое время. Однако известны реализующие правило Кемени алгоритмы, обеспечивающие нахождение точного решения за время порядка нескольких секунд при размерности задачи до n < 20. Эта размерность вполне подходит для практических применений.
Множественность решений ЗРК означает, что ранжирований Кемени может быть слишком много. Хотя эти оптимальные решения, количество которых будем обозначать N, находятся на одном и том же минимальном расстоянии Кемени от т исходных ранжирований, они могут быть довольно далеки друг от друга. При определенных значениях т и n (особенно при малых и четных т > 4) значение N может достигать 107. При этом возникает хаосо-подобная ситуация, когда N >> т, и неопределенность после решения задачи значительно превышает исходную неопределенность.
Применение правила Кемени в агрегировании предпочтений требует пров едения систематических исследований и разработки основанных на них рекомендаций по преодолению указанных выше трудностей.
Целью диссертационной работы является разработка и экспериментальные исследования процедур агрегирования предпочтений на основе точного р е- шения задачи о ранжировании Кемени.
В связи с поставленной целью должны быть решены следующие задачи:
• анализ основных правил агрегирования предпочтений и исследование агрегирования предпочтений в форме правила Кемени и реализующего это правило точного алгоритма;
• проведение экспериментальных исследований транзитивно- сти/нетранзитивности входного профиля предпочтений и его связи с явлением множественности решений ЗРК;
• разработка правил преобразования множества оптимальных решений ЗРК в единственное итоговое оптимальное решение;
• исследование пространства слабых порядков при применении правила Кемени в методе комплексирования интервалов агрегированием предпочтений IF&PA
Методы исследования. Использованы методы теории голосования (социального выбора), математической статистики, комбинаторики, теории измерений и агрегирования предпочтений. Экспериментальные численные исследования проводились с использованием метода Монте-Карло с генерацией наборов индивидуальных входных профилей, состоящих из случайных ранжирований, элементы которых распределены по равномерному закону.
Достоверность полученных результатов диссертационной работы подтверждается совпадением с достаточной точностью аналитических расчетов и результатов численных экспериментов.
Научная новизна
1. Предложена стратегия получения итогового ранжирования консенсуса при применении правила Кемени, заключающаяся в нахождении всех ранжирований консенсуса, являющихся точными оптимальными решениями, достижимыми при размерности задачи п < 20, и нахождении для них единственного подходящего итогового ранжирования консенсуса.
2. Экспериментальные исследования фактора множественности, связанного с проявлением транзитивности/нетранзитивности входного профиля предпочтения, показали, что вероятность транзитивности значительно выше при чётных значениях т, чем при нечётных, и плавно уменьшается с ростом п, тогда как вероятность множественности резко увеличивается при уменьшении чётных значений т, но плавно увеличивается при уменьшении нечётных значений т.
3. Предложено правило свёртки всех N оптимальных решений задачи о ранжировании Кемени в точное единственное итоговое ранжирование: в итоговом ранжировании консенсуса альтернативы располагаются в порядке убывания строковых сумм, вычисленных для N-взвешенной турнирной матрицы выходного профиля; две альтернативы толерантны друг другу, если они имеют одинаковые строковые суммы.
4. При применении правила Кемени в методе комплексирования интервалов агрегированием предпочтений IF&PA введено новое понятие инражирования как слабого порядка, наведенного входными интервалами, которое появляется в результате ограничений, накладываемых на обычные ранжирования интервальным характером исходных данных; показано, что мощность пространства ин- ражирований определяется треугольным числом для заданного числа n дискретных элементов.
Практическая ценность работы. Результаты диссертационной работы могут быть использованы для реализации процедур агрегирования предпочтений и нахождения отношения консенсуса при принятии решений (например, при выборе цветовой модели для цветометрического анализа состава веществ), оценивании качества продукции и услуг, решении многокритериальных задач, и т.п. В задачах комплексирования интервалов агрегированием предпочтений результаты работы могут использоваться для обработки интервальных данных разной природы, в ч а- стности, для организации межлабораторных сличений, для установления значений фундаментальных констант, повышения точности оценок измеряемых величин и т.д.
Реализация и внедрение результатов работы. Результаты исследований использованы при выполнении НИР по гранту 18-19-00203 Российского научного фонда "Агрегирование предпочтений для решения задач обработки многомерных гетероскедастичных измерительных данных", 2018-2020 гг.
Результаты работы также используются: в научно-исследовательской лаборатории "Безопасность и электромагнитная совместимость радиоэлектронных средств" федерального государственного бюджетного образовательного учреждения высшего образования "Томский государственный университет систем управления и радиоэлектроники"; в лаборатории службы релейной защиты и испытаний электрооборудования ООО "Горсети" г. Томска и в учебном процессе в отделении автоматизации и робототехники Инженерной школы информационных технологий и робототехники ТПУ. Акты внедрения приложены к диссертационной работе.
Положения, выносимые на защиту
1. Предложенная стратегия получения итогового ранжирования консенсуса обеспечивает возможность применения правила Кемени для широкого круга практических задач агрегирования предпочтений с максимально возможной точностью.
2. Полученные оценки вероятности появления нетранзитивности входного профиля соответствуют утверждениям, что при нечетных m вероятность появления нетранзитивного профиля всегда больше или равна вероятности парадокса Кондорсе, а при четных m вероятность появления нетранзитивного профиля всегда меньше вероятности парадокса Кондорсе; эти оценки согласуются с известными аналитическими оценками вероятности альтернативы Кондорсе и оценками вероятности появления множественности решений ЗРК.
3. Предложенная процедура свёртки всех N оптимальных решений задачи о ранжировании Кемени в точное единственное итоговое ранжирование посредством вычисления строковых сумм для N-взвешенной турнирной матрицы выходного профиля, имеет естественное обоснование на основе правила Борда.
4. Применение правила Кемени в методе комплексирования интервалов агрегированием предпочтений IF&PA приводит к пространству инражирований, которое является подмножеством пространства всех слабых порядков с единственным символом строгого порядка.
Апробация результатов работы. Основные результаты диссертационной работы докладывались на следующих конференциях: XIV Международная научно-практическая конференция студентов, аспирантов и молодых ученых "Современные техника и технологии", г. Томск, 2008 г.; XV Международная научнопрактическая конференция студентов, аспирантов и молодых учёных "Молодёжь и современные информационные технологии", г. Томск, 2017 г.; XVI Международная научно-практическая конференция студентов, аспирантов и молодых ученых "Молодежь и современные информационные технологии" г. Томск, 2018 г.; II всероссийская научно-практическая конференция с международным участием им. В.В. Губарева "Интеллектуальный анализ сигналов, данных и знаний: методы и средства", г. Новосибирск, 2018 г.; XVII Международная научно-практическая конференция студентов, аспирантов и молодых учёных "Молодежь и современные информационные технологии", г. Томск, 2020 г.; XIV Всероссийская научная конференция молодых ученых "Наука. Технологии. Инновации", г. Новосибирск, 2020 г.; Международный симпозиум ТК1-ТК-7-ТК13-ТК18 ИМЕКО, г. Санкт- Петербург, 2019 г.
Публикации. Основные результаты исследований отражены в 11 публикациях: 5 статей в ведущих научных журналах и изданиях, рекомендуемых ВАК, все проиндексированы в базах данных Scopus и (или) Web of Science, из них две статьи в журналах квартиля Q1; 6 статей в сборниках трудов международных и российских конференций.
Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 101 наименования. Работа содержит 127 страницы основного текста, включая 33 рисунка и 29 таблиц.
Во введении обоснована актуальность темы диссертации, сформулирована цель исследований, определены решаемые задачи, указаны научная новизна и практическая ценность результатов работы.
В первой главе введены необходимые термины и обозначения, в частности понятия ранжирования (слабого порядка) как формы представления предпочтений; проведен анализ основных правил выбора ранжирования консенсуса для заданных m ранжирований n альтернатив; подробно рассмотрена процедура агрегирования предпочтений в форме правила Кемени, а также свойства матрицы входного профиля предпочтения; дано описание рекурсивного алгоритма ветвей и границ для точного решения задачи о ранжировании Кемени.
Во второй главе рассматриваются причины явления множественности. Обсуждаются результаты экспериментальных численных исследований транзитивности / нетранзитивности входного профиля предпочтения A(m, n) в зависимости от числа ранжирований (избирателей), числа альтернатив (кандидатов) и плотности толерантностей. Рассматриваются случаи нетранзитивности выходного профиля оптимальных решений B(V, n).
В третьей главе детально рассмотрен выходной профиль ЗРК, исследуются свойства взвешенной турнирной матрицы, построенной для выходного профиля; а также соответствующие понятия выигрыша, проигрыша и ранга. Формулируются правила преобразования выходного профиля в единственное оптимальное решение, т.е. правила свёртки. Обсуждаются справедливость и обоснованность предлагаемых правил свёртки на основе счета Борда и понятия отношения "между", заданного на ранжированиях.
В четвертой главе рассмотрены две основные парадигмы применения правила Кемени: (1) измерение в многомерной порядковой шкале и (2) комплексиро- вание интервалов агрегированием предпочтений. Основное внимание уделено рассмотрению процедуры комплексирования интервальных данных агрегиров а- нием предпочтений (IF&PA), которая оперирует "инранжированиями" - слабыми порядками, наведенными входными интервалами. Показано, что мощность пространства инражирований определяется треугольным числом для заданного числа n дискретных элементов. Исследованы мощности смежных подпространств слабых порядков.
1. Рассмотрены две основные парадигмы применения правила Кемени: измерение в многомерной порядковой шкале и комплексирование интервалов агрегированием предпочтений. Основное внимание уделено рассмотрению процедуры комплексирования интервальных данных агрегированием предпочтений (IF&PA), которая преобразует заданные m исходных интервалов на вещественной числовой оси в "инражирования", которые являются частным случаем отношения слабого порядка (или ранжирования) на множестве n дискретных значений, принадлежащих к этим интервалам.
2. Введено новое понятие инражирования как слабого порядка, наведенного входными интервалами, которое появляется в результате ограничений, накладываемых на обычные ранжирования интервальным характером исходных данных.
3. Исследованы свойства пространства инранжирований с точки зрения комбинаторной теории. Показано, что пространство инражирований является подмножеством пространства всех слабых порядков с единственным символом строгого порядка. Получено выражение для расчета общего числа порождающих строгих порядков для всех возможных инранжирований заданной мощности для любого n.
4. Показано, что мощность пространства инражирований определяется треугольным числом для заданного числа n дискретных элементов. Также рассматриваются мощности других смежных пространств.
Заключение
1. Предложена стратегия получения итогового ранжирования консенсуса при применении правила Кемени, заключающаяся в нахождении всех ранжирований консенсуса, являющихся точными оптимальными решениями, достижимыми при размерности задачи п < 20, и нахождении для них единственного подходящего итогового ранжирования консенсуса. Стратегия обеспечивает возможность применения правила Кемени для широкого круга практических задач агрегирования предпочтений с максимально возможной точностью.
2. Экспериментальные исследования фактора множественности, связанного с проявлением транзитивности/нетранзитивности входного профиля предпочтения, показали, что вероятность транзитивности значительно выше при четных значениях т, чем при нечетных, и плавно уменьшается с ростом п, тогда как вероятность множественности резко увеличивается при уменьшении чётных значений т, но плавно увеличивается при уменьшении нечётных значений т. Полученные оценки согласуются с известными аналитическими расчетами.
3. Предложено правило свёртки всех N оптимальных решений задачи о ранжировании Кемени в точное единственное итоговое ранжирование: в итоговом ранжировании консенсуса альтернативы располагаются в порядке убывания строковых сумм, вычисленных для N-взвешенной турнирной матрицы выходного профиля; две альтернативы толерантны друг другу, если они имеют одинаковые строковые суммы. Предложенная процедура свёртки имеет естественное обоснование на основе правила Борда.
4. В рамках применения правила Кемени в методе комплексирования интервалов агрегированием предпочтений IF&PA введено новое понятие инражирования; показано, что мощность пространства инражирований определяется треугольным числом для заданного числа п дискретных элементов.
5. Результаты диссертационной работы были использованы при выполнении НИР по гранту РНФ 18-19-00203, а также в научно-исследовательской лаборатории "Безопасность и электромагнитная совместимость радиоэлектронных средств" Томского государственного университета систем управления и радиоэлектроники; в лаборатории службы релейной защиты и испытаний электрооборудования ООО "Горсети" г. Томска; в отделении автоматизации и робототехники Инженерной школы информационных технологий и робототехники ТПУ.
2. Введено новое понятие инражирования как слабого порядка, наведенного входными интервалами, которое появляется в результате ограничений, накладываемых на обычные ранжирования интервальным характером исходных данных.
3. Исследованы свойства пространства инранжирований с точки зрения комбинаторной теории. Показано, что пространство инражирований является подмножеством пространства всех слабых порядков с единственным символом строгого порядка. Получено выражение для расчета общего числа порождающих строгих порядков для всех возможных инранжирований заданной мощности для любого n.
4. Показано, что мощность пространства инражирований определяется треугольным числом для заданного числа n дискретных элементов. Также рассматриваются мощности других смежных пространств.
Заключение
1. Предложена стратегия получения итогового ранжирования консенсуса при применении правила Кемени, заключающаяся в нахождении всех ранжирований консенсуса, являющихся точными оптимальными решениями, достижимыми при размерности задачи п < 20, и нахождении для них единственного подходящего итогового ранжирования консенсуса. Стратегия обеспечивает возможность применения правила Кемени для широкого круга практических задач агрегирования предпочтений с максимально возможной точностью.
2. Экспериментальные исследования фактора множественности, связанного с проявлением транзитивности/нетранзитивности входного профиля предпочтения, показали, что вероятность транзитивности значительно выше при четных значениях т, чем при нечетных, и плавно уменьшается с ростом п, тогда как вероятность множественности резко увеличивается при уменьшении чётных значений т, но плавно увеличивается при уменьшении нечётных значений т. Полученные оценки согласуются с известными аналитическими расчетами.
3. Предложено правило свёртки всех N оптимальных решений задачи о ранжировании Кемени в точное единственное итоговое ранжирование: в итоговом ранжировании консенсуса альтернативы располагаются в порядке убывания строковых сумм, вычисленных для N-взвешенной турнирной матрицы выходного профиля; две альтернативы толерантны друг другу, если они имеют одинаковые строковые суммы. Предложенная процедура свёртки имеет естественное обоснование на основе правила Борда.
4. В рамках применения правила Кемени в методе комплексирования интервалов агрегированием предпочтений IF&PA введено новое понятие инражирования; показано, что мощность пространства инражирований определяется треугольным числом для заданного числа п дискретных элементов.
5. Результаты диссертационной работы были использованы при выполнении НИР по гранту РНФ 18-19-00203, а также в научно-исследовательской лаборатории "Безопасность и электромагнитная совместимость радиоэлектронных средств" Томского государственного университета систем управления и радиоэлектроники; в лаборатории службы релейной защиты и испытаний электрооборудования ООО "Горсети" г. Томска; в отделении автоматизации и робототехники Инженерной школы информационных технологий и робототехники ТПУ.
