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

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

ГУБЕРНАТОРОВ ВЛАДИМИР ПАВЛОВИЧ

ДИАГНОСТИРОВАНИЕ СЛОЖНЫХ СИСТЕМ НА ОСНОВЕ ЭВОЛЮЦИОННО-ГЕНЕТИЧЕСКОГО МОДЕЛИРОВАНИЯ

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

АВТОРЕФЕРАТ

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

31 ОКТ 2013

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

2013 г. 005536803

005536803

Работа выполнена на кафедре «Вычислительные системы и технологии» федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Нижегородский государственный технический университет им. Р.Е.Алексеева».

Научный доктор технических наук, профессор,

руководитель: Ломакина Любовь Сергеевна

Официальные Андреев Вячеслав Викторович

оппоненты: доктор технических наук, профессор, кафедра «-Ядерные реакторы и энергетические установки» НГТУ им.Р.Е. Алексеева, заведующий кафедрой

Банкрутенко Владимир Викторович,

кандидат технических наук, доцент, отдел информационных технологий ОАО «ОКБМ им.И.И. Африкантова», начальник отдела

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

организация: технических систем, г. Нижний Новгород («НИЦ КД»).

Защита диссертации состоится «21» ноября 2013 года в 13-00 часов в ауд. 1258 на заседании диссертационного совета Д212.165.05 при Нижегородском государственном техническом университете им. P.E. Алексеева по адресу: 603950, г. Нижний Новгород, ул. Минина, 24.

С диссертацией можно ознакомиться в библиотеке Нижегородского государственного технического университета им. P.E. Алексеева.

Автореферат разослан «21» октября 2013 года.

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

A.C. Суркова

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

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

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

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

Достижение поставленной цели предполагает решение следующих

задач:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

построения оптимальных тестовых последовательностей.

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

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

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

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

. Международных научно-технических конференциях

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

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

. X Международной молодежной научно-технической конференции

«Будущее технической науки» (Нижний Новгород, 2011); . XVI Нижегородской Сессии молодых учёных (Нижний Новгород, 2011);

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

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

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

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

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

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

Пусть Т - множество тестов, разработанных для проверки диашостмруемой системы. Каждый тест позволяет установить неисправность одного или группы блоков данной системы (Рис. 1).

1 иширлпл VI I № О ^

Блоки диагностируемой системы

* * т *—

В, а

1 0 2

Неисправность в неконтролируемом блохе В,

Компоненты, соответствующие контролируем им блокам

Неисправность в контролируемом блоке В

Неисправность в одном ю контролируемых блоков - в блоке В/ или в блоке В

а) б)

Ряс. I. Представление теста (а) и результатов его выполнения (б). Положим, что |Г| = М, а N - количество блоков. Тогда в качестве базовой модели диагностируемой системы будем использовать матрицу

идентификации Ли.м = (о,), элемент которой ащ е А равен 0, если тсст /, е Т не контролирует состояние у-го блока диагностируемой системы, и отличен от нуля в противном случае.

Выбранная модель позволяет представить тестовую последовательность в виде нагруженного дерева поиска 5 = л(г). листьями которого являются номера неисправных блоков системы 1€[1,ЛГ], а каждой внутренней вершине соответствует тест из некоторого подмножества г множества тестов Г = {г,...^}. При известной стоимости выполнения каждого теста С(1, € 7") = С, и вероятности неисправности каждого блока />(Д,,/е[1,Л']) = Р, можно вычислить стоимость исполнения тестовой последовательности:

С(5)= £С(Вг) Р(В,) (1).

иге*

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

с<во=сао-з

С (В5)=С(Вб) = СП 1)+СП3)^6.5 С(В2)=С(!])+СИ2)=7 С(Вз)=С(Вб)*С(11)+С(12)+С«4)=13

Рис. 2. Вычисление стоимости тестовой последовательности.

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

1л*,)

1«/У

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

Для нахождения оптимальной тестовой последовательности ставится задача:

Найти тестовую последовательность 5 = х(г с Г), позволяющую минимизировать целевую функцию С(Б), при условии <|К5) = ■

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

Эволюционно-генстическое моделирование

Формально эволюционно-генстический алгоритм (ЭГА) можно определить следующим образом:

ЭГЛ = (Р0,К,Л,,Ь,Я,И,/,к) (3)

• Р° = {лс,°,дг|....дг^} - начальная популяция;

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

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

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

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

• 5/ - операторы селекции;

• Л - операторы рекомбинации;

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

• к- критерий останова.

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

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

функции приспособленности /(дсг) = С(5г) будем прекращать при достижении заданной глубины диагностирования <К$Г) = ф^. Для того, чтобы хромосома однозначно соответствовала тестовой последовательности, условимся начинать раскодирование с первых генов хромосом (Рис. 3).

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

0 ш 0 ■1 и и о о

1 [ 0 _0| 0 1 1 0

1 0 1 1 0 0 1 1

ТГ 0 ~г 1 0 0 0 0

1 1 1 1 0 1 0 1

1 0 2 1 1 1 1 0

0 0 ТГ ТГ ! 0 1 6

ТГ 1 ТГ Т1 6 6 1 1

Хромосома

|6|7|8|4 |1 I 2|3|5 |

Перестановка номеров тестов

Рис. 3. Схема построения отображения К : {дс^} —» {5Г } по матрице идентификации при таланяой глубине диагностирования

Предложенный метод кодирования позволяет получать хромосомы одинаковой длины £»А/ и использовать не декодируемую часть хромосомы, как дополнительное средство выхода из локальных оптимумов.

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

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

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

* ЖАДНЫЙ ПОИСК

• • случайный поиск

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

область, иламиая первым ___м , __ геном первого ролитея»

\ \ _ <*""•*>

область поиска упорадочеиного область поиска жадного I I область, млаииа* первым оператора кроссинговера оператора гросскмговсра 1_| второго родите

I

Рис. 4. Область »олюпиоиио-генетического поиска при совместном применении жалкого н упорядоченного операторов кроссииговера.

Совместное применение выбранных операторов кроссинговера обеспечивает достаточное условие выхода из локальных оптнмумов: Уу: р(хг: л, —е С/)) * 0, где: и - множество тестовых последовательностей, удовлетворяющих условиям задачи; р(хг) -вероятность появления ху после применения генетических операторов Л (Рис. 4).

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

Так как проблема выхода из локальных оптнмумов решена на этапе выбора операторов репродукции, в качестве оператора селекции 5У предлагается использовать простую элитную селекцию на основе сравнения значений функции приспособленности /(х) = С(л).

Начальную популяцию Р° предлагается формировать путем применения фрактального оператора кроссинговера к двум случайно сгенерированным решениям.

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

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

Предложенную модификацию построим по схеме простого эволюционно-генетического алгоритма.

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

Динамическое программирование

Пусть {0, а, Р--у} - множество значений элементов ;-й строки матрицы идентификации А, тогда тест е Т разбивает множество блоков системы В на подмножества В0,Ва,ВР...Вг. Совокупность подмножеств В', соответствующих всевозможным сочетаниям тестов из Т обозначим К. Обозначим Г^сГ - множество тестов, позволяющих выполнить дальнейшее разбиение подмножества кл еК. Пару (кл\ТаЬ) будем называть ситуацией а, а Ь=\каИ\ - порядком ситуации. Каждой ситуации первого порядка соответствует ТаХ = 0, оптимальная тестовая последовательность Яа1=0, Сор,(.Уо1) = 0. Начиная с ситуаций второго порядка, на каждом шаге выбирается тест е Т^ и вычисляется С^Д^.Т^) = Сор,(5^).

Для ситуации второго порядка

С„р,(ка2,Та2) = Сор1^а2) = тт(С(Г, еТа)). При рассмотрении ситуации р

произвольного порядка хе[2,М] - (к^Т^), известны Свр,(8л) для всех

ситуаций порядка И<х, а Сор,(5рх) вычисляется с помощью уравнения Беллмана:

• 4 — тест из множества Трх\

• кр - подмножества, на которые /,• разбивает множество крх,

• Р1 - условная вероятность наличия неисправности в блоках Ву е к^.

Решением поставленной задачи будет тестовая последовательность 51, полученная при рассмотрении ситуации (к0М;Т0М). Данная ситуация является единственной ситуацией порядка М и для неё выполняется условие ком ~ В > Том = Т.

Имитация отжига

Общая схема алгоритма имитации отжига.

1. Выбирается температура отжига в виде дискретного отрезка [Д„,...Д„], устанавливается текущая температура Д' = Д(, / = и.

2. Выбирается начальное решение ха, оно становится текущим х = хп.

3. С помощью преобразования в получается решение-кандидат х" = в(х').

4. Вероятность, с которой решение х" = в(х') станет текущим, равна Р(х',х"), где Р - распределение Гиббса:

Дх) - значение целевой функции, соответствующее решению х.

5. Понижаем температуру /' = ;'-1, Д' = Д,..

6. Процесс прекращается при Д' = Д0, в противном случае переходим к

Сор,(крх,) = Сор1 (5Д1) = шт(С(/; + -С^к^Т^)) (5),

шагу 3.

Решение представляется в виде упорядоченной последовательности номеров тестов J = ^l,2,■.■,j,■■■■Щ из множества Т и преобразуется в тестовую последовательность с помощью оператора К: {хг} -> (Рис. 3).

Целевая функция решения х вычисляется, как стоимость

Преобразование О заключается в случайном выборе пары индексов (/;/), i<j последовательности {х'г} = х' и получении решения х" путём

конкатенации {х\,...х)}, {х'0,...} и {х'н,...х'м}.

При высоких температурах Д,-,г>и/2 решение х" = в(х') может быть выбрано текущим при /(х")> f(x'), поэтому возможен пропуск fonm(x) и попадание в локальный оптимум при уменьшении температуры. Чтобы избежать описанной ситуации, предлагается на каждой итерации алгоритма сохранять:

Решением поставленной задачи будет тестовая последовательность, соответствующая:

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

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

Динамическое программирование требует рассмотрения ситуаций всех (к^Т^), порождённых к^еК. Множество К соответствует булеану

множества Т и имеет мощность | К \= 2|Г| = 2м, следовательно,

соответствующей тестовой последовательности S: f (х) — С(5), х ——» S.

вычислительная сложность метола, основанного на динамическом программировании 0(2М).

При использовании оценки сложностей жадного и упорядоченного операторов кроссинговера и схемы простого генетического алгоритма, было установлено, что максимальная сложность предложенной модификации 1 волюционно-гснстичсского алгоритма (ЭГА) — кубическая относительно числа тестов множества Т и линейная относительно числа блоков диагностируемой системы. Оценка минимальной сложности не представляет интереса, так как для любого эволюциоино-генстического алгоритма эта сложность одинакова и равна O(l). Среднюю вычислительную сложность можно определить только экспериментально.

Алгоритм имитации отжига является итерационным, его вычислительная сложность пропорциональна сложности выполнения оператора в — О(М).

Рассмотрим экспериментальные оценки вычислительной сложности разработанных алгоритмов, выполненные с помощью программной реализации на языке С++ (Рис. 5). t,Cj

40

I

Г

Модификация ЭГА Динамическое программирование Имитация отжига

Рис. 5. Зависимость времени работы алгоритмов от числа тестов М.

Экспериментальная оценка сложности метода, основанного на

динамическом программировании, совпадает с аналитической — 0(2м). Для

получения экспериментальной зависимости времени работы эволюционно-

15

генетического алгоритма и метода имитации отжига от М воспользуемся приближёнными выражениями, полученными с помощью метода наименьших квадратов (МНК) (Рис. 6). ^ С 6

Рис. 7. Оценка зависимости времени работы алгоритмов от числа блоков N.

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

16

О

5 20 35 М

Рис. 6. Оценка мвисимости времени работы от М для модификации тволюционно-геиетяческого алгоритма и метола имитации.

Полученные результаты позволяют сделать вывод, что средняя вычислительная сложность предложенной модификации эволюционно-генстического алгоритма — О(М'), а сложность алгоритма имитации отжига - О(М). Зависимости времени работы предложенных алгоритмов от количества блоков диагностируемой системы N представлены на Рис. 7. 1,с

3 2 1

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

(Л/=5, 6.....50; N = 10). Результаты данного эксперимента (Рис. 8) позволяют

сделать вывод, что модификация эволюционно-генетнческого алгоритма эффективнее метода имитация отжига.

ОД

8

4

0

5 20 35 X/

Рис. 8. Значения целевой функции оптимальных тестовых последовательностей при исполыовании ЭГА и имитации отжига.

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

I

сигналов функциональных блоков. Стоимость тестов соответствует

Модификация ЭГА ........1 Д Имитация отжига |

. ; и! » • 1

/ А А

¿ут * и ч

= 5 ' V "■»••»^ »

временным затратам на отключение и подключение измерительной аппаратуры.

По функциональной схеме электропривода (Рис. 9) выполняется построение графа с указанием контрольных точек (Рис. 10) и соответствующей матрицы идентификации (Рис. 11).

Рис. 9. СИФУ автоматизированною электропривода. ТР — блок трансформаторов;

Ф — фильтры; У — операционные усилители; ВУ — входной усилитель; И — источники питания; УИ — усилители импульсов; Гр — гальваническая развязка; ДА, ДК — датчики транзисторов анодной и катодной групп; РУ — ячейка раздельного управления ТП.

В, Вг В} в* в. Вь Вг В, 5« В ю В„ Вп В,) Вы со,)

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0.4

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0.2

1 1 1 0 0 0 0 0 0 0 0 0 0 0 0.1

и 0 1 0 0 0 0 0 0 0 0 0 0 0,3

и 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0,3

1а 1 ■ 1 0 1 1 1 0 0 0 0 0 0 0 0 0.3

и 1 1 1 1 1 1 I 0 0 1 1 1 1 1 4

1л 1 1 1 1 1 1 1 1 0 1 1 1 1 1 2

1 1 1 1 1 1 1 1 1 1 1 1 I 1 2

(/» 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0,8

III 1 1 0 0 0 0 0 0 0 0 1 1 1 I 0.8

1и 1 1 0 0 0 0 0 0 0 0 0 1 0 0 1.2

1 1 0 0 0 0 0 0 0 0 0 0 1 0 1.2

1 1 0 0 0 0 0 0 0 0 0 0 0 1 0,3

Р(В) 0,04 0,06 0,04 0,01 0.03 0,03 0,26 0,07 0.02 0.04 0.04 0.09 0,09 XI8

Рис. II. Матрица идентификации СИФУ автоматизирован»™ электропривода.

С помощью предложенных в работе алгоритмов были получены

тестовые последовательности, представленные на Рис. 12.

Рис. 12. Оптимальные тестовые последовательности, полученные с немощью алгоритмов: (я) динамическое про! раммированне, (б) эволюциоино-гсштнческос моделирование, (в) имитация отжига.

Результаты вычислительных экспериментов показали, что предложенная модификация эволюционно-генстического алгоритма может эффективно применяться для решения задачи построения опгималыюй тестовой последовательности размерности (ЛМ4, Л/>14), так как обладает

меньшей вычислительной сложностью, чем метод динамического

программирования и выигрывает у имитации отжига по значению С(з).

В заключении изложены основные научные и практические результаты

диссертационной работы.

Приложение содержит

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

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

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

Основные результаты работы

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

2. Обоснован выбор матрицы идентификации в качестве базовой модели сложной системы.

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

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

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

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

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

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

Список опубликованных работ по теме диссертации Работы, опубликованные в ведущих рецензируемых научных журналах и изданиях, рекомендованных ВАК

[1] Губернаторов, В.П., Модификация эволюционно-генетического алгоритма для построения оптимальных тестовых последовательностей. [Текст] / В.П. Губернаторов // Вестник Нижегородского университета им. Н.И.Лобачевского, №3(1), 2012. - С. 179-183.

[2] Губернаторов, В.П., Модификация эволюционно-генетического алгоритма для эффективного диагностирования сложных систем [Текст] / JI.C. Ломакина, В.П. Губернаторов // Системы управления и информационные технологии, №3(53), Научн.-техн. ж. — Москва-Воронеж ИПУ-ВГТУ, 2013. - С. 59-64.

[3] Губернаторов, В.П., Метод диагностирования сложных технических систем на основе эволюционно-генетического моделирования [Текст] / Л.С. Ломакина, В.П. Губернаторов // Научно-технический вестник Поволжья. №4, - Казань, 2013. - С. 215-219.

Статьи в журналах и трудах научных конференций

[4] Губернаторов, В.П. Диагностика технических и программных систем с использованием современных информационных технологий [Текст] (научный руководитель Л.С. Ломакина) / А.Н. Вигура, A.C. Базин,

21

В.П. Губернаторов и др. // Отчет по НИР № государственной регистрации 01.2009.00405 от 28.01.09 -Н. Новгород: НГТУ, 2009. - 127 с.

[5] Губернаторов, В.П. Автоматизация поиска неисправностей в сложной системе на основе использования генетических алгоритмов [Текст] / В.П. Губернаторов // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2009)», 17 апреля 2009 г. - Н. Новгород: НГТУ, 2009. - С.262.

[6] Губернаторов, В.П. Автоматизация оптимального поиска неисправностей в сложной системе на основе использования эволюционно-генетического моделирования [Текст] / В.П. Губернаторов // Журнал «Труды НГТУ. Серия «Системы обработки информации и управления»» - Т. 74. -Вып. 15. - Н.Новгород: НГТУ, 2009. - С. 27-34.

[7] Губернаторов, В.П. Построение оптимальных вопросников эволюционно-генетическим моделированием / Л.С. Ломакина, В.П. Губернаторов // Свидетельство об официальной регистрации программ для ЭВМ № 009613297. Зарегистрировано в реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ от 25 июня 2009 г.

[8] Губернаторов, В.П. Особенности использования генетических алгоритмов при решении задач диагностики сложных систем [Текст] / В.П. Губернаторов // Материалы 15-й Международной открытой научной конференции «Современные проблемы информатизации». — Воронеж: ВГТУ, 2010.-С. 319-320.

[9] Губернаторов, В.П. Диагностирование сложных систем на основе эволюционно-генетического моделирования [Текст] / В.П. Губернаторов // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2010)», 23 апреля 2010 г. -Н. Новгород: НГТУ, 2010. - С. 296.

[10] Губернаторов, В.П. Оптимальный поиск неисправностей в сложных системах эволюционно-генетическим моделированием [Текст] /

В.П. Губернаторов // Межвузовский сборник научных трудов IV всероссийской научно-технической конференции «Прикладная информатика и математическое моделирование», 19-20 мая 2010 г. - Москва: МГУП, 2010.-С. 125.

[11] Губернаторов, В.П. Применение эволюционно-генетического моделирования для синтеза алгоритмов оптимального диагностирования [Текст] / В.П. Губернаторов // Сборник трудов конференции XVI Нижегородская Сессия молодых учёных. 14-17 февраля 2011 г. -Н. Новгород, 2011. - С. 176-179.

[12] Губернаторов, В.П. Применение эволюционной оптимизации для построения алгоритмов оптимального диагностирования [Текст] / В.П. Губернаторов И Материалы XII Международной научно-технической конференции «Будущее технической науки», 24 мая 2011 г. - Н. Новгород: НГТУ, 2011. - С.46.

[13] Губернаторов, В.П. Применение эволюционной оптимизации для построения алгоритмов оптимального диагностирования [Текст] / Губернаторов В.П. // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2011)», 22 апреля 2011 г. - Н.Новгород: НГТУ, 2011. - С. 318.

[14] Губернаторов, В.П. Анализ методов построения оптимальных тестовых последовательностей [Текст] / В.П. Губернаторов // Материалы Международной научно-технической конференции «Информационные системы и технологии (ИСТ-2013)», 19 апреля 2013 г. - Н.Новгород: НГТУ, 2013.-С. 271.

[15] Губернаторов, В.П. Алгоритмы оптимального диагностирования сложных систем [Текст] / В.П. Губернаторов // Материалы Международной научно-практической конференции «Системный анализ в проектировании и управлении», 1-3 июля 2013 г. - Санкт-Петербург: СПбГПУ, 2013. - С. 145147.

Подписано в печать 10.10.2013. Формат 60 х 84 l/t6. Бумага офсетная. _Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 728._

Нижегородский государственный технический университет им. P.E. Алексеева. Типография НГТУ. 603950, ГСП-41, г. Нижний Новгород, ул. Минина, 24.

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

им. Р.Е. Алексеева

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

04201453399

ГУБЕРНАТОРОВ Владимир Павлович

ДИАГНОСТИРОВАНИЕ СЛОЖНЫХ СИСТЕМ НА ОСНОВЕ ЭВОЛЮЦИОННО-ГЕНЕТИЧЕСКОГО МОДЕЛИРОВАНИЯ

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

Научный руководитель: д.т.н., профессор Л.С. Ломакина

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

СОДЕРЖАНИЕ

ВВЕДЕНИЕ..............................................................................................................4

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

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

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

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

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

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

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

2.4 Выводы.........................................................................................................46

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

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

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

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

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

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

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

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

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

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

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

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

3.5 Выводы.........................................................................................................89

-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] в качестве модели объектов диагностирования используются системы дифференциальных уравнений либо передаточных функций.

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