автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методы и средства исследования структурно сложных систем на основе симплициальных комплексов

ВВЕДЕНИЕ

ГЛАВА 1. ПОЛИЭДРАЛЬНЫЙ ПОДХОД К ИССЛЕДОВАНИЮ

СТРУКТУРНО СЛОЖНЫХ СИСТЕМЫ

1.1. Симплициальная модель структурно сложной системы

1.2. Исследование роли отдельных элементов системы

1.2.1. ЭКСЦЕНТРИСИТЕТ

1.2.2. ИСПОЛЬЗОВАНИЕ СИМПЛИЦИАЛЬНЫХ ЗВЕЗД В 27 ИССЛЕДОВАНИИ РОЛИ ЭЛЕМЕНТОВ.

1.2.3. ИССЛЕДОВАНИЕ УЗЛОВ СТРУКТУРЫ С ПОЗИЦИИ 31 ВХОДЯЩИХ И ИСХОДЯЩИХ СВЯЗЕЙ

1.3. Анализ сложности структуры систем

1.3.1. СТРУКТУРНЫЙ ВЕКТОР

1.3.2. МЕРА СЛОЖНОСТИ

ГЛАВА 2. ИССЛЕДОВАНИЕ СЕТЕВЫХ ПОТОКОВ

2.1. Сетевой подход в рамках полиэдрального анализа

2.2. Характеристики потоков

2.3. Динамичность

2.4. Согласованность

ГЛАВА 3. МНОГОМЕРНОЕ ВЗАИМОДЕЙСТВИЕ ЭЛЕМЕНТОВ

3.1. Многомерные связи и многомерные потоки

3.2. Анализ q-компонент

3.3. Симплициальная модель q-компоненты

3.4. Нерв совокупности

3.5. Многомерные препятствия, q-дыры

ГЛАВА 4. ПОЛИЭДРАЛЬНЫЙ АНАЛИЗ ТРАНСПОРТНЫХ

СЕТЕЙ

4.1 Исследование транспортных сетей с позиций 79 полиэдрального анализа

4.2 Исследование участка реальной транспортной сети

ГЛАВА 5. ПРИМЕНЕНИЕ ПОЛИЭДРАЛЬНОГО ПОДХОДА К юо ИССЛЕДОВАНИЮ СИСТЕМ, ОПИСАННЫХ УРАВНЕНИЯМИ В ПРОСТРАНСТВЕ СОСТОЯНИЙ

5.1 Подходы к построению симплициальной модели линейных Ю1 динамических систем

5.2 Полиэдральный анализ при нечётком подходе к описанию Ю8 симплициальных комплексов

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

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

Так, например, теория графов, начиная с 70-х годов, привлекает к себе пристальное внимание специалистов различных областей знания. Наряду с традиционными применениями ее в таких науках, как физика, электротехника, химия, она проникла и в науки, считавшиеся раньше далекими от неё, -экономику, социологию, лингвистику и другие. Теория графов оказалась полезной при изучении задач, возникающих в некоторых других разделах математики, таких как топологическая теория, теория групп, теория матриц и теория вероятностей. Не маловажной является взаимосвязь между теорией графов и теоретической кибернетикой, особенно теорией автоматов, исследованием операций, теорией кодирования и теорией игр. Всякий раз, когда встречалась новая область применения теории графов, возникала необходимость во введении и изучении новых или в дальнейшей разработке некоторых известных понятий. Эта необходимость в свою очередь возбуждала творческую активность в области исследования различных связанных с ними концепций. Такое непрерывное взаимодействие способствовало быстрому росту этой ветви математики. Был написан ряд книг, обсуждающих различные аспекты теории графов: анализ, синтез, перечисление, алгоритмы и приложения. Разработанная Фордом и Фалкерсоном теория потоков в сетях осветила ряд комбинаторных вопросов и позволила получить новые доказательства важных теорем теории графов. Закон Кирхгофа о сохранении потока играет центральную роль в разработке теории потоков в сетях. Большое внимание было уделено конструированию сетей связи, имеющих заданные свойства. Эта задача обычно сводится к построению экстремального графа, т.е. графа, имеющего минимальное или максимальное число ребер и обладающего заданным значением одного из топологических параметров.

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

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

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

Как видно, рассмотренные методы позволяют создавать модели систем с целью решения какого-либо определенного класса задач, т.е. представляют собой взгляд на систему как бы с одной стороны. Кроме того, эти подходы содержат определенные недостатки. Так, например, многомерность и многосвязность практически не учитываются при теоретико-графовом подходе к построению модели. В свою очередь, кластерные алгоритмы в попытке преодолеть сложность изучаемых объектов неизбежно приводят к потере информации о системе и разрушению ее реальной структуры. В связи с этим, представляется актуальной разработка методики исследования структуры сложных систем на глобальном уровне, т.е. с позиции структуры как единого целого, и локальном уровне, с позиции отдельных элементов, уровнях. Использование нестандартного, имеющего в настоящее время ограниченное применение, аппарата алгебраической топологии, теории групп, теории множеств и бинарных отношений дает возможность анализа структуры как сложного многомерного геометрического образования - симплициального комплекса. Формирование основных путей использования симплициальных комплексов для построения математических моделей структур систем и исследования их сложности относится к началу 70-х годов и связано с именами математиков К.Доукером (С.Оо\л/кег) и Р.Эткина (Р.Н.А1кт) [9, 10, 48, 53].

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

Поставленная цель достигается решением следующих задач:

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

• Развитие методов анализа взаимодействия и роли отдельных подсистем в структурно сложных системах.

• Разработка подхода к использованию возможностей полиэдрального анализа при исследовании сетевой проводимости.

• Развитие анализа многомерных связей и многомерных потоков структурно сложных систем.

• Исследование возможности применения аппарата нечёткой логики при исследовании систем описанных уравнениями в пространстве состояний с использованием полиэдрального анализа.

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

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

Основные выводы по диссертационной работе сводятся к следующему:

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

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

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

4. Симплициальное представление систем открывает для исследователя принципиально новый тип взаимодействия элементов - многомерное взаимодействие. Создание методов анализа многомерных потоков и многомерной проводимости систем является одним из наиболее перспективных направлений развития полиэдрального анализа.

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

1. Дегтярев К. Ю. Разработка методов и средств математического моделирования и анализа структур сложных систем на основе аппарата полиэдральной динамики. Диссертационная работа, 1995.

2. Катаев О. Ю. Использование групп гомологий симплициальных комплексов для анализа структурно сложных систем./Математическое моделирование и управление в сложных системах: сборник научных трудов под ред д.т.н. проф. Музыкина С.Н. -М.: МГАПИ 1999.

3. Кашаев О. Ю. Использование симплекс-метода для анализа систем, описанных уравнениями в пространстве состояний. / Математическое моделирование и управление в сложных системах: сборник научных трудов под ред д.т.н. проф. Музыкина С.Н. -М.: МГАПИ 1997.

4. Кашаев О. Ю. Возможности моделирования динамики сложных систем в рамках О-анализа. /Моделирование и исследование сложных систем: тезисы докладов научно технической конференции. Кашира 1996. 268с. -р. 40

5. Кашаев О. Ю. Полиэдральный подход к анализу роли элементов структурно сложных систем. /Новые информационные технологии: Материалы четвёртой всероссийской научно-технической конференции. Под общ. ред. к.т.д. Хныкина А.П. -М.: МГАПИ. 2001. 184с.

6. Кашаев О. Ю. Использование полиэдрального подхода в исследовании сетевых потоков. /Математическое моделирование и управление в сложных системах: сборник научных трудов. Под общ. ред д.т.н. проф. Музыкина С.Н. -М. МГАПИ 2001.

7. Кашаев О. Ю. Исследование многомерной проводимости при полиэдральном анализе структурно сложных систем. /Математическое моделирование и управление в сложных системах: сборник научных трудов. Под общ. ред д.т.н. проф. Музыкина С.Н. -М. МГАПИ 2001.

8. Atkin R. Mathematical Structure in Human Affairs. London: Heinemann

9. Publishing Company, UK, 1974. \0. Atkin R. Polyhedral dynamics and geometry of systems. NASA Report,1.xembourg, 1977. p. 45. \*\.CastiJ. Dynamical Systems and Their Applications. Linear Theory. Academic Press. New York, 1977.

10. Pontryagin L. Foundations of Combinatorial Topology/ Graylock Press. New York. 1952

11. Дж. Касти. Большие системы. Связность, сложность, катастрофы. -М.: Мир, 1982.-216 с.

12. Спеньер Э. Алгебраическая топология. -М.: Мир, 1971.

13. ДольдА. Лекции по алгебраической топологии. -М.: Мир, 1976.

14. Александров П. С. Введение в теорию множеств и общую топологию -М. Наука, 1977.

15. П.Кофман А. Введение в прикладную комбинаторику. -М.: Наука 1975.

16. Рейнгольд Э. Нивергельт Ю. Део Н. Комбинаторные алгоритмы. Теория и практика. -М.: Мир, 1980.

17. Свами М. Тхуласираман К. Графы, сети и алгоритмы. -М.: Мир, 1984.

18. Басакер P. Саати Т. Конечные графы и сети. -М.: Наука, 1974. 21 .Берне К. Теория графов и ее применение. -М.: ИЛ, 1962.

19. Кристофидес Н. Теория графов. -М.: Мир, 1978.

20. Харари Ф. Теория графов. -М.: Мир, 1973.

21. Форд Л. Фалкерсон Д. Потоки в сетях. -М.: Мир, 1966.

22. Дегтярев К. Ю. Хныкин А. П. Математические основы теории систем. Учебное пособие. МГАПИ. 1996.

23. Волченская Т. В. Теория графов. Учебное пособие. Пенза, 1998.

24. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ. М.: Высшая школа, 1989. - 368 с.

25. Меерович Г. А. Эффект больших систем. М.: Знание, 1985.

26. Бусленко Н.П. Моделирование сложных систем. -М.: Наука, 1978. 396 с.

27. Месарович М. Общая теория систем и её математические основы //Исследования по общей теории систем: Сб. переводов / Под ред. Садовского В. Н. И Юдина Э. Г. М.: Прогресс, 1969. -с. 165 - 180.

28. Нечипоренко В. И. Структурный анализ систем. М.: Советское радио, 1977. -213 с.

29. Советов Б. Я., Яковлев С. А. Моделирование систем. Учебник для вузов. -М.: Высшая школа, 1985. -271 с.

30. Свами М., Тхуласираман К. Графы, сети, алгоритмы. Пер. с англ. -М.: Мир, 1984.-450 с.

31. Харари Ф. Теория графов. Пер. с англ. -М.: Мир, 1973. 300 с.

32. Перегуда А. И., Повякало А. А. Учебное пособие по курсу "Моделирование систем". Обнинск: ОИАЭ, 1987. -74 с.

33. Белов В. В., Воробьёв Е. М., Шаталов В. Е. Теория графов. М.: Высшая школа, 1976.-391 с.

34. Gould P. Q-analysis or a language of structure: an introduction for social scientists, geographers and planners // Int. Journal Man-Machine Studies? Vol.13,1980. -pp. 169-199.

35. Warfield J. N. Binary matrixes in system modeling // IEEE Transactions on systems, man and cybernetics, vol. CMS-3, N5, 1973. pp. 441-449.44 .Johnson J. H. Q-discrimination analysis // Environment and Planning B, vol.8, N2, 1981. pp. 419-434.

36. Cullen I. Q-analysis and the theory of social scientific knowledge // Environment and Planning B: Planning and Design, vol.10, 1983. -pp. 393-401.

37. Seidman S. B. Relational models for social systems // Environment and Planning B: Planning and Design, vol.14, 1987. -pp. 135-148.

38. Harary F., Norman R., Cartwright D. Structural models an introduction to the theory of directed graphs. - N.Y.: John Wiley, 1965.

39. Dowker С. H. Homology groups of relations //Annals of Mathematics, vol.56, N1, 1952. pp. 84-95.

40. Blum H. F. Complexity and organization // Sunthese, vol.XV, N1, 1963. -pp. 59-65.

41. Ash by W. R. Some peculiarities of complex systems // Cybernetics Medicine, vol.9, N2, 1973.-pp. 1-7.

42. Earl C. F., Johnson J. H. Graph theory and Q-analysis // Environment and Planning B, vol.8, 1981, -pp. 367-391.

43. Bahm A. J. Wholes and parts // The Southwestern Journal of Philosophy, N3, 1972.-pp. 17-22.

44. CastiJ. L. Polyhedral dynamics II: Geometrical structures as a basis for decision making in complex systems. - Luxembourg, IIASA (report), 1976. - 20 p.

45. Johnson R. Barton G. Structural analysis and the development of feedback control schemes // Computers and chemical engineering, vol.9, 1985. pp. 547 - 555.

46. Griffiths H. B. Using mathematics to simplify Q-analysis // Environment and Planning B: Planning and Design, vol.10, 1983. -pp. 403-422.

47. Couclelis H. On some problems in defining sets for Q-analysis // Environment and Planning B: Planning and Design, vol.10, 1983. -pp. 423-438.

48. Atkin R. H. From cohomology in physics to q-connectivity in social science // Int. Journal Man-Machine studies, vol.4, 1972. -pp. 139-167.

49. Johnson J. H. Q-analysis: a theory of stars // Environment and Planning B. vol.11, 1984.-pp. 457-469.

50. Дектярёв К. Ю. Исследование поведения сложных систем методами полиэдральной динамики / Отчёт пл НИР, НПО "Взлёт", per. N 01900057878, 1989. 18 с.

51. Seidman S. В. Rethinking backcloth and traffic: perspectives from social network analysis and Q-analysis // Environment and Planning B: Planning and Design, vol.10, 1983. pp. 439-456.

52. Hilton P. J., Stammbach U. A. A course in homological algebra. N.Y.: Springer, 1971. -338 p.

53. Стрейц В. Метод пространства состояний в теории дискретных линейных систем управления. М.: Наука, 1985. - 290 с.

54. Пентл Р. Методы системного анализа окружающей среды. Пер. с англ. М.: Мир, 1979. -215 с.

55. Джефферс Дж. Введение в системный анализ: применение в экологии. Пер. с англ М.: Мир. - 256 с.

56. Биологическая кибернетика. Учебное пособие для вузов, изд. 2-е дополн. / Под ред. Когана А. Б. М.: Высшая школа, 1977. - 408 с.

57. Понгрягин Л.С. Основы комбинаторной топологии. -М.: Наука, 1976.-136 с.

58. Кофман А. Введение в теорию нечетких множеств. М.: Радио и связь, 1982.

59. Саати Т. Принятие решений. Метод анализа иерархий. Пер. с англ. М.: Рад^о и связь1993. -320 с.

60. Основы кибернетики. Теория кибернетических систем. / Том 2. Под. ред. Пупкова К.А. -М.: Высшая школа, 1976. -408 с.

61. ФриО Э. Элементарное введение в абстрактную алгебру. Пер. с венгерок. -М.: Мир, 1979.-262 с.

62. Rosen R. Complexity as a system property// Int. Journal General System, vol.3, 1977.-pp. 227-232.

63. Шафаревич И.P. Основные понятия алгебры / серия «Современные проблемы математики. Фундаментальные направления», том 11. -М.: Наука, 1986

64. Hsu Z.H., Lam К. Т. Topological code of graphs // Journal of the Franklin Institute, vol. 329, N1, 1992.-pp. 99-109.

65. Саати Т., Керне К. Аналитическое планирование. Организация систем. -М.: Радю и связь, 1991. 224 с.

66. Казаринов М.Ю. Детерминизм в сложных системах управления и самоорганизации. Изд-во ЛГУ, 1990. - 160 с.

67. Клир Дж. Системология. Автоматизация решения системных задач. Пер. с англ М.: Радио и связь, 1990. - 540 с.