Курсовая работа: Модель экспертной оценки
3. Математические методы решения
В предыдущем разделе были описанные методы подсчета глазков и основные требования к ним. Сравним эти методы. Как было отмечено, найлегшим среди них, но и наихудшим, есть правило относительного большинства. Можно убедиться, что в действительности оно противореччит мнению большинства. Поэтому оно не может быть выбрано для компьютерной реализации. Как Борда, так и Кондорсе заметили, что правило относительного большинства может приводить к избранию плохого кандидата, точнее такого кандидата, что в парном сравнении по правилу большинства проигрывает любому другому кандидату.
Для того, чтобы перебороть этот изъян, Кондорс и Борде предложили отказаться от правила относительного большинства, причем каждый из них предложил свое правило вместо данного. Кондорс предложил выбирать кандидата, который побеждает любого другого кандидата в парном сравнении, если такой победитель по Кондорсу существует. Борде предложил приписать очко каждому кандидату, который линейно растет в зависимости от его ранга в преимуществе избирателя. Потом он предложил избрать кандидата, который получил наибольшее суммарное количество очков у всех избирателей. Эти две идеи порождают два больше всего важных семейств правил голосования.
Результаты этих правил голосования могут сильно отличаться по свойствам. Одним из таких свойств есть аксиома монотонности. Правило голосование называется монотонным, если кандидат остается избранным при усилении его поддержки (то есть когда относительная позиция данного кандидата в чьих-то преимуществах улучшается, а относительные позиции других кандидатов не изменяются). Все методы подсчета глазков являются монотонными, но некоторые известные методы, что возникают из подсчета глазков, не являются такими. Примерами таких правил служит очень популярное правило относительного большинства с выбыванием и метод альтернативних голосов.
Есть две аксиомы, которые приводят к критике зажиточных по Кондорсе правил (поскольку данные правила нарушают эти аксиомы). С другой стороны, на этих аксиомах основана характеризация метода подсчета глазков. Эти аксиомы сравнивают кандидатов, избранных разнообразными группами избирателей. Они называются свойствами пополнения и участия. Пополнение значит, что если две группы избирателей, которые не пересекаются, (например, сенат и палата представителей) избирают того же кандидата а, то объединение этих двух избирательных органов подтвердит избрание а. Участие значит, что избиратель не может выиграть, воздерживаясь от голосования, в сравнении с возможностью принимать участие в голосовании и выразить свои преимущества. Любое зажиточное по Кондорсе правило нарушает обе этих аксиомы. В противовес этому правила подсчету очков характеризуются свойством пополнения (теорема Янга) и удовлетворяют аксиоме участия. Теорема Янга в настоящее время является самым существенным доказательством в поддержку методов подсчета очков, в частности системы очков Борда.
Зажиточные по Кондорсу правила голосования все же чрезвычайно популярны, в частности, благодаря простоте доведения парного сравнения по правилу большинства. Соответствующий класс зажиточных по Кондорсу методов основан на последовательных сравнениях по правилу большинства. Законопроект и многочисленные поправки к нему в конгрессе США голосуются именно таким способом. Известен метод последовательного исключения может нарушать условие оптимума по Парето. Другие методы, основанные на бинарных деревьях парных сравнений по правилу большинства, противоречат аксиоме монотонности. Наиболее простое правило, которое основано на последовательном сравнении и является оптимальным по Парето и монотонным, называется многоэтапным методом исключения. При использовании этого метода нужно меньше парных сравнений, чем в других, концептуально более простых методах, например в правиле Копленда. По последнему правилу избирается тот, кто выигрывает большинство парных дуэлей. Таким образом, голосование, основанное на последовательных парных сравнениях, может удовлетворять больше всего важным аксиоматическим требованиям, но только в том случае, если мы аккуратно выберем эту последовательность.
Правила Борда, относительного большинства и антибольшинства являют собой примеры правил голосования с подсчетом очков. Однако правило антибольшинства явно не монотонно, а правило относительного большинства – несправедливое.
Победитель Борда не может быть наихудших по Кондорсу, так как он является кандидатом, который имеет наивысший средний балл. По этому правилу всегда находятся оптимальный по Парето победитель или их множественное число. Примерами зажиточных по Кондорсу правил являются правила Копленда и Симпсона. Так же, как и правило Борда или любой другой метод подсчета очков, эти правила выбирают для каждого профиля подмножество победителей, которое может состоять из нескольких кандидатов, которые получили одинаковую оценку.
Как уже было отмечено, правила голосования должны быть монотонные, оптимальные по Парето, анонимные и нейтральные. Все правила голосования с подсчетом очков, кроме правила антибольшинства, оптимальны по Парето, монотонные, анонимные и нейтральные, если мы не указываем, что делать при равенстве очков. Кроме того, правила голосования должны удовлетворять аксиоме участия и пополнения. Метод Борда относится к этим правилам (это было показано в предыдущем разделе).
Правила Борда и Копленда, как отмечает Мулен, опираясь на практику, не очень части приводят к равенству очков, потому в этом ракурсе является наилучшими. Однако методы Кондорсе, к которым относится и правило Копленда, для некоторых профилей может не удовлетворять аксиоме участия.
Следующей группой правил являются правила, основанные на последовательном исключении за методом подсчета очков (относительное большинство с выбыванием, метод альтернативных голосов). Однако эти правила, как и любые другие методы, с выбыванием кандидатов нарушают свойство монотонности для некоторых профилей.
Метод ривнобижного исключения выбирает оптимальный за Парето результат в случае, когда при бинарных выборах нет ривностей. Однако если равенству возможные, то оптимум за Парето может нарушаться. Невзирая на выше перечисленные трудности, возможность за Кондорсе, широко известная в качестве демократического принципа, в то время как правило Борда "скрывает" настоящие симпатии избирателей за математической формулой. К зажиточным по Кондорсу правилам относят также следующие методы голосования:
а) голосование с последовательным исключением. При очевидных причинах это правило не является нейтральным и оптимальным по Парето, так как порядок исключений влияет на результат голосования. Определяя повестку дня, председатель фактически контролирует процесс выборов. Однако это правило достаточно широко используется Конгрессом США;
б) правило равномерного исключения. Оно порождает дерево без повторных исключений и требует проведения целого ряда мажоритарных турниров. Как было доказано в предыдущем разделе, бинарное дерево может дать оптимальное по Парето правило голосование только в более сложном случае, чем безповторне дерево. Также может нарушаться монотонность;
в) дерево многоэтапных исключений. Этот метод обеспечивает проведение наполовину меньшего количества мажоритарных турниров, чем метод Копленда. Оно имеет большой размер. Кандидатам, возможно, нужно принимать участие в дуэлях с тем же оппонентом по нескольку раз. Однако его алгоритм является достаточно простым. Дерево многоэтапного исключения порождает оптимальный за Парето и монотонный метод голосования. Всегда находится единственный победитель, а не множественное число. Однако этот метод порождает все трудности, которые связаны с использованием бинарных деревьев.
Таким образом, была проведена сравнительная характеристика всех методов голосования большинством голосов с исключением случаев безразличия и представления неправдивой информации.
Среди зажиточных по Кондорсу правил голосования мы обнаружили три метода, которые удовлетворяют основным требованиям оптимума по Парето, анонимности и монотонности: множественное число победителей по Копленду, множественное число победителей по Симпсону и дерево многоэтапного исключения. Среди методов подсчета очков наилучшим оказался метод определения победителя по Борду. Зажиточные по Кондорсу правила примененные на парном сравнении кандидатов по правилу относительного большинства. Для рядового избирателя они являются наиболее понятными.
Правило Борда удовлетворяет аксиоме участия и пополнения, но скрывает за математической формулой настоящие преимущества избирателей.
Для программной реализации выберем один из методов Копленда как самый простой и для сравнения определим победителя за Борда.
Приведем еще раз правила Копленда и Борда для того, чтобы перейти к формулировке алгоритма программы.
Правило Борда. Каждый избиратель сообщает свои преимущества, ранжируя р кандидатов от лучшего к худшему (безразличность запрещается). Кандидат не получает очков за последнее место, получает одно очко за предпоследнее и так далее, получает р-1 очков за первое место. Побеждает кандидат с наибольшей суммой очков. Он называется победителем по Борду.
Правило Копленда. Сравним кандидата а с любым другим кандидатом х. Начислим ему +1, если для большинства а лучше за х, -1, если для большинства х лучше за а, и 0 при равенстве. Суммируя общее количество очков по всем х, х¹а получаем оценку Копленда для а. Избирается кандидат, названный победителем по Копленду, с наивысшей из таких оценок.
Считаем, что входными данными задачи является уже сгруппированная информация: сформированные группы избирателей с одинаковыми в каждой группе рангами преимуществ. Однако допускается и занесение информации каждым избирателем отдельно.
4. Описание алгоритма
В данном разделе наводятся алгоритмы для нахождения победителей выборов. Для определения победителей Борда и Копленда воспользуемся непосредственно приведенными выше правилами, то есть реализуем их программно. Сложность алгоритмов, описанных ниже, прямо пропорциональна количеству групп избирателей и количества кандидатов, что еще раз подтверждает принадлежность данной задачи к Р-типу.
4.1 Определение победителя Борда
Для нахождения оценок Борда кандидаты ранжируются, то есть за каждое место в шкале избирателей кандидат получает определенное количество баллов.
Далее эти баллы суммируются.
Введем следующие переменные.
Пусть М – количество кандидатов;
S – количество групп избирателей;
Nаme[M] – массив имен избирателей;
Rаng[1..M, 1..S] – профиль преимуществ;
Many[S] – количество избирателей в каждой группе;
Bord[M] – массив оценок кандидатов.
Рассматриваем отдельно каждую группу избирателей. Для этой группы кандидат получает оценку [количество избирателей many[i]]*([количество кандидатов M] – [текущее значение счетчика j]). Найденная оценка добавляется к предыдущей. Алгоритм продолжает работу до тех пор, пока не будут рассмотрены все группы избирателей (i=S).
По правилу Борда получаем следующий алгоритм для нахождения оценок Борда.
Рис. 4.1 Алгоритм нахождения оценок Борда.
Рис. 4.2 Алгоритм нахождения оценок Копленда (начало)
4.2 Нахождение оценки Копленда
Для нахождения оценки Копленда кроме выше приведенных используем следующие переменные: Kopl[M] – массив оценок Копленда; Vybor1, vybor2 – вспомогательные переменные; используются для пересмотра имен кандидатов из массива имен name.
Сравнение проходит следующим образом.
Переменной vybor1 присваиваем значение имени первого кандидата из множественного числа имен name (contrl=1), а vybor2 – следующее (k=contrl+1). Если vybor1 находится выше, чем vybor2, в преимуществах избирателей всех групп, то к оценке Копленда (kopl[contrl]) кандидата vybor1 добавляется глазок, а vybor2 (kopl[k]) – отнимается и наоборот. Дальше переменной vybor2 присваивается следующее значение из массива имен (k=k+1), и процедура сравнения опять повторяется. Цикл продолжается до тех пор, пока не исчерпаются имена в списке кандидатов.
После этого переменной vybor1 присваивается второе имя из списка кандидатов (contrl=contrl+1), а vybor2 – третья. Опять проходит цикл по переменной vybor2. Цикл по переменной vybor1 заканчивается тогда, когда будут пересмотрены все кандидаты.
Получаем следующий алгоритм нахождения оценки Копленда.
Рис. 4.3 Алгоритм нахождения оценок Копленда (конец)
4.3 Алгоритм определения победителя за правилами Борда или Копленда
Как можно было увидеть, победителем по Борду (Копленду) является кандидат с наивысшей суммой очков. Поэтому процесс его определения является одинаковым для обоих случаев, и я его объединила одним алгоритмом. Как известно, правила Копленда и Борда порождают множественное число решений. Для нахождения победителя используем следующие переменные: K – количество победителей; Max – оценка победителей; Hl[M] – массив номеров победителей.
Сначала массив номеров победителей заполняем нулями.
Массивы оценок Копленда и Борда (kopl и bord) заменим формальным массивом v[M].
После того, как мы нашли оценки для кандидатов (массивы kopl и bord), среди них ищем максимальную (max). Дальше отбираем кандидатов, оценка которых равняется max (их номера из массива name заносятся в массив hl), и считаем количество победителей (k).
Пересматриваем заполненный массив hl. Если в нем только первое значение отличающееся от нуля, то значит, что мы нашли единственного победителя, и, следовательно, сохранили условие нейтральности.
В другом случае просматриваем те значения имен кандидатов (массив name), номера которых встречаются в массиве hl. Отобраны имена кандидатов упорядочиваем по списку. Победителем становится тот, имя которого находится первым в данном списке.
В данном случае условие нейтральности не сохраняется.
Мы получили следующий алгоритм.
Рис. 4.4 Алгоритм определения победителя (начало).
Рис. 4.5. Алгоритм определения победителя (конец).
5. Описание программы
5.1 Выбор технологии программирования
Наиболее распространенными парадигмами программирования, которые к тому же могут быть использованы в данной курсовой работе, являются парадигмы процедурного и объектно-ориентированного программирования.
Парадигма процедурного программирования больше всего широко распространена среди существующих словно программирование (например, Си и Паскаль). Здесь явно выделяют два вида разнообразных сущностей:
1) процедуры, которые исполняют активную роль, то есть представляются тем, которое задает поведение (функционирование) программы;
2) данные, что исполняют пассивную роль, то есть представляют тем, которое прорабатывается средством, продиктованным процедурами. Возможность составлять процедуры из команд (операторов) и вызывать их является ключом данной парадигмы. Особенностью этой парадигмы являются "боковые эффекты", которые возникают в тех случаях, когда разнообразные процедуры, которые используют общие данные, независимо их изменяют.
В процедурной парадигме активная роль в организации поведения уделяется процедурам, а не данным; причем процедура активизируется вызовом. Подобные средства задания поведения удобны для описаний детерминированной последовательности действий или одного процесса, или нескольких, но строго взаимозависимых процессов. При использовании программирования, ориентированного на данные, активную роль играют данные, а не процедуры. Здесь со структурами активных данных связывают некоторые действия (процедуры), которые активизируются тогда, когда осуществляется доступ к этим данным. Некоторые специалисты называют это средство активации действий "демонами". Программирование, ориентированное на данные, позволяет организовать поведение мало зависимых процессов, что тяжело реализовать в процедурной парадигме. Имела зависимость процессов значит, что они могут рассматриваться и программироваться отдельно. Однако при использовании парадигмы, управляемой данными, эти независимо запрограммированные процессы могут взаимодействовать между собой без их изменения (то есть без перепрограммирования). Парадигма объектного программирования в отличие от процедурной парадигмы не разделяет программу на процедуры и данные. Здесь программа организуется вокруг сущностей, названных объектами, что включают локальные процедуры (методы) и локальные данные (переменные). Поведение (функционирование) в этой парадигме организуется путем пересылки сообщений между объектами. Объъект, получив сообщение, осуществляет его локальную интепретацию, базируясь на локальных процедурах и данных. Такой подход позволяет описывать сложные системы наиболее естественным путем. Особенно он удобен для интегрированных IC. Объектно-ориентированное программирование (ООП) базируется на абстракциях данных. В основе этого метода лежит представление предметной области в виде совокупности объектов, которые взаимодействуют между собой через передачу сообщений. Модель абстракции данных заключается в инкапсуляции данных и операций над ними в отдельный классовый тип. Доступ к данным возможная лишь с помощью инкапсулированных операций. Классовый тип является автономно завершенным и позволяет полное или частичное наследование для других классов. ООП концентрируется на цели задачи, для которой разрабатывается программа. Задача строится как совокупность объектов, которые взаимодействуют между собой с помощью сообщений. Элементы программы разрабатываются в соответствии с объектами в описании задачи. Суть ООП заключается в определении наиболее удачных объектовых типов. Объектовый тип служит модулем, который может быть использованным для решения других подобных задач. Такой подход не нуждается в специальной вычислительной технике, но существенно отличается характером мышления исполнителей в сравнении с процедурными языками программирования.
