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

• Автор: Губернаторов, Владимир Павлович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Нижний Новгород
• Количество страниц: 133 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ГЛАВА 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 Выводы

ВВЕДЕНИЕ
Современные сложные технические системы требуют обеспечения высокого уровня надёжности функционирования. Это требование становится особенно актуальным, когда системой решается задача, сопряженная с опасностью потери человеческих жизней или значительных материальных ресурсов.
Основным современным методом измерения и обеспечения качества технических и программных систем является тестирование. Выполнение каждого теста связано с затратой некоторого количества материальных ресурсов, поэтому при необходимости периодического тестирования, возникает задача построения оптимальной тестовой последовательности, обеспечивающей минимум затрат на идентификацию состояний заданного числа отказов диагностируемой системы. Данная задача актуальна при контроле состояния технических систем и регрессионном тестировании программ.
Данной проблеме посвящено большое количество работ отечественных и зарубежных авторов: Г.Ф. Верзаков, П.П. Пархоменко, В.И. Сагунов, А.Ю. Аржененко, Д.В. Сперанский, В.В. Сапожников, М.А. Владимиров, J. Wegener, J. Ribero, A. Arcury, J. Shiozaky,n др.
На основании обзора литературных источников можно сделать вывод, что рассматриваемая задача является комбинаторной и может быть решена с помощью известных методов дискретной оптимизации. Однако, при построении оптимальных тестовых последовательностей для диагностирования сложных систем данные методы неэффективны, так как требуют трудоёмких вычислений. Когда использование точных методов оптимизации становится невозможным, практическую значимость приобретает приближённый подход.
Целью диссертационной работы является разработка модификации эволюционно-генетического алгоритма и соответствующих моделей и методов эффективного диагностирования сложных систем.
Задачи работы.
Достижение цели работы предполагает решение следующих задач:
• анализ существующих моделей и алгоритмов диагностирования и научно-техническое обоснование темы исследования;
• выбор базовой модели, описывающей сложный объект диагностирования как систему;
• разработка диагностической модели сложной системы, включающей алгоритмы построения оптимальных тестовых последовательностей;
• оценка вычислительной сложности разработанных алгоритмов;
• программная реализация разработанных алгоритмов;
• разработка методики реализации полученных результатов.
Методы исследования, применяемые в работе, основаны на теории графов, теории вероятностей, динамическом программировании, имитации отжига и эволюционно-генетическом моделировании. Для анализа и применения полученных результатов выполнено компьютерное моделирование разработанных алгоритмов на языке программирования С++. Научная новизна работы состоит в следующем:
1. Разработана модификация эволюционно-генетического алгоритма, отличающаяся специальными генетическими операторами, методами построения хромосом и функции приспособленности, адаптированная для решения задачи диагностирования сложных систем.
2. На основе предложенной модификации разработан новый метод оценки оптимального решения, позволяющий решить задачу
основанного на применении обобщенной модели и современных приближённых методов оптимизации.
Постановка Задачи.
В качестве объекта диагностирования рассматривается сложная техническая система. Система может быть представлена в виде совокупности элементов (функциональных блоков или параметров). Известны возможные неисправности элементов и соответствующие им априорные вероятности. Для диагностирования системы разработан набор тестов Т. Для каждого теста известны затраты на его исполнение.
Необходимо разработать оптимальную тестовую
последовательность, обеспечивающую минимум затрат на идентификацию состояния системы.
Для решения поставленной задачи необходимо:
• Построить базовую модель системы представляющей информацию о её структуре, возможных неисправностях, разработанных тестах и стоимости их исполнения.
• Разработать диагностическую модель системы, включающую алгоритмы построения оптимальных тестовых
последовательностей.
• Выполнить сравнение с известными алгоритмами.
• Применить полученные результаты на практике.