Реализация алгоритмов принятия решения о корректности или ошибочности состояний мультиверсий

Определяющим звеном мультиверсионной системы является блок принятия решения. Этот блок разделяет результаты (выходы) многочисленных программных версий на «корректные» и «ошибочные» [3]. Существует несколько методик подобного разделения. Самые общие из них основываются на классификации выходов. Наиболее перспективными из этих методик являются голосование абсолютным большинством, голосование согласованным большинством, а также нечеткое голосование согласованным большинством. В рамках данной работы, мной были предложены улучшения этих методик, а именно взвешенное голосование согласованным большинством и нечеткое взвешенное голосование согласованным большинством. Методики этой группы основаны на сравнении выходов мультиверсий и размещении идентичных из них в одинаковые классы (подмножества). Однако, в случаях, когда расчеты выполняются не с целыми числами, определение идентичны выходы или нет, является затруднительным. Для разрешения этой проблемы введем понятие соотношение равенства: мы будем говорить, что два числа равны, если они отличаются меньше чем на некоторое допустимое отклонение. Эти соотношения не требуют выполнения свойства транзитивности. Иными словами, если известно, что |a ‑ b| < ε и |b ‑ c| < ε, то отсюда не следует что |a ‑ c| < ε, где a, b и c – некоторые числа. Потенциальной проблемой методик данной группы является возможная неверная классификация выходов, и как следствие неверное принятие решения, что, в конечном счете, способно привести к отказу системы управления.

Вторая группа методик принимает решение без классификации выходов. В эту группу входят: медианное голосование и взвешенное медианное голосование. Они выбирают среднее значение из всех выходов как «корректное».

 

Алгоритм голосования абсолютным большинством (ГАБ)

Это самый простой алгоритм. При голосовании абсолютным большинством, для принятия решении необходимо, чтобы как минимум у версий результаты были идентичны (где - оператор округления до ближайшего большего целого). Например, для мультиверсионной системы с 7 независимо разработанными и функционально эквивалентными версиями, пороговое значение m будет равно 4.

Считается, что выходы большинства (т.е. класс, с числом элементом равным или превышающим m) мультиверсий – корректны, а остальные – ошибочны. Если равных выходов меньше чем m, то такая ситуация трактуется как неопределенность и принять решение невозможно.

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

Для реализации данного метода используется булева матрица согласования R. Элементы этой матрицы определяются следующим образом:

Иными словами, если выход версии i «согласен» с выходом версии j и дополнительно включает некоторую область ε, то r_ij = 1, иначе r_ij =0.

Для принятия решения, используя алгоритм голосования абсолютным большинством, необходимо в матрице R найти такую строку i, сумма элементов которой будет больше или равна пороговому значению m. Тогда все мультиверсии j, которым соответствуют r_ij равныеединице, являются корректными, а остальные ошибочными. В случае, когда такой строки не существует, происходит ошибку – решение принять невозможно.

 

Алгоритм голосования согласованным большинством (ГСБ)

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

Для реализации, как и в методе ГАБ, составляется матрица согласования R. Выбор нужного множества корректных выходов осуществляется в два этапа:

1. выбираются и запоминаются все строки, сумма элементов которых максимальна
2. случайным образом выбирается любая из этих строк

Если у найденной строки номер i, тогда все мультиверсии j, которым соответствуют r_ij равныеединице, являются корректными, а остальные ошибочными.

Главным преимуществом этого алгоритма, по сравнению с голосованием абсолютным большинством, является более высокая устойчивость к межверсионным ошибкам. Недостатками является присутствие элемента случайности в процессе принятия решения и более высокое требование к памяти. Например, при наличии двух равных классов вероятность выбора корректного выхода равна 0,5.

Основным недостатком классического алгоритма ГСБ является то, что решение принимается без учета накапливаемой статистики сравнения. При недостаточно высокой надежности самих программных модулей, снижается вероятность того, что класс с относительно большим числом элементов будет корректным. Это связано, с одной стороны, с тем, что корректные состояния может быть и в группе с несколько меньшим числом элементов, чем самая большая. А с другой – это элемент случайности при выборе среди классов с одинаковым числом состояния.

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

, где

i – номер строки в матрице согласования;

p_j – вероятность корректного выхода мультиверсии j;

n – количество мультиверсий.

В качестве p_i можно использовать накопленную статистическую информацию о ходе выполнения мультиверсий.

Тогда схема выбора нужного класса выходов принимает вид:

1. выбираются и запоминаются все строки, обладающие максимальным весом
2. случайным образом выбирается любая из этих строк

Такая схема называется взвешенное голосование согласованным большинством (ВГСБ). В связи с использованием вероятностей, этот алгоритм накладывает ограничение на нижнюю границу средней надежности программных модулей. Преимуществом взвешенного голосования является очень высокая устойчивость к межверсионным ошибкам и снижение влияния элемента случайности, по сравнению с базовым вариантом методики.

 

Алгоритм нечеткого голосования согласованным большинством (НГСБ)

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

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

В классической теории алгоритмов голосования, используются соотношения равенства, основывающиеся на четких множествах. Считается, что x равно некоторому числу a, если |x - a| < ε. Тогда характеристическая функция это равенство может быть представлена следующим образом:

Эта функция имеет прямоугольную форму (рисунок 2.4а) с центром в точке a и шириной основания равной ε. Степень принадлежности внутри этого прямоугольника равна 1, вне – равна 0. Однако, более удобно задавать степень принадлежности так, чтобы она уменьшалась по мере удаления от a. Например, задавать ее в виде треугольника (рисунок 2.4б):

(1)

 

Рисунок 2.4. Характеристическая функция соотношения равенства x и a
как а) четкого множества и б) нечеткого множества в форме треугольника

 

Матрица согласования в данном случае будет определяться как:

R = { r_ij }, где

Далее, производят усечение значений элементов полученной матрицы R к булевому виду , по некоторому заданному пороговому значению λ. Причем, значение λ нередко указывают в названии применяемой методики - например, для λ=0,5, название будет НГСБ-0,5.

Усечение значений происходит по следующей схеме:

После этого, полученная матрица = { } используется как матрица согласования в четком методе голосования согласованным большинством (как базовом, так и взвешенном), рассмотренном выше.

 

Медианное голосование

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

, где

r – корректный результат;

α_i – весовой коэффициент;

x_i – выход мультиверсии i;

n – количество мультиверсий.

Если α_i ≠ 1, то данный алгоритм называется взвешенное медианное голосование.

Эти алгоритмы применяются в случаях, когда произвести прямое сравнение результатов мультиверсий затруднительно. Например, когда мультиверсионная система используется для поиска оптимальных направлений. В такой ситуации напрямую сравнивать векторы не имеет смысла, так как они как минимум разной длины.