Содержание к диссертации
Введение
1. Анализ существующих алгоритмов голосования в задаче обеспечения отказоустойчивости сложных систем обработки информации 11
1.1. Принципы обеспечения отказоустойчивости сложных систем обработки информации 11
1.2. Существующие алгоритмы голосования в отказоустойчивых резервированных системах обработки информации 19
1.3. Критерий эффективности. Анализ существующих алгоритмов голосования 38
1.4. Цель работы и постановка задачи исследования 54
2. Разработка алгоритмов голосования в отказоустойчивых резервированных системах обработки информации на основе нечеткой логики 57
2.1. Разработка алгоритма голосования на основе нечеткой логики 57
2.2. Анализ эффективности разработанного алгоритма голосования на основе нечеткой логики 64
2.3. Сравнение алгоритма голосования на основе нечеткой логики по суммарной мере равенства с алгоритмом вычисления взвешенного среднего значения 71
3. Разработка алгоритмов голосования в отказоустойчивых резервированных системах обработки информации на основе нейронных сетей 78
3.1. Применения нейронных сетей в задачах голосования в резервированных системах обработки информации 78
3.2. Выбор структуры нейронной сети 79
3.3. Сравнение алгоритма голосования на основе нейронной сети с алгоритмом вычисления взвешенного среднего значения 93
4. Сравнительный анализ эффективности алгоритмов голосования в резервированных системах обработки информации и рекомендации по внедрению 99
4.1. Сравнительный анализ существующих лучших алгоритмов голосования с алгоритмом голосования на основе нейронной сети 99
4.2. Сравнение алгоритмов голосования в системе с различной вероятностью правильной работы элементов 102
4.3 Области эффективного применения различных алгоритмов голосования и методика выбора метода голосования в зависимости от конкретных условий применения 105
4.4 Применение разработанных алгоритмов голосования для обработки информации о характеристиках доступных каналов связи при создании аппаратуры каналообразования и коммутации с адаптивным конфигурированием и высокой помехообрывоустойчивостью 112
4.5. Применение разработанных алгоритмов голосования для обработки результатов экспериментов с целью повышения точности 120
Заключение 130
Список использованной литературы 132
- Существующие алгоритмы голосования в отказоустойчивых резервированных системах обработки информации
- Анализ эффективности разработанного алгоритма голосования на основе нечеткой логики
- Выбор структуры нейронной сети
- Сравнение алгоритмов голосования в системе с различной вероятностью правильной работы элементов
Введение к работе
Актуальность работы. Для удовлетворения высоким требованиям, предъявляемым к надежности аппаратуры и программного обеспечения в современных информационных системах, часто используется метод многократного резервирования.
Примерами резервированных систем обработки информации, рассматриваемых в данной работе, являются:
Системы с параллельным и независимым выполнением одной и той же задачи несколькими вычислителями, отличающимися друг от друга вплоть до наборов системной логики и фирмы изготовителя.
Системы, спроектированные разными группами инженеров с использованием различных языков и технологий программирования и работающие на основе параллельного выполнения нескольких функционально идентичных программных модулей, разработанных по одной спецификации.
Системы, использующие несколько различных физических каналов при передаче информации в сетях связи специального назначения.
Системы, в которых измерение некоторой физической величины осуществляется с использованием нескольких датчиков, основанных на различных принципах.
В перечисленных примерах в заданных контрольных точках необходимо принимать решение о выборе одного результата из нескольких, полученных функционально идентичными, но максимально отличными в остальном резервными модулями. Для решения данной проблемы хорошо зарекомендовали себя алгоритмы голосования, значительный вклад в развитие которых внесли такие отечественные и зарубежные ученые как Ю. И. Журавлев, П. Р. Лорцзак, М. А. Воук и др.
Наибольшее внимание в мировой науке было уделено алгоритмам голосования, выбирающим между результатами, принадлежащими целочисленному множеству малой мощности. Вместе с тем, в современной практике все чаще возникает необходимость выбора между ответами, принадлежащими множеству вещественных чисел. Вследствие большой мощности таких множеств задача голосования приобретает неопределенность и становится трудноформализуе-мой. Одним из решений этой задачи является алгоритм голосования с использованием нечеткой логики, предложенный Д. Ф.Макали стером, который впоследствии был развит в работах В.А.Морозова.
Однако, существующие алгоритмы голосования не в состоянии обеспечить высокую достоверность результатов на всем пространстве параметров распределения ответов, что объясняется недостаточной изученностью и проработкой поставленной проблемы. При решении трудноформализуемых задач нашли широкое применение методы искусственного интеллекта, в частности нечеткая логика и нейронные сети. Поэтому представляется целесообразным изучение возможности применения нечеткой логики и нейронных сетей для
решения задачи голосования в системах, результаты функционирования которых принадлежат множеству вещественных чисел.
Алгоритм голосования определяет результат работы всей резервированной системы в целом, поэтому ошибка на этапе голосования может привести к значительным материальным, финансовым и людским потерям. Таким образом, задача исследования и разработки алгоритмов голосования с целью повышения достоверности результатов работы резервированных систем, является актуальной.
В данной работе предложено дальнейшее развитие алгоритмов голосования на основе нечеткой логики и проведены исследования по разработке новых алгоритмов голосования на основе нейронных сетей.
Объект диссертационного исследования - блок принятия решений (голосования) в резервированных системах обработки информации.
Предмет диссертационного исследования - алгоритмы голосования на основе нечеткой логики и нейронных сетей.
Целью диссертационной работы является повышение достоверности алгоритмов голосования в резервированных системах обработки информации, результаты работы которых принадлежат множеству вещественных чисел.
Для достижения поставленной цели в диссертационной работе сформулированы следующие задачи.
Разработать программное обеспечение, позволяющее проводить численные эксперименты и анализировать достоверность алгоритмов голосования при наличии ошибочных результатов от резервных модулей.
Разработать алгоритм голосования на основе нечеткой логики.
Разработать алгоритм голосования на основе нейронных сетей, предложить методику подготовки исходных данных для повышения достоверности голосования.
Исследовать достоверность предложенных алгоритмов голосования методом численного моделирования и разработать методику голосования на основе алгоритмических композиций.
Методы исследования основаны на использовании методов системного анализа, теории вероятностей и математической статистики, теории нечетких множеств, нейроинформатики, теории планирования эксперимента, имитационного моделирования, теории информационных систем и обработки данных.
Научная новизна результатов, полученных в диссертационной работе, заключается в следующем:
Разработан алгоритм голосования на основе нечеткой логики, отличающийся введением блока вычисления суммарной меры подобия, что позволяет отказаться от необходимости выбора порога дефаззификации X и допуска є, субъективно влияющих на эффективность голосования и используемых традиционно в алгоритмах на основе нечеткой логики.
Предложен алгоритм голосования на основе многослойного персептро-на, отличающийся методикой подготовки результатов работы модулей для осуществления голосования с предварительным ранжированием по их взаим-
ному расположению на декартовой оси координат и последующим вычислением разностей координат между ними, что позволяет повысить достоверность голосования в резервированных системах обработки информации.
3. Разработана методика голосования на основе алгоритмической композиции в соответствии с областью компетенции каждого из рассмотренных алгоритмов, позволяющая повысить достоверность голосования на всем пространстве параметров распределения ответов резервных модулей.
Практическая ценность диссертационной работы состоит в следующем:
Разработаны алгоритмы на основе нечеткой логики и нейронных сетей, позволяющие повысить достоверность результатов голосования на 1-2%, что приводит к уменьшению количества отказов в условиях моделируемого примера на 30-40%.
Разработана методика голосования на основе алгоритмической композиции алгоритмов голосования в соответствии с их областью компетенции, позволяющая повысить достоверность выбора ответов на всем пространстве их параметров распределения на 1-2%, что приводит к уменьшению количества отказов в условиях моделируемого примера на 30-40%.
Результаты диссертационной работы нашли практическое применение в ОАО НИИ «Солитон» при разработке аппаратуры каналообразования и коммутации с адаптивным конфигурированием и высокой помехообрывоустойчиво-стью для сетей связи специального назначения.
Основные научные положения, выносимые на защиту:
Алгоритм голосования на основе нечеткой логики для использования в резервированных системах обработки информации, результаты которых принадлежат множеству вещественных чисел.
Алгоритм голосования на основе многослойного персептрона, отличающийся методикой подготовки результатов работы модулей для осуществления голосования с предварительным ранжированием по их взаимному расположению на декартовой оси координат и последующим вычислением разностей координат между ними.
Результаты анализа разработанных алгоритмов на основе численного моделирования и методика голосования на основе алгоритмической композиции известных алгоритмов голосования.
Апробация работы. Основные положения и результаты работы докладывались и обсуждались на: 10-й Международной научно-технической конференции «Радиоэлектроника, электротехника и энергетика» (Москва, 2004); 2-й Всероссийской научно-технической конференции «Искусственный интеллект в XXI веке» (Пенза, 2004); Международной научной конференции «XXXII Гага-ринские чтения» (Москва, 2006); 14-м Всероссийском семинаре «Нейроинфор-матика и ее приложения» (Красноярск, 2006); семинарах молодых ученых и аспирантов УГАТУ (Уфа, 2007-2008); VII - IX Международных семинарах по компьютерным наукам и информационным технологиям (CSIT) (Уфа, 2005, 2007; Карлсруэ, 2006); Всероссийских научно-технических конференциях «Нейроинформатика» (Москва, 2006-2007).
Публикации. Основные материалы диссертационной работы опубликованы в 16 работах, включая 3 статьи в рецензируемых журналах из списка ВАК, 12 публикаций в журналах, материалах Всероссийских и Международных конференций и в 1 свидетельстве о регистрации программы для ЭВМ в Роспатенте.
Структура и объем работы. Диссертация состоит из введения, четырех глав основного текста, заключения, списка использованной литературы из 115 наименований, содержит 66 рисунков и 9 таблиц. Общий объем диссертации составляет 142 страницы.
Существующие алгоритмы голосования в отказоустойчивых резервированных системах обработки информации
Рассмотрим алгоритмы голосования для переменных, принадлежащих множеству малой мощности возможных значений.
Алгоритм голосования по абсолютному большинству в резервированных системах обработки информации - самый простой алгоритм голосования. Пусть система состоит из N функционально идентичных элементов. На выходе такой системы имеется N переменных х» і — 1...N. Все переменные распределяются по множествам эквивалентности таким образом, что переменные внутри одного множества равны. Множество, число элементов которого больше чем N12, считается содержащим верный результат [34, 35]. Рассмотрим пример. Пусть 5 переменных приняли следующие значения: 1,2, 1, 2, 2. В данном случае переменные разделятся на два множества: [1, 1], [2, 2, 2]. Второе множество содержит верный результат, т.к. количество элементов в нем 3 больше 5/2. Недостаток алгоритма заключается в неопределенности, возникающей при отсутствии множества, число элементов которого превосходило бы половину общего числа элементов N. Вторым недостатком алгоритма является невозможность фильтрации более, чем N12 ошибок одновременно. Данные недостатки привели к возникновению следующего алгоритма голосования.
Алгоритм голосования по большинству в резервированных системах обработки информации - этот алгоритм аналогичен предыдущему за исключением того, что множеством, содержащим корректный результат, считается множество с максимальным количеством элементов. Рассмотрим пример. Пусть 5 переменных приняли следующие значения: 1, 2, 3, 4, 2. В данном случае переменные разделятся на четыре множества: [1], [2, 2], [3], [4]. Множеством, содержащим наибольшее количество элементов, является второе. Следовательно, верным результатом будет число 2. Как показано в примере, данный метод может фильтровать одновременно больше, чем N12 ошибок.
Недостатком данного метода является неопределенность, возникающая, если несколько множеств содержат максимальное количество элементов. Например, в случае: 1, 1, 2, 2, 3. В данном примере переменные разделятся на три множества [1, 1], [2, 2], [3]. Существует неопределенность - какому множеству - первому или второму, отдать предпочтение.
Алгоритм голосования по большинству с предысторией в резервированных системах обработки информации использует введение достоверности каждого элемента - параметра, в котором фиксируется статистика выданных элементом правильных ответов. Чем больше элемент выдает ответов, совпадающих с результатом голосования, тем выше его достоверность. Параметр достоверности может учитывать статистику работы элемента в течение всего срока работы или только за несколько последних циклов работы [36]. Голосование происходит аналогично предыдущему методу. В случае возникновения неопределенности содержащим правильный результат считается множество с переменными от наиболее достоверных элементов.
Алгоритм голосования наибольшей вероятности в резервированных системах обработки информации — этот алгоритм использует достоверность элементов Pi непосредственно во время голосования, а не только для разрешения неопределенностей, и является одним из самых надежных [37]. Пусть Рг(...) — вероятность события, г — размерность множества допустимых значений переменных, N — количество функционально-идентичных элементов, Р, — статистическая вероятность того, что элемент і даст верный результат, і = X...N, Vt - переменная с выхода элемента i, V{ — значение, которое принимает переменная Vi. Тогда условная вероятность того, что і — й элемент выдаст некоторый результат Vit при условии, что корректный результат равен некоторому числу к є [1, г] будет Пусть на выходе системы имеется iVчисел Vj, V2,..., VN.
Тогда условная вероятность этого события при условии, что корректный результат равен к, будет Prk {Fj = v,} х РгА {К2 = v2 } х - х Ргд. {yN - vN }. Меняя значение корректного результата к от 1 до г, находим такое значение корректного результата к, при котором вероятность появления именно этих V], V2,...,VN наибольшая. Данное значение корректного результата и будет выбрано. Необходимо каждый раз обновлять статистическую вероятность корректного результата (достоверность) Р, для каждого элемента, увеличивая ее для элементов, давших ответ, совпавший с результатами голосования и уменьшая для элементов, давших ответ, не совпавший с результатами голосования. Существует несколько работ, в которых был предложен ряд модификаций данного метода и произведена оценка его эффективности с существующими методами голосования. Было показано превосходство данного метода и его высокая надежность для систем с малым множеством значений [38, 39].
Рассмотрим алгоритмы голосования для переменных, принадлежащих множеству большой мощности возможных значений.
Алгоритм вычисления среднего значения (ВСЗ) в резервированных системах обработки информации - самый простой алгоритм голосования. Алгоритм заключается в определении среднего значения для всех N переменных. Результат вычисляется по формуле: у = ——. Недостаток данного алгоритма заключается в равноправном участии в голосовании всех N переменных, следствием чего является существенное отклонение результата голосования от истинного значения даже при одном неисправном элементе, если переменная на его выходе принимает значение, сильно отличное от остальных.
Анализ эффективности разработанного алгоритма голосования на основе нечеткой логики
Для сравнения эффективности алгоритмов голосования проведено моделирование 5-кратно резервированной системы обработки информации по алгоритму, приведенному в п. 1.3. Сравним эффективность лучшего из алгоритмов голосования, использующих множества эквивалентности, выбранного нами ранее в качестве эталонного, его существующего аналога на основе нечеткой логики и двух предложенных алгоритмов голосования на основе нечеткой логики: - алгоритм голосования по пересекающимся множествам эквивалентности (ГПМЭ); - алгоритм голосования на основе нечеткой логики по пересекающимся множествам эквивалентности (НГПМЭ); - алгоритм голосования на основе нечеткой логики по пересекающимся множествам эквивалентности с саморегулированием (НГПМЭС); - алгоритм голосования на основе нечеткой логики по суммарной мере равенства (НГСМР); На рис. 2.2 отчетливо виден недостаток НГПМЭ - это зависимость вероятности правильного решения от правильно подобранного порога дефаззификации. При изменении порога дефаззификации эффективность НГПМЭ резко падает. Оптимальная величина порога дефаззификации различна для различного распределения корректных и некорректных переменных. НГПМЭС лишен данного недостатка и превосходит в эффективности четкий метод ГПМЭ. Необходимо упомянуть, что при оптимальном значении порога дефаззификации НГПМЭ все-таки превосходит ГПМЭ. Итак, видно, что существовавшие до этого времени алгоритмы голосования на основе нечеткой логики, превосходят в эффективности существующие алгоритмы на основе четкой логики. Однако, два новых алгоритма голосования на основе нечеткой логики НГПМЭС и НГСМР превосходят их. Из этих двух НГСМР является наиболее эффективным. Данные выводы касаются только 3-кратно резервированной системы. На рис 2.3 представлена зависимость вероятности правильного решения от Я: СКОнекорректн = Зє, СКОкорректн = ОЛє, N=5, вероятность правильной работы элементов 0.75. В пятикратно резервированной системе обработки информации НГПМЭ проявляет тот же недостаток - зависимость вероятности правильного решения от правильно подобранного порога дефаззификации. Эффективность НГПМЭС в пятикратно резервированной системе обработки информации ниже эффективности алгоритмов на основе четкой логики ГПМЭ и НГПМЭ, хотя и не зависит от Я. Очевидно, алгоритм саморегулирования в НГПМЭС работает хуже в пятикратной системе, чем в трехкратно резервированной системе обработки информации. НГСМР не зависит от Я и по эффективности сравним с НГПМЭ в его оптимальной точке. По результатам исследования поведения алгоритмов голосования в пятикратно резервированной и трехкратно резервированной системах обработки информации и после исследования зависимости их эффективности от А, можно сказать, что новый алгоритм НГСМР показывает наилучшие результаты.
Выбор структуры нейронной сети
В данном разделе решается задача исследования возможности повышения достоверности голосования с помощью нейронных сетей. Нейронные сети позволяют с любой точностью вычислять произвольную непрерывную функцию f[xu ... jcN) [92]. Это доказывается в ряде теорем о возможности получить любую непрерывную функцию N переменных с помощью операций сложения, умножения и суперпозиции из непрерывных функций одного переменного [93-95]. Поскольку алгоритмы голосования в резервированной системе обработки информации, по сути, являются функциями N переменных, то можно предположить, что возможно сконструировать нейронную сеть и обучить ее таким образом, чтобы она, как минимум, не уступала приведенным выше в работе алгоритмам. Самым простым классом нейронных сетей является персептрон, поэтому именно он и был выбран в качестве исходной структуры нейронной сети. Наиболее распространенным методом обучения для персептрона является алгоритм обратного распространения, который и был выбран на начальном этапе исследования. Хотя и существует несколько модификаций данного метода [96-99], каждая из них оптимальна для конкретного случая.
Для обучения нейронной сети необходимо моделирование резервированной системы обработки информации, которое бы адекватно отражало работу N независимых элементов. Для моделирования необходима как генерация правильных результатов работы каждого элемента, так и генерация неправильных результатов работы элемента, вызванная либо сбоями и отказами в самом элементе, либо явившаяся следствием каких-либо помех и внешних факторов, часто присутствующих в агрессивной среде, в которой применяется резервированная система обработки информации.
В качестве базовой нейронной сети был выбран трехслойный персептрон с сигмоидальной функцией активации. Поскольку в большей части работы проводится анализ эффективности работы алгоритмов голосования применительно к 5-кратно резервированной системе обработки информации, как системы, использующейся в самых ответственных случаях, то была предложена следующая структура нейронной сети: пять входных нейронов, слой скрытых нейронов и один выходной нейрон. Во время обучения на входные нейроны подавались моделируемые результаты работы элементов, а на выходной нейрон подавался идеальный результат. По нашему предположению, таким образом нейронная сеть должна была обучиться выдавать идеальный результат. Входные данные для нейронной сети нормализовывались. Однако данная конфигурация не показала каких-либо положительных результатов. Проблема состояла в том, что моделируемый идеальный результат изменялся в большом диапазоне значений, и за этими изменениями нейронная сеть во время обучения не могла выделить необходимую закономерность между входными данными, которая бы обеспечивала необходимую точность работы. Нормализация входного вектора не дала никакого улучшения обучаемости сети, поэтому было сделано предположение о нарушении главного принципа обучения - представления для обучения только необходимой информации.
Для повышения эффективности обучения, было предложено отказаться от использования в выходном слое нейронной сети одного нейрона, выход которого пропорционален идеальному результату работы элементов и является вещественным числом с большим диапазоном значений [100]. В выходном слое установлено N нейронов, выход каждого из которых пропорционален достоверности результата соответствующего элемента. Считается, что правильный результат выдал тот элемент, величина выходного сигнала соответствующего нейрона которого больше, чем у остальных нейронов. Однако, данной оптимизации оказалось недостаточно.
В качестве входных данных нейронной сети предложено использовать евклидово расстояние между результатами работы N элементов. Итак, для 5-кратной системы у нейронной сети имеется 10 нейронов во входном слое, на входы которых подается нормализованное евклидовое расстояние между результатами работы 5 элементов:
Нормализация необходима для повышения точности нейронной сети.
Первоначально обучение проводилось для 10 нейронов в скрытом слое. Процесс обучения происходил последовательным уменьшением скорости обучения от 1 до 0.01 с шагом 0.01. Для каждой величины скорости обучения использовалось 100 циклов обучения. Для обучения нейронной сети использовались элементы с вероятностью правильной работы, равной 0.5. Столь низкая вероятность правильной работы выбрана для ускорения процесса обучения сети.
Данная сеть показала хорошие результаты обучения. Тем не менее, помимо евклидова расстояния между результатами предложено дополнительно ввести в нейронную сеть информацию о взаимном расположении результатов. Для этого, перед тем как подавать результаты элементов на вход сети, необходимо отсортировать их по возрастанию. На рис. 3.1 представлена эффективность работы сети без сортировки и с сортировкой входных данных для разных СКОнекорректн: СКОкорректн = О.Зе, N=5, вероятность правильной работы элементов 0.75.
Сравнение алгоритмов голосования в системе с различной вероятностью правильной работы элементов
В реальных резервированных системах обработки информации вероятность правильной работы элементов различна. Поэтому необходимо провести моделирование системы, приближенное к реальным условиям функционирования. Пусть вероятность правильной работы каждого элемента составит 0.65, 0.70, 0.75, 0.80 и 0.85, соответственно. На рис. 4.5 представлена зависимость вероятности правильного решения от СКОнекорректн: СКОкорректн = О.Зє, iV=5, вероятность правильной работы элементов 0.65, 0.70, 0.75, 0.80, 0.85, соответственно. На рис. 4.6 представлена зависимость вероятности правильного решения от СКОнекорректн: СКОкорректн = Б, N=5, вероятность правильной работы элементов 0.65, 0.70, 0.75, 0.80, 0.85, соответственно. При различной вероятности правильной работы элементов алгоритм НГСМР, учитывающий предысторию голосования, значительно улучшает свою эффективность по сравнению с остальными алгоритмами голосования. На рис. 4.7. представлена зависимость вероятности правильного решения от СКОкорректн: СКОнекорректн = Ъе, N=5, вероятность правильной работы В условиях различной вероятности правильной работы элементов, алгоритм НГСМР показывает наилучшую эффективность, например при СКОнекорректн = Ъе и СКОкорректн = 0.6є, вероятность принятия неправильного решения при использовании ВВСЗ составит 1-0.966=0.034, вероятность принятия неправильного решения при использовании НС и МЕД составит 1-0.974=0.026, вероятность принятия неправильного решения при использовании НГСМР будет 1-0.984=0.016. Таким образом, НГСМР показал уменьшение вероятности принятия неправильного решения на 1-0.016/0.034=0.53 (53%) по сравнению с ВВСЗ и на 1-0.016/0.026=0.38 (38%) по сравнению с МЕД для системы со средней вероятностью правильной работы элементов равной 0.75.
