Содержание к диссертации
Введение
1. Анализ математического и программного обеспечения иерархических систем проектированания сложных дискретных структур 9
1.1 Анализ методов и моделей, используемых при формализации процесса функционирования сложных дискретных структур 9
1. 2Анализ видов и методов декомпозиции Сложных дискретных структур 17
І.ЗАнализ программного обеспечения, используемого при исследования процесса функционирования дискретных структур 28
ВЫВОДЫ 33
2. Декомпозиционный метод исследования процесса функционирования сложной дискретной структуры на базе модели функционального блока 34
2.1 Формализация процесса функционирования сложной дискретной структуры , формализованного в виде сети Петри 34
2.2 Алгоритм декомпозиции сложной дискретной структуры 51
Выводы 61
3. Организация планирования эксперимента при исследовании функционирования дискретной структуры 62
3.1 Задача постановки эксперимента при анализе функционирования сложной структуры 62
3.2 Проверка адекватности модели функционального блока Дискретной структуры 68
3.3 Методика проведения эксперимента при анализе функционирования сложной структуры 73
Выводы 82
4. Программно-алгоритмический комплекс декомпозрщионного метода исследования сложных дискретных структур 83
4.1 Программное обеспечение анализа процесса функционирования дискретных структур 83
4.2 Программное обеспечение подсистемы декомпозиции сложного дискретной структуры 87
4.3 Экспериментальная проверка декомпозиционного метода исследования сложных дискретных структур 114
Выводы 120
Заключение 121
Литература
- 2Анализ видов и методов декомпозиции Сложных дискретных структур
- Алгоритм декомпозиции сложной дискретной структуры
- Проверка адекватности модели функционального блока Дискретной структуры
- Программное обеспечение подсистемы декомпозиции сложного дискретной структуры
Введение к работе
В настоящее время задача анализа сложных дискретных структур является актуальной и находит большое количество применений при моделировании таких объектов как центральный процессор цифровой вычислительной машины, работа склада товаров или магазина, автомобильного потока транспортной развязки и т.д. Однако, в силу исключительного разнообразия встречающихся на практике задач и недостаточной изученности их математического описания, арсенал формализации и моделирования непрерывно пополняется. Поэтому порядок структуризации, разбиения объектов на подсистемы и элементы объектов и отбор математических схем для описания элементов нельзя считать окончательно сложившимся.
Одним из известных методов исследования процесса функционирования сложных дискретных структур является их формализация в виде простых и цветных сетей Петри [13,28,81,82,113,146,148,163]. К достоинствам сетей Петри [29,64,159,177] можно отнести возможность их графическое представление, явное описание и действий и состояний системы, отображение результатов моделирования непосредственно на схеме сети. Это определяет актуальность разработки и исследование методов формализации сложных дискретных структур именно в виде простых и цветных сетей Петри.
Большинство современных методик исследования и анализа сложных дискретных структур [31,32,59,60,79,118,168] основываются на иерархических принципах, которые требуют обеспечения сквозного проектирования структур и возможности создания или использования эффективных средств анализа, ориентированных на соответствующие методы иерархического проектирования [18,101].
Этим проблемам посвящены работы Бадулина С.С. [3,20], Баранова СИ. [22,23,24,25,26], Гаврилова М.А. [40,41], Девяткова В.В. [41,51], Ниссена К. [106], Норенкова И.П. [108,109], Петренко А.И. [1], Пупырева Е.И. [41], Советова Б. Я. [126,127], Черненьког В.М. [139,140], Яковлева С.А. [127], Фридмана Т. [167], Ульмана Дж. [137,175], Янга С. [167], и др.
Среди этих требований необходимо отметить требования о создании систем, реализующих иерархические методы, поскольку именно они позволяют единообразно анализировать дискретную структуру на нескольких функциональных уровнях и с разной степенью детализации.
Одной из задач при разработке дискретных структур является задача анализа и контроля правильности функционирования структуры на ранних этапах его разработки. В результате системного проектирования определяется структурнаяххема, то есть набор функциональных блоков и их взаимодействие. На последующих этапах осуществляется моделирование работы отдельных блоков на уровне элементов без учета взаимодействия друг с другом, Предлагаемый метод иерархического исследования позволяет осуществить анализ и контроль правильности функционирования сложной структуры с использованием методов моделирования и декомпозиции, при котором структура описывается с разной степенью детализации [16,117,142,166].
Предлагаемый метод моделирования [10,11,17,36,68,145,189,197,198,202] позволит осуществить временной анализ работы структур и контроль правильности функционирования, определить скорость выполнения отдельных команд или последовательностей команд и определить загрузку аппаратных средств. Метод анализа дискретных структур только на основе моделей функциональных блоков недостаточен, так как не позволяет учитывать такие характеристики структуры как, например, временные параметры элементов, составляющих модель, а, следовательно, выполнять надежную верификацию проекта [27,73,150,152].
Моделирование больших систем [74,94,119,144] представляет собой задачу большой размерности, поэтому одним из методов исследования таких систем является метод декомпозиции, позволяющий разбивать исследуемую схему на части, проверяя работу каждой части и последовательно добавлять к проверенной части новые фрагменты.
В работах по моделированию [76,115,141,143,147,161,192] и многоуровневому анализу [21,99,116] предлагается использовать принцип "увеличительного стекла", когда различные участки схемы структуры анализируются с разной степенью детализации. Но в этих работах предполагалось, что переход с одного иерархического уровня на другой выполняется разработчиком схемы. Предлагаемый в работе метод декомпозиции моделей, реализованный в виде программного комплекса, позволяет реализовать принцип "увеличительного стекла" путем автоматического перехода от моделей функциональных блоков к моделям элементов.
Следующим этапом после создание математической модели и ее программной реализации является постановка вычислительного эксперимента. Данному направлению посвящен целый ряд работ [8,9,39,58]. Использование вычислительного эксперимента существенно уменьшает время исследования модели. Целями эксперимента могут быть: выяснение закономерностей функционирования системы, анализ влияния факторов на показатели качества систем, проверка адекватности модели. Традиционные методики проведения экспериментов из-за зависимости компонентов восстанавливаемого аналитического описания не позволяют определить раздельное влияние каждого фактора на результирующий показатель. В отличие от них теория планирования эксперимента дает возможность оценить вклад каждого параметра в значение показателя, т.е. приближенно восстановить закон функционирования объекта по экспериментальным данным. Полученное аналитическое описание объекта можно использовать для предварительного исследования вариантов построения системы. Основные методы теории планирования эксперимента рассмотрены, в частности, в [62,96,114]. Однако существует определенный пробел в научной литературе, связанный с методикой проведения экспериментов именно над цветными сетями Петри. В настоящей работе предложена методика проведения экспериментов над сетями Петри с использованием методов теории планирования эксперимента.
Для разработанных формализованных методов исследование сложных дискретных структур в виде сети Петри создано соответствующее программное обеспечение [77,97,98,102,129,130].
Данные программные продукты требуют существенных временных и аппаратных затрат при анализе процесса функционировании сложных структур.
Поэтому целью данной диссертационной работы является разработка метода иерархического исследования сложных дискретных структур, формализованных в виде сети Петри с использованием системы программного обеспечения анализа и контроля функционирования структуры.
Для достижения поставленной цели в работе решаются следующие основные задачи:
- проводится анализ методов проектирования и формализации дискретных структур, реализующих иерархический подход при исследовании таких структур;
- дается классификация методов декомпозиции сложных дискретных структур и программного обеспечения таких методов;
- осуществляется формализация процесса функционирования дискретных структур в виде сети Петри;
- формулируется задача и разрабатывается алгоритм декомпозиции модели сложной дискретной структуры;
- разработка методики проведения машинного эксперимента с целью проверки правильности функционирования дискретных структур, формализованных в виде сети Петри.
Решению перечисленных задач посвящены первые три главы диссертационной работы. В четвертой главе рассматриваются вопросы, связанные с разработкой программного обеспечения анализа функционирования сложных дискретных структур, декомпозиции модели структуры а и проведения экспериментальных исследований правильности функционирования таких структур.
2Анализ видов и методов декомпозиции Сложных дискретных структур
Моделирование больших систем представляет собой задачу большой размерности, поэтому одним из методов исследования таких систем является метод декомпозиции, позволяющий разбивать исследуемую схему на части, проверяя работу каждой части и последовательно добавлять к проверенной части новые фрагменты.
Известно [1,2,3,4,5,6,48,180] , что методы декомпозиции делятся по методу формализации сложных дискретных структур на структурные, объектные и алгоритмические. К структурным методам относятся последовательный, параллельный и последовательно-параллельный метод. Реализации методов декомпозиции различаются по математическому представлению исследуемой системы: в виде конечного автомата, графа или сети. При объектно-ориентированной декомпозиции система разбивается, в соответствии с формализацией ее элементов различными типовыми математическими моделями. При алгоритмической декомпозиции происходит разбиение алгоритма функционирования сложной структуры на модули, где каждый модуль системы выполняет один из этапов общего процесса функционирования.
По точности решения все методы декомпозиции можно разделить на детерминированные и эвристические. Хотя детерминированные методы дают точные результаты, они весьма трудоемки по реализации. Эвристические методы позволяют находить одно локальное решение. Следует также выделить и рандомизированные алгоритмы, ориентированные на случайный поиск, что дает возможность находить серию локальных решений с приближенными результатами.
Анализ точных методов [3,21] свидетельствует о сложности проблемы оптимального разбиения систем [22,38]. Их целесообразно применять для систем с малой размерностью (не более 30 компонентов), так как они требуют значительных затрат машинного времени. Приближенные эвристические методы [10] требуют меньших временных затрат в ущерб точности, но их можно применять для систем большой размерности [10,71,72,78,87]. Известны два варианта последовательного алгоритма разбиения [15,22,23,24,25,26]. По первому при формировании очередного блока выделяется подсхема, объем которой заведомо превышает допустимый; блок формируется в результате последовательного исключения компонентов из схемы. По второму, более распространенному, компоненты последовательно включаются в формируемый блок. Последовательно-параллельный алгоритм заключается в одновременном формировании всех блоков разбиения, когда на каждом шаге свободные компоненты распределяются по блокам. Дополнительные возможности дает применение параллельных методов разбиения схем. В частности, предложено использовать дерево свертки для компоновки схем по различным критериям [3]. Такое дерево позволяет частично получить информацию о всей схеме, что отличает данный подход от последовательного, при котором разбиение строится на основе локальной информации. В группе конструктивных алгоритмов последовательные методы требуют меньшего объема оперативной памяти, однако уступают параллельным в быстродействии. Кроме того, их можно применять к схемам различных типов и структур.
При использовании итерационных алгоритмов схему сначала разбивают на определенное число блоков произвольным образом, затем делают перестановки компонентов из одного блока в другой по принятым критериям. Перестановка производится двумя способами: парным и групповым обменом [10]. Для широкого класса схем оказалось эффективным использование алгоритма групповой замены.
Для рандомизированных алгоритмов [17,19,100,132] используют метод решения задачи разбиения, основанный на случайном поиске путем введения случайного шага в процессе разбиения с последующей оценкой его эффективности. Стохастический метод связан с намеренным введением элемента случайности в процессе разбиения. Это дает возможность находить серию локальных решений и выбирать наилучший. По адаптивному методу на каждой шаге проверяется выполнение ограничений, устраняются нарушения и производится локальная, оптимизация разрезания блоков, за которой снова следует проверка выполнения ограничений и т. Д. [154,155,171].
Описанные методы целесообразно применять при агрегации сложных систем на заданное число подсистем с минимизацией связей между ними .
Сравнивая итерационные алгоритмы с конструктивными, отметим, что структура первых предопределяет их применение к разбиению на фиксированное число блоков, в то время как вторые обычно ориентированы на минимизацию числа блоков, Вместе с тем итерационные алгоритмы могут успешно применяться в сочетании с конструктивными, образуя группу смешанных методов, при этом возможно применение итерационных методов для улучшения результатов.
Алгоритмы, основанные на последовательных и итерационных методах разбиения графа, описывающего функционирование дискретной структуры , на части, являются сложными, трудно поддаются программной реализации и требуют большого объема памяти [17]. Кроме того, качество результата зависит от первоначального разбиения графов и определяется по одному критерию.
Алгоритм декомпозиции сложной дискретной структуры
Следующим этапом после создания математической модели и ее программной реализации является постановка вычислительного эксперимента [8,9,62]. Данному направлению посвящен целый раздел математики, который называется теория планирования эксперимента (ТПЭ).
В теории планирования эксперимента исследуемый объект (реальный объект, модель объекта) рассматривается как "черный ящик", имеющий входы х (управляемые независимые параметры) и выходы у.
Переменные х принято называть факторами. Основное внимание в ТПЭ уделяется активному типу экспериментов, когда имеется возможность независимо и целенаправленно менять значения факторов х во всем требуемом диапазоне. Факторы в эксперименте бывают: качественными ; количественными .
Качественные факторы можно квантифицировать или приписать им числовые обозначения, тем самым перейти к количественным значениям. В дальнейшем будем считать, что все факторы являются количественными и представлены непрерывными величинами. Переменным х можно сопоставить геометрическое понятие факторного пространства - пространства, координатные оси которого соответствуют значениям факторов. Совокупность конкретных значений всех факторов образует точку в многомерном факторном пространстве. Примерами факторов являются: интенсивность потока запросов к базе данных, скорость передачи данных по каналу, объем запоминающего устройства. Кроме того, на объект воздействуют возмущающие факторы, они являются случайными и не поддаются управлению.
Область планирования задается интервалами возможного изменения факторов: где к - количество факторов. В теории ПЭ часто используют нормализацию факторов, т.е. преобразование натуральных значений факторов в безразмерные (кодированные) величины. Переход к безразмерным значениям х; задается преобразованием. где X; - натуральное значение фактора, Хю - натуральное значение основного уровня фактора, соответствующее нулю в безразмерной шкале, Ах, — интервал варьирования. Совокупность основных уровней всех факторов представляет собой точку в пространстве параметров, называемую центральной точкой плана или центром эксперимента. С геометрической точки зрения нормализация факторов равноценна линейному преобразованию пространства факторов, при котором проводятся две операции: перенос начала координат в точку, соответствующую значениям основных уровней факторов; сжатие - растяжение пространства в направлении координатных осей [14,33,75,120].
Активный эксперимент включает: систему воздействий, при которых воспроизводится функционирование объекта и регистрацию отклика объекта. План эксперимента задает совокупность данных, определяющих количество, условия и порядок реализации опытов. Опыт составляет элементарную часть эксперимента и предусматривает воспроизведение исследуемого явления в конкретных условиях с последующей регистрацией результата. В условиях случайности в одних и тех же условиях проводятся параллельные (повторные) опыты в интересах получения статистически устойчивых результатов. Опыт и предполагает задание конкретных значений факторам х:
Строки матрицы соответствуют опытам, столбцы - факторам, элемент матрицы Хц задает значение / -го фактора в j -м опыте .
Реализовав испытания в N точках области факторного пространства, определённые планом эксперимента, получим вектор наблюдений, имеющий следующий вид: У = У, Уг У N. (3.3) где уи - отклик, соответствующий u-ой точке плана.
Зависимость отклика от факторов носит название функции отклика, а геометрическое представление функции отклика - поверхности отклика. Функция отклика рассматривается как показатель качества или эффективности объекта. Этот показатель является функцией от параметров -факторов. На практике широкое распространение получили простые функции вида,
Проверка адекватности модели функционального блока Дискретной структуры
Создание плана эксперимента.
После того как выбраны факторы и отклики для эксперимента необходимо составить план эксперимента. В настоящее время используется свыше 20 различных критериев оптимальности планов, которые подразделяются на две основные группы. К первой группе относят критерии, связанные с ошибками оценок коэффициентов, а ко второй - с ошибкой оценки поверхности отклика [49,170,173]. Далее будут охарактеризованы только те критерии, которые наиболее часто применяются при решении задач оптимизации, описания поверхности отклика и оценки влияния факторов.
Критерии первой группы представляют интерес для задач оптимизации, выделения доминирующих (наиболее значимых) параметров на начальных этапах решения оптимизационных задач или для выявления несущественных параметров в задачах восстановления закономерности функционирования объекта. Геометрическое истолкование свойств ошибок коэффициентов связано со свойствами эллипсоида их рассеяния, определяемого математическим ожиданием и дисперсией значений ошибок.
Пространственное расположение, форма, и размер эллипсоида полностью зависят от плана эксперимента.
Критерию -оптимальности соответствует минимальный объем эллипсоида рассеяния ошибок (минимум произведения всех дисперсий коэффициентов полинома). В соответствующем плане эффекты факторов максимально независимы друг от друга. Этот план минимизируют ожидаемую ошибку предсказания функции отклика. Критерию А-оптимальности соответствует план с минимальной суммарной дисперсией всех коэффициентов. Критерию -оптимальности - план, в котором максимальная дисперсия коэффициентов будет минимальна.
Выбор критерия зависит от задачи исследования, так при изучении влияния отдельных факторов на поведение объекта применяют критерий Е-оптимальности, а при поиске оптимума функции отклика - D-оптимальности. Если построение D-оптимального плана вызывает затруднения, то можно перейти к -оптимальному плану, построение которого осуществляется проще.
Критерии второй группы используются при решении задач описания поверхности отклика, определения ограничений на значения параметров. Основным здесь является критерий -оптимальности, который позволяет построить план с минимальным значением наибольшей ошибки в описании функции отклика. Применение G-оптимального плана дает уверенность в том, что в области планирования нет точек с чрезмерно большой ошибкой описания функции.
Среди всех классов планов основное внимание в практической работе уделяется ортогональным и ротатабельным планам.
Ортогональным называется план, для которого выполняется условие парной ортогональности столбцов матрицы планирования, в частности, для независимых переменных, где N - количество точек плана эксперимента, к -количество независимых факторов. При ортогональном планировании коэффициенты полинома определяются независимо друг от друга вычеркивание или добавление слагаемых в функции отклика не изменяет значения остальных коэффициентов полинома. Для ортогональных планов эллипсоид рассеяния ориентирован в пространстве так, что направления его осей совпадают с направлениями координат пространства параметров.
Использование ротатабельных планов обеспечивает для любого направления от центра эксперимента равнозначность точности оценки функции отклика (постоянство дисперсии предсказания) на равных расстояниях от центра эксперимента. Это особенно важно при решении задач поиска оптимальных значений параметров на основе градиентного метода, так как исследователь до начала экспериментов не знает направление градиента и поэтому стремится принять план, точность которого одинакова во всех направлениях. В ряде случаев при исследовании поверхности отклика требуется униморфность модели, а именно, соблюдение постоянства значений дисперсии ошибки в некоторой области вокруг центра эксперимента. Выполнение такого требования целесообразно в тех случаях, когда исследователь не знает точно расположение области поверхности отклика с оптимальными значениями параметров. Указанная область будет определена на основе упрощенной модели, полученной по результатам экспериментов.
По соотношению между количеством оцениваемых неизвестных параметров модели и количеством точек плана эксперимента все планы подразделяются на три класса: ненасыщенные - количество параметров меньше числа точек плана; насыщенные - обе величины одинаковы; сверхнасыщенные - количество параметров больше числа точек плана. Метод наименьших квадратов применяют только при ненасыщенном и насыщенном планировании, и он не применим для сверхнасыщенного планирования.
Программное обеспечение подсистемы декомпозиции сложного дискретной структуры
Транслятор выражений предназначен для преобразования списка лексем в список команд для стековой машины. Каждая команда это объект соответствующего класса. Все классы представляющие команды реализуют интерфейс ICommand. Этот интерфейс содержит метод DoCommand(). Стековая машина использует список команд, вызывая для каждого объекта из этого списка метод DoCommand. Каждый класс переопределяет этот метод по-своему. В этом методе выполняются операции над стеком. Например, класс SummCommand в этом методе выталкивает из стека два верхних числа и кладет обратно в стек их сумму. Список команд стековой машины: SummCommand - сложение. SubstractCommand - вычитание. MultComand - умножение. DivideCommand - деление. ANDCommand - логическое И. ORCommand - логическое ИЛИ. EqualComand - равно. IsGreaterCommand - больше. IsGreaterOrEqualCommand - больше или равно. IsLessCommand - меньше . IsLessOrEqualCommand - меньше или равно. NotEqualCommand - не равно. PushCommand - положить в стек значение. RValueCommand - значение по ссылке. Команда RValueCommand кладет значение переменной указанной в качестве аргумента у конструктора класса - в стек. В отличие от нее PushCommand кладет в стек числовую константу.
Вычисление выражения заключается в последовательном выполнении команд созданных на основе постфиксной записи потока лексем.
Выбор технологии программирования
В качестве используемой технологии программирования было решено использовать объектно-ориентированный подход (ООП).
Технология ООП обладает тремя главными преимуществами: она проста для понимания — ООП позволяет мыслить категориями повседневных объектов; повышенно надежна и проста для сопровождения — правильное проектирование обеспечивает простоту расширения и модификации объектно-ориентированных программ. Модульная структура позволяет вносить независимые изменения в разные части программы, сводя к минимуму риск ошибок программирования; ускоряет цикл разработки — модульность и здесь играет важную роль, поскольку различные компоненты ОО-программ можно легко использовать в других программах, что уменьшает избыточность кода и снижает риск внесения ошибок при копировании.
Кроме этого, необходимо отметить, что сеть Петри достаточно просто декомпозируется на составляющие ее части - объекты: вершины, дуги, маркеры и т.п. Это является еще одним доводом в пользу использования ООП.
Для хранения информации в файлах было решено использовать формат XML (extended Markup Language) , поскольку этот открытый стандарт весьма широко используется в практике программирования и открывает возможности по взаимодействию с другими системами. Диаграммы классов
Поскольку в качестве основной технологии разработки был выбран ООП, необходимо выделить классы в разрабатываемой системе и представить их в виде диаграмм. Поля и методы классов на диаграмме не указаны, из-за их большого объема.
Пакет Compilator classes содержит все классы связанные с лексическим и синтаксическим анализом, а также трансляцией выражений в команды стековой машины и вычислением этих выражений. Пакет Petri classes содержит все остальные классы. Рассмотрим пакет Compilator classes. Stack Machine Commands
Лексический анализатор реализован в классе LexicalAnalyser. В результате своей работы анализатор создает поток лексем, реализуемый классом TokenStorage (саму лексему представляет класс Token). Синтаксический анализ, трансляцию и вычисление выражений выполняет класс CommandList. Используя поток лексем (TokenStorage) этот класс проверяет синтаксическую правильность выражения и создает на основе потока лексем множество команд. Все эти команды реализуют интерфейс ICommand, единственным методом которого является DoCommand. Каждая команда в реализации этого метода выполняет некоторую операцию над стеком. Например, класс SummCommand в методе DoCommand выталкивает из стека два числа и кладет в стек их сумму. Используемые команды изображены на диаграмме 4.4. Таким образом, выполняя последовательность команд, вычисляется выражение. Для хранения переменных фигурирующых в выражении
Пакет Petri classes содержит в себе все классы, связанные с представлением сети Петри и ее компонентов, а также классы визуального интерфейса для работы с сетями Петри. Основные классы сети Петри отображены на рис. 4.6. Ключевым классом является PetriNet - сеть Петри. В него также входят: список позиций (PetriSiteList), список переходов (PetriTransitionList), список типов маркеров (TokenTypeList), список деклараций переменных (DeclVarList), множество констант (Constant) и функций случайного распределения (RandomFunction).
