Имитационное моделирование

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ "МОСКОВСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ" МОДЕЛИРОВАНИЕ СИСТЕМ Конспект лекций по курсу «Имитационное моделирование» для студентов, обучающихся по направлениям подготовки 081100, 080500 и 230400 МОСКВА 2016 Составитель С.Е. Дробнов, Д.Е. Кошкин Редактор А.А.Миронов Конспект лекций по курсу «Имитационное моделирование» предназначен для студентов, обучающихся по направлениям 081100 Государственное и муниципальное управление, 080500 Бизнесинформатика и 230400 «Информационные системы». Печатается по решению редакционно-издательского совета университета © МИРЭА, 2016 3 ВВЕДЕНИЕ “Определите значения слов, И вы избавите человечество От половины его заблуждений”. Р.Декарт Моделирование – это метод исследования окружающего мира, в котором некоторому изучаемому явлению поставлена в соответствие модель в виде объекта, явления, процесса, который может заменить натуру в процессе исследований. Модель отражает некоторые свойства натуры, но всегда отличается от нее. Целью моделирования является принятие адекватных (то есть обоснованных, целесообразных и реализуемых) управленческих решений. Под системой понимают совокупность объектов, объединенных какой-либо формой регулярного взаимодействия. Термин динамические системы применяется к системам, свойства которых изменяются с течением времени. С помощью методов моделирования в производственной деятельности решаются вопросы:  исследования функциональных характеристик систем;  взаимодействия систем между собой;  прогнозирования результатов функционирования систем. При проектировании и эксплуатации сложных систем возникают многочисленные задачи, требующие оценки количественных и качественных закономерностей процессов их функционирования, проведения структурного, алгоритмического и параметрического синтеза. Решение этих проблем невозможно без использования математического моделирования. Это обусловлено такими особенностями больших систем, как сложность структур, стохастичность связей между элементами и внешней средой, неоднозначность алгоритмов поведения, большое количество параметров и переменных, неполнота и недетерминированность исходной информации. Математическое моделирование позволяет 4 существенно уменьшить время проектирования, во многих случаях позволяет найти оптимальное решение, исключить метод натурных проб и ошибок, перейти к параллельному процессу проектирования. В настоящее время при анализе и синтезе больших систем получил развитие системный подход, который отличается от классического (индуктивного) подхода. Классический подход рассматривает систему путем перехода от частного к общему и синтезирует систему путем слияния ее компонент, разрабатываемых отдельно. Системный подход предполагает последовательный переход от общего к частному, когда в основе рассмотрения лежит цель, причем исследуемый объект выделяется из окружающей среды. Важным для системного подхода является определение структуры системы – совокупности связей между элементами системы, отражающих их взаимодействие. Существуют две разновидности подходов к исследованию структуры системы и ее свойств: Структурные подходы – выявляются состав выделенных элементов системы и связи между ними. Функциональные подходы – рассматриваются алгоритмы поведения системы (функции - свойства, приводящие к достижению цели). Системный и классический подходы базируются, соответственно, на принципах дедукции и индукции при анализе систем. Индуктивные заключения при анализе обладают рядом недостатков в строгости выводов по сравнению с дедукцией, особенно в сложных неоднородных системах, взаимодействие элементов в которых может оказаться контринтуитивным. 5 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ МОДЕЛИРОВАНИЯ СИСТЕМ Понятие системы и элемента системы. Специалисты по проектированию и эксплуатации сложных систем имеют дело с системами управления различных уровней, обладающими общим свойством – стремлением достичь некоторой цели. Эту особенность учтем в следующих определениях системы. Система S – целенаправленное множество взаимосвязанных элементов любой природы. Внешняя среда Е – множество существующих вне системы элементов любой природы, оказывающих влияние на систему или находящихся под ее воздействием. Понятие модели. Модель – представление объекта, системы или понятия, в некоторой форме, отличного от их реального существования. Моделирование – во-первых, построение модели, во-вторых, изучение модели, в-третьих, анализ системы на основе данной модели. При системном подходе к моделированию систем необходимо, прежде всего, четко определить цель моделирования. Применительно к вопросам моделирования цель возникает из требуемых задач моделирования, что позволяет подойти к выбору критерия и оценить, какие элементы войдут в создаваемую модель М. Поэтому необходимо иметь критерий отбора отдельных элементов, которые будут включены в создаваемую модель. Цели моделирования: 1) Оценка – оценить действительные характеристики проектируемой или существующей системы, определить насколько система предлагаемой структуры будет соответствовать предъявляемым требованиям. 2) Сравнение – произвести сравнение конкурирующих систем одного функционального назначения или сопоставить несколько вариантов построения одной и той же системы. 6 3) Прогноз – оценить поведение системы при некотором предполагаемом сочетании рабочих условий. 4) Анализ чувствительности – выявить из большого числа факторов, действующих на систему те, которые в большей степени влияют на ее поведение и определяют показатели ее эффективности. 5) Оптимизация – найти или установить такое сочетание действующих факторов и их величин, которое обеспечивает наилучшие показатели эффективности системы в целом. 1-4 – задачи анализа, 5 – задача синтеза. Стадии разработки моделей. На базе системного подхода может быть предложена и некоторая последовательность разработки моделей. Выделяют две основные стадии проектирования: Макропроектирование – на основе данных о реальной системе S и внешней среде Е строится модель внешней среды, выявляются ресурсы и ограничения для построения модели системы, выбирается модель системы и критерии, позволяющие оценить адекватность модели М реальной системы S. Микропроектирование – в значительной степени зависит от конкретного типа выбранной модели. В случае имитационной модели необходимо обеспечить создание информационного, математического, технического и программного обеспечения систем моделирования. Независимо от типа используемой модели М при ее построении необходимо руководствоваться рядом принципов системного подхода: 1) Пропорционально-последовательное продвижение по этапам и направлениям создания модели; 2) Согласование информационных, ресурсных, надежностных и других характеристик; 3) правильное соотношение отдельных уровней иерархии в системе моделирования; 7 4) целостность отдельных обособленных стадий построения модели. Характеристики моделей систем. При моделировании рассматривают следующие характеристики моделей: Цель функционирования – определяется степенью целенаправленности поведения модели М. Модели могут быть разделены на одноцелевые, предназначенные для решения одной задачи, и многоцелевые, позволяющие разрешить или рассмотреть ряд сторон функционирования реального объекта. Сложность – оценивается по общему числу элементов в системе и связей между ними. В качестве элементов можно выделить уровни иерархии, отдельные функциональные подсистемы в модели М, входы и выходы и т.д. Целостность – указывает на то, что создаваемая модель М является одной целостной системой S(M), включает в себя большое количество составных частей (элементов), находящихся в сложной взаимосвязи друг с другом. Неопределенность. Проявляется в системе: по состоянию системы, возможности достижения поставленной цели, методам решения задач, достоверности исходной информации и т.д. Основной характеристикой неопределенности служит мера информации – энтропия, позволяющая в ряде случаев оценить количество управляющей информации, необходимой для достижения заданного состояния системы. При моделировании основная цель – получение требуемого соответствия модели реальному объекту, и в этом смысле количество управляющей информации в модели можно также оценить с помощью энтропии и найти то предельное минимальное количество, которое необходимо для получения требуемого результата с заданной достоверностью. Поведение системы – позволяет оценить эффективность достижения системой поставленной цели. В зависимости от наличия случайных воздействий можно различать детерминированные (когда случайные переменные и системе отсутствуют или не учитываются) и стохастические системы (когда в системе 8 присутствуют случайные переменные), по своему поведению – непрерывные, дискретные и т.д. Поведение системы S позволяет применительно к модели М оценить эффективность построенной модели, а также точность и достоверность полученных при этом результатов. Очевидно, что поведение модели М не обязательно совпадает с поведением реального объекта, причем часто моделирование может быть реализовано на базе иного материального носителя. Адаптивность – способность модели приспособиться к различным внешним возмущающим факторам в широком диапазоне изменения воздействий внешней среды, а также изучение поведения модели в изменяющихся условиях, близких к реальным. Существенным может оказаться вопрос устойчивости модели к различным возмущающим воздействиям. Организационная структура системы моделирования как комплекс технических средств, информационного, математического и программного обеспечения системы моделирования позволяет оптимизировать время моделирования и точность получаемых результатов. Управляемость модели со стороны экспериментаторов для получения возможности рассмотрения протекания процесса в различных условиях, имитирующих реальные. Наличие многих управляемых параметров и переменных модели в реализованной системе моделирования дает возможность поставить широкий эксперимент и получить обширный спектр результатов. Возможность развития модели позволяет создавать мощные системы моделирования для исследования многих сторон функционирования реального объекта. ТЕМЫ ДОКЛАДОВ 1. Математическое моделирование как наука и искусство. 2. Перспективы развития сложных систем. компьютерного моделирования 3. История математического и имитационного моделирования. 9 4. Последние достижения моделирования. в области компьютерного 5. Моделирование в биоинформатике. Основные аспекты и последние достижения. 6. Моделирование в информационной безопасности. Основные аспекты и последние достижения. 7. Проблемы классического подхода индуктивных умозаключений. в моделировании и 10 2. КЛАССИФИКАЦИЯ СИСТЕМ МОДЕЛИРОВАНИЯ Модель – объект, находящийся в определенном объективном соответствии с исследуемым объектом, несущий о нем определенную информацию и способный его замещать на определенных этапах познания. Таблица 2.1. Классификация систем моделирования Признак Виды моделей классификации Аспект Функциональный моделирования Описание Описывает совокупность функций, функциональных подсистем, их взаимосвязи. Функциональное описание исходит из того, что всякая система выполняет некоторые функции: просто пассивно существует, служит областью обитания других систем, обслуживает системы более высокого порядка, служит средством для создания более совершенных систем. Функционирование системы может описываться: числовым функционалом, зависящем от функций, описывающих внутренние процессы системы; качественным функционалом (упорядочение в терминах «лучше», «хуже», «больше», «меньше» и т.д.). Функционал количественно или качественно описывающий деятельность системы называют 11 Информационный функционалом эффективности. Функциональная организация может быть описана:  алгоритмически;  аналитически;  графически;  таблично;  посредством временных диаграмм функционирования;  вербально (словесно). Описание должно соответствовать концепции развития систем определенного класса и удовлетворять некоторым требованиям: должно быть открытым и допускать возможность расширения (сужения) спектра функций, реализуемых системой; предусматривать возможность перехода от одного уровня рассмотрения к другому, т.е. обеспечивать построение виртуальных моделей систем любого уровня. Отражает состав и взаимосвязи между элементами системы. Совокупность информации, характеризующая существенные свойства и состояния объекта, процесса, 12 Поведенческий (событийный) явления, а также взаимосвязь с внешним миром. Информационные модели делятся на: Описательные информационные модели это модели, созданные на естественном языке (т.е. на любом языке общения между людьми: английском, русском, китайском, мальтийском и т.п.) в устной или письменной форме. Формальные информационные модели это модели, созданные на формальном языке (т.е. научном, профессиональном или специализированном). Примеры: все виды формул, таблицы, графы, карты, схемы и т.д. Описывает динамику функционирования с помощью понятий: состояние системы, событие, переход из одного состояния в другое, условия перехода, последовательность событий. Кроме переменных, определяющих состояние системы и логики, определяющей, что произойдет в ответ на какоето событие, система дискретно-событийного моделирования содержит следующие компоненты: 13 Часы – основной компонент системы, синхронизирующий ее изменения, т.е. возникновение событий. Список событий – система моделирования поддерживает, по крайней мере, один список событий моделирования. Однопоточные системы моделирования, основанные на мгновенных событиях, имеют только одно текущее событие. В то время как многопоточные системы моделирования и системы моделирования, поддерживающие интервальные события, могут иметь несколько текущих событий. В обоих случаях имеются серьёзные проблемы с синхронизацией между текущими событиями. Генераторы случайных чисел. Дискретнособытийные модели делятся на детерминированные и стохастические, в зависимости от того, каким образом генерируются события и основные характеристики очередей: время наступления событий, длительность обслуживания, количество клиентов, поступающих в очередь в 14 Соответствие оригиналу Полный единицу времени. К поведенческим моделям относятся также модели Монте-Карло. Моделирование по методу Монте-Карло представляет собой автоматизированную математическую методику, предназначенную для учета риска в процессе количественного анализа и принятия решений. Стохастические дискретно-событийные модели отличаются от моделей Монте-Карло наличием часов. Моделирование по методу Монте-Карло. Статистика – основные данные, которые собираются в системах дискретнособытийного моделирования:  Средняя занятость (доступность) ресурсов;  Среднее количество клиентов в очереди;  Среднее время ожидания в очереди. Условие завершения (им могут быть: возникновение заданного события и прохождение заданного числа циклов по часам системы моделирования). Получают изоморфные модели (включающие все 15 Приближенный Форма реализации Реальный Мысленный Наличие управляемых переменных Конструктивный Дескриптивные (описательные, концептуальные) характеристики объектаоригинала), находящиеся в строгом соответствии с оригиналом и дающие о нем исчерпывающую информацию. Получают гомоморфные модели (подобные в определенной степени объекту-оригиналу) путем сознательного огрубления исследуемого процесса, значительного сокращения числа факторов, отбора среди них наиболее существенных. Используется возможность исследования характеристик либо на реальном объекте, либо на его части. Применяется, когда модели не реализуемы в заданном интервале времени, либо отсутствуют условия для их физического создания. В модель включаются управляемые переменные, что позволяет находить эффективное управляющее воздействие. Предварительное содержательное описание исследуемого объекта, не содержащее управляемых переменных, оно играет вспомогательную роль и предшествует построению конструктивной модели (например, математической). 16 Модели имеют вид схем, отражающих наши представления о том, какие переменные наиболее существенны и как они связаны между собой. Изменение во Статический Служит для описания времени состояния объекта в фиксированный момент времени. Динамический Служит для исследования объекта во времени. Степень Детерминированный Отображение процессов, в определенности которых все параметры и воздействия предполагаются не случайными, а причинно обусловленными. Стохастический Учитываются вероятностные процессы и события. Способ Наглядный Строятся модели реализации геометрического подобия (изобразительные модели):  Чертежи;  Схемы;  Диаграммы;  Карты;  Макеты самолетов;  модели солнечной системы в планетариях;  модели атома и т.п. Математический Процесс установления (символический) соответствия реальному объекту некоторого набора символов и выражений, например математических. Математические модели наиболее удобны для исследования и 17 Имитационный Натурный Физический Аналоговый количественного анализа, позволяют не только получить решение для конкретного случая, но и определить влияние параметров системы на результат решения. Воспроизведение (с помощью ЭВМ) алгоритма функционирования сложных объектов во времени, поведения объекта. Имитируются элементарные явления, составляющие процесс, с сохранением их логической структуры и последовательности протекания. Это искусственный эксперимент, при котором вместо проведения натурных испытаний с реальным объектом проводятся опыты на математических моделях. Проведение исследования на реальном исследуемом объекте. Исследования проводятся на установках, которые сохраняют физическую природу исследуемого объекта, но отличаются от него размерами, формой и другими характеристиками (аэродинамическая труба, в которой отрабатываются свойства летательного аппарата). Набор одних свойств 18 используется для отображения свойств другой физической природы: гидравлическая система как аналог электрической или транспортной; электрическая система как аналог механической, транспортной системы. 19 3. ОСНОВНЫЕ ПОДХОДЫ К МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ СИСТЕМ ПОСТРОЕНИЮ Наибольшие затруднения и наиболее серьезные ошибки при моделировании возникают при переходе от содержательного описания объектов исследования к формальному. Это объясняется участием в этом творческом процессе коллективов разных специальностей: специалистов в области систем, которые требуется моделировать (заказчиков), и специалистов в области машинного моделирования (исполнителей). Эффективным средством для нахождения взаимопонимания между этими группами специалистов является язык математических схем. Он позволяет во главу угла поставить вопрос об адекватности перехода от содержательного описания системы к ее математической схеме, а лишь затем решать вопрос о конкретном методе получения результатов с использованием ЭВМ: аналитическом, имитационном или комбинированном (аналитико-имитационном). Применительно к конкретному объекту моделирования, т.е. к сложной системе, разработчику модели должны помочь конкретные, уже прошедшие апробацию (ранее проверенные и одобренные) математические схемы для данного класса систем, показавшие свою эффективность в прикладных исследованиях на ЭВМ и получившие название типовых математических схем. Математическая модель – это совокупность математических объектов (чисел, переменных, множеств, векторов, матриц и т.п.) и отношений между ними, адекватно отображающая физические свойства создаваемого технического объекта. Процесс формирования математической модели и использования ее для анализа и синтеза называется математическим моделированием. При построении математической модели системы необходимо решить вопрос о ее полноте. Полнота модели регулируется, в основном, выбором границы между системой и внешней средой «система S – среда Е». Также должна быть решена задача упрощения модели, которая помогает выделить в зависимости от цели моделирования основные свойства системы, отбросив второстепенные. 20 При переходе от содержательного к формальному описанию процесса функционирования системы с учетом воздействия внешней среды применяют математическую схему как звено в цепочке «описательная модель – математическая схема – математическая (аналитическая и/или имитационная) модель». Модель объекта (системы S) можно представить в виде множества величин, описывающих процесс функционирования реальной системы: совокупность входных воздействий на систему X: xi  X , i  1, n X ; (3.1) совокупность воздействий внешней среды V: v j  V , j  1, nV ; (3.2) совокупность внутренних (собственных) параметров систем H: hk  H , k  1, nH ; (3.3) совокупность выходных характеристик системы Y: yq  Y , q  1, nY ; (3.4) В общем случае xi, yq, vj, hk являются элементами непересекающихся подмножеств и содержат как детерминированные, так и стохастические составляющие. Входные воздействия, воздействия внешней среды Е и внутренние параметры системы являются независимыми (экзогенными) переменными, которые в векторной форме имеют соответственно вид x(t )  ( x1 (t ),..., xnX (t )); v(t )  ( v1 (t ),..., vnV (t )); h(t )  ( h1 (t ),..., hnH (t )); (3.5) а выходные характеристики являются зависимыми (эндогенными) переменными и в векторной форме имеют вид: 21 y(t )  ( y1 (t ),..., yn y (t )); (3.6) Процесс функционирования системы S описывается во времени оператором FS , который преобразует экзогенные переменные в эндогенные в соответствии со следующим соотношением: y (t )  FS ( x(t ), v(t ), h(t ), t ); (3.7) Зависимость (3.7) называется законом функционирования системы FS . Он задается в виде функции, функционала, логических условий, в алгоритмической, табличной формах или в виде словесного правила соответствия. По изменению во времени модели делятся на динамические и статические. Динамическими моделями называются, если математические соотношения (3.7) описывают поведение объекта (системы) моделирования во времени t, т.е. отражают динамические свойства. Для статических моделей математическая модель представляет собой отображение между двумя подмножествами свойств моделируемого объекта Y и {X, V, H} в определенный момент, что в векторной форме может быть записано как y  F ( x, v, h); S (3.8) Соотношения (3.7) и (3.8) могут быть заданы различными способами: аналитически (с помощью формул), графически, таблично и т.д. Эти соотношения могут быть получены через свойства системы S в конкретные моменты времени, называемые состояниями. Если рассматривать процесс функционирования системы S как последовательную смену состояний z1(t ),..., zk (t ) , то они могут быть интерпретированы как координаты точки в k-мерном фазовом пространстве. Причем каждой реализации процесса будет соответствовать некоторая фазовая траектория. Совокупность всех возможных значений состояний {z} называется пространством состояний объекта моделирования Z, причем zk  Z . Таким образом, под математической моделью объекта (реальной системы) понимают конечное подмножество переменных 22 вместе с математическими связями между ними и характеристиками y(t ) . {x(t ), v(t ), h(t )} Математическая модель также может быть стохастической, т.е. учитывающей случайные переменные, и детерминированной, если математическое описание объекта моделирования не содержит элементов случайности или они не учитываются, т.е. если можно считать, что стохастические воздействия внешней среды v(t ) и стохастические внутренние параметры h(t ) отсутствуют. Это значит, что все характеристики системы однозначно определяются детерминированными входными воздействиями y (t )  f ( x, t ) (3.9) Типовые математические схемы На первоначальных этапах моделирования и исследования систем в области системотехники и системного анализа рациональнее использовать типовые математические схемы, имеющие ряд преимуществ простоты и наглядности. К ним относятся: Дифференциальные (а также интегральные, интегродифференциальные и другие) уравнения - используются для представления систем, функционирующих в непрерывном времени, когда не учитываются случайные факторы (детерминированная модель); Конечные и вероятностные автоматы - для представления систем, функционирующих в дискретном времени; Системы массового обслуживания - в качестве стохастических моделей для представления систем с непрерывным временем; Сети Петри - для анализа причинно-следственных связей в сложных системах, где одновременно параллельно протекает несколько процессов; Агрегативные системы - данный подход является общим (универсальным) и применяется для описания поведения непрерывных и дискретных, детерминированных и стохастических систем (например, Автоматизированных системах обработки 23 информации и управления (АСОИУ)). При агрегативном описании сложный объект (система) расчленяется на конечное число частей (подсистем), сохраняя при этом связи, обеспечивающие взаимодействие частей. Таким образом, при построении математических моделей процессов функционирования систем можно выделить следующие основные подходы: непрерывно-детерминированный (D-схемы); дискретно-детерминированный (F-схемы); дискретно-стохастический (Р-схемы); непрерывно-стохастический (Q-схемы); сетевой (N-схемы); обобщенный или универсальный (А-схемы). ТЕМЫ ДОКЛАДОВ 1. Современные методы прогнозирования явлений и процессов. 2. Сети массового обслуживания и их применение. 3. Качественные методы моделирования систем. 4. Системная динамика как методология исследования сложных процессов. и инструмент 5. Моделирование и анализ распределенных информационных систем. 6. Модификация сетей специального вида. Петри для моделирования систем 7. Вложенные сети Петри и моделирование распределенных систем. 8. Моделирование систем на основе анализа размерностей и теории подобия. 24 9. Анализ сложных систем с помощью моделей клеточных автоматов. 10. Методы интеллектуального анализа данных. 25 4. НЕПРЕРЫВНО-ДЕТЕРМЕНИРОВАННЫЕ МОДЕЛИ (DСХЕМЫ) Непрерывно-детерминированные модели используются для анализа и проектирования динамических систем с непрерывным временем, процесс функционирования которых описывается детерминированными зависимостями. Данный класс систем может быть описан с помощью:  дифференциальных;  интегральных;  интегрально-дифференциальных;  общих функциональных уравнений. При этом важнейшее место среди них занимают дифференциальные уравнения, описывающие динамические системы. В этих уравнениях неизвестными выступают функции одной или нескольких переменных и их производные различных порядков. Если неизвестные - функции одной независимой переменной, то имеют место обыкновенные дифференциальные уравнения. Если неизвестные - функции многих переменных, то речь идет об уравнениях в частных производных, которые в настоящее время получили широкое распространение и используются для исследования систем с распределенными параметрами. Исторически сложилось так, что в течение трехсот лет интенсивно изучались методы решения дифференциальных уравнений. Эти уравнения длительное время служили основным средством решения научно-технических задач. В силу этого в настоящее время имеется глубоко разработанная теория, богатый аналитический аппарат и широкий набор численных методов решения обыкновенных дифференциальных уравнений. Рассмотрим особенности непрерывно детерминированного подхода, используя в качестве математической модели дифференциальные уравнения. 26 Математическое соотношение для детерминированных систем в общем виде:  y l     f ( y , t ), y (t 0)   y (4.1) Например, процесс малых колебаний маятника обыкновенными дифференциальным уравнением ( t ) m l    m gl(t )  0 описан 2 2 1 1 t 2 2 (4.2) где m1, l1 - масса, длина подвески маятника,  - угол отклонения маятника от положения равновесия. Из этого уравнения можно найти оценки интересующих характеристик, например период колебаний T  2 l / g (4.3) Дифференциальные уравнения, D-схемы являются математическим аппаратом теории систем автоматического регулирования и управления (САУ). Стоит отметить, что САУ является частным случаем динамическим систем, описываемых D–схемами, которые выделены в отдельный класс моделей в силу их практической специфики. При проектировании и эксплуатации систем САУ необходимо выбрать такие параметры системы, которые бы обеспечивали требуемую точность управления. ТЕМЫ ДОКЛАДОВ 1. Дифференциальные уравнения. История создания. Области применения. Примеры. 2. Уравнения в частных Особенности. Примеры. производных. Назначения. 3. Теория систем управления. История. Области применения. Примеры. 27 5. ДИСКРЕТНО-ДЕТЕРМЕНИРОВАННЫЕ МОДЕЛИ (FСХЕМЫ) ДДМ являются предметом рассмотрения теории автоматов (ТА). ТА - раздел дискретной математики, изучающий абстрактные автоматы - вычислительные машины, представленные в виде математических моделей - и задачи, которые они могут решать. Теория автоматов наиболее тесно связана с теорией алгоритмов: автомат преобразует дискретную информацию по шагам в дискретные моменты времени и формирует результат по шагам заданного алгоритма. Конечный автомат (КА) имеет множество состояний и входных сигналов, являющихся множествами. Автомат задаётся F- схемой: F=, внутренних конечными (5.1) Где x, y, z – соответственно, конечные множества входных, выходных сигналов (алфавитов) и конечное множество внутренних состояний (алфавита); z0 – начальное состояние (при z0Z); φ(z,x) – функция переходов; ψ(z,x) – функция выхода. Автомат функционирует в дискретном автоматном времени, моментами которого являются такты. Такты - примыкающие друг к другу равные интервалы времени, каждому из которых соответствуют постоянные значения входного, выходного сигнала и внутреннего состояния. Абстрактный автомат имеет один входной и один выходной каналы. В момент t, будучи в состоянии z(t), автомат способен воспринять сигнал x(t) и выдать сигнал y(t) = [z(t),x(t)] (5.2) z(t+1) = [z(t),z(t)], z(t)Z; y(t)Y; x(t)X (5.3) переходя в состояние 28 Абстрактный КА в начальном состоянии z0 принимая сигналы {x(0), x(1), x(2), …, x(tn)} выдаёт сигналы {y(0), y(1), y(2), …, y(tn)} (выходное слово). Различают F- автоматы 1-ого рода (автомат Мили), и автоматы 2-ого рода. F-автомат 1-ого рода функционирует схеме: z(t+1) = [z(t),x(t)], t=0,1,2… (5.4) y(t)=[z(t),x(t)], t=0,1,2… (5.5) F-автомат 2-ого рода: z(t+1)= [z(t),x(t)], t=0,1,2… (5.6) y(t)=[z(t-1),x(t)], t=1,2,3… (5.7) Автомат 2-ого рода, для которого функция выходов не зависит от входной переменной x(t), называется автоматом Мура: y(t) = [z(t)], t=0,1,2,… (5.8) Таким образом, уравнения 1-5 полностью задающие F- автомат, являются частным случаем уравнения    z (t )  ( z 0 , x , v , h , t ) (5.9)   где z - вектор состояния, x - вектор независимых входных  переменных, v - вектор воздействий внешней среды, h - вектор собственных внутренних параметров системы, z 0 - вектор начального состояния, t – время. По числу состояний конечные автоматы бывают: С памятью - имеют более одного состояния; Без памяти (комбинационные или логические схемы) – обладают лишь одним состоянием. Таким образом, работа комбинационной схемы заключается в том, что она ставит в соответствие каждому входному сигналу x(t) определённый выходной сигнал y(t), т.е. реализует логическую функцию вида: 29 y(t) = [x(t)], t=0,1,2,… (5.11) Эта функция называется булевой, если алфавиты X и Y, которым принадлежат значения сигналов x и y состоят из 2-х букв. По характеру отсчёта времени (дискретному) F-автоматы делятся на:  синхронные - моменты времени, в которые автомат "считывает" входные сигналы, определяются принудительно синхронизирующими сигналами. Реакция автомата на каждое значение входного сигнала заканчивается за один такт синхронизации.  асинхронные - входной сигнал считывается непрерывно, поэтому автомат, реагируя на достаточно длинный входной сигнал постоянной величины x, может, как это следует из 1-5, несколько раз изменить своё состояние, выдавая соответствующее число выходных сигналов, пока не перейдёт в устойчивое. Для задания F-автомата необходимо описать все элементы множества F= (5.12) т.е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов. Для задания работы F-автоматов наиболее часто используются способы:  табличный;  графический;  матричный. Далее рассмотрим более подробно каждый из них. Табличный способ задания работы F-автомата В табличном способе задания используется таблицы переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы - его состояниям. При этом обычно 1-ый столбец 30 слева соответствует начальному состоянию z0. На пересечении i-ой строки и j-ого столбца таблицы переходов помещается соответствующее значение (zk,xi) функции переходов, а в таблице выходов - (zk, xi) функции выходов. Для F-автомата Мура обе таблицы можно совместить, получив так называемую отмеченную таблицу переходов, в которой над каждым состоянием zk автомата, обозначающим столбец таблицы, стоит соответствующий этому состоянию выходной сигнал (zi). Описание работы F-автомата Мили таблицами переходов и выходов иллюстрируется таблицей (5.1), а описание F-автомата Мура - таблицей переходов (5.2). Таблица 5.1 xj zk z0 x1 x2 xj x1 z1 Переходы (z0,x1) (z1,x1) (z0,x2) (z1,x2) … … … Выходы (z0,x1) (z1,x1) … … zk … … (zk,x1) (zk,x2) … … … (zk,x1) Таблица 5.2 (zk) xi (z0) (z1) z0 z1 x1 (z0,x1) (z1,x1) x2 (z0,x2) (z1,x2) … xl (z0,xl) (z1,xl) … … … … (zk) zk (zk,x1) (zk,x2) … (zk,xl) 31 Примеры табличного способа задания F-автомата Мили F1 с тремя состояниями, двумя входными и двумя выходными сигналами приведены в таблице 5.3, а для F- автомата Мура F2 - в таблице 5.4. Таблица 5.3 xj x1 x2 x1 x2 z0 z0 z1 Переходы z2 z0 z0 z2 Выходы y1 y1 y1 y2 z2 z0 z1 Таблица 5.4 xi y1 z0 x1 z1 x2 z3 y1 z1 z4 z1 y y3 z2 z4 z1 y2 z3 z2 z0 y3 z4 z2 z0 y2 y1 Графический способ задания работы F-автомата В этом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершин дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал xk вызывает переход из состояния zi в состояние zj, то на графе автомата дуга, соединяющая вершину zi с вершиной zj обозначается xk. Для того, чтобы задать функцию переходов, дуги графа необходимо отметить соответствующими выходными сигналами. Для автоматов Мили эта разметка производиться так: если входной сигнал xk действует на состояние zi, то согласно сказанному получается дуга, исходящая из zi и помеченная xk, эту дугу дополнительно отмечают выходным сигналом y = (zi, xk). Для автомата Мура аналогичная разметка графа такова: если входной сигнал xk, действуя на некоторое состояние автомата, вызывает переход в состояние zj, то дугу, направленную в zj и помеченную xk, дополнительно отмечают выходным сигналом y = (zj) (и обозначение это ставится над состоянием zj). На рис. 1 приведены заданные ранее таблицами F- автоматы Мили F1 и Мура F2 соответственно. 32 Рис. 5.1. Графы автоматов Мили (а) и Мура (б). При решении задач моделирования часто более удобной формой является матричное задание конечного автомата. При этом матрица соединений автомата есть квадратная матрица С=||cij||, строки которой соответствуют исходным состояниям, а столбцы состояниям перехода. Элемент cij=xk/yS в случае автомата Мили соответствует входному сигналу xk, вызывающему переход из состояния zi в состояние zj и выходному сигналу yS, выдаваемому при этом переходе. Для автомата Мили F1, рассмотренного выше, матрица соединений имеет вид:  /y  x2 1  C1   x1 / y1  /y  x1 2   x /y 2 1 x / y  x / y  1 1 2 2  (5.13)   Если переход из состояния zi в состояние zj происходит под действием нескольких сигналов, элемент матрицы cij представляет собой множество пар "вход/выход" для этого перехода, соединённых знаком дизъюнкции. Для F-автомата Мура элемент cij равен множеству входных сигналов на переходе (zizj), а выход описывается вектором выходов:   ( z 0)       ( z1)  y  ......     ( z k )  (5.14) i-ая компонента которого – выходной сигнал, отмечающий состояние zi. 33 Пример. Для рассмотренного ранее автомата Мура F2 запишем матрицу состояний и вектор выходов:    C2     x2   x2 x x x 1  2  2    x 2  1   1  x x y    1  y  x1 2  ; y   y   3 x1     y2   y   3 (5.15) Для детерминированных автоматов переходы однозначны. Применительно к графическому способу задания F-автомата это означает, что в графе F-автомата из любой вершины не могут выходить 2 и более ребра, отмеченные одним и тем же входным сигналом. Аналогично этому в матрице соединений автомата С в каждой строке любой входной сигнал не должен встречаться более одного раза. Для F-автомата состояние zk называется устойчивым, если для любого входа xiX, для которого (zk,xi)=zk имеет место (zk,xi)=yk. Таким образом, F- автомат называется асинхронным, если каждое его состояние zkZ устойчиво. На практике в большинстве случаев автоматы являются асинхронными, а устойчивость их состояний обеспечивается тем или иным способом, например, введением сигналов синхронизации. На уровне абстрактной теории часто удобно оперировать синхронными конечными автоматами. Пример. Рассмотрим асинхронный F-автомат Мура, который описан в табл. 5.5 и приведён на рис. 5.2. Таблица 5.5 xi x1 x2 x3 y1 z0 z1 z2 z0 y y2 z1 z1 z1 z0 y3 z2 z1 z2 z2 34 Рис. 5.2. Граф асинхронного автомата Мура. Если в таблице переходов асинхронного автомата некоторое состояние zk стоит на пересечении строки xS и столбца zS(Sk), то это состояние zk обязательно должно встретиться в этой же строке в столбце zk. С помощью F-схем описываются узлы и элементы ЭВМ, устройства контроля, регулирования и управления, системы временной и пространственной коммутации в технике обмена информацией. Широта применения F-схем не означает их универсальность. Этот подход непригоден для описания процессов принятия решений, процессов в динамических системах с наличием переходных процессов и стохастических элементов. ТЕМЫ ДОКЛАДОВ 1. Теория графов. История создания. Области применения. Примеры. 2. Теория автоматов. История создания. Области применения. Примеры. 3. Автомат Мура. История создания. Области применения. Примеры. 4. Автомат Мили. История создания. Области применения. Примеры. 35 6. НЕПРЕРЫВНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ (Q-СХЕМЫ) К ним относятся системы массового обслуживания (англ. Queuing system), наываемые также Q-схемами. Системы массового обслуживания (СМО) и сети массового обслуживания являются предметом рассмотрения теории массового обслуживания (ТМО) - раздела теории вероятностей, целью исследований которого является рациональный выбор структуры системы обслуживания и процесса обслуживания на основе изучения потоков требований на обслуживание, поступающих в систему и выходящие из неё, длительности ожидания и длины очередей. Под системой массового обслуживания понимают динамическую систему, предназначенную для эффективного обслуживания случайного потока заявок при ограниченных ресурсах системы. Обобщённая структура СМО приведена на рисунке 6.1. Рис. 6.1. Схема СМО. Поступая на вход СМО, однородные заявки делятся на типы в зависимости от порождающей их причины. Интенсивность потока заявок типа i (i=1,…,M) обозначена i . Совокупность всех типов заявок образует входящий поток СМО. Обслуживание заявок выполняется m каналами. Различают каналы: 36 Универсальные. Для универсального канала типа j считаются известными функции распределения длительности Fij ( ) обслуживания заявок произвольного типа. Специализированные. Для специализированных каналов функции распределения длительности обслуживания каналов заявок некоторых типов являются неопределёнными. В качестве процесса обслуживания могут быть представлены различные по своей физической природе процессы функционирования экономических, производственных, технических и других систем (потоки поставок продукции некоторому предприятию, потоки деталей и комплектующих изделий на сборочном конвейере цеха, заявки на обработку информации ЭВМ от удалённых терминалов и пр.). При этом характерными особенностями для работы таких объектов являются случайное поведение заявок (требований) на обслуживание и завершение обслуживания в случайные моменты времени. Для исследования Q-схем применяются аналитические и имитационные модели (последние обеспечивает большую универсальность). Понятие массового обслуживания В любом элементарном акте обслуживания можно выделить две основные составляющие: ожидание обслуживания заявкой и обслуживание заявки. Это можно отобразить в виде некоторого i-ого прибора обслуживания Пi, состоящего из накопителя заявок и канала обслуживания заявок ki. При этом в накопителе может находиться одновременно li=0…LiH заявок, где LiH - ёмкость i-ого накопителя. ui Hi w i Пi Ki yi Рис. 6.2. Схема прибора СМО 37 На каждый элемент прибора обслуживания Пi поступают потоки событий: в накопитель Hi поток заявок wi , на канал ki поток обслуживания ui. Потоком событий (ПС) называется последовательность событий, происходящих одно за другим в какие-то случайные моменты времени. Разновидности потоков событий Различают потоки однородных и неоднородных событий. Однородный поток событий (ОПС) характеризуется равнозначностью всех заявок и моментами поступления этих событий (вызывающими моментами), то есть дополнительные особенности заявок не учитываются. ОПС задаётся последовательностью {tn}={0, t1, t2, …, tn}, где tn - момент поступления n-ого события неотрицательное вещественное число. ОПС может быть также задан в виде последовательности промежутков времени {tn} между n-ым и (n1)-ым событиями. Неоднородный ПС характеризуется не только вызывающим моментом, но и набором признаков самого события. Таким образом, НПС называется последовательность {tn, fn} , где tn- вызывающие моменты; fn- набор признаков события. Например, может быть задана принадлежность к тому или иному источнику заявок, наличие приоритета, возможность обслуживания тем или иным типом канала и т.п. Неоднородным ПС может также называться поток, в котором события разделены интервалами времени t1, t2, ..., являющимися случайными величинами. И если эти интервалы t1, t2, ... являются независимыми между собой, то такой поток событий называется потоком с ограниченным последействием. Поток событий называется ординарным, если вероятность того, что на малый интервал времени Δt, примыкающий к моменту времени ti , попадает больше одного события Р>1 (ti, Δt), пренебрежительно мала по сравнению с вероятностью того, что на этот же интервал времени Δt попадает ровно одно событие P = 1 (t, Δt). 38 Ординарность потока событий означает, что события в потоке приходят поодиночке, а не парами, тройками и т. д. Например, поток клиентов, направляющихся в парикмахерскую, практически можно считать ординарным, чего нельзя сказать о потоке клиентов, направляющихся в ЗАГС для регистрации брака, и т. д. Рассматривая ординарный поток событий, найдем среднее число событий, наступающих на интервале времени Δt, примыкающем к моменту времени t. Пусть Pi (t, Δt) - вероятность того, что на промежутке времени Δt , примыкающем к моменту времени t, произойдет i событий. Тогда для малого Δt получаем: 0*P0(t, Δt) + 1*P1(t, Δt) = P1(t, Δt) . Среднее число событий в единицу времени расчитывается следующим образом: lim(Δt -> 0) (P1(t, Δt) / Δt) , если этот предел существует, он называется интенсивностью (плотностью) потока событий. Если для любого интервала Δt событие P0(t0, Δt) + P1(t1, Δt) + Р1(t, t)=1, то P1(t, t) - вероятность попадания на интервал t ровно одного события. Как сумма вероятностей событий, образующих полную группу и несовместных, то для ординарного потока событий P0(t, t) + P1(t, t)  1, Р1(t, t)=(t), где (t)- величина, порядок малости которой выше, чем t, т.е. lim((t))=0 при t0. Стационарным ПС называется поток, для которого вероятность появления того или иного числа событий на интервале времени Δt зависит от длины этого участка и не зависит от того, где на оси времени от 0 до t взят этот участок. Применительно к элементарному каналу обслуживания ki можно считать что поток заявок wi∈W, т.е. интервалы времени между моментами появления заявок на входе ki , образует подмножество неуправляемых переменных, а поток обслуживания ui∈U, т.е. интервалы времени между началом и окончанием обслуживания заявки, образует подмножество управляемых переменных. 39 Заявки, обслуженные каналом ki и заявки, покинувшие прибор Пi не обслуженными по тем или иным причинам (например, из-за переполнения накопителя), образуют выходной поток yi ∈Y. Процесс функционирования прибора обслуживания Пi можно представить как процесс изменения состояний его элементов во времени Zi(t). Переход в новое состояние для Пi означает изменение количества заявок, которые в нём находятся (в канале ki и накопителе Hi). Таким образом, вектор состояний для Пi имеет вид: zi = (ziH , ziK) , где ziH - состояние накопителя Hi, (ziH=0 - накопитель пуст, ziH=1 – в накопителе имеется одна заявка, ..., ziH=JiH –накопитель полностью заполнен); JiH – емкость накопителя Нi, измеряемая числом заявок, которые в нем могут поместиться; zik – состояние канала Ki (zik=0 – канал свободен, zik = 1 – канал занят). Разновидности Q-схем В практике моделирования систем, имеющих более сложные структурные связи и алгоритмы поведения, для формализации используются не отдельные приборы обслуживания, а Q-схемы, образуемые композицией многих элементарных приборов обслуживания Пi. Если ki различных приборов обслуживания соединены параллельно, то имеет место многоканальное обслуживание (многоканальная Q-схема), а если приборы Пi и их параллельные композиции соединены последовательно, то имеет место многофазное обслуживание (многофазная Q-схема). Таким образом, для задания Q-схемы необходим оператор сопряжения R, отражающий взаимосвязь элементов структуры. Связи в Q-схеме изображают в виде стрелок (линий потока, отражающих направление движения заявок). 40 Различают Q-схемы: Разомкнутые, характерищующиеся тем, что выходной поток не может снова поступить на какой-либо элемент, т.е. обратная связь отсутствует. Замкнутые, характеризующиеся наличием обратных связей, по которым заявки двигаются в направлении, обратном движению входвыход. Собственными (внутренними) параметрами Q-схемы являются количество фаз LФ, количество каналов в каждой фазе LjK, количество накопителей каждой фазы LjH, ( где j=1… LФ и K=1… LФ,), ёмкость i-ого накопителя j-ой фазы LijH. Следует отметить, что в теории массового обслуживания в зависимости от ёмкости накопителя применяют следующую терминологию: системы с потерями (LiH= 0, накопитель отсутствует); системы с ожиданием (LiH ∈ N, емкость накопителя не ограничена, т.е. являет собой всё множество натуральных чисел); смешанные системы (LiH ограничена). = Нi , емкость накопителя Для задания Q-схемы необходимо описать множество ее внутренних параметров H, а также алгоритмы (дисциплины) её функционирования, которые определяют правила поведения заявок в различных неоднозначных ситуациях. В зависимости от места возникновения таких ситуаций различают алгоритмы:  ожидания заявок в накопителе Нi ,  обслуживания заявок каналом Ki. Приоритеты заявок Неоднородность потока заявок введения класса приоритетов. учитывается с помощью В зависимости от динамики приоритетов Q-схемы различают: 41 Статические, когда приоритеты назначаются заранее и не зависят от состояний Q-схемы, т.е. они являются фиксированными в пределах решения конкретной задачи моделирования. Динамические приоритеты - возникают непосредственно при моделировании. Исходя из правил выбора заявок из накопителя Нi на обслуживание каналом ki можно выделить: Относительные приоритеты. Это означает, что заявка с более высоким приоритетом, поступившая в накопитель Нi, ожидает окончания обслуживания заявки, уже находящейся в канале обслуживания ki , и только после этого занимает канал. Абсолютные приоритеты. Это значит, что заявка с более высоким приоритетом, поступившая в накопитель, прерывает обслуживание каналом ki заявки с более низким приоритетом и сама занимает канал (при этом вытесненная из ki заявка может либо покинуть систему, либо быть снова записана на какое-то место в Нi). Правила поведения заявок в системе Необходимо также знать набор правил, по которым заявки покидают накопитель Нi и канал обслуживания ki. Для Нi существуют правила переполнения и ухода, связанные с истечением времени ожидания заявки в Нi. Для ki – правила выбора маршрутов или направлений ухода. Кроме того, для заявок необходимо задать правила, по которым они остаются в канале ki, т.е. правила блокировок канала. При этом различают блокировки ki по выходу и по входу. Такие блокировки отражают наличие управляющих связей в Q-схеме, регулирующих поток заявок в зависимости от состояний Q-схемы. Набор возможных алгоритмов поведения заявок в Q-схеме можно представить в виде некоторого оператора алгоритмов поведения заявок А. Таким образом, Q-схема, описывающая процесс функционирования СМО любой сложности однозначно задаётся в виде набора множеств: Q = . 42 W – множество входящих потоков; U – множество потоков обслуживания; Y – множество выходных потоков; Н – множество собственных параметров системы; Z – множество состояний системы; R – оператор сопряжения элементов в системе; А – оператор алгоритмов обслуживания заявок. ТЕМЫ ДОКЛАДОВ 1. Одноканальная СМО с отказами. Многоканальная СМО с отказами. 2. Одноканальная СМО с ожиданием и ограничением на длину очереди. Многоканальная СМО с ожиданием и ограничением на длину очереди. 3. Одноканальная СМО с ожиданием, Многоканальная СМО с ожиданием. Многоканальная СМО без ограничения на длину очереди, но с ограничением на время ожидания. 4. Замкнутая одноканальная СМО. Замкнутая многоканальная СМО. 5. Многоканальная СМО с отказами и взаимопомощью между каналами типа "все как один". Многоканальная СМО с ожиданием, ограничением на длину очереди и взаимопомощью между каналами типа "все как один". Многоканальная СМО с ожиданием и взаимопомощью между каналами типа "все как один" 6. Многоканальная СМО с отказами и "равномерной" взаимопомощью между каналами. Многоканальная СМО с ожиданием, ограничением на длину очереди и "равномерной" взаимопомощью между каналами. Многоканальная СМО с ожиданием и "равномерной" взаимопомощью между каналами. 43 7. ДИСКРЕТНО-СТОХАСТИЧЕСКИЕ МОДЕЛИ (P-СХЕМЫ) Рассмотрим особенности построения математических схем при дискретно-стохастическом подходе к формализации процесса функционирования исследуемой системы S. Так как сущность дискретизации времени при этом подходе остается аналогичной рассмотренным конечным автоматам, то влияние фактора стохастичности проследим также на разновидности таких автоматов, а именно на вероятностных (стохастических) автоматах. В общем виде вероятностный автомат можно определить как дискретный потактный преобразователь информации с памятью, функционирование которого в каждом такте зависит только от состояния памяти в нем и может быть описано статистически. Применение схем вероятностных автоматов (Р-схем) имеет важное значение для :  разработки методов проектирования дискретных систем, проявляющих статистически закономерное случайное поведение;  для выяснения алгоритмических возможностей таких систем и обоснования границ целесообразности их использования;  для решения задач синтеза по выбранному критерию дискретных стохастических систем, удовлетворяющих заданным ограничениям. Введем математическое понятие Р-автомата, используя понятия, введенные для F-автомата. Рассмотрим множество G, элементами которого являются всевозможные пары (xj, zs), где xj и zs – элементы входного подмножества X и подмножества состояний Z соответственно. Если существуют две такие функции  и  , то с их  Z и G  Y , то говорят, помощью осуществляются отображения G  что F ( Z , X ,Y , , ) определяет автомат детерминированного типа. Введем в рассмотрение более общую математическую схему. Пусть Ф – множество любых пар вида (zk, yj), где yj – элемент выходного подмножества Y. Потребуем, чтобы любой элемент 44 множества G индуцировал (способствовал появлению) на множестве Ф некоторый закон распределения следующего вида: Таблица 7.1. Элементы Ф (z1, y1) (z1, y2) … (zk, yj-1) (zk, yj) (xj, zk) b11 b12 … bK(j-1) bKj При этом: K J  b kj  1, (7.1) k 1 j 1 где bKj – вероятности автомата в состоянии zk и появлении на выходе сигнала yj, если он был в состоянии zs и на его выход в этот момент времени поступил сигнал xi. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G. Обозначим множество этих таблиц через В. Тогда четверка элементов F(Z,X,Y,B) называется вероятностным автоматом (Pавтоматом). Частным случаем Р-автомата являются автоматы, у которых либо переход в новое состояние, либо выходной сигнал определяются детерминировано. Если выходной сигнал Р-автомата определяется детерминировано, то такой автомат называется Yдетерминированным вероятностным автоматом. Если выбор нового состояния является детерминированным, то автомат называется Z-детерминированным вероятностным автоматом. Для оценки различных характеристик исследуемых систем, представляемых в виде Р-схем, наряду с аналитическими моделями можно применять и имитационные модели, реализуемые, например, методом статистического моделирования. 45 ТЕМЫ ДОКЛАДОВ 1. Вероятностные автоматов. автоматы. Редукция вероятностных 2. Вероятностные автоматы. Вероятностные реакции. 3. Вероятностные автоматы. Вероятностные автоматы Мура с числовым выходом. 4. Вероятностные автоматы. Вероятностные языки. 46 8. СЕТИ ПЕТРИ Сети Петри – математический аппарат для моделирования динамических дискретных систем. Впервые описаны Карлом Петри в 1962 году. Сеть Петри представляет собой двудольный ориентированный граф, состоящий из вершин двух типов – позиций и переходов, соединённых между собой дугами. Вершины одного типа не могут быть соединены непосредственно (т.е. не могут быть соединены две позиции или два перехода друг с другом). В позициях могут размещаться метки (маркеры), способные перемещаться по сети. Событием называют срабатывание перехода, при котором метки из входных позиций этого перехода перемещаются в выходные позиции. События происходят мгновенно, либо разновременно, при выполнении некоторых условий. При этом срабатывание перехода вызывает некоторую задержку, которая определяется или задается разными способами. Некоторые виды сетей Петри: Временная сеть Петри – переходы обладают весом, определяющим продолжительность срабатывания (задержку). Стохастическая сеть Петри – задержки являются случайными величинами. Функциональная сеть Петри – задержки определяются как функции некоторых аргументов, например, количества меток в каких-либо позициях, состояния некоторых переходов. Цветная сеть Петри – метки могут быть различных типов, обозначаемых цветами, тип метки может быть использован как аргумент в функциональных сетях. Понятие цветности в этих сетях тесно связано с понятиями переменных, типов данных, условий и других конструкций, более приближенных к языкам программирования. Однако несмотря на некоторые сходства между цветными сетями Петри и программами, они еще не применялись в качестве языка программирования. 47 Ингибиторная сеть Петри – возможны ингибиторные (дословно «замедляющие») дуги, запрещающие срабатывания перехода, если во входной позиции, связанной с переходом ингибиторной дугой, находится метка. Иерархическая сеть – содержит не мгновенные переходы, в которые вложены другие, возможно, также иерархические, сети. Срабатывание такого перехода характеризует выполнение полного жизненного цикла вложенной сети. WF-сети – подкласс сетей Петри, называемый также сетями потоков работ. Формализм WF-сетей введён Вил ван дер Аальстом (англ. Wil van der Aalst) для моделирования потоков работ в workflow-системах. Сеть Петри PN = (P,T,F) называется сетью потоков работ (WF-сетью), если выполняются следующие условия: 1. существует только одна исходная позиция i, такая что отсутствуют переходы входящие в i; 2. существует только одна конечная позиция o, такая что отсутствуют переходы выходящие из o; 3. каждый узел данной сети расположен на пути от i к о. Развитие теории направлениям: сетей Петри проводилось по двум Формальная теория сетей Петри – занимается разработкой основных средств, методов и понятий, необходимых для применения сетей Петри. Прикладная теория сетей Петри – связана главным образом с применением сетей Петри к моделированию систем, их анализу и получающимся в результате этого глубоким проникновением в моделируемые системы. Моделирование в сетях Петри осуществляется на событийном уровне. Определяются, какие действия происходят в системе, какие состояния предшествовали этим действиям и какие состояния примет система после выполнения действия. Выполнение событийной модели в сетях Петри описывает поведение системы. Анализ результатов выполнения может сказать 48 о том, в каких состояниях пребывала или не пребывала система, какие состояния в принципе не достижимы. Однако такой анализ не дает числовых характеристик, определяющих состояние системы. Не смотря на описанные выше достоинства сетей Петри, неудобства применения сетей Петри в качестве языка программирования заключены в процессе их выполнения в вычислительной системе. В сетях Петри нет строго понятия процесса, который можно было бы выполнять на указанном процессоре. Нет также однозначной последовательности исполнения сети Петри, так как исходная теория представляет нам язык для описания параллельных процессов. Рис. 8.1. Фрагмент сети Петри Если задержки являются случайными величинами, то сеть называют стохастической сетью Петри. В таких сетях возможно введение вероятностей срабатывания возбужденных переходов. Так, на рис. 8.2 представлен фрагмент сети Петри, иллюстрирующий конфликтную ситуацию – маркер в позиции p2 может запустить либо переход t1, либо переход t2. В таких ситуациях в стохастической сети предусматривается вероятностный выбор срабатывающего перехода. Рис. 8.2. Конфликтная ситуация Пример: Требуется описать с помощью сети Петри процессы возникновения и устранения неисправностей в некоторой технической системе, состоящей из множества однотипных блоков; в 49 запасе имеется один исправный блок; известны статистические данные об интенсивностях возникновения отказов и длительностях таких операций, как поиск неисправностей, замена и ремонт отказавшего блока. Поиск и замену отказавшего блока производит одна бригада, а ремонт замененного блока – другая бригада. Отметим, что при числе меток в позиции, равном M, можно в ней не ставить M точек, а записать в позиции значение M. В нашем примере (см. рис. 8.3) значение M в позиции p2 соответствует числу имеющихся в системе блоков. Переходы отображают следующие события: t1 – отказ блока, t2– поиск неисправного блока, t3– его замена, t4– окончание ремонта. Рис. 8.3. Сеть Петри для примера технической системы. Очевидно, что при непустой позиции p2 переход t1 срабатывает, но с задержкой, равной вычисленному случайному значению моделируемого отрезка времени между отказами. После выхода маркера из t1 он попадает через p1 в t2, если имеется метка в позиции p6, это означает, что обслуживающая систему бригада специалистов свободна и может приступить к поиску возникшей неисправности. В переходе t2 метка задерживается на время, равное случайному значению длительности поиска неисправности. Далее маркер оказывается в p3 и, если имеется запасной блок (маркер в p4), то запускается переход t3, из которого маркеры выйдут в p2, p5 и в p6 через отрезок времени, требуемый для замены блока. После этого в t4 имитируется восстановление неисправного блока. 50 ТЕМЫ ДОКЛАДОВ 1. Временная сеть Петри. Области применения. Примеры. 2. Стохастическая Примеры. 3. Функциональная Примеры. сеть сеть Петри. Области применения. Петри. Области применения. 4. Цветная сеть Петри. Области применения. Примеры. 5. Ингибиторная сеть Петри. Области применения. Примеры. 6. Иерархическая . Области применения. Примеры. 7. WF-сети. Области применения. Примеры. 51 9. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ Генетические алгоритмы (ГА) - адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и принципу "выживает наиболее приспособленный" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны "развивать" решения реальных задач, если те соответствующим образом закодированы. ГА могут использоваться, например, чтобы:  проектировать структуры моста, для поиска максимального отношения прочности/веса,  определять наименее расточительное размещение для нарезки форм из ткани,  интерактивно управлять химическом заводе,  сбалансировать компьютере. загрузки процессом, на например на многопроцессорном Вполне реальный пример: израильская компания Schema разработала программный продукт Channeling для оптимизации работы сотовой связи путем выбора оптимальной частоты, на которой будет вестись разговор. В основе этого программного продукта и используются генетические алгоритмы. Основные принципы ГА были сформулированы Голландом (Holland, 1975) и хорошо описаны во многих работах. В отличие от эволюции, происходящей в природе, ГА только моделируют те процессы в популяциях, которые являются существенными для развития. Точный ответ на вопрос: какие биологические процессы существенны для развития, и какие нет? - все еще открыт для исследователей. 52 В природе особи в популяции конкурируют друг с другом за различные ресурсы, такие, например, как пища или вода. Кроме того, члены популяции одного вида часто конкурируют за привлечение брачного партнера. И наиболее приспособленные к окружающим условиям особи будут иметь относительно больше шансов воспроизведения потомков. А слабо приспособленные особи либо совсем не произведут потомства, либо их потомство будет очень немногочисленным. Это означает, что гены от высоко адаптированных или приспособленных особей будут распространятся в увеличивающемся количестве потомков на каждом последующем поколении. Комбинация хороших характеристик от различных родителей иногда может приводить к появлению "суперприспособленного" потомка, чья приспособленность больше, чем приспособленность любого из его родителя. Таким образом, вид развивается, лучше и лучше приспосабливаясь к среде обитания. ГА используют прямую аналогию с таким механизмом. Они работают с совокупностью "особей" – популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. Например, мерой приспособленности могло бы быть отношение силы/веса для данного проекта моста. (В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы.) Наиболее приспособленные особи получают возможность "воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Так и воспроизводится вся новая популяция допустимых решений, выбирая лучших представителей предыдущего поколения, скрещивая их и получая множество новых особей. Это новое поколение содержит более высокое соотношение характеристик, которыми обладают хорошие члены предыдущего поколения. Таким образом, из поколения в поколение, хорошие характеристики 53 распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге, популяция будет сходиться к оптимальному решению задачи. Хотя модель эволюционного развития, применяемая в ГА, сильно упрощена по сравнению со своим природным аналогом, тем не менее ГА является достаточно мощным средством и может с успехом применяться для широкого класса прикладных задач, включая те, которые трудно, а иногда и вовсе невозможно, решить другими методам. Однако, ГА, как и другие методы эволюционных вычислений, не гарантирует обнаружения глобального решения за полиномиальное время. ГА не гарантируют и того, что глобальное решение будет найдено, но они хороши для поиска "достаточно хорошего" решения задачи "достаточно быстро". Там, где задача может быть решена специальными методам, почти всегда такие методы будут эффективнее ГА и в быстродействии и в точности найденных решений. Главным же преимуществом ГА является то, что они могут применяться даже на сложных задачах, там, где не существует никаких специальных методов. Даже там, где хорошо работают существующие методики, можно достигнуть улучшения сочетанием их с ГА. Пример ГА: Решение Диофантова уравнения. Рассмотрим диофантово (только целые решения) уравнение: a+2b+3c+4d=30, где a, b, c и d - некоторые положительные целые. Применение ГА за очень короткое время находит искомое решение (a, b, c, d). Архитектура ГА-систем позволяет найти решение быстрее за счет более 'осмысленного' перебора. Мы не перебираем все подряд, но приближаемся от случайно выбранных решений к лучшим. Для начала выберем 5 случайных решений: 1 ≤ a,b,c,d ≤ 30. Вообще говоря, мы можем использовать меньшее ограничение для b,c,d, но для упрощения пусть будет 30. 54 Таблица 9.1. 1-е поколение хромосом и их содержимое. Хромосома 1 2 3 4 5 (a,b,c,d) (1,28,15,3) (14,9,2,4) (13,5,7,3) (23,8,16,19) (9,13,5,2) Чтобы вычислить коэффициенты выживаемости, подставим каждое решение в выражение a+2b+3c+4d. Расстояние от полученного значения до 30 и будет нужным значением. Таблица 9.2. Коэффициенты выживаемости первого поколения хромосом (набора решений). Хромосома Коэффициент выживаемости 1 |114-30|=84 2 |54-30|=24 3 |56-30|=26 4 |163-30|=133 5 |58-30|=28 Так как меньшие значения ближе к 30, то они более желательны. В нашем случае большие численные значения коэффициентов выживаемости подходят, увы, меньше. Чтобы создать систему, где хромосомы с более подходящими значениями имеют большие шансы оказаться родителями, мы должны вычислить, с какой вероятностью (в %) может быть выбрана каждая. Одно решение заключается в том, чтобы взять сумму обратных значений коэффициентов, и, исходя из этого, вычислять проценты. (Заметим, что все решения были сгенерированы Генератором Случайных Чисел). 55 Таблица 9.3. Вероятность оказаться родителем. Хромосома 1 2 3 4 5 Оптимальность (1/84)/0.135266 = 8.80% (1/24)/0.135266 = 30.8% (1/26)/0.135266 = 28.4% (1/133)/0.135266 = 5.56% (1/28)/0.135266 = 26.4% Для выбора 5-ти пар родителей (каждая из которых будет иметь 1 потомка, всего - 5 новых решений), представим, что у нас есть 10000-сторонняя игральная кость, на 880 сторонах отмечена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома 4 и на 2640 сторонах отмечена хромосома 5. Чтобы выбрать первую пару кидаем кость два раза и выбираем выпавшие хромосомы. Таким же образом выбирая остальных, получаем: Таблица 9.4. Симуляция выбора родителей. Хромосома отца Хромосома матери 3 1 5 2 3 5 2 5 5 3 Каждый потомок содержит информацию о генах и отца и от матери. Вообще говоря, это можно обеспечить различными способами, однако в нашем случае можно использовать так называемый "кроссовер" (cross-over). Пусть мать содержит следующий набор решений: a1,b1,c1,d1, а отец - a2,b2,c2,d2, тогда возможно 6 различных кроссоверов (| = разделительная линия): Таблица 9.5. Кросс-оверы между родителями. Хромосома-отец Хромосома-мать Хромосома-потомок a1 | b1,c1,d1 a2 | b2,c2,d2 a1,b2,c2,d2 or a2,b1,c1,d1 a1,b1 | c1,d1 a2,b2 | c2,d2 a1,b1,c2,d2 or a2,b2,c1,d1 a1,b1,c1 | d1 a2,b2,c2 | d2 a1,b1,c1,d2 or a2,b2,c2,d1 56 Есть достаточно много путей передачи информации потомку, и кроссовер - только один из них. Расположение разделителя может быть абсолютно произвольным, как и то, что отец или мать будут слева от черты. А теперь попробуем проделать это с нашими потомками. Таблица 9.6. Симуляция кроссоверов хромосом родителей. Хромосома-отец Хромосома-мать Хромосома-потомок (13 | 5,7,3) (1 | 28,15,3) (13,28,15,3) (9,13 | 5,2) (14,9 | 2,4) (9,13,2,4) (13,5,7 | 3) (9,13,5 | 2) (13,5,7,2) (14 | 9,2,4) (9 | 13,5,2) (14,13,5,2) (13,5 | 7, 3) (9,13 | 5, 2) (13,5,5,2) Теперь мы можем вычислить коэффициенты выживаемости (фитнес, fitness) потомков. Таблица 9.7. Коэффициенты выживаемости потомков (fitness). Хромосома-потомок (13,28,15,3) (9,13,2,4) (13,5,7,2) (14,13,5,2) (13,5,5,2) Коэффициент выживаемости |126-30|=96 |57-30|=27 |57-30|=22 |63-30|=33 |46-30|=16 Средняя приспособленность (fitness) потомков оказалась 38.8, в то время как у родителей этот коэффициент равнялся 59.4. Следующее поколение может мутировать. Например, мы можем заменить одно из значений какой-нибудь хромосомы на случайное целое от 1 до 30. Продолжая таким образом, одна хромосома в конце концов достигнет коэффициента выживаемости 0, то есть станет решением. Системы с большей популяцией (например, 50 вместо 5-ти) сходятся к желаемому уровню (0) более быстро и стабильно. 57 ТЕМЫ ДОКЛАДОВ 1. Генетические алгоритмы. Модель «Genitor» (автор D. Whitley). 2. Генетические алгоритмы. Модель «CHC» (автор Larry J. Eshelman) 3. Генетические алгоритмы. «Островная модель» (авторы W. N. Martin, J. Lienig, J. P. Cohoon) 4. Генетические алгоритмы. Модель «Cellular Genetic Algorithms» (авторы A. J. Nebro, J. J. Durillo, F. Luna, B. Dorronsoro, E. Alba) 58 10. ИСКУССТВЕННЫЕ НЕЙРОННЫЕ СЕТИ Искусственные нейронные сети (ИНС) – математические модели, а также их программные или аппаратные реализации, построенные по принципу организации и функционирования биологических нейронных сетей – сетей нервных клеток живого организма. Это понятие возникло при изучении процессов, протекающих в мозге, и при попытке смоделировать эти процессы. ИНС представляют собой систему соединённых и взаимодействующих между собой простых процессоров (искусственных нейронов). Такие процессоры обычно довольно просты, особенно в сравнении с процессорами, используемыми в персональных компьютерах. Каждый процессор подобной сети имеет дело только с сигналами, которые он периодически получает, и сигналами, которые он периодически посылает другим процессорам. Тем не менее, будучи соединёнными в достаточно большую сеть с управляемым взаимодействием, такие локально простые процессоры вместе способны выполнять довольно сложные задачи. С точки зрения машинного обучения, нейронная сеть представляет собой частный случай методов распознавания образов, дискриминантного анализа, методов кластеризации и т. п. С математической точки зрения, обучение нейронных сетей – это многопараметрическая задача нелинейной оптимизации. С точки зрения кибернетики, нейронная сеть используется в задачах адаптивного управления и как алгоритмы для робототехники. С точки зрения развития вычислительной техники и программирования, нейронная сеть – способ решения проблемы эффективного параллелизма. А с точки зрения искусственного интеллекта, ИНС является основой философского течения коннективизма и основным направлением в структурном подходе по изучению возможности построения (моделирования) естественного интеллекта с помощью компьютерных алгоритмов. Нейронные сети не программируются в привычном смысле этого слова, они обучаются. Возможность обучения – одно из главных преимуществ нейронных сетей перед традиционными алгоритмами. Технически обучение заключается в нахождении коэффициентов связей между нейронами, при которых ИНС выдавала бы ответы с некоторой приемлемой точностью (доля 59 ошибочных ответов ИНС менее заданного порога). Искомые коэффициенты связей представляют собой некоторое локальное решение, не гарантирующее самых лучших результатов работы ИНС для всех возможных входных параметров, а только удовлетворяющее заданной точности работы. В процессе обучения нейронная сеть способна выявлять сложные зависимости между входными данными и выходными, а также выполнять обобщение. Это значит, что в случае успешного обучения сеть сможет вернуть верный результат на основании данных, которые отсутствовали в обучающей выборке, а также неполных и/или «зашумленных», частично искаженных данных. Таблица 10.1. Машина фон Неймана по сравнению с биологической нейронной системой. Процессор Память Машина фон Неймана Биологическая нейронная система Сложный Простой Высокоскоростной Низкоскоростной Один или несколько Большое количество Отделена от процессора Интегрирована процессор Локализована Адресация содержанию Вычисления Надежность Специализация в Распределенная не по Адресация содержанию Централизованные Распределенные Последовательные Параллельные Хранимые программы Самообучение Высокая уязвимость Живучесть по Численные и символьные Проблемы восприятия oперации 60 Среда Строго определенная функционирования Строго ограниченная Плохо определенная Без ограничений Биологические нейронные сети. Нейрон (нервная клетка) является особой биологической клеткой, которая обрабатывает информацию (рис. 10.1). Она состоит из тела клетки (cell body), или сомы (soma), и двух типов внешних древоподобных ветвей: аксона (axon) и дендритов (dendrites). Тело клетки включает ядро (nucleus), которое содержит информацию о наследственных свойствах, и плазму, обладающую молекулярными средствами для производства необходимых нейрону материалов. Нейрон получает сигналы (импульсы) от других нейронов через дендриты (приемники) и передает сигналы, сгенерированные телом клетки, вдоль аксона (передатчик), который в конце разветвляется на волокна (strands). На окончаниях этих волокон находятся синапсы (synapses). Рис. 10.1. Биологическая модель нейрона. Синапс является элементарной структурой и функциональным узлом между двумя нейронами (волокно аксона одного нейрона и дендрит другого). Когда импульс достигает синаптического окончания, высвобождаются определенные химические вещества, называемые нейротрансмиттерами. Нейротрансмиттеры диффундируют через синаптическую щель, возбуждая или затормаживая, в зависимости от типа синапса, способность нейронаприемника генерировать электрические импульсы. Результативность синапса может настраиваться проходящими через него сигналами, так что синапсы могут обучаться в зависимости от активности 61 процессов, в которых они участвуют. Эта зависимость от предыстории действует как память, которая, возможно, ответственна за память человека. Необходимо заметить, что первые формализованные описания неройнной сети появились в 1943 г. в работах У. Маккалока и У. Питтса. Это формализованное описание легло в дальнейшем во все модели нейронных сетей. Вместе с тем, в этом описании не учитываются некоторые специфичные для мозга особенности биологических нейронных сетей. Не учитываются влияние химической среды вокруг нейронов, влияние клеток глии и пространственной удаленности нейронов друг от друга. Модель представляется в виде сложной функции, принимающей на вход ряд параметров (входной сигнал) и генерирующей ответ (выходной сигнал). В дальнейшем многими авторами высказывались идеи пересмотра формализованного описания нейронных сетей, но основная идея остается прежней. Архитектура нейронной сети. ИНС может рассматриваться как направленный граф со взвешенными связями, в котором искусственные нейроны являются узлами. По архитектуре связей ИНС могут быть сгруппированы в два класса (рис. 10.2): сети прямого распространения, в которых графы не имеют петель, и рекуррентные сети, или сети с обратными связями. Рис. 10.2. Систематизация архитектур сетей прямого распространения и рекуррентных (с обратной связью). В наиболее распространенном семействе сетей первого класса, называемых многослойным перцептроном, нейроны расположены 62 слоями и имеют однонаправленные связи между слоями. На рис. 10.2 представлены типовые сети каждого класса. Сети прямого распространения являются статическими в том смысле, что на заданный вход они вырабатывают одну совокупность выходных значений, не зависящих от предыдущего состояния сети. Рекуррентные сети являются динамическими, так как в силу обратных связей в них модифицируются входы нейронов, что приводит к изменению состояния сети. В Таблице 10.2 представлены различные алгоритмы обучения и связанные с ними архитектуры сетей (список не является исчерпывающим). В последней колонке перечислены задачи, для которых может быть применен каждый алгоритм. Каждый алгоритм обучения ориентирован на сеть определенной архитектуры и предназначен для ограниченного класса задач. 63 Таблица 10.2. Алгоритмы обучения. Обучающее Алгоритм Парадигма Архитектура Задача правило обучения С учителем Коррекция ошибки Однослойный и Алгоритмы Классификация многослойный обучения образов перцептрон перцептрона Аппроксимация Обратное функций распространение Предскащание, Adaline и управление Madaline Правило Рекуррентная Алгоритм Классификация Больцмана обучения образов Больцмана Правило Многослойная Линейный Анализ данных Хебба прямого дискриминантны Классификация распространения й анализ образов Соревнование Соревнование Векторное Категоризация квантование внутри класса Сжатие данных Классификация Сеть ART ARTMap образов Без учителя Коррекция Многослойная Проекция Категоризация ошибки прямого Саммона внутри класса распространения Анализ данных Правило Прямого Анализ главных Анализ данных Хебба распространения компонентов Сжатие данных или соревнование Сеть Хопфилда Обучение Ассоциативная ассоциативной память памяти Соревнование Соревнование Векторное Категоризация квантование Сжатие данных SOM Кохонена SOM Кохонена Категоризация Анализ данных Сети ART ART1, ART2 Категоризация Смешанная Коррекция Сеть RBF Алгоритм Классификация ошибки и обучения RBF образов соревнование Аппроксимация функций Предсказание, управление 64 Примеры приложений Предсказание финансовых временных рядов Входные данные – курс акций за год. Задача – определить завтрашний курс. Проводится следующее преобразование – выстраивается в ряд курс за сегодня, вчера, за позавчера. Следующий ряд – смещается по дате на один день и так далее. На полученном наборе обучается сеть с 3 входами и одним выходом – то есть выход: курс на дату, входы: курс на дату минус 1 день, минус 2 дня, минус 3 дня. Обученной сети подаем на вход курс за сегодня, вчера, позавчера и получаем ответ на завтра. Нетрудно заметить, что в этом случае сеть просто выведет зависимость одного параметра от трёх предыдущих. Если желательно учитывать ещё какой-то параметр (например, общий индекс по отрасли), то его надо добавить как вход (и включить в примеры), переобучить сеть и получить новые результаты. Для наиболее точного обучения стоит использовать метод ОРО, как наиболее предсказуемый и несложный в реализации. Психодиагностика Серия работ М. Г. Доррера с соавторами посвящена исследованию вопроса о возможности развития психологической интуиции у нейросетевых экспертных систем. Полученные результаты дают подход к раскрытию механизма интуиции нейронных сетей, проявляющейся при решении ими психодиагностических задач. Создан нестандартный для компьютерных методик интуитивный подход к психодиагностике, заключающийся в исключении построения описанной реальности. Он позволяет сократить и упростить работу над психодиагностическими методиками. Хемоинформатика Нейронные сети широко используются в химических и биохимических исследованиях. В настоящее время нейронные сети являются одним из самых распространенных методов хемоинформатики для поиска количественных соотношений структура-свойство, благодаря чему они активно используются как для прогнозирования физико-химических свойств и биологической 65 активности химических соединений, так и для направленного дизайна химических соединений и материалов с заранее заданными свойствами, в том числе при разработке новых лекарственных препаратов. Нейроуправление Нейронные сети успешно применяются для синтеза систем управления динамическими объектами. Нейросети обладают рядом уникальных свойств, которые делают их мощным инструментом для создания систем управления: способностью к обучению на примерах и обобщению данных, способностью адаптироваться к изменению свойств объекта управления и внешней среды, пригодностью для синтеза нелинейных регуляторов, высокой устойчивостью к повреждениям своих элементов в силу изначально заложенного в нейросетевую архитектуру параллелизма. Экономика Алгоритмы искусственных нейронных сетей нашли широкое применение в экономике. С помощью нейронных сетей решается задача разработки алгоритмов нахождения аналитического описания закономерностей функционирования экономических объектов (предприятие, отрасль, регион). Эти алгоритмы применяются к прогнозированию некоторых «выходных» показателей объектов. Применение нейросетевых методов позволяет решить некоторые проблемы экономико-статистического моделирования, повысить адекватность математических моделей, приблизить их к экономической реальности. Поскольку экономические, финансовые и социальные системы очень сложны и являются результатом действий и противодействий различных людей, то является очень сложным (если не невозможным) создать полную математическую модель с учётом всех возможных действий и противодействий. В системах подобной сложности является естественным и наиболее эффективным использовать модели, которые напрямую имитируют поведение общества и экономики. А это как раз то, что способна предложить методология нейронных сетей. 66 Электронные переводчики речи Автоматический, почти синхронный голосовой перевод с английского на путунхуа с задержкой в несколько секунд, в котором сам вариант на путунхуа звучал в вокальной манере оригинала, продемонстрировала Microsoft Research. Директор Microsoft по разработкам Рик Рашид провёл презентацию технологии в Тяньцзине 25 октября 2012г. Microsoft применила новую систему машинного обучения на основе искусственных нейронных сетей, которая сокращает непонимание до каждого седьмого−восьмого слова. Но самое большое достижение – это, конечно, генерация речи с сохранением модуляций голоса говорящего. Собеседникам будет легче друг друга понять, и тем самым общение станет эффективнее. Г-н Рашид битый час общался с машиной, прежде чем она усвоила все нюансы его разговорной манеры. ТЕМЫ ДОКЛАДОВ 1. Классификация по типу входной информации: Аналоговые нейронные сети, Двоичные нейронные сети. 2. Классификация по характеру обучения: Обучение с учителем, Обучение без учителя, Обучение с подкреплением. 3. Классификация по характеру настройки синапсов: Сети с фиксированными связями, Сети с динамическими связями. 4. Классификация по времени передачи сигнала 5. Искусственные нейронные сети в играх на примере Google AlphaGo. 6. Искусственные нейронные сети и принятие решений на примере IBM Watson. 67 11. СТАТИСТИЧЕСКОЕ МОДЕЛИРОВАНИЕ На этапе исследования и проектирования систем при построении и реализации машинных моделей широко используется метод статистических испытаний (Монте-Карло), который базируется на использовании случайных чисел, т.е. возможных значений некоторой случайной величины с заданным распределением вероятностей. Статистическое моделирование представляет собой метод получения с помощью ЭВМ статистических данных о процессах, происходящих в моделируемой системе. Для получения представляющих интерес оценок характеристик моделируемой системы, с учетом внешних воздействий внешней среды, статистические данные обрабатываются и классифицируются с использованием методов математической статистики. Таким образом, сущность метода статистического моделирования сводится к построению некоторого моделирующего алгоритма, имитирующего поведение и взаимодействие элементов системы с учетом случайных входных воздействий и воздействий внешней среды, и реализации этого алгоритма с использованием программно-технических средств ЭВМ. При статистическом моделировании систем одним из основных вопросов является учет стохастических воздействий. Количество случайных чисел, используемых для получения статистически устойчивой оценки характеристики процесса функционирования системы S, при реализации моделирующего алгоритма на ЭВМ, колеблется в остаточно широких пределах в зависимости от:  класса объекта моделирования;  вида оцениваемых характеристик;  необходимой точности моделирования. и достоверности результатов Результаты статистического моделирования существенно зависят от качества исходных (базовых) последовательностей случайных чисел. На практике используются три основных способа генерации случайных чисел:  аппаратный (физический); 68  табличный (файловый);  алгоритмический (программный). Аппаратный способ. Генерация случайных чисел обеспечивается специальной электронной приставкой-генератором (датчиком) случайных чисел, служащей в качестве одного из внешних устройств ЭВМ. Реализация этого способа генерации не требует дополнительных вычислительных операций ЭВМ по выработке случайных чисел, а необходима только операция обращения к внешнему устройству (датчику). В качестве физического эффекта, лежащего в основе таких генераторов чисел, чаще всего используются шумы в электронных и полупроводниковых приборах, явления распада радиоактивных элементов и т. д. Достоинства:  запас чисел не ограничен;  расходуется мало операций;  нe занимается место в памяти машины. Недостатки:  требуется периодическая проверка;  нельзя воспроизводить последовательности;  используется специальное устройство;  необходимы меры по обеспечению стабильности. Табличный способ. Случайные числа, представленные в виде таблицы, помещаются в память ЭВМ. Этот способ получения случайных чисел обычно используют при сравнительно небольшом объеме таблицы и файла чисел. Достоинства:  требуется однократная проверка;  можно воспроизводить последовательности. 69 Недостатки:  запас чисел ограничен;  много места в ОЗУ;  необходимо время для обращения к памяти. Алгоритмический способ. Способ получения последовательности случайных чисел основанный на формировании случайных чисел в ЭВМ с помощью специальных алгоритмов и реализующих их программ. Каждое случайное число вычисляется с помощью соответствующей программы по мере возникновения потребностей при моделировании системы на ЭВМ. Достоинства:  требуется однократная проверка;  многократная чисел; воспроизводимость последовательности  мало места в памяти и нет внешних устройств. Недостатки:  запас чисел ограничен периодом последовательности;  затраты машинного времени. Программная имитация случайных воздействий сводится к генерированию некоторых стандартных процессов и их последующего функционального преобразования. Псевдослучайные числа – это числа, полученные по какой-либо формуле и имитирующие значения случайной величины. Под словом «имитирующие» подразумевается, что эти числа удовлетворяют ряду тестов так, как если бы они были значениями случайной величины. Требования к генератору случайных чисел. Требованиями, к идеальному генератору случайных чисел формулируются следующим образом. Полученные с помощью идеального генератора псевдослучайные последовательности чисел должны:  состоять из квазиравномерно распределенных чисел; 70  содержать статистически независимые числа;  быть воспроизводимыми;  иметь неповторяющиеся числа;  получаться времени; с минимальными затратами машинного  занимать минимальный объем машинной памяти. В практике моделирования применяются последовательностей псевдослучайных чисел вида: xi 1  Ф( xi ) генерации (11.1) Данные алгоритмы представляют рекуррентные соотношения первого порядка, для которых начальное число x0 и постоянные параметры заданы. Рассмотрим некоторые процедуры получения последовательностей равномерно распределенных псевдослучайных чисел. Метод серединных квадратов Пусть имеется 2n-разрядное число, меньшее 1: xi  0, a1,..., a2n (11.2) 1. Возведем его в квадрат: xi2  0, b1,..., b4n (11.3) 2. Отберем средние 2n разрядов xi  0, bn 1,..., b2n которые будут являться очередным числом псевдослучайной последовательности. Недостаток метода: наличие корреляции между числами последовательности, в некоторых случаях может отсутствовать. Пример. Если начальное число х0=0,2152, то (х0)2=0,04631104. Тогда х1=0,6311, затем (х1)2=0,39828721, тогда х2=0,8287, и т. д. 71 Метод середины произведения Метод является модификацией метода серединных квадратов и состоит в том, что два 2n-значных числа перемножаются и средние 2n цифр этого произведения принимаются в качестве следующего числа последовательности. Таким образом, если xi 1  0, a1,..., a2n (11.4) xi  0, b1,..., b2n (11.5) то для получения числа хi+1 необходимо перемножить хi-1 и хi: xi 1  0, n~1,..., n~4n (11.6) Отберем средние 2n цифр этого произведения xi 1  0, n~11,..., n~3n (11.7) Несмотря на то, что данный метод имеет тенденцию к вырождению, он обеспечивает лучшее качество псевдослучайных чисел, чем у чисел, полученных с помощью метода серединных квадратов. Конгруэнтный метод Широкое применение для получения последовательностей псевдослучайных равномерно распределенных чисел получили конгруэнтные процедуры генерации, которые могут быть реализованы мультипликативным либо смешанным методом. Конгруэнтные процедуры являются чисто детерминированными, т.к. описываются в виде рекуррентного соотношения: xi 1  xi   (mod M ) где xi ,  ,  , M (11.8) - неотрицательные целые числа. Раскрывая соотношение (11.8) получим xi 1   ' x0  ( '1) /(  1)(mod M ) (11.9) Если задано начальное значение х0, множитель  и аддитивная константа  , то (11.9) однозначно определяет последовательность 72 целых чисел {хi}, составленную из остатков от деления на М, членов последовательности { ' x0  ( '1) /(  1)} (11.10) Мультипликативный метод Задает последовательность неотрицательных целых чисел {хi}, не превосходящих М, по формуле xi  xi 1 (mod M ), т.е. это частный случай (11.8) при  = 0. Пример. Если М=113, λ=101 и x0=50, то x0*= 50/113 = 0,4424, x1=101·50 (mod 113) = 78, x1*= 78/113 = 0,6902 и т.д. ТЕМЫ ДОКЛАДОВ 1. Генераторы псевдослучайных величин. Метод серединных квадратов. 2. Генераторы псевдослучайных Мультипликативный метод. величин. 3. Генераторы псевдослучайных величин. Метод Фибоначчи с запаздываниями. 4. Генераторы псевдослучайных величин. Вихрь Мерсенна. 5. Генераторы псевдослучайных Макларена-Марсальи. величин. Генератор 73 12. РАСПРЕДЕЛЕНИЯ СЛУЧАЙНЫХ ВЕЛИЧИН Биномиальное распределение (дискретное) X - количество «успехов» в последовательности из n независимых случайных экспериментов, таких что вероятность «успеха» в каждом из них равна p. q=1-p. Закон распределения Х имеет вид: xk 0 1 … k … n n n-1 k k n-k pk q n·p·q Cn ·p ·q pn Здесь вероятности находятся по формуле Бернулли: P(X=k)= Cnk·pk·(1-p)n-k= Cnk·pk·qn-k Характеристики: M(X)=np, D(X)=npq, σ=√npq. Примеры многоугольников распределения для n=5 и различных вероятностей: Рис. 12.1 Биномиальные распределения для n=5. Пуассоновское распределение (дискретное) Распределение Пуассона моделирует случайную величину, представляющую собой число событий, произошедших за фиксированное время, при условии, что данные события происходят с некоторой фиксированной средней интенсивностью и независимо друг от друга. 74 При условии p  0, n  , np    const закон распределения Пуассона является предельным случаем биномиального закона. Так как при этом вероятность p события A в каждом испытании мала, то закон распределения Пуассона называют часто законом редких явлений. Ряд распределения: xk 0 pk 1 … k … k e   e   …  e   … k! Вероятности вычисляются по формуле Пуассона: P( X  k )  k k! e  . Числовые характеристики: M(X)=λ, D(X)= λ, σ=√ λ Разные многоугольники распределения при λ =1;4;10. Рис. 12.1 Пуассоновские распределения. Показательное распределение (непрерывное) Экспоненциальное или показательное распределение – абсолютно непрерывное распределение, моделирующее время между двумя последовательными свершениями одного и того же события. Плотность распределения: 0, x  0 p( x )    x   e , x  x 75 где λ > 0. Числовые характеристики: M(X)=1/λ, D(X)=1/λ2, σ=1/λ Плотность распределения при различных значениях λ > 0. Рис. 12.3. Показательные распределения. Равномерное распределение (непрерывное) Равномерный закон распределения используется при анализе ошибок округления при проведении числовых расчётов (например, ошибка округления числа до целого распределена равномерно на отрезке [-0,5; 0,5]), в ряде задач массового обслуживания, при статистическом моделировании наблюдений, подчинённых заданному распределению. Плотность распределения: 0, x  a  1 p( x )   ,a  x  b b  a  0, x  b Числовые характеристики: M(X)=(a+b)/2, D(X)=((b-a)2)/12, σ=(b-a)/2√3 76 График плотности вероятностей: Рис. 12.4 Равномерное распределение. Нормальное (непрерывное) распределение или распределение Гаусса Нормальное распределение, также называемое распределением Гаусса – распределение вероятностей, которое играет важнейшую роль во многих областях знаний, особенно в физике. Физическая величина подчиняется нормальному распределению, когда она подвержена влиянию огромного числа случайных помех. Ясно, что такая ситуация крайне распространена, поэтому можно сказать, что из всех распределений в природе чаще всего встречается именно нормальное распределение – отсюда и произошло одно из его названий. Плотность распределения: f ( x)  1 ( x  a )2 exp(  )  2 2 2 Числовые характеристики: M(X)=a, D(X)= σ2, σ= σ 77 Пример плотности распределения: Рис. 12.5 Нормальные распределения. Нормальный закон распределения случайной величины с параметрами a=0 и σ=1 называется стандартным или нормированным, а соответствующая нормальная кривая - стандартной или нормированной. Функция Лапласа x 1 t 2 / 2 ( x)  e dt 2 0 Вероятность попадания нормально распределенной случайной величины X в заданный интервал (a;b) P(  X   )  (  a  a )  ( )   Вероятность отклонения нормально распределенной случайной величины X на величину δ от математического ожидания (по модулю).   P( X  a   )  2( ) 78 ТЕМЫ ДОКЛАДОВ 1. Вероятностные распределения. биномиальное распределение. Отрицательное 2. Вероятностные распределения. Гамма-распределение. 3. Вероятностные Колмогорова. распределения. Распределение 4. Вероятностные распределения. Распределение Парето. 5. Вероятностные распределения. Распределение Пирсона. 6. Вероятностные распределения. Распределение Стьюдента. 7. Вероятностные распределения. Распределение хи-квадрат. 79 8. 13. МОДЕЛИРОВАНИЕ ПРОГРАММИРОВАНИЯ СИСТЕМ И ЯЗЫКИ Большое значение при реализации модели на ЭВМ имеет вопрос правильного выбора языка программирования. Язык программирования должен отражать внутреннюю структуру понятий при описании широкого круга понятий. Высокий уровень языка моделирования значительно упрощает программирование моделей. Основными моментами при выборе ЯМ является:  проблемная ориентация;  возможности сбора, обработки, вывода результатов;  быстродействие;  простота отладки;  доступность восприятия. Этими свойствами обладают процедурные языки высокого уровня. Для моделирования могут быть использованы языки Имитационного моделирования (ЯИМ) и общего назначения (ЯОМ). Более удобными являются ЯИМ. Они обеспечивают:  удобство программирования модели системы;  проблемная ориентация. Недостатки ЯИМ:  неэффективность рабочих программ;  сложность отладки;  недостаток документации. Основные функции языка программирования: 80  управление процессами машинного времени); (согласование системного и  управление ресурсами (выбор и распределение ограниченных средств описываемой системы). Как специализированные языки, ЯИМ обладают некоторыми программными свойствами и понятиями, которые не встречаются в ЯОН. К ним относятся: Совмещение. Параллельно протекающие в реальных системах S процессы представляются с помощью последовательно работающей ЭВМ. ЯИМ позволяют обойти эту трудность путём введения понятий системного времени. Размер. ЯИМ используют динамическое распределение памяти (компоненты модели системы М появляются в ОЗУ и исчезают в зависимости от текущего состояния. Эффективность моделирования достигается так же использованием блочных конструкций: блоков, подблоков и т.д. Изменения. ЯИМ предусматривают обработку списков, отражающих изменения состояний процесса функционирования моделируемой системы на системном уровне. Взаимосвязь. Для отражения большого количества между компонентами модели в статике и динамике ЯИМ включаем системно организованные логические возможности и реализации теории множеств. Стохастичность. ЯИМ используют специальные программные генерации последовательностей случайных чисел, программы преобразования в соответствующие законы распределения. Анализ. ЯИМ предусматривают системные способы статистической обработки и анализа результатов моделирования. Наиболее известными языками SIMULA, SIMSCRIPT, GPSS, SOL, CSL. моделирования являются Для языков, используемых в задачах моделирования, можно составить классификацию следующего вида. (рис. 13.1) 81 Рис. 13.1 Классификация языков моделирования. Представление системы S в виде типовой схемы, в которой участвуют как дискретные, так и непрерывные величины, называются комбинированными. Предполагается, что в системе могут наступать события двух видов:  события, зависящие от состоянии Zi;  события, зависящие от времени t. При использовании языка GAPS на пользователь возлагается работа по составлению на языке FORTRAN подпрограмм, в которых описываются условия наступления событий, законы изменения непрерывной величины, правил перехода из одного состояния в другое. 82 SIMSCRIPT - язык событий, созданный на базе языка FORNRAN. Каждая модель Mj состоит из элементов, с которыми происходят события, представляющие собой последовательность формул, изменяющих состояние моделируемой системы с течением времени. Работа со списками, определяемые пользователем, последовательность событий в системном времени, работа с множествами. FORSIT - пакет ПП на языке FORNRAN позволяет оперировать только фиксированными массивами данных, описывающих объекты моделируемой системы. Удобен для описания систем с большим числом разнообразных ресурсов. Полное описание динамики модели можно получить с помощью ПП. SIMULA - расширение языка ALGOL. Блочное представление моделируемой системы. Функционирование процесса разбивается на этапы, происходящие в системном времени. Главная роль в языке SIMULA отводится понятию параллельного оперирования с процессами в системном времени, универсальной обработки списков с процессами в роли компонент. GPSS- интегрирующая языковая система, применяющаяся для описания пространственного движения объектов. Такие динамические объекты в языке GPSS называются транзактами и представляют собой элементы потока. Транзакты "создаются" и "уничтожаются". Функцию каждого из них можно представить как движение через модель М с поочерёдным воздействием на её блоки. Функциональный аппарат языка образуют блоки, описывающие логику модели, сообщая транзактам, куда двигаться и что делать дальше. Данные для ЭВМ подготавливаются в виде пакета управляющих и определяющих карт, которым составляется по схеме модели, набранной из стандартных символов. Созданная программа GPSS, работая в режиме интерпретации, генерирует и передаёт транзакты из блока в блок. Каждый переход транзакта приписывается к определенному моменту системного времени. ТЕМЫ ДОКЛАДОВ 1. Язык GAPS. История создания, области применения. 83 2. Язык SIMSCRIPT. История создания, области применения. 3. Язык FORSIT. История создания, области применения. 4. Язык SIMULA. История создания, области применения. 5. Язык GPSS. История создания, области применения. 84 14. ПЛАНИРОВАНИЕ МАШИННЫХ ЭКСПЕРИМЕНТОВ С МОДЕЛЯМИ СИСТЕМ Методы планирования эксперимента на модели. Основная задача планирования машинных экспериментов заключается в получении необходимой информации об исследуемой системе при ограниченных ресурсах (затраты машинного времени, памяти и т.п.). К числу частных задач, решаемых при планировании машинных экспериментов, относятся задачи уменьшения затрат машинного времени на моделирование, уменьшения погрешности результатов моделирования, проверки адекватности модели и т.п. Эффективность машинных экспериментов существенно зависит от выбора плана эксперимента, т.к. именно план определяет объём и порядок проведения вычислений на ЭВМ, приёмы накопления и статистической обработки результатов моделирования системы. Поэтому основная задача планирования машинных экспериментов с моделью формируется следующим образом: необходимо получить об объёме моделирования, заданном в виде моделирующего алгоритма (программы) при минимальных или ограниченных затратах машинных ресурсов на реализацию процесса моделирования. Таким образом, при машинном моделировании необходимо не только рационально планировать и проектировать саму модель системы, но и процесс её использования, т.е. проведения с ней эксперимента. При планировании машинных экспериментов возникает целый ряд проблем, взаимно связанных как с особенностью функционирования моделируемого объекта, так и с особенностью машинной реализации модели и обработки результатов эксперимента. В первую очередь к таким относятся проблемы построения плана машинного эксперимента, стохастической сходимости результатов, ограниченности машинных ресурсов, уменьшения дисперсии оценок, полученных на машинной модели и т.д. Рассмотрим основные понятия теории планирования эксперимента. В планировании эксперимента различают входные 85 (изогенные) и выходные (эндогенные) переменные: х1, х2,…, хк; y1, y2…, ye. Входные переменные в ТПЭ называют факторами а выходные – реакциями. Каждый фактор xi, i=1,2,…,k может принимать в эксперименте одно или несколько значений, называемых уровнями. Фиксированный набор уровней факторов определяет одно из возможных состояний рассматриваемой системы. Одновременно этот набор представляет собой условия проведения одного из возможных экспериментов. Каждому фиксированному набору уровню факторов соответствует определённая точка в многомерном пространстве, называемая факторным пространством. Эксперименты не могут быть реализованы во всех точках факторного пространства, а лишь в принадлежащих допустимой области, как это например оказано для случая двух факторов Х1 и Х2 на рисунке (рис. 14.1). Рис. 14.1 Геометрическое представление поверхности реакции. Реакцию (отклик) системы можно представить в виде зависимости: yl=l(x1, x2,…,xk); e=1…m. Функцию e, связанную с факторами, называют функцией отклика, а её геометрический образ – поверхностью отклика. Исследователь заранее не известен вид зависимостей l, l=1…m, поэтому используют приближение соотношения: ~yl  l (x1 , x2 ,..., xk ), l  1, m. 86 Зависимость и l находятся по данным эксперимента. Последний необходимо поставить так, чтобы при минимальных затратах ресурсов (числе испытаний), варьируя выходные значения по специально сформулированным правилам, построить математическую модель системы и оценить её характеристики. Факторы при проведении эксперимента могут быть управляемыми и неуправляемыми, количественными или качественными, фиксированными и случайными. Фактор относится к изучаемым, если он включён в модель для изучения свойств системы. Количественными факторами являются интенсивности входящих потоков заявок, интенсивности потоков обслуживания, ёмкости накопителей, количество обслуживающих каналов и другие. Качественным факторам не соответствует числовая шкала (дисциплины постановки на очередь, обслуживание каналов и другие). Фактор является управляемым, если его уровни целенаправленно выбираются экспериментатором. При планировании эксперимента обычно изменяются несколько факторов. Основными требованиями, предъявляемыми к факторам - независимость и совместимость. Совместимость означает, что все комбинации факторов осуществимы. Для выбора конкретной модели планирования эксперимента необходимо сформулировать такие её особенности, как адекватность, содержательность, простота. План эксперимента обычно используется для определения экстремальной характеристики объекта. Поэтому планирование эксперимента называется экстремальным. В планировании эксперимента наибольшее значение нашли модели в виде алгебраических полиномов. Предполагаем, что изучается влияние К количественных факторов хi на некоторую  в отведённый для экспериментирования локальной области факторного пространства ограниченного х i min–xi max, i=1…k. Функцию квадратичной. отклика обычно выбирают     b0  bi xi  bij xi x j  f ( x) B линейной или (14.1) 87    f ( x )  вектор  полином; B -  ( x ),   o,d ,  где с элементами f входящих в исходный вектор коэффициентов. Для двух факторов имеем: f0=1, f1=x1, f2=x2, f12=x1x2, f11=x12, f22=x22.  B  (b0,b1,b2,b12,b11,b22). Так как полином (14.1) содержит d коэффициентов, то план эксперимента должен содержать Nd различных экспериментальных точек:  x11  x D   12  ...   x1 N x x 21 22 ... x 2N x x   ... k2 ... ...   ... x kN  ... k1 (14.2) где xin - значение, которое принимает i-ая переменная в u-ом испытании. i=1…k, u=1...N. Матрица D называется планом эксперимента. Реализовав испытания в N очках области факторного пространства, определённом планом эксперимента, получим вектор наблюдений имеющий следующий вид: y   1 y  y   2  ...  y   N (14.3) где yu - реакция соответствующей u-ой точке плана. Плану эксперимента планирования:  f  01  f x   02  ...   f 0 N f f 11 12 ... f 1N поставим f f 21 22 ... f 2N в ... f f ... ... ... ... f 111 112 11 N соответствие f f    222  ...  f 22 N  матрицу 221 (14.4) где fil, fijl - координатные функции при соответствующих коэффициентах модели, в l - ом эксперименте. 88 Построению плана эксперимента предшествует проведение ряда неформализованных действий (принятия решения) направленных на выбор локальной области факторного пространства G. Необходимо учитывать, что как только модель сформирована включение дополнительных факторов для уточнения модели невозможно. Вначале следует выбрать границы xi min и xi max области определения факторов исходя из свойств объекта. Например, температура при термобарических экспериментах не может быть ниже абсолютного нуля и выше температуры плавления материала из которого изготовлена термобарокамера. После определения области G необходимо найти нулевые (основные) уровни факторов и интервалы варьирования xi, i=1…k. Эксперимент, в котором реализуются все возможные сочетания уровней факторов, называется полным факторным экспериментом (ПФЭ). Если выбранная модель включает только линейные члены полинома и их произведения, то для оценки коэффициентов модели используется ПЭ с варьированием всех k факторов на двух уровнях, т.е. q=2. Такие планы называются планы типа 2k, где n=2k- число всех возможных испытаний. Начальным этапом ПЭ для получения коэффициентов линейной модели основан на варьировании факторов на двух уровнях: нижнем xiн и верхнем xiв, симметрично расположенных относительно основного уровня xi0, i=1…k. Геометрическая интерпретация показана ниже на рис. 14.2: Рис. 14.2 ПЭФ типа 22. Для упрощения записи условий каждого эксперимента факторы кодируют в виде безразмерных величин 89 ~ x  (x  x уровень кодированного фактора является нулём 0, граничные значения соответственно +1 и -1. i i ) /  xi , i  1,2,..., k .Средний i0 Стратегическое планирование машинных экспериментов с моделями систем Можно выделить стратегическое и тактическое ПЭ на моделях систем. Стратегическое планирование – ставит своей целью получение необходимой информации о системе S с помощью модели MM, реализованной на ЭВМ. Оно аналогично внешнему проектированию при создании системы S. Тактическое планирование – определяет способы проведения каждой серии испытаний машинной модели MM. Оно аналогично внутреннему проектированию системы S. Рассмотрим элементы стратегического планирования ПЭ. Его целью может быть: Получение функции реакции системы от независимых фактов: y=f(b0,b1…,x1,x2,…xk) Нахождение экстремума: f(b0,b1…,x1,x2,…xk). Во 2-ом случае для определения наилучшей комбинации фактов могут быть использованы методы систематической или случайной выборки. К систематическим относятся методы:  одного фактора;  предельного анализа;  наискорейшего спуска;  равномерной сетки. Проблемой является большое количество факторов. Для k=10 ПЭФ должен состоять из 1024 точек. Используют неполные планы, метод "поверхности реакции". Следующей проблемой является многокомпонентность функции реакции. Здесь можно использовать последовательное однокомпонентное ПЭ. Этот подход не всегда возможен из-за 90 связанности компонентов. Используются интегральные оценки с применением весовых функций, функций полезности и т.д. Другой проблемой является стохастическая сходимость результатов ПЭ. В качестве результатов ПЭ используется средние некоторых распределений, для оценки которых применяют выборочные средние, найденные путём многократны прогонов модели на ЭВМ. Сходимость выборочных средних с ростом объема выборки называется стохастической. Эта сходимость, как правило, медленная. Если  - стандартное отклонение среднего N наблюдений будет равно / N , т.е. для уменьшения случайной выборки в k раз требуется увеличить объем выборки в k2 раз. Планирование машинного эксперимента представляет собой итерационный процесс, когда выбранная модель плана эксперимента проверяется на реализуемость, а затем, если это необходимо, вносят соответствующие коррективы в модель. Планирование эксперимента с моделью проводится в несколько этапов:  построение структурной модели;  построение функциональной модели. Структурная модель ПЭ характеризуется числом факторов и числом уровней для каждого фактора. Из опыта известно, что 20% факторов определяют 80% свойств системы. Ортогональное распределение плана упрощает определение коэффициентов аппроксимации. Упрощение дает принятие числа уровней всех факторов одинаковыми (не больше 3). Функциональная модель ПЭ определяет количество элементов структурной модели Nф, т.е. необходимое число различных информационных точек Nф. Причём Nф