МНОГОАГЕНТНЫЕ СИСТЕМЫ В.Б.Тарасов Московский государственный технический университет им. Н.Э. Баумана
ЛЕКЦИЯ 1. ОСНОВЫ СИСТЕМОЛОГИИ СИСТЕМОТЕХНИКА СИСТЕМНЫЙ АНАЛИЗ СИСТЕМОЛОГИЯ
СИСТЕМОЛОГИЯ Системология (общая теория систем) есть междисциплинарная область, разрабатывающая методологические принципы исследования и моделирования систем любой природы. Основными понятиями системного подхода являются понятия системы и среды, элемента и связи, функции и структуры, организации и поведения, адаптации и развития.
СИСТЕМНЫЙ АНАЛИЗ Системный анализ – это методология общей теории систем, заключающаяся в исследовании объектов путем представления их в качестве систем, проведения их структуризации и дальнейшего углубленного изучения. Системный анализ связан с использованием системного подхода к изучению объектов любой природы. Основными понятиями системного подхода являются понятия системы и среды, элемента и связи, функции и структуры, организации и поведения, адаптации и развития. В системной методологии активно используется принцип относительности, согласно которому любая система и ее границы всегда зависят от наблюдателя (исследователя), его целей. Различие между элементами и системами относительно: системы, выделяемые на некотором уровне анализа (одним наблюдателем) могут рассматриваться как элементы на более общем уровне (для другого наблюдателя), и наоборот. Впервые на необходимость учета взаимодействия между системой и наблюдателем указал еще У.Р.Эшби.
Чем является система? Что делает система? СТРУКТУРА ПОВЕДЕНИЕ (ФУНКЦИОНИРОВАНИЕ) ТРЕУГОЛЬНИК ЛЕМУАНА Исследование систем можно представить как треугольник, включающий онтологический, функциональный и генетический полюса (треугольник Лемуана) [Le Moigne, 1983]. Первый полюс соответствует вопросу «Чем является система?», второй – вопросу «Что делает система?», а третий – вопросу «Как развивается система?». Чем становится система? РАЗВИТИЕ ОСНОВНЫЕ ПОДХОДЫ В СИСТЕМОЛОГИИ: 1) функционально-структурный; 2) поведенческий; 3) эволюционно-органический
1. Система как множество элементов с отношениями Все классические определения системы сводятся к ее выражению в виде пары, состоящей из элементов и отношений (связей) между ними, что можно формально записать в виде S = X, R, где X - множество элементов, а R – множество отношений. Из формулы видно, что можно построить различные виды систем по: а) числу и типам элементов, образующих систему; б) по типам и интенсивности отношений между ними [Клир,1990]. В частности, по числу элементов системы подразделяются на малые, большие и сверхбольшие, а по типам элементов – на однородные и неоднородные. СОДЕРЖАТЕЛЬНЫЕ И ФОРМАЛЬНЫЕ ОПРЕДЕЛЕНИЯ СИСТЕМЫ
2. Cистемой называется структурно-функциональная целостность. Система рассматривается как совокупность структур, обеспечивающих выполнение определенных функций. Это определение системы опирается на исходные понятия функции и структуры и отражает идеи единого функционально-структурного подхода в системологии. Соотношение между понятиями функции и структуры аналогично соотношению между понятиями содержания и формы. Функции системы, выражающие ее содержание, характеризуют взаимосвязь между частями и целым, между компонентами и целостной системой, а также между системой и окружающей средой. Соответственно различаются внешние функции (взаимосвязи системы со средой) и внутренние (взаимосвязи между элементами и системой). Обычно определение функции означает выделение одноименной подсистемы. Структура системы означает форму ее представления в виде составных частей. Структура охватывает множество элементов, образующих состав системы, вместе с базовыми связями между ними.
ПРИМЕР ВЫДЕЛЕНИЯ ОСНОВНЫХ ФУНКЦИЙ ОТКРЫТОЙ СИСТЕМЫ КОГНИТИВНАЯ ФУНКЦИЯ СРЕДА СИСТЕМА РЕГУЛЯТИВНАЯ ФУНКЦИЯ РЕСУРСНАЯ ФУНКЦИЯ
CРЕДА СИСТЕМЫ ВНУТРЕННЯЯ СРЕДА (ЦЕЛИ, ЗАДАЧИ, РЕСУРСЫ) МАКРОСРЕДА МИКРОСРЕДА СРЕДА ВНЕШНЯЯ СРЕДА
МИКРОСРЕДА СИСТЕМЫ (НА ПРИМЕРЕ ПРЕДПРИЯТИЯ) МИКРОСРЕДА СИСТЕМЫ (НА ПРИМЕРЕ ПРЕДПРИЯТИЯ) Основные параметры рынка (емкость рынка, спрос на конкретные позиции номенклатуры товаров, текущая платежеспособность потребителей и их требования к качеству товара) Заказчики Поставщики Подрядчики Конкуренты ПРЕДПРИЯТИЕ (ОРГАНИЗАЦИЯ) Потребности и предпочтения заказчиков клиентоцентризм
МОРФОЛОГИЯ СИСТЕМЫ Термином «морфология системы» охватывается ее функциональная и пространственная организация, которые определяются понятиями состав и структура. В технике термин «морфология» означает строение, структурную форму изделия, организованного в соответствии с его функциями, материалом и способом выполнения. В морфологической структуре можно выделить два аспекта: пространственный и функционально-технологический. Так пространственные структуры образуются отношениями типа «целое-часть», расстояние («близость – удаленность»), окрестность, направление, взаимное положение, размер, и т.п. в физическом пространстве, а также отношениями типа «сходство-различие» в абстрактном пространстве свойств. Примерами пространственных структур служат варианты размещения станков в заводских цехах, схема перемещения мастера в рабочих помещениях в течение смены, и т.д
СОДЕРЖАТЕЛЬНЫЕ И ФОРМАЛЬНЫЕ ОПРЕДЕЛЕНИЯ СИСТЕМЫ 3. Система как целенаправленный объект Цель как системообразующий фактор Cистема есть комплекс взаимодействующих (и «взаимосодействующих», т.е. кооперирующих) элементов, объединенных для достижения определенной цели [П.К.Анохин, 1978]. Здесь цель может пониматься как образ потребного будущего, опережающее отражение желаемого результата и выступает как системообразующий фактор. Сегодня в системной методологии активно используется принцип относительности, согласно которому любая система и ее границы условны и всегда зависят от наблюдателя (исследователя), его целей. Впервые на необходимость учета взаимодействия между системой и наблюдателем указал еще У.Р.Эшби
СОДЕРЖАТЕЛЬНЫЕ И ФОРМАЛЬНЫЕ ОПРЕДЕЛЕНИЯ СИСТЕМЫ 4. Организационная система как множество отношений Организация – это множество отношений между составляющими (индивидами), образующих целое или систему, которая обладает новыми, неизвестными свойствами по сравнению с этими составляющими. (А.А.Богданов. «Тектология: Всеобщая организационная наука», 1912 г.) Система: Организация: элементы отношения отношения элементы (восходящее проектирование) (нисходящее проектирование)
ОПРЕДЕЛЕНИЯ ОРГАНИЗАЦИИ Организация – такая социо-техническая система, в которой состояние любой части можно определить, только зная состояние всей системы (Р.Акофф и Ф.Эмери «О целеустремленных системах») ОРГАНИЗАЦИЯ = САМООРГАНИЗАЦИЯ (автономия) РЕОРГАНИЗАЦИЯ (преобразование, развитие) ЭКООРГАНИЗАЦИЯ (адаптация к среде) (Э.Морен «Метод»)
ОРГАНИЗАЦИЯ: ИЕРАРХИЧЕСКАЯ СИСТЕМА Иерархическая система задается парой HS = X, h, где X – множество, а h – отношение, называемое иерархией, (пример, отношение «начальник-подчиненный»), т.е. антисимметричное, антирефлексивное, транзитивное, полное отношение
ОСНОВНЫЕ ХАРАКТЕРИСТИКИ МНОЖЕСТВА Границы – четкие или Двухуровневая иерархия (по вложенности): расплывчатые неполностью определенные множества Мощность X Мера m (X) Порядок A B, A,B X X CВЯЗЬ МЕЖДУ ИЕРАРХИЕЙ И НЕОПРЕДЕЛЕННОСТЬЮ H = (A,B), A B, A,B X H (X) A B Область определенности Область неопределенности
КЛАССИЧЕСКОЕ ОПРЕДЕЛЕНИЕ МЕРЫ Аддитивность меры Понятие меры есть одно из важнейших математических понятий, как, впрочем, и понятие интеграла, соответствующего данной мере. Оно является естественным обобщением понятия длины отрезка, площади плоской фигуры, объема пространственной фигуры. Классические меры удовлетворяют условию аддитивности. Пусть А и В– некоторые события, а Х – полное множество событий. Мерой называется функция множества m: 2 X R +, R + =[0, ), которая удовлетворяет следующим условиям: 1) А 2 X, А X m (A) 0; 2) m( ) = 0; 3) А, В 2 X, m (A B) = m (А) + m (В) – m (A B).
ВЕРОЯТНОСТНАЯ МЕРА И МЕРА ДИРАКА Наиболее известным случаем классической меры является нормальная мера или вероятностная мера А.Н.Колмогорова P: 2 X [0,1], которая удовлетворяет следующим условиям: 1 ) P( ) = 0, P(Х) =1 (ограниченность) 2) А,В 2 X, А В P(A) P(B)(монотонность) 3) А,В 2 X, А В= P(A B)=P(А)+P(В) (аддитивность ) В общем случае, берется -алгебра множеств, 2 X и аксиома аддитивности записывается в форме А i, А i = P ( А i ) = P(А i ). С вероятностной мерой связана статистика средних значений. Пусть x 0 есть заданный элемент в X. Частным случаем вероятностной меры является примитивный класс мер Дирака m D, определяемый соотношением: А 2 X, 1, если x 0 A m D (А) = 0 в противном случае. Мера Дирака есть частный случай вероятностной меры, соответствующий детерминированной сингулярной информации (мера полной уверенности).
ВЗАИМОЗАМЕНЯЕМОСТЬ МНОЖЕСТВ И ФУНКЦИЙ Еще Дж.фон Нейман отмечал, что понятия функции и множества являются взаимозаменяемыми: функция может быть рассмотрена как множество упорядоченных пар, а множество может быть выражено с помощью его характеристической функции: 1, если x X f(x) = 0, если x X Если взять понятие функции как первичное, то можно строить разные теории путем наложения ограничений на область определения и область значений рассматриваемой функции. Этот единый подход приобрел особую актуальность при построении нестандартных множеств и гибридных моделей, например, недоопределенных, переопределенных, нечетких множеств.
МУЛЬТИМНОЖЕСТВО Мультимножеством А называется множество, которое может включать повторяющиеся элементы. Пусть X = {x 1, …, x m } – обычное множество, все элементы которого различны. Мультимножеством А, порожденным множеством X, называется совокупность наборов одинаковых элементов вида А = {n A1 x 1, n A2 x 2,…, n Am x m }. В общем случае мультимножество можно задать с помощью двух базовых функций: характеристической функции f : X {0, 1} и функции кратности n. Функция кратности мультимножества выражается как n: X N 0, где N 0 = {0,1,2,…} – множество неотрицательных целых чисел. По сути, формализация мультимножества сводится к определению его функции кратности.
ИНТЕРПРЕТАЦИИ МУЛЬТИМНОЖЕСТВА 1. Множество с различной частотой встречаемости элементов 2. Множество, состоящее из n экземпляров («точных копий») каждого типа x X (X – множество типов). 3. Взвешенное множество, когда кратность отождествляется с весом n=w. А={w 1 x 1, w 2 x 2,…, w n x n }, где w i = w A (x), а выражение w i x i можно понимать как алгебраическое произведение элемента x i и его веса w i, i=1,…,n. n x Векторы и матрицы также могут использоваться для наглядного представления мультимножеств Петровский А.Б. Пространства множеств и мультимножеств. – М.: Едиториал УРСС, 2003.
НЕКОТОРЫЕ ВИДЫ НЕСТАНДАРТНЫХ МНОЖЕСТВ Неполностью (избыточно) определенные множества X = X +, X, X 0, где X + = {x x X }, X = {x x X }, X 0 = {x x ?X }, 1. Переопределенное множество – это множество с избыточной и противоречивой информацией относительно принадлежности его элементов +1, если x A; А = {x x i А, x j А, x k ( )А} f(x) = 0.5, если x( )А; 0, если x А. 2. Недоопределенное множество – это множество с неполной информацией относительно принадлежности его элементов +1, если x A; А = {x x i А, x j А, x k ( )А} f(x)= 0.5, если x( )А; 0, если x А.
ОСНОВЫ МАТЕМАТИЧЕСКОЙ ТЕОРИИ ОТНОШЕНИЙ Классическое n-арное отношение определяется как подмножество декартова произведения произвольных n множеств: R X 1 X 2 … X n. На практике часто ограничиваются рассмотрением бинарных отношений. 1. Пусть X и Y – два различных множества. Тогда подмножество декартова произведения R X Y называется бинарным отношением в широком смысле или соответствием. 2. Пусть имеем декартово произведение множества X на себя. Тогда бинарное отношение определяется формулой R X X. Другая запись бинарного отношения: x r y 1, если x=y Отношение E (x,y) = называется единичным, т.е. играет роль 0, если x y единицы для операции композиции E R = R E = R. Обратное отношение определяется как R 1 (x,y) = R (y,x), x,y X
МАТРИЦА ОТНОШЕНИЙ Пусть X есть n-элементное множество, а R – отношение на этом множестве. Перенумеруем элементы множества X целыми числами от 1 до n. Построим теперь квадратную матрицу размером n n. Ее i-я строка соответствует i-му элементу множества X, а j-й столбец – j-му элементу множества X. Обозначим элемент, стоящий на пересечении i-й строки и j-го столбца через r ij. Тогда матрица бинарного отношения задается следующим образом 1, если выполняется R(х i, x j ) 1, если выполняется R(х i, x j ) f R = r ij.= 0 в противном случае, 0 в противном случае, Матрицу, составленную из элементов r ij, принято обозначать r ij. Она содержит всю информацию о том, для каких пар элементов из X выполнено отношение R. Итак, отношение R на конечном множестве X можно задать его матрицей r ij.Матрица, для которой r ij = 0 при всех i и j, задает пустое отношение, которое не выполняется ни для одной пары.
СВОЙСТВА ОТНОШЕНИЙ Пары свойств: Свойство – Антисвойство
КОММЕНТАРИИ К СВОЙСТВАМ ОТНОШЕНИЙ: РЕФЛЕКСИВНОСТЬ - АНТИРЕФЛЕКСИВНОСТЬ I. Рефлексивность: E R, f R (x, х) = 1, x X. I. Рефлексивность: E R, f R (x, х) = 1, x X. Рефлексивное отношение всегда выполняется между объектом и им самим. самим. Рефлексивное отношение можно представить матрицей, у которой на главной диагонали стоят единицы. В графе, изображающем рефлексивное отношение, каждая вершина имеет петлю. I*. Антирефлексивность: R E =, f R (x, х) = 0, x X Антирефлексивное отношение выполняется лишь для различных, несовпадающих объектов. Матрица, представляющая антирефлексивное отношение, имеет на главной диагонали нули, а в соответствующем графе петли непременно отсутствуют.
КОММЕНТАРИИ К СВОЙСТВАМ ОТНОШЕНИЙ: СИММЕТРИЧНОСТЬ - АНТИСИММЕТРИЧНОСТЬ II. Симметричность: R = R –1, x, y X. Свойство симметричности в теории отношений означает одновременное выполнение как прямого отношения R(x,y), так и обратного отношения R(y,x). В матрице, представляющей симметричное отношение, выполняется принцип зеркального отображения элементов относительно главной диагонали r ik = r ki. В соответствующем графе вместе с каждой стрелкой, идущей из вершины x в вершину y, имеется и аналогичная, противоположно направленная стрел ка. Поэтому симметричное отношение можно изображать неориентированным графом. II*. Асимметричность: R R –1 =, x, y X. Из двух соотношений xRy и yRx, по меньшей мере, одно не выполнено. Для матричных элементов имеем равенство r ik r ki = 0.. Если отношение R асимметрично, то оно и антирефлексивно. Этот факт легко показать, подставив в r ik r ki = 0, i=k; получаем r kk 2 = 0, т.е. r kk = 0. Таким образом, граф асимметричного отношения не может иметь петель
КОММЕНТАРИИ К СВОЙСТВАМ ОТНОШЕНИЙ: ТРАНЗИТИВНОСТЬ III.Транзитивность: R R R или R 2 R, x, y, z X. Условие транзитивности означает, что если справедливы условия R(x,y) и R(y,z), то выполняется и R(x,z). Это условие можно наглядно представить на графе отношения R. Если точки x и z соединены путем, проходимым по направлению стрелок, то существует стрелка, ведущая непосредственно из вершины x в вершину z. Условие 3) определяет положительную транзитивность. В свою очередь, отрицательная транзитивность задается в виде R R R или R 2 R, x, y, z X. Замечание. Для рефлексивного отношения R транзитивность эквивалентна равенству R 2 =R. По индукции отсюда следует: если R(x,y 1 ), R(y 1,y 2 ), R(y n-1,z) то R(x,z). Транзитивным замыканием отношения R называется отношение, определяемое следующим образом : ^ R = R 1 R 2 R k..., где отношения R k определяются рекурсивно: R 1 =R, R 2 =R R, R k =R k-1 R. ^ Если отношение R транзитивно, то R=R.
ОТНОШЕНИЯ СХОДСТВА И ЭКВИВАЛЕНТНОСТИ Симметричное и рефлексивное отношение называется отношением сходства. Транзитивное отношение сходства есть отношение эквивалентности. На основе отношения эквивалентности получают классы эквивалентности и разбиения. Отношение эквивалентности E можно представить с помощью отображения из X в 2 X, где 2 X – множество всех подмножеств универсума X. Это отображение [ ] E : X 2 X задается в виде [x] E = {y X E(x,y)}. Подмножество [x] E есть класс эквивалентности, содержащий x. Если какие-то объекты принадлежат к одному и тому же классу эквивалентности, то они считаются неразличимыми. Семейство всех классов эквивалентности называется фактор-множеством и обозначается U/E={[x] E x U}. Оно определяет разбиение универсального множества X, т.е. семейство попарно неперекрывающихся подмножеств, объединение которых есть универсальное множество. Имеется взаимно-однозначное соответствие между отношениями эквивалентности и разбиениями множества.
ПРИБЛИЖЕННОЕ МНОЖЕСТВО Пусть Х – множество, а R X X – отношение неразличимости (эквивалентности). Тогда пара =(Х, R) образует пространство приближений. Классы эквивалентности по отношению R называются элементарными множествами в пространстве приближений, а любая совокупность элементарных множеств образует составное множество в. Произвольное подмножество A X можно точно определить на основе имеющейся информации, т.е. классов эквивалентности. Вместо этого каждое множество заменяется двумя множествами, которые называются нижним приближением RХ = {x x R X} (наибольшее составное множество, содержащееся в Х) и верхним приближением RХ = {x x R X} (наименьшее составное множество, содержащее X) соответственно. Pawlak Z. Rough Sets // International Journal of Computer and Information Sciences. – – Vol.11. – P
ОТНОШЕНИЯ РАЗЛИЧИЯ И РАССТОЯНИЯ (МЕТРИКИ ) Симметричное и антирефлексивное отношение называется отношением различия. Транзитивное отношение различия есть расстояние (метрика). Отметим, что для расстояний берется условие отрицательной транзитивности, обобщающее неравенство треугольника.
ОТНОШЕНИЯ ПРЕДПОЧТЕНИЯ И ПОРЯДКА Антисимметричные и рефлексивные отношения называются отношениями нестрогого предпочтения, а антисимметричные и антирефлексивные отношения – отношениями строгого предпочтения. Транзитивные отношения предпочтения называются нестрогими и строгими порядками соответственно. Если отношение порядка удовлетворяет к тому же условию полноты, то оно называется отношением полного порядка. Полные строгие порядки образуют иерархии. Бинарное отношение есть отношение порядка, если оно обладает следующими свойствами: (1) рефлексивность: х х, x X (2) транзитивность: если х у и у z, то х z, x, y, z X. (3) антисимметричность: если х у и у х, то х = у, x, y X. Бинарное отношение называется отношением предпорядка (квазипорядка), если оно удовлетворяющее следующим условиям: (2) рефлексивность: х х, x X (3) транзитивность: если х у и у z, то х z, x, y, z X.
КЛАССИФИКАЦИОННАЯ ТАБЛИЦА ОТНОШЕНИЙ
УПОРЯДОЧЕННОЕ МНОЖЕСТВО Частично упорядоченное множество есть пара POSET = X,, где X – множество, – отношение частичного порядка (антисимметричное: если x y и y x, то x = y, x,y X, x y рефлексивное: x x, x X транзитивное: если x y и y z, то x z, x,y,z X ). Частично упорядоченное множество становится цепью или линейно упорядоченным множеством, если помимо условий антисимметричности,рефлексивности и транзитивности выполняется еще и условие полноты (линейности): либо x y, либо y x, x,y X
РЕШЕТКА
АЛГЕБРАИЧЕСКАЯ СИСТЕМА Алгебраическая система задается тройкой AS = X,, П, где X – непустое множество, называемое носителем или основой алгебраической системы, – множество операций, П – множество предикатов. Заметим, что в могут входить константы, которые рассматриваются как нульместные функции. Объединение множеств операций и предикатов П называется сигнатурой. При П = алгебраическая система становится универсальной алгеброй, а При = она превращается в реляционную систему.
СОДЕРЖАТЕЛЬНЫЕ И ФОРМАЛЬНЫЕ ОПРЕДЕЛЕНИЯ СИСТЕМЫ 5. Понятие алгебраической системы как тройки AS = X,, П, где X – непустое множество, называемое носителем или основой алгебраической системы, – множество операций, – множество операций, П – множество предикатов. Заметим, что в могут входить константы, которые рассматриваются как нульместные функции. Объединение множеств операций и предикатов П называется сигнатурой.
АЛГЕБРАИЧЕСКИЕ СИСТЕМЫ: Универсальные алгебры Реляционные системы Алгебры Группоиды Полугруппы Моноиды Группы Группировки Упорядоченные множества Решетки Дистрибутивные решетки Алгебры де Моргана Алгебры Клини