Комбинаторные схемы поддержки модульных систем

М.Ш. Левин,
вед. н. сотр., к.т.н., е-mail: mslevin@acm.org
ИППИ РАН, г. Москва

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

Support layer for modular systems involves combinatorial schemes as special system problems (design of hierarchical system model, evaluation of system and its components, detection of system bottlenecks, improvement and extension of system, multistage design to build a system trajectory, modeling of combinatorial evolution of system and forecasting. Scheme for aggregation of modular solutions is used as well. Hierarchical morphological system model is used as a basic one. The schemes above are examined as composition of combinatorial models (multiple choice problem, morphological clique, multicriteria ranking, assignment, clustering, searching for a median, etc.) and corresponding solving procedures, which include expert judgment. List of applications contains software, communication systems, apparatus, standards, sensors, plans, modular educational courses.

Введение

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

рис. 1 Цикл системы, модель, комбинаторные схемы

(1) построение иерархической (древовидной) модели системы, (2) оценивание системы и ее частей, (3) комбинаторный синтез, (4) выделение системных узких мест, (5) улучшение/расширение системы, (6) многостадийное проектирование для формирования траектории системы, (7) моделирование комбинаторной эволюции и прогнозирование. Дополнительно используется вспомогательная схема агрегации модульных решений.

В результате получается 4-уровневая общая структура [2]:

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

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

(в) указанные выше комбинаторные схемы,

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

1. Построение иерархических моделей систем

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

2. Оценивание систем и их частей

С общей точки зрения, целесообразно рассматривать следующие типы шкал/оценок [1],[5]: количественная, порядковая, векторная, шкалы на основе частичных порядков. Интегрированная оценка составных систем должна включать оценки частей/компонентов системы и оценки их совместимости (в случае двухуровневой структуры). Таким образом возникают типовые задачи: оценивание компонента или связи компонентов по определенной шкале, трансформация оценки (из одной шкала в другую), интеграция оценок компонентов в интегрированную оценку по итоговой шкале для системы (или составного компонента). Обзор таких типовых задач оценивания содержится в [5]. Оценивание компонентов или альтернатив для компонентов обычно требует многокритериального оценивания на основе испытаний, вычислений, экспертных суждений (многокритериальные оценки можно трансформировать в порядковые оценки). Оценивание совместимости может проводиться аналогично. Для интегрированных оценок автором используются шкалы на основе частичных порядков (на базе порядковых оценок или на базе оценок в виде мультимножеств) [1],[5],[6].

3. Комбинаторный синтез

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

4. Выявление системных узких мест

В качестве узких мест рассматриваются объекты: (а) компонент или связь компонентов, (б) группа компонентов, (в) группа связанных компонентов, (г) структура системы [1],[7]. Кроме того, важными являются динамические задачи выявления узких мест [7], в частности интеграция данных на основе клики над потоками графов [8]. Выявление некачественной структуры системы требует специальных подходов.

5. Улучшение и расширение систем

Базовые ситуации улучшения модульных систем включают модификацию системы на основе улучшения/замены компонента(ов) или их совместимости. Для улучшения структур систем (например, сетей) имеются известные задачи (пополнение графа - augmentation problem, назначении горячих связей – hotlink assignment). Задачи покрывающих деревьев (минимальное покрывающее дерево, дерево Штейнера и их модификации, включая многокритериальные постановки) могут также рассматриваться как улучшение структур [9]. Особое значение имеет задача расширения системы: присоединение дополнительной части системы или новое обобщенное проектирование [9], [10].

6. Многостадийное проектирование

При многостадийном проектировании целью является построение траектории системы в виде цепочки системных версий или с использованием более сложной структуры на «верхнем» уровне (например, орграф, для каждой вершины которого определяется версия системы) [1],[11].

7. Моделирование комбинаторной эволюции и прогнозирование

Здесь исследуются несколько поколений системы и с выделением типовых изменений-операций между поколениями и добавлением необходимых дополнительных операций по улучшению системы (последнее поколение). Далее можно рассматривать задачу синтеза нового поколения системы как комбинаторный выбор и/или синтез операций изменения [12].

8. Агрегация модульных решений

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

(а) определение подрешения исходных решений и его расширение (задачи рюкзачного типа или ИММП), (б) (а) определение надрешения исходных решений и его сужение (задачи рюкзачного типа или ИММП), (в) новое обобщенное проектирование системы на основе всех известных элементов (из всех исходных решений и дополнительных элементов) [13].

Заключение

В работе кратко представлено описание специального инструментального уровня поддержки для модульных систем. Ряд прикладных примеров содержатся в публикациях [1],[10],[12],[14],[15].

Литература

1. Levin M.Sh. Composite Systems Decisions, Springer, 2006.

2. Levin M.Sh. Note on combinatorial engineering frameworks for hierarchical modular systems. Preprint, 2013. http://arxiv.org/abs/1304.0030 [math.OC]

3. Levin M.Sh. Four-layer framework for combinatorial optimization problems domain. Advanced Engineering Software, 42(12), 1089-1098, 2011.

4. Levin M.Sh. Towards design of hierarchy (research survey). Electronic preprint, 2012. http://arxiv.org/abs/1212.1705 [math.OC]

5. Levin M.Sh. Note on evaluation of hierarchical modular systems. Electronic preprint, 2013. http://arxiv.org/abs/1305.4917 [cs.AI]

6. Levin M.Sh. Multiset estimates and combinatorial synthesis. Electronic preprint, 2012. http://arxiv.org/abs/1205.2046 [cs.SY]

7. Levin M.Sh. Towards detection of bottlenecks in modular systems. Electronic preprint, 2013. http://arxiv.org/abs/1306.01428 [cs.AI]

8. M.Sh. Levin, Towards clique-based fusion of graph streams in multi-funciton system testing. Informatica, 23(3), 391-404, 2012.

9. Levin M.Sh. Improvement/extension of modular systems as combinatorial reengineering (survey).Preprint, 2012. http://arxiv.org/abs/1304.4965 [cs.AI]

10. Levin M.Sh. Towards communication network development. IEEE Int. Conf. Sibircon 2010, Vol. 1, Novosibirsk, 280-285.

11. Levin M.Sh. Towards multistage design of modular systems. Electronic preprint, 2012. http://arxiv.org/abs/1306.4635 [cs.AI]

12. Levin M.Sh. Towards combinatorial evolution of composite systems. Expert Systems with Applications, 40(4), 1342-1351, 2013.

13. Levin M.Sh. Aggregation of composite solutions: strategies, models, examples. Electronic preprint, 2011. http://arxiv.org/abs/1111.6983 [cs.SE]

14. Levin M.Sh. Modular design and improvement of the management system in smart home with the use of interval mutliset estimates. J. of Communications Technology and Electronics, 58(6), 584-593, 2013.

15. Levin M.Sh. A modular approach to the communication protocol and standard for multimedia information: A review. J. of Communications Technology and Electronics, 58(6), 594-601, 2013.