Содержание к диссертации
Введение
Глава 1. Концепция алгоритмического моделирования на основе распределенных алгоритмических сетей 9
1.1. Алгоритмическое моделирование и текущее состояние теории алгоритмических сетей 9
1.2. Концептуальная модель процесса алгоритмического моделирования на основе распределенных алгоритмических сетей 21
1.3. Обсуждение и выводы по главе 1 25
Глава 2. Алгоритмические сети - формализм для описания структуры моделей сложных систем 27
2.1. Алгоритмические модели и алгоритмические сети, основные определения 27
2.2. Операции над алгоритмическими сетями и отношения на алгоритмических сетях 36
2.3. Вычисления на алгоритмических сетях 98
2.4. Обсуждение и выводы по главе 2 109
Глава 3. Преобразования алгоритмических моделей, описанных на основе алгоритмических сетей в процессе их разработки и эксплуатации 112
3.1. Преобразования алгоритмических моделей 112
3.2. Методы формирования структуры алгоритмических моделей 118
3.3. Методы исследования поведения алгоритмических моделей 128
3.4. Методы принятия решений на алгоритмических моделях 146
3.5. Обсуждение и выводы по главе 3 156
Глава 4. Распределенные алгоритмические сети и алгоритмические модели 161
4.1. Операции, отношения и вычисления на распределенных алгоритмических сетях 161
4.2. Преобразования распределенных алгоритмических моделей 185
4.3. Обсуждение и выводы по главе 4 189
Глава 5. Автоматизации моделирования на основе распределенных алгоритмических сетей 191
5.1. Существующие возможности автоматизации моделирования на основе алгоритмических сетей 191
5.2. Структура системы автоматизации моделирования на основе распределенных алгоритмических сетей 196
5.3. Обсуждение и выводы по главе 5 200
Заключение 202
Литература 205
- Концептуальная модель процесса алгоритмического моделирования на основе распределенных алгоритмических сетей
- Методы формирования структуры алгоритмических моделей
- Операции, отношения и вычисления на распределенных алгоритмических сетях
- Структура системы автоматизации моделирования на основе распределенных алгоритмических сетей
Концептуальная модель процесса алгоритмического моделирования на основе распределенных алгоритмических сетей
Люди создают модели, чтобы решать свои задачи, однако достаточно большую систему человек один охватить не в силах, это приводит к созданию людьми достаточно узко специализированных моделей, которые рассматривают только часть системы и огрубленно учитываются другие стороны анализируемого процесса, что приводит к существенным ошибкам и неточностям. Чтобы избежать этого можно объединить все такие частные модели в единую комплексную, у которой будет не один, а группа пользователей. Такая модель позволяла бы достаточно точно отражать анализируемую систему. Это приведет к существенному увеличению размерности модели, которая может превысить имеющиеся вычислительные ресурсы или стать ненаблюдаемой для одного человека, при этом каждого пользователя все равно будет интересовать только его круг задач и та часть модели, которая к ним относится. Развитие сетевых технологий позволяет отказаться от необходимости реального объединения всех моделей в одну, возможно организовать совместную работу частных моделей и групп их пользователей, как единой распределенной модели. Пути получения распределенных моделей это или декомпозиция имеющейся модели большой размерности, или обединение при помощи сетевых компьютерных технологий некоторого множества частных моделей, расположенных на разных компьютерах без их реального объединения. Но получая более качественные результаты, пользователь лишается возможности решать свои задачи независимо, без результатов других скомплексированных моделей. Необходима эффективная организация совместной работы моделей, которая во многом определяется структурой его компонент. в зависимости от рассматриваемой задачи, возможны различные структуризации процесса моделирования [1,2,116,130], но всегда в той или иной форме выделяются следующие его основные подпроцессы:
- разработка структуры модели;
- проверка адекватности модели объекту или эталонной модели;
- поиск решений с использованием модели.
Данные подпроцессы можно считать упорядоченными в приведенной последовательности, но, на практике, они тесно переплетаются между собой и часто выполняются параллельно друг-другу.
Процедуру алгоритмического моделирования на основе использования алгоритмических сетей можно представить последовательностью следующих шагов:
1) Формулировка решаемой проблемы и составление первоначального словесного описания, сценария моделируемого процесса.
2) Выделение наиболее существенных, для решаемой задачи, явлений, имеющих место в ходе процесса и установления между непосредственно взаимодействующими явлениями причинно-следственных и временных зависимостей.
3) Формирование сценария процесса в терминах выделенных явлений и отношений, упорядочение сценария на основании выявленных отношений (может быть сделано в виде некоторого ориентированного графа).
4) Выявление числовых характеристик явлений, замена причинно-следственных вычислительными отношениями между числовыми характеристиками, формирование решаемой проблемы в терминах полученных вычислительных отношений.
5) Формирование на основании полученных вычислительных зависимостей алгоритмической сети модели.
6) Формирование задания для вычислительного эксперимента над моделью и сбор исходной информации необходимой для его выполнения.
7) Проведение вычислительного эксперимента и анализ его результатов.
Здесь и далее под сценарием будем понимать некоторое словесное структурированное и частично упорядоченное описание вариантов последовательности явлений имеющих место в ходе моделируемого процесса. Данное понятие сценария довольно близко к понятию сценария в [130] и может использовать для уточнения описания аналогичную описанной в [132] графическую форму.
В рассматриваемой процедуре на каждом из выделенных шагов возможен возврат к любому из предыдущих. Пункты 1-5 относятся к формированию структуры модели, пункты 6-7 могут относится как к проверке адекватности так и к поиску решений.
Формирование структуры модели может происходить при известных фрагментах алгоритмических сетей для некоторых подпроцессов моделируемого процесса. В этом случае встает вопрос формализации преобразований и комплексирования уже известных алгоритмических сетей в новую, этот вопрос важен и в случае формирования структуры модели, когда таких сетей нет, и в случае использования распределенных алгоритмических сетей. Аналогично и для анализа модели и поиска решений, преобразования дожны позволять варьировать процесс проведения вычислительного эксперимента с целью повышения его эффективности и корректности. При алгоритмическом моделировании в отличии от функционального подхода, в случае неадекватности модели предпочтение как средству приведения к желаемому результату, отдается корректировке структуры, а не подгонке коэффициентов.
Разница в случае обычных и распределенных алгоритмических сетей будет заключаться в том, что для распределенных сетей не нужно будет формировать единую, но нужно быть уверенным, что это возможно. Преобразования распределенных алгоритмических сетей должны охватывать оба случая их образования: декомпозиции исходной единой сети или комплексирование имевшихся ранее сетей. Преобразования для обычных нераспределенных сетей дожны соответствовать случаю распределенной сети состоящей их одного фрагмента. Преобразования моделей не сводятся автоматически к преобразованиям над алгоритмическими сетями, сеть описывает только структуру модели, а в модели могут соответствовать информационные массивы и т.п. и, поэтому, требуют отдельного рассмотрения. В дальнейшем будем, в основном, рассматривать такие преобразования моделей, которые могут быть сведены к преобразования сетей с наложением дополнительных условий для возможности их осуществления.
Формализация преобразований над алгоритмическими сетями и моделями должна обеспечить повышение степени автоматизации процесса алгоритмического моделирования, что должно увеличить его привлекательность для конечного пользователя и повышение оперативности разработки новых версий системы автоматизации моделирования. Рассмотренный процесс алгоритмического моделирования и выдвинутые требования по его реализации будем рассматривать как концептуальную модель, которой будем руководствоваться при разработке методов моделирования сложных систем на основе распределенных алгоритмических сетей.
Методы формирования структуры алгоритмических моделей
Рассмотрим предполагаемый сценарий формирования структуры модели.
При реализации функции формирования структуры AM используются процессы формирования АС и задания интерпретации, выполняемые параллельно друг другу. В начале формирования модели предполагаются известными ее некоторый условный идентификатор, отличающий ее от других моделей, предметная область, объект и процесс для которого нужно разработать модель, а также некоторое подмножество терминов предметной области Т. То есть известны элементы описания модели IM, ОРО, 10, ОР, Т. АС в начале пуста. Далее происходит трудно формализуемый процесс экспликации, в данном случае выражения характеристик явлений, происходящих в ходе моделируемого процесса, в виде переменных, а причинно-следственных связей между явлениями в виде вычислительных зависисмостей. В результате по сути одновременно формируются подмножестива X, Р и Х-»Т, Р-»Т. Далее происходит отображение на Р и X некоторой графической конструкции, т.е. строится подмножества Р, Р и Р- Р и Q-»X. Появляются некоторые фрагменты АС (можно принять, что они первоначально являются единичными АС), которые затем объединяются в более крупные, те в еще более крупные, при этом процесс экспликации продолжается и порождает новые фрагменты. И так, пока создатель модели не посчитает, что она достаточно полно отображает принятый сценарий моделируемого процесса. При выполнении функции формировани структуры AM такие элементы ее описания, как ОР, Т могут изменяться.
После окончания выполнения функции, получим AM с уровнем абстрагирования соответствующим известными 1М, ОРО, 10, ОР, АС, Т, Х Т, Р-УГ. То есть неопределенным остается только множество вариантов законов изменения числовых значений переменных модели МВ.
Определение 3.2.1.
Уровень абстрагирования AM, соответствующий известным элементам описания IM, ОРО, Ю, ОР, АС, Т, Х- Т, Р- T называется уровнем абстрагирования окончания выполнения функции формирования структуры AM. Рассмотренный вариант сценария формирования структуры AM имеет много трудно формализуемых моментов, особенно если АМ создается не опираясь на ранее сделанные. С точки зрения формирования АС модели все сводится к многократному применению ранее определенной операции объединения АС. Если имеются ранее разработанные AM, то процесс формирования структуры AM, может быть частично автоматизирован.
Обычно пользователь имеет достаточно четкое представление, хотя бы для части характеристик моделируемого процесса, какие из них отобразятся в исходные, задаваемые, а какие в результирующие переменные будущей модели, в том числе, по каким из результирующих он, в первую очередь, будет оценивать состояние модели. Если имеется некоторое множество ранее разработанных моделей, то процесс формирования АС, можно представить следующим образом.
Пусть имеется некоторое множество AM {AMi}, уровень абстрагирования которых приведен к уровню окончания выполнения функции формирования структуры AM, у которых какие-либо из элементов описания ОРО;, Юь ОPj совпадают, для некоторых пар пересечение их множеств Т1 не пусто (Т;т 0). Пусть требуется сформировать структуру AM, для которой известны IM, ОРО, 10, ОР и заданы подмножества исходных переменных W, расчетных переменных V, которые обязательно должны присутствовать в формируемой модели, подмножества терминов предметной области Г такое, что W - T", У - T не пусты. Необходимо найти такое подмножество из фрагментов АС имеющихся моделей, объединение которых даст АС , обеспечивающую максимальное включение элементов из W в in(AC) и V в out(AC) и обеспечит их функциональную связь, для формируемой модели. Для элементов из W и V не вошедших в полученную таким образом AM, использующий их фрагмент АС и AM формируется вручную.
Рассмотрим особенности выполнения преобразований над АС в рассматриваемой постановке задачи формирования структуры AM.
Определим для АС, что в дальнейшем понимается под функциональной или вычислительной связью между переменными входящими в множества W и V. Определение 3.2.2.
1. Переменные х и у называются функционально (вычислительно) связанными если в АС существует подграф, который является представлением у=f(х,8). Р(х, 8) обозначает, в общем случае, многомерную функцию от х и всех других переменных некоторого множества ScX, необходимых для вычисления у.
2. Пусть есть множество W исходных переменных и множество V результирующих. В АС переменные из множеств V cX и W cX называются функционально (вычислительно) связаными, если для любой переменной уєУ, найдется хотя бы одна переменная xeW, что y=f(x,S), и любая переменная хє W входит как аргумент хотя бы в одну y=f(x,S).
Теорема 3,2.1.
1. Если х и у функционально связаны, то в исходной АС есть хотя бы один путь включающий дуги соответствующие переменным х и у (S y}{x}(AC) 0).
2. in(S{y}0(AC)) включает все переменные функционально связанные с переменной у из in(AC).
3. out(S0{x}(AC)) включает все переменные функционально связанные с переменной у из out(AC).
Доказательство.
1. Вытекает из определения 3.2.2 и определения операции выделения подграфа 2.2.20. По определению операции выделения подграфа S{y}w(AC) 0 только если S{y 0(AC) и S0W(AC) имеют общие вершины (т.е. непустое пересечение), но это означает, что переменная х используется для вычисления переменной у, а это, по определению 3.2.2, означает, что у вычислительно зависит от х.
2. Вытекает из определения 3.2.2 и определения операции выделения подграфа 2.2.20, согласно которому S{y 0(AC) включает все вершины, из которых есть путь в вершину, в которой у выходная. Следовательно подграф включает и все те вершины со входами соответствующими переменным из in(AC), из которых есть путь в вершину вычисляющую у и которые, согласно определению 3.2.2, будут функционально связаны с у.
3. Вытекает из определения 3.2.2 и определения операции выделения подграфа 2.2.20. Схема рассуждения аналогична случаю 2, но с заменой іп(АС) на out(AC).
Теорема доказана
Рассмотрим теорему, определяющую условие получения требуемой АС из заданных фрагментов АС.
Теорема 3.2.2.
Для заданной АС модели и не пустых W и V, in(Sv w AC))= W и out(Sv\у АС))зУ тогда и только тогда, когда переменные из W и V функционально (вычислительно) связаны.
Доказательство.
Пусть W и V функционально связаны, тогда по теореме 3.2.1 и определению 3.2.2 для любых xeW и уєУ имеем S{y}w(AC) 0, XGin(S{y w(AC)), yeout(S y!w(AC)), или, если рассматривать х и у как одноэлементные множества, {x}ein(S{y}{x}(AQ), {y}eout(Sw{x}(AC)). Из определения операции выделения подграфа 2.2.20 SVW AC) есть пересечение объединения всех S{y 0(AC) и всех S0W(AC), которые по теореме 3.2.1 включают все переменные функционально связанные с х или у. В силу дистрибутивности пересечения и объединения АС, можно считать SV W AC) объединением всех пересечений S y}0(AC) и S0W(AC), каждое из которых, если оно не пусто равно S y}{x}(AC), или объединению всех S{y}w(AC). Во всех S {х}(АС) переменные из W входные и при объединении ими остануться (W задает множество внешних входных дуг выделяемого подграфа). Во всех S y {X}(AC) переменные из V выходные и при объединении ими остануться (V задает множество внешних выходных дуг выделяемого подграфа). Отсюда in(Sv W (AC))3W и out(Sv w AC))3V .
Операции, отношения и вычисления на распределенных алгоритмических сетях
Имеющаяся в последнее время тенденция к децентрализации процессов экономического и социального управления, при попытке соблюдении общесистемных целей стимулирует разработку и использование моделей отдельных элементов больших систем учитывающих возможности взаимодействия с другими моделями. Проблематика распределенных систем, моделей, ЭВМ, вычислений рассматривается давно [140-143], но только развитие сетевых технологий в вычислительной технике сделало реальностью их использование и породило новые возможности (например, "многоагентные системы" [144-145]). Применительно к AM на основе АС этот вопрос ранее частично рассматривался только в [89,98]. При рассмотрении распределенных АС учитываются только самые общие моменты организации их взаимодействия, без учета возможных особенностей их реализации в той или иной аппаратной или программной среде.
Рассмотрим понятие распределенной АС. Пусть имеется исходная единая алгоритмическая модель некоторого процесса в предметной области. Данная модель включает описание подпроцессов данного процесса происходящие на разных объектах, которые могут быть территориально удалены друг от друга и структура их моделей описывается отдельными непересекающимися друг с другом АС. Модели подпроцессов могут использоваться как самостоятельные, когда рассматриваются вопросы связанные только с тем объектом, на котором происходит подпроцесс и совместно с остальной моделью, когда необходимо определить характеристики системы в целом. Шаг моделирования и число шагов во всех выделенных фрагментах при совместном их использовании одинаковы, реккурентность относительно одной и той же переменной. Иметь все такие модели сведенные в единую, помещаемую на одной ЭВМ, не всегда технологически целесообразно, так как может не быть пользователя, которого интересует вся модель целиком, и не всегда возможно по компьютерным ресурсам. Таким образом исходная единая АС разделена на отдельные фрагменты, которые могут быть распределены между несколькими пользователями, каждый из которых интересуется и имеет доступ для манипулирования только к своему фрагменту модели и соответствующей ей части входных данных. Будем считать, что каждый из пользователей имеет свою ЭВМ, которая входят в общую компьютерную сеть. Второй случай, пусть имеется некоторое множество частных моделей некоторых связанных между собой процессов происходящих на разных объектах, которые объединяются в одну систему с единым процессом включающим все имеющиеся процессы (например, отдельные заводы организуются в производственное объединение), но сводить все модели в единую нецелесообразно (из-за большого объема и недостатка компьютерных ресурсов или необходимость взгляда на весь процесс возникает нечасто, например только на этапе годового планирования, а модели все равно используются на каждом заводе и т.п.). В данном случае АС отдельных моделей могут пересекаться, но их объединение было бы не пусто и могло бы дать АС, которую затем можно было бы разделить на непересекающиеся фрагменты и придти к первому из рассмотренных случаев. Оба этих случая приводят к понятию распределенной АС. Исходя из изложенных предположений дадим определение распределенной АС.
Определение 4.1.1.
Множество отдельных АС, объединение которых было бы не пусто, называется распределенной АС, а отдельные составляющие ее АС фрагментами распределенной АС (ФАС). Распределенная АС всегда рассматривается при одинаковом шаге моделирования и одном и том же общем числе шагов для всех составляющих ее фрагментов.
Каждый фрагмент распределенной АС может иметь несколько компоненент связности, в составе распределенной АС могут быть равные друг другу фрагменты. Распределенная АС может состоять из одного фрагмента, тогда она будет соответствовать обычным АС, рассмотренные в главе 2. Пример распределенной АС приведен на Рис.4.1.1.а.
Определение 4.1,2.
Распределенная АС состоящая из непересекающихся фрагментов, называется распределенной АС канонического вида.
Пример АС в каноническом виде проиведен на Рис.4.1.1.6.
Определение 4.1.3.
Фрагменты распределенной АС называются связанными между собой, если in(OACi)nout(OACj) 0 или in( ACj)nout(OACi 0. Определение 4.1.4.
Множество связанных между собой и не связанных с остальной частью распределенной АС ее фрагментов называется компонентой связности распределенной AC.
Все введенные для единых АС операции применимы и к распределенным, но возникают некоторые особенности, которых не было в обычных АС. Распределенная АС не имеет единого множества Р, а имеет множество множеств Р, соответствующих фрагментам сосотавляющим распределенную АС, но все операции и отнощения для распределенных АС реализуются так, как если бы существовала обычная АС составленная из имеющихся фрагментов AC =ACiU...uACn 0 с единым множеством Р =F!U...uFn.
Определение 4.1.5.
Обычная нераспределенная АС, которая была бы получена объединением всех фрагментов распределенной AC AC =ACiU...uACn, называется замещающей AC.
Пример замещающей АС, для АС приведенной на Рис. 4.1.1 .а, приведен на Рис. 4 Л. 1 .в.
Определение 4.1.6.
Для распределенной AC in(AC) равно in(AC ) замещающей сети, out(AC) равно out(AC ) замещающей сети.
Определение 4.1.7.
Распределенные сети АС и АС , состоящие из фрагментов АСЬ...,АСп и АСь...,АСт равны только тогда, когда равны их замещающие АС.
АС на Рис.4.1.1.а равна АС на Рис.4.1.1.в.
Определение 4.1.8.
Распределенные АС называется равными по распределению, если сети АС и АС равны, состоят из равного числа фрагментов и для каждого фрагмента одной АС найдется равный фрагмент другой и при исключение любой пары равных фрагментов оставшиеся дополнения АС и АС будут также равны по распределению. АС на Рис.4.1.1.а будет равна по распределению сама себе.
Определение 4.1.9.
Распределенные сети АС и АС , состоящие из фрагментов АСЬ...,АСп и АСь...,АСт соответственно изоморфны только тогда, когда изоморфны их замещающие АС.
Определение 4.1.10.
Распределенные АС называется изоморфными по распределению, если распределенные сети АС И АС изоморфны, состоят из равного числа фрагментов и для каждого фрагмента одной АС найдется изоморфный фрагмент другой АС. При исключение любой пары равных фрагментов оставшиеся дополнения АС и АС будут также изоморфны по распределению.
Определение 4.1.11.
Распределенная сеть АС вкладывается в АС только тогда, когда замещающая сеть АС вкладывается в замещающую сеть АС . Распределенная сеть АС называется подграфом распределенной сети АС .
Очевидно, что фрагмент распределенной АС является ее подграфом.
Определение 4.1.12.
Распределенная сеть АС1 изоморфно вкладывается в АС2 только тогда, когда замещающая сеть АС изоморфно вкладывается в замещающую сеть AC2.
Определение 4.1.13.
Распределенная сеть АС вкладывается в АС по распределению только тогда, когда в АС имеется подграф равный по распределению АС .
Структура системы автоматизации моделирования на основе распределенных алгоритмических сетей
Рассмотренные возможности реализации автоматизированной технологии алгоритмического моделирования [82-84,88] охватывают небольшую часть изложенных методов, которые могут быть полностью реализованы лишь в последующих версиях системы автоматизации моделирования КОГНИТРОН.
Рассмотрим укрупненную структуру системы автоматизации алгоритмического моделирования в полной мере использующие рассмотренные в работе методы и модели. Система должна работать под управлением сетевой операционной системы и учитывать соответствующие требования по аппаратному и программному обеспечению. Основные требования к системе с точки зрения пользователя, это максимально возможная степень автоматизации процесса, приближение ее к "кнопочной системе" [126]. Пользователь не должен чувствовать существенной разницы при работе с обычной или распределенной моделью.
Основные режимы системы:
1. Создание структуры модели.
2. Вычислительный эксперимент над моделью.
Режим создания структуры модели предполагает наличие автоматизированных процедур ввода модели, корректировки ее структуры, построения структуры из фрагментов АС ранее разработанных моделей, синтаксического анализа АС, построения тезауруса предметной области, построения соответствия между тезаурусами разных предметных областей, оптимизации структуры модели, хранения моделей.
Режим вычислительного эксперимента предполагает наличие автоматизированных процедур преобразований алгоритмических сетей моделей в соответствии с заданной целью вычислительного эксперимента, ввода, поиска и корректировки требуемой для расчетов исходной информации, организации расчета модели, анализа результатов, хранения исходной информации и результатов.
Укрупненная структура системы автоматизации моделирования на основе распределенных алгоритмических сетей приведена на Рис. 5.2.1. Есть две внешние связи системы - с пользователем и компьютерной сетью. Пользователь определяет требуемый режим работы. В режиме создании структуры модели соответствующий блок системы взаимодействует с пользователем, базой моделей и блоком сетевого диспетчера. В режиме выполнении вычислительного эксперимента соответствующий блок системы взаимодействует с пользователем, базой моделей, базой данных и блоком сетевого диспетчера. База моделей содержит информацию об АС моделей, их интерпретацию в терминах предметных областей. База данных содержит информацию об остальных элементах описания моделей, представленных в базе моделей. Сетевой диспетчер осуществляет поиск требуемых компонент распределенных моделей в доступном сетевом пространстве, организует их совместное использование в сетевом режиме.
Выход системы в сетевой режим определяется либо заданием пользователя, либо происходит автоматически при исчерпании возможностей базы моделей или базы данных имеющейся на рассматриваемом компьютере. При задании пользователем некоторой распределенной модели происходит автоматический вызов всех составляющих ее обычных моделей в доступном сетевом пространстве. Далее, если это удалось, производится синтаксический контроль АС модели, затем производится вызов остальных элементов описания модели и выполнение необходимых действий с моделью. Автоматический выход в поиск в доступном сетевом пространстве осуществляется, если при выполнении автоматизированных процедур формирования АС модели, сбора исходных данных для расчета или при установлении соответствия между терминами различных предметных областей после проверки содержимого базы моделей и базы данных на исходном компьютере цель процедуры не достигнута и пользователь отказывается дополнять требуемую информацию в ручном режиме. Если поиск в доступном сетевом пространстве не привел к достижению цели процедуры система сообщает об этом пользователю.
