Software & Systems

Концептуальное проектирование систем и САПР – актуальные направления, которые для решения своих задач используют методы теории принятия решений (ТПР). На начальном этапе проектирования требуются перебор и оценивание большого количества альтернатив. Параметры проблемной области могут значительно ограничивать множество допустимых методов принятия решений (МПР) вплоть до пустого множества. Несмотря на то, что в настоящее время существует целый ряд методов ТПР, отсутствует (не создан) механизм получения новых методов, которые могли бы быть использованы в новых (ранее не встречавшихся) проблемных областях. То, что такие области имеются и будут появляться, показано в [1] при помощи метода систематического покрытия поля. В современных источниках подходы к синтезу МПР авторами не обнаружены.

Типовым подходом к созданию новых систем является морфологический метод Цвики [2]. В настоящее время данный метод, а также его модификации [3] широко применяются для синтеза технических объектов. Использование его в качестве механизма синтеза информационных объектов и процессов в общем случае, и в частности МПР, является допустимым с учетом необходимой структуризации МПР, составляющих поле синтеза. Под информационным объектом будем понимать абстрактную систему, преобразующую входной поток информации в выходной с учетом различных ограничений, накладываемых средой на абстрактную систему.

Следует отметить, что использование морфологического метода влечет за собой известные проблемы, одной из которых является формирование объектов, содержащих недопустимые комбинации элементов, что в конечном счете может привести к невозможности получения какого-либо допустимого решения. Принимая во внимание данный аспект, а также то, что синтезу подлежит частный случай информационного объекта – МПР, авторы разработали соответствующий метод синтеза [4, 5].

Для описания используются следующие элементы: a – атрибут (attribute), представляющий собой кортеж áaName, aGroupñ, где aName – наименование атрибута, aGroup – группа, к которой относится атрибут; d – поток данных (data flow), представляющий собой кортеж ádName, Añ, где dName – наименование потока данных, A={a1, a2, …, ad} – множество атрибутов, описывающих поток данных; s – этап (step), представляющий собой кортеж ásName, Din, Dout, Añ, где sName – наименование этапа, Din={d1, d2, …, dm} – множество входных потоков данных этапа, m – количество входных потоков данных этапа, Dout={d1, d2, …, dn} – множество выходных потоков данных этапа, n – количество выходных потоков данных этапа; A={a1, a2, …, as} – множество атрибутов, характеризующих этап; m – метод (method) принятия решений, представляет собой упорядоченную совокупность этапов ás1, s2, …, skñ, преобразующих входной поток данных, поступающий от ЛПР, в выходной поток данных.

Для элементов определены операции получения множества входных потоков данных этапа s – Din(s)={d1, d2, …, dn}; выходных потоков этапа s – Dout(s)={d1, d2, …, dm}; множества атрибутов этапа s – A(s)={a1, a2, …, ak}; множества атрибутов потока данных d – A(d)={a1, a2, …, at}, а также получение группы атрибута Group(a)=aGroup.

Принцип процедуры синтеза состоит в следующем.

1.     Все методы должны быть декомпозированы на последовательные этапы и описаны в виде информационных объектов. Этапы составляют поле синтеза.

2.     Задаются набор входных потоков данных («Дано») и набор выходных потоков данных («Требуется»).

3.     При помощи блочно-лабиринтного морфологического метода [3] итерационно формируется множество результатов – цепочек, состоящих из этапов поля синтеза. Условие формирования цепочки: хотя бы один выходной поток данных предыдущего этапа соответствует хотя бы одному входному потоку данных следующего этапа.

4.     Отношение числа связанных входных потоков данных этапа к общему количеству входных потоков данных этапа составляет определенность этапа. Решения сортируются по мультипликативному критерию определенности решения, равному произведению определенности всех этапов, составляющих решение.

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

Далее приведено формальное описание процедуры синтеза.

Дано:  – задание на синтез, где ={d1, d2, …, dm} – множество входных потоков данных – ограничений на синтез, m – количество входных потоков данных цепочки синтеза; ={d1, d2, …, dn} – множество выходных потоков данных – ограничений на синтез, n – количество выходных потоков данных цепочки синтеза; U={s1, s2, …, sk} – множество этапов, представляющих собой поле синтеза (из каких структурных элементов допустимо собирать цепочки решений), k – мощность поля синтеза; E={e1, e2, …, es} – множество эвристических правил, используемых в процессе поиска решения; M – матрица (matrix) , показывающая совместную необходимость или несовместность использования пары атрибутов, mijÎ{–1, 0, 1}: mij=–1 – для возможности существования у этапа атрибута ai требуется отсутствие у него атрибута aj, mij=0 – на совместное присутствие у этапа атрибутов ai и aj ограничения не накладываются, mij=1 – для возможности существования у этапа атрибута ai требуется наличие у него атрибута aj; M(ai, aj) – получение вида совместимости атрибутов ai, aj={–1, 0, 1}; проверка на совместимость свойств используется на шаге сопряжения этапов, составляющих поле синтеза: «–1» – явно заданная несовместимость.

Требуется: сформировать последовательность этапов:

Выражения   назовем определенностью этапов: отношение мощности множества совпадающих потоков данных (выходных – предыдущего этапа и входных – текущего этапа) к мощности множества входных потоков данных текущего этапа. Для краткости обозначим

– (certainty) определенность этапа sj, где j=1;

 – определенность этапа sj, где j=2, …, n, i=1, …, n–1;

 – определенность выходных потоков данных задания на синтез, составляющих набор «Требуется», где j=n.

Выражение – целевая функция формирования решения. Область допустимых решений ZTÎ[0, …, 1]. ZT(ri) – определение целевой функции решения ri.

Алгоритм синтеза

Первый этап – формирование последовательных цепочек синтеза: R¢={r¢1, r¢2, …, r¢n}. Каждое решение состоит из последовательности этапов, полученной стандартным методом блочно-лабиринтного синтеза:

.

В процессе блочно-лабиринтного синтеза могут использоваться эвристики из множества E:

1)     – значение целевой функции, вычисляемой в процессе синтеза, должно быть в диапазоне от zl до zh;

2)    ½r¢i½£L – мощность множества этапов, составляющих решение, не должна превышать заданное ограничение.

3)    значение целевой функции ZT(r¢i) не должно убывать с увеличением мощности множества решения ½r¢i½;

4)    процедура блочно-лабиринтного синтеза должна продолжаться даже в том случае, если  (решение найдено).

Наиболее перспективным считается решение, имеющее , где i=1…½R¢½.

Второй этап – оптимизация полученных цепочек. Суть оптимизации в преобразовании линейной последовательной цепочки этапов в сеть. В процессе такого преобразования определяются потоки данных между этапами: Dout(si)ÇDin(sj)¹Æ, i  jÎ[3…½r¢i½].

Результатом второго этапа является множество решений R²={r²1, r²2, …, r²n}, значение целевых функций которых ZT(r²i)³ZT(r¢i) за счет формирования потоков данных между промежуточными этапами.

Третий этап – выполнение процедуры синтеза нового этапа.

Шаг 1. Определяется множество пар этапов SP={ási, sjñ}, связанных между собой потоками данных: Dout(si)ÇDin(sj)¹Æ и . Для каждой пары ási, sjñ выполняется цикл из шагов 2–4.

Шаг 2. Ведется проверка Group(A(Dout(si)))= =Group(A(Din(si))), то есть совпадают ли группы принадлежности атрибутов выходных потоков данных этапа si с группами принадлежности атрибутов входных потоков данных этапа sj. Если они не совпадают, то выполняется анализ следующей пары этапов, если совпадают, выбираются пары совпадающих по группам атрибутов потоков данных DP={ádi, djñ} и для каждой пары выполняется следующая операция (переход к шагу 3).

Шаг 3. Осуществляется проверка A(di)»A(dj): атрибуты выходного потока данных di частично совпадают с атрибутами входного потока данных dj. Если совпадают полностью, то выполняется анализ следующей пары потоков данных (переход к шагу 2), если совпадают частично – выходной поток данных di этапа si используется в процедуре синтеза нового этапа. Для этого "aiÎ{A(di)Ç ÇØA(dj)} выполняется следующая операция (переход к шагу 4).

Шаг 4. Проверяется допустимость M(ai, ajÎ ÎA(sj)). Если результат равен –1, то необходимо проводить анализ следующей пары потоков данных (переход к шагу 3). Если результат равен 0 или 1, атрибуты совместимы и следует перейти к очередному атрибуту потока данных ai+1ÎA(pi). Если "aiÎA(di)®M(ai, ajÎA(sj))Î{0, 1}, то создается новый этап s¢, отличающийся от этапа sj тем, что вместо входного потока данных pj в нем используется поток данных pi. Данный этап добавляется в поле синтеза, и процедура построения цепочек решений повторяется заново.

Шаг 5. Выход из цикла синтеза возможен при следующих условиях:

–      на очередном проходе цикла не было синтезировано ни одного нового этапа s¢;

–      достигнут предел итераций синтеза, заданный входным условием.

Описание созданной автоматизированной системы

С целью автоматизации процедур синтеза МПР авторами была разработана автоматизированная система (АС) «АЛЬФА-Синтез» (Свид. о гос. регистрации прогр. для ЭВМ № 2012614072 от 4 мая 2012 г., авторы: Д.П. Олейников, С.П. Олейников, Л.Н. Бутенко, Д.В. Бутенко). Система включает подсистемы структурирования МПР (работы с БД структурных элементов), синтеза МПР, формирования результатов синтеза, а также СУБД на базе MS SQL Server (рис. 1).

АС функционирует в режимах структурирования и синтеза МПР.

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

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

–      на первом формируется дерево решений, ветви которого определяют результаты синтеза;

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

–      на третьем синтезируются недостающие этапы, повышающие определенность всего решения в целом.

Решение задачи синтеза нового метода принятия решений

С целью проверки работоспособности разработанной системы была решена задача синтеза метода принятия решения «Вербальный Парето-ми­нимаксный критерий».

Формирование поля синтеза: на данном этапе в АС введены структурированные описания МПР и заданы правила совместимости атрибутов. Матрица совместимости приведена на рисунке 2.

Задание условий синтеза: на данном шаге создана сессия синтеза, заданы входные и выходные потоки данных, а также этапы, составляющие поле синтеза.

После запуска процедуры синтеза были указаны его ограничения.

Выполнение 1-го этапа процедуры синтеза: на данном этапе происходит первичное формирование решения в соответствии с алгоритмом, представленным ранее.

Выполнение 2-го этапа процедуры синтеза: на данном этапе выполняется сетевая оптимизация решения. Графическая интерпретация результатов оптимизации приведена на рисунке 3.

Выполнение 3-го этапа процедуры синтеза: на данном этапе выполняется формирование недостающего этапа с целью увеличения определенности решения.

Синтезированный этап сохраняется в БД АС и помещается в поле синтеза. После повторного запуска процедуры синтеза (этапы 1–3) было получено решение, соответствующее условию синтеза. Графическая интерпретация решения приведена на рисунке 4.

Созданная АС «АЛЬФА-Синтез» реализует разработанный авторами метод синтеза МПР.  АС функционирует в режиме структурирования МПР, в ходе которого формируется структурированное описание МПР, этапов и потоков данных, а также в режиме синтеза МПР, в ходе которого задаются требования к новому методу, поле синтеза и условия завершения синтеза. Результатом работы данного режима являются сокращенные диаграммы DFD, содержащие потоки данных и этапы преобразования информации (процессы).

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

Следует отметить возможность применения данной системы для синтеза не только МПР, но и информационных процессов, элементы поля синтеза которых могут быть описаны следующим образом: m={ásName, Din, Dout, Añ}, то есть в соответствии с предлагаемым авторами способом.

Литература

1.     Олейников Д.П. Принятие решений при качественных критериях оценки альтернатив. Волгоград: ВолгГТУ, 2006. 274 с.

2.     Zwicky F., Welson A. The morphological approach to discovery, invention research and construction. New methods of thought and procedure. Berlin: Springer, 1967, pp. 278–297.

3.     Андрейчиков А.В., Андрейчикова О.Н. Системный анализ и синтез стратегических решений в инноватике: Математические, эвристические и интеллектуальные методы системного анализа и синтеза инноваций: учеб. пособие. М.: ЛИБРОКОМ, 2012. 304 с.

4.     Олейников Д.П., Бутенко Л.Н. Синтез методов принятия решений на базе морфологического подхода // Вестн. компьютерных и информ. технологий. 2013. № 11. С. 21–26.

5.     Олейников Д.П., Бутенко Л.Н. Синтез методов принятия решений на базе морфологического подхода // Вестн. компьютерных и информ. технологий. 2013. № 12. С. 21–26.

References

1.     Oleynikov D.P. Prinyatie resheniy pri kachestvennykh kriteriyakh otsenki alternativ [Decision-making in qualitative criteria for evaluating alternatives]. Volgograd, Volgograd State Tech. Univ. Publ., 2006, 274 p.

2.     Zwicky F., Welson A. The morphological approach to discovery, invention research and construction. New methods of thought and procedure. Berlin, Springer, 1967, pp. 278–297.

3.     Andreychikov A.V., Andreichikova O.N. Sistemny analiz i sintez strategicheskikh resheniy v innovatike: Matematicheskie, evristicheskie i intellektualnye metody sistemnogo analiza i sinteza innovatsiy [System analysis and synthesis of strategic decisions in innovation: Mathematical, heuristic and intelligent methods of system analysis and synthesis of innovation]. Study guide, Moscow, “LIBROKOM” Publ., 2012, 304 p.

4.     Oleynikov D.P., Butenko L.N. The synthesis of decision-makings on the basis of the morphological approach. Vestn. kompyuternykh i inform. tekhnologiy [Herald of computer and information technologies]. 2013, no. 11, pp. 21–26.

5.     Oleynikov D.P., Butenko L.N. The synthesis of decision-makings on the basis of the morphological approach. Vestn. kompyuternykh i inform. tekhnologiy [Herald of computer and information technologies]. 2013, no. 12, 21–26.