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

НИЖЕГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

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

разработка моделей и алгоритмов ОПТИМИЗАЦИи процедур ДИАГНОСТИрования на граф-моделях

технических систем

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

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

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

200 7

Работа выполнена на кафедре «Информатика и системы управления»

Нижегородского государственного технического университета (НГТУ)

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

профессор Соколова Э.С.

Официальные оппоненты: доктор технических наук,

профессор Кирьянов К.Г.

кандидат технических наук,

доцент Уваров П.И.

Ведущая организация: Научно-исследовательский Центр

контроля и диагностики,

Н.Новгород

Защита состоится «_____» ________________ 2007 г. в __________ часов на заседании диссертационного совета № Д.212.165.05 в Нижегородском государственном техническом университете по адресу: 603600, г. Нижний Новгород, ГСП-41, ул. К.Минина, 24.

С диссертацией можно ознакомиться в библиотеке НГТУ.

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

Автореферат разослан «_______» _______________ 2007 г.

Ученый секретарь

диссертационного совета

к.т.н., доцент А. П. Иванов

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

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

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

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

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

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

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

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации

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

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

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

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

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

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

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

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

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

Для целей диагностирования восстанавливаемые структурно-сложные объекты представляются граф-моделями с множеством входов X=(x1, x2, …, xn) и выходов Z=(z1, z2, …, zm), где n и m достаточно большие величины (до 100 и более единиц) (рисунок 1). Вершины графа представляют возможные состояния объекта, вызванные дефектами – отказом структурных элементов, выходом за пределы допуска параметров, событиями или явлениями, вызывающими неисправности в объекте, а дуги отражают соответствующие причинно-следственные связи. Граф упорядочивается так, что направление дуги в графе соответствует перемещению от причины дефекта к следствию и отражает направление распространения или обнаружения дефекта.

Пусть G=(V, A) – ориентированный упорядоченный граф без контуров и петель, где V=(v1, v2, …,vN) – множество вершин графа, соответствующих возможным дефектам, A=(a1, a2, …,ak)={(vi, vj), i, j=1,…,N} – множество дуг графа, отражающих причинно-следственные связи между дефектами. Эквивалентная матричная модель - матрица смежности вершин графа.

Обозначим X=(x1, x2, …,xn) – множество входных вершин графа  G, соответствующих функциональным входам исследуемого объекта, или входам, на которые возможна подача тестовых воздействий (в ГПСС – это дефекты, которые не являются следствием проявления других дефектов); Z=(z1, z2, …,zm) – множество выходных вершин графа, соответствующих диагностическим параметрам, снимаемым в точках контроля.

Матрицей проверок называется матрица B, составленная из N-мерных векторов проверок br(xi, zj)= (b1r, b2r, …,bNr), brB, компоненты которых bkr=1, если k-я вершина  (k=1,..., N) принадлежит хотя бы одному пути от xi к zj, и bkr=0 в противном случае.

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

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

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

Пусть n и m – количество входных и выходных вершин графа, тогда общее число строк в матрице B будет равно n·m. При построении оптимальной стратегии диагностирования по критерию минимального количества проверок, удовлетворяющих заданному критерию глубины поиска дефекта, в процессе работы алгоритма будут строиться матрицы проверок, содержащие 1, 2, …, n·m проверок. Количество всех возможных матриц, содержащих по i проверок из возможных n·m, вычисляется с помощью формулы сочетаний: .

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

Количество возможных проверок зависит от степени связности вершин графа. Учитывая коэффициент достижимости КД, характеризующий степень связности исследуемых графов и определяющий долю заполнения матрицы ненулевыми элементами: , (N – размерность матрицы достижимости D; – общее число элементов в матрице достижимости D; k - число ненулевых элементов в матрице достижимости D выше главной диагонали), получим общее число диагностических пар во всех построенных матрицах проверок для заданного графа с учетом его топологии: .

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

.

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

.

Суммируя значения l1 и l2, получим аналитическое выражение для определения общего количества элементарных операций сравнения элементов столбцов матрицы проверок:

Согласно полученному аналитическому выражению, даже для небольшого объекта, граф-модель которого имеет n=10 входов и m=10 выходов при общем числе вершин N=100 и значении КД = 0,2, количество операций сравнения пар элементов столбцов матрицы проверок будет составлять порядка 6,271034. И если ЭВМ обрабатывает, например, 3108 подобных операций в секунду, то потребуется 6,631018 лет на обработку данных для решения поставленной задачи методом полного перебора.

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

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

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