Содержание к диссертации
Введение
ГЛАВА 1. Современное состояние задач формализации и анализа дискретных организационно-технологических систем 11
1.1. Организационно-технологические системы со структурированными агентами, их разновидности 11
1.2. Анализ использования сетевых моделей при построении и исследовании различных систем
1.2.1. Анализ и построение систем управления технологическими процессами 20
1.2.2. Построение дорожных карт развития систем 30
1.2.3. Анализ систем массового обслуживания
1.3. Понятие о многоагентных триадных сетях и области их применения 40
1.4. Постановка цели и задач исследования 49
ГЛАВА 2. Понятие и методика построения бинарных индикаторных сетей, область их применения 51
2.1. Понятие бинарной индикаторной сети 51
2.2. Алгоритм построения дискретных систем и анализа процессов с помощью интерактивных моделей на основе БИС 61
2.3. Программно-алгоритмическое обеспечение для построения систем на основе моделей в форме бинарных индикаторных сетей
2.3.1. Описание интерфейса программы 68
2.3.2. Описание основных классов, процедур и функций 74
2.4. Выводы 78
ГЛАВА 3. Понятие и методика построения ООО-моделей систем массового обслуживания 81
3.1. Понятие ООО-модели 81
3.1.1. Уровень обеспечения 82
3.1.2. Уровень обслуживания 85
3.1.3. Уровень отчетности
3.2. Алгоритм анализа систем массового обслуживания на основе ООО-моделей 89
3.3. Выводы 92
ГЛАВА 4. Практическое применение методов, основанных на бинарных индикаторных сетях и ООО-моделях 94
4.1. Описание технологического процесса выращивания искусственных сапфиров на основе бинарной индикаторной сети 95
4.2. Автоматизация вытягивания монокристалла сапфира на основе управляющего автомата, построенного на бинарной индикаторной сети 106
4.3. Бинарная модель для проведения имитационного эксперимента по модернизации установки по выращиванию искусственных сапфиров 118
4.4. ООО-модель многофункционального центра предоставления государственных и муниципальных услуг 125
4.5. Бинарная сетевая дорожная карта «Обеспечение информационной безопасности МФЦ» 137
4.6. Выводы 144
Основные результаты и выводы 147
Список сокращений 150
Список литературы 152
- Анализ использования сетевых моделей при построении и исследовании различных систем
- Программно-алгоритмическое обеспечение для построения систем на основе моделей в форме бинарных индикаторных сетей
- Алгоритм анализа систем массового обслуживания на основе ООО-моделей
- Бинарная модель для проведения имитационного эксперимента по модернизации установки по выращиванию искусственных сапфиров
Анализ использования сетевых моделей при построении и исследовании различных систем
Рассматриваемые в данной работе вопросы относятся к области искусственного интеллекта (ИИ) и интеллектуального управления.
Термин «искусственный интеллект» (artificial intelligence) был предложен Джоном Маккарти в 1956 году на семинаре в Дартмутском колледже (США). С конца 1980-х годов искусственный интеллект превратился в науку и на сегодняшний день является одной из наиболее динамично развивающихся областей знаний. Зарождение ИИ как науки связано с именами таких ученых, как У. Мак-Каллок, Дж. Маккарти, М. Минский, Ф. Розенблатт, А. Тьюринг и др. В России развитие исследований в области ИИ связано с такими учеными, как А.А. Ляпунов (один из основателей российской кибернетики), М.М. Бонгард (организатор семинара «Автоматика и мышление» в МГУ в 1954 г., автор алгоритма «Кора», моделирующего деятельность человеческого мозга при распознавании образов), Д.А. Поспелов (основатель нового направления в ИИ – ситуационного управления), М.А. Гаврилов и М.Л. Цетлин («пионеры» становления российской школы ИИ, например знаменитой Гавриловской школы) и др.
Известно несколько определений понятия искусственного интеллекта. Приведем некоторые из них. В толковом словаре по искусственному интеллекту [64] ИИ понимается как: – научное направление, в рамках которого ставятся и решаются задачи аппаратного или программного моделирования тех видов человеческой деятельности, которые традиционно считаются интеллектуальными. – свойство интеллектуальных систем выполнять функции (творческие), которые традиционно считаются прерогативой человека. А.К. Тугенгольд [67] дает следующее определение. Искусственный интеллект – научное направление, в рамках которого строятся теории и модели, призванные объяснить и использовать в технических системах принципы и механизмы интеллектуальной деятельности человека.
В учебном пособии для ВУЗов «Системы искусственного интеллекта» [16] В.В. Девятков приводит ряд высказываний отечественных и зарубежных ученых относительно понятия ИИ: – восхищающие новые усилия заставить компьютеры думать… машины с разумом в полном и языковом смысле (J. Haugeland, 1955 г.); – автоматизация деятельности, которую мы ассоциируем с человеческим мышлением, такой как принятие решений, решение задач, усвоение знаний (R.E. Bellman, 1978 г.); – исследование умственных способностей с помощью использования вычислительных моделей (E. Charniak and D. McDermot, 1985 г.); – теория эвристического поиска и вопросы создания решателей задач, относящихся к разряду творческих или интеллектуальных (Г.С. Поспелов, 1986 г.); – система, которая способна находить оригинальные и эффективные ответы, часто неожиданные как для пользователя и конструктора ЭВМ, так и для составителя программ, по которым работает машина (А.Г. Ивахненко, 1986 г.); – искусство создания машин, способных выполнять действия, которые потребовали бы интеллекта от людей, если бы они эти действия выполняли (R. Kurzweil, 1990 г.); – область исследования, которая пытается понять и моделировать разумное поведение в терминах вычислительных процессов (R.J. Schalkoff, 1990 г.); – исследование того, как заставить компьютеры делать вещи не хуже людей (E. Rich and K. Knigpt, 1991 г.); – изучение исчислений, которые позволяют понимать, рассуждать и действовать (P.H. Winston, 1992 г.); – отрасль науки о компьютерах, которая интересуется автоматизацией разумного поведения (J.I. Luger and W.A. Stubblefield, 1993 г.).
Как видно, определений и подходов к пониманию ИИ огромное множество. Однако стоит заметить, что все эти высказывания так или иначе связывают искусственный интеллект с умением рассуждать и действовать (принимать решения) на основании этих рассуждений, то есть ИИ – это техническая (информационная и программно-аппаратная) реализация некоторых интеллектуальных способностей человека [67]. В.Б. Тарасов выделяет две точки зрения в решении задач ИИ [62]: – решение задачи одним агентом на основе инженерии знаний представляет собой точку зрения классического ИИ, согласно которой агент (например, динамическая интеллектуальная система), обладая глобальным видением проблемы, имеет все необходимые способности, знания и ресурсы для ее решения. – распределенный ИИ предполагает, что отдельный агент может иметь лишь частичное представление об общей задаче и способен решить лишь некоторую ее подзадачу. Поэтому для решения сколько-нибудь сложной проблемы, как правило, требуется взаимодействие агентов, которое неотделимо от организации многоагентной системы. Этот социальный аспект решения задач есть одна из фундаментальных характеристик концептуальной новизны передовых компьютерных технологий и искусственных (виртуальных) организаций, строящихся как многоагентные системы.
Как видно, при рассмотрении данных подходов вводятся в рассмотрение понятия агента и многоагентной системы (МАС). Агентом считается все, что действует (слово «агент» произошло от латинского слова «agere» – действовать). Но предполагается, что компьютерные агенты обладают некоторыми другими атрибутами, которые отличают их от обычных «программ», такими как способность функционировать под автономным управлением, воспринимать свою среду, существовать в течение продолжительного периода времени, адаптироваться к изменениям и обладать способностью взять на себя достижение целей, поставленных другими.
Программно-алгоритмическое обеспечение для построения систем на основе моделей в форме бинарных индикаторных сетей
Реализации крупномасштабных проектов и построению сложных систем, требующих больших финансовых и временных затрат, как правило, предшествует построение и анализ математической модели, на основе которой прорабатываются стратегические планы управления проектом. В модели желательно использовать формальный язык, доступный и наглядный для экспертов – специалистов в предметной области. Таковым является, например, графическое описание поведения системы, отождествляемой с проектом. Эффективно применение при моделировании систем сетей Петри и их модификаций [28, 50, 86], в том числе «индикаторных сетей» [88, 96, 97], представляющих собой сеть Петри с переходами, помеченными логическими выражениями специального вида (индикаторными выражениями), и дугами, помеченными числовыми коэффициентами – весами. Комбинация графических и алгебро-логических языковых средств позволяет уменьшить размерность модели и тем самым повысить степень ее наглядности. С другой стороны, модель должна отображать структурные характеристики системы: поставленные перед ней цели; действия, направленные на достижение целей; показатели состояния системы. Трехслойная (триадная) модель системы, отображающая взаимодействие указанных трех характеристик, исследовалась в [88, 96, 97] и ряде других. В триадной модели фиксируются и анализируются как связи внутри каждого слоя, так и связи между слоями (цели-действия, цели-показатели, действия-показатели) и воздействия на систему внешней среды. Это делает описание взаимодействия параметров в рамках модели и верификацию корректности взаимодействий достаточно сложными.
В данной работе предлагается упрощенный подход к построению систем и агентов за счет перехода от триадной к бинарной схеме. Суть подхода заключается в следующем. Показатели, образующие нижний слой в триадной модели [88, 96, 97], разбиваются на 4 группы: оценки состояния системы (процесса); ресурсы, необходимые для выполнения действий; внешние события, влияющие на ход процесса; воздействия системы на внешнюю среду. Для всех групп, кроме оценки состояния системы, показатели внутри группы не влияют друг на друга. Взаимонезависимы и показатели из разных групп. Что касается оценочных показателей, то они хотя и могут в некоторых случаях вступать во взаимодействие, но выявить и промоделировать это взаимодействие (фиксируемое в когнитивной карте [39]) весьма непросто. При «грубом» моделировании им можно пренебречь. С учетом сказанного, в графовом представлении триадной модели слой показателей вырождается в набор не связанных между собой позиций, т.е. становится лишним. Показатели, принадлежащие всем четырем группам, войдут как аргументы в индикаторные выражения, нагружающие переходы в графе целей и графе действий. При бинарном имитационном моделировании процесса на заданном временном горизонте отслеживается функционирование, в том числе взаимодействие, графов целей и действий с выявлением динамики всех показателей. В последнее время для обозначения стратегий развития систем на средне- и долгосрочную перспективу, в том числе стратегий управления проектами, применяют термин «дорожная карта» [30, 32, 97]. Предлагаемую в работе модель в общем случае будем называть бинарной индикаторной сетью (БИС), а дорожную карту, построенную на основе БИС – бинарной сетевой дорожной картой (БСДК). В процессе моделирования систем с помощью БИС строится лента поведения, отражающая дискретные изменения параметров системы (целей, действий, показателей).
Анализируемый временной горизонт процесса выполнения проекта – развития системы (горизонт прогнозирования) состоит из n1 «участков стабильности», на которых изменяются только значения параметров, но остаются неизменными их состав и взаимосвязи. Другими словами, участок характеризуется фиксированной БИС. Участки стабильности разделены критическими точками, определяемыми как моменты появления «предугрозы» (например, выход показателя за пределы допустимого диапазона значений, недостижение цели за нормативное время, «зависание» процесса из-за недостаточности ресурсов или ошибочной последовательности действий, и т.д.). В критических точках из множества возможных выбирается определенный вариант продолжения процесса и выполняется соответствующее этому выбору преобразование БИС – изменение состава и/или взаимосвязей параметров путем операций над графами и корректировки индикаторных выражений. Смена индикаторной сети трактуется как управление процессом выполнения проекта.
Каждому участку стабильности на горизонте моделирования ставится в соответствие БИС. При этом начальную сеть задает ЛПМ – Лицо, Проводящее Моделирование. В ходе имитационного моделирования определяются критические точки, в которых ЛПМ «задумывается» о варианте продолжения процесса развития, принимает решение и трансформирует сеть предыдущего участка в сеть последующего участка стабильности, т.е. управляет процессом. Таким образом, процесс развития в общем случае характеризуется (n-1)-кратным изменением индикаторной сети. Изменение по усмотрению ЛПМ производится в обоих или одном слое сети и носит выборочный характер: выделяется фрагмент графового описания уровня, выделенный фрагмент «вырезается» и замещается другим фрагментом при сохранении преемственности в отношении остальной части графа слоя. Эта процедура подобна медицинской операции, и потому названа «графохирургической» операцией [88].
Бинарное моделирование является интерактивным в том смысле, что оно выполняется в форме диалога между компьютером и ЛПМ: компьютер отслеживает функционирование (развитие) системы на участке стабильности и фиксирует появление критической точки («предугрозы»), ЛПМ на основе полученной информации принимает решение и корректирует БИС.
Далее будет приведено определение и пример индикаторной сети, рассмотрена БИС на основе индикаторных сетей. Затем будет дано описание алгоритма построения дискретных систем и анализа процессов с помощью интерактивных моделей на основе БИС на заданном временном горизонте, порождающего последовательность БИС.
Алгоритм анализа систем массового обслуживания на основе ООО-моделей
Суть агентного подхода к имитационному моделированию раскрывается на среднем уровне - уровне обслуживания, где происходит обработка заявок.
Для магазина самообслуживания [87] на этом уровне имеет место взаимодействие магазина с покупателем, причем покупка продуктов осуществляется в режиме самообслуживания. Как говорилось ранее, средний уровень ООО-модели отображается множеством параллельно работающих одинаковых циклических индикаторных сетей - графами клиентов. В данном примере в каждом графе реализуется следующая последовательность действий (рис.3.2): ео - ожидание покупателя; ei - отбор товаров (в корзину); Є2 - расчет в кассе; е3 - сообщение в базу данных. Индикаторные формулы, дополняющие каждый из графов Г2і: Р(гі): (ео=1)л(еі=0)л(8і=1Н(ео=0)л(еі=1) Р(г2): (еі=1)л(е2=0)л(К3=Кп) (еі=0)л(е2=1) Р(г3): (е2=1)л(ез=0)л(82=8тН(е2=0)л(ез=1) Р(г4): (ез=1)л(ео=0) (ез=0)л(е0=1)л(8і=0) Дополнительные переменные, используемые в индикаторных формулах: Si - появление в магазине нового покупателя (0 - покупателя нет, 1 -покупатель зашел в магазин); Кз - количество товара в корзине; Кп - количество товара, необходимое покупателю; S2 - сумма денег, переданная покупателем кассиру; Sт - стоимость товаров в корзине покупателя. Граф Г2i представляет собой ни что иное, как модель агента-заявки. Его роль может играть покупатель в магазине, клиент банка, посетитель многофункционального центра. На уровне обслуживания описаны типовые действия агента при прохождении его через систему массового обслуживания. Помимо простейшей линейной структуры граф Г2i может содержать и разветвления, обозначающие выбор того или варианта развития событий в зависимости от внешних и внутренних параметров и от целевых ориентиров агента. Например, в графе уровня обслуживания ООО-модели МФЦ (раздел 4.4) последовательность дальнейших действий посетителя зависит от того, как он записывается на прием: в живую очередь либо предварительно по телефону или через интернет. Таким образом, хотя модель агента универсальна и одинакова для всех заявок, в ней учитываются индивидуальные особенности поведения каждой отдельно взятой заявки при прохождении ее через систему. С другой стороны, присутствует и мотивационная составляющая – агент выбирает наиболее подходящий вариант развития событий, исходя из своих убеждений. К примеру, снова рассматривая запись на прием заявителя, можно сказать, что при наличии у заявителя свободного времени и потребности скорейшего получения государственной услуги он запишется на прием в живую очередь на текущий день, а при отсутствии желания долгого ожидания в очереди он запишется предварительно на последующие дни на определенное время. Итак, хотя модель агента уровня обслуживания ООО-модели описывается, казалось бы, только последовательностью действий, она сочетает в себе и целевые ориентиры агента, выраженные через возможность выбора той последовательности действий (ветви графа), которая будет в наибольшей степени удовлетворять его потребности.
На каждом из описанных уровней в процессе моделирования заносятся сообщения в базу данных о количестве и стоимости полученного товара от поставщика и количестве и стоимости проданного товара каждому покупателю. На основании содержимого базы данных на нижнем уровне ООО-модели (уровне отчетности) рассчитываются ключевые показатели предприятия в данный момент или накопленным итогом с начала моделируемого периода.
Уровень отчетности представляет собой сводку основных показателей работы системы в отчетном периоде, а также служит индикатором выполнения заданных нормативов этих показателей.
Как видно из рис. 3.3 [87], граф отчетности так же имеет циклическую структуру в том смысле, что основные показатели рассчитываются каждый раз в новом отчетном периоде. На рис.3.3 переход q0 как раз символизирует начало нового отчетного периода.
Остальная (нециклическая) часть графа имеет древовидную структуру. Позиции графа представляют собой ключевые показатели системы. Наличие маркера в позиции символизирует достижение заданного значения показателя в отчетном периоде. Маркеры сначала заносятся в нижние позиции графа (на рис. 3.3 это позиции p7-p11) по достижению соответствующих значений показателей, а затем движутся по сети при срабатывании переходов. В индикаторные формулы уровня отчетности помимо позиций входят непосредственно числовые значения ключевых показателей и заданные для них уровни.
. Граф Г3 – основные показатели финансово-хозяйственной деятельности предприятия (уровень Отчетности) Здесь следует отметить, что строчными буквами (p1-p11) будем обозначать позиции переходов графа Г3, а прописными (P1-P11) – непосредственно показатели, соотнесенные соответствующим позициям. Таким образом, в индикаторных формулах переменные рі-рп будут принимать значения 1 или 0, соответствующие наличию либо отсутствию маркера в позиции, то есть попаданию либо непопаданию значения показателя в заданный диапазон. Переменные Pi-Рц в свою очередь будут отражать количественные значения показателей. Переменные, соответствующие нормативным требованиям, будем обозначать соответствующими индексами min или max, например, требуемый минимальный объем продаж - Pi imin. Наличие маркера в позиции служит своего рода индикатором достижения требуемого значения показателя.
Бинарная модель для проведения имитационного эксперимента по модернизации установки по выращиванию искусственных сапфиров
Истинность переменных Pз-Рб соответствует выполнению сопоставленных им условий. Аналогично БИС на рис. 4.24 при переходе из dk в do по срабатыванию перехода tм метки в целевых позициях Cі-Сз обнуляются.
Построенными моделями оператор может пользоваться в процессе проведения эксперимента. По ним однозначно можно отследить выполнение или невыполнение поставленных целей, кроме того, осуществлять мониторинг параметров работы системы и выявлять неточности и ошибки работы алгоритмов. Пользуясь приложением для моделирования БИС [59, 93], оператор может вносить в модель текущие параметры работы системы и прогнозировать следующие шаги развития процесса. Помимо этого, в случае неправильности работы алгоритма, можно воспользоваться инструментом «графохирургических» операций [88] для корректировки последовательности действий.
На сегодняшний день системы массового обслуживания (СМО) все более плотно входят в повседневную жизнь каждого человека. Мы постоянно ходим в магазины самообслуживания и поликлиники, в банки и на почту. Кроме того, сейчас появилась возможность предварительной записи на прием в различные организации (по телефону либо через интернет). Вследствие роста численности клиентов, разнообразия СМО, ограниченности используемых ресурсов все более актуальными становятся задачи теории систем массового обслуживания (ТСМО) [70]. К таким задачам можно отнести увеличение пропускной способности СМО, оптимизацию распределения нагрузки на канал, сокращение времени обслуживания одной заявки и т.д. Одним из методов ТСМО является имитационное моделирование систем, позволяющее провести анализ работы системы, проследить ее поведение во времени, выявить «тонкие» места и рационализировать или оптимизировать ее дальнейшую работу. Ранее в разделе 4.3 было рассмотрено построение виртуальных СМО на основе трехуровневых графовых ООО-моделей (Обеспечение, Обслуживание, Отчетность) [87]. Ниже приведена модифицированная концепция ООО-модели на примере конкретной СМО – многофункционального центра предоставления государственных и муниципальных услуг (МФЦ).
В 2010 году государство приняло решение пересмотреть подход к своей политике в области информационных технологий. Пришло понимание того, что ценны не только внедренные технологии и разработанные информационные системы сами по себе, но и то, какую пользу они приносят гражданам, бизнесу, всему обществу. В связи с этим Правительством РФ была утверждена государственная программа «Информационное общество (2011-2020 годы)» [15].
С целью обеспечения доступности для населения, повышения качества и уменьшения сроков оказания государственных и муниципальных услуг Президентом Российской Федерации 27 июля 2010 года был подписан федеральный закон № 210-ФЗ «Об организации предоставления государственных и муниципальных услуг» [56]. В данном законе, в том числе, дано следующее определение МФЦ. Многофункциональный центр предоставления государственных и муниципальных услуг (далее – многофункциональный центр) – организация, созданная в организационно-правовой форме государственного или муниципального учреждения (в том числе являющаяся автономным учреждением), отвечающая требованиям, установленным настоящим Федеральным законом, и уполномоченная на организацию предоставления государственных и муниципальных услуг, в том числе в электронной форме, по принципу «одного окна» [56].
То есть МФЦ – это своего рода площадка для оказания государственных услуг. С одной стороны, здесь представлены заявители (физические или юридические лица), обращающиеся за услугой, а с другой – организации (органы исполнительной власти, федеральные и муниципальные службы, организации иных форм собственности), оказывающие данную услугу (рис. 4.26).
Услуги на площадке МФЦ могут оказывать как непосредственно представители организаций-участников (ПОУ) МФЦ, так и универсальные специалисты (УС), являющиеся сотрудниками самого МФЦ. Управление потоком заявителей осуществляется с помощью системы электронной очереди.
Общая схема организации и связей МФЦ Соответственно МФЦ является полноценной СМО, в которой поток заявок это поток заявителей, каналы обслуживания - это окна приема специалистами, а ограниченные ресурсы - это ограниченные время работы, количество специалистов, скорость обработки заявок. Основная цель создания МФЦ - это повышение доступности и упрощение процедуры получения государственных услуг для населения. Для ее достижения решается ряд задач: - рациональное размещение специалистов различных организаций, обеспечение их комфортной работы; 128 - оптимизация алгоритма работы системы электронной очереди, управление ее работой, распределение ограниченного числа талонов между живой очередью и предварительной записью; - организация комфортных мест ожидания для заявителей; - организация обучения специалистов; - повышение скорости и качества обработки документов. Некоторые из перечисленных задач (работа с электронной очередью, обучение специалистов) можно решать методами имитационного моделирования, один из которых будет описан ниже. В целом методы имитационного моделирования достаточно актуальны и применяются при работе с бизнес-процессами [66], СМО [22] и в других сферах. Рассмотрим построение обобщенной модели работы МФЦ на основе ООО-модели [87]. Данная модель включает в себя 3 уровня: - Уровень Обеспечения; - Уровень Обслуживания; - Уровень Отчетности. Каждый из уровней представляет собой индикаторную сеть [88], состоящую из одного или нескольких двудольных графов.
Рассмотрим подробнее уровень обеспечения. Ранее [87] этот уровень включал в себя один граф. Однако, в данном случае товаром являются государственные услуги (государственная регистрация права, изготовление кадастрового паспорта, изготовление технической документации и т.д.), предоставляемые несколькими организациями, которые работают параллельно в разных окнах приема. Исходя из этого целесообразно на уровне обеспечения ввести множество циклических графов Гц работы специалистов с заявителями, а не использовать один граф, как это было сделано ранее. Все услуги, оказываемые на площадке МФЦ, можно разделить на три типа: - консультации (результатом таких услуг является информация, необходимая заявителю в конкретной жизненной ситуации, например, консультация по вопросу регистрации прав на недвижимое имущество); 129 - прием документов (при получении такой услуги заявитель сдает некий определенный перечень документов специалисту для получения других документов либо назначения определенных льгот, выплат и т.д., например, прием запросов на выдачу информации из Единого государственного реестра прав на недвижимое имущество и сделок с ним (ЕГРП) или прием документов для назначения адресной социальной помощи); - выдача документов (как правило, за такой услугой заявитель обращается после получения услуги по приему документов, и результатом данной услуги является пакет документов, который выдается заявителю, например, свидетельство о государственной регистрации права, страховой номер индивидуального лицевого счета (СНИЛС) или кадастровый паспорт). В связи с этим для каждого типа услуг целесообразно привести отдельную последовательность действий как отдельную ветвь графа Гц.Такой граф, описывающий последовательность действий специалиста при работе с заявителем, приведен на рис. 4.27.