Надежность интеллектуальных информационных систем

Министерство образования РФ Тверской государственный университет Факультет прикладной математики и кибернетики Кафедра информационных систем и технологий В. А. Масюков Надежность информационных систем КУРС ЛЕКЦИЙ УЧЕБНОЕ ПОСОБИЕ Тверь, 2002 г. Содержание. Введение. ………………………………………………………………………………………………….3 1. Надежность интеллектуальных информационных систем…………………………………….4 2. Основы расчета надежности невосстанавливаемых систем…………………………………...8 2.1. Расчет надежности систем при основном соединении элементов……………………………8 2.2. Расчет надежности при общем резервировании……………………………………………...11 2.3. Расчет надежности систем при поэлементном резервировании…………………………….15 3. Основы расчета надежности восстанавливаемых систем…………………………………….17 3.1. Расчет надежности систем с использованием марковского процесса………………………17 3.2. Расчет надежности систем с использованием распределения Пуассона………………...…20 4. Методы расчета надежности систем со сложной структурой… … … ………………………21 4.1. Метод разложения по ключевым элементам…………………………………………………21 4.2. Метод эквивалентности работоспособных состояний……………………………………….22 4.3. Метод преобразования логических функций работоспособности…………………………..24 5. Принципы диагностики надежности информационных систем……………………………..25 5.1. Метод обработки изображений с использованием булевых функций…………………….. 25 5.2. Алгоритм поиска неисправностей с использованием оптимизации на графах…………….28 5.3. Методы технической диагностики…………………………………………………………… 29 5.3.1. Метод потенциалов………………………………………………………………………29 5.3.2. Метод среднего риска……………………………………………………………………31 5.3.3. Метод диагностических комплексов…………………………………………………. .35 Литература………………………………………………………………………………………………36 2 Введение. В настоящее время проблема надёжности является ключевой и, по существу, от неё во многом зависят темпы развития современных информационных систем. Опасность заключается не только в том, что новые сложные информационные системы не будут работать (будут возникать проблемы), но главным образом в том, что отказ в их работе (в том числе и неправильная работа) может привести даже к катастрофическим последствиям. Согласно ГОСТа 27.002-82, надёжность – свойство объекта сохранять во времени в установленных пределах значения всех параметров, характеризующих способность выполнять требуемые функции в заданных рамках и условиях применения, технического обслуживания, ремонта, хранения и транспортирования. Более просто, надежность – свойство объекта сохранять свою работоспособность на некотором отрезке времени. С развитием и усложнением информационных систем потребовалась разработка теории информационных систем. Начало формирования этой теории относится к середине предыдущего столетия. Математическим фундаментом теории надёжности являются теория вероятностей, математическая логика и теория принятия решений. Прикладные вопросы теории надёжности являются предметом рассмотрения в этом учебном пособии. В учебном пособии изложены основы расчёта надёжности информационных систем различной сложности. Все основные положения теории поясняются на примерах. В связи с тем, что все ситуации, которые могут встретиться на практике предусмотреть невозможно, в пособии рассматриваются наиболее общие закономерности и принципиальные положения, необходимые для диагностики и расчёта надёжности информационных систем различной сложности. 3 1. Надёжность интеллектуальных информационных систем. Под надёжностью интеллектуальных информационных систем понимается способность устойчивого сотрудничества индивидов, входящих в состав этих систем, иначе говоря, способность сохранять системами свою работоспособность. Пример интеллектуальных информационных систем: коллектив (людей, интеллектуальных роботов), семья. Успешность сотрудничества зависит от индивида (объектоверт, субъектоверт, экстерналист, интерналист), которая характеризуется: 1) Степенью воздействия на него окружения (чувствительностью к окружению). 2) Степенью его воздействия на окружение (характером реакции на воздействие окружения). Будем считать, что объектоверт – это человек чувствительный к своему окружению, а субъектоверт – нечувствительный. Следовательно, объектоверт более склонен воспринимать, что вокруг него происходит, и подвергаться влиянию происходящего. Субъектоверт же больше подвержен влиянию собственных мыслей и чувств, чем окружения. Объектоверсия и субъектоверсия проявляются как тенденции, а не как незыблемые приверженности. Поэтому при некоторых обстоятельствах объектоверт может действовать как субъектоверт и наоборот. Чем дальше от крайностей находится человек в этом пространстве, тем более он склонен откликаться как на внешние, так и на внутренние стимулы. При некоторых обстоятельствах (например, в дружеской компании) субъектоверту свойственно больше походить на объектоверта, чем обычно. С другой стороны, объектоверт, работающий в своем кабинете, может выглядеть как субъектоверт. Аналогично различие между художником-реалистом и художником-сюрреалистом. Будем считать, что экстерналист – это тот, кто склонен изменять окружение в соответствии со своими нуждами. Интерналист сам адаптируется к окружению. Если кто-то вторгается в окружение экстерналиста, раздражая или отвлекая его, то он, вероятно, попытается пресечь такое вмешательство. Интерналист в этой же ситуации скорее будет парировать факт вторжения или же переберется в другое место. Экстерналист попытается организовать группу, в которую сам входит, чтобы возглавить ее; интерналисту более свойственно следовать за каким-либо лидером. Если в доме холодно экстерналист попробует включить отопление, а интерналист – потеплее оденется. Пространство типов личностей представлено на рис. 1. 1,0 Объектоверт Объективный интерналист (ОИ) Объективный экстерналист (ОЭ) Субъективный интерналист (СИ) Субъективный экстерналист (СЭ) Субъектоверт 1,0 Интерналист Экстерналист 1,0 Рис. 1. Пространство личности. 4 Предполагается, что большинство людей относится к двум смешанным типам: объективный интерналист и субъективный экстерналист. Однако практическое распределение конкретных людей по типам личностей весьма затруднительно. Но, если тип личности определен, то предполагается, что частные типы (например, интерналист и экстерналист) всецело поглощены соответственно своим внутренним, либо внешним миром, в то время как смешанные типы сохраняют, хотя и по разному, некоторый контакт и со своей психической реальностью, и со своим окружением. Частные типы, столкнувшись с проблемами, требующих самоприспособления, склонны изменяться таким образом, что соответствующие им точки в пространстве личности смещаются к внешним границам (т. е. свойственные им черты только увеличиваются). Смешанные же типы склонны смещаться к центру этого пространства, которому соответствует психологическая зрелость и сила. Например, потребление алкоголя дает такие краткосрочные эффекты (частным типам свойственно пить сверх меры, смешанным типы пьют умеренно), а по мере созревания и старения эти эффекты усиливаются. Пример расположения двух индивидов (А и В) в пространстве личностей показан на рис. 2. Взаимоотношения между ними можно охарактеризовать двумя мерами: 1. Неравновесие (|ОА - ОВ|): эта мера представляет собой разницу в их удаленности от точки О (точка центоверсии). Направление может быть обусловлено, например, разницей в степени чувствительности на влияние внешней среды или степени реакции на это влияние. 2. Асимметрия ( θ ): это угол между продолжением отрезков АО и ОВ. Если точки А и В совпадают, то этот угол полагается равным 180o . При увеличении неравновесия между двумя индивидами им становится все труднее адаптироваться друг к другу. Более центровертированный партнер будет склонен руководить и влиять на менее центровертированого партнера. Зачастую это будет происходить вопреки тем традиционным ролям, которые они для видимости играют. При возрастании асимметрии от 0 до 90o увеличиваются искажения в восприятии одного типа другим, хотя изменении этого угла от 90 до 180o происходит уменьшение этого искажения. Когда асимметрия достигает 90o партнеры постепенно теряют надежду на возможность перемен, т. е. на выполнение ожидание относительно своего партнера в соответствии со своим восприятием. Пару А и В представляет в пространстве личности точка G (рис. 2), находящаяся на середине отрезка OD. Если пара симметрична и равновесна, то она попадает в точку центроверсии и, значит, будет находиться в состоянии равновесия. Чем дальше пара удалена от точки центроверсии, тем менее успешной она по всей вероятности окажется. Естественно, что пара всегда расположена ближе к центру центроверсии, чем по меньшей мере один из ее участников, если только оба не находятся в одной и той 1 же точке. Заметим, что OG = OD , где N – число индивидов. N Пары из диагональных ячеек 1. Объективный интерналист (ОИ) и субъективный экстерналист (СЭ). Если между ними возникла проблема, то оба будут согласны изменять ОИ. Внешнюю проблему воспримет ОИ, сообщит СЭ, который ею займется. Система устойчива (надежна). 2. Субъективный интерналист (СИ) и объективный экстерналист (ОЭ). Если между ними возникает проблема, то СИ будет склонен ее решить изменяя самого себя, а ОЭ будет ему помогать. Хотя СИ свойственна нечувствительность к усилиям ОЭ, однако он с удовольствием предоставит инициативу ОЭ для воздействия на окружение, если есть внешняя проблема. Система устойчива (надежна). 5 1,0 (ОЭ) (ОИ) Объектоверт В D G А Субъектоверт (СЭ) (СИ) 1,0 Интерналист Экстерналист 1,0 Рис. 2. Два индивида в пространстве личности. Пары из смежных ячеек 3. Объективный экстерналист (ОЭ) и субъективный экстерналист (СЭ). Соперничество друг с другом из-за того, кому управлять окружением для решения их проблемы, к тому же проблему они понимают каждый по своему. В паре они будут производить впечатление агрессивности (по отношению к их окружению). Нет механизма решения внутренних проблем. Надежность системы невысокая. 4. Объективный интерналист (ОИ) и субъективный интерналист (СИ). Каждый будет пытаться изменить самого себя для решения своих проблем. Со стороны ОИ потребуются постоянные личные жертвы, т. к. на него больше влияет внешняя среда, причем СИ не будет их осознавать, а поэтому вряд ли их оценит. Таким образом, они будут выглядеть пассивной парой. Надежность системы невысокая. 5. Объективный интерналист (ОИ) и объективный экстерналист (ОЭ). Усилия обоих при решении внутренних проблем направлены на изменение ОИ. Однако действия относительно внешней среды берет на себя ОЭ, а ОИ прячется за его спиной. Это положительно сказывается на устойчивости системы. Система надежная. 6. Субъективный интерналист (СИ) и субъективный экстерналист (СЭ). Оба не будут осознавать друг друга и откликаться друг на друга. СЭ попытается использовать СИ в собственных интересах, но СИ не будет чувствителен к его усилиям и не откликнется на них. Со временим партнеры будут Все более удаляться друг от друга. Надежность системы низкая. Пары из одной и той же ячейки 7. Два субъективных экстерналиста (СЭ - СЭ). Каждый будет рассматривать внешнюю проблемы с точки зрения влияния на самого себя, и каждый попытается управлять другим для ее решения. Но оба останутся нечувствительными и не будут откликаться на усилия друг друга. Не решаются внутренние проблемы. Все же они будут соперничать и сотрудничать ради контроля над социальными ситуациями, которыми каждый из них попытается управлять в своих собственных интересах. Надежность системы средняя. 8. Два объективных интерналиста (ОИ - ОИ). Каждый будет пытаться адаптироваться для решения общей проблемы. Они будут сознающей окружение, но пассивной парой. Надежность системы высокая. 6 9. Два субъективных интерналиста (СИ - СИ). Оба нечувствительны друг к другу, почти не будут взаимодействовать. Каждый оставит другого в покое и будет рад, что и его оставили в покое. По отношению к окружению пара пассивна. Надежность системы средняя. 10. Два объективных экстерналиста (ОЭ - ОЭ). Каждый будет чувствителен к своему партнеру и попытается его изменить для решения совместных проблем. Но ни один не будет откликаться на такие усилия. Будут совместные поиски решения проблем в изменении своего окружения при соперничестве между собой. Надежность системы высокая. Тройки и семейства Пара индивидов, в отношениях между которыми возникли трудности, может найти выход в присоединении к себе еще одного (рис. 3) или нескольких лиц. В семьях это происходит, разумеется, при рождении детей. При этом можно ожидать, что обстоятельства будут так влиять на ребенка, чтобы у него сформировалась личность, приближающая семью к равновесию. Причем сам ребенок будет тем ближе к центру инверсии, чем устойчивей пара его родителей. Таким образом, существует своеобразная генетика личности: определенные комбинации типов родителей создают определенные типы детей. 1,0 (ОЭ) (ОИ) Объектоверт В D G E F А C Субъектоверт (СЭ) (СИ) 1,0 Интерналист Экстерналист 1,0 Рис. 3. Три индивида в пространстве личности. 1. Объективно интерналистическая семья (ОИ) будет вероятно, чувствительна к нуждам своих членов и члены семьи, вероятно, адаптируются к нуждам друг друга. Они будут приносить коллективные жертвы ради тех, кто больше нуждается в поддержке. Невмешательство в личную жизнь будет высоко цениться и станет достоянием всех членов семьи. Такое семейство будет сравнительно мало общаться с друзьями и знакомыми. Но в такой семье будут много читать, будет интерес к происходящему вокруг, но без попыток управлять этими событиями. Надежность семьи высокая. Мой дом – моя крепость. 2. Субъективно экстерналистическая семья (СЭ) будет менее чувствительна к нуждам своих членов, а члены – более склонны управлять друг другом. Стремление к обособленной личной жизни. Характерна меньшая зависимость друг от друга, но активная совместная деятельность. Чаще общение со знакомыми, в широком круге общения преобладают знакомые, а не близкие друзья. Свойственно увлечение активными видами отдыха (прогулки, пикники). Надежность семьи средняя. 7 3. Субъективно интерналистическая семья (СИ) будет иметь много общих черт с монастырем. Семья будет всячески избегать контактов с окружением, ее члены будут мало взаимодействовать друг с другом. Надежность семьи средняя. 4. Объективно экстерналистическая семья (ОИ) во многом напоминает живущую в одном помещении общину. К обособленной личной жизни никто не стремится, зато будет много общения, взаимовлияния и групповой деятельности. Это будет экстенсивная группа. Надежность семьи высокая. 2. Основы расчета надежности невосстанавливаемых систем. 2.1. Расчета надежности невосстанавливаемых систем при основном соединении элементов. Основное соединение элементов – последовательное соединение элементов, когда отказ хотя бы одного элемента приводит к отказу всей системы. Структурная схема системы с основным соединением элементов приведена на рис. 2.1.1. Рис. 2.1.1. Структурная схема системы с основным соединением элементов. Будем считать, что отказы элементов – события случайные и независимые. Обозначим вероятность отказа i-го элемента системы на интервале времени (0, t) как qi (t ) . В связи с тем, что отказ и работоспособность i-го элемента образуют полную группу событий, то pi (t ) + qi (t ) = 1 , (2.1.1) где pi (t ) - вероятность нахождения i-го элемента в работоспособном состоянии на интервале (0, t). Для системы с основным соединением элементов вероятность безотказной работы за время t можно определить как произведение вероятностей безотказной работы всех элементов: n P (t ) = ∏ pi (t ) (2.1.2) i =1 В частном случае, если все элементы одинаковы, выражение (2.1.2) принимает вид: P (t ) = [ pi (t )] n (2.1.3) В общем случае вероятность отказа системы на интервале (0, t), учитывая формулы (2.1.1) и (2.1.2) может быть определенная следующим образом: n Q (t ) = 1 − ∏ pi (t ) (2.1.4) i =1 8 или n Q (t ) = 1 − ∏ (1 − qi (t )) (2.1.5) i =1 Статистические данные свидетельствуют о том, что отказы типовых элементов информационных систем для нормального периода эксплуатации, т. е. до возникновения износовых отказов, подчиняются экспоненциальному закону. Для экспоненциального закона распределения вероятность отказа элемента системы может быть записана в виде: qi (t ) = 1 − e − λit , (2.1.6) где λi - интенсивность отказа i-го элемента. Для тех же условий вероятности безотказной работы элемента системы, с учетом (2.1.1) и (2.1.6.), равна: qi (t ) = e − λit (2.1.7) Тогда с учетом (2.1.6) и (2.1.7) выражения (2.1.2) и (2.1.5) приобретают вид: n P (t ) = ∏ e −λit i =1 (2.1.8) и n Q (t ) = 1 − ∏ (1 − (1 − e −λit )) (2.1.9) i =1 или Q (t ) = 1 − e − λt , (2.1.10) n где λ = ∑ λi - интенсивность отказов системы. i =1 Таким образом, сравнивая выражения (2.1.6) и (2.1.10), можно сделать вывод, что системы с основным соединением элементов сохраняется экспоненциальная модель отказов, аналогичная модели отказов отдельных элементов системы. Показатель безотказной работы системы в течении заданного времени для оценки надежности системы является основным (формулы (2.1.2), (2.1.3), (2.1.8)). Однако, в ряде случаев желательно определение величины среднего времени безотказной работы системы T 0 . Для оценки величины T 0 можно воспользоваться следующей формулой: ∞ T 0 = ∫ P (t )dt (2.1.11) 9 Для рассматриваемого случая (экспоненциальная модель отказов) средне время безотказной работы системы равно: ∞ T 0 = ∫ e −λt dt = − e − λt λ ∞ = 1 (2.1.12) λ Если проанализировать выражения (2.1.2), (2.1.3), (2.1.8), (2.1.11), (2.1.12), то можно сделать вывод, что включение в структуру системы хотя бы одного ненадежного элемента резко снижает надежность системы. Таким образом, для повышения надежности информационной системы с основным соединением элементов в ее структуру наиболее рационально включать равнонадежные элементы. Пример расчета надежности системы В структуру информационных систем включены (последовательно): информационное устройство, устройство управления исполнительное устройство. Каждое устройство включает в себя по N = 10 4 единиц одинаковых элементов, для которых определены средние интенсивности отказов, соответствующих интенсивности отказов индикаторов ( λ1 ), электронных схем ( λ2 ) и микродвигателей ( λ3 ). Система 1: λ1 = 2 * 10 −8 , λ2 = 1 * 10 −7 , λ3 = 3,7 * 10 −7 . * * Система 2: λ1 = 2 * 10 −8 , λ2 = 13,7 * 10 −7 , λ3 = 3,7 * 10 −7 . Требуется определить характеристики надежности: 1. Вероятность безотказной работы каждой из систем в течении 200 часов. 2. Среднее время их безотказной работы. а также проанализировать результаты расчета надежности. Порядок расчета: 1. Определяем среднюю информационные системы: * интенсивность отказов устройств, входящих в - λ1 * N = 2 *10 −8 *10 4 = 0,2 * 10 −3 час −1 (для первой и второй системы), - λ2 * N = 1 * 10 −7 * 10 4 = 10 −3 час −1 (для первой системы), * λ2 * N = 13,7 * 10 −7 * 10 4 = 13,7 * 10 −3 час −1 (для второй системы), - λ3 * N = 3,7 * 10 −7 * 10 4 = 3,7 * 10 −3 час −1 (для первой и второй системы). 2. Определяем среднюю интенсивность отказов для каждой из систем: m =3 λ0 = ∑ λi * N = 0,2 * 10 − 3 + 10 − 3 + 3,7 * 10 − 3 = 4,9 * 10 − 3 час −1 , i =1 m =3 λ0 = ∑ λi * N = 0,2 * 10 − 3 + 13,7 * 10 − 3 + 3,7 * 10 − 3 = 17,6 * 10 − 3 час −1 . * * i =1 3. Определяем характеристики надежности для каждой из систем: −3 P (t = 200час) = e −200*λ0 = e −200*4, 9*10 ≅ 0,373 10 * −3 P * (t = 200 час ) = e −200*λ0 = e −200*17,6*10 ≅ 0,03 T0 = * T0 = 1 λ ≅ 200 час. 1 λ* ≅ 56 час. 4. Сравнение характеристик надежности систем показывает, что уменьшение (примерно на порядок) надежности одного из устройств систем ( λ*2 > λ2 ) приводит к снижению надежности системы в целом (к снижению вероятности безотказной работы ( P (t ) P * (t ) ) примерно на порядок, к уменьшению примерно в 4 раза среднего времени безотказной работы ( T 0 T 0* )). 2.2. Расчет надежности невосстанавливаемых систем при общем резервировании. 2.2.1 Постоянное включение резерва. Э10 Э20 Эi0 Эn0 Вых Вх Э11 Э21 Эi1 Эn1 Э1j Э2j Эij Эnj Э1m Э2m Эim Эnm Рис. 2.2.1.1. Структурная схема системы при общем резервировании. Как видно из рис. 2.2.1.1 система с основным (последовательным) включением элементов n элементов ( э10 , э20 ,... эn 0 ) резервируются m аналогичными системами (m – кратность резервирования). В случае отказа любого элемента системы (основной цепи) система заменяется резервной. Вероятности безотказной работы элементов систем Pij (t ) известны. Требуется определить вероятность безотказной работы системы при общем резервировании POP (t ) и среднее время безотказной работы TOP . Определение выражения для оценки вероятности безотказной работы рассматриваемой системы проведем в два этапа: 11 1. Вероятность события, что все элементы j-ой цепочки находятся в работоспособном состоянии, равна: n Pj (t ) = ∏ Pij (t ) (2.2.1.1) i =1 2. Вероятность события, что хотя бы один элемент j-ой цепочки не работает, равна: n q1 j = 1 − ∏ Pij (t ) (2.2.1.2) i =1 3. Вероятность события, что хотя бы один элемент в каждой из m цепочек не работает, равна: m n j =0 i =1 q1m = ∏ (1 − ∏ Pij (t )) (2.2.1.3) 4. Вероятность события, что хотя бы одна цепочка работает, (вероятность безотказной работы системы) равна: m n j =0 i =1 POP = 1 − ∏ (1 − ∏ Pij (t )) (2.2.1.4) Аналогичным образом найдем выражение для определения вероятности безотказной работы системы при экспоненциальном законе распределения отказов элементов системы – pi (t ) = e n n i =1 i =1 − λit : Pj (t ) = ∏ e − λi t = e − λ0t , где λ0 = ∑ λi (2.2.1.5) 2. q1 j = 1 − e − λ0t (2.2.1.6) 3. q1m = (1 − e − λ0t ) m +1 (2.2.1.7) 4. POP (t ) = 1 − (1 − e − λ0t ) m +1 (2.2.1.8) 1. Среднее время безотказной работы системы определим для условия экспоненциального закона распределения отказа элементов: ∞ ∞ TOP = ∫ P (t )dt = ∫ (1 − (1 − e − λ0t ) m +1 )dt (2.2.1.9) В результате интегрирования этого выражения путем использования подстановки z = 1 − e определяем окончательное выражение: − λ0t 12 TOP = 1 λ0 m 1 ∑1+ i (2.2.1.10) i =0 или m 1 , (2.2.1.11) i =0 1 + i где T 0 - среднее время безотказной работы нерезервируемой системы. Из анализа полученных выражений следует, что с увеличением кратности резервирования (m>1) время безотказной работы растет все медленней. Поэтому общее резервирование целесообразно при небольшой кратности резервирования (m=1;2). TOP = T 0 ∑ 2.2.2 Включение резерва замещения. При резервировании замещением резервные элементы подключаются на место основного после его отказа и принимают на себя его функции. Аналитические методы исследования характеристик надежности при этом довольно громоздки. Поэтому на практике обычно ограничиваются рассмотрением случая, когда наработка до первого отказа элемента в системе подчиняется экспоненциальному закону распределения, однако, учитывается, что в общем случае интенсивности отказов для основной ( λ0 ) и резервных ( λ1 ) элементов различны ( λ0 ≥ λ1 ). Граф состояний и возможных переходов системы, состоящей из основной цепи при m – кратном резервировании, представлен на рис 2.2.2.1, где состояние S 0 - основная и все резервные цепи работоспособны, состояние S 1 - отказ одной резервной цепи, состояние S 2 - отказ двух резервных цепей, … , состояние S m - отказ основной и всех резервных цепей. λ0 0 + m λ1 0 + ( m −1) λ1 0 + ( m +1−i ) λ1 0 + ( m −i ) λ1 S 0 λ → S 1 λ → ... λ  → S i λ → ... → S m +1 Рис. 2.2.2.1. Граф состояний и возможных переходов системы при включении резерва замещением. Обычно предполагается, что случайные процессы в системе являются Марковскими, т.е. у которых для каждого момента времени вероятность любого состояния системы в будущем зависит только от состояния системы в исходный момент времени и не зависит, от того каким путём она пришла в это состояние. Тогда информация о вероятностях перехода системы в разные состояния позволяет определить вероятность каждого из возможных состояний системы. Для определения каждого из возможных состояний системы используется система дифференциальных уравнений Колмогорова. Для пояснения природы возникновения этих уравнений приведём следующие преобразования. 1). P (t + ∆t ) = P (t ) ⋅ (1 − q(∆t )) - вероятность, того что система в течение времени ∆t сохранит работоспособность (2.2.2.1.) (2.2.2.2.) 2). P (t + ∆t ) − P(t ) ≅ − P (t ) ⋅ λ ⋅ ∆t , при λ ⋅ ∆t → 0 P(t + ∆t ) − P(t ) 3). = −λ ⋅ P(t ) , при ∆t → 0 (2.2.2.3.) ∆t dP(t ) 4). = −λ ⋅ P(t ) (2.2.2.4.) dt 13 Таким образом, изменение вероятности нахождения системы в некотором состоянии определяется произведением величины потока отказов в системе и величины исходной вероятности нахождения системы в этом состоянии. Для примера состояний, приведённого на рис. 2.2.2.1., система дифференциальных уравнений (2.2.2.5.) Колмогорова имеет следующий вид:         dPi (t ) = [λ 0 + (m + 1 − i ) ⋅ λ1 ] ⋅ Pi −1 (t ) − [λ 0 + (m − i ) ⋅ λ1 ] ⋅ Pi (t )  dt  ...........................................................................................................   dPm +1 (t )  = λ 0 Pm +1 (t )  dt Начальные _ условия : P0 (t ) = 1; P1 (t ) = L = Pi (t ) = L = Pm +1 (0) = 0   dP0 (t ) = −(λ 0 + m ⋅ λ1 ) ⋅ P0 (t ) dt dP0 (t ) = (λ 0 + m ⋅ λ1 ) ⋅ P0 (t ) − [λ 0 + (m − 1) ⋅ λ1 ] ⋅ P1 (t ) dt ........................................................................................................... (2.2.2.5.) После преобразования этой системы уравнений к системе алгебраических уравнений и соответствующих преобразований определяются показатели надёжности системы: i i −1  ma λ0 −λ0 ⋅t  −λ1⋅t    i ⋅ 1 + ∑ ⋅ 1 − e P (t ) = e   , где ai = ∏  j +   λ1 j =0  i =0 i!  T3 = системы. ∞ m 1 = ⋅ P t dt T ( ) 0 ∑ ∫ i =01 + i ⋅ k , где k= λ1 λ0 , T0 = 1 λ0    (2.2.2.6.) - среднее время безотказной работы нерезервированной (2.2.2.7.) Если принять P (t ) = e T3 = λ1 = 0 , то получим выражение для системы с ненагруженным резервированием: −λ0 ⋅t m +1 m (λ ⋅ t )i ⋅∑ 0 i =0 i! (2.2.2.8.) (2.2.2.9.) λ0 Таким образом, среднее время безотказной работы при ненагруженном резервировании сравнению со средним временем безотказной работы нерезервированной системы в (m + 1) раз. Если в выражениях (2.2.2.6) и (2.2.2.7) принять, что (λ1 = 0) возрастает по λ1 = λ 0 , то после некоторых преобразований получим формулы (2.2.1.8) и (2.2.1.9), описывающие работу системы с нагруженным резервированием. Пример расчёта надёжности системы. (λ0 Для условий примера расчёта 2.1.1. требуется оценить надёжность системы для случаев общего резервирования = λ1 ) и резервирование замещением с ненагруженным резервом (λ1 = 0 ) при кратности резервирования m = 1 . 1. Определим характеристики надёжности системы при общем резервировании: 14 2 −3⋅200   − ⋅ 4 , 9 10 = 1 − 1 − e  = 0,6 ;   m+1 2 −3⋅200   −λ0*⋅t   17 , 6 10 − ⋅ *  P (t ) = 1 − 1 − e = 1 − 1 − e  ≅ 0,06 ;     m 1 = 200 ⋅ (1 + 0,5) = 300 ч. Top = T0 ⋅ ∑ i=01 + i m 1 = 56 ⋅ (1 + 0,5) ≅ 84 ч. T *op = T0* ⋅ ∑ i=01 + i −λ ⋅t P (t ) = 1 − 1 − e 0    m+1 2. Определим характеристики надёжности при резервировании замещением с ненагруженным резервом: ) ( m (λ ⋅ t )i −λ ⋅t ⋅∑ 0 = e 0 ⋅ (1 + λ 0 ⋅ t ) = 0,373 ⋅ 1 + 4,1 ⋅ 10 −3 ⋅ 200 ≅ 0,74 i =0 i! i *0 ⋅t m λ*0 ⋅ t * * λ − P (t ) = e = e −λ 0 ⋅t ⋅ 1 + λ*0 ⋅ t = 0,3 ⋅ 1 + 17,6 ⋅ 10 −3 ⋅ 200 ≅ 0,13 ⋅∑ i =0 i! m +1 T3 = = 2 ⋅ 200 = 400 ч. P (t ) = e −λ0 ⋅t ( ) ( ) ) ( λ0 T *3 = m +1 = 2 ⋅ 56 = 112 ч. λ*0 2.3 Расчёт надёжности систем с поэлементным резервированием. Структурная схема с поэлементным резервированием приведена на рис. 2.3.1. i-я секция э10 э20 эi 0 эn 0 э11 э21 эi1 эn1 Вх. Вых. э1 j э2 j эij эnj э1m э2 m эim эnm Рис. 2.3.1. Структурная схема с поэлементным резервированием. Система представляет собой последовательное соединение n секций, каждая из которых содержит m + 1 параллельно соединённых элементов. Отказ в работе секции происходит, если откажут все m + 1 элементов. Система работоспособна, т.е есть путь от входа к выходу, если работоспособны все n секций. Определение выражения для оценки вероятности безотказной работы приведём в три этапа: 1. Вероятность отказа работы всех m элементов i − й секции равна: 15 qim = 2. ∏ [1 − pij (t )] m j =0 Вероятность работы хотя бы одного элемента i − й секции (или вероятность работы i − й секции): Pi1 = 1 − 3. (2.3.1.) ∏ [1 − pij (t )] m (2.3.2.) j =0 Вероятность работоспособности всех n секций системы (или вероятность безотказной работы системы ) равна: [ ] n  m  Pэр = ∏ 1 − ∏ 1 − pij (t )   i =1  j =0 При равнозначности всех элементов в каждой секции p { n m+1 Pэр = ∏ 1 − 1 − pi (t ) i =1 [ ] (2.3.3.) ij = pi выражение (2.3.3.) можно представить в виде: } (2.3.4.) Для экспонциального закона распределения отказов элементов P = e i −λi ⋅t выражение (2.3.4.) приобретает вид: m+1  n   −λi ⋅t    Pэр = ∏ 1 − 1 − e     i =1    (2.3.5.) Вероятность безотказной работы системы при поэлементном резервировании выше вероятности безотказной работы системы при общем резервировании (формула 2.2.1.8.). Пример расчёта надёжности системы при поэлементном резервировании. Для условий примера расчёта (2.1.1 ) оценим характеристики надёжности при m = 1 , n = 3 , считая, что каждый элемент включает в себя 10 системы равна: 4 однотипных (последовательных соединённых) звеньев. Вероятность безотказной работы m +1   2 2 n   −λi ⋅t  −3⋅200     −3⋅200    − ⋅ , 2 10 − 10       Pэр = ∏ 1 − 1 − e = 1 − 1 − e  ⋅ 1 − 1 − e  ⋅            i =1        2  −3⋅200    3 , 7 10 − ⋅ ⋅ 1 − 1 − e   = 1 ⋅ 0,96 ⋅ 0,73 ≅ 0,7       m+1  2  n   −λi*⋅104⋅t  3   − ⋅ ⋅ 13 , 7 10 200   *   P эр = ∏ 1 − 1 − e   ⋅ 0.73 = 1 ⋅ 0,14 ⋅ 0,73 ≅ 0,1 .  = 1 ⋅ 1 − 1 − e     i =1        Для сравнения результаты расчёта надёжности невосстанавливаемых систем без резервирования, при общем резервировании, при включении резерва замещением, а также при поэлементном резервировании представлены в таблице 2.3.1. (для двух вариантов информационных систем №1 и №2, при кратности резервирования m = 1 ). 16 Табл. 2.3.1. Показатели надёжности Вероятность безотказной Среднее время безотказной работы работы №1 №2 №1 №2 0,37 0,03 200 56 0.6 0,06 300 84 0.7 0.1 0,74 0,13 400 112 Характер резервирования Резервирования нет Общее резервирование Поэлементное резервирование с нарушением резерва Резервирование замещением с ненарушенным резервом Как видно из табл. 2.3.1. наилучшие показатели надёжности имеет система, резервирование которой осуществляется с ненагруженным резервом. 3.Основы расчёта надёжности восстанавливаемых систем. 3.1. Оценка надёжности систем с использованием марковских процессов. Рассмотрим методику определения надёжности системы, основанную на расчёте вероятностей состояний системы, описываемой марковским процессом перехода из одного состояния в другое. Основные положения методики поясним на примеры системы, структура которой представлена на рис.3.1, а граф состояний приведён на рис.3.2. На рис.3.2 λ 01 и λ12 - интенсивности отказов элементов систем, а µ10 и µ 21 интенсивность восстановления работоспособности элементов системы. Восстановленная система 1 Вх. Вых. 2 Рис. 3.1. Структурная схема восстанавливаемой системы. λ 12 01 λ→    → S 0 ←   S ←    S2 1 µ µ 10 21 рис. 3.2. Граф состояний и возможных переходов восстанавливаемой системы. Как видно из рис.3.2 общее число состояний системы равно трём: • Состояние S 0 - два элемента, составляющих систему работоспособны. • Состояние S1 - один из элементов системы отказал. • Состояние S 2 - оба элемента системы отказали. Система дифференциальных уравнений (3.1.) для графа, приведённого на рис.3.2., имеет следующий вид: dP0  = −λ 01 ⋅ P0 (t ) + µ10 ⋅ P1 (t )  dt  dP1  = λ 01 ⋅ P0 (t ) − (λ12 + µ10 ) ⋅ P1 (t ) + µ 21 ⋅ P2 (t ) dt  dP2  = − µ 21 ⋅ P2 (t ) + λ12 ⋅ P1 (t )  dt  (3.1) 17 Решение системы уравнений 3.1. существенно упрощается, если учесть, что рассмотренный процесс является стационарным, для которого производные dPi можно принять равными нулю, т.е. вероятности нахождения системы в dt каждом из состояний не меняются. Тогда система дифференциальных уравнений 3.1. переходит в следующую систему алгебраических уравнений (3.2.): 0 = −λ 01 ⋅ P0 + µ10 ⋅ P  0 = λ 01 ⋅ P0 − (λ12 + µ10 ) ⋅ P1 + µ 21 ⋅ P2   0 = − µ 21 ⋅ P2 + µ12 ⋅ P1   1 = P0 + P1 + P2 (3.2) Последнее уравнение необходимо потому, что первые три уравнения сводятся к двум. Решение системы уравнений 3.2. даёт: P0 = 1  λ 01 λ ⋅λ 1 + +  µ10 µ 21 ⋅ µ10 P 1 = P0 ⋅ λ 01 µ 01 P2 = P0 ⋅ λ 01 ⋅ λ12 µ 21 ⋅ µ10    Результаты решения системы уравнений типа (3.2.) для информационной системы, число состояний которой равно n , может быть записано следующим образом:  λ λ 01 ⋅ λ12 L λ n −1,n λ ⋅λ P0 = 1 + 01 + 01 12 + L + µ n ,n −1 L µ 21 ⋅ µ10  µ10 µ 21 ⋅ µ10 P 1 = P0 ⋅     −1 λ 01 µ 01 …………………………………………………… Pn = P0 ⋅ λ 01 ⋅ λ12 L λ n −1,n µ n ,n −1 µ 21 ⋅ µ10 Таким образом, результаты решения системы уравнений типа (3.2.) непосредственно определяются видом графа состояний и переходов. Пример оценки надёжности восстанавливаемой системы. Система технического зрения робота резервируется в случае её отказа аналогичной системой, выполняющей функции контроля, а система вышедшая из строя восстанавливается. Интенсивность отказов равна λ = 4 ⋅ 10 −5 ч −1 , а −2 −1 интенсивность восстановления µ = 10 ч . Требуется определить вероятность работоспособности робота, т.е. возможность получения роботом зрительной информации. Решение: 1. Составляет граф состояний и переходов: 18 λ 12 01 λ→    → S 0 ← S   ←   1 µ µ  S2 10 21 Состояние S 0 - системы технического зрения работоспособны. Состояние S1 - одна из систем неработоспособна. 2. Состояние S 2 - обе системы неработоспособны. Находим интенсивности переходов из одного состояния в другое: λ01 = 2 ⋅ λ = 2 ⋅ 4 ⋅ 10 −5 = 8 ⋅ 10 −5 ч −1 λ12 = λ = 4 ⋅ 10 −5 = 10 −5 ч −1 µ 21 = 2µ = 2 ⋅ 10 − 2 ч −1 µ10 = µ = 10 − 2 ч −1 3. Находим вероятность нахождения робота в работоспособном состоянии.  λ λ ⋅λ P0 = 1 + 01 + 01 12  µ10 µ 21 ⋅ µ10    −1 ≅ 0,98 19 P 1 = P0 ⋅ λ 01 ≅ 0.01 µ 01 P = P0 + P1 ≅ 0,99 Вероятность отказа системы равна: Q = 1 − P ≅ 0,01 3.2. Оценка надёжности систем с использованием распределения Пуассона. При поэлементном распределении отказов согласно закону Пуассона вероятность одного отказа равна: q(t )1 = λ ⋅ t ⋅ e −λ⋅t Вероятность n отказов: q n ( λ ⋅ t )n −λ⋅t ⋅e (t ) = n! m (λ ⋅ t )n − λ ⋅ t ⋅e (t ) = ∑ n≤m n = 0 n! ∞ (λ ⋅ t )n ⋅ e − λ ⋅ t Вероятность отказов > m элементов: q (t ) = ∑ n>m n = m + 1 n! Вероятность отказов ≤ m элементов: q Предполагается, что если нет в запасе исправных элементов, то выход из строя одного элемента ведёт к нарушению работы всей системы. Пример планирования числа запасных элементов. Вариант А. Число отказов системы за время пополнения запаса элементов системы (t 3 ) равно n = λ ⋅ t3 = 3 . Требуется определить необходимое число элементов m , входящих в комплект запасных элементов для обеспечения вероятности безотказной работы системы P (t ) ≥ 0,99 . Решение: В соответствии с вероятностями (3.2.4.)составляем табл. 3.2.1. m 5 6 7 8 9 q n>m (t ) 0,1847 0,0839 0,0335 0,0119 0,0038 Табл. 3.2.1. 10 0,0011 Как видно из табл. 3.2.1 поставленному требованию соответствует комплект запасных элементов при m = 9 , тогда P (t ) = 1 − Qn>m (t ) = 1 − 0,0038 = 0,9962 > 0,99 Вариант В. Дано: λi = 5 ⋅ 10 −6 ч −1 • Интенсивность отказов элементов системы • число элементов в системе N = 60 (элементы соединены последовательно) • период пополнения комплекта запасных элементов t 3 = 8 ⋅ 10 ч 3 Требуется: Определить требуемое число запасных элементов m для вероятности отказа системы q (t ) ≤ 0,01 Решение: λ = λi ⋅ N = 5 ⋅ 10 −6 ⋅ 60 = 3 ⋅ 10 −4 ч −1 1. Определим суммарную интенсивность отказов: 2. Определим среднее число отказов системы за время t 3 : n = 3 ⋅ 10 − −4 ⋅ 8 ⋅ 10 3 = 2,4 20 Используя, выражение (3.2.4.) получим: q 3. n>m=8 (t ) = 0,0033 < 0,01 4. Методы расчёта надёжности систем со сложной структурой. 4.1. Метод разложения по ключевым элементам. Существо метода заключается в том, что сложная структура заменяется несколькими более простыми структурами, сумма вероятностей работоспособных состояний которых равна вероятности нахождения исходной системы (со сложной структурой) в работоспособном состоянии. В основу метода положены следующие правила разложения сложной структуры: 1. В исходной структуре выбирается элемент с наибольшим числом связей с другими элементами системы, который будем называть элементом разложения с вероятностью безотказной работы Px . 2. В месте расположения элемента разложения делается замыкание, а элемент разложения подключается последовательно с исходной схемой. Получается первая структура. В месте расположения элемента разложения элемент разложения делается отрыв, а элемент разложения подключается аналогично 4.2., но с вероятностью безотказной работы 1 − Px . 3. ( ) Сумма вероятностей безотказной работы первой структуры P1 и второй структуры P2 определяет вероятность безотказной работы исходной системы со сложной структурой. В случае необходимости: когда возникает трудность в определении вероятностей вновь сформированных систем, разложение проводится многократно. 4. 5. Пример разложения системы со сложной структурой. Требуется, используя метод разложения по ключевым элементам, оценить надёжность системы, представленной на рис. 4.1.1. Вероятности нахождения элементов в работоспособном состоянии соответственно равны: Pa = P = Pc = P = Pe = 0,8 . b d a Вх. d .Вых. c b e Рис. 4.1.1. Исходная сложная структура. Решение: 1. Примем в качестве элемента разложения – элемент c , тогда после замыкания схемы элемента c в соответствии с п.4.2. метода получаем первую структуру (рис. 4.1.2). a d Вх. 2. в месте расположения Вых. b e Рис. 4.1.2. Первая упрощённая структура. В соответствии с 4.3. метода в месте разложения элемента c делаем обрыв и получаем вторую структуру (рис. 4.1.3). a Вх. d Вых. b e Рис. 4.1.3. Вторая упрощённая структура. 3. Вероятности безотказной работы упрощённых структур, представленных на рис. 4.1.2. и рис. 4.1.3., с учётом п.2 и п.3 метода равны: 21 4. ( )( ) P1 = Pc ⋅ Pa + P − Pa ⋅ P ⋅ P + Pe − P ⋅ Pe b b d d P2 = (1 − Pc ) ⋅ Pa ⋅ P + P ⋅ Pe − Pa ⋅ P ⋅ P ⋅ Pe d b d b 5. ( ) Тогда, после подстановки истинных значений вероятностей безотказной работы элементов системы, получим: P1 = 0,736 , P2 = 0,176 Вероятности безотказной работы исходной сложной системы, представленной на рис.4.1.1. равна: P = P1 + P2 ≅ 0,91 . 4.2. Метод эквивалентности работоспособных состояний. Рассмотрим условие эквивалентности структур типа “треугольник” и “звезда”, которые представлены на рис. 4.2.1. и рис. 4.2.2. 2 a 1 с 3 b Рис. 4.2.1. структура треугольник. 1 y 2 z 3 x Рис. 4.2.2. Структура звезда. Чтобы структура типа “звезда” была эквивалентна структуре типа “треугольник”, необходимо выполнение следующих равенств: (1 → 2)a ∨ bc = xy,  (1 → 3)b ∨ ac = xz,  (2 → 3)c ∨ ab = yz, (4.2.1.) a, b, c, x, y, z обозначают события, состоящие в том, что элементы находятся в работоспособном состоянии. Из выражений (4.2.1.) следует, что вероятности работоспособного состояния цепей (1 → 2 ) , (1 → 3) , (2 → 3) для “треугольника” и “звезды” должны быть равны, поэтому получаем систему уравнений (4.2.2): Pa + P ⋅ Pc − Pa ⋅ P ⋅ Pc = Px ⋅ Py  b b  P + Pa ⋅ Pc − Pa ⋅ P ⋅ Pc = Px ⋅ Pz  b b  Pc + Pa ⋅ P − Pa ⋅ P ⋅ Pc = Py ⋅ Pz  b b  (4.2.2.) 22 Для случая, когда Pa = P = Pc = PТ и Pa = P = Pc = Pз система уравнений (4.2.2.) упрощается: b b P 1Т = P 2 Т = P 3 Т = P 2 з (4.2.3.) Пример определение вероятности безотказного состояния мостиковой схемы. Требуется определить вероятность безотказного состояния мостиковой схемы (рис. 4.1.1.) методом эквивалентных состояний, если вероятность безотказного состояния всех элементов исходной системы равна: P = 0,8 . Решение: 1. Преобразуем группу элементов a, b и c , соединённых по схеме “треугольник” в “звезду” (рис. 4.2.3. и рис. 4.2.4.) Структура “треугольник” a d Вх. .Вых. с b e Рис. 4.2.3. Исходная сложная система. Структура “звезда” y Вх. d .Вых. x z e Рис. 4.2.4. Структура, в которой группа элементов (a, b, c ) исходной структуры, образующих структуру “треугольник” (рис. 4.2.3.) преобразована в структуру “звезда”. 2. При вероятности безотказной работы всех элементов Px = Py = Pz = Pз , тогда численное значение этой вероятности равно: ( условии, 1 2 что ) структуры “звезда” равны 3 Pз = PТ + PТ − PТ = 0,96 . 3. Вероятность ( безотказной работы ) исходной сложной системы равна: P = Px ⋅ Py ⋅ P + Pz Pe + Py ⋅ P ⋅ Pe ⋅ Pz = 0,91 . Такой же результат был получен в примере 4.1.1. d d 4.3. Метод преобразования логических функций работоспособности. Последовательность действий этого метода следующая: 1. Формулируются условия работоспособности системы. 2. На основе сформулированных условий записывается логическая функция работоспособности Fл . 3. В случае необходимости функция Fл преобразуется к виду, удобному для проведения дальнейших операций (в 4. основном с целью её упрощения). Функция Fл преобразуется в алгебраическую функцию Fа , в которой простые события (высказывания) заменяются их вероятностями. 23 5. В полученное выражение подставляются числовые значения вероятностей состояний элементов, и определяется вероятность нахождения системы в работоспособном состоянии. Пример расчёта надёжности. Требуется: Определить вероятность работоспособного состояния системы, структура которой представлена рис. 4.1.1., при условии, что вероятности нахождения всех элементов в работоспособном состоянии равны: Pa = P = Pc = P = Pe = 0,8 . b d Решение: 1. Условия работоспособности ситемы: Система работоспособна, если выполнено хотя бы одно из следующих условий: • Работоспособны элементы b, e • Работоспособны элементы a, c, e Работоспособны элементы b, c, d • 2. 3. Логическая функция работоспособности имеет следующий вид: Fл = (ad ) ∨ (be ) ∨ (ace ) ∨ (bcd ) Преобразуем исходную функцию Fл с целью исключения повторяющихся членов: − Fл = c(ad ∨ be ∨ ae ∨ bd ) ∨ c(ad ∨ be ) , далее упрощаем полученное выражение: − − Fл = c[a (d ∨ e ) ∨ b(e ∨ d )] ∨ c(ad ∨ be ) .В результате получаем: Fл = c[(a ∨ b ) ∨ (d ∨ e )] ∨ c(ad ∨ be ) . 4. Fл получаем Fа = c[(a + b − ab )(d + e − de )] + (1 − c )(ad + be − adbe ) , На основе функции вероятностями: [( )( )] алгебраическую затем заменяем простые ( события P (t ) = Pc ⋅ Pa + P − Pa ⋅ P ⋅ P + Pe − P ⋅ Pe + (1 − Pc ) ⋅ Pa ⋅ P + P ⋅ Pe + Pa ⋅ P ⋅ P ⋅ Pe b b d d d b d b 5. Fа : функцию их ) Вероятность безотказной работы системы равна: P (t ) = 0,91 В результате использования метода преобразования логических функций работоспособности для расчёта надёжности мостиковой схемы получена формула для расчёта вероятности безотказной работы этой схемы, полностью совпадая с аналогичной формулой при использовании метода разложения по ключевым элементам. Это ещё раз подтверждает факт, что конечный результат расчёта надёжности сложных систем не зависит от метода расчёта надёжности, выбор которого сказывается только на характере и сложности процесса оценки надёжности систем. 5. Принципы технической диагностики надёжности информационных систем. 5.1. Метод обработки изображений с использованием булевых функций. Задача обработки изображений заключается в преобразовании изображения A → a (i, j ) в изображение B → b(i, j ) с использованием булевой функции F : B = F ( A) (5.1.1.) или a(i, j ); a i + τ ; j + τ * ; a i + τ ; j + τ * ,L, a i + τ , j + τ * , { j} = 0,L , N ; {} i = 0, L, M ;     1 1  2 2  s s        b(i, j ) = F    τ , τ * = 0,±1,L ,± s    { } Конкретный вид булевой функции определяется применительно к реальной задаче. 24 A. Выделение контура изображения. На рис. 5.1.1. приведено исходное изображение объекта A, а на рис. 5.1.2.- выделенный контур объекта, т.е. желаемый результат B после преобразования F. Для выделения правых столбцов (правых граничных точек строк) используем функцию: b ij (1) = aij ∧ ai′, j −1 (5.1.1.) На основе рпеобразования изображения (5.1.1.) выполняется операция логического умножения (конъюкция) при ( ij ) наложении на исходное изображение a его элементов влево на один элемент     нового изображения  a ′ i −1, j  , формируемого из исходного путём сдвига всех (τ * = −1) 1 и выполнения для этого изображения операции отрицания . Для выделения левых столбцов (левых граничных точек строк) выполняется анологичная операция для bij (2 ) τ * = 1 :   1 − = aij ∧ ai′, j +1 (5.1.2.) Для выделения верхних строк (верхних граничных точек строк) используем функцию: b ij (3 ) = aij ∧ ai′−1, j (5.1.3.) На основе преобразования изображения (5.1.3.) выполняется операция логического умножения (конъюкция) при ( ij ) наложении на исходное изображение a (     нового изображения  a ′ i, j −1  , формируемого из исходного путём сдвига всех ) его элементов влево на один элемент τ 1 = −1 и выполнения для этого изображения операции отрицания . Для выделения строк выполняются операции аналогичные (5.1.3.), для τ 1 = 1 : bij (4 ) = aij ∧ ai′+1, j (5.1.4.) В результате приведения преобразований исходного изображения (5.1.1.,5.1.2,5.1.3,5.1.4.) может быть получено окончательное выражение, обеспечивающее выделение контура исходного изображения, путём применения логического (1) (2 ) (3 ) (4 ) сложения (дизъюнкции): B = b ij ∨ b ij ∨ b ij ∨ b ij (5.1.5.) Как было показано ранее, этот результат показан на рис. 5.1.2. Как видно из полученного результата при преобразовании изображения (на основе использования приведённого алгоритма) выделяется как внешний, так и внутренний контур изображения. M . . . i . . . 2 1 1 1 1 1 1 2 . 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 . . . . . j . . . . . . Рис. 5.1.1. Исходное изображение объекта A. N M . . . i 1 1 1 1 1 1 1 1 1 1 1 1 1 1 25 . 1 1 1 1 . 1 1 1 1 1 . 1 1 1 1 2 1 1 1 1 1 1 0 1 2 . . . . . . j . . . . . . N Рис. 5.1.2. Выделенный внешний и внутренний контур изображения объекта A. B. Восстановление изображения. В результате воздействия различных помеховых сигналов изображение объекта может быть изменено, тогда возникает необходимость нахождения булевых функций, устраняющих помеховые воздействия. Приведём примеры выбора таких функций для элементарных помеховых воздействий с иллюстрацией характера преобразования изображений (рис. 5.1.3, рис. 5.1.4). Рис. 5.1.3. иллюстрирует устранение одиночного помехового воздействия на нулевом фоне a (i, j ) путём преобразования изображения в b(i, j ) на основе приведённой булевой функции. a (i, j ) i b(i, j ) → 1 i j j Рис. 5.1.3. Иллюстрация устранения одиночного помехового воздействия. ) ( { } 0, если a i + τ , j + τ * = 1, где τ ,τ * ∈ {0,±1} ∑  b(i, j ) =  τ ,τ * a(i, j ) − в _ остальных _ случаях  Рис. 5.1.4. иллюстрирует устранение помехового воздействия, вызванного двумя элементарными помехами, расположенными вблизи друг друга на нулевом фоне. a (i, j ) b(i, j ) 1 i 1 → i j j Рис. 5.1.4. Иллюстрация устранения сдвоенного помехового воздействия. ( ) { } 0, если ∑ a i + τ , j + τ * ≤ 2, где τ ,τ * ∈ {0,±1}  b(i, j ) =  τ ,τ * a(i, j ) − в _ остальных _ случаях  Рассмотренный алгоритм устраняет воздействие и одиночных помех. 26 Анализ способов построения алгоритмов устранения помеховых воздействий показывает, что возможность построения эффективных алгоритмов защиты от помех во многом зависит имеющихся предварительной информации о характере помеховых воздействий. 5.2. Алгоритм поиска неисправностей с использованием оптимизации на графах. Если информационная система может быть представлена в виде графа, то для решения задачи технической диагностики могут использоваться алгоритмы поиска кратчайшего пути, соединяющего две выделенные вершины исходного графа. При этом длина пути определяется как сумма длин отдельных дуг, составляющих этот путь, а длины дуг можно интерпретировать как некоторые затраты или весовые коэффициенты. Итерационный алгоритм, представленный Дейкстрой, считается одним из наиболее эффективных алгоритмов решения такой задачи. В этом алгоритме при поиске кратчайшего пути из вершины S в вершину E каждой вершине в ходе выполнения алгоритма присваивается число l ( x ) , равное длине кратчайшего пути из S в x включающего только окрашенные вершины. 1. Первый шаг: Положим: l1 (S ) = 0 , l ( x ) = ∞ а также (для всех x, не связанных с S ) и y = S ( y -последняя из окрашенных вершин), а также определить значения l для вершин, связанных с вершиной S . 2. Итерационны шаг: Для каждой неокрашенной вершины следующим образом пересчитать величину: l ( x ) = min l ( x ), l ( y ) + l ( x, y ) , где l ( x, y ) - длина дуги. Если l ( x ) = ∞ для всех неокрашенных вершин x , {i } i закончить процедуру алгоритма, т.к. в исходном графе отсутствуют пути из вершины S в неокрашенные вершины. В противном случае окрасить ту из вершин x , для которой величина l ( x ) является наименьшей. Кроме того i +1 окрашивается дуга, ведущая в выбранную на данном шаге вершину x . Положить y = x , т.е. окрасить вершину x . 3. Заключительный шаг: Если y = E , то закончить процедуру, т.к. кратчайший путь из вершины в вершину E найден. Это единственный путь из в E , составленный из окрашенных дуг, полученное решение обладает следующими свойствами. Окрашенные дуги образуют в исходном графе ориентированное дерево с корнем в вершине S . Это дерево называется деревом кратчайших путей. Единственный путь до любой из вершин x , принадлежащих дереву кратчайших путей, является кратчайшим путём между указанными вершинами. Если кратчайшему пути из вершины S в вершину Y ′ в дереве кратчайших путей принадлежит вершина Y ′′ , то часть этого пути, заключенная между Y ′ и Y ′′ , является кратчайшим путём между этими вершинами. Пример определение кратчайшего пути. Требуется определить кратчайший путь от вершины S до вершины E в графе, приведённом на рис. 5.2.1. методом Дейкстры. 4 a 4 b 7 S 2 E 4 3 2 c 3 d Рис 5.2.1. Ориентированное дерево кратчайших путей на графе с корнем в вершине. 27 Шаг 1: l1 (S ) = 0 , l1 (a ) = 4 , l1 (b ) = 7 , l1 (c ) = 3 , l1 (d ) = ∞ , l1 (e ) = ∞ , y = S , т.е. окрашена вершина S . Шаг 2: l 2 (a ) = min{l1 (a ), l1 (S ) + l (S , a )} = min{4,0 + 4} = 4 , l 2 (b ) = min{l1 (b ), l1 (S ) + l (S , b )} = min{7,0 + 7} = 7 l 2 (c ) = min{l1 (c ), l1 (S ) + l (S , c )} = min{3,0 + 3} = 3 , l 2 (d ) = min{l1 (d ), l1 (S ) + l (S , d )} = min{∞,0 + ∞} = ∞ , l 2 (E ) = min{l1 (E ), l1 (S ) + l (S , E )} = min{∞,0 + ∞} = ∞ , Окрашивается вершина c и дуга (S , c ) Шаг 3: l3 (a ) = min{l 2 (a ), l 2 (c ) + l (c, a )} = min{4,3 + ∞} = 4 , l3 (b ) = min{l 2 (b ), l 2 (c ) + l (c, b )} = min{7,3 + ∞} = 7 , l3 (d ) = min{l 2 (d ), l 2 (c ) + l (c, d )} = min{∞,3 + 3} = 6 , l3 (E ) = min{l 2 (E ), l 2 (c ) + l (c, E )} = min{∞,3 + ∞} = ∞ , Окрашивается вершина a и дуга (S , a ) Шаг 4: l 4 (b ) = min{l 3 (b ), l3 (a ) + l (a, b )} = min{7,4 + 4} = 7 , l 4 (d ) = min{l 3 (d ), l3 (a ) + l (a, d )} = min{6,4 + 4} = 6 , l 4 (E ) = min{l3 (E ), l3 (a ) + l (a, E )} = min{∞,4 + ∞} = ∞ , Окрашивается вершина d и дуга (S , d ) Шаг 5: l5 (b ) = min{l 4 (b ), l 4 (d ) + l (d , b )} = min{7,6 + ∞} = 7 l5 (E ) = min{l 4 (E ), l 4 (d ) + l (d , E )} = min{∞,6 + 2} = 8 Окрашивается вершина b и дуга (S , b ) Шаг 6: l 6 (E ) = min{l 5 (E ), l5 (b ) + l (b, E )} = min{8,7 + 2} = 8 , Окрашивается вершина E и дуга (S , E ) В результате, как показано на рис. 5.2.1. оплучено окрашенное дерево кратчайших путей. 5.3. Методы технической диагностики. 5.3.1. Метод потенциалов. Пусть имеется обучающая последовательность из m образцов, для которых справедлив диагноз Di . Тогда в качестве эталонного образца принять математическое ожидание выборки: 1 m (5.3.1.1.). xi0 = ∑ xij m j =1 Для процесса распознования предъявляемых (неизвестных) образцов, т.е. получения ответа на вопрос о их принадлежности к образцам с диагнозом Di , в методе потенциалов используется следуюc −a⋅ x − xi0 , где a > 0 и c > 0 (5.3.1.2.) щая дискрименантная (разделительная) функция: f i ( x ) = l По физическому смыслу дискрименантная функция (5.3.1.2.) представляет собой потенциал в точке x от источника (заряда) в точке xi0 . При этом константы a и c выбираются экспериментальным путём. Тогда алгоритм распознавания имеет следующий вид: ψ = 1,2,L, n;ψ ≠ i . x ∈ Di , если f i ( x ) > fψ ( x ) , где 29 Качество (надёжность) распознавания (при условии, что среди представленных образцов имеется только один объект с диагнозом Di ) может быть оценена следующим образом: n ∑ fψ (x ) ψ =1 эi x = 1 − k f i (x ) ( ) (5.3.1.3.). Решение о принадлежности образца x к диагнозу Di можно принять с заданной надёжностью, если эi x > э0 , (5.3.1.4.) k где э0 - установленный уровень качества распознавания. Если условия (5.3.1.4.) не выполняются, то для решения задачи распознавания требуется получения дополнительной информации, например, путём увеличения объёма выборки. ( ) Пример расчёта надёжности. Информационная система может находиться в одном из двух состояний ( D1 -исправное состояние, D2 - неисправное состояние). Эталонные образцы этих состояний x10 и x 20 , а предъявленная выборка для распознавания x (рис 5.3.1.1.) Требуется определить, в каком из этих двух состояний находится информационная система. Координаты математических ожиданий выборок показаны на рис. 5.3.1.1. Мера распознавания должна быть не менее 0,5 (э( x ) ≥ 0.5) . Решение: 1. Воспользуемся потенциальной дискриминантной функцией (5.3.1.2.) при значении констант a = 0,1, c = 1 . Тогда значение этой функции для каждой из состояний будет равно: f1 (x ) = e −0.1⋅ x1 − x10 ( ) − (x ( ) ( 2 2 − x 20 ) 2 =e −0.1⋅ (1 − 3) − (4 − 1,5) 2 2 ≅ 0,73 ) 2 2 −0.1⋅ x1 − x − x 2 − x −0.1⋅ (1 − 4 ) − (4 − 7 ) f 2 (x ) = e =e ≅ 0,66 x ∈ D , т.к. f1 ( x ) > f 2 ( x ) ⇔ 0,73 > 0,66 f1 (x ) 0,66 = 1− = 0,1 2. Мера надёжности распознавания: э( x ) = 1 − f1 (x ) + f 2 (x ) 0,73 0 2 1 0 2 2 Рис. 5.3.1.1. Иллюстрация постановки задачи распознавания принятия решения (отнесения предъявленной выборки x к классу x1 или x 2 ). 30 5.3.2. Метод среднего риска. Принятие решения о том, в каком состоянии находится информационная система, осуществляется на основе минимизации величины среднего риска. В зависимости от предварительной информированности в условиях распознавания состояний системы могут быть использованы различные типы критериев принятия решений: критерий Байеса, Минимаксный критерий, критерий Неймана-Пирсона. Критерий Байеса. Если известны плотности распределения вероятностей ( f1 ( x ), f 2 ( x )) нахождения системы в состоянии 1 и 2 . От параметра, а также априорные вероятности появления этих состояний при условии что P1 + P2 = 1 , заданы стоимости правильных (C11 ,C 22 ) и ошибочных (C12 , C 21 ) решений, то используется критерий Байеса (рис. 5.3.2.1.) и решается задача распознавания состояний. Рис. 5.3.2.1. иллюстрация использования для принятия решения критерия Байеса. Как видно из графика 5.3.2.1. там толожены значения параметра x , соответствующие максимумам плотности распределения µ1 и µ 2 , а значение параметра x , соответствующее порогу принятия решения (x = x0 ) которому соответствуют области определяющие вероятности неправильного принятия решения: Fпр (вероятность пропуска нераспознавания состояния 1 и вероятность ложной тревоги Fлт , т.е когда система находится в состоянии 1, а из правила принятия решения следует, что система находится в состоянии 2). По аналогии, нетрудно понять какие области определяют вероятность (1 − Fлт ) правильного распознавания состояния 1, а также вероятность правильного распознавания состояния 1 − Fпр . ( ) Средняя стоимость всех решений (средний риск) равен сумме всех стоимостей, умноженных на вероятности их получения с учётом априорных вероятностей: ( ) Cср = С12 ⋅P 1 ⋅(1 − Fлт ) + С12 ⋅ P1 ⋅ Fлт + С 22 ⋅P 2 ⋅ 1 − Fпр + С 21 ⋅ P2 ⋅ Fпр , (5.3.2.1.) где с11 - стоимость правильного распознавания состояния 1, с22 - стоимость правильного распознавания состояния 2, с12 - стоимость ложной тревоги FЛТ , с21 - стоимость пропуска FПР . Заменяя Р 2 на Р и Р1 на (1-Р), а также подставляя выражение для определения соответствующих вероятностей получим: 31 x0 ∞ ∞ x0 −∞ x0 x0 −∞ cср = (1 − P )(c11 ∫ f 1 ( x )dx +c12 ∫ f 1 ( x )dx ) + P (c22 ∫ f 2 ( x )dx +c21 ∫ f 2 ( x )dx ) (5.3.2.2) Чтобы минимизировать средний риск путем выбора порога х 0 , вычислим первую производную dcСР и приравняем ее к нулю в точке х = х 0 . dx dcСР = (1 − P )(c11 * f1 ( x 0 ) − c12 * f1 ( x 0 )) + P (c21 * f 2 ( x 0 ) − c22 f 2 ( x 0 )) = 0 dx (5.3.2.3) откуда: f 2 ( x 0 ) (1 − P )(c12 − c11 ) (5.3.2.4) = f1 (x 0 ) P (c21 − c22 ) Фактически выражение (5.3.2.4) является решением поставленной задачи и называется отношением правдоподобия (при с11 = с22 ): (1 − P ) * c12 (5.3.2.5) P * c21 где Λ 0 - отношение правдоподобия. Средний риск будет минимальным min cСР при выборе такого порога х 0 , при котором справедливо выражение (5.3.2.5). Для случая нормального распределения и при одинаковых дисперсиях (σ 12 = σ 22 = σ 2 ) отношение правдоподобия приобретает вид: Λ0 = Λ0 = e − ( x 0 − M 2 )2 − ( x 0 − M 1 )2 2σ 2 =e − 2 x 0 ( M 1 − M 2 ) − 0,5 ( M 12 − M 2 ) σ 2 (5.3.2.6) Решим это равенство относительно х 0 : ln Λ 0 = x 0 M1 − M 2 σ 2 + ( M 1 − M 2 )(M 1 + M 2 ) 2σ 2 (5.3.2.7) Т. к. должно удовлетворяться (5.3.2.5), то x0 = M1 + M 2 (1 − P ) * c12 σ2 − ln 2 M1 − M 2 P * c21 (5.3.2.8) При многоальтернативной задаче распознавания состояния системы критерием распознавания к-го состояния из общего числа состояний М является выполнение неравенства: 32 M ∑P *c i =1 i ik M * f i ( x ) ≤ ∑ Pi * cim * f m ( x ); m ≠ k , m = (1, M ) , (5.3.2.8) i =1 где Pi - априорная вероятность возникновения i-го состояния; cik , cim - стоимость принятия правильных и неправильных решений относительно к-го и m-го состояний; f i ( x ), f m ( x ) - плотности распределения вероятности возникновения i-го и m-го состояния. Выражение (5.3.2.8) может быть использовано для составления алгоритма принятия решения при распознавании многих состояний. Минимаксный критерий В случае, когда неизвестны априорные вероятности Р, необходимо применить критерий минимизации среднего риска, не требующий значение этих вероятностей. По аналогии с теорией игр для этого используется так называемый минимаксный критерий, суть которого состоит в следующем. Если перебрать все возможные значения Р, то при этом величина минимального значения среднего риска сСР будет меняться по некоторому закону, достигая своего максимального значения при некотором значении априорной вероятности Р 0 (рис 5.3.2.2). Рис. 5.3.2.2. График изменения величины минимального значения среднего риска ( min cСР ) от x величины априорной вероятности (Р). Следовательно, если исходить из предположения самых неблагоприятных значений априорных вероятностей Р = Р 0 и выбрать для этих условий нормой принятия решений Х 0 = Х Р , то величина среднего риска при любом значении Р не будет превосходить значение min max cСР . Однако, если x P выбрать любое другое значение х 0 , т. е. которое минимизирует величину среднего риска для более благоприятных значений априорных вероятностей, то в действительности потери могут значительно превысить min max cСР (если в действительности ситуация окажется менее благоприятной). x P Найдем значение вероятностей D (вероятности правильного распознавания) и FЛТ (вероятности ложной тревоги), определяющие значение х Р : dcCP = −c11 (1 − FЛТ ) − c12 FЛТ + c22 D + c21 (1 − D ) = 0 (5.3.2.9) dP 33 где D = 1 − FПР - вероятность правильного распознавания. В координатах D и FЛТ это уравнение прямой (рис. 5.3.2.3) с угловым коэффициентом c −c tg β = 12 11 : c22 − c21 D = FЛТ c12 − c11 c11 − c21 + c22 − c21 c22 − c21 (5.3.2.10) Рис. 5.3.2.3. Иллюстрация принятия решения по минимаксному критерию (т. А), критерию Байеса (т. В) и критерию Неймана – Пирсона (т. С). Как видно из Рис. 5.3.2.3 т. А соответствует принятию решения по минимаксному критерию. Если (1 − P ) * c12 в точке В касательная имеет наклон равный Λ 0 = , т. е. tg α = Λ 0 , то т. В соответствует P *21 выбору порога х 0 по критерию Байеса. По сравнению с принятием решения по критерию Байеса, выбор минимаксного критерия диктуется отсутствием априорной информации о состояниях системы и стремлением в этих условиях использовать осторожную стратегию, которая гарантирует даже в самом худшем случае (относительно значений априорных вероятностей) получение минимума среднего риска, не превышающего значения min max cСР . x P Критерий Неймана – Пирсона Во многих случаях бывает трудно определить не только априорные вероятности, но и задать стоимости правильных и неправильных решений. Однако, при этом можно выдвинуть некоторые требования к уровням вероятностей D и FЛТ . Имея характеристику D = f ( FЛТ ) , представленную на рис. 5.3.2.3, можно задав допустимое значение вероятности ложной тревоги FЛТ найти единственное значение D 0 . Точка С соответствует принятию решения по критерию Неймана – Пирсона. 34 5.3.3. Метод диагностических комплексов. Очень часто для решения задачи технической диагностики важно не наличие или отсутствия какого-либо одного признака, а появления или не появления некоторого комплекса признаков. Если отобрано N наиболее значимых признаков (К), а число возможных диагнозов два ( L1 , L 2 ) , то можно построить линейную разделяющую функцию: N f ( K ) = ∑ λi K i , (5.3.3.1) i =1  1, если _ диагноз _ L1 где λi =  − 1, если _ диагноз _ L 2 Если система имеет больше признаков, характерных для состояния L1 чем L 2 , то она находится в состоянии L1 (и наоборот): f ( K ) ≥ 0 ⇒ L1   или  f ( K ) < 0 ⇒ L 2  (5.3.3.2) Однако для распознавания состояния системы может быть возможно определенное состояние признаков (комплекс признаков - S), а не просто их количество. Тогда факт появления комплекса признаков фиксируется при выполнении некоторой совокупности условий, которые могут быть описаны логическими функциями. Логические функции могут быть самыми различными в зависимости от диагноза. В этом случае роль разделяющих функций могут выполнять сами логические функции ( FЛ ) .  1, если _ диагноз _ L1 FЛ =  0, если _ диагноз _ L 2 (5.3.3.3) Пример распознавания состояния системы Система имеет два состояния: L1 - неисправное и L 2 - исправное. Состояние L1 описывается одним из трех комплексов признаков (S 1 , S 2 , S 3 ) , включающих в себя по четыре признака ( K 1 , K 2 , K 3 , K 4 ) . Следовательно, неисправное состояние выявляется при появлении любой из комбинации признаков, значения которых приведены в таблице неисправностей 5.3.3.1. Таблица 5.3.3.1 Комплексы признаков S1 S2 S3 Признаки K1 1 1 K2 1 K3 K4 1 В остальных случаях система находится в исправном состоянии. 35 Решение В качестве разделяющей функции может служить следующая логическая функция: FЛ = [(1 ~ k 1* ) ∧ (0 ~ k 2* ) ∧ (0 ~ k 3* ) ∧ (0 ~ k 4* )] ∨ ∨ [(1 ~ k 1* ) ∧ (1 ~ k 2* ) ∧ (0 ~ k 3* ) ∧ (0 ~ k 4* )] ∨ (5.3.3.4) ∨ [(0 ~ k 1* ) ∧ (0 ~ k 2* ) ∧ (0 ~ k 3* ) ∧ (1 ~ k 4* )] где k 1* , k 2* , k 3* , k 4* - фактическое значение признаков. Тогда: 1, если _ система _ находится _ в _ состоянии _ L1 _( неисправна ) FЛ =   0, если _ система _ находится _ в _ состоянии _ L 2 _(исправна ) (5.3.3.5). 36