Сигнальные графы. Лекция 21 марта 2021. Ориентированные (сигнальные) графы
 Скачать 437.5 Kb.
|
|
Ориентированные (сигнальные) графы Наряду со структурными схемами для графического изображения моделей информационных процессов в инфокоммуникационных системах широко используются ориентированные графы, которые в ряде случаев благодаря своим наглядности и прозрачности позволяют легче, чем структурные схемы, провести необходимые преобразования, значительно упрощающие решение задач анализа и синтеза информационных систем. Ориентированным графом называется множество точек, называемых вершинами и множества самонепересекающихся ориентированных кривых, называемых дугами, которые подчиняются следующим трем правилам: 1) каждая незамкнутая дуга содержит только две вершины; 2) каждая замкнутая дуга содержит только одну вершину; 3) дуги не имеют общих точек, кроме вершин. Ориентированный граф информационной системы имеет кроме того следующие свойства: 1) каждая дуга соответствует звену модели информационной системы и характеризуется оператором изображаемого его звена; 2) каждая вершина соответствует какой-либо переменной структурной схемы. Граф информационной системы может быть построен по структурной схеме. При переходе от структурной схемы к ориентированному графу необходимо следовать следующим правилам: 1) знаки суммирования сигналов в элементах суммирования учитываются в операторах соответствующих дуг; 2) каждый элемент суммирования заменяется вершиной, которой ставится в соответствие выходная переменная звена; 3) каждое звено структурной схемы заменяется дугой с оператором звена; 4) каждой переменной внешних воздействий соответствует своя вершина. Так структурной схеме (рис. 1, а) соответствует граф, показанный на рис. 1, б. При построение графа, эквивалентного структурной схеме дискретной системы, дополнительно к четырем выше сформулированным правилам пользуется специфическим правилом: дискретные элементы изображаются как и на структурной схеме ключами с учетом, что передаточные функции формирующих звеньев объединены с операторами других непрерывных звеньев (рис. 2, где W1(s)=Wф3(s)W(s)). Рис. 1 Ориентированные графы могут быть преобразованы с использованием следующих правил: 1) параллельные дуги можно заменить одной дугой с передачей равной сумме передач исходных дуг; 2) путь, не содержащий не принадлежащих ему дуг, можно заменить одной дугой с передачей равной произведению передач отдельных дуг этого пути. Для упрощения сложного графа и вычисления по нему передачи между двумя любыми вершинами используется правило Мэйсона, выражаемое следующей формулой: Здесь Wi – передача i-го пути от вершины x к вершине y, равная произведению передач дуг, входящих в этот путь; m - число таких путей; ∆ - определитель графа, вычисляемый по формуле : где W0j, Wok, Wol – передачи j-го, k-го или l-го контуров, равные произведению передач входящих в них дуг; в первой сумме суммируются передачи всех контуров, во второй сумме – произведения передач несоприкасающихся (не имеющих общих вершин) контуров; в третьей сумме суммируются произведения трех передач трех несоприкасающихся контуров и так далее; ∆ I – определитель подграфа, остающегося от исходного графа после удаления дуг и вершин i-го пути, включая дуги, подходящие к этим вершинам (другими словами ∆I – определитель той части графа, которая не касается с рассматриваемого i-го пути). В качестве примера рассмотрим использование формулы Мэйсона для графа, изображенного на рис. 3. Представленный граф содержит: 1) два пути от вершин G к вершине Y Wп1 = W1W3W5W7, Wп2= W5W7W9; 2) пять простых контуров: W01 = -W1W2, W02 = -W3W4, W03 = -W5W6, W04 = -W7, W05 = -W1W3W5W7W8 3) четыре пары несоприкасающихся контуров : W01W03, W01W04, W02W04, W03W04; 4) одну тройку несоприкасающихся контуров W01W03W04; 5) определитель подграфа первого пути ∆ = 1, так как нет контуров, несоприкасающихся с первым путем; 6) определитель подграфа второго пути: = 1 + W1W2; определитель всего графа ∆ = 1 - (W01 + W02 + W03 + W04 + W05) + + (W01W03 + W01W04 + W02W04 + W03W04) - W01W03W04. Передача всего графа от вершин G к вершине Y: Пример Пусть дана схема передачи информационно-управляющих сигналов в технической системе (рис. 4). Преобразование структурной схемы к сигнальному графу Граф прохождения сигнала G= 1. Каждой вершине графа xiX ставится в соответствие одна переменная структурной схемы (обозначение переменных сигналов приведено на рисунке 4). 2. Каждой дуге (xi, xj)X поставлена в соответствие передаточная функция одного из блоков структурной схемы. 3. Если из вершины исходит несколько дуг, то для них входная величина общая. Это устраняет в графе точки разветвления. 4. Если в вершину входит несколько ребер, то соответствующая этой вершине переменная равна сумме входных сигналов. Это делает не нужным использование в графе сумматоров. Учитывая перечисленные особенности перехода от структурной схемы к сигнальному графу, перейдем от схемы рис. 4 к соответствующему сигнальному графу (см. рис. 5). Вершины отмеченные серым цветом - это заданные контрольные точки. Матрица смежности Матрицей смежности графа G называется матрица R=[rij] размером nxn, где n – число вершин графа, в которой Матрица инцидентности Матрицей инцидентности графа G называется матрица S = [sij] размера n x m, где n – число вершин графа, а m – число дуг графа, в которой: Для построения графа пронумеруем все дуги графа в произвольном порядке, но с учетом нумерации передаточных функций. Матрица инцидентности Построение бинарных матриц путей выхода для заданных контрольных точек Согласно заданию выделено множество К контрольных точек (выходов). Оно имеет вид: К={x1, x4, y, x13} Построим матрицы путей для каждого из этих выходов. Бинарная матрица P = pij путей размера l x m, где l – число путей, строится по следующему правилу: Матрица путей выхода для x1 Матрица путей выхода для x4 Матрица путей выхода для y Матрица путей выхода для x13 Бинарная матрица контуров Бинарная матрица контуров C = cij размера h x m, где h - число контуров, строится по следующему правилу: Предварительно пронумеруем все контуры в произвольном порядке. Бинарная матрица контуров Матрица касания контуров Бинарная матрица контуров Ck = cij размера h x k, где k - число контуров, строится по следующему правилу: Матрица касания контуров Матрица касания путей и контуров Бинарная матрица контуров Cl = cij размера l x k, где l - число путей для заданного выхода, строится по следующему правилу: Матрица касания путей и контуров Формула Мэзона для заданного сигнального графа Используя универсальную топологическую формулу, носящую имя Мэзона, можно получить передачу между любыми двумя вершинами. Формула имеет следующий вид: где - передача k-го пути между вершинами j и r; - определитель графа. Он характеризует контурную часть графа и имеет следующий вид: где: L – множество индексов контуров, L2 - множество пар индексов не касающихся контуров, L3 - множество троек индексов не касающихся контуров, Ki – передача i-го контура, - минор пути, это определитель подграфа, полученного удалением из полного графа вершин и дуг, образующих путь . = 1 - К1- К2 - К3 - К4 - К5 - К6 - К7 - К8 + К7К2 + К7К3 + К7К5 + К7К6 + К7К8 = 1- К1-К2-К3-К4 - К5 - К6 - К7 - К8 + К7(К2 + К3 + К5 + К6 + К8) К1 = W1W3W4W5W6 K2 = W3W4W7 K3 = W1W3W4W8 K4 = W2W3W4W6 W7 K5 = W2W3W4W7 K6 = W2W3W4W8 K7 = W5W6 K8 = W3W4 = 1 - W3W4(W1W5W6 + W7 + W1W8 + W2W6W7 + W2W7 + 2W2W8+ 1) + W5W6(W3W4(W7+ W1W5W6+ W2W7+ W2W8+1)-1) Применение нейронных сетей для оптимизации параметров информационной системы В последнее время для целей управления все шире начинают применять нейронные сети (НС), отличающиеся тем, что они способны при отсутствии какого-либо описания объекта управления лишь по его входным и выходным сигналам моделировать поведение объекта и решать оптимизационные задачи. Кроме того, НС обладают такими достоинствами, как высокое быстродействие, относительно небольшие затраты на разработку, что нередко делает их наиболее привлекательными для использования. НС можно рассматривать как однородную вычислительную среду, оперирующую четкими и нечеткими данными, способную к обучению и самообучению. Рис. 4.8. Структуры наиболее распространенных в настоящее время многослойных сетей На рис. 4.8 изображены структуры некоторых наиболее распространенных в настоящее время многослойных сетей. Среди них базовыми и принципиально разными являются три типа сетей, соответствующих трем методам их обучения: самоорганизующиеся сети Кохонена с обучением без ″учителя″; динамические сети Хопфилда с обучением по методу последовательного подкрепления знаний; многослойные сети прямого распространения, где осуществляется обучение с ″учителем″. В задачах управления обычно используются полносвязные двух- трехслойные сети. Искусственный нейрон (базовый процессорный элемент (БПЭ)) реализует на выходе q отображает Rn → R1 в соответствии с соотношением q = f( ) = f( ), где r0, r1, …, rn – входные параметры; w0, w1, …, wn – весовые коэффициенты синаптических связей БПЭ (рис. 4.9). Рис. 4.9. Схема базового процессорного элемента. Входной параметр r0 и коэффициент связи w0 вводят специально для инициализации сети; обычно r0 = +1; коэффициенты w0, как и остальные wj, j , настриваются в процессе обучения; ″функция активации″ f(·) – монотонная, непрерывно дифференцируемая на интервале (–1, +1) или (0, +1). Для искусственных нейронов наиболее употребительны (рис. 4.10): Рис. 4.10. Функции активации. Некоторые из них имеют следующее математическое описание [5]: 1. экспоненциальная функция f(x) = exp(–x2/σ), σ = const; 2. функция гиперболического тангенса f(x) = th(x) = (ex – e–x)/(ex + e–x), f′(x) = (1 + f(x))(1 – f(x)); 3. сигмоидная функция f(x) = 1/(1 + e–x), f′(x) = f(x)(1 – f(x)); 4. бинарные функции различного определения. Известные методы синтеза регуляторов для инфокоммуникационных систем требуют как минимум знание информации о структуре математической модели объекта. Зачастую также необходимо точно знать и значения параметров модели. Нейросети способны путем оценки тренировочных данных выучить on-line динамические характеристики сложных объектов и поэтому могут являться альтернативным методом реализации современных систем регулирования. Исходя из выше сказанного, рассмотрим реализацию регулятора, на основе нейроконтроллера. Синтез нейроконтроллера проводится по следующей методике. Для выбранного вида активационной функции (рис. 4.10), первоначально, стохастически, задаются весовые коэффициенты и сдвиги нейронов нейроконтроллера. Затем на систему управления подаются тестовые сигналы (–1; –0,5; 0; 0,5; 1) и по переходному процессу в системе с такими параметрами нейроконтроллера рассчитываются значения критерия (4.9). F=(1/(n·tр)·∑ ∫(ei + (k/(IejI + ε)·dej/dt)2·dt, ej=((зад(min))j - 1)2·(t)2. tр 0 n J=1 где n – количество тестовых сигналов; tp – время переходного процесса; е – ошибка по выходной координате; ε – малая положительная постоянная, принятая 0,01; (зад(min))j – j - й тестовый сигнал (задание на управляемую переменную); 1 – текущее значение управляемой переменной (скорость, натяжение, положение и т.д.); k – масштабный коэффициент, лежащий в пределах 10 – 1000. После этого при помощи генетических операций (кроссовер, мутация, инверсия), по методике описанной в, параметры нейроконтроллера варьируются таким образом, чтобы критерий качества, рассчитываемый по (4.9) стремился к минимуму, при этом каждый раз пересчитывается значение критерия (4.9). Выше описанная процедура повторяется до тех пор, пока эффективный радиус популяции и ее разнообразие не становится близкими к минимуму. После этого процесс синтеза нейроконтроллера для данного вида активационной функции нейронов скрытого слоя считается законченным, и его параметры больше не меняются. При синтезе нейрорегулятора могут быть выбраны например следующие характеристики генетического алгоритма: – приспособленность особей рассчитывается только для новых, – коэффициент давления отбора 10%, – математическое ожидание кроссовера 1, – дисперсия кроссовера 1, дисперсия мутации 0,002, вероятность транслокаций 0,01, вероятность инверсии 0,01, всего особей 20, родителей 20, потомков 10. Моделирование нейросетевой системы управления и синтез нейроконтроллера может быть выполнено с помощью специализированного приложения Neural Network математического пакета MATLAB. |