Методы формализации и обобщения непроизводных структурных элементов в системе многоуровнего анализа транспортной инфраструктуры

Размещено на http://www.allbest.ru//

Методы формализации и обобщения непроизводных структурных элементов в системе многоуровнего анализа транспортной инфраструктуры

В.И. Батищев

Рассмотрены вопросы реализации аппарата формализации структурного непроизводного уровня представления системной модели. На основе топологического и категорно-функторного представления транспортной сети предложен метод декомпозиции системы на непроизводные структурные элементы, составляющие основу базы знаний информационно-аналитического комплекса анализа состояния транспортной инфраструктуры.

Ключевые слова: системная модель, топологическое пространство, категорно-функторная концепция, непроизводный структурный элемент.

непроизводный формализация транспортный инфраструктура

Транспортной системе (ТС) присущи свойства сложных систем, среди которых следует выделить многоаспектность и неопределенность их поведения, иерархию, структурное подобие и избыточность основных элементов и подсистем ТС, связей между ними, многовариантность реализации функций управления на каждом из уровней сложной технической системы, территориальную распределенность компонент. Однако ТС как составляющая крупномасштабной инфраструктурной промышленной системы имеет ряд особенностей: комплексная, а не отраслевая поддержка промышленных объектов; инерционность, связанная с крайне высокими затратами на коренное изменение структуры, и направленность на развитие, реконструкцию и модернизацию существующих схем. В данных условиях информационно-аналитические системы анализа состояния крупномасштабных инфраструктурных промышленных систем являются основным средством и инструментом системных исследований в данной области. Это обусловлено, с одной стороны, усложнением технических систем, когда эффективное формирование и отбор технических и организационных решений требуют анализа десятков тысяч параметров [1, 2]; кроме того, зачастую необходима оценка не просто отдельных параметров, а некоторой топологической структуры, что накладывает дополнительные сложности.

С учетом специфики формирования ТС для разработки многоуровневого информационно-аналитического комплекса используется формально-математический аппарат на основе категорного подхода [2], основанный на включении сформированной категории обобщенных вычислительных моделей в продукционные системы представления знаний.

При таком аппарате формализации специалисты выделяют следующие уровни [3, 4] представления системной модели: параметрический уровень; структурный уровень, включающий в себя контурный уровень; структурный непроизводный уровень; структурный производный уровень; семантический уровень, включающий в себя функциональный уровень. Все перечисленные уровни представления описываются в форме системы преобразования обобщенных вычислительных моделей.

Категорийно-функторная концепция предполагает, что в категории объект принципиально целостен, так как не рассматривается его внутренняя структура, а сопоставление и установление взаимосвязей осуществляется посредством функторов. Использование основных видов функторов (пренебрегающие и конструктивные) позволяет при проведении системных исследований корректно выполнять такие операции со структурами данных объектов, как декомпозиция и агрегирование [5]. Из этого следует, что основной задачей структурного производного уровня является декомпозиция категорий на более «бедные» с определением конструктивного функтора для перехода к категориям, содержащим более сложные объекты. Например, построить функторы из категории топологических пространств в категории логических описаний операций проективного пространства, что позволит решать топологические задачи с помощью методов булевой алгебры.

Рассмотрим структурный непроизводный уровень применительно к ТС как топологическое пространство, определяемое ее структурой. Топология рассматривает не количественные характеристики границ, а сам факт наличия или отсутствия физической связи между элементами. Если точки пересечения взаимодействуют друг с другом напрямую, то они считаются связанными, что отражается на проекции некоторой линией. Комплекс таких линий определяет схему разбиения полиэдра на симплексы [6]. Тогда транспортную сеть можно представить как конечную совокупность К двумерных симплексов (минимальных единичных составляющих) некоторого евклидова пространства R2, двумерного комплекса (полиэдра) К. Идея разбиения полиэдра на симплексы прямо следует из определения компонента комплекса. Компонентой некоторого комплекса K называется такой связный его подкомплекс L, что K распадается в сумму непересекающихся подкомплексов L и M. Если K1, …, Kp - совокупность всех компонент комплекса K, то они попарно не пересекаются и в сумме составляют весь комплекс K [6]. С другой стороны, в геоинформационных системах (ГИС) применение термина «топологический» не такое строгое, как в топологии. В ГИС топологическая модель определяется наличием и хранением совокупностей взаимосвязей, таких как соединение дуг на пересечениях, упорядоченный набор звеньев, взаимосвязи смежности между ареалами и т. п. В ГИС термин «топологический» означает, что в модели объекта хранятся некоторые взаимосвязи, которые позволяют проведение дополнительного пространственного анализа [7]. Топологические модели позволяют представлять элементы моделей объектов в виде графов. Площади, линии и точки описываются границами и узлами (дуговая/узловая структура). Каждая граница идет от начального к конечному узлу, и известно, какие площади находятся слева и справа. Теоретической основой моделей служат алгебраическая топология и теория графов. В соответствии с алгебраической топологией координатные типы данных - площади, линии и точки - называются 2-мерными ячейками, 1-мерными ячейками и 0-мерными ячейками соответственно. Тогда карта транспортной сети будет рассматривается как ориентированный двухмерный ячеечный комплекс или связанный граф G=(U, X), где U = { Pi,…,Pm} - множество вершин (набор пересечений дуг), а X = {{{ Pi},{ Pк}}} - множество дуг графа. Процедура поиска всех симплексов данного комплекса, где каждый n-мерный симплекс разбиения имеет n+1 вершин, попарно соединяющихся ребрами, и каждому из них соответствует n+1 максимальный полный подграф, сводится к поиску максимальных полных подграфов исходного графа [8].

Рассмотрим транспортную сеть как взаимосвязь между накопителями и потоками. В системной динамике накопители используются для представления таких объектов реального мира, в которых сосредотачиваются различного рода ресурсы, например материальные, энергетические, информационные и т. п. Накопители задают статическое состояние моделируемой системы. Их значения изменяются с течением времени согласно существующим в системе потокам. Если накопители задают статическое состояние моделируемой системы, то потоки задают динамику системы. Значения накопителей изменяются с течением времени именно согласно существующим в системе потокам. Входящие в накопитель потоки увеличивают значение накопителя, а исходящие из него потоки, соответственно, его уменьшают [9].

Из вышесказанного точка пересечения дорог, или накопитель, является одновременно приемником Vi транспортного потока и его же источником Ii (рис. 1), тогда для следующего перекрестка входящий поток Vi+1 будет равен исходящему потоку от предыдущего накопителя (рис. 2) при условии, что все накопители имеют одинаковое состояние.

На основе знания качественного описания входящих и исходящих потоков ТС строится матрица их взаимодействия в системе (см. таблицу) по аналогии с матрицей смежности в теории графов. Тогда на основе матрицы смежности можно построить граф G'=(U', X'), где U = {{Vi,Ii}…{Vn,In}} - множество вершин графа, а X = {Pi,…,Pm} - множество соединений вершин графа при условии равенства входящего и исходящего потоков Vj = Ik, j?k. Например, для матрицы из приведенной таблицы строится граф G'=(U', X'), отображающий структуру взаимоотношения потоков друг с другом (рис. 3).

В качестве единичной составляющей такой структуры предложено принять обобщенное понятие - непроизводный структурный элемент (НСЭ). НСЭ - ограниченная область структуры системы, отличающаяся только ей присущей совокупностью совместно взаимодействующих на категорном уровне свойств простых объектов. На топологическом уровне НСЭ является симплекс, тогда для применения априори известных законов и свойств топологической модели транспортной сети к модели, основанной на взаимоотношении накопителей и потоков, следует доказать изоморфизм графов G(U, X) и G'(U',X') в общем виде.

Таблица 1

Матрица взаимодействия потоков

Итак, рассмотрим графы G(U, X) и G'(U',X'). Так как определяющим условием построения этих графов является количество пересечений дуг или количество взаимоотношений потоков, то количество вершин для обоих графов равно m => |U| = |U'|, а количество ребер определяется наличием связи между пересечениями или равностью количества входящего и исходящих потоков => |X| = |X'| = p. Будем говорить, что эти графы изоморфны, если можно установить взаимно однозначное соответствие между их вершинами и ребрами так, что если вершины ui,uj графа G(U, X) соответствуют вершинам u'i,u'j графа G'(U', X'), то ребро xi = (ui,uj) G, если оно существует, соответствует ребру x'i = (u'i,u'j) G', если оно существует. Если ребро x'i соответствует ребру xi, то вершины u'i,u'j соответствуют вершинам ui,uj. Из этого следует, что изоморфные графы отличаются лишь нумерацией их вершин, что для нашего случая проверить затруднительно, так как требуется перебор всех m соответствий между вершинами. Воспользуемся понятием степени вершины. Степенью вершины u s(G,u) в графе G(U,X) называется количество его вершин, смежных с u, или, что то же самое, число ребер, инцидентных этой вершине [8]. Ясно, что при всяком изоморфизме - графов G и G' соответствующие друг другу вершины должны иметь одинаковую степень: для любой u U из u - u' должно следовать s(G,u) = s(G',u'). Далее, пусть G(U,X) - m вершинный граф (|U| = m), а s1,s2,…,sm - степени его вершин и G'(U',X') - m вершинный граф (|U'| = m), а s'1,s'2,…,s'm - степени вершин, ему принадлежащих, тогда упорядоченные системы s(G) = (s1,s2,…,sm) и s(G') = (s'1,s'2,…,s'm) являются векторами степеней графов G и G' соответственно. Из сказанного выше следует, что для изоморфизма графов G и G' необходимо совпадение векторов их степеней, для нашего случая степени каждой вершины будут равны как для графа G, так и для G' => s(G) = s(G'). Однако это условие является необходимым, но недостаточным, так как для графа G s1=s2=,…,=sm и для графа G' s'1=s'2=,…,=s'm, что говорит об s - однородности графов. Тогда рассмотрим постановку задачи об изоморфизме графов G(U,X) и G'(U',X'), с точки зрения математического программирования [11]. Пусть A=(Aij)mЧm и A'=(A'ij)mЧm - матрица смежности графов G и G' соответственно. Как известно из [8], для изоморфизма этих графов достаточно существование (невырожденной) матрицы T=(tij)mЧm, имеющей одну единицу в каждой строке и каждом столбце, чтобы выполнялось условие подобия [11]

.

Это условие перепишем в виде

,

что равносильно следующим условиям:

, i,j = 1, 2, …, m.

Задача о поиске матрицы T сводится к минимизации функции

при условиях

j = 1, 2, …, m,

i = 1, 2, …, m,

tij, i, j = 1, 2, …, m.

В нашем случае минимальное значение функции F1T равно нулю, а по [12] нулевые минимальные значения нелинейных целевых функций (F1T) достигаются для изоморфных графов и только для них, что говорит об изоморфизме графов G(U, X) и G'(U',X').

Таким образом, конечной целью представления системной модели на структурном непроизводном уровне являются декомпозиция структуры системы на НСЭ и выявление их взаимного сочетания. Эта процедура сводится к поиску полных подграфов («клик») графа G=(U, X). Результатом является набор «клик», соответствующих набору НСЭ ТС.

Предложенные методы формального представления ТС на этапе структурного непроизводного уровня позволили сформировать базу знаний, включающую в себя несколько десятков НСЭ транспортной сети. Данная база входит в состав информационно-аналитического комплекса анализа состояния ТС.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Батищев В.И., Губанов Н.Г. Методы адаптивного формирования информационных систем анализа состояния сложных технических объектов // Прикладная информатика. - №6(24). - 2009. - С. 152-156.

Батищев В.И., Губанов Н.Г. Категорные методы комплексного представления и структуризации разнородных данных в информационных системах анализа сложных объектов // Проблемы управления и моделирования в сложных системах: Тр. XII Международ. конф. - Самара: СНЦ РАН, 2010. - С. 263-267.

Батищев В.И., Губанов Н.Г. Категорное представление сложных технических объектов в индуктивных системах логического вывода // Проблемы управления и моделирования в сложных системах: Тр. IX Международ. конф. - Самара: СНЦ РАН, 2008. - С. 185-191.

Потапов А.С. Распознавание образов и машинное восприятие: общий подход на основе принципа минимальной длины описания. - СПб.: Политехника, 2007. - 548 с.

Охтилев М.Ю., Соколов Б.В., Юсупов Р.М. Интеллектуальные технологии мониторинга и управления структурной динамикой сложных технических объектов. - М.: Наука, 2006. - 410 с. ISBN 5-02-033789-7.

Понтрягин Л.С. Основы комбинаторной топологии. 3-е изд. - М.: Наука. Гл. ред. физ.-мат. лит., 1986. - 120 с.

Журкин И.Г., Шайтура С.В. Геоинформационные системы. М.: КУДИЦ-ПРЕСС, 2009. - 272 с. ISBN 978-5-91136-065-8.

Зыков А.А. Основы теории графов. - М.: Вузовская книга, 2004. - 664 с.

James M. Lyneis System dynamics applied to project management: a survey, assessment, and directions for future research / James M. Lyneis and David N. Ford - System Dynamics Review Vol. 23, No. 2/3, (Summer/Fall 2007): 157-189.

Антонов А.В. Системный анализ: Учеб. для вузов. - М.: Высш. шк., 2004. - 454 с.

Мишина А.П., Проскуряков И.В. Высшая алгебра. - М.: Наука, 1962.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учеб. пособие. - М.: ФИЗМАТЛИТ, 2002. - 240 с.

Размещено на Allbest.ru