Диагностирование сложных систем на основе эволюционно-генетического моделирования тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат наук Губернаторов, Владимир Павлович

• Губернаторов, Владимир Павлович
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Губернаторов, Владимир Павлович

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ ДИАГНОСТИРОВАНИЯ СЛОЖНЫХ СИСТЕМ

1.1 Основные теоретические направления технического диагностирования

1.2 Выводы и постановка задачи

ГЛАВА 2. БАЗОВАЯ МОДЕЛЬ ОБЪЕКТА ДИАГНОСТИРОВАНИЯ

2.1 Необходимые понятия и определения

2.2 Математическое описание объекта диагностирования

2.3 Формальная постановка задачи

2.4 Выводы

ГЛАВА 3. ДИАГНОСТИЧЕСКАЯ МОДЕЛЬ ОБЪЕКТА

3.1 Построение модификации эволюционно-генетического алгоритма

3.1.2 Кодирование решений

3.1.3 Выбор операторов рекомбинации

3.1.4 Выбор операторов селекции и поисковой стратегии

3.1.5 Формирование начальной популяции

3.1.6 Выбор критерия останова

3.1.7 Схема разработанной модификации эволюционно-генетического алгоритма

3.1.8 Возможности применения параллельных вычислений

3.1.9 Аналитическая оценка вычислительной сложности разработанной модификации эволюционно-генетического алгоритма

3.3 Нахождение оптимальной тестовой последовательности с помощью метода динамического программирования

3.4 Нахождение оптимальной тестовой последовательности с помощью метода имитации отжига

3.5 Выводы

-2ч ч

Введение диссертации (часть автореферата) на тему «Диагностирование сложных систем на основе эволюционно-генетического моделирования»

ВВЕДЕНИЕ

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

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

Данной проблеме посвящено большое количество работ отечественных и зарубежных авторов: Г.Ф. Верзаков, П.П. Пархоменко, В.И. Сагунов, А.Ю. Аржененко, Д.В. Сперанский, В.В. Сапожников, М.А. Владимиров, J. Wegener, J. Ribero, A. Arcury, J. Shiozaky,H др.

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

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

Достижение цели работы предполагает решение следующих задач:

• анализ существующих моделей и алгоритмов диагностирования и научно-техническое обоснование темы исследования;

• выбор базовой модели, описывающей сложный объект диагностирования как систему;

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

• оценка вычислительной сложности разработанных алгоритмов;

• программная реализация разработанных алгоритмов;

• разработка методики реализации полученных результатов.

Методы исследования, применяемые в работе, основаны на теории графов, теории вероятностей, динамическом программировании, имитации отжига и эволюционно-генетическом моделировании. Для анализа и применения полученных результатов выполнено компьютерное моделирование разработанных алгоритмов на языке программирования С++. Научная новизна работы состоит в следующем:

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

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

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

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

Практическая ценность и рекомендации по использованию результатов.

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

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

Разработанные алгоритмы применяются в Институте проблем машиностроения Российской академии наук, что подтверждается актом о внедрении. Они также используются в учебном процессе при подготовке магистрантов направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. P.E. Алексеева.

Разработанный программный комплекс зарегистрирован в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ. Свидетельство об официальной регистрации программ для ЭВМ № 009613297.

Результаты работы использованы в госбюджетной НИР (Отчет по НИР «Диагностика технических и программных систем с использованием современных информационных технологий». Номер государственной

регистрации 01.2009.00405 от 28.01.09 - Н. Новгород: НГТУ), выполненной в рамках НИОКР «Диагностические и информационно-поисковые системы» (Номер регистрации 01201252337, интернет-номер И111112195013, руководитель работы Ломакина Л.С.).

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

1. Диагностическая модель сложной системы, включающая алгоритмы построения оптимальных тестовых последовательностей.

2. Модификация эволюционно-генетического алгоритма для

эффективного диагностирования сложных систем.

3. Метод диагностирования сложной технической системы,

основанный на разработанной модификации.

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

- Международных научно-технических конференциях «Информационные системы и технологии (ИСТ-2009, ИСТ-2010, ИСТ-2011, ИСТ-2013)» (Нижний Новгород);

- XV Международной открытой научной конференции «Современные проблемы информатизации» (Воронеж, 2010);

- IV Всероссийской научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, 2010);

- X Международной молодежной научно-технической конференции «Будущее технической науки» (Нижний Новгород, 2011);

- XVI Нижегородской Сессии молодых учёных (Нижний Новгород, 2011);

- XVII Международной научно-практической конференции «Системный анализ в проектировании и управлении» (Санкт-Петербург, 2013). Публикации. По теме диссертации опубликовано 15 работ, в том числе

3 статьи в ведущих рецензируемых научных журналах и изданиях, рекомендованных ВАК, свидетельство о государственной регистрации программы для ЭВМ № 009613297

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка и приложений. Общий объём работы 129 страниц текста, содержащего 64 рисунка и 5 таблиц. Список литературы содержит 90 наименований.

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

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

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

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

Четвёртая глава {Практическая реализация и вычислительный эксперимент). Выполнена оценка сложности разработанных алгоритмов и рассмотрено их применение на реальном примере.

В заключении изложены основные научные и практические результаты диссертационной работы. Приложение содержит:

• Акт о внедрении разработанной автоматизированной системы диагностирования технических систем в Институте проблем машиностроения РАН,

® Акт о внедрении результатов диссертационной работы в учебный процесс подготовки магистрантов направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. P.E. Алексеева,

• Свидетельство о государственной регистрации программы для ЭВМ.

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ МЕТОДОВ ДИАГНОСТИРОВАНИЯ СЛОЖНЫХ СИСТЕМ 1.1 Основные теоретические направления технического

диагностирования

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

Основной целью технической диагностики является эффективное определение диагноза объекта.

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

Техническое диагностирование решает задачи [2]:

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

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

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

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

ГЛАВА 4. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ......................................90

4.1 Описание программной реализации..........................................................90

4.2 Экспериментальная оценка вычислительной сложности........................97

4.3 Исследование схождения разработанной модификации эволюционно-генетического алгоритма................................................................................103

4.4 Нахождение оптимальной тестовой последовательности на примере диагностирования СИФУ автоматизированного электропривода.............105

4.4 Нахождение оптимальной тестовой последовательности для сложной системы на примере диагностирования комплектного автоматизированного электропривода..........................................................110

4.5 Выводы.......................................................................................................118

ЗАКЛЮЧЕНИЕ....................................................................................................119

БИБЛИОГРАФИЧЕСКИЙ СПИСОК................................................................120

ПРИЛОЖЕНИЯ...................................................................................................130

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

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

Рис 1. Схема тестового (а) и функционального (б) диагностирования. СД - система диагностирования. ОД - объект диагностирования.

Решение задачи определения состояния объекта с помощью тестового или функционального диагностирования требует построения:

1. модели объекта диагностирования;

2. алгоритмов и методов диагностирования;

3. методов оценки полноты и эффективности диагностирования. Построение модели объекта диагностирования, является

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

Модель объекта диагностирования должна включать в себя представление информации о [3]:

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

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

3. О разработанных тестах. Под тестом следует понимать процесс оценки диагностических параметров объекта.

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

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

Для проверки или исправности или работоспособности непрерывных объектов широкое применение находят аналитические модели, связанные с «формульным» представлением объекта диагностирования.

В работах [4, 5, 6, 7] в качестве модели объектов диагностирования используются системы дифференциальных уравнений либо передаточных функций.

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

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

В работе [6] предлагается метод диагностирования, основанный на использовании модели системы в виде амплитудно-частотных характеристик. В качестве базовых функций разложения используются ортогональные полиномы. Вводится понятие га-преобразования и на его основе предлагается метод вычисления коэффициентов разложения исследуемой функции в ряд Фурье. Методика применяется для диагностирования систем автоматического управления. Так же указывает высокая сложность данной методики.

Если качество переходных процессов является существенным условием работоспособности объекта, моделью может выступать система дифференциальных уравнений. В работе [7] для решения задачи поиска дефектов применяют аппарат теории идентификации, а дифференциальные уравнения используются в форме "ТАРовских" структурных схем. Элементами такой структурной схемы является функциональные блоки, описанные аналитически в виде передаточных функций.

В работе [8] так же применяется модели в виде дробно-рациональных передаточных функций и систем дифференциальных уравнений. Рассматриваются линейные динамические и нелинейные статические системы. Производится анализ методов обнаружения неисправностей на основе различных алгоритмов классификации и логического вывода. Рассмотренные модели применяются на примерах диагностирования системы регулирования давления в пневморессоре самолёта и системы управления движением легкового автомобиля.

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

Использование логической модели позволяет решать все перечисленные выше задачи диагностирования для контактных, цифровых и динамических систем [9].

Одной из первых моделей данного типа является двузначная логическая модель, представленная в работе [10]. При построении данной модели исследуемый объект представляется функциональной схемой в виде совокупности блоков и связей между ними. Каждому блоку функциональной схемы ставят в один или несколько логических блоков, имеющих один входной и один выходной параметр. Множество допустимых значений входных и выходных параметров считается известным. Логический блок считается неисправным, если при допустимом входном сигнале на выходе наблюдается недопустимый сигнал. Исправному состоянию ставится в соответствие значение «1», неисправному - «0».

Формально логическая модель является графом, вершинами которого являются логические блоки, а рёбрами - связи между блоками. Логические модели в виде графа, отражающего структуру объекта, применяются в работах [11, 12, 13].

Для моделирования программных систем широко применяется управляющий граф. Управляющий граф — модель программной системы, представляющая в виде орграфа поток управления (систему управляющих связей) в программе.

Для построения данной модели используется:

• членение программы на операторы (команды);

• информация о тождественности операторов;

• информация о возможных управляющих связях между операторами.

Считается, что между операторами () и 5 существует управляющая связь, если оператор передает управление оператору 5 (возможно, при выполнении некоторых условий).

Формально управляющий граф — это помеченный упорядоченный мультиграф с выделенной начальной вершиной (входом) и непустым множеством конечных вершин (выходов).

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

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

Рис. 2. Фрагмент программы на языке С и соответствующий ему

управляющий граф.

В настоящее время в качестве диагностической модели часто используют не сам управляющий граф, а его модификацию — информационный граф. Под информационным графом понимается управляющий граф программы, который дополнен схемой потока данных участвующих в вычислениях [11]. Такой граф позволяет учитывать зависимости и по данным, и по управлению [12]. Его использование позволяет обнаруживать более широкий спектр ошибок: ошибки, связанные с неправильным заданием константы, неправильным заданием типа переменной, неверным форматом данных, ошибки в спецификациях, в

размещении переменных и массивов; неверную расстановку и функционирование флажков, неправильное окончание программных последовательностей, отсутствие инициализации переменных, неправильное формирование и употребление логических выражений [12, 13].

Рис. 3. Фрагмент программы и соответствующая ему схема потока

данных.

Для тех случаев, когда трудно выделить конструктивные функционально самостоятельные блоки применяют логические модели, основанные на аппарате теории распознавания образов [14], либо имитационные логические модели.

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

х-а-Чэ у=а*с

х=а-гЬ; ¡Г(х<100) {у=а*с,} еЬе

{У=а+с;}

Рис. 4. Фрагмент программы на языке С и соответствующий ему

информационный граф.

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

Когда для каждой компоненты вектора состояния системы задан закон распределения вероятности, для поиска неисправностей может быть использована модель в виде сети Байеса [15]. Применение Байесовой сети в задачах диагностирования рассмотрено в работах [16, 17, 18]. Данная модель представляет собой вероятностное дерево событий. Байесова сеть — это ациклический орграф, вершины графа соответствуют событиям, рёбра — отображают условные зависимости между этими событиями (Рис. 5). Две вершины А и В Байесовой сети считаются условно независимыми если каждый путь из А в В (или из В в А) содержит хотя бы один узел С \(СФ А)/\(СФ В) .

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

Р(С | Д) - вероятность диагноза С после того, как стало известно наличие у исследуемого объекта признака /);

Рф | С) - вероятность появления признака Б у объекта, находящегося в состоянии С; Р(С) - вероятность диагноза С;

И - вероятность появления признака И во всех объектах рассматриваемого множества, независимо от их состояния;

Р уу; =Р(д\аЪс) р'00= РОМ)

Рис.5. Пример Байесовой сети.

Процесс расчёта условных вероятностей для всех вершин называется обучением сети.

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

Первому слою сети соответствуют диагностические параметры объекта, последнему слою - события, соответствующие состояниям объекта: исправен или неисправность в /- м блоке. Промежуточные слои, называющиеся «сенсорами», являются вспомогательными и используются для задания причинно-следственных связей между событиями первого и последнего слоя.

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

При использовании сети Байеса в качестве результирующего состояния объекта диагностирования выбирается состояние С с максимальной апостериорной вероятностью Р(С\Э).

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

соответствующему определённой неисправности. К моделям рассмотренного типа относятся искусственные нейронные сети [19], применяющиеся для решения задач поиска дефектов в работах [20, 21, 22].

В основе нейросетевого моделирования лежит математическая модель живого нейрона (Рис. 6). Синапсы живого нейрона моделируются с помощью весов, присваиваемых соответствующим входам. Отрицательный вес присваивается входам, которые должны тормозить реакцию нейрона положительный — входам, возбуждающим нейрон.

Смещение Ы'кО

Фиксированный вход Хо = ±1

Входные сигналы

—^Ю/кО

(XI о—

Хр \

Функция Сумматор активации

Выход У к

Веса^Ча, ¡=!...р

Порог 8к

Рис. 6. Модель «Искусственный нейрон».

Тело клетки-нейрона моделируется сумматором и функцией активации. Сумматор вырабатывает некоторый сигнал, который определяется как линейная комбинация входов нейрона, взятых с определёнными весами. Функция активации формирует выход У нейрона и может быть нескольких видов:

- Пороговая функция активации может принимать два значения: 0, если выход сумматора меньше заданного значения вк , или 1 - в противном случае.

- Кусочно-линейная функция активации ф(у)=

-1 V > 1 /2

0 | —1/2<у< 1/2 .

1 V <— 1 /2

- Сигмоидальная (Б-образная) функция активации ср(у) = 1ап\\(у/2) . Искусственная нейронная сеть может рассматриваться, как направленный граф с взвешенными связями, в котором искусственные

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

Перед использованием нейросеть необходимо обучить, подобрав для каждого нейрона значения весов м> и порога в (Рис. 7).

Входные параметры, обеспечивающие желаемое значение на выходе

Рис. 7. Обучение искусственной нейронной сети.

В диагностировании искусственные нейронные сети используются как системы статической классификации состояний системы (используют правила, полученные при обучении, для преобразования вектора параметров системы в код состояния системы). При этом используют различную архитектуру нейронных сетей [19]. В работах [21, 22] строится одна нейросеть, которая обучается на распознавание всех возможных состояний системы (Рис. 8а). При возможности появления в диагностируемой системе кратных ошибок обучение такой сети становится весьма сложной задачей. Используются обобщенно-регрессионная нейронная сеть (вИ^ГМ) с топологией прямой передачи сигнала, вероятностная нейронная сеть (Р1Ч]Ч) и адаптивная (самоорганизующаяся) нечеткая нейронная сеть.

Список литературы диссертационного исследования кандидат наук Губернаторов, Владимир Павлович, 2013 год

Список типов

[Тип 1]Маркер «красный» .

БЩип!]

[Тип! А],Л.Г=Л.7-7.

82[Тип2]

[Тип1 А]

Сч ётгчик_п о_м ад ул ю!4? X Перечисление V [0... К]

ь

[1ип 2] Маркер «жёлтый» : { Счётчик_по_м одулюТУ X}; (Тип 3] Маркер «синий» :

[Гип1А]

Л.Х++. А.У++.

[Тип! А]

[Тип2 С] [Тип2 С]=

С.Хтт-.

!—{ИхЖ

(А.У>0)&&(В.Х= С.Х)

[ТипЗВ], В.Х=А.Х,

[Данные Б],

г>=з.о.

53[ГшЯ О_ГТипЗВ]

54[Д энные]

Сч ёхчик_п о_ы од уто N X Данные В };

[Данные] Маркер «зелёный»

Рис. 10. Пример. Начальная маркировка цветной сети Петри (очередь).

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

В работе [25] распознавание дефекта системы контроля утечек газа (Рис. 11а) выполняется с помощью дерева распространения ошибок [26,27]. Как и сеть Петри, дерево распространения ошибки представляет собой двудольный ориентированный граф, состоящий из вершин двух типов — событий и переходов. Рёбра данного графа моделируют причинно-следственные связи между событиями. Переходы представляют собой элементарные операции булевой логики и задают правила срабатывания причинно-следственных связей между событиями (Рис. 116). Для входных событий могут быть известны вероятности, тогда для остальных событий подсчитываются условные вероятности по формуле Байеса. Две вершины-события А и В дерева распространения ошибок считаются условно

независимыми если путь каждый из А в В (или из В в А) содержит хотя бы две вершины типа переход С,И: (СфО).

Лампа Детектор Л'?]

Репе

Рис. 11а. Система обнаружения утечки газа.

Рис. 116. Дерево распространения ошибок для системы с Рис. 11а.

Ряд работ [28, 29, 30] посвящен диагностированию неисправностей с помощью графа причинно-следственных связей. В качестве объектов диагностирования рассматриваются системы различной физической природы: химические производства [28], системы человеко-машинного взаимодействия [29], систем внутрифабричного гидротранспорта.

Ориентированный граф может использоваться для представления причинно-следственных связей в системе (Рис. 12).

Ро

Р1

и 12 ¥2

Рис. 12. Система цистерн. Здесь и — обозначают потоки вещества между цистернами, а Ь/ и Ь2- уровни вещества в этих

цистернах.

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

@—ЦИ)-Ци)—Кв)--------

Рис. 13. Размеченный орграф для системы с Рис.12. — недопустимое убывание потока Fl приводит к блокировке канала между

цистернами 1 и 2.

Обычно считают, что каждый параметр может иметь только три состояния: высокий, нормальный и низкий, что обозначается на графе «+», «О» и «-» соответственно. Вершина размеченного орграфа называется значимой, если она соответствует ненулевому состоянию параметра, т. е. параметру, значение которого отклоняется от нормы.

о +

Рис. 14. Разметка вершин орграфа для системы с Рис. 12. при

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

Согласованные дуги отражают тот факт, что соответствующий данной дуге путь является путём распространения ошибки.

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

+

Рис. 15. Граф причинно-следственных связей для системы с Рис.12.

Граф причинно-следственных связей является имитационной моделью и используется в диагностировании как визуальная модель распространения ошибки в системе. Поиск ошибки осуществляется путём нахождения наиболее сильно связанных компонент этого графа (ядра) [28].

В работах [1, 2, 31, 32] производится дальнейшее развитие логических моделей, предлагается графо-матричная логическая модель, позволяющая использовать обобщенный подход к диагностированию технических систем различной природы. Матричное представление графа в виде таблицы функций неисправностей впервые рассматривается в работе [31]. Таблица функций неисправностей задаётся в виде прямоугольной матрицы у4 = ||а(/|| , строкам которой соответствуют проверки из заданного множества /7, а столбцам состояния объекта - Е. Столбец Е0 соответствует исправному состоянию исследуемого объекта. Элементы ац матрицы соответствуют результату проверки 77, при условии нахождении объекта в состоянии Е,. Таблица функций неисправностей может быть использована, как универсальная модель описания объекта при построении алгоритмов диагноза, даже когда изначальное описание объекта отлично от языка таблиц функций неисправностей [1]. В работе [32] рассматриваются примеры построения таблицы функций неисправностей для дискретных и непрерывных объектов. В работе [33] указывается возможность использования имитационных моделей для построения таблицы функций

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

В работах [1, 2] указывается, что непосредственное использование таблицы функций неисправности, как формы представления информации при решении задач диагноза, часто является невозможным по причине высокой размерности таблицы.

Интересный опыт в данном отношении имеет теория надежности [34,35,36,37], ее структурные модели для расчета количественных показателей надежности включают только те состояния, возможность которых по каким-либо причинам в заданном временном интервале не вызывает сомнений. Иными словами, уровень детализации элементов структурной модели объекта назначается исходя из статистических данных по интенсивности отказов его физических элементов.

В дальнейшем, в работах [38, 39, 40, 41] предлагается использовать матрицу проверок (матрицу идентификации). Столбцы матрицы проверок А = \\ац\\ соответствуют блокам (либо параметрам в случае имитационной модели) исследуемой системы. Элементы а,, матрицы равен 1, если тест 77, контролирует состояние блока Б, диагностируемой системы и равен 0 в противном случае.

Данная матрица обладает меньшей размерностью, чем таблица функций неисправностей, и может успешно применяться для диагностирования объектов любой природы: технических [40], программных [38] и аппаратно-программных систем [39].

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

Безусловный время-вероятностный подход, рассмотренный в работах [42], является экспериментально-статистическим методом построения условного алгоритма диагностирования [1,2]. Критерием оптимальности является математическое ожидание времени восстановления системы. Оптимизация диагностирования осуществляется в соответствии с отношением:

Р(еi) р{е2) Pie,) р(епр) f?)

t(ei)> t(e2) ••• ({е,) -¡(е„) U'

• p(e,) - вероятность неисправности блока е,;

• t(e,) - время необходимое для проверки блока е,.

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

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

Ряд работ [45, 46, 47] посвящен построению алгоритмов оптимального диагностирования методом динамического программирования. В качестве критерия оптимальности используется средняя стоимость исполнения условного алгоритма поиска неисправности. При этом учитывают результаты предыдущих проверок. Для этого выбирают первую проверку и в зависимости от ее исхода разбивают множество состояний S = {S,} объекта диагностирования на классы S° и S', а затем выбирают проверки, позволяющие выполнить дальнейшее разбиения этих классов. Выбор

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

Отдельно следует отметить группу работ [38, 48, 49, 50, 51, 52], посвященных решению задач оптимального диагностирования в базисе теории информации. Способ заключается в выборе минимального количества контролируемых параметров объекта и определении последовательности их контроля. На начальном этапе выбирается точка контроля, которая доставляет максимальное количество информации о системе. Для этого оцениваются значения вероятностей неисправностей блоков р(у,) методом статистического моделирования и вычисляется условная энтропия при условии, что система вышла из строя Н(Т). С этой целью случайным образом генерируется состояние системы. В качестве априорных сведений о системе используются вероятности появления дефектов в модулях. С увеличением числа диагностических экспериментов увеличивается точность оценки р(у) и Н{У). На каждом из последующих шагов выбирается та точка контроля, которая доставляет максимальное дополнительное количество информации. Процедура выбора точек контроля заканчивается после того, как будет выбрано заданное количество точек контроля или достигнута заданная глубина локализации дефекта. Известен так же модифицированный алгоритм, учитывающий стоимости проверок [38, 49].

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

Для диагностирования сложных систем используется декомпозиция [53, 54] либо приближённые методы.

Применение приближенных методов построения оптимальных алгоритмов диагностирования рассматривается в работах [ 55, 56, 57, 58, 59, 60, 61, 62].

В работе [55] рассматривается применение приближённых методов оптимизации в задачах диагностирования дискретных устройств.

В работе [56] выполняется тестирование программного обеспечения. Особое внимание уделяется применению универсальных популяционных алгоритмов оптимального тестирования. Предлагается кодировать тестовые программы в виде структур значений базовых типов. Данный способ кодирования позволяет использовать различные техники эвристического поиска, такие как метод восхождения к экстремуму (Hill climbing) или метод имитации отжига. Однако при предложенном кодировании в результате поиска могут возникать недопустимые решения, которые невозможно декодировать в тестовые программы, поэтому в работе вводится специальный механизм штрафов, искусственно снижающий значения целевой функции недопустимых решений. Из-за генерации недопустимых решений предложенный метод обладает низкой эффективностью при диагностировании сложной системы системы.

Дальнейшее развитие рассмотренные методы получили в работе [57]. В данной работе рассматривается диагностирование программ, написанных на языке Java. Тестовая программа строиться на уровне байт кода и выполняется символьно с помощью модифицированного компилятора JML. Проводится исследование эвристических алгоритмов: метод имитации отжига, муравьиный алгоритм и метод восхождения к экстремуму. Для генерации тестовых программ используются STGP (строго типизированный генетический алгоритм). Основным достоинством предложенного подхода является возможность тестирования программ от сторонних разработчиков, когда исходный код программы не доступен. Особое внимание в данной работе уделено использованию эволюционно-генетических алгоритмов.

Применению эволюционно-генетического моделирования в задачах диагностирования посвящены работы [ 58, 59, 60, 61].

В работе [58] впервые описано применение эволюционной оптимизации для генерации тестовых данных. Тестовые данные здесь

генерируются случайно. Генетический алгоритм применяется для дополнения набора сгенерированных тестов в том случае, если сгенерированный набор не обеспечивает полного покрытия ветвей управляющего графа программы.

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

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

В работе [61] описано применение строго типизированного генетического программирования (8ТСР) при тестировании объектно-ориентированного программного обеспечения. Тестовые программы представляются, как деревья вызовов (МСБ). Данные деревья отображают зависимости между вызовами методов, заданного тестового объекта. Совместное использование 8ТСР и МС8 позволяет учитывать свойства наследования и полиморфизма обеспечивает синтаксическую корректность (компилируемость) получаемых тестовых программ. Для повышения

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

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

1.2 Выводы и постановка задачи

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

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

• Логические модели:

о структурные граф-модели (двузначная логическая модель,

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

о модели, основание на теории распознавания образов (Байесовы

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

Основным достоинством логических моделей является простота их построения и применения. Так же следует отметить, что данная модель не

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

• перечень точек подачи рабочих и тестовых воздействий;

• перечень точек проверки диагностических параметров с описанием способов их оценки и данными о затратах материальных ресурсов на оценку;

• перечень допустимых значений диагностических параметров;

• описание возможности появления различных дефектов одного и того же элемента системы.

Однако следует отметить ряд недостатков:

• структурные логические модели требуют наличия выделенных технологических или функциональных блоков;

• имитационные модели требуют задания причинно-следственных связей и при представлении сложных систем обладают большой размерностью;

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

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

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

основанного на применении обобщенной модели и современных приближённых методов оптимизации.

Постановка Задачи.

В качестве объекта диагностирования рассматривается сложная техническая система. Система может быть представлена в виде совокупности элементов (функциональных блоков или параметров). Известны возможные неисправности элементов и соответствующие им априорные вероятности. Для диагностирования системы разработан набор тестов Т. Для каждого теста известны затраты на его исполнение.

Необходимо разработать оптимальную тестовую

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

Для решения поставленной задачи необходимо:

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

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

• Выполнить сравнение с известными алгоритмами.

• Применить полученные результаты на практике.

ГЛАВА 2. БАЗОВАЯ МОДЕЛЬ ОБЪЕКТА

ДИАГНОСТИРОВАНИЯ 2.1 Необходимые понятия и определения

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

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

Техническое состояние — совокупность свойств объекта подверженных изменению в процессе производства, эксплуатации и ремонта. Различают следующие возможные его состояния (Рис. 16):

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

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

- работоспособное - состояние, в котором объект способен выполнять все рабочие функции, предусмотренные технической документацией;

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

Исправно Неисправно

Работоспособно

Неработоспособно

Рис. 16. Состояния исследуемого объекта.

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

Техническое состояние объекта определяется по диагностическим признакам.

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

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

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

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

Состояние системы в целом рассматривается как функция, зависящая от состояния входящих в неё элементов.

Тестом называется оценка диагностических признаков при заранее определённых условиях с целью локализации дефекта или дефектов.

Каждый тест состоит из отдельных испытаний - элементарных тестов. Элементарным тестом {элементарной проверкой) называется акт однократной оценки диагностического признака. Оценка диагностического признака производится в заранее установленных местах объекта диагностирования, называемых контрольными точками. Элементарный тест может быть представлен в виде пары (Х,У,Т), где X -определённое воздействие на объект диагностирования, У - ожидаемая реакция на это воздействие, Z - контрольная точка на которой производится сравнение с У реакции объекта на воздействие X.

2.2 Математическое описание объекта диагностирования

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

- Структурная организация объекта диагностирования;

- Возможные неисправности и соответствующие им вероятности;

- Множество тестов Т, разработанное для идентификации состояния

объекта диагностирования;

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

Представим объект диагностирования в виде ориентированного графа G(B, U) с N вершинами [1]. Обозначим В - множество вершин графа, U -множество рёбер графа. Если можно выделить конструктивные или функциональные блоки объекта, вершины графа соответствуют структурным блокам объекта диагностирования, а рёбра графа - связям между блоками [63]. Если выделить блоки затруднительно - вершины графа соответствуют параметрам объекта диагностирования, а рёбра графа - причинно-следственным связям между параметрами.

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

Пронумеруем блоки объекта, диагностирования и разметим вершины графа G(B, U) соответствующими номерами {1,2, ... N}. Отметим на графе контрольные точки, соответствующие тестам t, е Т. Контрольные точки представляются в виде разметки рёбер графа G(B, U). Ребро Uy = (Ва, Bß) размечено контрольной точкой Zy, тогда и только тогда, когда при выполнении одного из тестов t, е Т осуществляется оценка диагностического параметра Yy, являющегося выходным для блока Ва и входным для блока Bß.

На Рис. 17 изображёна структурная схема системы электроснабжения переменного тока (а) и её граф-модель (б). Обозначения: ТД — тяговый двигатель, па, пг - частота вращения соответственно тягового двигателя и генератора; u, f, iB- напряжение, частота и ток возбуждения генератора; if-

-38-

управляющее воздействие на тяговый двигатель; РН - регулятор напряжения; СГС - синхронный генератор; РЧ - регулятор частоты; БЗУ -блок защиты и управления.

а)

п

Рис. 17. Граф-модель объекта диагностирования с разметкой вершин и

указанием контрольных точек.

Введём в рассмотрение модель элементарного теста.

По определению теста, каждый тест í¡ е Т может выть представлен в виде множества /, = {тк, тк = (Х,к, У,к, Да)}, где тк - элементарный тест.

На графе С(В, Ц) элементарный тест тк может быть изображён в виде контрольной пары вершин (Вз, Ву), где: Д> - вершина, соответствующая блоку, на вход которого подаётся входной сигнал Х,к', Ву - вершина, из которой выходит дуга и, соответствующая контрольной точке Х-,к. Элементарный тест хк контролирует состояние блока В/ тогда и только тогда, когда в графе (7(5, Ц) существует хотя бы один путь из вершины Вц в вершину Ву, проходящий через вершину Ву{Рис. 18а).

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

Элементарный тест тк может быть представлен моделью в виде УУ-мерного бинарного вектора ук (Рис. 186). Единица на /-ом месте в двоичном коде вектора ук означает, что /-ый блок объекта диагностирования контролируется данным элементарным тестом и является исправным, если результат теста положительный. При отрицательном результате

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

Нулевые значения компонент вектора v* соответствует блокам, неконтролируемым элементарным тестом тк. При положительном результате теста и неисправном состоянии всей исследуемой системы в целом формулируется вывод о том, что неисправен по меньшей мере один из N-k неконтролируемых блоков.

Очевидно, что максимальное число различных элементарных тестов Мтах равно количеству всевозможных последовательностей из 0 и 1 длины N, за исключением «неинформативных» последовательностей 0000... О и 111... 1 :

Mma=A"2-2=2N-2 (3), A j - число размещений с повторениями из 2 по N.

Рис. 18а. Представление элементарного теста тк —>(В,, В?), соответствующего контрольной точке Ъ* на графе объекта диагностирования. Выделены вершины, соответствующие контролируемым блокам.

м В2 вз В4 В5 В6 1 И В8

ш 1 1 1 0 0 0 ш 1°

Рис. 186. Модель элементарного теста тк —»(/?/, В7), соответствующего контрольной точке Zн на графе объекта диагностирования (Рис. 18а).

На основе модели элементарного теста может быть построена модель объекта в виде бинарной матрицы идентификации. Бинарная матрица идентификации - это прямоугольная Л=||я,у|| матрица столбцам, которой соответствуют блоки исследуемого объекта, а строкам элементарные тесты.

Если два или более столбца в матрице А совпадают, то неисправности в соответствующих им блоках являются неразличимыми (Рис. 19а). Описанная ситуация может возникнуть из-за ориентированных циклов в графе Ч). Данные циклы свидетельствуют о наличии обратных связей между блоками исследуемой системы. Для возможности обнаружения неисправности данных блоков, необходимо вводить контролируемые разрывы в контуры обратных связей (Рис. 196).

а) XI

В1 В2 ВЗ

11 1 1 1

а 1 1 1

а 1 1 1

14 1 1 1

V

Л

б)

В1 В2 вз

11 1 0 0

а 1 1 0

а 1 1 0

14 1 1 1

Рис. 19. Введение контролируемых разрывов в граф исследуемой системы для идентификации состояния блоков, входящих в конуры

обратных связей.

Если известны стоимости элементарных тестов, для построения оптимального алгоритма диагностирования может быть использована теория вопросников [43, 51, 52, 64, 65].

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

• Бинарная матрица идентификации обладает большой размерностью.

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

Разовьём рассмотренную модель для преодоления указанных недостатков.

Введём в рассмотрение модель теста. Так же, как и элементарный тест, представим его в виде целочисленного вектора. Так как тест = {г* } является суперпозицией входящих в него элементарных тестов г*, соответствующий ему вектор может быть получен по алгоритму, изображённому на Рис. 20.

(СЖ ВЗ, В4> ГвГ)

II

1 0 2

* | 1 1 0 | 1 |~2~1 с=> Г"В2^)Г~В4

Рис. 20. Получение вектора геста = {г/, т2} по векторам входящих в него элементарных гестов.

Модель теста. Каждый тест будем моделировать с помощью мерного вектора. Равенство нулю /-й компоненты такого вектора означает, что тест, соответствующий данному вектору, не контролирует состояние /-го логического блока диагностируемого объекта. Ненулевое значение /-й компоненты, напротив, свидетельствует о том, что тест, соответствующий данному вектору, контролирует состояние /-го логического блока диагностируемого объекта [66]. Наличие нескольких классов ненулевых компонент отражает тот факт, что выполнение соответствующего теста позволяет получить дополнительную информацию о расположении отказавшего блока (Рис. 21).

Представление тестя Возможные результаты теста Л» 2

состояние блока Вг

Рис. 21. Пример модели теста.

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

мхы —? элемент которой А равен 0, если тест ¡¡^Т не контролирует состояние ]-го блока диагностируемой системы, и отличен от нуля в противном случае (Табл. 1).

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

Таблица 1.

Пример матрицы идентификации.

в, в2 Вз в4 С(и)

1, 1 0 1 1 1

1 0 1 2 6

п 1 0 1 0 4

и 1 1 0 0 8

Р(В,) 0,1 0,3 0,5 0,1

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

Предложенная модель позволяет представить тестовую последовательность в виде нагруженного дерева поиска 5=5(г) , листьями которого являются номера неисправных блоков системы ¡е[1,1\Г\, а каждой внутренней вершине соответствует тест из некоторого подмножества т множества тестов {//... /л/} (Рис. 22).

В, В< С(0

2 0 0 0 1 1 3

1 1 0 0 1 0 4

■у Л, 2 0 1 0 1 3.5

0 0 0 1 1 1 6

2 2 1 1 0 0 5

Р(В) 0.3 0.2 0.1 0.1 0.2 0.1

Рис. 22. Матрица идентификации и пример графа тестовой

последовательности.

При известной стоимости выполнения каждого теста С(/, е Т) = С, и вероятности неисправности каждого блока Р(В,, /е[7,УV]) = Р, можно вычислить стоимость исполнения тестовой последовательности:

С(5)= X С(В:)-Р(В:) (4)

гегсл? 4

где 2 - множество блоков диагностируемой системы, состояния которых могут быть идентифицированы путём выполнения последовательности £ С(В:) - стоимость идентификации состояния блока г, определяемая как суммарная стоимость тестов, принадлежащих пути от корня дерева 5 до листа Вг (Рис.23).

С(В1 к#1)=з

С(В5)=С(В6}=С(М)+С(13)=3+3,5=6,5 С(В2)=С(11)+С(12)=3+4=7 1 С(ВЗ)=С(В4 )=С(И )+С^2)+С(14)=3+4+6=13

С=£ С(В1)Р(В1) = 2 0,1 13 + 0.2 7 + 0.2 6,5 + 0.1 6,5 +0.3 3 = 6,85

1=1

Рис. 23. Подсчёт стоимости но графу тестовой последовательности,

изображённому на Рис. 22.

В качестве глубины диагностирования системы достигаемой при исполнении тестовой последовательности Б рассматривается величина:

I Р(Вг)

/'ел?

где 2 - множество блоков диагностируемой системы, состояния которых могут быть идентифицированы путём выполнения последовательности $ (Рис. 24).

Глубина диагностирования Граф тестовой, последовательноепш Я тестовой последовательности 5*

Р(В1)+Р(В2)+Р(В5)+Р(В6])

I Р(В,)

6

/елг

I г (в.)

Рис. 24. Подсчёт глубины диагностирования но графу тестовой.

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

Сформулируем поставленную задачу, используя предложенную модель сложной системы и введённые критерии оптимальности.

2.3 Формальная постановка задачи.

Найти тестовую последовательность 5 = 5 (т <=Г) , позволяющую минимизировать целевую функцию С (Б), при условии <р(5) = </?0 .

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

2.4 Выводы.

ГЛАВА 3. ДИАГНОСТИЧЕСКАЯ МОДЕЛЬ ОБЪЕКТА

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

3.1 Построение модификации эволюционно-генетического

алгоритма.

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

Впервые использовать методы и модели механизма развития органического мира на Земле в качестве принципов комбинаторного перебора вариантов решения оптимизационных задач предложил в конце 60- х годов американский исследователь Джон Холланд, а сам термин «генетический алгоритм» введён в обиход Д. Балги (США) в своей диссертации в 1967 г.

В мире сейчас успешно развиваются три основные научные школы по генетическим алгоритмам. К ним относятся американская, европейская и российская школы. В американской школе отметим таких учёных как Д.Холланд, Д.Гольдберг, Д.Коза, Л.Чабес, Д.Уитли и др. В европейскую школу входят такие учёные, как Р.Клинг, П.Банерджи, Э.Фалькенауер и др. В российской отметим И.Букатову, Д.Батищева, И.Норенкова, В.М.Курейчика, В.В.Курейчика, Л.Гладкова и др.

Применение эволюционно-генетичееких алгоритмов рассматривается в работах [67,68,69,70,71,72]. Данная область исследования является перспективной и интерес к ней в мире с каждым годом возрастает.

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

Схема базового [71] (классического [70]) эволюционно-генетического алгоритма изображена на Рис. 25.

Формально эволюционно-генетический алгоритм можно определить следующим образом [73]:

ЭГА = (Р°, К, I, Ь, Б1, Я, / к) (6),

• Р° — {х\,х°2,... - начальная популяция;

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

• Х- размер популяции;

• К — биективное отображение множества допустимых решений во множество хромосом, определяющее способ кодирования;

• Ь - длина хромосомы;

57 - операторы селекции; Я - операторы рекомбинации;

/-/(х) - функция приспособленности (целевая функция для эволюционной оптимизации); к - критерий останова.

в К. —

Начало

т

т

Анализ условия задачи и Настройка генетического алгоритма

Выбор аюео ба кодирования решешш

Определение размера и способа пояучеюи начальной попутящш

Определение набора операх еров селекции н репродукции

Выбор крггтерия останова

«Нет» - Новое поколение

Рис. 25. Схема классического эволюционио-геиетического алгоритма.

Модификация эволюционно-генетического алгоритма [74]

заключается в выборе параметров (6), согласно условиям поставленной задачи.

3.1.2 Кодирование решений.

Рассмотрим в качестве генома популяции множество номеров тестов J = { 1,2,...,у,—М) . Допустимой хромосомой будем считать любую перестановку из элементов этого множества. При раскодировании хромосомы формирование тестовой последовательности и

вычисление функции приспособленности /(ху) = С {Б ) будем прекращать при достижении заданной глубины диагностирования (р{8у) — (р0.

Для того чтобы хромосома однозначно соответствовала тестовой последовательности, условимся начинать раскодирование с первых генов хромосом (Рис. 26).

Алгоритм раскодирования.

Тест, соответствующий первому гену , становится корнем дерева тестовой последовательности, при этом множество всех блоков исследуемой системы разбивается на классы В°2,... , В0,..., В°н} , и образуется Н ветвей дерева, по которым расположены подозрительные на неисправность блоки диагностируемого объекта. Просматриваются все ветви, тест,

соответствующий следующему гену х\ , добавляется к ветви у только в том случае, если он позволяет выполнить дальнейшее разбиение подмножества В° на классы [в\, Вх2,... , В^,... ,В[С}. Затем, операция повторяется для

тестов, соответствующих оставшимся генам ху2,...хум. Процесс прекращается при выполнении одного из условий:

1. у): 1^.1 = 1 - в каждом классе содержится ровно по одному

блоку;

2. (р{Зу) = (р0;

3. Рассмотрены все гены х] хромосомы .

Предложенный метод кодирования позволяет получать хромосомы одинаковой длины Ь=М и использовать не декодируемую часть хромосомы, как дополнительное средство выхода из локальных оптимумов [75].

Матрица идентификации

В1 В2 вз В4 В5 В6 В7 В8

11 0 0 0 1 1 1 0 0

«2 1 1 0 0 0 1 1 0

13 1 0 1 1 0 0 1 1

14 0 0 0 1 0 0 0 0

15 1 1 1 1 0 1 0 1

16 1 0 2 1 1 1 1 0

17 0 0 0 0 1 0 1 0

18 0 1 0 1 0 0 1 1

Используется для раскодирован ия

Граф тестовой последовательности 5

Для подсчёта Стоимости исполнения С (Б) преобразуется

Хромосома х.

6 7 8 4 1 2 3 5

V ч Перестановка нол 7 1еров тестов

а 18 14 11 и 13 15

Тестовая последовательность Л'

16 17 18 И 12

Рис. 26. Схема построения отображения К:{х''}—»{£.,] с помощью матрицы идентификации при заданной глубине диагностирования

<Ро=1 •

3.1.3 Выбор операторов рекомбинации.

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

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

Рис. 27. Схождение популяции к глобальному (слева) и к локальному

оптимуму.

Для гарантированного выхода из локального оптимума при бесконечном числе итераций необходимо чтобы выполнялось очевидное условие: вероятность появление оптимального решения после применения генетических операторов не равна 0. Для поставленной задачи условие выглядит так:

Pix-^S^frO (7)

пит

• х — хромосома, соответствующая оптимальной тестовой последовательности;

• Sonm — оптимальная тестовая стратегия;

• Р - вероятность появления х""'" после применения генетических операторов.

Данное условие является необходимым и достаточным, однако, положение глобального оптимума, заранее неизвестно, поэтому проверить данное условие при построении генетического алгоритма не представляется возможным. Предлагается использовать следующее условие: для выхода из гарантированного выхода из локального оптимума достаточно, чтобы после применения операторов R в популяции могла появиться любая допустимая хромосома[76].

\/1-.Р(хеХ<)оп)*0 (8)

• х1 — хромосома;

• Х- множество допустимых тестовых стратегий;

• Р - вероятность появления после применения генетических операторов.

Данное условие является достаточным, включает в себя условие (7) и может быть использовано для анализа пространства поиска набора выбранных операторов Я.

Сформулируем требования к набору операторов /?:

1. Выполнение любого оператора Я^Я на множестве допустимых хромосом приводит к получению допустимых хромосом-потомков;

2. Набор операторов позволяет выполнять поиск во всём пространстве допустимых решений;

3. Предусмотрены средства выхода из локальных оптимумов.

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

Рассмотрим следующие операторы:

• операторы кроссинговера:

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

• операторы мутации с различным числом и положением точек разрыва.

Упорядоченный оператор кроссинговера применяется на двух родительских хромосомах х1 и х2 и даёт две новые хромосомы хГ и х2'. Число точек разрыва может быть от 1 до (М- 1). Точка разрыва (на рисунках будет обозначаться « | ») берётся случайно. Далее происходит копирование левого сегмента х1 в хГ. Остальные позиции хГ берутся из х2 в упорядоченном виде слева направо, исключая элементы уже попавшие в хГ.

х1: А В В С | ?Е Н в Б

х2: О А В Е рС Р Б Н

хГ: АВОС^ОЕРН

х2': ОАВЕ|ОСНР

Получение х2' может выполняться различными способами наиболее распространённый метод копирования левого сегмента из х2, а далее анализ х1 методом, указанным выше. Тогда имеем х2': {САВЕ|БСНР}. При использовании нескольких точек разрыва алгоритм принципиально не меняется, только в хромосому хГ копируется нулевая часть Р1, а все части Р1, имеющие нечётный номер (например: х1= {А В | С Б Е | Б в Н}, часть №1={А В}, часть №3 = { Б в Н } ). Следует отметить, что при любом количестве и расположении точек кроссинговера при применении данного оператора к паре родительских хромосом, имеющих первый ген имеющих первый ген а0 и Ь0 соответственно, получается хромосома-потомок, принадлежащая множеству:

(а0**...*)и(60**...*) (9)

• (а0**...*)— множество допустимых хромосом, начинающихся с гена ао

• (Ь0**...*)— множество допустимых хромосом, начинающихся с гена Ь0

ч

X

ч

У/Л ' область, которой будет принадлежать хромосома-потомок

Область заданная первым» генами второго родителя — {ЬО ?... Т)

Область, заданная первыми генами первого родителя — (аО ? ... ?}

Рис.28. Область поиска упорядоченного оператора кроссинговера.

Область поиска данного оператора (Рис. 30) полностью зависит от состава популяции родительских хромосом. Если в популяции в результате её генерации или после применения операторов селекции отсутствуют хромосомы, начинающиеся с гена я, , то вся область (д,**...*) становится недоступной для дальнейшего генетического поиска, и возможно попадание в локальный оптимум. Во избежание подобной ситуации необходимо использовать данный оператор совместно с другими операторами Я, обеспечивающими возможность перехода в область поиска (д,■**.••*).

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

упорядоченный оператор кроссинговера с фрактальным расположением точек кроссинговера. Применяется на двух родительских хромосомах х1, х2 длиной М и даёт М новых хромосом при М — 2-к — 1, и М+2 новых

хромосом при М — 2-к, . Пример использования данного оператора изображён на Рис. 29.

111515 4 15 16 1

16 1514 3 12 111

Й И 12 3| 6 5 | 4

х4 1 6 | 5 4| 1 2|3

I 1 2 6 3 5 4 I

|6 5 1 4 2 з I

хз [ЩПИШЦ

и шшшпшш

«5 111^161515141 *6 I в | 5 | 1 1 4 | 2 |~3"1

и I 1 I 4 I 6 111 5~т х§ 16 13 1115 1 2Т?1

Рис. 29. Пример применения упорядоченного фрактального оператора.

Частично-соответствующий оператор кроссинговера применяется на двух родительских хромосомах х1 и х2 и даёт две новых хромосомы хГ и х2\ Число точек разрыва может быть от 1 до (М- 1). Точка разрыва берётся случайно, далее происходит копирование правого сегмента х1 в х2\ Остальные позиции хГ берутся из левого сегмента х2, с заменой повторяющихся генов на отсутствующие, х2у получается аналогичным способом:

х1\ А В С О х2: в А В Е

Е ¥ в Н СЭРЫ

хГ: САВО|ЕРОН

х1: А В С О х2: в А В Е

Е Р в Н СЭРЫ

хГ: АВСЕ|СОРН

При использовании нескольких точек разрыва алгоритм принципиально не меняется.

Область поиска данного оператора (**...*йг0)и(**...*/>0) } ао и Ь0 последние гены родительских хромосом х1 и х2 соответственно. По своим поисковым характеристикам данный оператор идентичен обычному упорядоченному оператору кроссинговера.

Циклический оператор кроссинговера применяется на двух родительских хромосомах х1 и х2, создаёт две новых хромосомы хГ и х2\ реализует рекомбинацию согласно циклам, которые существуют при установлении соответствия между генами первой и второй родительской хромосомы: