Модификация алгоритма голосования NVP-CV для одного вида матриц согласования

Results of computer simulation of photovoltaic array simulator with cascade connection of pulse and continuous power amplifiers are presented.

Принята к печати в декабре 2006 г.

• В.    А. Морозов

МОДИФИКАЦИЯ АЛГОРИТМА ГОЛОСОВАНИЯ NVP-CV ДЛЯ ОДНОГО ВИДА МАТРИЦ СОГЛАСОВАНИЯ

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

Абсолютное большинство исследователей надежности программного обеспечения (ПО) [1; 2] сходятся во мнении, что концепция мультиверсий является эффективным способом повышения надежности ПО. Но, при использовании мультиверсионного подхода возникает необходимость выбора корректных выходов среди всего множества выходов данного набора версий. Эта задача, как правило, решается с помощью какого-либо алгоритма голосования. Таким образом, корректность работы всей мультиверсионной системы зависит от используемого алгоритма голосования.

В настоящее время предложены следующие алгоритмы голосования [1; 2]:

• -    алгоритм голосования абсолютным большинством (N-version programming with majority voting, NVP-MV);

• - алгоритм голосования согласованным большинством (N-version programming with consensus voting, NVP-CV);

• -    нечеткий алгоритм голосования абсолютным большинством (Fuzzy majority voting);

• -    нечеткий алгоритм голосования абсолютным большинством (Fuzzy consensus voting);

• -    алгоритм голосования абсолютным большинством с минимизацией (minMV;

• -    алгоритм голосования согласованным большинством с минимизацией (minCV);

• -    формализованный алгоритм голосования абсолютным большинством (Formalized majority voting, FMV);

• -    формализованный алгоритм голосования согласованным большинством (Formalized consensus voting, FCV);

• -    максимально вероятное голосование (Maximum likelihood voting, MLV);

• -    медианное голосование.

Для каждого алгоритма характерны свои достоинства и недостатки, и каждому алгоритму соответствует определенная область применения.

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

Перед тем как перейти к рассмотрению схемы работы алгоритма, остановимся на некоторых нюансах его применения:

• -    при сравнении значений выходов мультиверсий используют понятие эквивалентности выходов. Так, выход одной версии эквивалентен выходу другой версии, если значения выходов отличаются не более чем на фиксированное число. Такое число называют допустимым отклонением;

• -    в качестве корректного результата возвращается набор эквивалентных выходов. Такой набор выбирается из всего множества выходов, которое образовано выходами версий;

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

такого требования необходимо для решения проблемы несовместимости разбиения (inconsistent partition problem) [2].

Рассмотрим схему работы алгоритма голосования согласованным большинством [1].

Пусть дан набор версий некоторого модуля:^,^,..., Л^-и пусть N- число версий. Обозначим через x_v x₂, ., x_N конкретные выходные значения каждой версии. Пусть также задано допустимое отклонение е. Тогда алгоритм выглядит следующим образом.

Шаг 1. Построение матрицы согласования R. Матрица согласования представляет собой булеву матрицу размерностью Ах N. Элементы матрицы согласования вы числяются по следующему принципу:

r ij

1,

0,

I Xi - xj< е, иначе.

Шаг 2. Проверка отношения эквивалентности на матрице согласования. Должны быть выполнены следующие свойства отношения эквивалентности:

-рефлексивность:

г. - 1 V i,(2а)

• -    симметричность:

rij-rjiV ^Р

• -    транзитивность:

если r.t -1 и r - 1, то г. - 1 V i, у.(2в)

Если отношение эквивалентности не выполнено, то матрицу согласования необходимо изменить с использованием булевых композиций, перейдя к шагу 3. Если же отношение эквивалентности выполнено, то следует переходить к шагу 4.

Необходимо особо отметить, что на матрице согласования свойства рефлексивности и симметричности выполняются всегда. В общем случае может быть не выполнено только свойство транзитивности. Отношение, на котором выполнены только свойства рефлексивности и симметричности, называют допустимым отношением (tolerance relation) [1]. В работе [3] показано, что если на матрице выполнено допустимое отношение, то не более чем за N- 1 булевых композиций мы получим матрицу согласования, на которой выполнено отношение эквивалентности (2а, 2б, 2в).

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

Пусть даны матрицыА и В. Все элементы а матрицы А имеют значения 0 или 1, и все элементы Аматрицы В имеют значения 0 или 1. Тогда булева композиция матрицА и В будет

N

С А м B, c ₈ = © ( a, © b_s ) , (3) где c. - элементы результирующей матрицы; © - функция логического «или»; © - функция логического «и».

Применительно к матрице согласования булева композиция определена следующим образом: R² -R u R £ R. При условии выполнения свойства транзитивности нужно переходить к шагу 4.

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

Например, если матрица согласования имеет вид, представленный в табл. 1, то согласно методике голосования согласованным большинством корректными выходными значениями являютсяxpx2,x3,x5 (в 1,2,3,5 строках число единиц максимально и равно четырем). А в случае когда есть несколько различных строк с максимальным числом единиц, набор корректных выходов может быть выбран случайно.

Таблица 1

	Х 1	Х г	Х з	Х 4	Х 5	Х б
Х 1	1	1	1	0	1	0
Х г	1	1	1	0	1	0
Х 3	1	1	1	0	1	0
Х 4	0	0	0	1	0	1
Х 5	1	1	1	0	1	0
Х б	0	0	0	1	0	1

Алгоритм голосования согласованным большинством не эффективен в случае, когда в матрице согласования имеется несколько различных строк с максимальным числом единиц. Действительно, если таких строк две и мы выбираем набор корректных выходов случайно, то вероятность того, что мы выбрали правильный ответ, равна 0,5 (а если таких строк три, то 1 / 3). Рассмотрим пример.

Пример 1. Пусть программный модуль реализован девятью эквивалентными и независимыми версиями (А- 9) и пусть е - 0,1, а значения выходов версий следующие:

• - версия 1:x₁ -0,321;

• -    версия 2: x₂ - 0,322;

• - версия 3:x₃ -0,323;

• -    версия 4: x₄ - 0,65;

• - версия 5: x₅ -0,821;

• -    версия 6: x₆ - 0,822;

• -    версия 7: x₇-0,823;

• - версия 8: x₈ -0,651;

• -    версия 9: x₉-0,1.

Для решения применим алгоритм, описанный выше.

Шаг 1. Построение матрицы согласования. Для данного набора выходных значений матрица согласования представлена в табл.2.

Шаг 2. Проверка отношения эквивалентности на матрице согласования. На этой матрице согласования отношение эквивалентности (2а, 2б, 2в) выполнено.

Шаг 3. В его выполнении нет необходимости.

Шаг 4. Определение набора корректных выходов. В 1,2и 3-й строках полученной матрице число единиц максимально и в 5, 6и 7-й строках число единиц также мак- симально. Таким образом, множество корректных выходов равно либо xt = 0,321; х2 = 0,322; х3 = 0,323, либо х5 = 0,821; х6 = 0,822; х7= 0,823. Теперь перед нами стоит задача выбора одного из множеств. При случайном выборе вероятность корректного срабатывания модуля равна только 50 %, что недостаточно высоко. С другой стороны, если можно было бы возможность сравнить, какой из наборов версий: 1,2,3 или 5, 6,7 -работает надежнее, то выбор был бы очевиден.

Таблица 2

	Х 1	Х 2	Х 3	Х 4	Х 5	Х 6	Х 7	Х 8	Х 9
Х 1	1	1	1	0	0	0	0	0	0
Х 2	1	1	1	0	0	0	0	0	0
Х д	1	1	1	0	0	0	0	0	0
Х 4	0	0	0	1	0	0	0	1	0
Х 5	0	0	0	0	1	1	1	0	0
Х 6	0	0	0	0	1	1	1	0	0
Х 7	0	0	0	0	1	1	1	0	0
X g	0	0	0	1	0	0	0	1	0
Х 9	0	0	0	0	0	0	0	0	1

Принимая во внимание последнее, предлагаем следующую модификацию алгоритма голосования согласованным большинством:

• -    надежности (вероятности безотказной работы) всех версий модуля определены до момента голосования (например, с использованием метода наработки на отказ);

• -    любой набор версий представляет собой систему с параллельным соединением [3], надежность которой может быть вычислена по формуле

l

R_t , = 1 — П (1 — А ),                (4)

i=k

где £<...<;< N- номера версий, входящих в рассматриваемый набору . - надежность z-й версии, входящей в набор.

Итак, предлагаемый автором модифицированный алгоритм следующий. Первые три шага алгоритма NVP-CV остаются без изменения, а четвертый шаг выглядит таким образом.

Шаг 4. Определение набора корректных выходов. На этом шаге выполняются следующие операции:

• -    подсчитываем количество единиц в каждой строке матрицы согласования. Обозначим количество единиц У;

• -    определяем строки, в которых количество единиц максимально;

• -    если строки с максимальным числом единиц одинаковы (единицы стоят на одинаковых позициях, как в табл. 1), то набор корректных результатов определяем по позициям единиц в строке и завершаем работу алгоритма. Если же имеются несколько различных строк, тогда переходим к следующему шагу;

• -    для каждой строки с максимальным числом единиц по формуле (4) вычисляем надежность соответствующе

го набора версий. Обозначим эти надежности R_{fc Г} Набор версий определяем следующим образом: в набор включаем те версии, номерам которых соответствуют единицы в строке; далее в качестве набора версий, которые вернули корректный результат, выбираем тот набор, надежность которого выше. Отметим, что набор корректных результатов всегда соответствует максимальному числу эквивалентных выходов.

Проиллюстрируем работу модифицированного алгоритма на примере.

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

• - версия 1:х₁ = 0,321,р₁ =0,3;

• -    версия 2: х₂ = 0,322, р₃ = 0,4;

• - версия 3:х₃ = 0,323,р₃ =0,5;

• -    версия 4: х₄ = 0,65,_р₄ = 0,1;

• - версия 5:х₅ = 0,821,р₅ = 0,7;

• -    версия 6: х₆ = 0,822,_р₆ = 0,8;

• - версия 7: х₇ = 0,823,_р₇ = 0,9;

  -версия 8: х₈=0,651,р₈ = 0,3;

• -    версия 9: х₉=0,1,р₉ = 0,4.

Для решения применим модифицированный алгоритм голосования согласованным большинством.

Шаг 1. Для данного набора выходных значений матрица согласования представлена в табл. 3.

Таблица 3

	Х 1	Х 2	Х 3	Х 4	Х 5	Х 6	Х 7	Х 8	Х 9
Х 1	1	1	1	0	0	0	0	0	0
Х 2	1	1	1	0	0	0	0	0	0
Х 3	1	1	1	0	0	0	0	0	0
Х 4	0	0	0	1	0	0	0	1	0
Х 5	0	0	0	0	1	1	1	0	0
Х 6	0	0	0	0	1	1	1	0	0
Х 7	0	0	0	0	1	1	1	0	0
Х 8	0	0	0	1	0	0	0	1	0
Х 9	0	0	0	0	0	0	0	0	1

Шаг 2. На этой матрице отношение эквивалентности (2а, 2б, 2в) выполнено.

Шаг 3. В его выполнении нет необходимости.

Шаг 4. В 1,2и 3-й строках полученной матрицы число единиц максимально, и в 5, 6и 7-й строках число единиц также максимально, но строки различны. Таким образом, множество корректных выходов равно либо х₁ = 0,321; х₂ = 0,322; х₃ = 0,323, либо х₅ = 0,821; х₆= 0,822; х₇= 0,823. Вычислим УиR_{^ ;}(табл. 4).

Итак, в соответствии с приведенным выше алгоритмом множество корректных выходов однозначно равно х5 = 0,821; х6=0,822; х7=0,823, поскольку 0,994 > 0,79.