автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Разработка моделей и алгоритмов оптимизации процедур диагностирования на граф-моделях технических систем

нижегородским государственный техническим университет

На правах рукописи

ООЗОБТЭТВ

V»

СТЕПАНЕНКО Мария Анатольевна

РАЗРАБОТКА МОДЕЛЕЙ И АЛГОРИТМОВ ОПТИМИЗАЦИИ ПРОЦЕДУР ДИАГНОСТИРОВАНИЯ НА ГРАФ-МОДЕЛЯХ ТЕХНИЧЕСКИХ СИСТЕМ

Специальность 05 13 01 - «Системный анализ, управление и обработка информации (в науке и промышленности) по техническим наукам»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Нижний Новгород 2007

003057978

Работа выполнена на кафедре «Информатика и системы управления» Нижегородского государственного технического университета (НГТУ)

Научный руководитель:

доктор технических наук, профессор Соколова Э С

Официальные оппоненты:

доктор технических наук, профессор Кирьянов К Г

кандидат технических наук, доцент Уваров П И

Ведущая организация:

Научно-исследовательский Центр контроля и диагностики, Н Новгород

Защита состоится « 31 » ^СсСьЯ-_ 2007 г в /3 ¿i /ЛкР

часов на заседании диссертационного совета № Д212 165 05 в Нижегородском государственном техническом университете по адресу 603600, г Нижний Новгород, ГСП-41, ул К Минина, 24

С диссертацией можно ознакомиться в библиотеке НГТУ Ваш отзыв на автореферат в одном экземпляре, заверенный печатью, просим направлять на имя ученого секретаря совета

Автореферат разослан« /J » C¿/l/i£~¿Jt 2007 г

Ученый секретарь диссертационного совета

к т н , доцент

А П Иванов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы.

Стремительные темпы развития и внедрение во все сферы деятельности современных технических систем, непрерывный рост их структурной сложности и размерности, специализированные условия применения и требования к безотказности выполняемых аппаратурой функций определяют актуальность проблемы надежности, качества и безопасности эксплуатации технических объектов Большое значение в успешном решении этих задач принадлежит методам и средствам контроля и диагностики технических систем и программного обеспечения

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

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

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

Основоположниками теории диагностирования дискретных и непрерывных технических систем являются отечественные и зарубежные ученые П П Пархоменко, Е С Согомонян, В В Карибский, А В Мозгалевский, Я Я Осис, В А Гуляев, Д Маеда, С Рамомурти Дальнейшее развитие теория синтеза контролепригодных объектов получила в работах П В Глущенко, В И Сагунова, С И Беляевой, Л С Ломакиной, где в качестве моделей объектов диагностирования используются логические модели и графы причинно-следственных связей, анализ которых позволяет назначить оптимальные совокупности точек контроля для снятия диагностической информации, а процедуры диагностирования реализуются в соответствии с матрицей проверок Разработка автоматизированных методов построения матрицы проверок и анализ результатов ее обработки позволили эффективно решить задачу своевременного обнаружения дефектов в

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

Диссертационная работа выполнена по межвузовской научно-технической программе «Диагностические и информационно-поисковые системы»

Цель работы

Разработка и исследование моделей и методов оптимизации процедур обработки диагностической информации на граф-моделях восстанавливаемых объектов с большим числом состояний при реализации допусковых методов контроля Автоматизация разработанных алгоритмов для их практического применения

Методы исследования

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

Объекты исследования

Объектами исследования являются восстанавливаемые технические объекты, представимые логическими моделями или графами причинно-следчтвенных связей, число возможных состояний, обусловленных возникновением дефектов, в которых достигает сотен и тысяч единиц

Научная новизна диссертационной работы

1 Разработана модель классов эквивалентности диагностических пар (МКЭДП), компактно представляющая все множество отображений «вход-выход» многовходовых граф-моделей диагностирования, построенных на большом числе вершин, соответствующих состояниям технического объекта

2 Разработан метод построения оптимальных процедур диагностирования дефектов в объектах высокой сложности на базе МКЭДП по числу элементарных проверок на заданной глубине поиска дефектов

3 Предложена символьная модель кодирования допустимых решений для использования методов эволюционного моделирования при решении задач синтеза контролепригодных объектов

4 Разработан алгоритм построения и визуализации граф-модели объекта с заданными свойствами, характеризуемыми коэффициентом достижимости, для моделирования процесса построения диагностических процедур

5 Выполнена аналитическая оценка переборных методов в задачах построения оптимальных процедур диагностирования объектов высокой структурной сложности и показана невозможность их практической реализации

6 Предложены критерии оценки эффективности методов построения процедур диагностирования Проведен анализ вычислительной трудоемкости разработанных методов построения оптимальных процедур диагностирования по критерию объема обрабатываемой диагностической информации

Практическая значимость работы

Применение разработанной модели классов эквивалентности диагностических пар позволяет генерировать эффективные алгоритмы построения процедур диагностирования технических систем на граф-моделях с большим числом возможных состояний - дефектов Оптимйзация объема обрабатываемой диагностической информации обеспечивает своевременность принятия ■ управленческих решений с целью предотвращения аварийных ситуаций Автоматизация построения оптимальных процедур диагностирования дефектов позволяет существенно повысить эффективность проектирования контролепригодных систем

Реализация результатов работы

Разработанные математические модели, методы и алгоритмы

- реализованы в среде Borland С++ с использованием MFC (Microsoft Foundation Classes) и библиотеки Gdiplus dll Получено свидетельство об официальной регистрации программы для ЭВМ № 2007610902 "Модуль исследования контролепригодности системы (Defectoscopy)",

- используются в учебном процессе в виде фрагмента лекций в рамках курса «Надежность, эргономика и качество АСОиУ» для студентов, обучающихся по специальности 22 02 00 «Автоматизированные системы обработки информации и управления» в ГОУ ВПО Нижегородский Государственный Технический Университет

Апробация работы

Основные результаты диссертационной работы докладывались и обсуждались на Всероссийских научно-технических конференциях "Информационные системы и технологии" ИСТ-2003, ИСТ-2004, ИСТ-2005, на Международной научно-технической конференции "Информационные системы и технологии" ИСТ-2006, на V Международной конференции «Идентификация систем и задачи управления» SICPRO '06, на 11-й Нижегородской сессии молодых ученых (технические науки) ' >

Публикации

По результатам диссертационной работы опубликовано 13 работ в печатных изданиях, в том числе 1 работа в издании, рекомендованном ВАК

Структура и объём работы

Диссертационная работа изложена на 147 печатных листах, включает 33 рисунка и 18 таблиц, состоит из введения, 4 глав, заключения, списка литературы и 3 приложений

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Обзор работ в области диагностики технических средств показал отсутствие общего подхода к построению эффективных моделей и алгоритмов диагностирования причин возникновения отказов и анализа предаварийных ситуаций в объектах на граф-моделях с числом дефектов до нескольких сотен единиц В результате формулируются постановки задач исследования — разработка моделей и алгоритмов синтеза процедур диагностирования структурно-сложных объектов, оптимизирующих объем обрабатываемой диагностической информации с целью принятия решений по управлению объектом

Во второй главе приводится классификация диагностических моделей, и описываются их свойства Показано, что большой класс объектов

различной физической природы можно представить логическими моделями или графами причинно-следственных связей (ГПСС), построенными в пространстве их свойств Граф-модель объекта диагностирования хорошо приспособлена к решению задач обнаружения дефектов, описывает все множество возможных состояний объекта, вызванных дефектами, на качественном и структурном уровне определяя причины их возникновения и следствия их проявления Свойства граф-моделей привели к их широкому применению в задачах технической диагностики

Для целей диагностирования восстанавливаемые структурно-сложные объекты представляются граф-моделями с множеством входов Х=(хи х2, х„) и выходов 2=(21, 22, , где пит достаточно большие величины (до 100 и более единиц) (рисунок 1) Вершины графа представляют возможные состояния объекта, вызванные дефектами - отказом структурных элементов, выходом за пределы допуска параметров, событиями или явлениями, вызывающими неисправности в объекте, а дуги отражают соответствующие причинно-следственные связи Граф упорядочивается так, что направление дуги в графе соответствует перемещению от причины дефекта к следствию и отражает направление распространения или обнаружения дефекта

Пусть С7=(У, А) - ориентированный упорядоченный граф без контуров и петель, где К=(у/, - множество вершин графа, соответствующих

возможным дефектам, Л=(а/, а2, ,ак)={(^„ V}=1, - множество дуг графа, отражающих причинно-следственные связи между дефектами Эквивалентная матричная модель - матрица смежности вершин графа

Обозначим Х=(х/, х2, ,х„) - множество входных вершин графа Сг, соответствующих функциональным входам исследуемого объекта, или входам, на которые возможна подача тестовых воздействий (в ГПСС - это дефекты, которые не являются следствием проявления других дефектов), 2=(г,, 22, ,2щ) - множество выходных вершин графа, соответствующих диагностическим параметрам, снимаемым в точках контроля

Рисунок 1 Граф-модель объекта диагностирования

Матрицей проверок называется матрица В, составленная из № мерных векторов проверок Ьг(х„ (Ь!г, Ъ2п ,Ьцг), ЬгеВ, компоненты которых Ьу=\, если к-я вершина (к=1, , И) принадлежит хотя бы одному пути от х, к г„ и Ьь~0 в противном случае

Стратегия диагностирования и поиска дефектов заключается в подаче тестовых воздействий на входы х, , снятии результатов на выходах г, и обработке результатов логическим перемножением строк матрицы проверок, для которых результат проверки равен 0 (параметр не в допуске) и инверсий строк проверок с единичным результатом (параметр в допуске)

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

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

Пусть пит- количество входных и выходных вершин графа, тогда общее число строк в матрице В будет равно п т При построении оптимальной стратегии диагностирования по критерию минимального количества проверок, удовлетворяющих заданному критерию глубины поиска дефекта, в процессе работы алгоритма будут строиться матрицы проверок, содержащие 1,2, , пт проверок Количество всех возможных Матриц, содержащих по г проверок из возможных п т, вычисляется с

1 . Ч I г (п ту

помощью формулы сочетаний С{п т,г) = —---—

(п т — 1)'г'

Среднее количество строк матрицы проверок, определяющее вычислительную сложность алгоритма, будет равно Общее число

матриц проверок В, построенных в процессе работы алгоритма,

соответственно равно т,1)J = 2" - 1

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

к

О ненулевыми элементами Кд = ———, (Я - размерность матрицы

2

п М2~М * достижимости и, --- - общее число элементов в матрице

достижимости О, к - число ненулевых элементов в матрице достижимости В выше главной диагонали), получим общее число диагностических пар во всех построенных матрицах проверок для заданного графа с учетом его

, ипт Л „ п т топологии а =\2 -2) Кд

Число столбцов в матрице проверок В равно числу вершин в графе (ЛО Поэлементное сравнение между собой всех возможных пар столбцов, '

N1

количество которых С(Л^,2) = ^—2)121' опРеделяется выРажением

/,=(2'"-2) Кд ~

Так как количество строк в полной матрице проверок составляет значение п т Кд, выражение для общего количества элементарных операций сравнения элементов столбцов в полной матрице проверок В имеет вид

Л"

к=Кл п т-,--г-

2 д (М- 2)'2'

Суммируя значения 1\ и /2, получим аналитическое выражение для определения общего количества элементарных операций сравнения Е элементов столбцов матрицы проверок

ЛМ

'(N-2)12'

Согласно полученному аналитическому выражению, даже для небольшого объекта, граф-модель которого имеет «=10 входов и т= 10 выходов при общем числе вершин 7У=100 и значении Кд = 0,2, количество операций сравнения пар элементов столбцов матрицы проверок будет составлять порядка 6,27х 1034 И если ЭВМ обрабатывает, например, 3 х 10 подобных операций в секунду, то потребуется 6,63х 1018 лет на обработку данных для решения поставленной задачи методом полного перебора

Анализ работы методов направленного поиска показал их значительную погрешность в определении квазиоптимального решения, т к

Е = 11+12 = Кд п т(хг 2""

поиск оптимальных решении происходит не во всём пространстве допустимых решений.

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

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

Диагностической Парой (х,- назовем пару вершин д, и х) в графе С, если результат тестового воздействия, поданного на вход элемента может быть снят на выходе элемента 2Г При этом сигнал, снимаемый в точке контроля г,, является диагностическим параметром объекта.

Эквивалентными диагностическими парами (принадлежащими одному классу эквивалентности) назовем диагностические пары Ь — (X/, имеющие одинаковые значения выходов Щ.

Все множество диагностических пар единственным образом разбивается на непересекающиеся классы эквивалентности.

входы

выходы

ЬХ,

IX,

ЬХз

1ХП

Щл

1х\2

0-1

\ " 1X2,]

О I 1

fri.fi

1хш

и ■ .1 1X1.1 1

Ш* 1*тпЛ * * * • • * • • • ¡X

ГП1Г1;|1ИИ|1Т[П11|И111И11П11111Г1111П1111111И1Ш11П11ГГП111ИПИ1!1ГШ1

?л

Ли

Рисунок 2. Модель классов эквивалентности диагноста чес кйх пар (МКЭДП)

Модель классов эквивалентности диагностических пар объединяет в себе две части: входы и выходы граф-модели объекта. Поскольку каждый из т выходов (2\, г2, ... , гт) графа достижим от определенного числа его входов (х\, хг, ... , х„), все множество входов X в соответствии с критерием достижимости от них т выходов разбивается на совокупность множеств Х\,

Хг, , Хт Множество А^ включает все входы, от которых достижим выход 2), множество Х2 включает все входы, от которых достижим выход и т д Так как от одного и того же входа могут быть достижимы несколько различных выходов (например, г, и то данные множества в общем случае пересекаются (Х,глХ,£0, г, у =1, , т, г ^у)

Входы в модели МКЭДП кодируются номерами, соответствующими номерам входов граф-модели объекта, выходы кодируются номерами, соответствующими номерам точек контроля, используемых для диагностирования технического состояния объекта

Каждый массив входов Х1 = |,, х12, ,х,г } представляется

некоторой лентой ЬХ„ состоящей из совокупности кадров одинаковой длины по количеству входов г, , от которых достижим выход I (г=1, , те) Длина кадра для каждой ленты ЬХ, различна, так как каждый выход достижим от различного числа входов

Вычислим наименьшее общее кратное Ь для мощностей множеств входов |=Г1, , \Хт\=гт Введем шкалу длины Ь, разбитую на единичные интервалы Поместим шкалу под лентами множеств входов так, чтобы их границы совпали (рисунок 2)

Вертикальное сечение лент входов ЬХ,{]= 1, , т) определяет частное решение задачи

Назовем частным решением Я, совокупность, состоящую из т диагностических пар {(*, .г,), [х2^,г2), , образующих

очередную процедуру диагностирования, заключающуюся в подаче диагностических воздействий на соответствующие входы и снятие реакций в соответствующих точках контроля (выходах граф-модели)

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

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

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

Разработано и приведено описание алгоритма построения процедуры диагностирования объекта (рисунок 3) для следующей постановки задачи

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

дефекта, равную единице, при поочередной подаче тестовых воздействий на диагностические входы

шш |я;|,

ВРсВп

вп = {Ь,А. ,ъ„1

КГП{В[,) = \

где Вп - полная матрица проверок на назначенной совокупности точек контроля, Вр - матрицы проверок, обеспечивающие одноразличимость дефектов, В0/'- матрица проверок, включающая минимальное число диагностических пар и сохраняющая одноразличимость дефектов, КГп -коэффициент глубины поиска дефекта, являющийся мерой контролепригодности, определяющий долю однозначно различимых дефектов Значение коэффициента глубины поиска дефекта определяется по матрице проверок В в соответствии с выражением

где Т(г) - число совпадающих столбцов в матрице проверок В, определяющих число неразличимых дефектов, р - общее число столбцов матрицы В _

Начало

Начало процедуры

Ввести шкалу длины £.

Процедура интерпретации графической модели в множество решений задачи построения процедуры диагностирования

point [01=0 interval^ 0 counter=0

MIN — mm j, j = 1, , m

Построить частные решения П матрицы проверок В{П) /=1 counter

h, = h, -MIN /=И

Выбрать оптимальное решение Пор? Кт(В(ПорО)-*гпах

point [counter+\]=point [counter] + MIN counten=counter+1

| Исключить из модели диагностические пары образующие П |

Построить частные решения /7'с/7, матрицы проверок 8(П оП,)/=1 counter

Выбрать оптимальное решение Пор? Кт(В(П и Пор!))-* тах

П- П uHopt

| point ¡counter*l^L counter - counter+1 [

Рисунок 3 Блок-схема алгоритма оптимизации процедуры диагностирования по числу

диагностических пар

Для объекта, представленного граф-моделью, следует заполнить модель классов эквивалентности диагностических пар (МКЭДП) и выполнить алгоритм оптимизации процедуры диагностирования по числу диагностических пар, обеспечивающих одноразличимость дефектов (рисунок 3) Процедура интерпретации графической модели в множество решений задачи построения процедуры диагностирования, включенная в алгоритм, позволяет определить координаты границ частных1 решений в координатах шкалы Ь

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

Задача 3.2. Обеспечить заданное значение критерия контролепригодности (Кгп)

объекта при минимальных затратах, связанных с реализацией процедуры диагностирования С(В'Р) -> лип,

= {ЬиЬ2, ,ЬП\

Задача 3.3. Обеспечить оптимальное значение критерия контролепригодности > (КГп) при ограничениях на затраты, связанные с проведением процедуры диагностирования

/чл (5р)-»тах,

п>

КГП(В-Р)>К

Вм={ьиь2, А),

Яр С= Я

п>

С(Вр)<С

где С(Вр) - затраты на организацию диагностических проверок, С*-заданное значение ограничений на затраты

Приведены алгоритмы решения задач 3 2 и 3 3, где в качестве показателя контролепригодности используется коэффициент глубины поиска дефекта Кгп Для решения задачи 3 2 необходимо реализовать обход путей дерева решений в направлении сверху вниз и слева направо, проанализировать соответствующие матрицы проверок, и вычислить затраты на организацию диагностических проверок С(В'Р) При этом, если в процессе выполнения алгоритма возникает нарушение ограничения по стоимости (текущее значение затрат на реализацию диагностических пар С{В*Р) больше минимального Ст1„), то обход дерева в данном направлении не продолжается Решая задачу 3 3, необходимо произвести обход путей дерева решений в направлении сверху вниз и слева направо, отсекая ветви, для которых в процессе выполнения алгоритма нарушаются ограничения по стоимости (текущее значение затрат на реализацию диагностических пар С(ВР) больше

заданного С ). Как и при решении задачи 3.2, следует производить обход 1-го пути полного дерева решений в направлении от начальной вершины к висячей и подсчитывать суммарные затраты на организацию точек съема диагностической информации С{/) построенного частного решения, сравнивая ее с порогом С .

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

Для граф-модели объекта диагностирования строится модель классов эквивалентности диагностических пар и выполняется ее анализ следующим образом.

Вычислить сумму V мощностей множеств входов X,,.. .,Х„ :

nt . j

r-lw

j-i

В результате вычислений возможны два случая:

1. Полученное значение V не превышает размерности шкалы L: V <L.

2. Полученное значение V> L.

Для вычисления V используется матрица достижимости D исходного графа, в которой следует проанализировать подматрицу размерности расположенную в правом верхнем углу, т.е. рассмотреть строки, соответствующие входам xh ... , х,„ и столбцы, соответствующие выходам z,. ..., zm исходной граф-модели.

Очевидно, что количество единиц в каждом столбце, соответствующем выходу Zj (i=l, ... , т), равно мощности множеств входов X, (iW, ... , т), а сумма всех единиц в рассматриваемой подматрице будет равна V.

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

Во втором случае строится символьная модель, соответствующая двоичному вектору длины IV: W— 2 * countег+2,

где counter - общее число различных частных решений, полученных для исходного вида модели классов эквивалентности диагностических пар. Пример такого вектора приведен на рисунке 4.

I 2*counteri-2

Рисунок 4. Двоичный вектор длины fV

В предложенной символьной модели выделено три функциональных участка (А, Б и О)

Первый и второй участки (А, Б) двоичного вектораJY соответствуют отрезкам [1, counter] и [counter*-1, 2*counter] длины counter Они содержат единицы в битах, соответствующих частным решениям, которые будут участвовать в построении допустимого решения задачи

Третий участок (О) вектора W соответствует отрезку [2*counter+l, 2*counter+2] Этот участок символьной модели несет информацию о том, какая операция будет выполнена над множествами ВА и ВБ, соответствующими множествам диагностических пар, построенным по отрезкам А и В, соответственно

- 00 - разность множеств Вл и ВБ ВА \ Вб, Из общего числа диагностических пар, построенных по участку А, исключаются те пары, которые одновременно принадлежат и отрезку А, и отрезку Б (ВА \ ВБ = ВА\ ВА&ВБ) вектора W,

- 01 - разность множеств ВБ и ВА ВБ\ ВА,

- 10 — объединение множеств ВА и ВБ ВА yj В/; К диагностическим парам, построенным по участку А, добавляются пары, соответствующие участку Б,

- 11 — пересечение множеств ВА и ВБ ВА & В,; Учитываем только те диагностические пары, которые одновременно принадлежат и отрезку А, и отрезку Б символьной модели (рисунок 5)

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

В четвертой главе приведено краткое описание разработанного программного продукта «Модуль исследования контролепригодности системы Defectoscopy» (рисунок 6) для решения задач построения процедур диагностирования восстанавливаемых объектов, использующих допусковые методы контроля, представленных граф-моделями, построенными в пространстве конструктивных свойств или взаимосвязей их параметров

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

- метод на базе разработанной МКЭДП,

- метод полного перебора решений;

- метод случайного выбора строки, удаляемой из полной матрицы проверок, при выполнении критерия различимости столбцов,

B£kjBa

Рисунок 5 Диаграмма Эйлера для множеств ВА и В б

- комбинации методов на базе МКЭДП и метода случайного выбора удаляемой строки;

- генетический алгоритм поиска решения.

Рисунок 6. Модуль исследования контролепригодности системы (Dc fee tosco ру)

Оценена эффективность разработанных методов.

Исследования, проведенные для графов различной топологии

(обработано — 700 графов) показали, что метод построения оптимальной процедуры диагностирования,

основанный ¡ta анализе МКЭДП, требует по сравнению с методами случайного выбора и комбинированного метода (МКЭДП+ случайный выбор) меньших временных затрат, и с увеличением размерности обрабатываемого пэафа выигрыш во времени растет (рисунок 7).

Например, для графов с количеством вершин N=450 время построения оптимальной процедуры

диагностирования при использовании метода па основе МКЭДП составило в среднем 35 секунд, метод случайного выбора потребовал 176 секунд, а при

¿Сп^эннын выбор » МКЭДП +Спучэйкв»м выбор * МКЭДП

Рисунок 7. Время построения диагностической Процедуры различными методами оптимизации

использовании комбинации методов сначала метода на базе МКЭДП, а затем метода случайного выбора временные затраты составили 91 секунду

Введен показатель

относительного улучшения

процедуры диагностирования §в, характеризующий степень

улучшения процедуры

диагностирования относительно полной матрицы проверок, вычисляемый по формуле

ы-к

\в

100%,

ь Случайным выбор « МКЭДП • МКЭДП+Случайный выбор

Рисунок 8 Улучшение процедуры диагностирования относительно полной матрицы проверок для различных методов оптимизации

где |Вор,| - мощность матрицы проверок, полученной в результате оптимизации

процедуры диагностирования, \Bfuiil - мощность полной матрицы проверок

Экспериментально получено, что комбинация метода на основе МКЭДП с методом случайного выбора, а также метод, построенный на базе МКЭДП, дают лучшие решения по критерию относительного улучшения процедуры диагностирования (рисунок 8) Например, для графов с количеством вершин N=450 использование метода на основе МКЭДП позволило сократить процедуру диагностирования в среднем на 86,41%, метод случайного выбора - на 38,25%, а при использовании комбинации методов сначала метода на базе МКЭДП, а затем метода случайного выбора процедура диагностирования сократилась на 88,71%

Приведены результаты применения разработанных моделей и алгоритмов к диагностированию участка газотранспортной сети (ГГТС) между двумя компрессорными станциями Заволжской и Сеченовской Ужгородского коридора, модель которого представлена графом причинно-следственных связей, содержащим 531 вершину, 319 входных вершин, 98 назначенных точек контроля Метод оптимизации процедуры поиска с использованием МКЭДП позволил в 12 раз (на 91,69%) сократить количество обрабатываемой диагностической информации, т е размер матрицы проверок уменьшился в 12 раз при условии одноразличимости дефектов Комбинированный метод в 18 раз (на 94,43%) сократил матрицу проверок

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

2 Разработан алгоритм построения диагностических процедур на базе модели классов эквивалентности диагностических пар и алгоритм интерпретации графической модели в множество решений задачи построения эффективных процедур диагностирования

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

4 Реализован алгоритм автоматизированного проектирования граф-модели объекта с заданной топологией, определяемой коэффициентом достижимости, и требуемым коэффициентом глубины поиска дефекта с целью моделирования и апробации разработанных моделей и алгоритмов

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

6 Выполнена апробация разработанных алгоритмов для диагностирования участка газотранспортной сети между компрессорными станциями Заволжской и Сеченовской Ужгородского коридора В результате сокращен объем хранимой в базе данных информации для оценки качества функционирования газотранспортной сети

Список публикаций по теме диссертации

1 Степаненко, M А Контролепригодность обьекта диагностирования с одиночными дефектами / M А Степаненко // Информационные системы и технологии (ИСТ-2003) тез докл всеросс науч -техн конф , Нижегород гос техн ун-т - H Новгород, 2003 С 132-133

2 Степаненко, M А Решение задачи распределения коэффициента глубины диагностирования в сложной системе / M А Степаненко // Системы обработки информации и управления Труды Нижегород гос тех ун-та / НГТУ - H Новгород, 2003 T 37 В 10 С 83-92

3 Соколова, Э С Об основных принципах тестирования программ/ Э С Соколова, M А Степаненко// Информационные системы и

технологии (ИСТ-2004) тез докл всеросс науч -техн конф, Нижегород гос техн ун-т - H Новгород, 2004 С 109-110

4 Соколова, Э С Формализованный подход к тестированию кратных ошибок в программных модулях / Э С Соколова, M А Степаненко // Системы обработки информации и управления Труды Нижегород гос тех ун-та / НГТУ - H Новгород, 2004 Т 47 В 11 С 90-93

5 Соколова, Э С Построение процедур диагностирования технического состояния объектов / Э С Соколова, M А Степаненко, О Е Гущин // Информационные системы и технологии (ИСТ-2005) тез докл всеросс науч -техн конф , Нижегород гос техн ун-т - H Новгород, 2005 С 136-137

6 Гущин, О H Разработка нового подхода к построению процедур диагностирования технических объектов / ОН Гущин, С H Капранов, M А Степаненко // Системы обработки информации и управления Труды Нижегород гос тех ун-та / НГТУ - H Новгород,

2005 Т 54 В 12 С 54-57

7 Гущин, О H Оптимизация процедур диагностирования технического состояния объекта / ОН. Гущин, С H Капранов, M А Степаненко // Системы обработки информации и управления Труды Нижегород гос тех ун-та / НГТУ - H Новгород, 2005 Т 54 В 12 С 58-61

8 Степаненко, M А Метод построения процедур диагностирования технического состояния объектов с использованием символьной модели / MA Степаненко, Э С Соколова, С H Капранов // Программа (с аннотациями докладов) V Международной конференции «Идентификация систем и задачи управления» SICPRO '06 Москва 30 января - 2 февраля 2006г, Институт проблем управления им В А Трапезникова РАН - M 2006

9 Степаненко, M А Метод построения процедур диагностирования технического состояния объектов с использованием символьной модели / M А Степаненко, Э С Соколова, С H Капранов // Труды V Международной конференции «Идентификация систем и задачи управления» SICPRO '06 Москва, 30 января - 2 февраля 2006 г, Институт проблем управления им В А Трапезникова РАН - M

2006 С 1254-1266

10 Акатьев, H Д Алгоритм оптимизации программы поиска дефектов / H Д Акатьев, M И Минеев, M А Степаненко // Информационные системы и технологии (ИСТ-2006) тез докл международ науч -техн конф , Нижегород гос техн ун-т - H Новгород, 2006 С 183-184

11 Степаненко, M А Оптимизация автоматического метода синтеза ацикличного однонаправленного графа / MA Степаненко // XI Нижегородская сессия молодых ученых Технические науки "Татинец", 12-16 февраля 2006г, H Новгород С 29-30

12 Соколова ЭС. Разработка алгоритма локализации дефектов на назначенной совокупности контрольных точек / Э С Соколова, M А Степаненко//Журн Контроль Диагностика -2006 №9 С 41-44

13 Акатьев, H Д Алгоритм оптимизации назначения контрольных точек / H Д Акатьев, M И. Минеев, M А Степаненко // Информационные системы и технологии (ИСТ-2007) тез докл международ науч -техн конф , Нижегород гос техн ун-т - H Новгород, 2007. С 138-139

Подписано в печать 16 04 07 Формат 60 х 84 '/16 Бумага офсетная Печать офсетная Уч-изд л 1,0 Тираж 100 экз Заказ 316

Нижегородский государственный технический университет им РЕ Алексеева Типография НГТУ им РЕ Алексеева 603950, Нижний Новгород, ул Минина, 24

ВВЕДЕНИЕ.

ГЛАВА 1 АНАЛИЗ ПРОБЛЕМЫ ДИАГНОСТИРОВАНИЯ ТЕХНИЧЕСКОГО СОСТОЯНИЯ СЛОЖНЫХ ОБЪЕКТОВ.

1.1 Обзор существующих методов диагностирования технических систем.

1.2 Причины возникновения, характеристики и классификация отказов в технических системах.

1.3 Постановка задач исследования.

ГЛАВА 2 РАЗРАБОТКА МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ ДЛЯ ДИАГНОСТИРОВАНИЯ СЛОЖНЫХ ТЕХНИЧЕСКИХ СИСТЕМ

2.1 Математические модели объектов диагностирования и их свойства.

2.2 Модель классов эквивалентности диагностических пар.

2.3 Количественные оценки сложности методов обработки диагностической информации на базе матричных моделей.

ВЫВОДЫ ПО ГЛАВЕ 2.

ГЛАВА 3 РАЗРАБОТКА АЛГОРИТМОВ ПОСТРОЕНИЯ ПРОЦЕДУР ЛОКАЛИЗАЦИИ ДЕФЕКТОВ НА БАЗЕ МОДЕЛИ КЛАССОВ ЭКВИВАЛЕНТНОСТИ ДИАГНОСТИЧЕСКИХ ПАР.

3.1 Алгоритм минимизации комбинационной процедуры поиска дефектов на базе модели классов эквивалентности диагностических пар.

3.2 Минимизация затрат на проведение процедуры диагностирования, обеспечивающей заданный уровень контролепригодности объекта.

3.3 Максимизация критерия контролепригодности при ограничении на затраты, связанные с проведением процедуры диагностирования.

3.4 Повышение эффективности применением генетических алгоритмов к задачам технической диагностики на основе МКЭДП.

ВЫВОДЫ ПО ГЛАВЕ 3.

ГЛАВА 4 АВТОМАТИЗАЦИЯ РАЗРАБОТАННЫХ МЕТОДОВ И

АЛГОРИТМОВ И ИХ ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ.

4.1 Автоматизация алгоритмов построения процедур диагностирования технического состояния объектов.

4.2 Описание разработанного программного продукта для построения процедур диагностирования на базе МКЭДП.

4.3 Применение разработанных алгоритмов для диагностирования участка газотранспортной сети.

4.4 Минимизация множества перекрытых вентилей для решения задач диагностики транспортных сетей.

4.5 Оценка эффективности методов построения процедур диагностирования граф-моделей технических систем по результатам экспериментов.

ВЫВОДЫ ПО ГЛАВЕ 4.

Актуальность проблемы

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

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

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

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

Основоположниками теории диагностирования дискретных и непрерывных технических систем являются отечественные и зарубежные ученые П.П. Пархоменко, Е.С. Согомонян, В.В. Карибский [7; 12-15], А.В. Мозгалевский [4-5], Я.Я. Осис [17-18], В.А. Гуляев [31; 39], Д. Маеда, С. Рамомурти. Дальнейшее развитие теория синтеза контролепригодных объектов получила в работах П.В. Глущенко, В.И. Сагунова, С.И. Беляевой, J1.C. Ломакиной [19; 20; 45-51], где в качестве моделей объектов диагностирования используются логические модели и графы причинно-следственных связей, анализ которых позволяет назначить оптимальные совокупности точек контроля для снятия диагностической информации, а процедуры диагностирования реализуются в соответствии с матрицей проверок. Разработка автоматизированных методов построения матрицы проверок и анализ результатов ее обработки позволили эффективно решить задачу своевременного обнаружения дефектов в объектах невысокой сложности, в которых число возможных состояний, обусловленных дефектами, сравнительно невелико. Рост размерности и структурной сложности технических устройств опережает возможности активно используемых методов поддержания их в работоспособном состоянии своевременным обнаружением дефектов. Необходима разработка новых эффективных моделей для решения задач диагностики объектов, состоящих из нескольких сотен и даже тысяч единиц, автоматизация процедур построения оптимальных стратегий диагностирования технического состояния и прогнозирования поведения сложных современных технических систем.

Диссертационная работа выполнена по межвузовской научно-технической программе «Диагностические и информационно-поисковые системы».

Цель работы

Разработка и исследование моделей и методов оптимизации процедур обработки диагностической информации на граф-моделях восстанавливаемых объектов с большим числом состояний при реализации допусковых методов контроля. Автоматизация разработанных алгоритмов для их практического применения.

Методы исследования

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

Объекты исследований

Объектами исследования являются восстанавливаемые технические объекты, представимые логическими моделями или графами причинно-следственных связей, число возможных состояний, обусловленных возникновением дефектов, в которых достигает сотен и тысяч единиц.

Научная новизна диссертационной работы

1. Разработана модель классов эквивалентности диагностических пар (МКЭДП), компактно представляющая все множество отображений «вход-выход» многовходовых граф-моделей диагностирования, построенных на большом числе вершин, соответствующих состояниям технического объекта.

2. Разработан метод построения оптимальных процедур диагностирования дефектов в объектах высокой сложности на базе МКЭДП по числу элементарных проверок на заданной глубине поиска дефектов.

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

4. Разработан алгоритм построения и визуализации граф-модели объекта с заданными свойствами, характеризуемыми коэффициентом достижимости, для моделирования процесса построения диагностических процедур.

5. Выполнена аналитическая оценка переборных методов в задачах построения оптимальных процедур диагностирования объектов высокой структурной сложности и показана невозможность их практической реализации.

6. Предложены критерии оценки эффективности методов построения процедур диагностирования. Проведен анализ вычислительной трудоемкости разработанных методов построения оптимальных процедур диагностирования по критерию объема обрабатываемой диагностической информации.

Практическая значимость работы

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

Реализация результатов работы

Разработанные математические модели, методы и алгоритмы

- реализованы в среде Borland С++ с использованием MFC (Microsoft

Foundation Classes) и библиотеки Gdiplus.dll (Приложение 1). Получено свидетельство об официальной регистрации программы для ЭВМ № 2007610902 "Модуль исследования контролепригодности системы

Defcctoscopy)"(npmio-,KeHHe 3);

- используются в учебном процессе в виде фрагмента лекций в рамках курса «Надежность, эргономика и качество АСОиУ» для студентов, обучающихся по специальности 22.02.00 «Автоматизированные системы обработки информации и управления» в ГОУ ВПО Нижегородский Государственный Технический Университет (Приложение 3).

На защиту выносятся следующие результаты работы:

1. Разработана модель классов эквивалентности диагностических пар (МКЭДП), соответствующая отображению «вход-выход» графа, для целей диагностирования.

2. Разработан и реализован алгоритм построения процедур диагностирования технического состояния объектов высокой сложности на базе модели классов эквивалентности диагностических пар.

3. Разработан механизм кодирования допустимых решений генетического алгоритма в задачах синтеза контролепригодных на базе разработанной модели.

4. Выполнены исследование, анализ и оценка эффективности существующих и разработанных алгоритмов диагностирования, построенных на базе МКЭДП.

Апробация работы

Основные результаты диссертационной работы докладывались и обсуждались на Всероссийских научно-технических конференциях "Информационные системы и технологии" ИСТ-2003, ИСТ-2004, ИСТ-2005, на Международной научно-технической конференции "Информационные системы и технологии" ИСТ-2006, на V Международной конференции

Идентификация систем и задачи управления» SICPRO '06, на 11-й Нижегородской сессии молодых ученых (технические науки).

Публикации

По результатам диссертационной работы опубликовано 13 работ в печатных изданиях, в том числе 1 работа в издании, рекомендованном ВАК.

Структура и объём работы

Диссертационная работа изложена на 147 печатных листах, включает 33 рисунка и 18 таблиц, состоит из введения, 4 глав, заключения, списка литературы и 3 приложений.

ВЫВОДЫ ПО ГЛАВЕ 4

1. Приведено описание программного продукта "Модуль исследования контролепригодности системы (Defectoscopy)" для анализа надежности и моделирования процесса построения диагностических процедур для технических объектов с большим числом возможных дефектов.

2. Разработан алгоритм автоматизированного проектирования заданной топологии граф-модели объекта для анализа эффективности работы предложенных алгоритмов.

3. Выявлены аналитические зависимости размерности процедуры диагностирования и вычислительной трудоемкости решения задач от топологии граф-модели объекта диагностирования при использованием различных методов оптимизации.

4. Экспериментально показана эффективность использования в составе исследуемых методов разработанной модели классов эквивалентности диагностических пар МКЭДП.

5. Разработанные алгоритмы на практике применены для диагностирования участка газотранспортной сети между компрессорными станциями (КС) Заволжской и Сеченовской Ужгородского коридора. Показана эффективность применения разработанных моделей и алгоритмов построения диагностических процедур сложных объектов с большим числом состояний и диагностических признаков на примере газотранспортных сетей.

6. Сформулирована и решена задача минимизации множества перекрытых вентилей для целей диагностирования сетей транспортировки среды.

ЗАКЛЮЧЕНИЕ

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

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

2. Разработан алгоритм построения диагностических процедур на базе модели классов эквивалентности диагностических пар и алгоритм интерпретации графической модели в множество решений задачи построения эффективных процедур диагностирования.

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

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

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

6. Выполнена апробация разработанных алгоритмов для диагностирования участка газотранспортной сети между компрессорными станциями Заволжской и Сеченовской Ужгородского коридора. В результате сокращен объём хранимой в базе данных информации для оценки качества функционирования газотранспортной сети.

1. ГОСТ 20911-89. Техническая диагностика. Термины и определения. -Введен 01.01.91.-13 с.

2. ГОСТ 27.002-89. Надежность в технике. Основные понятия. Термины и определения. Введен 01. 07. 90.- 37 с.

3. Биргер, И.А. Техническая диагностика / И.А. Биргер. М. : Машиностроение, 1978. - 240 с.

4. Мозгалевский, А.В. Техническая диагностика / А.В. Мозгалевский, Д.В. Гаскаров. — М.: Высшая школа, 1975 206 с.

5. Гаскаров, Д.В. Прогнозирование технического состояния и надежности радиоэлектронной аппаратуры / Д.В. Гаскаров, Т.А. Голинкевич, А.В. Мозгалевский. — М.: Сов. радио, 1974 224 с.

6. Шибанов, Г.П. Техническая диагностика систем методом распознавания двумерных сигналов / Б.В. Городецкий, J1.T. Тотаев // Вопросы технической диагностики. — Таганрог : Вып. 1. ТРТИ, 1970.

7. Пархоменко, П.П. Основы технической диагностики: (Оптимизация алгоритмов диагностирования, аппаратурные средства) / П.П. Пархоменко, Е.С. Согомонян: под ред. П.П. Пархоменко. — М. : Энергия, 1981.- 320 с.

8. Дмитриев, А.К. Применение алгоритмов распознавания образов в задачах технической диагностики / А.К. Дмитриев, В.В. Александров // Техническая диагностика. М.: Наука, 1972. С. 127- 130.

9. Dhyllon, B.S., С. Singh, Engineering Reliability, New Techniques and Applications, Willey&Sons, London, 1981.

10. Henley, E. J., H. Kumamoto, Reliability Engineering and Risk Assessment, Prentice-Hall, New York, 1982

11. Давыдов, П.С. Техническая диагностика радиоэлектронных устройств и систем / П.С. Давыдов. — М.: Радио и связь, 1988 256с.

12. Карибский, В.В. Техническая диагностика объектов контроля / В.В. Карибский, П.П. Пархоменко, Е.С. Согомонян. М. : Энергия, 1967. -78 с.

13. Карибский, В.В. Основы технической диагностики / В.В. Карибский, П.П. Пархоменко, Е.С. Согомонян, В.Ф. Далчев. М. : Энергия, 1976. -464 с.

14. Согомонян, B.C. О диагностике неисправностей в дискретных блочных объектах. / B.C. Согомонян // Автоматика и телемеханика. МО.: 1969, С. 156- 167.

15. Согомонян, B.C. Контроль работоспособности и поиск неисправностей в функционально связанных системах. / B.C. Согомонян // Автоматика и телемеханика, МО.: 1964, т.25, № 6, С. 980- 990.

16. Маркович, З.П. Предварительное определение диагностических параметров / З.П. Маркович // Кибернетика и диагностика : сб. ст. -Рига : Зинатне, 1969, вып.З, С. 19- 32.

17. Осис, Я.Я. Алгоритм предварительного выбора эффективных диагностических параметров / Я.Я. Осис, З.П. Маркович // Кибернетика и диагностика : сб. ст. Рига: Зинатне, 1970, вып.4, С. 77 - 91.

18. Аузинь, П.К. Минимизация числа точек съема диагностической информации, основанная на алгебраическом анализе структуры граф-модели сложного объекта / П.К. Аузинь, Я.Я. Осис // Кибернетика и диагностика : сб. ст. Рига: Зинатне, 1969, вып.З, С. 33- 42.

19. Гаркавенко, С.И. О диагностике неисправностей в непрерывных объектах / С.И. Гаркавенко, В.И. Сагунов // Автоматика и телемеханика, 1976, №9, С. 177- 187.

20. Гаркавенко С.И. О доопределении минимальной совокупности точек контроля с целью поиска неисправностей произвольной кратности в непрерывных объектах диагностирования. / С.И. Гаркавенко, В.И. Сагунов // Автоматика и телемеханика, 1977, №7, С. 175- 179.

21. Мозгалевский, А.В. Техническая диагностика (непрерывные объекты). Обзор / А.В. Мозгалевский // Автоматика и телемеханика. -1978, № 1, С. 145- 166.

22. Методика выбора диагностических параметров для непрерывных объектов, представленных логическими моделями. -Горький: Гос. Комитет стандартов СМ СССР, ВНИИНМАШ, 1977. 67 с.

23. Методика выбора диагностических параметров для непрерывных объектов, представленных логическими моделями в форме графа, с помощью ЭВМ. -Горький: Горьковский филиал ВНИИНМАШ, 1978. -79 с.

24. Пашковский, Г.С. Задачи оптимального обнаружения и поиска отказов в РЭА / Г.С. Пашковский. М.: Радио и связь, 1981. - 280 с.

25. Литвин, А.И. Распознавание отказов в системах автоматики с помощью ортогональных дискретных функций / А.И. Литвин, О.В. Подгорный, А.А. Засядько // Электронное моделирование. -1995,- 17, №2. С. 67-69.

26. Дмитриев, А.К. Модель процесса диагностирования технических объектов при использовании непрерывных диагностических признаков / А.К. Дмитриев, И.Д. Кравченко // Изв. Вузов. Приборостроение. -1994, №11-12. С. 3-9.

27. Дмитриев, А.К. Выбор диагностических признаков с максимальной разрешающей способностью / А.К. Дмитриев, И.Д. Кравченко // Изв. Вузов. Приборостроение, -1996, -39, №4. С.3-7.

28. Дмитриев, А.К. Методы и алгоритмы синтеза оптимальных систем диагностирования сложных технических объектов по критерию минимума затрат / А.К. Дмитриев, И.Д. Кравченко С.П. Винниченко // Надежность и контроль качества. -1996, №7. С.43-50.

29. Рекомендации по оценке контролепригодности машин и приборов. -Горький : Горьковский филиал ВНИИНМАШ, 1972.- 26 с.

30. Методика выбора показателей и оценки уровня контролепригодности конструкций машин и приборов. Горький: Горьковский филиал ВНИИНМАШ, 1975.- 42 с.

31. Методические указания по проектированию контролепригодных устройств и систем / АН УССР, Ин-т проблем моделирования в энергетике. Сост. Гуляев В. А. Киев: Наук. Думка,1985.-32 с.

32. Жуков, М.В. Показатели системы диагностирования / М.В. Жуков, В.В. Карибский // Автоматика и телемеханика. -1979, №7. С. 137-145.

33. Сагунов, В.И. Обеспечение максимальной глубины поиска дефекта при заданном числе дополнительных точек контроля / В.И. Сагунов // Надежность и контроль качества. -1979, № 10. С.З- 7.

34. ГОСТ 23563-79. Техническая диагностика. Контролепригодность объектов диагностирования. Введен 18.04.79. - 11 с.

35. ГОСТ 24029-80. Техническая диагностика. Категории контролепригодности объектов диагностирования. Введен 10.03.80. -8 с.

36. Давыдьков, А.И. Оптимизация глубины диагностирования технических объектов. / А.И. Давыдьков // Сб. "Техническая диагностика электронных систем". Киев: Наук. Думка, 1982. С.51-56.

37. Нечаев, B.C. Минимизация эксплуатационных издержек на автомобильном транспорте / B.C. Нечаев // Сб. трудов НИИУавтопром. -Горький, 1982, вып. 2. С.84- 85.

38. Гуляев, В.А. Техническая диагностика управляющих систем / В.А. Гуляев. Киев: Наук. Думка, 1983. - 208 с.

39. Надежность технических систем : Справочник / Ю.К. Беляев и др.. -М.: Радио и связь, 1985.- 608 с.

40. Птицына, JI.K. Применение графовых моделей для определения показателей качества обнаружения появляющихся дефектов / JI.K. Птицына, E.JI. Трубицына // Сб. науч. Трудов С.-Петербург. Гос. Техн. Ун-т. -1995, №452. С. 110-120.

41. Птицына, JI.K. Оценка показателей качества обнаружения появляющихся дефектов при двухуровневой системе принятия решений / JI.K. Птицына // Сб. науч. Трудов С.-Петербург. Гос. Техн. Ун-т.- 1995, №452. С.98-109.

42. Соколова, Э.С. Об одном алгоритме диагностирования одиночных дефектов / Э.С. Соколова // Стандарты и качество. Методы менеджмента качества. №7, 2001. С.28-30.

43. Соколова, Э.С. Разработка и реализация моделей, методов и алгоритмов решения задач оптимального синтеза контролепригодных объектов: дис. д-ра техн. наук. / Э.С. Соколова Нижний Новгород., 2001.-351 с.

44. Ломакина, Л.С. Контролепригодность структурно связанных систем / Л.С. Ломакина, В.И. Сагунов. М.: Энергоатомиздат. 1990 - 111 с.

45. Сагунов, В.И. Влияние глубины диагностирования на структурную надежность систем "человек-машина" / В.И. Сагунов и др.// VII Всесоюзный симпозиум "Эффективность, качество и надежность систем "человек-техника": Тезисы докл. Часть 2.-М.,1984.С.71.

46. Беляева, С.И. Алгоритм построения минимальной диагностирующей матрицы для определения кратных дефектов / С.И. Беляева, В.И. Сагунов // Автоматизация процессов обраб. первич. инф. 1993. -№18.- С. 128- 134,150.

47. Глущенко, В.В. Диагностико-прогнозирующие системы управления информационными процессами в сетевых комплексах Дис. : д-ра техн. наук : 05.13.06 СПб., 1999.

48. Глущенко, П.В. Диагностирование электротехнических объектов на основе моделей / П.В. Глущенко. — СПб.: СПГУВК, 1996.

49. Глущенко, П.В. Техническая диагностика: Моделирование в диагностировании и прогнозировании состояния технических объектов / П.В. Глущенко.— М.: Вузовская книга, 2004. 248 с.

50. Беляева, С.И. Теоретические основы структурного диагностирования и обеспечения контролепригодности сложных технических и программных объектов: Дис. д-ра техн. наук. / С.И. Беляева Горький. 1990.-264 с.

51. Чипулис, В.П. Диагностирование утечек в гидравлических цепях. / В.П. Чипулис//АиТ. 1997. №1. С. 150-159.

52. Емельянов, Е.Е. Теория и практика эволюционного моделирования / Е.Е. Емельянов, В.М. Курейчик, В.В. Курейчик. М.: Физматлит, 2003.

53. Давиденко, Генетический алгоритм для трассировки двухслойных каналов / В.Н. Давиденко, В.М. Курейчик // Журн. "Автоматизация проектирования". 1999. №1, Издательство "Открытые системы" (http://www.osp.ruA.

54. Гладков, JI. А. Генетические алгоритмы: учеб. пособие / JI. А. Гладков, В.М. Курейчик, В.В. Курейчик. Ростов-на-Дону : ООО «Росиздат», 2004.-400 с.

55. Батищев, Д.И. Поисковые методы оптимального проектирования / Д.И. Батищев. -М.: Сов. радио, 1975-216 с.

56. Батищев, Д.И. Методы оптимального проектирования / Д.И. Батищев. М.: Радио и связь, 1984.-248 с.

57. Батищев, Д.И. Вычислительная сложность экстремальных задач переборного типа / Д.И. Батищев, Д.И. Коган. Н.Новгород : Нижегород. гос. ун-т., 1994.-111 с.

58. Батищев, Д.И. Генетические алгоритмы решения экстремальных задач / Д.И. Батищев // Учеб. пособие. Воронеж, гос. техн. ун-т; Нижегородский гос. ун-т. Воронеж, 1995, 69 с.

59. MIL-HDBK-756B, Reliability Modeling and Prediction, 1982.

60. MIL-HDBK-217, Revision F, Notice 2, Military Handbook. Reliability prediction of electronic equipment, 1995.

61. Billinton R., Allan R. N., Reliability Evaluation of Power Systems, Plennum press, New York&London, 1984.

62. R. Sahner, et al., Performance and Reliability Analysis of Computer Systems, Kluwer Academic Publishers, 1996.

63. Ammar H., Cukic В., Fuhrman C., and Mili A., "A Comparative Analysis of Hardware and Software Reliability Engineering", Institute for Software Research Fairmont, USA 1999.

64. Karen S. Kurasaki Intercoder Reliability for Validating Conclusions Drawn from Open-Ended Interview Data Field Methods, Vol. 12, No. 3, August 2000 p.179-194.

65. Thorhuus R. "Software Fault Injection Testing", Master of Science Thesis in Electronic System Design, Stockholm, February, 2000.

66. Watson A.H., McCabe T.J. Structured Testing: A Testing Methodology Using the Cyclomatic Complexity Metric // NIST Special Publication 500235./ Ed. By Wallace D.R. Gaithersburg, National Institute of Standards and Technology, 1996.123 p.

67. Гаранин, Ю.А. Минимизация числа точек съема диагностической информации / Ю.А. Гаранин, В.И. Сагунов // Межвузовский сб. научных трудов. Системы обработки информации и управления. -Н.Новгород : НГТУ. 1997.- С. 44-45.

68. Сагунов В.И. О поиске кратных ошибок в программных модулях / В.И. Сагунов, М.Е. Бушуева, Э.С. Соколова // Контроль и диагностика. 2001. №8. С. 11-13.

69. Соколова, Э.С. Обнаружение дефектов в процессе проектирования и эксплуатации программ / Э.С. Соколова, Д.В. Дмитриев // Успехи современного естествознания М. : «Академия естествознания». 2004. №2. С. 74-76.

70. Соколова, Э.С. Обеспечение контролепригодности технических систем с помощью эволюционного моделирования / Э.С. Соколова, С.Н. Капранов // Методы менеджмента качества. 2004. №8. С. 42-46.

71. Капранов, С.Н. Разработка моделей и методов синтеза контролепригодных объектов с помощью генетических алгоритмов : дис. канд. техн. наук. / С.Н. Капранов. Нижний Новгород. 2004. -150с.

72. Соколова, Э.С. Оптимизация коэффициента глубины поиска дефектов методом генетических алгоритмов / Э.С. Соколова, С.Н. Капранов //Журн. Контроль. Диагностика. -2004. №4. С. 32-40.

73. Воронин В.В. Множество возможных дефектов и виды технических состояний / В.В. Воронин // Приборы и системы. Управление, контроль, диагностика. -2002. №6. С. 41-45.

74. Богатырев, В.А. Отказоустойчивость компьютерных систем при многофункциональности модулей / В. А. Богатырев // Информационные технологии. 2002. №12. С. 2-7.

75. Богатырев, В.А. Эффективность обеспечения отказоустойчивости вычислительных систем на основе динамического распределения запросов / В.А. Богатырев // Информационные технологии. -2002. №4. С. 42-48.

76. Богатырев, В.А. О модификации функции «перманент матрицы» и ее применении в комбинаторных методах анализа надежности вычислительных систем / В.А. Богатырев // Информационные технологии. 2002. № 1. С. 5-11.

77. Жуков, О. Д. Обнаружение и коррекция ошибок компьютерных вычислений на основе модулярной алгебры / О. Д. Жуков // Информационные технологии. 2002. №6. С. 15-24.

78. Жуков, О. Д. Методы контроля ошибок для компьютерных модулярных вычислений / О.Д. Жуков // Информационные технологии. 2003. №2. С. 33-39.

79. Мироновский, JI.A. Диагностирование линейных систем методом комплементарного сигнала / JI.A. Мироновский // Информационные технологии. 2002. №5. С. 52-57.

80. Ведешенков, В.А. Организация самодиагностирования технического состояния цифровых систем / В.А. Ведешенков // Автоматика и телемеханика. 2003. №11. С. 165-182.

81. Ведешенков, В.А. Подход к самодиагностированию возникающего отказа в цифровых системах / В.А. Ведешенков // Автоматика и телемеханика. -2005. №4. С. 127-140.

82. Липаев, В.В. Надежность программных средств / В.В. Липаев. М. : Синтег, 1998.

83. Standard IEEE 1219-1998. Software maintenance.

84. IEC 60880 Ed. 1.0 b: 1986. Software for computers in the safety systems of nuclear power stations.

85. NIST 500-234 1996. Reference information for software verification and validation process.

86. ГОСТ 28806-90. Качество программных средств. Термины и определения.-М.: Изд-во стандартов, 1991.

87. Хренов, Н.Н. Основы комплексной диагностики северных газопроводов / Н.Н. Хренов. М.: Газоил пресс, 2003. - 352 с.

88. Ионин, Д.А. Современные методы диагностики магистральных газопроводов / Д.А. Ионин, Е.И. Яковлев. JI.: Недра, 1987. - 232 с.

89. Соловьев, А.В. Метод обеспечения отказоустойчивости распределенных систем управления со случайным потоком заявок и статическим распределением задач / А.В. Соловьев, Е.Н. Турута // Управление ресурсами в интегральных сетях. М. : Наука. 1991. С. 109116.

90. Черноруцкий, И.Г. Методы оптимизации и принятия решений / И.Г. Черноруцкий. СПб.: Лань, 2001.-384 с.

91. Степаненко, М.А. Контролепригодность обьекта диагностирования с одиночными дефектами / М.А. Степаненко // Информационные системы и технологии (ИСТ-2003): тез. докл. всеросс. науч.-техн. конф., Нижегород. гос. техн. ун-т. Н.Новгород, 2003. С.132-133.

92. Степаненко, М.А. Решение задачи распределения коэффициента глубины диагностирования в сложной системе / М.А. Степаненко // Системы обработки информации и управления: Труды Нижегород. гос. тех. ун-та / НГТУ.- Н.Новгород, 2003. Т.37. В.10. С. 83-92.

93. Соколова, Э.С. Об основных принципах тестирования программ/ Э.С. Соколова, М.А. Степаненко// Информационные системы и технологии (ИСТ-2004): тез. докл. всеросс. науч.-техн. конф., Нижегород. гос. техн. ун-т. Н.Новгород, 2004. С.109-110.

94. Соколова, Э.С. Формализованный подход к тестированию кратных ошибок в программных модулях / Э.С. Соколова, М.А. Степаненко // Системы обработки информации и управления: Труды Нижегород. гос. тех. ун-та/НГТУ.- Н.Новгород, 2004. Т.47. В. 11. С. 90-93.

95. Степаненко, М.А. Оптимизация автоматического метода синтеза ацикличного однонаправленного графа / М.А. Степаненко // XI Нижегородская сессия молодых ученых. Технические науки "Татинец", 12-16 февраля 2006г., Н.Новгород. С. 29-30.

96. Соколова, Э.С. Разработка алгоритма локализации дефектов на назначенной совокупности контрольных точек / Э.С. Соколова, М.А. Степаненко //Журн. Контроль. Диагностика. 2006. №9. С. 41-44.