Диссертация (1090638), страница 15
Текст из файла (страница 15)
4.4).СтандартизированныйПротоколвзаимодействияБлок контроля СВРУправление моделямиКонфигурированиеЗапросыОтветыИнтерфейс связиИнтерфейс связиБАМНКоммутаторпространствимен(моделей)ХранилищемоделейМодель 1Модель 2Модель 3Модель 4Блокисполненияопераций надмоделямиМодель 5...Модель МРис. 4.4. Предложенная базовая архитектура системы временных решенийВ результате анализа интегрированных сред разработки модульных кроссплатформенных приложений, предложена реализация системы временных решений на основе инструментального средства конструирования интегрированной среды CLIPS (С Language Integrated Production System). Механизм расши-87рения CLIPS позволяет встроить в интерпретатор TQL недостающие модули,необходимые для моделирования [81, 91, 92].4.2. Метод визуализации и принятия решения на основе графовогопредставления поступающей информации, в форме физических аналогий,изменения энергии деформации связей между упругими теламиВизуализация рассматривается в работе, как способ представления обработки информации в системе обеспечивающей удобство аналитика (ЛПР) прирешении задачи построения прогноза, при возникновении кризисных событий.В последние годы в области визуализации информации появляются новые методы визуализации, модифицируются существующие, появляются все большепрограммных продуктов, специализирующихся на визуальной аналитике.
Изучение методов и разработка систем визуализации информации также входит впрограмму Computer Science ведущих американских университетов, таких какStanford и Berkeley. Также свою заинтересованность в данной области проявляет NSA (Агентство национальной безопасности США), что подтверждаетсяанонсированием разработок программных комплексов в области визуализациибольших объемов данных. Все это подчёркивает значимость исследований иперспективу развития данной научной области, а накопленный потенциал может способствовать дальнейшему внедрению методов визуализации информации в специальных областях.Перспективным подходом в вопросах разработки современных математических моделей для исследования критических инфраструктур, информационного взаимодействия является использование методов математического анализаи визуализация сложной концептуальной структуры [94].
Моделирование информации в виде объектов и связей между ними, оценки их взаимозависимостии уязвимости, а так же выявления потенциально уязвимых объектов, все этиметоды обеспечат ответственное лицо за принятие решения универсальным и вто же время простым инструментом для рассмотрения и понимания этих слож-88ных концептуальных структур, с выполнением следующего требования – искомого результата можно, а следовательно, и нужно достичь с минимумом прилагаемых усилий [95].При нахождении изображения графа можно рассматривать граф как систему тел с силами, взаимодействующими между телами, например, считаявершины графа телами, а ребра пружинами. В этом случае алгоритм находитконфигурацию тел с локально минимальной энергией – так называемую конфигурацию равновесия сил, в которой каждое тело занимает такую позицию, чтосумма всех сил, приложенных к телу, равна нулю.Таким образом [95], можно представить, что на каждый узел действуетсила (, ) со стороны узла , если узлы и связаны.
При этом на каждыйузел действует сила отталкивания (, ) со стороны узла . Сила отталкивания (, )действует как на связанные узлы, так и на несвязанные. Для представления графа мы можем написать систему уравнений равновесия для всехузлов A:∑∊ (, ) + ∑∊ (, ) = 0,(4.1)где и – i-е компоненты векторов ⃗ и ⃗ , I – множество узлов связанных сузлом A, а V множество всех узлов графа.При этом наиболее простые и симметричные изображения соответствуютслучаю, когда (, ) и (, ) зависят только от (, ) – расстояния междуузлами определяется метрикой Евклида, где n – размерность пространства вложения:22 (, ) = ∑==1 ( − ) ,(4.2)Зависимости сил от расстояний между узлами необходимо подобрать так,чтобы получались симметричные изображения при несложных вычислениях.Реализованы варианты для функций F и G: (, ) =1(,) ×((,)−,)×(− )2(,) ×(− )(,)2 (,), (, ) =,(4.3)89где 1(,) , 2(,) и , константы, и соответствующие координаты узлов и .Пусть рассматриваемый граф имеет образ на плоскости.
Каждому i-муузлу соответствуют его координаты ( ). Всему графу ставим в соответствиевектор, состоящий из наборов (1 , 2 , … , ). Такие вектора можно складывать покомпонентно по правилу:(1 ′ ,2 ′ ,… , ′ ) + (1 ′′ ,2 ′′ ,… , ′′ ) = (1 ′ + 1 ′′ ,2 ′ + 2 ′′ ,… , ′ + ′′ ), (4.4)умножать на скаляр:(1 , 2 , … , ) = (1 , 2 , … , ) ,(4.5)⃗⃗) такого вектора как:Определим норму (⃗⃗) = (| |),((4.6)При реализации метода физических аналогий алгоритм рисования графаразбивается на следующие шаги:1.
Узлы графа отображаются в точки пространства представления произвольным образом. Необходимо обеспечить условие, при котором эти точки неоказались бы на одной прямой. Для этого достаточно построить отображениеузла i в точку (, ()), где ( ) полином, степень которого не превышает количество узлов графа и больше одного.
При этом множеству этих точек соответ⃗⃗;ствует вектор 2. В соответствии с уравнениями (4.1) и (4.2) находим силу, действующую на каждый узел. Силы, действующие на все узлы графа, можно записать ввиде вектора ⃗ подчиняющегося правилам (4.4), (4.5) и (4.6).3. Новое положение точек вычисляется как:⃗⃗ ′ = ⃗⃗ + ⃗ ,(4.7)где η – подобранная скалярная величина, после этого шаги 2 и 3 повторяются.При каждой итерации проверяется неравенство > (⃗ ) ( заранее подобранный параметр, чем он меньше, тем ближе система к равновесию, но большевремя построения), если оно выполняется, вычисления обрываются, и граф ри-90суется с последними вычисленными координатами.
Для получения более централизованных изображений в уравнение (4.1) можно ввести член U отвечающий за притяжение всех узлов к центру изображения (например, ввести потен2циал = − ∑==1 при этом модифицируя функцию U можно по разномусконфигурировать изображение. Потенциал U целесообразно использовать приналичии нескольких несвязных компонент, что приводит к сокращению времени построения. Используемый алгоритм аналогично переносится на случайтрехмерного пространства (рис. 4.6).Реализация разработанного метода даёт приемлемое время построениядля графов содержащих около 300 узлов достаточных для графического представления развивающейся кризисной ситуации на экране ПЭВМ разрешением1920х1080 пикселей. Для повышения скорости работы приведённый алгоритмтребует модернизации.
Рассмотрим несколько приёмов позволяющих существенно ускорить время работы алгоритма для больших графов [96, 97].Рис. 4.5. Граф, содержащий несколько связных компонент, с наложенным потенциалом = −(2 + 2 ) [98, 99]91Рис. 4.6. Наибольшая связная компонента графа изображённогона рис. 4.5, без наложения внешнего потенциала [98, 99]Рис. 4.7. Граф, изображённый на рис. 4.5, с изъятой наибольшей компонентойи наложением внешнего потенциала = −(2 + 2 ) [98, 99]92Рис. 4.8. Трехмерное представление графа изображенного на рис. 4.5 [98, 99]4.2.1.
Развитие метода построения графов, основанногона применении физических аналогийКонстанта существенным образом влияет на скорость построения графов, чем больше тем выше скорость построения. При этом при увеличении на определённом этапе алгоритм начинает расходится, что проявляется в неограниченном росте норме силы (⃗ ). Для преодоления данной коллизии естьдва пути:при работе алгоритма отслеживается величина (⃗ ), как только она становится больше определённого наперёд заданного значения , т.е.
(⃗ ) > происходит редукция вектора сил ⃗ → ⃗ , где < 1 заранее определенная константа;при построении отслеживается динамика (⃗ ), при росте нормы силывеличина начинает снижаться, и наоборот при уменьшении (⃗ ) константу будем увеличивать.93Эти приёмы основаны на динамической подстройке константы к состоянию физической системы ассоциированной с графом. Реализация данныхулучшений позволяет в несколько раз увеличить скорость построения. Приэтом эволюция представления при построении существенным образом зависитот графа, что не позволяет применить универсальную функцию = ((⃗ )) вкачестве подстройки.Еще один подход заключается в применении специального отображенияR к связному графу .