Дискретный синтез систем с переменной структурой тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

г

\

РОС .

Ш

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

МАЗКУР Акрам

ДИСКРЕТНЫЙ СИНТЕЗ СИСТЕМ С ПЕРЕМЕННОЙ СТРУКТУРОЙ

Специальность 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

САНКТ-ПЕТЕРБУРГ 1994 г.

Работа выполнена на кафедре статистического моделирования математике- механического факультета Санкт-Петербургского государственного университета.

Научный руководитель:

кандидат технических наук,доцент Ю. А. Сушков

Официальные оппонеты:

доктор технических наук, нрофесор Г. И. Анкудинов,

кандидат физико-математических наук, доцент М. К. Чирков

Ведущая организация:

Санкт-Петербургский государственный электротехнический

университет.

Защита состоится 1994 г. в часов

на заседании специализированного совета К 063.57.49 по присуждению ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, Ст. Петергоф, Библиотечная пл., 2, математико-механический факультет СПбГУ.

С диссертацией можно ознакомиться в библиотеке им. М. Горького СПбГУ, Университетская наб., 7/9.

Автореферат разослан

»я »а 1994 г.

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

А. И. Шепелявый

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Устройства, режим работы которых зависит от ее структурной настройки (от связей, вводимыми между составляющими ее элементами), широко используются в различных областях детельности человека. К таким системам относиться механизмы перемены передач, фильтры и регуляторы переменной структуры, логико-динамические системы и др.

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

В реферируемой работе исследуются основные структурные свойства систем, состоящих из двухполюсников и трехполюсни-ков, изучаются их функциональные возможности, ставятся и решаются задачи синтеза, которые можно отнести к классу структурной аппроксимации.

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

Цель работы. Состоит в изучении структурных и функциональных свойств систем с переменной структурой, состоящих из двухполюсных и трехнолюсиых элементов, исследовании особенностей возникающих, при этом задач структурной оптимизации, разработке алгоритмов решения задач структурного синтеза систем и реализации их на ПЭВМ.

Методы исследования. В основе методов решения задач

синтеза использовались основы теории графов, сетей и гиперграфов, дискретной математики, различные комбинации методов дискретной оптимизации: жадные алгоритмы на матроидалышх структурах, методы перебора с отсечениями, линейного, динамического и целочисленного программирования, случайного поиска, стохастического жадного алгоритма. Для численной оценки некоторых из предложенных методов использоалисъ методы статистического моделирования (Монте-Карло).

Научная новизна, В диссертации получены следующие результаты:

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

- предложены операции к-объединения блоков, изучены их свойства, что позволило упростить генераторы блок-схем;

- разработан новый способ синтеза систем из двухполюсников, включающий комплекс различных методов дискретного и случайного поиска, что позволило решать задачу асимптотически точно;

- предложен способ перебора конечных отображений с отсеиванием на базе симплекс-метода и перечисления гамильтоновых путей;

- найдены функциональные зависимости между функциями выхода в многорежимных системах;

- разработаны жадные (в том числе статистические) алгоритмы для поиска остовных гипердеревьев при некоторых ограничениях;

- найдены необходимые и достаточные условия планарности гиперграфа с ориентированными гиперребрами,- на границе которых распределение вершин задается группой Кранца;

- определены функциональные возможности планарных многокаскадных систем, состоящих из двухполюсников и трохполюсви-ков.

Практическая ценлость полученных результатов определяется возможностью использования как для развития теории конкретных технических систем с переменной структурой, так и непосредственным использованием разработанных алгоритмов и программ для синтеза этих систем.

Апробация работы и публикации. Основные результаты работы докладывались:

- на семинаре кафедры статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета:

- на семинаре кафедры теоретической кибернетики математико-механического факультета Санкт-Петербургского государственного университета:

- на международной конференции по математическим методам и программному обеспечению в компьютерном моделировании (Санкт-Петербург, 24-29 май 1994).

Основные результаты опубликованы в 4 работах.

Структура и объем работы. Диссертация состоит из введения. пяти глав, заключения, списка литературы и приложений. Основной текст диссертации занимает 105 страниц машинописного текста. Библиография содержит 63 наименований. Общий объем дисс ертации 153 страници. В диссертации имеется 28 рис. и 7 таб.

СОДЕРЖАНИЕ РАБОТЫ

Во пведепин дается описание многорежимной системы и not-можнме практические применения. Приводится краткое содержание работы, а также список используемых обозначений.

с

В первой главе дается сетевое (гиперграфовое) определение многорежимной системы и приводится общая постановка задачи синтеза.

Многорежимная система задастся ч< чшг.ркой объектов

Е = (Г. i), id. f). 111

где Г = (Z.E) - структурный (гинер)граф системы, Z множество се полюсов , 0 • входной, н> - выходной полюса. Каждому i 6 Z сопоставлена переменная u.-; € II, причем ыа - 1. Миологию ребер Е - D+ U. где D - множество функциональных ребер (элементов), Е - множество элементов управления. Каждому ребру е € D сопоставлено уравнение

+ (1 - = 0, Ге ={<».(*, ">}. её/Л (21

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

-ui„ + Ar-W,, = и, Ге={л,/*}, (3,

для систем из двухполюсных элементов. Здесь £ Л конструктивный параметр элемента с 6 D. Предполагается, что для этих систем уравнений выполнено условие независимости:

|ГА| > |Д|+ </- 1, УЛС£>. А^<р, </6 2:3.

Каждому ребру (t,jl в U сопоставляется уравнение

oJ^Wj, если I 4 J, \ и;,- = 0. если j » 0 }

Пусть R — подмножество уравнений (4| из U. |R| - я — I, где а = \Z\-\D\ ~ степень свободы системы. Некоторые |R| уравнений (4), уравнение I я система (2) совместно определяют режим работы системы, а значение сигнала на выходе

У (А) =■ и;,.

называется функцией выхода системы.

Графы г" = Ги = называются соответственно

функциональным грифом и графом управления.

выхода существенно зависит от вектора А.

Сформулируем в общем виде задачу синтеза, уточняемую в дальнейшем при решении конкретных задач.

При синтезе многорежимных систем считаются заданными: (а) последовательность значений, которые желательно воспроизвести на выходе на различных режимах

называемая выюдпой гаммой-. I < г: (С) семейство интервалов {[(//,,.'/с,)!' 6 I : 1}, внутри которых должны находиться соответствующие выходные сигналы:

(в) область значений Л, среди которых выбираются значения конструктивных Параметров Ар е Л.в 6 О. а также желаемое значение А„ £ Л:

(г) обычно предполагаются заданными число полюсов X и с те-пень свободы т.

В результате решения задачи синтеза требуется найти: (а) число элементов управления и. необходимое для воспроизве-

(5) структурный граф системы Г = {.£,£> + V):

(в> значения конструктивных параметров Ае €

(г) соответствие у: : (1 : I) —> (1 : г), определяющее режим ¿к. на

котором выходной сигнал //„-а га .'/*(«'»• < у .-л- < ,'/г».).

П|1И =»том значение критерия, определяющего близость к //<, А' £ 1 : должно быть как можно меньше и при этом выпол-нялг я бы ряд ограничений, например: < < € П:

Ар € Л, с€ О и другие. В качестве такого критерия исполыова-

которых функция

</ = {Ht-fh.....</<)•

дения заданной гаммы на каких-то I режимах из г =

лись в различных задачах квадратичный и минимаксный:

„ у-'[¡М- - У к У г \V~ek - Ук I

Га = > —- , Г, = шнх - . {01

9к 1 Ук. I

При оценке близости конструктивного параметра Л к желаемому А„ использовался критерий

е€Г"

Во второй главе предлагается метод генерирования попарно неизоморфных блок-схем для 1/62:3. В основе метода лежат два основных принципа;

(1) рекуррентное построение множества блок-схем с нириме-трами(<1,сг), если известно множество попарно неизоморфных схем с параметрами (¡1 - 1 ,а), (¡1 — 1,а — 1), (Л— 1,(7 — 2);

(2) для различения изоморфных схем используется двойственный код блок-схемы, что значительно сокращает время, чем при использовании прямого.

Такой метод позволил рас ширить католог блок-схем, имеющих практическое значение.

Вводится операция к-обге.динения блок-схем Й5, (2,, я,) и В31(г1,ог), состоящая в попарном объединении к вершин. Обозначается знаком

Доказано, что множество блок-схем, порождаемых рекуррентными формулами

= ВБ(2-1,о) + 2В8{з,2), (7)

В3(х,<г) = т + 1)+3В5(3,2), (8)

ВБ{х,а) = -2,а-1) + 1Л5(з,2). (91

обязательно содержит полное множество попарно неизоморфных блок-схем г,(Т).

Показано, что из множества кактусообразные блок-

схемы можно получить с помощью формулы (0), блок-схемы, у которых нет вершин степени один, - с помощью формулы (8), а все остальные только по формуле (7). Такой подход позволяет сразу отсечь большое число изоморфных блок-схем.

Для дальнейшего различения предлагается использовать минимальный двойственный Код, т.е. лексикографически упорядоченное семейство ребер (множеств ИНЦИДентных вершин). Это важно, так как дне блок-схимы имморфнм тп/да ч только ттдп, когда совпадают их м ан импльпыг днойпнн/ нныг коды.

Предложен алгоритм (В общем случае переборный), позволяющий значительно уменьшить время На сравнение изоморфных схем при наличии естественных ограничений.

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

Приведены расширение католога блок-схем По сравнению с известными, Программы, реализующие ра сработанные алгоритмы примеры расчета.

В третьей главе решается задача с интеза систем, у которых функциональные элементы - двухполюсники (»'._/), опис ываемые уравнением

и; = А,-у

О задаче синтеза считается заданным гамма передаточных отношений г/, необходимое число режимов /, область значений л Э Ам, 1,7 6 2, желаемое значение конструктивных Параметров Л0. Необходимо найти функциональный граф г", вектор А 6 Л<(, отображение у> : (1 I) —» (1 : г), где 1 : г - множество возможных п системе режимов. При этом критерий

5 = р-Ц А,А„,ГН) +

где Р = Г, или Гг из (б), а р - весовой коэффициент, обеспечивающий близость выходных функций Уу, к д и параметра А к А„,

П1

должен быть минимальным

S —» mí» г".,.*

Считая, что о и г заданы, эту задачу обычно сводили ь следующей: найти

min iitin шin S,

HS A ¿

где первый минимум находился Перебором по блок-схемам с заданными </ и а. второй случайным поиском по А. третий динамическим программированием. Однако такой подход не всегда дает точное решение.

Предложенный в работе алгоритм работает по схеме

min min (11 - uiiii L + min F).

И у А " ff» v!

которая дает возможность при достаточно большом числе испытаний случайного поиска получать точное решение.

Длл случая, когда число / не слишком велико предлагается иной подход к синтезу. Рассматривается структурный граф самого общего вида, иосле чего задача сводится к задаче квадратичного программирования с линейными ограничениями. Поиск допустимого решения при этом « троится совместно <• отображением у?, после чего используется метод Хука-Дживса. На последнем этапе путем минимизации числа управляющих элементов методом Магу обобщенный структурный граф преобразуется в оптимальный.

В ряде случаев, когда известны некоторые свойства структурного графа, отображение ip удается находить различными методами перебора, учитывая частичную упорядоченность функций выхода. В этом случае число различных упорядочений значительно меньше соответствующего факториала.. В частности, для двухкаскадной системы, у которой один каскад содержит лишь два функциональных элемента, числа упорядочений образуют числа Каталана.

и

П заключении рассмотрен конкретный пример синтеза транс форматора с переменной структурой.

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

Общая система синтеза таких схем аналогична описанной в предыдущей главе; Однако существует принципиальная трудность при построении минимальных остчвпых гипердеревьеи.

Известно, что подграфы гиперграфа, являющиеся гипердеревьями, образуют независимые множества ребер матроида. Поэтому для поиска минимального истинного гипердерева можно использовать жадный алгоритм. К сожалении», из определения гиперлеса как графа (ГН\И'), у которого |Г.!| > |.1| +//-!> У.4 С И^ Л / О, следует, что ДЛЯ проверки, является ли некоторый граф гиперлссом. требуется -.экспоненциальное время.

Предложены алгоритмы, которые при разумных ограничениях распо лшют гиперлес значительно быстрее, чем перебор подмножеств из Н". Кроме того разработаны стохастические жадные алгоритмы построении остовных гипердеревьеи, поьа»аш«ие при их стохастическом моделировании возможность получать практически важные результаты а приемлемое время.

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

у>:(1 :1)—(1 :г).

В пятой главе получены условия размещения гиперграфов на плоскости при ограничения* на расположение вершин гиперребер, а также получены оценки максимального числа режимов в плаиарных с истемах.

Обычно при оценке планарности гиперграфа предполагается, что размещение вершин на границе ребра Подчиняется симметрической группе. В этом случае исследоваиие планарности гиперграфа сводятся к распознаванию планарности его кенигова

представления. В работе предлагается более общее Пред< таиле-ние для случая, когда размещение вершин задается (Плетением симметрических групп, что имеет большое практическое значение. Предложены алгоритмы распознавания планарности графа для небольшого числа вершин.

Построена верхняя оценка маю имального числа режимов в каскадных планарных системах из двухполюсников и ддн cnot об построения системы, где это число режимов достигается.

Аналогичная оценка и соответствующая система построены также для планаряцх систем. со< тоящих из трехполюсников.

В приложении приведены программы, реализующие предложенные в работе алгоритмы.

По теме диссертации опубликованы работы: Ц! Мазкур А. , Сушков Ю. А. Передаточные функции линейных систем с переменной структурой//Теория и приложения дискретных систем. - Из-во СПбГУ. - 1993. вып.27. -С. 88-97.

[2] Мазкур А. , Сушков Ю. А. Пленарные гипергафы. Леи.

в ВИНИТИ, .V 284.5-0 93 от 16.U.1993. - 11 С. f3J Мазкур А. , Сушков Ю. А. , Фатташ И. Математические модели многорежимныХ'<;И1'1ем//Вычислительная техника и вопросы кибернетики. - Из-во СПбГУ. 1994. вып. 28. - С. 13-31.

|4j Mazkour А. , Shípulin I, , Sushkov Y. Graph пикЬ'Ь of гЬяпц*" structure mechanism я//International work «hop on Mafhrmatirnl methods and Tools in computer Miuuiatjon. S.-TetersInirK. -19У4. may 24-28. -P. 07-99.