close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
На правах рукописи
ГВОЗДЮК ИЛЬЯ ВЯЧЕСЛАВОВИЧ
УПРАВЛЕНИЕ ПОВЕДЕНИЕМ ДИСКРЕТНЫХ СИСТЕМ
С ПАМЯТЬЮ ПРИ ФУНКЦИОНАЛЬНОМ ВОССТАНОВЛЕНИИ
НА ОСНОВЕ ПЕРИОДИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
05.13.01 – Системный анализ, управление и обработка информации
(в технической отрасли)
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Саратов – 2018
Работа выполнена в Федеральном государственном бюджетном
образовательном учреждении высшего образования «Саратовский
государственный технический университет имени Гагарина Ю.А.»
Научный руководитель:
член-корреспондент РАО, лауреат премии
Президента РФ, Заслуженный деятель науки РФ,
доктор технических наук, профессор,
Сытник Александр Александрович
Официальные
оппоненты:
Гусятников Виктор Николаевич,
доктор физико-математических наук, профессор,
Саратовский социально-экономический институт
(филиал) Федерального государственного
бюджетного образовательного учреждения высшего
образования «Российский экономический
университет имени Г.В. Плеханова», заведующий
кафедрой прикладной математики и информатики
Богомолов Алексей Сергеевич,
кандидат физико-математических наук, доцент,
Федеральное государственное бюджетное
учреждение науки Институт проблем точной
механики и управления Российской академии наук,
г. Саратов, заведующий лабораторией системных
проблем управления и автоматизации
в машиностроении
Ведущая организация:
Федеральное государственное автономное
образовательное учреждение высшего образования
«Самарский национальный исследовательский
университет имени академика С.П. Королева»
Защита диссертации состоится «27» ноября 2018 г. в 15.00 на заседании
диссертационного совета Д 212.242.04 при ФГБОУ ВО «Саратовский
государственный технический университет имени Гагарина Ю.А.» по адресу:
410054, Саратов, ул. Политехническая, 77, корпус 1, ауд. 414.
С диссертацией можно ознакомиться в научно-технической библиотеке
ФГБОУ ВО «Саратовский государственный технический университет имени
Гагарина Ю.А.» и на сайте www.sstu.ru
Автореферат разослан «_____» октября 2018 г.
Ученый секретарь
диссертационного совета
2
Торгашова Ольга Юрьевна
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы исследования. Эффективность управления
современными техническими системами в значительной мере зависит от их
способности амортизировать возникающие в процессе работы нарушения.
Быстрое и достоверное обнаружение неисправностей, устранение их
последствий в максимально короткие сроки и с наименьшими затратами
оптимизируют работоспособность технических объектов.
Для современного состояния общей теории восстановления характерно
использование для амортизации неисправностей двух основных типов
избыточностей технических систем: структурной (аппаратурной) и
временной. В первом случае для устранения последствий возникших:
нарушений в состав (структуру) технического объекта вводятся
дополнительные резервные модули. При выходе из строя основной части
схемы на существующий структурный резерв возлагается задача реализации
заданного исправного поведения. Во втором – имеющийся в данный
конкретный момент или искусственно создаваемый резерв времени
(временная избыточность) используется либо для организации «повторного
счета», либо для повторного запуска, логической операции, измененной в
результате неисправности и т. д.
Выход из строя (или отсутствие в силу сложностных, ценностных и
прочих ограничений) аппаратурного резервирования порождает вопрос:
«Можно ли использовать свойства текущего (в условиях существования
неисправностей) закона функционирования технической системы для
формирования на её выходах требуемой совокупности правильных
исправных реакций?» Ответ на него предполагает изучение имевшейся в
данный момент времени функциональной избыточности технической
системы, а также возможных вариантов её целенаправленного создания на
этапе проектирования. Восстановление поведения технических объектов,
осуществляемое на указанных принципах, впервые было введено
А.А. Сытником и названо функциональным. Затем функциональное
восстановление дискретных систем с памятью достаточно подробно
исследовалось
его
учениками
Т.Э. Шульгой,
Н.С. Вагариной,
О.В. Мещеряковой, Н.И. Посохиной, К.П. Вахлаевой, С.Ю. Дронкиным,
А.Н. Кунявской и др.
Функциональное восстановление дополняет перечисленные выше
традиционные концепции восстановления. Решение задач функционального
восстановления позволяет обоснованно ответить на вопрос о возможности
дальнейшего управления и эксплуатации технических систем после
возникновения и обнаружения неисправностей в условиях, когда
невозможно (нецелесообразно) немедленно провести ремонт дефекта или
отсутствует (вышло из строя) аппаратурное резервирование.
Модель конечного детерминированного автомата является, несмотря на
ряд определенных недостатков, наиболее используемой при формальном
описании поведения такого класса технических объектов как дискретные
3
системы с памятью. Конечные автоматы и все возможные их приложения
подробно рассматривались большим количеством авторов. К их числу
следует отнести работы Э. Мура, А. Гилла, В.М. Глушкова А.М. Богомолова,
П.П. Пархоменко, В.А. Твердохлебова, М.Ф. Каравая, Э.В. Евреинова,
И.В. Прангишвили, В.И. Варшавского, Я.М. Барздиня, В.Б. Кудрявцева и др.
А.А. Сытником было показано, что проблема функционального
восстановления для произвольного класса технических объектов
алгоритмически неразрешима, то есть не существует единого универсального
метода
построения
восстанавливающих
последовательностей
для
произвольной дискретной системы с памятью.
Поэтому одной из актуальных задач является рассмотрение и выделение
разрешимых классов и типов технических объектов или, в терминологии
конечных автоматов как формальных моделей технических систем,
определение конкретных принципов и видов поведений, для которых
возможно
разработать
метод
синтеза
восстанавливающих
последовательностей.
Конечные детерминированные автоматы составляют один из важнейших
классов математических моделей динамических систем с конечным
множеством состояний. Практическое и теоретическое значение автоматных
моделей в решении задач проектирования и технического диагностирования,
познания процессов формирования и передачи сигналов в биологических
системах и т.д. стало причиной интенсивных исследований в области теории
автоматов.
Разнообразие возникших задач привело к выделению классов автоматов
(автоматы типов Мили и Мура, автоматы Медведева), а также к разработке
различных математических способов их задания (табличное задание, графы
автоматов, автоматные матрицы, логические уравнения и т.д.).
Потребность в использовании автоматных моделей для реальных
объектов с большим числом состояний привела к развитию теории
структурных автоматов, в которой абстрактная форма автомата заменялась
структурной формой, то есть композицией преобразователей сигналов и
элементов памяти.
Структурная форма задания конечных автоматов принципиально
повысила эффективность приложений теории автоматов и представила новые
возможности для теоретических исследований. В частности, в диссертации
декомпозиция автомата на комбинационную часть и память используется с
целью применения развитого математического аппарата алгебры логики.
В качестве средства разделения множества состояний автомата на
подмножества
используется
приложение
периодических
последовательностей входных сигналов. Как показано А.М. Богомоловым и
В.А. Твердохлебовым, в этом случае возникает циклическое изменение
состояний. Такой подход позволяет состояния, не вошедшие в циклы,
исключить из анализа.
Выбор периодов в периодических последовательностях входных
сигналов оказался связанным с рядом не решенных в теории вопросов,
4
которые и стали предметом исследования. Кроме этого, потребовалось
разработать критерии эффективного изменения состояний в циклах, методы
построения и реализации соответствующих экспериментов с автоматами,
формальный аппарат постановки задач и представления результатов.
В литературе существуют отдельные результаты без существенного
теоретического обобщения. В диссертации эти результаты формально
обобщены и предложены принципы функционирования автоматов в режиме
циклического изменения состояний.
В диссертационной работе рассматриваются два подхода к выделению
такого рода классов поведений дискретных систем с памятью, точнее, два
взаимоследующих и взаимодополняющих подхода. Вначале исследуется
структурная форма представления конечно-автоматных моделей и
выделяются их типы в зависимости от классов булевских функций,
описывающих их переходы-выходы. Затем используется результат
В.А. Твердохлебова о виде графов функции переходов-выходов с точки
зрения периодических последовательностей. Последние в рамках теории
экспериментов с автоматами подробно изучались А.Н. Кунявской.
Принципиальное отличие предлагаемого подхода заключается в применении
идеи В.А. Твердохлебова о «периодичности» к анализу и синтезу
восстанавливающих последовательностей для обеспечения повышения
управляемости и отказоустойчивости дискретных систем с памятью.
Разработка и реализация данного подхода и составляет круг исследований,
представленных в настоящей диссертации, об актуальности которых говорят
сделанные выше замечания.
Целью диссертационной работы является решение важной научнотехнической задачи, заключающейся в разработке формальных моделей и
методов управления, обеспечивающих функциональное восстановление
поведения сложных технических систем дискретного типа с памятью.
Для достижения поставленной цели необходимо решение следующих
задач:
1) Определить условия, позволяющие выделить класс технических
объектов с памятью, для которых существует решение задачи
функционального восстановления поведения в случае возникновения
неисправности.
2) Разработать метод функционального восстановления поведения
технических объектов с памятью выделенного класса.
3) Определить критерии (достаточные и/или необходимые условия),
которым должны удовлетворять технические объекты, чтобы существовало
решение задачи функционального восстановления их поведения с помощью
периодической восстанавливающей последовательности входных сигналов.
Объектом исследования в данной работе являются технические
системы дискретного типа.
Предметом исследования в настоящей работе являются методы и
модели функционального восстановления поведения технических объектов с
памятью.
5
Теоретическую и
методологическую
основу
исследования
составляют аналитические методы теории графов, теории множеств,
системного анализа и теории автоматов, методы технической диагностики.
При проведении моделирования и вычислительных экспериментов на
ЭВМ использовались современные аппаратные и программные средства.
Программный комплекс и алгоритмы реализованы на языке Делфи.
Обоснованность и достоверность научных положений, выводов и
рекомендаций подтверждается использованием утверждений, строго
доказанных формальными методами. Справедливость выводов относительно
адекватности используемых методов и моделей подтверждается
многочисленными примерами и приведенной программной реализацией.
Научная новизна результатов диссертационного исследования
заключается в следующем:
1) Предложен, обоснован и исследован метод выделения разрешимых
фрагментов функционального восстановления поведения технических
объектов дискретного типа с памятью на основе анализа их структурного
представления в виде замечательных классов булевых функций. Такой
подход, по сравнению с существующими принципиально расширяет
возможности получения аналитических решений задачи функционального
восстановления технических объектов.
2) Предложен и разработан подход к восстановлению поведения
дискретных систем с памятью, основанный на использовании
восстанавливающих
периодических
последовательностей
текущего
неисправного закона функционирования. Такой подход по сравнению с
существующими позволяет решать задачу восстановления правильного
функционирования технических объектов в условиях, когда традиционные
методы восстановления (аппаратурное резервирование, ремонт и т. д.) либо
недееспособны, либо в принципе не могут быть реализованы в данный
момент времени.
3) Впервые
определены
критерии
(достаточные
условия),
устанавливающие существование решения задачи функционального
восстановления для заданной пары: «исправное поведение, класс
потенциальных текущих поведений (класс неисправностей)» на основе
восстанавливающих периодических последовательностей.
4) Показана возможность применения автоматного представления
нейронных сетей при решении задачи функционального восстановления
поведения технических объектов дискретного типа для класса
маршрутизирующих сетевых структур.
5) Предложен новый метод к построению логических элементов
маршрутизирующих сетевых устройств, основанный на использовании
автоматного представления нейронных сетей, который позволяет
существенно уменьшить необходимый объем памяти для хранения
структуры сети и время, необходимое на выработку решения о дальнейшей
пересылке пакета (более 60% при решении возможности функционального
восстановления поведения заданной системы).
6
Положения и результаты, выносимые на защиту:
1) Разработанный подход выделения класса технических объектов с
памятью на основе исследования их структурного представления и
принадлежности классам булевских функций, позволяющий в условиях
существования
неисправности
решить
задачу
функционального
восстановления.
2) Разработанный
и
обоснованный
метод
построения
восстанавливающих периодических, позволяющий в условиях существования
неисправностей сформировать на выходах заданную совокупность
правильных исправных реакций.
3) Полученный и обоснованный ряд критериев, позволяющих
установить возможность функционального восстановления конкретного
исправного поведения относительно заданного класса неисправностей с
использованием восстанавливающих периодических последовательностей.
4) Для
информационно-коммуникационных
систем
показанная
возможность
функционального
восстановления
при
автоматном
представлении их поведения нейронными сетями.
Научная и практическая значимость диссертационного исследования
заключается в разработке методов функционального восстановления
поведения для некоторых классов технических систем дискретного типа с
памятью. Практическая значимость работы состоит в использовании
предложенных методов повышения отказоустойчивости технических
объектов дискретного типа с памятью, в частности для информационнокоммуникационных систем и различных сетевых структур.
Личный вклад автора. Все основные результаты, выводы и положения,
выносимые на защиту, получены автором лично. В совместных работах
автору принадлежит ведущая роль в разработке общей концепции работы, ее
структуры, методологии обеспечения функционального восстановления
технических систем дискретного типа, создании математических моделей,
методов и реализующих их программных комплексов.
Реализация и внедрение результатов исследования. Проведенные в
работе исследования выполнены в соответствии с планом госбюджетных
научно-исследовательских работ, проводимых на кафедре «Информационнокоммуникационные системы и программная инженерия» СГТУ имени
Гагарина Ю.А. в рамках научного направления кафедры «Разработка
теоретических основ, методологий синтеза и анализа вычислительных,
информационных и человеко-машинных систем» и в рамках базовой части
государственного задания Минобрнауки России «Разработка методов
дискретного
анализа
семантики слабоструктурированных
систем»
(№ госрегистрации 01201253990).
Результаты работы также использовались в учебном процессе при
чтении лекций по курсу «Сети и телекоммуникации» студентам направления
09.03.01 «Информатика и вычислительная техника» и направления 09.03.04
«Программная инженерия».
7
Апробация результатов исследования. Диссертационная работа
многократно обсуждалась на научных семинарах кафедры «Информационнокоммуникационных системы и программная инженерия» Саратовского
государственного технического университета имени Гагарина Ю.А. в 20142018 годах, на международных научных конференциях: ХХ юбилейной
Всероссийской научной конференции «Инжиниринг предприятий и
управление
знаниями»
(ИП&УЗ-2017);
Международной
научнопрактической
конференции
«Информационно-коммуникационные
технологии в образовании, производстве и научных исследованиях» ICIT
(Саратов 2017, 2018); Международной научно-технической конференции
«Перспективные информационные технологии (ПИТ)» (Самара, 2017, 2018).
Соответствие
темы
диссертации
требованиям
паспорта
специальностей научных работников
Диссертационная работа соответствует п. 2, 10, 11, 13 паспорта
специальности 05.13.01 «Системный анализ, управление и обработка
информации» и заключается в следующем:
1) Формализация и постановка задач системного анализа, оптимизации,
управления, принятия решений и обработки информации.
2) Методы и алгоритмы интеллектуальной поддержки при принятии
управленческих решений в технических системах.
3) Методы и алгоритмы прогнозирования и оценки эффективности,
качества и надежности сложных систем.
4) Методы получения, анализа и обработки экспертной информации.
Публикации. По теме диссертационного исследования опубликовано
12 печатных работ, из которых 4 в ведущих рецензируемых изданиях,
рекомендуемых ВАК РФ.
Структура и объем работы. Диссертация состоит из введения, четырех
глав, заключения, списка использованной литературы, включающего 84
наименования. Работа изложена на 152 страницах, включая 2 приложения,
содержит 32 рисунка.
ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении показана актуальность исследуемой проблемы,
рассмотрена степень ее проработанности, определены предмет, объект, цель
и задачи и методы исследования, а также определены новизна, теоретическая
и практическая значимость полученных результатов.
В
первой
главе
диссертации
рассматриваются
вопросы
функционального восстановления поведения на основе конечно-автоматных
моделей. В первом параграфе этой главы обсуждаются проблемы
алгоритмической разрешимости (существования универсального алгоритма
построения восстанавливающих последовательностей для произвольного
технического объекта). К сожалению, на основании результата А.А. Сытника
ответ на этот вопрос отрицательный, то есть рассматриваемая проблема
является алгоритмически неразрешимой. Иными словами, создание методов
функционального восстановления поведения дискретных систем с памятью
8
может развиваться только по пути выделения типов технических объектов и
(или) их законов функционирования. Предлагается один из возможных
подходов к выделению разрешимых фрагментов классов технических систем,
основанный на идее В.А. Твердохлебова о строении графа, представляющего
поведение конечного автомата.
Определение. А = (S, X, Y, , ) - конечный детерминированный
автомат, где S, X и Y – соответственно множества состояний, входных и
выходных сигналов, а  и  функции переходов  : S  X  S и
выходов  : S  X  Y.
На основании теоремы В.А. Твердохлебова:
Для любого конечного автомата А и входного слова р:
1) граф GA(p) состоит из конечного числа связных изолированных
подграфов;
2) каждый связный изолированный подграф содержит один и только
один элементарный цикл с точностью до циклического сдвига
последовательности вершин;
3) каждая вершина может быть корнем дерева, причем из вершин
дерева существуют пути только к корню.
В качестве выходной реакции автомата можно рассматривать последний
сигнал в цепочке выходных сигналов под воздействием входной
периодической последовательности. Восстановление поведения конечного
детерминированного автомата именно с помощью периодических
восстанавливающих последовательностей накладывает определенные
ограничения на класс объектов, для которых этот прием дает решение
поставленной задачи.
Допустим,
периодическая
последовательность
является
восстанавливающей для неисправного сигнала х. Если состояния 1, 2, 3
автомата А2, соответствующего поведению в «неисправном» режиме
функционирования,
под
воздействием
этой
периодической
последовательности переходят в одно общее для них состояние s, то и для
автомата А1, соответствующего заданному поведению, эти состояния
должны переходить под воздействием сигнала x в одно и то же состояние s.
Граф зацикливания по входному слову р «неисправного» автомата должен
содержать такое же количество циклов, что и граф «исправного» автомата
под воздействием входного сигнала х с теми же множествами вершин
циклов. В этом случае всевозможные произведения таких слов не будут
выводить нас за пределы цикла и будут давать на выходе одну из
перестановок множества вершин. Одно из таких слов может дать решение
задачи восстановления в смысле восстановления для состояний,
принадлежащих циклу. Получается, что нужно построить два алгоритма.
Первый – это способ нахождения всех периодических последовательностей,
переводящих автомат в цикл с нужным набором вершин. Если при этом
последовательность вершин совпадает с циклом для восстанавливаемого
сигнала х, то периодическая последовательность будет восстанавливающей.
9
Если нет, то нужно применять алгоритм нахождения восстанавливающей
последовательности
как
произведения
различных
периодических
последовательностей.
Функционирование автомата на основе его зацикливания
Пусть А = ( S, X, Y, ,  ) конечный детерминированный автомат. Во
множестве вариантов его функционирования выделим такие, которые
определяются следующими ограничениями:
1) К автомату А прикладываются только периодические входные
последовательности вида pm , где pX * и mN.
2) При эксперименте с автоматом А наблюдаются только некоторые
выходные сигналы, выдаваемые автоматами при изменении его состояний в
цикле.
В этом случае можно сократить количество анализируемой
информации и исключить из рассмотрения реакции автоматов (реализующих
заданное и текущее поведение), выдаваемые под воздействием входного
сигнала x и восстанавливающей периодической последовательности
соответственно для состояний, не принадлежащих циклам. Если важным
моментом является именно обстоятельство получения конкретного
выходного сигнала y, который выдается автоматом под воздействием
входного сигнала для нескольких состояний автомата, в том числе для
состояния цикла, то перевод «неисправного» автомата в режим
зацикливания, сокращающий варианты переходов автомата в различные
состояния, является оправданным, особенно в случае большого числа
состояний автомата. Для исключения из анализа некоторых состояний
автомата
возможно
также
приложение
ряда
периодических
последовательностей с различными периодами.
Кроме описанного выше подхода к применению периодических
последовательностей в качестве восстанавливающих на некотором
подмножестве множества состояний автомата, возможно также прикладывать
периодические последовательности для того, чтобы перевести автомат в то
подмножество состояний, на котором известными методами можно
построить
восстанавливающие
(не
обязательно
периодические)
последовательности.
Для анализа поведения системы в режиме зацикливания необходимо
более детально рассмотреть функционирование автомата под воздействием
периодических последовательностей и построить математическую модель
процесса зацикливания. Эти вопросы рассматриваются в третьем параграфе.
Основная идея сокращения числа состояний автомата, требующих
анализа при восстановлении, состоит в исключении из анализа всех вершин
деревьев, кроме корней деревьев. Корни деревьев образуют циклы или петли.
Следовательно, в предлагаемом методе восстановления поведения
анализируется наблюдаемое поведение автомата, представленное циклами и
переходами из одного цикла в другой. Процесс построения такого автомата
 представлен ниже.
10
Построение по заданному конечному детерминированному
автомату
А = ( S, X, Y, ,  ) автомата (модели зацикливания) , у которого:
1) Входными сигналами являются слова piX*, используемые как периоды
периодических входных последовательностей.
2) Выходными сигналами являются слова qjY*, построенные выделением
некоторых выходных сигналов, выдаваемых автоматом при изменении его
состояний в цикле.
3) Множеством состояний автомата полагаются только те состояния, которые
образуют циклы.
4) Задачи для автомата А решаются как задачи для автомата
~ ~
 = ( [S], {pi , iI} , {qj, jJ} ,  ,  )
~ ~
где [S] – множество состояний, входящих в циклы, а  и  – новые функции
переходов и выходов.
Для автомата А используются два способа расширения функции выходов .
1) Функция  расширяется до функции вида : SX * Y* по правилу:
(sS ) (xX) (pX* )  (s, xp) =  (s, x)  ( (s, x), p).
2) С целью уменьшения объема наблюдаемых выходных сигналов автомата
используется расширение функции  до функции ` вида
` :SX * Y, при котором наблюдается только последний выходной сигнал:
( sS ) ( xX ) ( pX* ) ` (s, xp) =  ( (s, p), x ), где функция 
расширена до функции вида  : S  X *  Y по правилу:
(  s S ) (  x X ) (  p  X * )  (s, x p) =  ( (s, x), p )
Основным результатом является Теорема 3.
Теорема 3. Пусть автомат А1= (S,
X, Y, , ) соответствует
«исправному» типу функционирования, А2=(S, X, Y, , ) описывает
поведение системы после возникновения неисправности. 1 – модель
зацикливания автомата А1 , 2 – модель зацикливания автомата А2. Тогда
любое решение p { pi , 1 ir} задачи восстановления для автоматов 1
mi
и 2 является решением задачи восстановления для автоматов А1 и А2.
Очевидно, что если не существует периодических восстанавливающих
последовательностей для множества «неисправных» входных сигналов, то
автомат  не будет демонстрировать поведение, аналогичное «исправному»
режиму функционирования, вне зависимости от множества входных
сигналов автомата . Однако отсутствие решения задачи восстановления в
виде периодических восстанавливающих последовательностей не означает,
что задача восстановления неразрешима. Таким образом, метод
периодических последовательностей подразумевает нахождение частных
классов задач, в которых он может быть успешно применен.
11
Построение
графа,
соответствующего
периодическим
последовательностям, при решении задачи восстановления поведения Gp
удобно производить, если задать автомат А с помощью автоматной матрицы
переходов МA или матрицы переходов-выходов UA. Эти вопросы
рассмотрены в четвертом параграфе первой главы. Основным результатом
является разработанный Матричный метод построения циклов графа Gp
при восстановлении поведения конечного детерминированного автомата.
Матричный метод построения циклов графа Gp при восстановлении
поведения конечного детерминированного автомата
Исходные данные:
1) конечный детерминированный автомат A = (S, X, Y, , ),
соответствующий «неисправному» поведению автомата;
2) входное слово pX* , где p =К.
Шаг 1. Строится матрица переходов-выходов ( U A )К.
Шаг 2. К этой матрице применяется операторLр. (производящий
сокращение элементов матрицы uKij по множеству входных сигналов).
Шаг 3. Из матрицы Lр( U A )К исключаются столбцы, все элементы
которого – пустые множества, и строки с таким же, как исключенные
столбцы, номером (при пересчете столбцов слева направо и строк сверху
вниз) до тех пор, пока не будет получена матрица, не имеющая столбцов из
пустых элементов. Номера оставшихся после этой процедуры столбцов
определяют состояния, принадлежащие циклам графа зацикливания ьGp.
 m
Шаг 4. Строится ( L pU A ) , где m  m1  m2 , m1 определяет наибольшую
длину пути в цикл, m2 – наибольшую длину цикла.
 m
Шаг 5. Строится матрица F ( L pU A ) , определяющая последний
выходной сигнал в цепочке выходных сигналов автомата под воздействием
p m при любом начальном состоянии.
Во второй главе диссертации исследуются свойства модели поведения
дискретных систем на основе их структурного представления.
Классификация конечных детерминированных автоматов может быть
построена на связи состояний и выходных сигналов (автоматы типа Мили,
автоматы типа Мура, на роли входных сигналов (автономные и
неавтономные автоматы), на свойства памяти (автоматы с конечной
глубиной памяти) и т. п. Свойства автоматов этих классов используются при
восстановлении поведения автоматов.
Комбинационная часть автомата представляет произвольную
композицию конечных автоматов без памяти, называемых обычно
логическими элементами. Всякая комбинационная схема (часть автомата)
обладает некоторым множеством внешних входных узлов, некоторым
множеством выходных узлов и некоторым множеством внутренних узлов.
Таким образом, при исследовании типов поведений дискретных систем
12
можно использовать классическую классификацию булевских функций
(замечательные классы).
Сочетание двух классификаций автоматов на основе учета числа
состояний, входных и выходных сигналов, с одной стороны, и разделения
автоматов на классы по принадлежности функций переходов и выходов
определенному классу функций алгебры логики – с другой может давать
интересные частные случаи.
Лемма 1. Если возникновение неисправности не выводит автомат из
класса самодвойственных, сохраняющих ноль, связных автоматов вида А=
(E2, E2, φ), то полное восстановление поведения невозможно.
Условие принадлежности автоматов в «исправном» и «неисправном»
режимах функционирования одному классу определяет, с одной стороны,
метод
восстановления
(конкретный
вид
восстанавливающих
последовательностей), с другой – может означать, что восстановление
поведения невозможно, т. е. «неисправный» автомат не является
универсальным по отношению к заданному.
Решение задачи восстановления связано с нахождением для каждого
«неисправного» входного сигнала х «исправной» выходной реакции y. При
этом полезно проанализировать свойства функций переходов и выходов при
фиксировании этого входного сигнала.
Функции переходов  и выходов  конечного детерминированного
автомата А = (S, X, Y. , ) определены на переменных xXиsS, имеющих
разную интерпретацию. Фиксирование s переводит функцию  (s, x) в
функцию s (x). Аналогично, фиксируя входной сигнал x, мы получаем
описание изменений состояний при ограничении на входы автомата. В
общем случае свойства функции, которыми она обладает до фиксирования
переменных, не сохраняются при фиксировании некоторых (и всех)
переменных.
В настоящее время исследование проблемы восстановления поведения
дискретных систем с памятью направлено на поиск классов конечных
детерминированных автоматов, для которых данная задача разрешима, и
можно построить универсальный алгоритм решения.
В третьей главе диссертации рассматривается проблема поиска
критериев выделения «разрешимых» классов технических объектов.
Приложение к автомату восстанавливающей периодической
последовательности
позволяет,
во-первых,
сократить
количество
анализируемой информации, во-вторых, перевести автомат в известное
подмножество множества состояний автомата, для которого возможно найти
восстанавливающие последовательности. Это удобно делать в тех случаях,
когда нас интересуют не все, а некоторые составляющие закона
функционирования автомата, либо когда восстановление поведения на всем
множестве состояний невозможно.
Подавая на вход автомата любое слово р необходимое количество раз,
мы переводим автомат в некоторое подмножество S´ множества состояний S
13
автомата. Задача состоит в поиске тех периодических последовательностей,
которые переводят автомат в такое множество состояний, на котором
работают уже известные алгоритмы решения. Ранее было рассмотрено, какой
должна быть минимальная длина периодической последовательности, чтобы
из любого состояния автомата попасть в состояние цикла.
В рамках такого подхода к решению задачи восстановления поведения
возможны
следующие
варианты
применения
периодических
последовательностей. С одной стороны, можно для каждого «неисправного»
входного сигнала искать «свою» периодическую последовательность,
которая может быть как восстанавливающей сама по себе, так и переводить
автомат из любого состояния в некоторое подмножество состояний, для
которого
затем
необходимо
определять
восстанавливающую
последовательность (также, возможно, периодическую, а возможно и
непериодическую).
С другой стороны, в зависимости от поставленных целей можно
попытаться найти одну и ту же периодическую последовательность для всех
входных сигналов, с тем чтобы вне зависимости от входного сигнала автомат
демонстрировал заданное поведение на некотором фиксированном
подмножестве состояний. И в том, и в другом случае очевидным является то,
что из всего множества входных слов р из входного алфавита X*, можно
сразу исключить те слова, граф зацикливания которых содержит небольшое
число вершин, например содержит единственный цикл периода два или
петлю. Как одно из условий восстановления поведения методом
зацикливания можно ввести минимальное количество состояний, для
которых автомат выдает заданные выходные реакции, т.е. минимальное
число вершин графа зацикливания по входной периодической
последовательности с периодом р. В этом случае определяющим оказывается
выбор периодов, то есть слов в алфавите X, которые используются в
периодических последовательностях.
В диссертации предлагается выбирать слова – периоды для
восстанавливающих последовательностей входных сигналов на основе
использования свойств комбинационных частей в структуре автоматов,
которые задаются функциями алгебры логики.
Проведенный на этой основе в предыдущих главах анализ типов
поведений технических систем позволил получить ряд критериев решения
задачи функционального восстановления (Теоремы 3.3.3.-3.3.5.). Их
обоснование связано с преодолением серьезных математических трудностей.
Определение. Множество { ~x1 }  { ~x 2 }  . . .  { ~x n }  E1z  E 2z  . . .  E nz
2
будем называть цилиндрическим по последним n1 компонентам и набору
( ~x1 , ~x 2 , . . . , ~x n ) первых n2 компонент.
2
14
1
Теорема 3.3.3. Пусть Aj ,j = 1, 2 , – конечные детерминированные
автоматы вида A j  (( E2 ) n , ( E2 ) n , ( E2 ) n ,  ,  j ) , для которых выполняются
условия:
1
3
2
1) в непустом множестве конституент единицы

{ h1ih2i }
1  i  n3
существует цилиндрическое по последним n1 компонентам подмножество W;
2) (1, 2, . . . ,  n2  n2 )W;
3) функциональному восстановлению с приложением периодической
восстанавливающей последовательности входных сигналов с периодом
p = (1, 2, . . . ,  n2 ) соответствует возможное зацикливание по 
циклам L1, L2 , . . ., L;
4) при изменении состояний автомата A1 в цикле L ,  = 1, 2, … , 
на выходах автомата выдается точно a наборов выходных сигналов,
отличных от нулевого набора (0, 0, . . . , 0);
5) Для любых , l, 1  , l выполняется неравенство
a
| L |  al
 l
.
|L  |
|L l |
Тогда функциональным восстановлением с зацикливанием с периодом
p восстанавливается поведение автомата в паре автоматов (A1 , A2).
Теорема 3.3.4. Aj ,j = 1, 2 , – конечные детерминированные автоматы
вида A j  (( E 2 ) n , ( E 2 ) n , ( E 2 ),  ,  j ) . Пусть слово р переводит автомат A2
1
2
в множество состояний S 1  S . В непустом множестве  f1  f 2  существует
цилиндрическое по первым n2 компонент подмножество
В = {(1i, 2i, . . . ,  ( n1  n2 )i )}, 1<i<r, такое, что множество состояний,
соответствующих этому подмножеству, совпадает с S1. Тогда периодическая
последовательность с периодом р переводит автомат в режимы
функционирования, совпадающие с заданными.
Теорема 3.3.5. Пусть Aj , j = 1, 2 , конечные детерминированные
автоматы вида A j  (( E2 ) n , ( E2 ) n , ( E2 ) n ,  ,  j ) , в непустом множестве
конституент
{ h1jh2j }, где 1 in3, существует цилиндрическое по последним n1,
компонент подмножество
Ai  (( E2 ) n , ( E2 ) n , ( E2 ) n ,  ,  i ) W и (1, 2, . . . ,  n1  n2 ) W.
Если
функциональному
восстановлению
с
приложением
восстанавливающей периодической последовательности входных сигналов с
периодом p= (1, 2, . . . ,  n2 ) соответствует зацикливание по единственному
циклу нечетной длины d2 и наибольшей длиной d1 пути в цикл, то
восстановлением <p, d1, d2> восстанавливается поведение автомата в паре
автоматов (A1, A2).
1
1
2
2
3
3
15
Метод функционального восстановления поведения конечного
детерминированного автомата с зацикливанием по однобуквенному
периоду
Вход:
детерминированные
A j  (( E2 ) , ( E2 ) , ( E2 ) ,  ,  j ) , Aj , j = 1, 2 .
n1
Конечные
n2
автоматы
A1и
A2
вида
n3
Средства функционального восстановления: простой безусловный
эксперимент (по Э. Муру и А. Гиллу) с приложением периодической
последовательности с периодом – однобуквенным словом и наблюдением
выходных сигналов при изменениях состояний в циклах.
Шаг 1. Функциям выходов 1 и 2 сопоставляются наборы функций
алгебры логики (h11, h12, . . . , h1n3 ) и (h21, h22, . . . , h 2 n3 ) и строится множество
конституент единицы

1  i  n3
{ h1ih2i }. Если это множество пусто, то метод
неприменим.
Шаг 2. В (непустом) множестве

1  i  n3
{ h1ih2i } выделяется
подмножество W, цилиндрическое по последним n1 координатам. Если
такого подмножества нет, то метод неприменим.
Шаг 3. В рассматриваемом цилиндрическом подмножестве х
выбирается элемент (1, 2, . . . ,  n1  n2 ) и для периода p = (1, 2, . . . ,  n2 )
определяются циклы L1, L2 , . . . , L и величины a1, a2 , . . . , a для автомата A1.
Шаг 4. Для определенных на шаге 3 величин |L1 |, |L2 | , . . . , |L| и a1,
a2 , . . . , a проверяется условие
a
| L |  al
 l
|L  |
|L l |
для всех  и l, , 1  , l. Если для выбранного периода p это условие
выполняется, с приложением последовательности pd1 r (d1 – наибольшая
длина путей в циклы, а r – наименьшее общее кратное чисел |L1 |, |L2 | , . . . ,
|L|) и наблюдением r последних выходных сигналов автомат
восстанавливается в паре автоматов (A1 , A2).
Если для p условие не выполняется, то производится перебор
цилиндрических подмножеств и их элементов в соответствии с шагами 2 и 3.
Если перебор по всем вариантам, определяемым шагами 2 и 3, не дает
выполнения условия, указанного в шаге 4, то метод неприменим.
Основу для построения методов функционального восстановления
поведения дискретных систем с памятью составляют модели конечных
детерминированных автоматов.
В четвертой главе приводится методологический пример
исследования реальных технических систем, описывающих информационнокоммуникационные сети, и использованием представления поведения в виде
представления модели поведения в виде нейронной сети.
16
Постановка
задачи
управления
моделированием
отказоустойчивого поведения (функционально-восстанавливаемого)
информационно-коммуникационной системы
Необходимо создать логический элемент коммутирующего устройства,
способный на основе некоторой базы данных принимать решение
относительно направления пришедшего на вход пакета на один из портов для
достижения цели наискорейшей (наилучшей) доставки пакета адресату. На
вход элемента будет подаваться закодированный каким-либо образом номер
(сетевой адрес) получателя пакета, на выходе же должен сформироваться
закодированный каким-либо образом номер порта, на который следует
переслать пакет для его доставки. Кроме того, при подключении устройств к
сети логический элемент будет информироваться специальным сообщением
о том, за каким портом относительно него следует искать новое устройство.
Соответственно эта информация будет использоваться для внесения
изменений в базу данных элемента.
Под успехом нейронной сети будем понимать правильность
(отказоустойчивость или возможность функционального восстановления) ее
в выборе маршрута для заданного пакета. Неудачей, соответственно, будем
называть случай, когда логический элемент ошибся в выборе маршрута и
данный пакет не будет доставлен адресату. Под отказом нейронной сети
будем понимать ситуацию, когда на каждый из ее выходов поступил сигнал 0
(это означает, что логический элемент коммуникационного устройства не
обладает информацией относительно того, за каким из портов располагается
устройство с заданным адресом, и проинформирует об этом отправителя
пакета сообщением специального формата).
Результаты моделирования информационно-коммуникационной сети
из 500 компьютеров с коммуникационным устройством с 32 портами (рис. 1).
120
100
Процент
80
Успехи
60
Неудачи
Отказы
40
20
0
1
123 245 367 489 611 733 855 977 1099 1221 1343 1465 1587 1709 1831 1953
Итерация
Рисунок 1. Линейный выход, модель 500/32 (обучение 1 нейрона)
17
Приведенные примеры показывают, как осуществляется реальный
переход от автоматной модели поведения дискретной системы к изучению
её в виде моделирующей нейронной сети при решении задачи
функционального восстановления.
В заключении содержатся основные выводы по результатам
исследования, подводятся итоги и приводятся рекомендации по применению
полученных результатов.
ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ
В
результате
проведенного
диссертационного
исследования
предложены и исследованы формальные модели и методы управления,
создания и эксплуатации техническим систем с памятью с точки зрения
задачи функционального восстановления их поведения.
В результате проведенных исследований получены следующие
теоретические и практические результаты.
1) Разработан подход выделения класса технических объектов с
памятью на основе исследования их структурного представления и
принадлежности классам булевских функций, позволяющий в условиях
существования
неисправности
решить
задачу
функционального
восстановления.
2) Разработан и обоснован метод построения восстанавливающих
периодических
последовательностей,
позволяющий
в
условиях
существования неисправностей сформировать на выходах заданную
совокупность правильных исправных реакций.
3) Получен и обоснован ряд критериев, позволяющих установить
возможность функционального восстановления конкретного исправного
поведения относительно заданного класса неисправностей с использованием
восстанавливающих периодических последовательностей.
4) Для
информационно-коммуникационных
систем
показана
возможность
функционального
восстановления
при
автоматном
представлении их поведения нейронными сетями.
5) Предложен новый подход к построению логических элементов
маршрутизирующих сетевых устройств, основанный на использовании
автоматного представления нейронных сетей, который позволяет
существенно уменьшить необходимый объем памяти для хранения структуры
сети и время, необходимое на выработку решения о дальнейшей пересылке
пакета (более 60 % при решении возможности функционального
восстановления поведения заданной системы).
18
Публикации по теме диссертации
Статьи в рецензируемых изданиях, рекомендованных ВАК РФ
1) Гвоздюк, И.В. О возможностях моделирования гетерогенных
информационных систем на основе агентного подхода [Текст] /
И.В. Гвоздюк, А.В. Сластихин, Т.Э. Шульга // Вестник СГТУ. – 2014. –
№ 4 (77). – С. 167-175.
2) Гвоздюк, И.В. Об одном методе моделирования сетевых
информационных систем [Текст] / А.А. Сытник, И.В. Гвоздюк // Вестник
СГТУ. – 2015. – № 4 (81). – С. 157-164.
3) Гвоздюк, И.В. Оптимизация ресурсоёмких вычислительных задач
на графическом процессоре [Текст] / А.А. Сытник, С.П. Ивженко,
И.В. Гвоздюк // Известия Самарского научного центра Российской академии
наук. – 2016. – Т. 18. – № 4 (4). – С. 835-838.
4) Гвоздюк, И.В. Математическая модель активности пользователей
программного обеспечения [Текст] / А.А. Сытник, Т.Э. Шульга,
Н.А. Данилов, И.В. Гвоздюк // Программные продукты и системы. Тверь,
2018. Т. 31. № 1. С. 79-84.
Публикации в других изданиях
5) Гвоздюк, И.В. О возможностях применения онтологического
моделирования при разработки электронных видеоархивов [Текст] /
И.В. Гвоздюк, А.А. Сытник, Т.Э. Шульга // Инжиниринг предприятий и
управление знаниями (ИП&УЗ- 2017): сб. науч. тр. ХХ юбилейной Всерос.
науч. конф., 28-28 апреля 2017 г. / под науч. ред. Ю.Ф. Тельнова: в 2 т. – М.:
ФГБОУ ВО «РЭУ им. Г.В.Плеханова», 2017. – Т. 1. – С. 111-116.
6) Гвоздюк, И.В. Моделирование управления технических систем
дискретного типа на основе автомата с изменениями состояний в циклах
[Текст] / И.В. Гвоздюк, Н.А. Данилов, А.А. Сытник, Т.Э.Шульга // Проблемы
управления в социально-экономических и технических системах: сб. науч.
статей. – Саратов: Изд. центр «Наука», 2017. – С. 28-34.
7) Гвоздюк, И.В. О некоторых свойствах дискретных моделей при
управлении сложными системами [Текст] / А.А. Сытник, И.В. Гвоздюк //
Проблемы управления в социально-экономических и технических системах:
сб. науч. статей. – Саратов: Изд. центр «Наука», 2017. – С. 79-84
8) Гвоздюк, И.В. Об одном подходе к синтезу автоматных моделей
при управлении технических систем дискретного типа [Текст] / И.В. Гвоздюк //
Проблемы управления в социально-экономических и технических системах:
сб. науч. статей. – Саратов: Изд. центр «Наука», 2017. – С. 25-28.
9) Gvozduk, I.V. Uncertainty interval evaluation [Текст] /
A.A. Solopekina,
A.A.
Sytnik,
I.V.
Gvozduk
//
Перспективные
информационные технологии (ПИТ-2017): тр. Междунар. науч.-техн. конф. /
под ред. С.А. Прохорова. – Самара: Изд-во Самар. науч. центра РАН, 2017. –
С. 28-33.
19
10) Gvozduk, I.V. Multiport modulator [Текст] / N. Semezhev,
A.A. Solopekina, I.V. Gvozduk // Перспективные информационные технологии
(ПИТ-2017): тр. Междунар. науч.-техн. конф. / под ред. С.А. Прохорова. –
Самара: Изд-во Самар. науч. центра РАН, 2017. – C. 33-37.
11) Гвоздюк, И.В. Об одном подходе к автоматному моделированию
поведения
информационно-коммуникационных
систем
[Текст]
/
А.А. Сытник, И.В. Гвоздюк // Перспективные информационные технологии
(ПИТ-2017): тр. Междунар. науч.-техн. конф. / под ред. С.А. Прохорова. –
Самара: Изд-во Самар. науч. центра РАН, 2017. – C. 194-199.
12) Гвоздюк, И.В. Автоматное моделирование при восстановлении
поведения одного класса нейронных сетей [Текст] / И.В. Гвоздюк //
Проблемы управления в социально-экономических и технических системах:
сб. науч. статей. – Саратов: Изд.центр «Наука», 2018. – С. 83-89.
Подписано в печать 21.09.18
Формат 6084 1/16
Бум. офсет.
Усл. печ. л. 1,0
Уч.-изд. л. 1,0
Тираж 100 экз.
Заказ 41
Бесплатно
Саратовский государственный технический университет имени Гагарина Ю.А.
410054, Саратов, Политехническая ул., 77
Отпечатано в Издательстве СГТУ. 410054, Саратов, Политехническая ул., 77
Тел.: 24-95-70; 99-87-39, е-mail: izdat@sstu.ru
20
1/--страниц
Пожаловаться на содержимое документа