13.09.1997
Синтез
последовательно-параллельной
стратегии
Трансформация
декомпозируемых
систем
Задачи
комбинаторного
синтеза
сложных систем
из их частей
(подсистем,
компонентов и
т. п.) являются
важным
практическим
направлением
во многих
приложениях
(техника,
экономика и
др.). Часто
такой подход
называют
модульным
проектированием
(например,
разработка
программного
обеспечения, проектирование
электронных
систем и др.) или
планированием
(например,
модульное
планирование
в
производственных
системах).
В
последние
годы
значимость
модульного подхода
резко
возрастает,
поскольку во
многих
областях
созданы и
создаются
библиотеки и
каталоги
компонентов
(локальных
решений) или
такие
локальные
решения
можно получить
за счет
информационного
анализа имеющихся
баз данных
и/или
заказать.
Иными
словами, проектирование
сложных
решений во
многих приложениях
теперь
основывается
на подборе
локальных
проектных
вариантов и
композиции
их в
результирующую
систему.
Очевидно,
что широкое
применение
такого композиционного
подхода к
проектированию
сложных
систем требует
разработки
или
переосмысления
следующего:
·
моделей
описания
систем;
·
моделей
комбинаторного
синтеза;
·
информационной
поддержки
модульного
проектирования;
·
взаимодействия
специалистов
(экспертов,
проектировщиков,
лиц
принимающих
решение и др.)
и
компьютерных
систем;
·
накопления
примеров
использования
композиционного
подхода;
·
обучения
специалистов
основам модульного
проектирования.
Следует
отметить, что
в России
накоплен значительный
опыт по проектированию
сложных
систем, часто
базирующийся
именно на
модульном
проектировании.
Приведем
несколько
примеров
научных направлений
указанного
типа:
·
проектирование
декомпозируемых
сложных
систем в
Вычислительном
Центре РАН [6];
·
проектирование
сложных
систем на
основе
морфологического
и многокритериального
подхода в
Институте проблем
управления
РАН,
Институте
системных
исследований
РАН и ряде
отраслевых
организаций
[1, 2, 4, 5];
·
аппроксимационно-комбинаторный
метод
проектирования
в
Вычислительном
Центре РАН [12];
·
математическое
исследование
"синтеза
знаний" [13, 15];
·
системная
среда САПР
для
проектирования
СБИС в
НИИСАПРАН [11].
В
данной
статье
кратко
описываются
декомпозируемые
системы и
основные
операции для
них
(представление,
оценивание,
выявление
узких мест,
сравнение,
отбор вариантов,
синтез,
модификация),
иерархическое
комбинаторное
проектирование
и реинжиниринг
систем,
приложения.
Отметим,
что
предложенная
схема
проектирования
декомпозируемых
систем -
"Иерархическое
Морфологическое
Многокритериальное
Проектирование"
(ИММП), хотя и
похожа на
иерархические
подходы к
проектированию,
принятию
решений, на генетические
методы
решения
задач, отличается
от них, в
частности,
учетом
порядковой
совместимости
элементов
составных
решений.
Под
декомпозируемой
системой мы
понимаем
следующее:
система
состоит из
частей (компонентов);
для каждой
части
имеется или
может быть
сформировано
некоторое
множество
альтернативных
проектных
вариантов
(ПВ).
Мы
рассматриваем
детерминированные
комбинаторные
задачи,
направленные
на композицию
декомпозируемых
систем из компонентов.
Дополнительно
мы учитываем
парные
взаимосвязи
(С) или
совместимость
между ПВ.
Часто
реальные
системы
требуют
многоуровневого
описания или
такое
описание
целесообразно
использовать
(например,
для
уменьшения исходной
размерности).
Приведем
перечень основных
функциональных
операций,
требуемых
при
проектировании,
анализе и
преобразовании
декомпозируемых
систем:
·
описание
и/или
представление
(разработка
древовидной
модели
системы;
требований
и/или
характеристик
системы и ее
частей и их
взаимосвязей
С);
·
оценивание
системы и ее
частей
(получение
оценок ПВ и С,
формирование
интегральных
оценок
системы в
целом);
·
выявление
узких мест
(выявление
элементов
системы в
виде
частей-компонентов
и/или их
совместимостей,
улучшение
которых
приводит к
улучшению
качества
системы в
целом);
·
сравнение
(сравнение
вариантов
системы или
ее частей);
·
отбор
(выбор лучших
вариантов
системы или
ее частей);
·
синтез (композиция
системы из ПВ
с учетом
качества ПВ и
С);
·
модификация
(преобразование,
улучшение,
адаптация), т.
е. изменение,
в частности,
элементов и
их взаимосвязей,
состава.
Программные
модули и
блоки данных,
элементы
маршрутов,
модели из
проектных
библиотек,
тесты и средства
верификации
и их
комбинации
могут
рассматриваться
как
указанные
выше ПВ. Наша
задача может
быть
рассмотрена
как составная.
Отметим, что
мы не
рассматриваем
модели
синтеза,
подобные тем,
которые
используются
в химии
(синтез
химических
продуктов и
др.).
Пример
декомпозируемой
системы
представлен
на рис. 1. При
этом
рассматривается
следующая
ситуация:
исходная
система S включает
три
компонента A, B, C с
соответствующими
ПВ: A1, A2, B1, B2, B3, C1, C2. В
качестве
примера
составного
решения можно
привести
следующее: S' = A2 * B1 * C1.
Дополнительно
мы можем
рассматривать
некоторые
изменения
системы
(трансформация,
улучшение и
т. п.): добавить
ПВ (A3, C3, C4);
исключить ПВ
(B2, C1);
добавить
компонент D с ПВ (D1, D2, D3).
Задача
композиции является
важной
частью
процесса
проектирования
в различных
проектных
дисциплинах.
Укажем
некоторые
западные
проектные методологии,
которые
включают
такой этап в
рамках общей
схемы
проектирования:
·
проектная
методология
в
·
JESSI COMMON FRAMEWORK для
процесса
проектирования
[42];
·
иерархическое
принятие
решений [30];
·
параллельное
проектирование
[46];
·
модульное и
многозадачное
проектирование
и
производство
[16, 48, 50];
Рассматриваемый
в работе
подход к проектированию
декомпозируемых
систем ИММП включает
следующие
стадии:
·
задание
требований к
проектируемой
системе и ее
компонентам
(цели или
критерии,
ограничения);
·
формирование
структуры
проектируемой
системы;
·
генерация
проектных
альтернатив
ПВ;
· оценивание
ПВ и С;
·
ранжирование
(оценивание в
порядковой
шкале
качества) ПВ;
·
композиция
составных ПВ;
·
анализ
составных ПВ
и их
улучшение.
Укажем
базовые
предположения,
используемые
в ИММП:
·
проектируемая
система
имеет иерархическую
древовидную
структуру;
·
качество
(эффективность,
совершенство
и т. п.) системы
представляет
собой агрегацию
качества
составных
частей и
качества
совместимости
этих частей;
·
критерии
качества
являются
монотонными;
·
качество
совместимости
частей системы
(или
подсистемы)
равно
агрегации
парных совместимостей
частей;
·
многокритериальные
характеристики
качества
частей или
совместимостей
могут быть
отображены
на некие
порядковые шкалы,
и эти шкалы
могут быть
согласованы.
Обычно
для
перечисленных
задач применяются
следующие
подходы:
·
оптимизационные
модели [16, 25, 49];
·
системы на
основе баз
знаний [27, 44, 49];
·
гибридные
методы [32].
ИММП
описан в
работах [37, 39], а
модели
комбинаторного
синтеза - в [36].
Рассмотрим
задачу
нашего
подхода к
комбинаторному
синтезу -
морфологическую
клику. Предполагается,
что
проектируемая
система
состоит из m
компонентов,
и для каждого
компонента i = 1, ..., m существует
множество
альтернативных
ПВ (морфологический
класс i). Задача
заключается
в следующем:
найти композицию
(морфологическую
схему, т. е.
клику)
S = S(1) * ... * S(i) * ... * S(m),
где
S(i)
является
отобранным
ПВ для
компонента i (один
представитель
из каждого
морфологического
класса) при
условии
ненулевой
совместимости
между ПВ.
Предполагается
порядковая
оценка
совместимости
для всех пар
ПВ из разных
морфологических
классов. (0
соответствует
несовместимости.)
Мы
используем
векторную
оценку
совершенства
системы:
N(S) = (w(S); n(S)),
где
w(S) -
минимум
парных
совместимостей
в S, n(S) = (n(1), ..., n(r), ..., n(k)) описывает
отобранные
ПВ (n(r) - это
число ПВ с
приоритетом r в S, где r = 1
соответствует
лучшему
классу
качества и w = 0, ..., t, t
соответствует
лучшей
совместимости).
На
рис. 2
представлено
пространство
совершенства
составной
системы в
виде решетки,
которая
соответствует
вектору N.
Таким
образом мы
ищем
составную
систему S, которая
является
недоминируемой
по N(S).
Аналогично
можно
описать
задачу, когда
из каждого
морфологического
класса ПВ
выбирается
несколько
проектных
вариантов. Такие
постановки
встречаются
в инженерной
практике
последнее
время
(решения с
избыточностью
по подсистемам).
Отметим
также, что n(S)
является
размытой
оценкой.
Cхема
решения
состоит из:
·
построения
допустимых
решений;
·
выбора
Парето-эффективных
решений по N.
Предложенная
задача
морфологической
клики близка
к ряду
известных
моделей и
подходов к проектированию
[3, 20, 28, 31, 43, 47, 52].
Для
анализа
сложных
решений мы
используем
элементы
двух типов ПВ
и C в
отношении
решения S: S-улучшающие,
S-нейтральные
и S-ухудшающие
элементы по
вектору N, где S-ухудшающие
элементы
рассматриваются
как "узкие
места",
которые
должны быть
улучшены.
Алгоритм
анализа и
улучшения
заключается
в следующем:
·
поиск узких
мест
(нахождение
всех S-ухудшающих
элементов
для
множества
Парето-эффективных
ПВ);
·
построение
окрестности
множества Парето-эффективных
точек (каждый
элемент этой
окрестности
может быть
преобразован
в
Парето-эффективную
точку только
одним улучшающим
действием);
·
исследование
возможных
улучшающих
действий для
каждого выявленного
узкого места
и для каждого
элемента
окрестности.
Многостадийное
планирование
используется
в экономике,
производственных
системах, при
решении
сложных
проблем в
искусственном
интеллекте [45].
На рис. 3
представлены
два примера
последовательно-параллельных
стратегий
для
четырехстадийной
задачи.
Отметим,
что
последовательно-параллельный
процесс
соответствует
дерево-декомпозируемому
графу, т. е.
возможна
декомпозиция
исходного
графа на базе
дерева
"происхождения".
Другие
дерево-декомпозируемые
графы
(например,
деревья,
частичные k-деревья)
исследуются
в работе [18]. В
нашем случае
мы
используем
структуру,
которая подобна
И-ИЛИ дереву.
Мы
рассматриваем
композицию
схемы решения
на основе
ИММП, в том
числе последовательно-параллельную
композицию
составных ПВ
для
обработки
данных с
учетом С
между ПВ. В
этом
приложении С
соответствует
совместимости
последовательных
ПВ (локальных
процедур
решения для
конкретного
периода) и
независимости
параллельных
ПВ.
Общая
схема
проектирования
последовательно-параллельной
стратегии
включает
следующие этапы:
1.
Построение
(описание)
базовой
иерархической
модели
стратегии
(морфологии).
2.
Анализ и
отбор
элементов
исходной
модели с
целью
формирования
рабочей
морфологии стратегии.
3.
Композиция
последовательно-параллельной
стратегии на
основе ИММП.
Примеры
построения
стратегий
описаны в литературе
[34, 36].
Трансформация
(улучшение,
преобразование,
реинжиниринг
и т. п.) сложных
систем исследуются
в различных
дисциплинах
[17, 21, 26, 29].
В
общем случае
можно
указать два
повода для
проектирования
систем [51]:
·
улучшение
существующей
системы;
·
проектирование
новой
системы.
В
первом
случае
происходит
эволюционное
улучшение и
многокритериальный
отбор проектных
альтернатив
[14, 19, 49].
В
работе [39]
представлен
многостадийный
процесс
трансформации
декомпозируемой
новой
системы. На
каждой
стадии на
основе ИММП
формируется
некая
композиция
действий по
трансформации
(улучшению)
системы.
На
верхнем
иерархическом
уровне
осуществляется
композиция
стадийных
составных действий
в
комплексную
многостадийную
стратегию
улучшения
(также на
основе ИММП).
Заметим,
что иерархические
подходы
применяются
многие годы,
например:
·
иерархическое
планирование
систем [23];
·
иерархическое
принятие
решений в производственных
системах [30];
·
иерархическое
планирование
в искусственном
интеллекте hierarchical tasks network (HTN) decomposition [24].
Укажем
опубликованные
примеры
применения
ИММП:
·
проектирование
и улучшение
интерфейса
пользователя
[33];
·
проектирование
последовательного
набора
интерфейсов
пользователя
[34];
·
анализ и
проектирование
человеко-машинных
систем [38];
·
информационное
проектирование
в гипертекстовых
системах [35, 40];
·
проектирование
конвейеров [41];
·
планирование
информационного
центра [7];
·
подготовка
бизнес-планов
[9];
·
реинжениринг
информационных
систем [39];
·
обучение,
включая
проектирование
учебных программ,
планирование
карьеры
студента [8, 10].
Следует
указать
некоторые
теоретические
и
практические
направления,
которые представляются
важными:
·
стратегическое
многоэтапное
проектирование
систем с учетом
неопределенности
в появлении
альтернативных
вариантов
реализации
компонентов
сложных
систем,
включая
вероятностные
описания ПВ
или описания
на основе теории
размытых
множеств и т.
п.;
·
многостадийное
планирование
стратегий
решения
задач при
проектировании
и
планировании;
·
исследование
более
сложных
комбинаторных
моделей
синтеза
систем,
например, с
учетом
зависимости
парной
совместимости
от других
элементов
систем;
·
построение
декомпозиционных
схем решения
сложных
задач
комбинаторной
оптимизации;
·
использование
комбинаторного
синтеза в
информационных
технологиях
на различных
этапах
обработки
данных;
·
обучение
специалистов
комбинаторному
проектированию
сложных
многодисциплинарных
систем.
1.
Березовский
Б.А., Данилов
В.Н., Кортнев
А.В., Коссов О.А.
и др.
Формирование
наборов
высших
растений для
замкнутой
биотехнической
системы
жизнеобеспечения:
Обзор.-М.:
ОНТИТЭИМикробиопром,
1977. - 75 с.
2.
Березовский
Б.А., Конторер
Л.А.,
Эффективный алгоритм
построения
множества
недоминируемых
вариантов
декомпозируемых
объектов. -
Автоматика и
телемеханика.
1987, # 1. - с. 115-121.
3.
Гэри М.,
Джонсон Д.,
Вычислительные
машины и трудно
решаемые
задачи. Пер. с
англ. - М.: Мир, 1982. - 416 с.
4.
Дубов Ю.А.,
Травкин С.И.,
Якимец В.Н.,
Многокритериальные
модели
формирования
и выбора вариантов
систем. - М.:
Наука, 1986. - 296 с.
5.
Емельянов
С.В., Озерной
В.М., Ларичев
О.И. и др. Выбор
рациональных
вариантов
технологических
шахт с учетов
большого
числа критериев.
- Горн. журнал. -
1972, # 5.
6. Краснощеков
П.С., Морозов
В.В., Федоров
В.В., Декомпозиция
в задачах
проектирования.
- Техническая
кибернетика.
- 1979, # 2. - с. 7-17.
7.
Левин М.Ш.,
Задача
планирования
информационного
центра. - НТИ,
сер. 2. - 1995, # 2. - с. 16-24.
8.
Левин М.Ш., О
третьей
грамотности.
- НТИ, сер. 2. - 1995, # 6 - с.
20-30.
9.
Левин М.Ш.,
Типовые
задачи
принятия
решений при
подготовки
бизнес-планов.
- НТИ, сер. 1. - 1995, # 10. - с.
7-13.
10.
Левин М.Ш.,
Иерархический
комбинаторный
подход к
планированию
карьеры. - НТИ,
сер. 2. - 1996, # 12. - с. 22-27.
11.
Стемпковский
А.Л., Шепелев
В.А., Власов А.В.,
Системная
среда САПР
СБИС. - М.: Наука,
1994. - 251 с.
12.
Хачатуров
В.Р.,
Аппроксимационно-комбинаторный
метод
декомпозиции
и композиции
систем и
ограниченные
топологические
пространства,
решетки,
оптимизация.
- Ж. вычислительной
математики и
математической
физики. - 1985. - Том 25,
# 12. - с. 1777-1794.
13.
Цой Е.В., Юдин
А.Д., Юдин Д.Б.,
Проблемы
дополнения и
синтеза
знаний. -
Автоматика и
телемеханика.
- 1994, # 7. - с. 3-36.
14.
Эйрес Р.,
Научно-техническое
прогнозирование
и
долгосрочное
планирование.
- М.: Мир, 1971. - 296 с.
15.
Юдин Д.Б.,
Системы
синтеза
знаний. - Докл. АН СССР. -1990. - Том 315, # 4. - с. 809-812.
16. Berman O. and Ashrafi
N., "Optimization Models for Reliability of Modular Software
Systems". IEEE Trans. on Software Engineering, Vol. 19, # 11, pp.
1119-1123, 1993.
17. Berman O., Ingco
D.I. and Odoni A., "Improving the Location of Minimax Facilities Through Network Modification".
Networks, vol. 24, pp. 31-41, 1994.
18. Borie R.B.,
"Generation of Polynomial-Time Algorithms for Some Optimization Problems
on Tree-Decomposable Graphs". Algorithmica, Vol.
14, # 2, pp. 123-137, 1995.
19. Buede D.M. and Choisser R.W., "Providing an Analytical Structure for
Key System Choices", J. of Multi-Criteria Decision Analysis, vol. 1, # 1,
pp. 17-27, 1992.
20. Carraway R.L. and
Schmidt R.L., "An Improved Discrete Dynamic Programming Algorithm for
Allocating Resources Among Interdependent Projects". Manag.
Sci., Vol. 37, # 9, pp. 1195-1200, 1991.
21. Das D., Gupta S.K., and Nau
D., "Reducing setup cost by automatic generation of redesign suggestions.
In: Proc. of ASME Conference "Computers in Engineering", 1994.
22. Demes G.H., Fenves
S.J., Grossmann I.E., Hendrickson C.T., Mitchell T.M., Prinz
F.B., Sewiorek D.P., Subrahmanian
E., Talukdar S. and Westerberg A.W., "The
Engineering Design Research Center of Carnegie Mellon
University". Proc. of the IEEE, Vol 81, # 1, pp.
10-23, 1993.
23. Dempster M.A.H.,
Fisher M.L., Jansen L., Lageweg B.J., Lenstra J.K., and Rinnooy Kan
A.H.G., "Analytical Evaluation of Hierarchical Planning Systems".
Operations Research, vol. 29, # 4, pp. 707-716, 1981.
24. Erol K., Nau D., and Hendler J., "HTN
Planning: Complexity and Expressivity". In: AAAI-1994,
25. Grossmann I.E., "Mixed-Integer
Non-linear Programming Techniques for the Synthesis of Engineering
Systems". Res. in
26. Gunasekaran A., Korukonda A.R.,
27. Gupta A.P.,
28. Hall M., Jr.,
Combinatorial Theory, 2nd ed.,
29. Hammer M., and Champy
J., "Reengineering the corporation: A manifesto for business
revolution", Harper business, 1993.
30. Harhalakis G.,
Lin C.P., Nagi R. and Proth
J.M., "Hierarchical Decision Making in Computer Integrated Manufacturing
Systems". In: Proc. of the Third Int. Conf. on CIM. CS Press, pp. 15-24,
1992.
31. Knuth D.E. and Raghunathan
A., "The Problem of Compatible Representatives".
32. Kusiak A.,
"Artificial Intelligence and Integrated Manufacturing Systems". In:
A. Kusiak (Ed.) Artificial Intelligence. Implications
for CIM.
33. Levin M.Sh.,
"Hierarchical Design of User Interfaces". In: B. Blumenthal, J. Gornostaev, C. Unger (eds.), Human Computer Interaction.
LNCS, vol.876, Berlin: Springer, pp. 140-151, 1994.
34. Levin M.Sh.,
"A Hierarchical Planning and Problem Solving: Approach to Interface
Design". In: Proc. of Intl. Conf. on Human-Computer Interaction EWHCI'95,
35. Levin M.Sh.,
"Towards Hypertexts and Decision Making." In: Proc. of Intl. Conf. on
Human-Computer Interaction EWHCI'95,
36. Levin M.Sh.,
Towards Combinatorial Models of Synthesis, Technical Report 96-1-002, The
37. Levin M.Sh.,
"Hierarchical Morphological Multicriteria Design
of Decomposable Systems". J. Concurrent Engineering: Research and
Applications, vol. 4, no. 2, 1996, 111-118.
38. Levin M.Sh.,
"Combinatorial Analysis and Adaptation of Human-Computer Systems".
Proc. of Intl. Conf. on Human Computer Interaction EWHCI'96,
39. Levin M.Sh.,
"Improvement of Decomposable Systems". Advances in Concurrent
Engineering, 3rd ISPE Intl. Conf. on Concurrent Engineering,
40. Levin M.Sh.,
"Combinatorial Design in Hypertext". Proc. of 5th Intl. Conf. on
Information Systems Development,
41. Levin M.Sh., and Kaganov Yu.T., Hierarchical
Design of Vibration Conveyor. In: Proc. of Intl. Conf. on "Information
Technology in Design",
42. Liebisch D.C. and
Jain A., "JESSI COMMON FRAMEWORK Design Management - The Means to
Configuration and Execution of the Design Process". In: Proc. of EURO
DAC'92. Los Alamitos: CS Press, pp. 552-557, 1992.
43. Martello S. and. Toth
P, Knapsack Problem: Algorithms and Computer Implementation,
44. McDermott J., "R1: A Rule-Based Configurer of Computer Systems". Artificial
Intelligence, vol. 19, # 2, pp. 39-88, 1982.
45. Muhanna W.A. and
Pick R.A., "Meta-modeling Concepts and Tools for
Model Management: A Systems Approach". Management Science, vol. 40, no. 9,
pp. 1093-1123, 1994.
46. Reddy Y.V.R., Srinivas
K., Jagannathan V. and Karinthi
R., "Computer Support for Concurrent Engineering". Computer, vol. 26,
# 1, January, pp. 12-15, 1993.
47. Singha J. and
Katz J.L., "A Branch-And-Fathom Algorithm for the
48. Sriram D., Logcher R. and Fukuda S. (Eds.), Computer-Aided Cooperative
Product Development. LNCS, vol. 492, Springer-Verlag,
1991.
49. Sykes E.A. and White C.C., III, "Multiobjective Intelligent Computer-Aided Design".
IEEE Transactions on Systems, Man, and Cybernetics, vol. 21, # 6, pp.
1498-1511, 1989.
50. Tsukune H.,
Tsukamoto M., Matsushita T., Tomita F., Okada K., Ogasawara T., Takase K. and Yuba T., "Modular Manufacturing".
J. of Intel. Manufacturing, vol. 4, no. 2, pp. 163-181, 1993.
51. Van Gigch J.P.,
Applied General Systems Theory. 2nd ed., Vol. 1 and 2, Harper and Row
Publishers, 1978.
52. Zwicky F.,
Discovery Invention, Research Through the Morphological Approach.
Журнал
"Автоматизация
проектирования",
#04, 1997 год
//
Издательство
"Открытые
системы" (http://www.osp.ru/)
Постоянный
адрес статьи:
http://www.osp.ru/ap/1997/04/14.htm