Введение к работе
Актуальность темы. Основным современным методом измерения и обеспечения качества технических и программных систем является тестирование. Выполнение каждого теста связано с затратой некоторого количества материальных ресурсов, поэтому при необходимости периодического тестирования возникает задача построения оптимальной тестовой последовательности, обеспечивающей минимум средних затрат на идентификацию состояний заданного числа отказов диагностируемой системы. Данная задача актуальна при контроле состояния технических систем и регрессионном тестировании программ.
Данной проблеме посвящено большое количество работ отечественных и зарубежных авторов: Г.Ф. Верзаков, П.П. Пархоменко, В.И. Сагунов, А.Ю. Аржененко, Д.В. Сперанский, В.В. Сапожников, М.А. Владимиров, J. Wegener, J. Ribero, A. Arcury, J. Shiozaky, и др.
На основании обзора литературных источников можно сделать вывод, что рассматриваемая задача является комбинаторной и может быть решена с помощью известных методов дискретной оптимизации. Однако, при построении оптимальных тестовых последовательностей для диагностирования сложных систем данные методы неэффективны, так как требуют трудоёмких вычислений. Когда использование точных методов оптимизации становится невозможным, практическую значимость приобретает приближённый подход.
Целью диссертационной работы является разработка модификации эволюционно-генетического алгоритма и соответствующих моделей и методов эффективного диагностирования сложных систем.
Задачи работы.
Достижение поставленной цели предполагает решение следующих задач:
анализ существующих моделей и алгоритмов диагностирования и
научно-техническое обоснование темы исследования;
выбор базовой модели, описывающей сложный объект диагностирования как систему;
разработка диагностической модели сложной системы, включающей алгоритмы построения оптимальных тестовых последовательностей;
оценка вычислительной сложности разработанных алгоритмов;
программная реализация разработанных алгоритмов;
разработка методики реализации полученных результатов.
Методы исследования, применяемые в работе, основаны на теории графов, теории вероятностей, динамическом программировании, имитации отжига и эволюционно-генетическом моделировании. Для анализа и применения полученных результатов выполнено компьютерное моделирование разработанных алгоритмов на языке программирования C++.
Научная новизна работы состоит в следующем:
-
Разработана модификация эволюционно-генетического алгоритма, отличающаяся специальными генетическими операторами, методами построения хромосом и функции приспособленности, адаптированная для решения задачи диагностирования сложных систем.
-
На основе предложенной модификации разработан новый метод оценки оптимального решения, позволяющий решить задачу диагностирования с наименьшим использованием вычислительных ресурсов, по сравнению с другими известными методами.
-
Разработан алгоритм построения тестовой последовательности, для которого экспериментально установлено, что он имеет меньшую вычислительную сложность, по сравнению с известными. Практическая ценность и рекомендации по использованию
результатов. Разработанная в диссертационной работе модификация эволюционно-генетического алгоритма позволила снизить затраты на контроль функционирования и определение состояния технической системы в процессе её производства и эксплуатации. Результаты работы могут быть использованы в промышленном производстве для снижения затрат на
обеспечение высокого уровня надёжности производимых технических систем.
Реализация результатов работы.
Разработанные алгоритмы применяются в Институте проблем машиностроения Российской академии наук, что подтверждается актом о внедрении. Они также используются в учебном процессе при подготовке магистрантов направления «Информатика и вычислительная техника» по программе «Диагностические и информационно-поисковые системы» в Нижегородском государственном техническом университете им. Р.Е. Алексеева.
Разработанный программный комплекс зарегистрирован в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам РФ. Свидетельство об официальной регистрации программ для ЭВМ № 009613297.
Результаты работы использованы в госбюджетной НИР (Отчет по НИР «Диагностика технических и программных систем с использованием современных информационных технологий». Номер государственной регистрации 01.2009.00405 от 28.01.09 -Н. Новгород: НГТУ), выполненной в рамках НИОКР «Диагностические и информационно-поисковые системы» (Номер регистрации 01201252337, интернет-номер ИНН 12195013, руководитель работы Ломакина Л.С.).
Обоснованность и достоверность результатов диссертационной работы обеспечена использованием результатов последних исследований в области имитационного и эволюционно-генетического моделирования, корректным применением современного математического аппарата и подтверждены вычислительными экспериментами на реальном примере.
На защиту выносятся: 1. Диагностическая модель сложной системы, включающая алгоритмы
построения оптимальных тестовых последовательностей.
2. Модификация эволюционно-генетического алгоритма для
эффективного диагностирования сложных систем.
3. Метод диагностирования сложной технической системы,
основанный на разработанной модификации.
Апробация работы. Основные положения диссертации и результаты диссертационной работы представлялись и докладывались на следующих научных конференциях:
Международных научно-технических конференциях «Информационные системы и технологии (ИСТ-2009, ИСТ-2010, ИСТ-2011, ИСТ-2013)» (Нижний Новгород);
XV Международной открытой научной конференции «Современные проблемы информатизации» (Воронеж, 2010);
IV Всероссийской научно-технической конференции «Прикладная информатика и математическое моделирование» (Москва, 2010);
X Международной молодежной научно-технической конференции «Будущее технической науки» (Нижний Новгород, 2011);
XVI Нижегородской Сессии молодых учёных (Нижний Новгород, 2011);
XVII Международной научно-практической конференции «Системный анализ в проектировании и управлении» (Санкт-Петербург, 2013). Публикации. По теме диссертации опубликовано 15 работ, в том числе
3 статьи в ведущих рецензируемых научных журналах и изданиях, рекомендованных ВАК, свидетельство о государственной регистрации программы для ЭВМ № 009613297.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, библиографического списка и приложений. Общий объём работы 129 страниц текста, содержащего 64 рисунка и 5 таблиц. Список литературы содержит 90 наименований.
