close

Вход

Забыли?

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

?

Структурно-параметрический синтез и анализ моделей потоковых систем промышленно-логистического назначения на основе квазиклеточных сетей

код для вставкиСкачать
На правах рукописи
Аристов Антон Олегович
Структурно-параметрический синтез и анализ моделей
потоковых систем промышленно-логистического назначения на
основе квазиклеточных сетей
Специальность 05.13.01 — Системный анализ, управление
и обработка информации (промышленность)
Автореферат
диссертации на соискание учёной степени
доктора технических наук
Москва – 2018
Работа выполнена в ФГАОУ ВО
«Национальный исследовательский технологический университет «МИСиС»
Научный консультант:
доктор технических наук, профессор
Горбатов Александр Вячеславович
Официальные оппоненты:
Большаков Борис Евгеньевич, доктор технических наук, профессор,
заведующий кафедрой устойчивого инновационного развития ГБОУ
ВО Московской области «Международный университет природы
общества и человека «Дубна»;
Ляпунцова Елена Вячеславовна, доктор технических наук,
профессор,
профессор
кафедры
Инновационного
предпринимательства (ИБМ 7) ФГБОУ ВО «Московский
государственный технический университет имени Н. Э. Баумана
(национальный исследовательский университет)»;
Сениченков Юрий Борисович, доктор технических наук, профессор,
профессор кафедры "Распределенные вычисления и компьютерные
сети" ФГАОУ ВО «Санкт-Петербургский политехнический
университет Петра Великого»
Ведущая организация:
ФГБУН «Институт проблем управления им. В.А. Трапезникова»
Российской Академии Наук
Защита диссертации состоится 6 июля 2018 г. в 11 ч. 00 мин.
на заседании диссертационного совета Д 212.132.13
при Национальном исследовательском технологическом университете «МИСиС»
по адресу: 119991, Москва, Ленинский проспект д.6 стр. 2, ауд. А-305
С диссертацией можно ознакомиться в библиотеке Национального
исследовательского технологического университета «МИСиС»
и на сайте: http://misis.ru/science/dissertations/2018/3385/
Учёный секретарь
диссертационного совета,
к.ф.-м.н.
Лычев А.В.
1
Общая характеристика работы
Актуальность работы. В промышленности, транспорте, медицине,
социальной сфере и других областях часто рассматриваются системы, поведение
которых объясняется явлениями, связанными с распространением потоков. Такие
системы включают в себя структуру (пространство) и потоки, распространяемые в
такой структуре. Задачи анализа и синтеза таких систем, проектирования,
управления, принятия и выработки проектных решений включают в себя аспекты
моделирования, расчётов и визуализации потоков, а также получения их
характеристик. Речь идёт как о характеристиках системы в целом (пропускная
способность системы в целом, плотность, величина потока за время и т. д.), так и
характеристики отдельных локальных участков такой системы (интенсивность
потока в заданной области, пропускная способность участка, время прохождения
участка и т. п.). Указанные величины используются при решении широкого круга
задач конкретной предметной области, тесно связанных с эффективностью
функционирования потоковой системы. Примерами таких задач является выбор
состава автопарка и оценка производительности карьеров, оценка времени
прохождения транспортных средств по участкам дорог при различных
конфигурациях таких участков, время эвакуации персонала промышленных
предприятий и других объектов массового пребывания людей в зависимости от
численности сотрудников и посетителей. Указанные задачи не только
предполагают оценку параметров потоковых систем при различных вариантах её
функционирования, но и варьирование структуры самой системы (например, при
эксплуатации дополнительных карьерных экскаваторов, открытии новых
выработок).
Моделирование потоков в таких системах независимо от предметной
области играет значимую роль как общенаучный метод исследования, при котором
рассматриваемая система и потоки в ней заменяются упрощённым их
представлением, отражающим принципиально важные особенности этой системы.
На современном этапе моделирование осуществляют с применением
вычислительной техники с различными уровнями детализации, формируя при
этом, прежде всего микроскопические и макроскопические модели, для которых
существует объективная проблема преобразования моделей и перехода от одного
уровня моделирования к другому.
В условиях моделирования потоков уровни детализации приобретают
особую актуальность, поскольку потоки в различных предметных интерпретациях
обладают дуализмом. С одной стороны, поток следует понимать как совокупность
взаимодействующих объектов (частиц жидкости, газа; единиц готовой продукции
и полуфабрикатов, людей, транспортных средств, бит информации), с другой –
поток воспринимается как некоторый объект (поток жидкости, транспортный
поток, поток сырья, поток продукта, информационный поток). Подобный дуализм
определяет подходы к построению микро- и макромоделей потока. Отраслевой
2
особенностью потоковых систем в промышленности и логистике (промышленнологистического назначения) является дуализм потока, при котором поведение
потока в целом сводится к поведению отдельных потокообразующих объектов.
Учитывая, что поток предполагает поведение большого количества
взаимодействующих объектов, на практике при исследовании систем, сводящихся
к поведению потоков, используют компьютерные модели. Для компьютерного
моделирования характерны некоторые принципиальные особенности:
 компьютерная реализация предполагается для моделей, как на микро-, так и
на макроуровне, при этом проблема перехода между этими уровнями попрежнему актуальна;
 предполагается достаточно широкое распространение «инкрементального»
(итерационного) моделирования, при котором осуществляется не
построение функции моделируемого параметра f от времени, т. е. f (t ) , а
вычисление нового значения из предыдущего, т. е. f t = f t−1+Δ f . При
таком подходе нет явно записанного уравнения потока;
 поведение системы реализуется с течением модельного времени, которое в
частном случае может совпадать с реальным;
 целью моделирования является получение мгновенных характеристик
отдельных объектов потока, а также макропараметров потока за некоторое
время моделирования;
 следует различать задачу проектирования и разработки инструментария
компьютерного моделирования и предметную задачу, решаемую с
применением указанного инструментария.
На сегодняшний день компьютерные модели потоковых систем строятся для
конкретных предметных областей и предполагают некоторую цель и только один
уровень моделирования. Наиболее распространёнными подходами является
объектно-ориентированное моделирование на микроуровне и дискретные модели
потоков в сетях на макроуровне. Если модели микроуровня предназначены для
сбора статистики поведения отдельных объектов с течением времени и получения
характеристик потока на их основе, то макроскопические модели учитывают
потоки с точки зрения их связи со средой, в которой они распространяются; при
этом каждый поток является отдельным объектом.
Таким образом, исходя из рассмотренных особенностей, актуальной
проблемой является разработка новых универсальных моделей и методов синтеза
и анализа потоковых систем, не зависящих от предметной интерпретации и
позволяющих обеспечить переходы между микро- и макроописаниями
моделируемой системы.
Степень разработанности темы. Вопросы моделирования и анализа
потоковых систем, так или иначе рассматривалось в различные этапы развития
важнейших отраслей деятельности человека, таких как градостроительство,
транспорт, промышленность, медицина, оборона и др. Исторически проблема
3
исследования и проектирования потоковых систем возникла как реальная
потребность указанных областей, а моделирование и анализ в них целесообразно
рассматривать как основу проектирования. Идеи развития подходов к
исследованию потоковых систем в различных областях рассматривались
С.Ю.Фронтином, Г.Платвием, А.Клавдием, Г.Кроном, Г.Жомини, А.М. Бадаляном,
В.М. Ерёминым, М.М.Ахмадинуровым, А.П. Буслаевым, и др. В приведённых
работах рассматриваются модели, ориентированные на проектирование систем
городских коммуникаций, электрических машин, прогнозирование развития
транспортных систем, организации военных сил и других областей. Особенностью
данных работ является то, что разрабатываемые модели были ориентированы на
применение исключительно в предметных областях, специалистами в которых и
являлись их авторы. Следует также отметить, что ряд работ по исследованию
потоков был разработан в условиях отсутствия вычислительных машин,
способных рассчитывать поведение потока на основе поведения отдельных его
потокообразующих объектов, поэтому предполагал разработку моделей на
макроуровне.
С
развитием
вычислительной
техники
появилась
возможность
моделирования потоковых систем на микроуровне, предполагающих рассмотрение
не потока в целом (как на микроуровне), а отдельных потокообразующих объектов,
для которых характерно определённое локальное взаимодействие. Реализация
микромоделей потоковых систем описана в работах Д. фон Неймана, А. Тьюринга,
М.Гарднера, С. Улама, Н. Виннера, С. Вольфрама, Д.Х.Конвея, К. Петри, Э. Мура,
В.А.Горбатова, А.В. Горбатова, А.М. Вендрова, Л.В. Калмыкова, В. Тоффоли, Э.
Йордана и др. Для моделирования на микроуровне применяются подходы, так или
иначе основанные на дискретных структурах (клеточных автоматах, графах,
конечных автоматах, сетях Петри и др.). Кроме того, в ряде работ дискретные
структуры применяются для построения макромоделей потоковых систем.
Наиболее известные работы по макромоделированию на дискретных структурах
разработаны Л.Р.Фордом,
Д.Р.Фалкерсоном, Э.В. Дейкстра, Д.Россом,
А.Е.Петровым и др. При этом следует отметить, что указанные модели не
учитывают неравномерность потоков (пробки на дорогах, простой оборудования,
скопление газа в шахте, образование тромбов в кровеносной системе и др.). Кроме
того, объективной проблемой является переход между моделями микроуровня и
моделями макроуровня, что отмечено в работах Г.Альтшуллера. В настоящее время
такой переход рассматривается в каждом конкретном случае на примере
конкретной предметной области (например, транспорт). Следует также отметить,
что модели микро- и макроуровня разрабатывались в различные периоды развития
вычислительной техники. Рассмотренное выше доказывает целесообразность
разработки подхода к проектированию потоковых систем, который позволил бы
обеспечить компьютерное моделирование таких систем в различных предметных
интерпретациях, переход между микроуровнем (потокообразующие объекты) и
4
макроуровнями (поток в целом) в компьютерном моделировании, обеспечить
получение на основе моделей различных характеристик потока и обеспечить его
визуализацию. Решением указанных проблем является разработка особого типа
дискретных структур.
В работе решается научная проблема структурно-параметрического синтеза
и анализа компьютерных моделей систем, исследование поведения которых
сводится к моделированию распространения потоков в них (потоковых систем), в
различных предметных интерпретациях в области промышленности и логистики,
обеспечивающих в рамках единой структуры моделирование с различными
уровнями детализации (микро- и макромоделирование).
Идея работы. Синтез и анализ моделей потоковых систем осуществляется
на основе нового типа дискретных структур (предложенных автором) –
квазиклеточных сетей, обеспечивающих моделирование в рамках единой
структуры потоковых систем на микро- и макроуровне независимо от предметной
интерпретации, их анализ и визуализацию данных. Следует отметить, что
квазиклеточные
сети
представляют
собой
дискретные
структуры,
ориентированные в первую очередь на использование в качестве математического
обеспечения компьютерного моделирования потоковых систем, независимо от
предметной интерпретации.
Объектом исследования являются потоковые системы промышленнологистического назначения.
Предметом
исследования
являются
подходы
к
структурнопараметрическому синтезу и анализу компьютерных моделей системных связей и
закономерностей
функционирования
потоковых
систем
промышленнологистического назначения на основе квазиклеточных сетей; а также к выработке
их предметных интерпретаций.
Цель работы: Разработка универсального подхода к структурнопараметрическому синтезу и анализу моделей потоковых систем на основе
квазиклеточных сетей, как дискретных структур, предполагающих интеграцию
моделирования на микро- и макроуровнях в рамках единой структуры, и
обеспечивающих
повышение
эффективности
разработки
специального
математического и программного обеспечения моделирования и анализа
потоковых систем промышленно-логистического назначения.
Задачи исследования:
 Анализ подходов к разработке моделей потоковых систем в различных
предметных областях. Установление общих принципов, характерных для
различных предметных интерпретаций (промышленность, логистика,
транспорт, информационные системы, биологические системы).
 Анализ подходов к представлению моделей потоковых систем. Выявление
преимуществ и недостатков существующих подходов.
 Разработка теоретических основ нового типа дискретных структур –
5
квазиклеточных сетей. Разработка динамических и статических аспектов
квазиклеточных сетей. Классификация квазиклеточных сетей.
 Разработка методов синтеза и анализа квазиклеточных сетей.
 Разработка подходов к применению квазиклеточных сетей для
представления моделей потоковых систем и проведения на их основе
модельного эксперимента.
 Автоматная формализация и программная реализация квазиклеточных сетей.
Методы исследования:
 общенаучные методы
◦ теоретические методы: абстрагирование (от предметной области); анализ
подходов к моделированию потоковых систем; индукция (обобщение);
метод аналогий;
◦ эмпирические методы: модельный эксперимент; метод дедукции
(сужение); функциональное моделирование.
 частнонаучные методы : теории графов; теории конечных автоматов;
клеточных автоматов; аналитической геометрии
Научные положения, выносимые на защиту:
1. Новый тип дискретных моделей системных связей и функционирования
потоковых систем – квазиклеточные сети, отличающиеся от существующих
возможностью моделирования в рамках одной дискретной структуры на
микро- и макроуровнях. Разработаны теоретические основы квазиклеточных
сетей (основные понятия, элементы структуры, динамические аспекты).
2. Подход к применению квазиклеточных сетей в задачах структурнопараметрического синтеза моделей структуры системных связей и
функционирования потоковых систем, позволяющий установить аналогии
элементов квазиклеточных сетей и методов их синтеза с моделируемыми
объектами в промышленных и логистических предметных интерпретациях.
3. Подход к проектированию специального алгоритмического обеспечения
синтеза и анализа моделей потоковых систем на основе квазиклеточных
сетей, представленный в виде IDEF0-модели логической организации
процесса проектирования инструментариев моделирования потоковых
систем.
4. Предметные интерпретации квазиклеточных сетей в задачах анализа
сложных систем: потоков людей на объектах массового их пребывания,
потоков в транспортной и промышленной логистике, систем
документооборота. Отдельно рассматриваются вопросы визуализации
информации на основе обработки результатов моделирования работы
квазиклеточных сетей.
5. Специальное
математическое
и
алгоритмическое
обеспечение,
представленное в виде моделей программной и физической реализации
работы квазиклеточных сетей: оценки алгоритмических аспектов,
6
моделирование работы квазиклеточных сетей на машинах Тьюринга и
конечных автоматах, программная реализация на принципах объектноориентированного подхода.
Обоснованность научных положений подтверждается:
1. Корректным применением теории множеств, теории графов и мографов,
теории конечных автоматов, теории клеточных автоматов, теории сетей
Петри, теории потоков в сетях, теории моделирования, уравнений
аналитической геометрии, теории автоматизированного проектирования
информационных систем, стандартов в области информационных
технологий.
2. Результатами внедрения математического и программного обеспечения,
полученного в ходе исследования, в практику разработки инструментариев
компьютерного
моделирования
потоковых
систем
промышленнологистического назначения.
3. Результатами экспертиз, проведённых при регистрации разработок в
Федеральном Институте Промышленной собственности (Роспатент) и
Объединённом Фонде Электронных Ресурсов «Наука и Образование»
Российской Академии Образования (бывш. Фонде Алгоритмов и Программ).
4. Результатами экспертизы заявки на получение гранта, а также отчётов по
гранту Российского Фонда Фундаментальных исследований (РФФИ).
Научная новизна результатов исследования:
 Впервые разработан новый тип дискретных структур, не имеющих явно
заданной сигнатуры и предполагающих в рамках единой модели реализацию
микро- и макромоделирования систем, поведение которых объясняется
распространением потоков в ограниченном пространстве.
 Впервые предложен подход к применению квазиклеточных сетей в задачах
структурно-параметрического синтеза и анализа компьютерных моделей
потоковых систем.
 Впервые предложены предметные интерпретации квазиклеточных сетей в
ряде областей, тесно связанных с моделированием потоковых систем в
промышленности и логистике.
 Впервые применены подходы к автоматной формализации работы
квазиклеточных сетей и разработки на их основе инструментариев
компьютерного моделирования и визуализации потоковых систем.
Теоретическая значимость работы: Разработаны новые методы и средства
моделирования и анализа функционирования потоковых систем на основе нового
типа дискретных структур, обладающих возможностями клеточных автоматов,
конечных автоматов, теоретико-графовых моделей, сетей Петри и позволяющих
представить в рамках единой модели структуру и функционирование потоковых
систем на микро- и макроуровне.
Практическая значимость работы: Разработанные дискретные структуры
7
являются основой специального математического, алгоритмического и
программного обеспечения инструментариев компьютерного моделирования,
анализа функционирования и визуализации потоковых систем в промышленных и
логистических предметных интерпретациях.
Соответствие диссертации паспорту научной специальности: Научные
результаты, выносимые на защиту, соответствуют пунктам 1 (результаты 1,2,3),
2(результаты 3,4), 5(результаты 3,5), 7(результат 2,3), 12(результат 4) паспорта
научной специальности 05.13.01 – Системный анализ, управление и обработка
информации.
Апробация работы: Основные результаты диссертационной работы обсуждались
и докладывались на: Международной экологической конференции «Горное дело и
окружающая среда» (2006,2007,2013); I Московской научно-практической
конференции «Студенческая наука» (2006); Неделе студенческой науки МГГУ
(2007-2012); Международном симпозиуме «Неделя Горняка» (2008,2012–2017);
Международной
научно-практической
конференции
"Научно-техническое
творчество молодежи - путь к обществу, основанному на знаниях" (2011 – 2014);
Всероссийской конференции «Нейрокомпьютеры и их применение» (2012 – 2017);
Научных семинарах кафедры САПР МГГУ, МИСиС (2008-2017); Научном
семинаре кафедры АСУ НИТУ МИСиС (2017); Научном семинаре «Проблемы
современных информационно-вычислительных систем», Мехмат МГУ им.
Ломоносова (2014); Специализированном научном семинаре «Квазиклеточные
сети и другие инструментарии проектирования и моделирования потоковых
систем» под руководством автора (2014-2016); Семинаре «IT и инновации в горном
деле» (2016); Всероссийской выставке «Научно-техническое творчество
молодёжи» (2011 – 2014); Всероссийском научно-инновационном конкурсе
«Innostar» (2013); III Международной конференции «Суперкомпьютерные
технологии математического моделирования» (2016); Международной школе
молодых учёных «Моделирование и оптимизация сложных систем» (MOCS 2016);
Летней школе «Materials and Technologies» (2016); Национальной научнотехнической конференции «Компьютерное моделирование 2017 (КОМОД-2017)»;
X Всероссийской Мультиконференции по проблемам управления (МКПУ-2017);
Научных семинарах ИПУ РАН им. В.А. Трапезникова (2017).
Разработки по тематике диссертационного исследования отмечены: Премией
для поддержки талантливой молодёжи (2011), медалью «За успехи в научнотехническом творчестве» (2013), медалью «Лауреат ВВЦ» (медалью ВДНХ) (2014),
дипломом международной экологической конференции «Горное дело и
окружающая среда» (2013); дипломом конференции «Нейрокомпьютеры и их
применение» (2014).
Кроме того, по тематике диссертационной работы проводится постоянно
действующий научный семинар «Квазиклеточные сети и другие инструментарии
проектирования и моделирования потоковых систем», зарегистрированный на
8
Общероссийском математическом портале (mathnet.ru), научный руководитель –
доц., к.т.н. Аристов А.О.
Разработки в области квазиклеточных сетей под руководством автора
выполнены при поддержке гранта РФФИ (проект №15-08-06453 А).
Реализация результатов исследований: Результаты
диссертационного
исследования используются и приняты к использованию в следующих
организациях:
 АО «Синетик» приняты к использованию рекомендации по проектированию
математического
и
программного
обеспечения
инструментариев
моделирования и визуализации потоковых систем в рамках PLM-систем.
Непосредственно приняты к использованию разработанные инструментарии
моделирования логистики песчаного карьера в рамках жизненного цикла
производства железобетонных изделий.
 ООО «Институт математических методов в дорожно-транспортных
исследованиях» (ИНЭМДорТранс) в качестве математического обеспечения
компьютерных систем поддержки принятия решений в области
транспортной и промышленной логистики.
 ООО «Разработка информационных систем» в качестве математического
обеспечения инструментария моделирования потоков посетителей объектов
массового пребывания людей на этапе проектирования указанных объектов;
 НИТУ «МИСиС» в учебном процессе по дисциплинам «Моделирование»,
«Геометрическое моделирование в САПР», «Проектирование систем»,
«Компьютерные системы принятия решений», «Математическая логика и
теория алгоритмов».
Публикации: Основные положения и результаты диссертационного исследования
опубликованы в 40 работах, в том числе 1 научной монографии (бумажная и
электронная версия),12 в изданиях, входящих в перечень ВАК, 1 в изданиях,
индексируемых в библиографической базе SCOPUS, 3 рецензируемых учебных
пособиях. Англоязычные версии публикаций представлены в международном
архиве научных публикаций ArXiv.org (Cornell University, США) и индексируются
специализированными базами NASA ADS (Гарвардский университет, США) и
«The collection of computer science bibliographies» (Карлсруэ, Германия).
Программные разработки и аналитические модели зарегистрированы как
объекты интеллектуальной собственности в ФГУ ФИПС и ОФЭРНиО ИУО РАО
(получено 4 авторских свидетельства).
Структура и объём диссертации: Диссертационная работа состоит из введения,
семи глав и заключения; включает в себя 18 таблиц, 91 рисунок, список
использованной литературы из 212 наименований и приложения.
Автор
выражает
благодарность
своему научному
консультанту
проф. Горбатову А.В., директору института ИТАСУ НИТУ МИСиС проф.
Калашникову Е.А., профессорам НИТУ МИСиС Петрову А.Е., Рябову Л.П.,
9
Куприянову В.В., Шкундину С.З., Кривоножко В.Е., Тёмкину И.О., Соколову С.М.,
Бабичеву Ю.Е., Шеку В.М., доцентам НИТУ МИСиС Протасову В.И., Фёдорову
Н.В., Танцову П.Н., Лычеву А.В., г.н.с. ИПУ РАН, д.т.н. Красновой С.А.,
профессорам МГУ Филимонову Н.Б., Васенину В.А., профессору МГППУ
Куравскому Л.С., сотрудникам ООО «ИНЭМДорТранс» Ерёмину В.М.,
Бадаляну А.М., Шевцову А.И., сотрудникам ООО «Разработка информационных
систем» Степанькову А.Ю., Комиссарову М.Ю., ген. директору АО «Синетик»
Салдаеву А.В..
Основное содержание работы
Во введении описана актуальность проблемы структурно-параметрического
синтеза и анализа компьютерных моделей потоковых систем в различных
предметных интерпретациях, определена цель и задачи исследования.
В первой главе проводится обзор различных аспектов структурнопараметрического синтеза компьютерных моделей потоковых систем в различных
предметных областях. Рассматриваются системы, предполагающие потоки и их
распространение в ограниченном пространстве и времени (далее – потоковые
системы). Проектирование и исследование потоковых систем, так или иначе,
рассматривалось в различные этапы развития важнейших отраслей деятельности
человека, таких как градостроительство, транспорт, промышленность, медицина,
оборона и др. Для потоковых систем моделирование является общенаучным
методом исследования, поддержки принятия решений, проектирования (синтеза и
анализа) и управления потоковыми системами в различных предметных областях.
Оценивается степень разработанности направления исследований потоковых
систем. Установлено, что поток обладает дуализмом (совокупность
взаимодействующих объектов и поток как объект), определяющим микро- и
макромоделирование. На практике модели микро- и макроуровня для потоков
строятся для каждой конкретной предметной области для конкретного уровня
детализации и учитывают только отдельные аспекты их динамики. В ряде случаев
применяется аналогия потоков в различных предметных областях. Объективно
существует проблема перехода между микро- и макромоделями потоковых систем.
Потребность в решении такой проблемы связана с нарушением адекватности
моделей при переходе между уровнями моделирования, а также потребностью
рассмотрения как потока в целом, так и локальных ситуаций на участке потоковой
системы.
Модели микро- и макроуровня разрабатывались в различные периоды
развития
вычислительной
техники.
Рассмотренное
выше
доказывает
целесообразность разработки подхода к проектированию потоковых систем,
который позволил бы обеспечить компьютерное моделирование таких систем в
различных предметных интерпретациях, переход между микроуровнем
(потокообразующие объекты) и макроуровнями (поток в целом) в компьютерном
моделировании, обеспечить получение на основе моделей различных
10
характеристик потока и обеспечить его визуализацию. Решением указанных
проблем является разработка особого типа дискретных структур.
Во второй главе даётся первоначальное представление о новом типе
дискретных структур, синтезируемых на основе графовой модели.
Пусть имеем граф G = < V , U > (рис. 1). Воспользовавшись тем, что каждая
вершина V i ∈{V 1 ,V 2 ,... , V n } имеет координаты (x i ; y i ) , т. е. x i ∈{x 1 , x 2 , ... , x n } ,
y i ∈{y 1 , y 2 , ... , y n } , выделим вокруг каждой вершины круглую область радиуса R .
Каждое ребро графа (V ia , V ib ) имеет длину:
L i =√ ( x ib − x ia )2+( y ib− y ia )2 .
(1)
Возьмём на каждом ребре (V ia , V ib ) точки с шагом 2 R . Вокруг каждой
R,
точки
выделим
область
радиуса
определяемую
неравенством:
2
2
2
( x ' −x c ) +( y ' − y c ) ≤ R , где x ' , y ' - координаты произвольной точки в заданной
области, x c , y c - координаты центра каждой области, лежащие на ребре (V ia , V ib ) .
Тогда каждое ребро (рис. 2) разбивается на некоторое количество областей
L
n=round (
) , где R - радиус области вокруг точки, лежащей на ребре, L 2⋅R
длина ребра, round(...) - округление до ближайшего целого.
R
xc,yc
Via
Vib
Рис. 1. Базовый граф
Рис. 2. Разбиение ребра исходного графа
dx
dy
Обозначим dx ' = , dy ' = , тогда для любой области p на ребре
n
n
(V ia , V ib ) справедливо x p= xia + p⋅dx ' , y p= y ia + p⋅dy '
Фактически области, центры которых лежат на рёбрах, расположены по
касательным друг к другу, тогда на ребре найдётся пара областей p и p+1 , для
которой система уравнений:
{
2
2
( x− x p ) +( y− y p) = R
2
2
2
( x−x p+1 ) +( y− y p+1) = R
2
будет иметь как минимум одно решение при p=1,2,3, … , n-1.
L
∉Z , то система уравнений:
Поскольку в общем случае n=
2⋅R
(3)
11
{
2
2
2
( x− x n) +( y− y n) = R
,
2
2
2
( x−x ib ) +( y− y ib ) = R
(4)
в общем случае имеет 2 решения.
Таким образом, получаем дискретную структуру, изображённую на рис. 3.
Исходя из этого, вводятся определения статической структуры координатной
квазиклеточной сети для двухмерного и трёхмерного случаев.
Определение. Статической структурой двухмерной координатной квазиклеточной
сети называется дискретная структура, включающая в себя множество
Q={Q1 , Q2 ,... , Qn } круговых областей в двухмерном пространстве, имеющих
радиус R, каждая из которых взвешена соответственно элементами из множеств
X ={x 1 , x 2 , ..., x n } , Y ={y 1 , y 2 , ... , y n } . Тогда для каждой Qu ∈Q найдётся хотя бы
Qv ∈Q ( u , v =1,2 , ... , n ; u≠v )
одна
такая,
что
выполняется
условие
(x u− x v )2+( y u− y v )2 ≤4R 2 .
Область, определяемую элементом множества Q={Q1 , Q2 ,... , Qn } в соответствии
с определением статической структуры называется элементом квазиклеточной
сети, областью или клеткой.
Определение статической структуры учитывают только топологические
свойства квазиклеточной сети, однако не учитывает её динамический аспект. В
плане учёта динамических аспектов квазиклеточных сетей, определения 1,2
следует расширить. Взвесим каждый Q p элементом S p , характеризующим
состояние каждой клетки Q p=(x p , y p , S p) :
S p ∈{S 1 , S 2 , ... , S M }
,
S p=( p1, p 2, ... , p L )
где p1, p2, ... , p L - фазовые переменные.
Рис. 3. Структура квазиклеточной сети
(5)
12
Вводится понятие состояния квазиклеточной сети как переменной
дискретной или непрерывная величина, которой взвешена каждая клетка
квазиклеточной сети.
Интуитивно понятным примером состояния квазиклеточной сети является
бинарное состояние S p ∈{0,1} , сравнимое с наличием «фишки» в клетке по
аналогии с сетями Петри. На примере бинарного состояния представляются
динамические аспекты квазиклеточных сетей, предполагающие изменение её
состояния во времени. Бинарное состояние клетки квазиклеточной сети
моделирует наличие в области пространства некоторого микрообъекта. Тогда
считаем, что состояние клетки определяется параметрами находящегося в ней
микрообъекта, а также переменными параметрами самой клетки, изменяющимися
под воздействием микрообъекта.
Таким образом, постоянные и переменные величины, которыми взвешена
каждая клетка, образуют структуру клетки квазиклеточной сети.
Определение. Структура клетки квазиклеточной сети – набор значений
переменных и констант, которыми взвешена каждая клетка квазиклеточной сети
Qi =(Bi ,C i , S i ) , где Bi =(B1, B2, ...) – неизменные (базовые) параметры клетки (от
англ. Basic) C i =(C 1, C 2, ...) , – параметры клетки, изменяющиеся при прохождении
объектов через клетку (от англ. Changeable), S i =(S 1, S 2, ...) – параметры объекта,
находящегося в клетке, т. е. переменные состояния (фазовые переменные) клетки
(от англ. State).
Динамический аспект квазиклеточных сетей предполагает изменение
состояния клеток квазиклеточных сетей с течением времени. Тогда для описания
динамического аспекта введём дискретное модельное время t =0, θ , 2 θ ,3 θ ,... ,
где θ =const .
Положим, что клетка Qu =( x u , y u , C u , S u ) , имеющая некоторое состояние
Su
передаёт указанное состояние соседней клетке Qv =( x v , y v , C v , S v ) ,
расположение которой
определяется для двухмерной квазиклеточной сети
условием:
(x u− x v )2+( y u− y v )2 ≤4R 2
(6)
,
определяемым элементами Bu =( Bu1 , Bu2 , ...) и B v =(Bv1 , Bv2 ,...) . Тогда условие
(6) является условием соседства клеток. Обобщим понятие о соседстве клеток.
Qu =( Bu1 , Bu2 , ... ,C u , S u)
Определение.
Условие
соседства
клеток
и
Qv =(B v1 , B v2 ,... , C v , S v ) – условие, определяемое предикатом соседства:
P (Qu , Qv )=P (B u1 , B u2 , ... , B v1 , B v2 ,...)=
{
0 , при ¬ f (B u1 , B u2 ,... , B v1 , B v2 , ...)
,
1 , при f ( B u1 , B u2 , ... , B v1 , B v2 , ...)
где
f (B u1 , Bu2 ,... , Bv1 , Bv2 ,...) – выражение, определяющее условие перехода.
Для двухмерной координатной квазиклеточной сети предикат соседства
13
Qu =( x u , y u , C u , S u ) и Qv =( x v , y v , C v , S v ) :
{
2
2
2
0 , при( x u −x v ) +( y u − y v ) >4R
P (Qu , Qv )=P ( x u , y u , x v , y v )=
2
2
2
1 , при( x u− x v ) +( y u− y v ) ≤4R
Для трёхмерной координатной квазиклеточной
Qu =( x u , y u , z u , C u , S u) и Qv =( x v , y v , z v , C v , S v ) :
{
сети
2
предикат
2
соседства
2
2
0 , при (x u − x v ) +( y u− y v ) +(z u− z v ) >4R
P (Qu , Qv )=P ( x u , y u , z u , x v , y v , z v )=
2
2
2
2
1 , при( x u −x v ) +( y u − y v ) +(z u− z v ) ≤4R
.
Между соседними клетками осуществляются переходы потокообразующих
состояний. Вводятся переходы для дискретных и непрерывных величин
состояния.
Qu → Q v
Определение. Переходом (передачей) дискретного состояния
квазиклеточной сети называется изменение состояний клеток, вида
{
{
S u (t)=S
S (t+θ )=S u (t)
→ v
,
P (Q u ,Q v )=1
S u (t +θ )=S
где
S–
некоторое
передаваемое
(потокообразующее) состояние, S – некоторое состояние, устанавливаемое после
передачи состояния S соседней клетке.
Для случая непрерывной величины потокообразующего состояния:
P (Qu , Qv )=1 →
{
S v (t+θ )=S v (t )+δ
, где δ – величина, на которую изменяется
S u (t+θ )=S u (t )−δ
величина состояния.
Пример передачи бинарного состояния между соседними клетками приведён
на рис. 4.
Рис. 4. Переход бинарного состояния между клетками
В масштабах квазиклеточной сети динамический аспект связан с понятием
«циркуляция». Вводятся понятия циркуляции для непрерывного и дискретного
состояний, как множество всех переходов, выполняемых каждый такт модельного
времени t =0, θ , 2 θ ,3 θ ,... .Кроме рассмотренных выше правил перехода,
связанных с потокообразующим состоянием, назначаются ограничивающие
условия, при выполнении которых происходит передача потокообразующего
состояния.
В соответствии с ограничивающими условиями определяются различные
14
типы циркуляции, предполагающие порядок передачи состояний. В работе
определены три типа циркуляции – случайная, направленная, микроциркуляция.
Определение. Случайной циркуляцией в квазиклеточной сети называется
циркуляция, при которой каждый из возможных (согласно определению переходов
и ограничивающих условий) переходов состояния Qu →Q vi осуществляется с
некоторой вероятностью р(Qu →Q vi ) , причём ∑ p(Qu →Q vi )=1 .
i
Пример передачи состояния при случайной циркуляции приведён на рис. 5.
Переходы осуществляются с вероятностями p(Qu → Q v ) , p(Qu → Q w) . В общем
случае для всех переходов состояния Qu →Q vi , где i=1,2 ,... , m и выполняется
условие соседства, справедливо
перехода: ∀i : p(Q u → Qvi )=
∑ p(Qu → Q vi )=1 .
i
В случае равновероятного
1
.
m
Рис. 5. Случайная циркуляция
Определение. Циркуляция в квазиклеточной сети называется направленной, в том
случае, если из всех возможных (согласно определению переходов и
ограничивающих условий) переходов состояния Qu →Q vi будет осуществляться
переход Qu → Q vk , где Qvk по некоторому критерию лучше других клеток Qi
удовлетворяет некоторому условию.
В случае двухмерной координатной квазиклеточной сети при возможности
осуществления передач состояния Qu →Q vi , где i=1,2 ,... , m состояние передаётся
в клетку, наиболее близкую по расстоянию к некоторой целевой точке (координате
( x vi − x с )2+( y vi − y с )2 (рис. 6).
√
точки): min
i
Qu
xc,yc
xc,yc
Qv
Qv
Qw Qu
Qw
Qv
Qu
Qw
xc,yc
Qv
Qu
Qw
xc,yc
Рис. 6. Примеры передачи состояния при направленной циркуляции
15
Определение. Микроциркуляцией в квазиклеточной сети называется циркуляция,
при которой в структуре каждой клетки содержатся данные, определяющие
направление передачи состояния.
Для двухмерной координатной квазиклеточной сети циркуляция, при
которой осуществляются переходы Qu → Q v , направления которых определяются
данными в структуре клетки Qu =( x u , y u , dx u , dxu , S u) , и для которой:
x v =x u+dxu
.
y v = y u +dyu
Рис. 7. Передача состояния при микроциркуляции
Структура каждой клетки дополняется величинами изменения координат в
заданном направлении (рис. 7): Qu =( x u , y u , dx u , dxu , S u) dx u= x v − x u , dy u= y v − yu
x v =x u+dxu
. Для микроциркуляции справедливо: y = y +dy
v
u
u
Определение. Микроциркуляцией со случайным выбором направлений
называется циркуляция, при которой осуществляются переходы Qu → Q v ,
направления
которых
определяются
данными
в
структуре
клетки
Qu =( x u , y u ,( dxv1 , dx v1 , p v1 ) ,(dx v2 , dxv2 , p v2 ) ,... , S u ) , где p v1 , p v2 ,... – вероятности
передачи состояния из данной клетки в Qv1 ,Q v2 ,... соответственно.
Структура каждой клетки дополняется величинами изменения координат в
каждом из заданных направлений и вероятностью перехода в них:
Qu =( x u , y u ,( dxuv , dx uv , p uv) , (dx uw , dx uw , p uw ) , S u )
.
Осуществляется по тем же правилам, что
и случайная циркуляция и
микроциркуляция (рис. 8).
Выше представлены наиболее разновидности циркуляции в квазиклеточных
сетях. Рассматриваемые типы циркуляции проходят дискретно с течением
модельного времени. Ещё ряд особенностей связан с разрешением перехода
состояний в клетки, содержащие «фишки». В этом случае устанавливается
ограничивающее условие:
S v (t)=S 0 ,
(7)
где S 0 – некоторое состояние, которое не передаётся соседним клеткам и
позволяет принимать состояние от другой клетки. Для случая бинарных состояний
это фактически обозначает отсутствие фишки. Если в сети с бинарным состоянием
16
при наличии «фишек» в клетку передаётся состояние от другой клетки («фишка»),
то возникает ситуация с потерей «фишек». Таким образом, очевидно
существование квазиклеточных сетей как с постоянным числом фишек и с
непостоянным. Указанные типы квазиклеточных сетей отличаются только
наличием ограничивающего условия (7).
Qv
Qu
Qu
Qw
Qv
Qv
Qw Qu
Qw
Рис. 8. Передача состояния при микроциркуляции со случайным
выбором направлений
Таблица 1. Классификация квазиклеточных сетей
Критерий классификации
Классификация
По условию передачи
состояния
 Сети постоянной циркуляции
 Условно-событийные

По типу циркуляции



Случайной циркуляции
Направленной циркуляции
Микроциркуляции
Смешанной циркуляции
По базовым параметрам
структуры клетки
 Двухмерные координатные
 Трёхмерные координатные
 и т.д.
По типу переменных
состояния
 С дискретным состоянием
 С непрерывным состоянием
 С постоянным числом фишек
По сохранению состояния
 С переменным числом фишек
 Сети суммирования
Работа квазиклеточной сети осуществляется тактами, т. е. с применением
дискретного модельного времени для реализации работы квазиклеточных сетей.
При этом происходит сканирование системы через каждый сколь угодно малый
промежуток времени θ на предмет изменения её состояния. В этом случае для
модельного времени справедливо:
t i =t 0 +i⋅θ ,
(9)
t i =t i−1+θ .
(10)
17
Рассмотренные типы циркуляции являются основной характеристикой
классификации (табл. 1) квазиклеточных сетей, приведённых в диссертации. Под
квазиклеточными сетями в общем случае понимается дискретная структура,
обладающая статическим (статическая структура) и динамическим (циркуляция)
аспектами. В классификации такие структуры названы квазиклеточными сетями
постоянной циркуляции. Кроме того, интуитивно понятным классом
квазиклеточных сетей являются условно-событийные сети, в которых циркуляция
определяется не модельным временем, а некоторыми условиями передачи
состояния (ограничивающими условиями). Несмотря на это, в рамках диссертации
рассматриваются именно сети постоянной циркуляции, поскольку идея условнособытийных квазиклеточных сетей мало отличается от принципов
функционирования сетей Петри.
В третьей главе рассматриваются подходы к построению статической
структуры квазиклеточной сети – методы синтеза. Также вводится ряд
специальных элементов, влияющих на циркуляцию в квазиклеточной сети.
Первоначально идея формирования квазиклеточных сетей как дискретных
структур представлена на основе графой модели, т. е. квазиклеточная сеть
синтезируется методом базового графа. Метод предполагает синтез структуры
квазиклеточной сети путём распределения клеток по рёбрам некоторого графа (см.
рис. 1), сравнивая который и квазиклеточную сеть, полученную методом базового
графа (см. рис. 3), нетрудно видеть, что квазиклеточная сеть фактически придаёт
динамические свойства базовому графу. Графовая модель является основой для
представления пространства распространения потоков в «потоках в сетях».
Подобные модели относятся к макромоделям потоков и не учитывают их
неравномерность, а также тот факт, что поток на микроуровне рассматривается как
совокупность объектов-частиц. В такой ситуации метод базового графа
применительно к макромоделям позволит перейти от макроуровня моделирования
к микроуровню.
Методом базового графа называется синтез структуры квазиклеточной сети
{
Q={Q1, Q 2, ...}
Qi =( x i , y i ,C i , S i )
, предполагающий построение круговых областей, центры
которых
лежат
на
прямолинейных
рёбрах
взвешенного
графа
G=〈{(V j , x j , y i )∣ j=1,2 ,... ,∣V∣}, U 〉 , т. е. :
∀ Qi ∈Q ∃ (V k ,V p ) ∣
i=1,2 ,...
{
M kp=1
xi− xk yi− yk
=
x p − x k y p− y k
,
где M – матрица смежности базового графа.
Рассмотренное выше показывает, что квазиклеточная сеть обладает схожими
свойствами с клеточными автоматами. Фактически, клеточный автомат
18
представляет собой растровую структуру, в которой каждая точка пространства
соответствует клетке. В квазиклеточных сетях не предполагается деление всего
пространства на клетки (фактически растеризация), поскольку клетки
распределяются по правилам, фактически обозначающим метод синтеза.
Следует отметить, что клеточный автомат соответствует определению
квазиклеточной сети, однако с точки зрения топологии существенно отличается от
квазиклеточных сетей, рассмотренных выше.
Пусть имеем область пространства, в которой построена дискретная
структура, отвечающая определению статической структуры квазиклеточной сети
и соответствующая периодической структуре клеточного автомата. Для удобства
идентификации, каждый элемент определяется двумя порядковыми номерами (i,j)
и имеет вид:
Q (ijK )=( x ij , y ij , S ij ) .
(10)
(K)
Рассмотрим подмножество Qij ' , для которого справедливо:
{
(K)
(K)
Qij ' ∈Qij
(K )
Qij ' ≠∅
(11)
.
Фактически, речь идёт об удалении из множества клеток, образующих
клеточный автомат, части элементов. Это позволяет синтезировать квазиклеточную
сеть на базе клеточного автомата (рис. 10). Описанный подход к синтезу,
предполагающий удаление части клеток клеточного автомата называется методом
битого клеточного автомата.
Рис. 10 Клеточный автомат и квазиклеточная сеть, синтезированная методом
битого клеточного автомата
Метод битого клеточного автомата – синтез структуры квазиклеточной сети
{
Q={Q1, Q 2, ...}
Qi =( x i , y i ,C i , S i )
,
предполагающий
построение
клеток,
являющихся
19
{
Q i ∈Q '
(K)
подмножеством вкрапления клеточного автомата Q ' ⊂Q .
Метод базового графа и метод битого клеточного автомата
устанавливают связь квазиклеточных сетей с другими дискретными
структурами. В работе рассмотрен метод синтеза, предполагающий
формирование структуры квазиклеточных сетей без использования других
дискретных структур. Основу метода составляет специальный микрообъект,
параметрами которого являются пространственные координаты x c , y c . Назовём
микрообъект
генерирующей
фишкой
или
генерирующей
клеткой.
Рассматриваемый микрообъект на каждой итерации совершает перемещение на
величины Δ x ci , Δ y ci соответственно по осям x , y . Тогда для координат на
каждой итерации справедливо:
x ci+1=x ci +Δ x ci ,
(12)
y ci+1= y ci + Δ y ci
(13)
На каждой итерации происходит формирование клетки квазиклеточной сети в
координатах генерирующей фишки(рис. 11):
Qi =(x сi , y сi , S i ) .
(14)
Рис. 11. Метод генерирующей фишки
Стоит отметить, что для того, чтобы расположение формируемых клеток
удовлетворяло определению квазиклеточной сети, требуется, чтобы расстояние
между координатами генерирующей фишки x ci , y ci и x ci+1 , y ci+1 на соседних
итерациях не превышало величину 2R , установленную для квазиклеточной сети,
т.е фактически, расстояние между соседними клетками не должно превышать 2R :
Δ 2 x ci +Δ 2 y ci ≤4R 2 .
(15)
Невыполнение условия (15) приведёт к получению структуры, не отвечающей
определению квазиклеточной сети. Условие (15) имеет вид неравенства. Также по
определению квазиклеточной сети не требуется касания круговых областей, а
возможен вариант с их пересечением. Однако, метод синтеза, рассмотренный
20
выше и основанный на динамике микрообъекта – генерирующей фишки позволяет
формировать квазиклеточные сети, не имеющие пересечений клеток. В такой
ситуации требуется, чтобы
Δ 2 x ci +Δ 2 y ci =4R 2
Метод генерирующей фишки –
{
Q={Q1, Q 2, ...}
,
Qi =( x i , y i ,C i , S i )
предполагающий
(16)
.
синтез структуры квазиклеточной сети
построение
круговых
(сферических)
областей с центрами в точках x ci , y ci , координаты которых формируются при
движении некоторого микрообъекта, моделируемого
материальной точкой
(генерирующей фишки или генерирующей клетки). На каждой итерации
генерирующая фишка перемещается на величины Δ x ci , Δ y ci соответственно по
осям x , y : x ci+1=x ci +Δ x ci , y ci+1= y ci + Δ y ci .
Рассмотренные методы синтеза квазиклеточных сетей, такие как метод
базового графа и метод генерирующей фишки при условии (16) допускали
пересечение клеток. Однако метод генерирующей фишки позволяет синтезировать
квазиклеточные сети, в которых не возникнет пересечения клеток. Тогда, для
достижения указанного свойства, каждая клетка
Qi =(x сi , y сi , S i )
(17)
должна отвечать не только условию (17), но и:
∀ j : √( x сi − x j )2+( y ci− y j )2=4R 2 .
(18)
Также стоит отметить, что значительную роль играет зависимость величин
Δ x ci , Δ y ci на каждой итерации. Фактически речь идёт о зависимостях вида:
{
Δ x ci =Δ x (i )
Δ y ci =Δ y (i)
(19)
.
В структуру клеточных квазиклеточных сетей входят также особые клетки
или группы клеток,
для которых характерны специфические особенности
функционирования, влияющие на циркуляцию в квазиклеточной сети. Те или иные
элементы фактически вносят некоторые изменения в рассмотренные выше
принципы синтеза и циркуляции в квазиклеточных сетях.
Наряду с рассмотренным методом битого клеточного автомата, структура
квазиклеточной сети предполагает области, являющиеся подмножеством
клеточного автомата – вкрапления клеточного автомата.
Определение. Вкраплением клеточного автомата в координатную квазиклеточную
сеть или элементом клеточного автомата координатной квазиклеточной сети, или
областью клеточного автомата называется множество Q( K )⊂Q , для каждой клетки
(K )
(K)
которого Q i ∈Q
найдётся не менее 2 клеток Q j ∈Q , удовлетворяющих
2
2
2
2
условиям: ( x i− x j ) =(2⋅R) , ( y i − y j ) =(2⋅R)
21
где Qi =(x i , y i , S i ) , Q j =( x j , y j , S j ) , при этом не существует Q p=(x p , y p , S p) ,
Q p ∈Q( K ) при
xi = x j
yi = y j
для
которой
или
справедливо
( x i− x p )2+( y i − y p )2<(2⋅R)2 .
Синтез квазиклеточных сетей, включающих в себя элементы клеточного
автомата рассмотрим как расширение метода базового графа. В этом случае
предполагается, что базовый граф дополняется областями, преобразуемыми в
подмножество клеток клеточного автомата (рис. 12). Фактически при синтезе
квазиклеточной сети предполагается заполнение области элементами
квазиклеточной сети согласно вкрапления клеточного автомата.
а
б
Рис. 12. Вкрапление клеточного автомата
а — базовый граф, б — структура квазиклеточной сети
Пусть имеем область клеточного автомата шириной w и длиной l . Тогда
при синтезе клеточного автомата целесообразно задавать множество клеток в виде
двухмерного массива, где каждая клетка
Q
(K)
ij
Q(ijK )∈Q( K )
=( x ij , y ij , S ij ) .
задаётся в виде:
-20
Считаем, что начало отсчёта области клеточного автомата находится в
координатах (x 0, y 0) , тогда координаты клетки имеют вид:
x ij =x 0+2R⋅i
.
y ij = y 0+2R⋅j
(21)
(22)
Исходя из соотношений (20), (21), (22) для базового графа (рис. 12а)
получаем структуру квазиклеточной сети, представленную на рис. 12б.
В клеточных автоматах возможна передача состояния в клетки окрестности
фон Неймана (по определению теории клеточных автоматов), что соответствует
циркуляции в квазиклеточных сетях (ограничиваемой предикатом соседства).
Однако если рассматривать окрестность Мура (по определению теории клеточных
автоматов), предполагается передача состояния между клетками, для которых не
выполняется предикат соседства. Такую передачу состояния назовём диагональной
циркуляцией. Считаем, что в зависимости от условия задачи и предметной
22
интерпретации квазиклеточных сетей диагональная циркуляция допустима при
рассмотрении элементов клеточных автоматов в квазиклеточных сетях, несмотря
на то, что указанный тип передачи состояния не соответствует определению
циркуляции в квазиклеточных сетях в части выполнения предиката соседства.
Одной из проблем синтеза модели методом базового графа является
нарушение связи клеток с ребром, на котором клетки были синтезированы (рис.
13). Также особое внимание следует уделить рёбрам, пересекающимся не в
вершинах. Учитывая специфику генерации квазиклеточной сети на основе
базового графа, на таких рёбрах имеет место наличие клеток, являющихся
соседними. В описанной ситуации циркуляция не соответствует смежности в
базовом графе, что приводит к неадекватному преобразованию моделей, в
частности, модели потоков в сетях в квазиклеточные сети. Такая ситуация
сравнима с медицинским явлением, называемым анастомозом, т.е естественным
или искусственным соустьем органов, имеющих полость. Подобное явление в
квазиклеточных сетях названо анастомозом по аналогии с медицинским
термином.
Рис. 13. Нарушение связи со структурой базового графа
Вводится понятие базового элемента клетки квазиклеточной сети, т. е. элемента
структуры квазиклеточной сети, на основе параметров которого синтезирована
клетка. В методе базового графа таким элементом является ребро, на котором
синтезирована клетка, обозначим как Qu ∈U i . В методе генерирующей фишки
базовым элементом клетки является клетка, синтезированная на предыдущей
итерации, обозначим как Qu ∈Qi .
Определение. Анастомозом в квазиклеточной сети называется пересечение
клеток, относящихся к различным базовым элементам. Рёберным анастомозом
будем считать пересечение клеток, относящихся к разным рёбрам базового графа
23
Qu=( x u , y u , S u )
Q v =( x v , y v , S v )
G =〈V ,U 〉 , т. е.
Qu ∈U i ;Qv ∈U j ;U i ≠U j .
( x u− x v )2+( y u− y v )2≤(2⋅R)2
{
Для решения проблемы рёберного анастомоза в квазиклеточной сети в
работе предложен хроматический подход, предполагающий введение
дополнительного базового параметра, фактически влияющего на предикат
соседства.
Каждая клетка приобретает определённый цвет в соответствии с цветом
базового элемента (рис. 14). При этом вершины базового графа позволяют
синтезировать клетки, переход из которых возможен в нескольких направлениях
без каких-либо ограничений, т.е. все такие вершины могут быть окрашены в один
отдельный цвет col 0 . Таким образом, раскраска рёбер базового графа позволяет
решить проблему анастомоза, возникающего вблизи вершин базового графа при
генерации. При этом каждая клетка приобретает цвет (рис. 14), т. е. в состав
вектора B i входит составляющая, определяющая цвет клетки: B i =( x i , y i , col i ) ,
где
col i ∈{col (0) , col( 1) , col (2) , ... , col (h)}
, h – хроматический класс базового графа
(0)
[9], col – цвет клеток, сформированных на основе вершин базового графа. Тогда
предикат соседства примет вид:
P (Q u , Qv )=P ( x u , y u , x v , y v )=
{
1 , при
{
(x u− x v )2+( y u− y v )2≤4R 2
[
col u=col v
(24)
col u=col (0)
0 , иначе
,
где col 0 – цвет клетки, синтезированной на вершине базового графа.
Рис. 14. Назначение красок элементам квазиклеточной сети
24
Определение. Анастомозом генерирующей фишки называется ситуация, при
которой генерирующая фишка, находящаяся на i-й итерации формирования
(x сi , y сi ) ,
квазиклеточной
сети
в
координатах
нарушает
условие:
2
2
2
∀ j : √( x сi − x j ) +( y ci − y j ) ≥4R .
Ещё ряд элементов квазиклеточных сетей являются разновидностями
клеток, предназначенных для генерации, задержки или поглощения состояния, и
оказывающих влияние на циркуляцию в квазиклеточной сети.
Определение. Генератором (источником) в квазиклеточной сети называется клетка
Q g =( Bg ,C g , S g (t)) , для которой справедливо S g (t+θ )=S g (t)+ f (t) , где f (t ) –
некоторая дискретная или непрерывная функция работы генератора.
В квазиклеточных сетях с дискретными состояниями генератор
предполагает формирование фишки в определённые моменты времени. При этом
сгенерированная фишка продолжает циркуляцию по сети. Отдельно
рассматривается проблема работы генератора в условиях циркуляции,
заключающаяся в необходимости установления ограничений для работы
генератора, уже занятого фишкой в процессе циркуляции.
Для сетей суммирования проблема генерации и циркуляции влияет на
количество фишек:
S g (t+θ )=S g (t)+ f (t) ,
(25)
где f (t ) – функция, определяющая количество генерируемых фишек в каждый
момент времени. В случае если клетка не является генератором, то для неё
f (t )=0 .
(26)
Тогда передача состояния при циркуляции в сетях суммирования в общем
случае примет вид:
S v (t+θ )=S v (t )+δ+ f v (t)
,
(27)
S u (t+θ )=S u (t )−δ+ f u (t)
где δ - количество фишек, передаваемое в каждый момент времени θ ( при
δ≤S u (t) )
Qu =( x u , y u , S u) и
Qv =( x v , y v , S v ) ,
для
где
( x u− x v )2+( y u− y v )2 ≤( 2⋅R)2
f u (t) , f v (t) – функции генерации,
определяющие количество генерируемых фишек в каждый момент времени.
В общем случае предполагается, что состояние клетки определяется не
одной переменной, а набором фазовых переменных, тогда для каждой из них
вводятся ограничения и функции генерации.
Определение. Стоком в квазиклеточной сети с бинарным состоянием называется
клетка Qo=(B o , C o , S o (t )) , для которой независимо от циркуляции справедливо
S o (t+θ )=0 .
Обобщая понятие стока для квазиклеточных сетей различных типов, следует
определить, какое состояние следует считать «обнулением» клетки. Это состояние
и
u≠v ,
25
будет принимать сток каждый момент времени, независимо от циркуляции в
квазиклеточной сети. Пусть S (0) – состояние, которое предполагает «обнуление»
{
Q o =( x i , y i , S)
S ∈ {S (0) , S ( 1) , ... }
S (t)=S (0)
клетки. Тогда для стока в общем случае справедливо:
.
Следует отметить аналогию генераторов и стоков в квазиклеточных сетях с
одноимёнными элементами теории потоков в сетях. Однако, в отличие от
указанных элементов, генераторы и стоки в квазиклеточных сетях характерны для
моделирования потоков на микроуровне.
Определение. Турникетом (или клеткой задержки циркуляции) в квазиклеточной
сети называется клетка, сохраняющая полученное в некоторый момент времени
состояние S k в течение времени τ .
Q(T )=( x T , y T , S T (t ) , t m+τ , O(T ) (t )) , S T (t)∈{S k , S k }
{
S T (t m )=S k
→
O T (t m )=1
{
O(T )(t m )=0
S T (t)=S k ∣ t m <t<t m +τ ,
O(T )(t m +τ )=1
где S k – состояние, которое сохраняет турникет в течение времени τ ; S k –
состояние (состояния), при нахождении в котором турникет открыт и из которого
происходит переход турникета в состояние S k ; t m - момент времени закрытия
турникета после перехода в состояние S k ; O(T ) – внутреннее состояние турникета
(открыт/закрыт) O (T )∈{0,1} .
Предполагается, что клетка-турникет способна задержать некоторое
состояние S k в течение времени τ . Считаем, что в момент времени i⋅θ клеткатурникет Q(T ) приняла состояние S k , т. е.
{
(T )
Q =(x T , y T , S T (t))
.
S T (i⋅θ)=S k
(28)
Тогда по определению указанное состояние клетки S T (t)=S k остаётся
t =i⋅θ ,(i+1)⋅θ ,(i+2)⋅θ , ... ,i⋅θ+τ . После наступления
неизменным при
конечного момента времени t =i⋅θ+τ осуществляется переход состояния из
клетки Q(T ) в соседнюю клетку, согласно правилам перехода.
Определим логику работы клетки-турникета. Пусть S k – состояние, которое
сохраняет турникет в течение времени τ ; S k – состояние (состояния), при
нахождении в котором турникет открыт и из которого происходит переход
турникета в состояние S k ; t m - момент времени закрытия турникета после
26
перехода в состояние S k ; O – внутреннее состояние турникета (открыт/закрыт)
O(T )∈{0,1} . Учитывая, что S T (t)∈{S k , S k } , клетка-турникет примет вид:
(T )
Q (T )=( x T , y T , S T (t ) , t m+τ , O (T )) .
(29)
Исходя из рассмотренного представим логику работы турникета (табл. 2).
Следует отметить, что турникет обеспечивает не только задержку состояния, но и
неравномерность циркуляции.
Для экспериментальной оценки работы квазиклеточных в каждую клетку
вводится параметр группы C - Changeable, изменение которого происходит в
процессе циркуляции. Примером такого параметра является счётчик,
осуществляющий вычисление количества «фишек», прошедших через заданную
клетку.
Определение. Счётчиком в квазиклеточной сети называется состояние, для
которого справедливо
{
S p (t )=S сч
→ С p (t +θ )=C p (t )+1 , где S сч – некоторое
S p (t +θ )=S сч
состояние (или множество состояний), наступление которого (которых)
фиксируется счётчиком, S сч – состояний для которых S сч∩S сч=∅ .
Следует отметить, что счётчик фактически является параметром самой
клетки, а не микрообъекта, находящегося в ней. Согласно описанному выше для
счётчика справедливо:
{
S p (t )=0
→ С p (t+θ )=C p (t )+1
S p (t+θ )=1
(30)
.
Выражение (30) показывает количество «фишек», прошедших через
заданную клетку за указанное время t+θ . Следует отметить, что для небинарных
состояний, счётчик позволяет фиксировать не количество «фишек», а количество
случаев возникновения некоторого состояния.
В
четвёртой
главе
рассматриваются
аспекты
моделирования
квазиклеточными сетями. Основным назначением квазиклеточных сетей является
моделирование систем (в различных предметных интерпретациях), рассмотрение
которых сводится к распространению потоков. В рамках единой структуры
осуществлять моделирование на микро- и макроуровне. При этом в качестве
параметров микромодели выступают элементы структуры клетки по определению.
Сравнивая квазиклеточные сети с «потоками в сетях», описанными в работах
Форда и Фалкерсона, нетрудно видеть, что в квазиклеточных сетях рёбра базового
графа разбиваются на клетки. В «потоках в сетях» макроскопические параметры
моделей, например величина потока, берутся для ребра в целом. Таким образом, в
квазиклеточных сетях на базе переменных величин отдельных клеток
вычисляются макроскопические параметры, характерные для элементов сетей,
образованных клетками. В качестве таких элементов выступают измерительные
участки Q(m) .
27
Таблица 2. Логика работы турникета
t
S T (t)
t m+τ
O(T )
t <θ⋅(i−1)
Sk
0
1
t =θ⋅(i−1)
Sk
0
1
t =θ⋅i
Sk
θ⋅i+τ
1
θ⋅i>t >θ ⋅i +τ
Sk
θ⋅i+τ
0
t =θ⋅i+τ
Sk
θ⋅i+τ
0
t =θ⋅i+τ +θ
Sk
0
1
Иллюстрация
QT
Q
T
Q
T
Q
T
Q
T
QT
Определение.
Измерительным
участком
подмножество клеток, для которых
квазиклеточной
сети
называется
{
Q( m)⊂Q
Qi ∈Q(m)
, на базе переменных
Qi =(Bi ,C i , S i )
параметров которых вычисляются макроскопические величины, характерные для
элементов сетей, образованных подмножествами клеток в каждый момент
модельного времени t m=m⋅θ .
Введём определения параметров, вычисление которых производится на
основе значений счётчиков.
Определение. Аддитивным макропараметром измерительного участка Q(m) :
{
Q( m)⊂Q
квазиклеточной сети называются величины вида:
Qi ∈Q(m)
Qi =(Bi ,C i , S i )
)
S (C
i (t m )=∑ C k (t m )
i
(S)
i
S (t m)=∑ S j (t m )
,
где
S j ∈S i
j=1,2 ,... ,
C k ∈C i
i
зафиксированный момент времени моделирования t m=m⋅θ .
k=1,2 ,... ,
tm –
28
Определение. Мультипликативным макропараметром измерительного участка
{
Q( m)⊂Q
Qi ∈Q(m)
квазиклеточной сети называются величины вида:
Q(m) :
Qi =(Bi ,C i , S i )
)
P(C
i (t m )=∏ C k (t m)
i
(S)
i
P (t m)=∏ S j (t m )
,
где
S j ∈S i
j=1,2 ,... ,
C k ∈C i
k=1,2 ,... ,
tm –
i
зафиксированный момент времени моделирования t m=m⋅θ .
На основе аддитивных и мультипликативных параметров производится
экспериментальная оценка потоков в квазиклеточной сети.
Пусть имеем квазиклеточную сеть, каждая клетка которой задана в виде:
Q p=(x p , y p ,С p , S p) ,
(31)
(F )
где S p – состояние клетки, С p – счётчик некоторых состояний S p , являющихся
породообразующими. Логика работы счётчика имеет вид:
{
(F )
S p (t)=¬S p
.
С p (t+θ )=C p (t)+1 при
(F)
S p (t+θ )=S p
(32)
Считая, что модельное время имеет вид:
t m=m⋅θ ,
(33)
где m=1,2 , ... и используя возможности счётчика, определим величину потока
через клетку Q p=(x p , y p ,С p , S p) за время моделирования T m :
(Q p )
(T m )=C p (T m ) .
В случае бинарного состояния:
ξ
(34)
Tm
ξ
(Q p )
(T m )=C p (T m )= ∑ S p (t m ) .
(35)
t m=0
При рассмотрении потоков на отдельных рёбрах базового графа и других
измерительных участках:
( m)
ξ (Q )(T m )=∑ ξ
Q
( Q p)
(m)
(T m ) .
(36)
Для бинарного состояния оценка величины потока имеет вид:
ξ
( m)
(Q )
Tm
(T m )=∑ ∑ S p (t m ) .
(37)
Q (m) t m=0
Предложенные зависимости (34)-(37) позволяют оценивать величины
потоков на измерительных участках квазиклеточных сетей. Для оценки потока
берутся счётчики всех клеток на измерительном участке. В качестве ещё одного
29
варианта оценки величины потока рассматривается участок, на котором
устанавливается вход(-ы) и выход(-ы). Примером подобного участка является
множество клеток, синтезированных на ребре базового графа U k :
{
) ( U ) (U )
Q(U )=(Q(U
1, Q 2, Q 3, ...)
k
k
k
k
)
)
Qi =(x (U
, y(i U ) ,С (U
, S (i U ) )
i
i
k
k
(U k )
Si
k
k
.
∈ {0,1}
(38)
(U k )
Q i ∈U k
U k =(V ia , V ib )
В такой постановке оценка потока предполагает количество «фишек»,
прошедших участок от входа к выходу.
На указанном ребре графа установим
счётчики Qвх и Qвых . Тогда величина потока на ребре в момент времени t ,
вычисляется по формуле:
ξ
(U k )
(U )
(U )
(t)=C вх (t)−C вых (t) .
k
(39)
k
Кроме того, приведены экспериментальные оценки математического
ожидания и дисперсии, основанные на результатах моделирования работы
квазиклеточной сети:
( m)
M [ ξ (Q
( m)
(m)
ξ (Q ) (T m )
)
,
(T m )]=
Tm
( m)
(40)
( m)
D [ ξ (Q )(T m )]=M [( ξ (Q ) (T m ))2]−M 2 [ ξ ( Q ) (T m )] .
(41)
В работе идеи квазиклеточных сетей изложены на основе координатных
квазиклеточных сетей. Фактически квазиклеточные сети предполагают:
 синтез дискретной структуры, определяемой как односортное множество с
ограничением параметров элементов, определяющих соседство этих
элементов;
 динамика, основанная на передаче состояния между соседними элементами,
предполагающая изменение параметров самих элементов и наличие
микрообъекта в каждом элементе;
 метрика, предполагающая измерение характеристик элементов и
микрообъектов в элементах. На базе измерений строится моделирование
потоков в квазиклеточных сетях.
По определению структуры клетки обобщением квазиклеточной сети
является дискретная структура, для которой при Bi =(B1, B2, ...) между
компонентами вектора Bi устанавливаются зависимости, определяющие свойства
элементов и предикат соседства. В расширенном представлении о квазиклеточных
сетях в качестве базовых параметров выступают параметры, не обязательно
являющиеся геометрическими координатами. В диссертации приводится пример
распространения потоков во времени. Также следует установить величину, в
30
соответствии с которой происходят передача состояния и циркуляция. В
координатных квазиклеточных сетях в качестве такой величины выступало время,
течение которого определялось дискретным шагом θ . В общем случае речь идёт о
некоторой величине t ' , называемой динамической характеристикой.
Определение. Динамической характеристикой квазиклеточной сети называется
величина t ' , изменяющаяся дискретно, с изменением которой производятся
переходы в квазиклеточной сети, т. е. формируются дискретно заданные величины
C i (t ' ) и S i (t ' ) .
По определению динамической характеристики передача состояния в
квазиклеточной сети для бинарного состояния имеет вид:
{
{
P ( Bi1 , Bi2 ,... , B j1 , B j2 , ...)=1
S (t ' +θ )=S i (t ' )
→ j
S i (t ' )=1
S i (t ' +θ )=0
.
В условиях непрерывных фазовых переменных (46) принимает вид:
P (B i1 , B i2 , ... , B j1 , B j2 ,...)=1 →
{
S j (t ' +θ )=S j (t ' )+δ
S i (t ' +θ )=S i (t ' )−δ
(42)
(43)
,
где δ – величина фазовой переменной, передаваемой за один такт изменения
динамической характеристики квазиклеточной сети θ .
Следует отметить, что в зависимости от целей моделирования (42) и (43)
дополняются ограничивающими условиями. Таким образом, квазиклеточные сети
в общем случае представляют собой динамические дискретные структуры,
предполагающие изменение состояния, управляемые некоторым параметром –
динамической характеристикой.
В пятой главе рассматриваются вопросы разработки предметных
интерпретаций квазиклеточных сетей. Вопросы синтеза моделей потоковых систем
на основе квазиклеточных сетей и проектирование на их основе программных
инструментариев моделирования представлены в виде функциональной модели,
разработанной в соответствии со стандартом IDEF0 (Р 50.1.028-2001). Первый
уровень декомпозиции представлен на рис. 15. Модель описывает логическую
организацию процесса представления проектирования модели, её реализации и
моделирования на основе квазиклеточных сетей. На этапах разработки (А1, А2)
предполагается тесное взаимодействие архитекторов и разработчиков средств
моделирования со специалистами в предметных областях с целью выработки
требований к представлению моделируемой системы в виде квазиклеточной сети.
На рис. 16 представлена модель процесса разработки модели на основе
квазиклеточной сети. В ней отражён порядок применения рассмотренных выше
теоретических аспектов, связанных с синтезом структуры и циркуляцией в
квазиклеточной сети. Применение
методов
синтеза
квазиклеточной
представлено на рис. 17. Предполагается, что методы базового графа, битого
31
клеточного автомата и генерирующей клетки используются совместно. Метод
базового графа предполагается использовать в тех случаях, когда области
распространения потока первоначально заданы в виде графа, метод битого
клеточного автомата и вкрапления клеточного автомата расширяют метод базового
графа областями пространства, являющимися до некоторой степени
периодическими.
Метод генерирующей фишки предполагает синтез структуры на основе
поведения некоторого микрообъекта и фактически определение траекторий, по
которым будет осуществляется распространение других подобных микрообъектов
потока.
AUTHOR:
PROJECT:
USED AT:
DATE: 06/10/13
REV:
NOTES: 1 2 3 4 5 6 7 8 9 10
C1
Техническое
задание
x
WORKING
DRAFT
RECOMMENDED
PUBLICATION
Теория квазиклеточных
C2
сетей
DATE CONTEXT:
READER
Описание
системы
I1
Определить
потоки
A1
Определить
структуру
системы
Требования
к структуре
сети
Динамическая
характеристика
A2
Построить
квазиклеточную
сеть
A3
P. 3
Потоки
системы
Реализовать
квазиклеточную
сеть программно
A4
A0
TITLE:
Моделировать систему
Экспериментальные
данные
O2
Провести
A5
Уточнения по
функционированию
сети
NODE:
O1
Участок для
измерений
Установить
измерительный
участок
Квазиклеточная
сеть
M1 Разработчик
средств
моделирования
Программный
инструментарий
моделирования
эксперимент
A6
M2
Оператор
системы
M3 моделирования
Интегрированная
среда разработки
NUMBER:
Рис. 15 Моделирование системы на основе квазиклеточных сетей
P. 2
32
AUTHOR:
PROJECT:
USED AT:
DATE: 06/10/13
REV:
NOTES: 1 2 3 4 5 6 7 8 9 10
C1 Техническое
задание
Требования
к структуре
сети
WORKING
DRAFT
RECOMMENDED
PUBLICATION
C2Теория квазиклеточных
сетей
Структура
клетки
(вектор)
Определить
структуру
клетки
I1
x
READER
DATE CONTEXT:
Направленная
циркуляция
A31
Динамическая
характеристика
Определить
динамическую
характеристику
Потоки
системы
I2
O1
A32
Тип циркуляции
Определить
тип
циркуляции
Метод
синтеза
A33
Выбрать
метод
синтеза
A34
Структура
сети
Квазиклеточная
сеть
Построить
структуру
сети
Уточнения по
функционированию
сети
I3
A35
P. 4
O2
Установить
дополнительные
элементы
A36
Разработчик
средств
M1
моделирования
NODE:
TITLE:
A3
Программный
инструментарий
моделирования M2
Дополнительные
элементы
квазиклеточной
сети
NUMBER:
Построить квазиклеточную сеть
P. 3
Рис. 16. Проектирование квазиклеточной сети
AUTHOR:
PROJECT:
USED AT:
DATE: 06/10/13
REV:
NOTES: 1 2 3 4 5 6 7 8 9 10
Метод
C1 синтеза
Метод
базового
графа
Требования
к структуре
сети
I1
Построить
базовый
граф
A351
x
WORKING
DRAFT
RECOMMENDED
PUBLICATION
C2
Метод
битого
клеточного
автомата
Базовый
граф
A352
Уточнения по
функционированию
сети
I2
DATE CONTEXT:
Теория квазиклеточных
сетей
Метод
генерирующей
фишки
Синтезировать
сеть методом
базового графа
READER
Структура
сети
O1
Элемент
сети
Построить сеть
методом
генерирующей
фишки A353
Элемент
клеточного
автомата
Построить
элемент
клеточного
автомата
A354
Построить
методом
битого
клеточного
автоматаA355
Решить
проблему
анастомоза
A356
NODE:
A35
TITLE:
M1
M2
Разработчик
средств
моделирования
Программный
инструментарий
моделирования
Построить структуру сети
NUMBER:
Рис. 17. Синтез структуры квазиклеточной сети
P. 4
33
Предметная интерпретация квазиклеточных сетей сводится к установлению
связи их элементов (клеток, генераторов, стоков, турникетов и др.) с объектами
предметной области. В диссертации рассмотрены примеры моделирования
потоковых систем. Задача разработки инструментария моделирования потоков
людей на объекте массового пребывания (рис. 18) предполагает представление в
виде квазиклеточной сети пространства объекта и рассмотрение во времени
поведения потоков людей. В качестве клетки берётся область пространства объекта
массового пребывания. Моделирование потоков на объектах массового пребывания
осуществляется с целью оценки нагрузки на отдельные участки объекта, оценки
времени прохождения турникет, оценки времени эвакуации и др.
Павильон
Внутренняя
площадка
Турникеты
Внешняя
площадка
Рис. 18 Представление объекта массового пребывания людей в виде
квазиклеточной сети
Инструментарий моделирования используется в качестве средства
поддержки проектных решений в процессе проектирования объектов массового
пребывания и выработки мер безопасности при возникновении чрезвычайных
ситуаций.
Ещё ряд приложений квазиклеточных сетей – моделирование ситуаций в
транспорте и логистике. В этом случае в качестве клетки используется область
маршрута (дороги) перевозки. На рис. 19 приведён пример квазиклеточной сети,
предназначенной для моделирования транспортировки руды в карьере. Структура
клетки предполагает наличие и параметры транспортного средства (самосвала) в
заданной области пространства. Турникет интерпретируется как погрузчик,
задержка на турникете как наполнение самосвала.
Квазиклеточные сети обеспечивают возможности для визуализации, как
процесса, так и результатов моделирования. По имеющимся координатам клеток
строятся
соответствующие
потокообразующие
микрообъекты.
Пример
визуализации потоков людей на объекте массового пребывания представлен на
рис. 20a. На рис. 20б представлена тепловая карта, построенная на основе
счётчиков состояния на модели объекта массового пребывания людей.
34
а
б
Рис. 19 Представление транспортной логистики карьера
а — базовый граф квазиклеточной сети (маршруты движения самосвалов)
б — квазиклеточная сеть с элементами
35
а
б
Рис. 20 Визуализация потоков людей на объекте массового пребывания людей
a – визуализация отдельных посетителей,
б – тепловая карта, построенная на основе моделирования
В шестой главе рассмотрена практическая реализация работы
квазиклеточных сетей на примере нескольких подходов – моделирования
циркуляции на машине Тьюринга, представление работы квазиклеточной сети в
виде комбинации управляющего и операционного автоматов («Глушковский»
подход).
Моделирование циркуляции на машины Тьюринга производится с целью
оценки соответствия циркуляции в квазиклеточных сетях понятию алгоритма (в
соответствии с тезисом Тьюринга). В работе обосновано применение
специфической конструкции машин Тьюринга, работающих на маркированных
лентах, либо многоленточные варианты. Ленты в машины Тьюринга хранят
данные о состоянии клеток, две управляющие головки устанавливаются в
соответствующие наборы данных для клеток Qu и Qv с целью установления
предиката соседства и возможности осуществления перехода Qu → Q v .
«Глушковский» подход является основой для программной и физической
реализации. Структура операционного автомата приведена на рис. 21. Для
реализации работы квазиклеточной сети используются блоки памяти для хранения
параметров структуры клетки, блоки проверки состояния клеток, блок проверки
предиката соседства. Поскольку для реализации циркуляции необходимо течение
модельного времени, используется таймер. Кроме того, поскольку при реализации
переходов проверяется пара клеток, используются два счётчика. Для
управляющего автомата в диссертации представлены циклограмма и граф
переходов. Для более удобного представления граф переходов представлен в виде
диаграммы состояний UML (рис. 22).
Следует отметить, что простейшей реализацией «Глушковского» подхода
36
является программная реализация квазиклеточной сети на принципах объектноориентированного программирования, где блоки памяти представлены в виде
полей классов, моделирующих работу квазиклеточных сетей, а граф переходов
описывает логику их работы (методы классов). Таким образом, применение
автоматного подхода к моделированию квазиклеточной сети составляет
теоретическую основу проектирования программной и физической реализации
работы средств моделирования. На основе разработанных автоматных моделей
построено специальное программное обеспечение синтеза и анализа работы
квазиклеточных сетей.
S[cч1], S[сч2]
сч1+1, сч1=1
сч2+1, сч2=1
сч2
сч1
Сч.
кл. 2
Запуск проверки
условия соседства
Сч.
кл. 1
X[сч1],Y[сч1],
X[сч2], Y[сч2]
Блок
памяти
X,Y
Блок
состояний
S[сч1],
S[сч2]
Блок
проверки
единичного
состояния
Блок
проверки
условия
соседства
B
Управл яю щ ий
а в то м а т
Запуск проверки
единичного состояния
A1, A2
t+1
Таймер
Рис. 21 Комбинация операционного и управляющего автоматов
37
Рис. 22 Граф переходов, описывающий циркуляцию в квазиклеточной сети
В седьмой главе рассмотрены рекомендации по практическому применению
квазиклеточных сетей, реализованных программно. Рассмотрены возможности
программного комплекса синтеза и анализа работы квазиклеточных сетей.
Программный комплекс обеспечивает синтез квазиклеточной сети методами
базового графа, битого клеточного автомата, генерирующей клетки, а также ручное
распределение клеток в структуре квазиклеточной сети. Для построенной
структуры квазиклеточной сети устанавливаются элементы – генераторы, стоки,
турникеты и т. д. С применением программного комплекса промоделированы
некоторые распространённые ситуации в потоковых системах – неравномерное
движение потокообразующих объектов, использование нескольких стоков и
генераторов, моделирование очередей, заторов и т. п.
В качестве предметного примера приведена разработка инструментария
моделирования песчаного карьера (см. рис. 19). На примере показаны возможности
квазиклеточных сетей в задачах моделирования и визуализации работы песчаного
карьера, оценка объёмов добытой руды, имитация аварийных ситуаций (остановка
самосвала) и др.
Оценивается адекватность моделей на основе квазиклеточных сетей.
Поскольку в рамках единой модели рассматриваются параметры микро- и
макроуровней, то для квазиклеточной сети адекватность в отношении цели
моделирования является требованием к структуре клетки (набору параметров), а
не предметом её оценки. В рамках единой модели в зависимости от интерпретации
рассматриваются характеристики потоковых систем микро- и макроуровня.
Приведены характеристики, получаемые из единой модели для выбранной
предметной области (табл.3). Следует также отметить, что ещё ряд характеристик
сводятся к моделированию аддитивных и мультипликативных параметров
квазиклеточной сети.
В табл. 3 отметим аналогию между параметрами микро- и
макромоделирования в различных предметных интерпретациях. Указанная
аналогия позволяет оценить применимость квазиклеточных сетей в задачах
моделирования потоковых систем, для которых поток представляется как
направленное движение некоторых материальных объектов.
Границы применения квазиклеточных сетей тесно связаны с масштабами
потокообразующих микрообъектов их количеством, объёмом памяти ЭВМ,
необходимой для представления микрообъектов. Так, в части количественных
оценок реализации квазиклеточных сетей, в работе приводится оценка объёма
памяти для представления клеток, а также емкостная сложность работы
квазиклеточных сетей, представленной в виде графа переходов в шестой главе.
Установлено, что для кодирования состояний автомата, моделирующего
квазиклеточную сеть, требуется 4 бита, для кодирования микрокоманд — 5 бит.
Временная сложность при реализации работы квазиклеточной сети, состоящей из
38
2
N клеток составляет
N
−N .
2
Таблица 3. Моделируемые характеристики потоковых систем
Предметная
область
Моделируемые характеристики
На микроуровне
На макроуровне
- Количество транспортных средств в
- Координаты транспортного карьере в текущий момент времени;
средства в выбранный
- Количество транспортных средств,
момент времени;
прошедших карьер за время
- Состояние самосвала в
моделирования;
выбранный момент времени; - Расход топлива;
Логистические
- Количество самосвалов,
- Среднее время ожидания в очереди;
потоки в карьере
пошедших через область
- Среднее количество в очереди;
пространства за время;
- Среднее количество транспортных
- Расположение
средств на участке;
транспортных средств
- Объём песка/руды, вывезенный за время
(визуально).
моделирования;
- Нагрузка на участки карьера (визуально).
- Координаты транспортного
Транспортные средства в выбранный
потоки (кроме момент времени;
трубопроводного - Расположение
транспорта)
транспортных средств
(визуально).
- Интенсивность потока;
- Плотность потока;
- Среднее время ожидания (терминалы,
светофоры и т. д.);
- Среднее количество транспортных
средств в очереди;
- Нагрузка на участки карьера (визуально).
- Местоположение
(координаты) единицы
сырья/полуфабриката/
продукта в выбранный
Потоки в
момент времени;
логистике
- Количество единиц
(продукты,
продукта через область
полуфабрикаты)
пространства за время;
- Наполнение участка
технологической схемы
(визуально).
- Количество обрабатываемых единиц
продукта в текущий момент времени
- Производительность (количество единиц
сырья/полуфабриката/
продукта, прошедших технологическую
схему за время)
- Среднее время ожидания в очереди на
обслуживание
- Среднее количество в очереди на
обработку
- Среднее время простоя оборудования
Нагрузка на участки технологической
схемы (визуально)
- Координаты человека в
толпе в выбранный момент
времени
Потоки людей - Количество людей,
(в т.ч. эвакуация) прошедших через область
пространства за время
- Состояние потока людей
(визуально)
- Количество людей на объекте в текущий
момент времени
- Среднее время ожидания в очереди
- Среднее количество в очереди
- Среднее время ожидания в очереди
- Среднее количество людей на выбранном
участке
- Нагрузка на помещения (визуально)
39
Заключение
В результате диссертационного исследования решена проблема структурнопараметрического синтеза и анализа компьютерных моделей потоковых систем в
различных предметных интерпретациях в области промышленности и логистики,
обеспечивающих в рамках единой структуры моделирование на различных
уровнях детализации (микро- и макромоделирование). Установлено, что таким
типом моделей являются модели на основе квазиклеточных сетей. Разработаны
теоретические аспекты квазиклеточных сетей – синтез структуры, циркуляция,
специфические элементы. Рассмотрены вопросы практического применения
квазиклеточных сетей при разработке инструментариев моделирования и анализа
потоковых систем.
Практическое применение квазиклеточных сетей направлено на повышение
эффективности разработки специального математического и программного
обеспечения моделирования и анализа потоковых систем промышленнологистического назначения. Разработанные модели организации процесса
моделирования квазиклеточными сетями и модели работы программных средств
моделирования, предназначены для использования при проектировании
специального программного обеспечения синтеза и анализа моделей потоковых
систем промышленно-логистического назначения.
В результате исследований лично автором получены следующие основные
выводы и результаты:
1. Разработан новый тип дискретных структур – квазиклеточные сети, описаны
их теоретические основы: синтез,
(генераторы, стоки, турникеты,
трансформаторы, элементы клеточных автоматов); методы синтеза
квазиклеточных сетей метод базового графа, метод битого клеточного
автомата, метод генерирующей фишки; метрические оценки потоков в
квазиклеточных сетях.
2. Разработаны подходы к установлению связи между микро- и
макромоделированием в рамках квазиклеточных сетей (измерительный
участок, аддитивные и мультипликативные макропараметры, метрические
оценки потоков), синтез квазиклеточных сетей на основе макромоделей
(метод базового графа).
3. Установлена связь квазиклеточных сетей с другими дискретными
структурами – графами, сетями, клеточными автоматами, конечными
автоматами и др.
4. Разработан общий подход к проектированию инструментариев
моделирования и анализа поведения потоковых систем на основе
квазиклеточных сетей, представленный в виде модели проектирования и
применения средств моделирования в соответствии со стандартом IDEF0.
5. Предложены предметные интерпретации квазиклеточных сетей в задачах
моделирования потоков людей на объектах массового их пребывания,
40
потоков в транспортной и промышленной логистике, систем
документооборота.
6. Разработаны подходы к визуализации процесса моделирования потоковых
систем и его результатов на основе квазиклеточных сетей.
7. Программная и физическая реализация работы квазиклеточных сетей,
основанная на принципах теории конечных автоматов. Представление
работы квазиклеточной сети на машине Тьюринга доказывает
справедливость использования термина «Алгоритм» применительно к
циркуляции в ней. Представление квазиклеточных сетей в виде комбинации
операционного и управляющего автоматов является основой их
программной и физической реализации.
8. Разработано информационное и программное обеспечение инструментариев
моделирования и визуализации и анализа работы квазиклеточных сетей (без
приложения к конкретной предметной области), зарегистрированные в
установленном порядке как объекты интеллектуальной собственности.
9. Результаты диссертационного исследования апробированы и использованы в
практике работы АО «Синетик», ООО «Разработка информационных
систем», ООО «Институт экономико-математических методов в дорожнотранспортных исследованиях» о чём имеются акты о внедрении.
10. Качественный эффект от внедрения инструментариев моделирования на
основе квазиклеточных сетей заключается в возможностях моделирования в
рамках единой структуры потоковых систем на микро и макроуровнях на
различных этапах жизненного цикла продукции (с учётом многосортности
потоков), транспортных потоков, потоков на объектах массового пребывания
людей (сочетание уровней моделирования и визуализации, многосортность).
11. Количественный эффект заключается в снижении себестоимости разработки
программного обеспечения моделирования потоковых систем на 5%,
времени моделирования на 20% (для потоков на объектах массового
пребывания людей) прогнозируемое снижение стоимости разработки на 25%
(для транспортно-логистических систем), сокращении времени разработки
на 12% (для потоков на объектах массового пребывания людей).
12. На основе результатов диссертационного исследования разработаны
учебные
пособия
и
лабораторные
работы
по
дисциплинам
«Моделирование»,
«Геометрическое
моделирование
в
САПР»,
«Проектирование систем», «Компьютерные системы поддержки принятия
решений», «Математическая логика и теория алгоритмов».
Основные положения диссертационного исследования опубликованы в
следующих работах:
В изданиях, входящих в перечень ВАК РФ:
1. Аристов А.О. Квазиклеточные сети. Синтез и циркуляция // Горный
информационно-аналитический бюллетень (научно-технический журнал)
41
Mining Informational and analytical bulletin (scientific and tecnical journal). М.:Издательство «Горная книга». - 2013. - №2. - С.125-131
2. Аристов А.О. Циркуляция в квазиклеточных сетях и их классификация //
Горный информационно-аналитический бюллетень (научно-технический
журнал) Mining Informational and analytical bulletin (scientific and tecnical
journal). - М.:Издательство «Горная книга». - 2013. - №9. - С.188-194
3. Аристов А.О. Об элементах квазиклеточных сетей // Горный
информационно-аналитический бюллетень (научно-технический журнал)
Mining Informational and analytical bulletin (scientific and tecnical journal). М.:Издательство «Горная книга». - 2013. - №11. - С.322-332
4. Аристов А.О. Квазиклеточные сети и их приложения в задачах
моделирования посетителей объектов массового пребывания людей //
Компьютерные исследования и моделирование, 2014, т. 6, № 2, С. 285-294
5. Аристов А.О. Особенности моделирования потоковых систем на основе
квазиклеточных сетей с использованием структурной методологии
проектирования // Информационные технологии, 2014, № 6, С. 43-51
6. Аристов А.О. Квазиклеточные сети в общей постановке // Горный
информационно-аналитический бюллетень (научно-технический журнал)
Mining Informational and analytical bulletin (scientific and tecnical journal). М.:Издательство «Горная книга». - 2014. - №12. - С.224-227
7. Аристов А.О. Квазиклеточные сети. Микро- и макромоделирование //
Горный информационно-аналитический бюллетень (научно-технический
журнал) Mining Informational and analytical bulletin (scientific and tecnical
journal). - М.:Издательство «Горная книга». - 2014. - №12. - С.228-233
8. Аристов А.О. Метрические оценки потоков в квазиклеточных сетях //
Горный информационно-аналитический бюллетень (научно-технический
журнал) Mining Informational and analytical bulletin (scientific and tecnical
journal). - М.:Издательство «Горная книга». - 2015. - №1. - С.243-250
9. Аристов А.О. Геометрическое моделирование и визуализация данных
моделирования в квазиклеточных сетях // Научная визуализация (Scientific
Visualization) №5'2014 – С.81-87.
10.Ерёмин В.М., Аристов А.О. Компьютерные системы поддержки принятия
решений по управлению транспортными потоками на автомобильных
дорогах // Горный информационно-аналитический бюллетень (научнотехнический журнал) Mining Informational and analytical bulletin (scientific
and tecnical journal). - М.:Издательство «Горная книга». - 2011. - №11. С.341-344 Личный вклад : аспекты проектирования и синтеза
компьютерных моделей логистических систем в составе СППР
11. Аристов А.О. О некоторых приложениях квазиклеточных сетей в задачах
компьютерного
моделирования
потоковых
систем
//
Горный
информационно-аналитический бюллетень (научно-технический журнал)
42
Mining Informational and analytical bulletin (scientific and tecnical journal). М.:Издательство «Горная книга». - 2017. - №4. - С.205-217
12. Аристов А.О. Теоретические и прикладные основы применения
квазиклеточных сетей в компьютерном моделировании и визуализации
транспортной логистики песчаного карьера // Горный информационноаналитический
бюллетень
(научно-технический
журнал)
Mining
Informational and analytical bulletin (scientific and tecnical journal). М.:Издательство «Горная книга». - 2018. - №1. - С.201-214
Монография:
13. Аристов А.О. Теория квазиклеточных сетей : научная монография — М:
МИСиС, 2014. — 188с. ISBN 978-5-600-00320-0
Учебные пособия:
14. Аристов А.О. Практическое руководство по моделированию потоковых
систем квазиклеточными сетями : учебное пособие — М: МИСиС, 2015. —
132с.
15. Калитин Д.В., Аристов А.О. Геометрическое моделирование САПР :
учебное пособие. М.:МГГУ,2011 — 145с. Личный вклад : разработка
разделов по вопросам геометрического моделирования систем частиц,
визуализации двух- и трёхмерных объектов
16. Аристов А.О., Моргачёв К.В., Рябов Л.П., Суворов А.В., Фёдоров А.М.
Компьютерные системы поддержки принятия решений — М: МГГУ, 2012.
— 172с. Личный вклад : разработка разделов по вопросам проектирования
иинструментариев моделирования и синтеза моделей в логистической
предметной интерпретации
В других изданиях:
17. Аристов А.О., Романов Д.Ю. Графические методы построения
экологических карт. Экологическая безопасность как ключевой фактор
устойчивого развития. Сб. Докладов / Одиннадцатая международная
экологическая конференция студентов и молодых учёных. Москва, МГГУ.
2007 г. Том 2. - Смоленск, Ойкумена, 2007. - C. 58-61 Личный вклад :
аспекты визуализации пространственно распределённых данных в цветовой
шкале.
18. Аристов А.О. Квазиклеточные сети. Теоретическая база и программный
инструментарий моделирования
// Хроники объединенного фонда
электронных ресурсов «Наука и образование», № 11(42), 2012 – C.25 –
режим доступа: http://ofernio.ru/portal/newspaper/ofernio/2012/11.doc
19. Аристов А.О. Квазиклеточные сети. Проблемы моделирования и обучения //
XI Всероссийская научная конференция «Нейрокомпьютеры и их
применение». Тезисы докладов.–М: МГППУ, 2013. –C.95-96
20. Аристов А.О. Теория квазиклеточных сетей и её приложения //
Всероссийская выставка Научно-технического творчества молодёжи. II
43
Международная научно-практическая конференция «Научно-техническое
творчество молодёжи — путь к обществу, основанному на знаниях»:сборник
научных докладов/ Мос. гос. строит. ун-т - М.:МГСУ,2013 — C.230-234
21. Аристов А.О. Квазиклеточные сети и их предметные интерпретации в
задачах моделирования транспортной логистики открытых горных работ //
Всероссийская выставка Научно-технического творчества молодёжи. II
Международная научно-практическая конференция «Научно-техническое
творчество молодёжи — путь к обществу, основанному на знаниях»:сборник
научных докладов/ Мос. гос. строит. ун-т - М.:МГСУ,2013 — C.165-168
22. Аристов А.О. Методы синтеза квазиклеточных сетей // Научный вестник
МГГУ. - 2013. - № 9 (42). - C. 16-21
23. Аристов А.О. Модель проектирования, разработки и внедрения моделей
систем на основе квазиклеточных сетей // Хроники объединенного фонда
электронных ресурсов «Наука и образование», № 10(53), 2013 – C.22 –
режим доступа: http://ofernio.ru/portal/newspaper/ofernio/2013/10.doc
24. Аристов А.О. Потоки в квазиклеточных сетях // Устойчивое инновационное
развитие: проектирование и управление. — Электрон. журн. — 2013. —
№3(20)— C.36-41 — Режим доступа: http://www.rypravlenie.ru/?p=1523
25. Аристов А.О. Квазиклеточные сети как обучаемые структуры // Научный
вестник МГГУ. - 2013. - № 10 (43). - C. 8-13
26. Аристов А.О. О многосортности потоков в квазиклеточных сетях //
Научный вестник МГГУ. - 2014. - № 1 (46). - C. 8-14
27. Аристов А.О. Моделирование циркуляции в квазиклеточных сетях на
машине Тьюринга // Всероссийская выставка Научно-технического
творчества молодёжи. II Международная научно-практическая конференция
«Научно-техническое творчество молодёжи — путь к обществу,
основанному на знаниях»:сборник научных докладов/ Мос. гос. строит. ун-т
- М.:МГСУ,2014 — С.223-227
28.Аристов А.О. Программная реализация квазиклеточных сетей //
Всероссийская выставка Научно-технического творчества молодёжи. II
Международная научно-практическая конференция «Научно-техническое
творчество молодёжи — путь к обществу, основанному на знаниях»:сборник
научных докладов/ Мос. гос. строит. ун-т - М.:МГСУ,2014 — С.228-234
29. Аристов А.О. Анастомоз в квазиклеточных сетях [Электронный ресурс] //
Международный журнал. Устойчивое развитие: наука и практика. —
Электрон. Журн. — 2014. — №2(13) — С.164-168 — Режим доступа:
http://www.yrazvitie.ru/?p=1545
30. Aristov A.O. The quasi cellular nets-based models of transport and logistics
systems // REPORTS OF THE XXIII INTERNATIONAL SCIENTIFIC
SYMPOSIUM «MINER'S WEEK – 2015» - Moscow : National University of
Science and Technology “MISIS”. – PP. 280-287
44
31. Аристов А.О. Квазиклеточные сети : «Эффект нагревания» и переменные
величины // XIII Всероссийская научная конференция «Нейрокомпьютеры и
их применение». Тезисы докладов.–М: МГППУ, 2015. –C.107-108
32. Аристов А.О. Представление моделей элементов технологических схем
квазиклеточными сетями // XIV Всероссийская научная конференция
«Нейрокомпьютеры и их применение». Тезисы докладов.–М: МГППУ, 2016.
– C. 113-114.
33.Аристов А.О. Автоматизированные системы поддержки научных
исследований потоковых систем на основе квазиклеточных сетей //
Суперкомпьютерные технологии математического моделирования. Тезисы
докладов –М.:Издательский дом Математического института имени В.А.
Стеклова РАН, 2016. – С.15
34.Аристов А.О. Моделирование квазиклеточными сетями // Международная
школа молодых учѐных «Моделирование и оптимизация сложных систем»
(MOCS 2016). Тезисы докладов –М.:Издательский дом Математического
института имени В.А. Стеклова РАН, 2016. – С.30-31
35. Аристов А.О. Характеризация базового графа квазиклеточных сетей // XV
Всероссийская научная конференция «Нейрокомпьютеры и их применение».
Тезисы докладов.–М: МГППУ, 2017. – C. 177-178.
36. Аристов А.О. Интерактивный программный комплекс моделирования и
управления потоковыми системами на основе квазиклеточных сетей //
ДЕСЯТАЯ
ВСЕРОССИЙСКАЯ
МУЛЬТИКОНФЕРЕНЦИЯ
ПО
ПРОБЛЕМАМ УПРАВЛЕНИЯ МКПУ-2017. Материалы 10-й Всероссийской
мультиконференции. В 3-х томах. Ответственный редактор: И.А. Каляев.
2017. - Ростов-на-дону; Таганрог : издательство Южного федерального
университета, 2017 Т.1 – С. 174-176.
Авторские свидетельства на разработки:
37. Аристов А.О. Квазиклеточные сети. Теоретическая база и программный
инструментарий // Свидетельство ОФЭРНиО ИНИПИ РАО №18695 от
22.11.2012. Инв. номер ВНТИЦ №50201251427
38. Аристов А.О. Модель проектирования, разработки и внедрения моделей
систем на основе квазиклеточных сетей. Свидетельство ОФЭРНиО ИНИПИ
РАО №19581 от 23.10.2013. Инв. номер ВНТИЦ №50201351037
39. Аристов А.О. Система автоматизированного проектирования и
моделирования квазиклеточных сетей // Свидетельство о государственной
регистрации программы для ЭВМ №2014661056
40. Аристов А.О. Программный комплекс синтеза, анализа и моделирования
работы координатных квазиклеточных сетей с бинарным состоянием //
Свидетельство о государственной регистрации программы для ЭВМ
№2016662128
1/--страниц
Пожаловаться на содержимое документа