Миронов С.В., Пищухин А.М. Метасистемный подход в управлении

Подождите немного. Документ загружается.

281

На рисунке Г.18 показана более сложная решетка (&

/i, ≤ ). Перестановоч-

ные классы эквивалентности G-структур снова выделены жирным шрифтом,

равно как С-структуры и Р-структуры, сгруппированные по классам r-

эквивалентности. Каждому такому классу соответствует граф

и две ка-

нонические структуры C

и P

∈

). Для того чтобы более ярко проде-

монстрировать общие свойства этой решетки, на рисунке Г.19 перестано-

вочные классы С-структур обозначены только их идентификаторами и выде-

лены классы r-эквивалентности

Рисунок Г.18. Решетка с указанием классов r-эквивалентности и

канонических G- и Р-структур

282

Рисунок Г.19 – Упрощенная схема ре- Рисунок Г.20 – Решетка (&

/i, ≤ )

шетки (&

/i, ≤), полностью показан-

ной на рисунке Г.18

На рисунке Г.20 изображена решетка (&

/i, ≤), являющаяся подрешеткой

(

/i, ≤). Число около каждой схемы указывает на число различных С-

структур, входящих в перестановочный класс эквивалентности, показанный

на этой схеме; числа, помещенные около дуг, указывают на число непосред-

ственных уточнений С-структуры из данного перестановочного класса экви-

валентности в другой класс. Как уже объяснялось выше, эта решетка изо-

морфна решеткам, определенным на

/i, P

/i и (&

/i).

В то время как полные решетки (&

, ≤) представляют основу для ло-

кального уровня вычислений в задаче реконструкции, решетки (&

, ≤) и их

изоморфизмы являются основой для глобальных вычислений. Для работы на

глобальном уровне вычислений необходима процедура, порождающая для

любой заданной С-структуры C

∈

N) все непосредственные уточнения

в решетке (&

, ≤). Ниже приводится одна такая процедура, использую-

щая представление С-структур в виде графов.

283

Уточняющая процедура для С-структур (или КС-процедура). Дана С-

структура С

∈&

и соответствующий граф r

). Нужно определить все

непосредственные уточнения на множестве.

1) исключить одно ребро из графа r

), скажем ребро (a, b);

2) разделить каждый элемент х из С

, который содержит а и b на два

элемента х

= х - {b} и x

= x - {а} и заменить х из C

на x

и x

;

3) исключить все избыточные х

и x

, полученные на шаге 2 и записать

полученный результат в качестве непосредственного уточнения C

в решетке

,≤);

4) выполнить шаги 1—3 для всех ребер графа r

) и остановиться.

Данная процедура имеет следующие обоснования: 1) имеется взаимно одно-

значное соответствие между множествами R

и &

и, следовательно, любое изме-

нение графа приводит к изменению соответствующей С-структуры; 2) чем

меньше число ребер графа, тем более уточненной является соответствую-

щая С-структура; 3) поскольку никакой из циклов в вершинах нельзя исклю-

чить без нарушения .условия покрытия соответствующей С-структуры, то

наименьшим допустимым сокращением графа является исключение одного из

ребер. Таким образом, число ребер в графе определяет число непосредственных

уточнений соответствующей С-структуры.

Пример Г.18. Рассмотрим граф

и соответствующую С-структуру C

(ри-

сунок Г.21,а). Этот граф имеет шесть ребер и, следовательно, шесть непо-

средственных уточнений этой С-структуры. Они изображены на рисунке

Г.21,б. Например, уточнение получается с помощью RС-процедуры следую-

щим образом: 1) из графа

исключается ребро (Г,5) и получается граф

;

2) элемент (2, 4, 5} из C

(единственный элемент С

содержащий и 4 и 5)

разбивается на элементы (2, 5} и {2, 4}; 3) поскольку элемент {2, 4}

является единственным избыточным элементом ({2, 4} ⊂ {2, 3, 4}), он

исключается, а полученный результат С

={{1, 2}, {2, 5}, (2, 3, 4}}

записывается как непосредственное уточнение С

Так как элементы Р-структур представляют собой просто ребра со-

ответствующих графов, то процедура уточнения Р-структур (или RР-

процедура) совершенно тривиальна. Она состоит в исключении отдель-

ных ребер из заданного графа [смотри шаг 1 RС-процедуры] и интерпретации

результатов как Р-структур.

Полезны также процедуры, с помощью которых получаются все непо-

средственные укрупнения для множеств G-, С- и Р-структур. Они нужны для

определения полного структурного соседства заданной структуры. Формули-

рование этих процедур мы предоставляем читателю в качестве упражнения

(смотри также рисунок Г.10). Примеры такого соседства для трех этих ти-

пов структур приведены на рисунках Г.22 - Г.2Г. В этих примерах структуры

обозначены соответственно как G, С и Р. Их непосредственные уточнения

помечены нижними индексами, а непосредственные укрупнения - верхними.

На рисунке Г.22 показано, что в структурное соседство данной G-структуры

могут входить G-структуры, входящие в другой класс r-эквивалентности (на

рисунке Г.22 это структура G

). Чтобы непосредственные уточнения принад-

284

лежали тому же классу r-эквивалентности, можно слегка модифицировать

RG-npoцедуру, заменив условие |

S|≥ 2 на шаге 3 условием |

S |>2.

При

Рисунок Г.21. Пояснение к RС-процедуре: а — заданный граф и со-

ответствующая С-структура; б — непосредственные уточнения C

285

Рисунок Г.22. Структурное соседство G-структуры G

этом запрещается изменять элементы, содержащие только две вершины, и,

следовательно, граф данной r-структуры остается неизменным.

Представление о непосредственных уточнениях (или укрупнениях) струк-

тур различных типов можно использовать для разбиения соответствующего

множества структур на блоки структур, эквивалентных в смысле уровня

уточнения, т. е. таких структур, которые достигаются от универсальной

верхней границы {N

} соответствующей решетки уточнения за одинаковое

число шагов уточнения. Будем называть эту эквивалентность эквивалентно-

стью уровня уточнения и обозначать

≡

. Так, например, структуры G

, G

на

рисунке Г.22 - l-эквивалентные G-структуры из множества &

; структуры, по-

казанные на рисунке Г.21,б, - l-эквивалентные С-структуры из множества

; структуры Р

, Р

, P

на рисунке Г.24 являются l-эквивалентными

Р-структурами из множества &

Г.

Для того чтобы можно было составить представление о скорости роста

числа структур этих трех типов с ростом п, а также числа их классов i- и l-

эквивалентности, в таблице Г.12 приведены соответствующие данные для

п ≤ 7. Понятно, что

,|R||,R||P||&|

/)n(n

nnnn

−

286

Рисуноу Г.23 - Структурное соседство С-структуры С

Рисунок Г.24 - Структурное соседство Р-структуры

287

Таблица Г.12 - Число G-структур в &

и &

, С-структур и их

классов i-эквивалентности и классов l-эквивалентности для n ≤ 7

2 3 4 5 6 7

4 18 166 7,579 7,828,352 2,414,682,040,996

2 9 114 6,894 7,785,062 2,414,627,396,434

2 8 64 1,024 32,768 2,097,152

/i|

3 8 28 208

/i |

2 5 20 180

/i |

2 4 П 34 156 1,044

/l|

3 7 15 31 63 127

/l |

2 5 12 27 58 121

/l |

2 4 7 11 16 22

где показатель п(п — 1)/2 — общее число возможных ребер в графе, опреде-

ленном на N

. Ясно также, что |G

/1|=п(п—1)/2+1. Вычисление |R

/i| для

заданного более сложно, но эта задача уже решена в теории графов (смотри

раздел Г.11). Приведенные в таблице Г.12 значения |G

|, |G

/i|, |G

/l|,

|, |G

/i| и |G

/l| известны только для п≤7.

Введем упоминавшиеся уже структуры еще одного типа. Это такие

структуры, для которых при работе с вероятностными системами для опре-

деления несмещенной реконструкции не нужна итеративная процедура со-

единения. Обычно их называют ациклическими структурами.

Для решения задачи реконструкции наибольший интерес представля-

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

строго ациклическими структурами или L-структурами. G-структура

∈G

является L-структурой тогда и только тогда, когда не существует

такой пары (а, b)

∈

, что она входит в некий элемент G

и связана через

несколько соединенных элементов. Будем множество L-структур для не-

коего п обозначать L

Определим множество L

формально. Пусть дана G-структура

∈&

. Для любой пары (a, b)

∈

пусть

a,b

={x|x

∈

, {а, b ⊂ х}.

Тогда G

является L-структурой (G

∈

) тогда и только тогда, когда не суще-

ствует пары (a, b)∈N

, являющейся элементом транзитивного замыкания r

- Х

а,b

Очевидно, например, что все структуры из множества G

(рисунок

Г.16), за исключением структуры G

={{1, 2}, {2, 3}, (3, 1}}, явля-

ются L-структурами. В множестве G

только три структуры не являются

L-структурами. Они принадлежат к одному и тому же классу i-эквива-

лентности, который можно, например, представить С-структурой

С={{1, 2}, {2, 3}, {3, 4}, {4, 1}}. В самом деле, транзитивное замыка-

ние r

(С - X

1,2

)- это N

, и, следовательно, пара (1, 2) является ее элемен-

том.

288

L-структуры отличаются тем, что для них не нужно использовать ите-

ративную процедуру соединения независимо от порядка, в котором объеди-

няются элементы рассматриваемой L-структуры. Ациклические структуры,

не являющиеся L-структурами, этим замечательным свойством не обла-

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

цедуры соединения, нужно применять базовую процедуру соединения к

элементам, расположенным в определенном порядке. Определение таких

порядков требует сложных вычислений и проверок, так что методологиче-

ское значение таких структур существенно уступает значению L-структур.

С помощью различных понятий, введенных в этом разделе, можно

более конкретно сформулировать задачу реконструкции. Дана обобщенная

система и множество заданных пользователем реконструктивных гипотез

(базирующихся на множестве G

, &

, P

или L - cтpyктyp). Решение зада-

чи реконструкции сводится к выбору подмножества данного множества в

соответствии с некоторыми требованиями. Обычно требуется, чтобы: 1)

расстояния, соответствующие выбранным гипотезам, были как можно

меньше и 2) сами гипотезы были, возможно, более уточненными. Оба эти

требования предполагают упорядочение множества реконструктивных гипо-

тез. Упорядочение в соответствии с требованием 2 фиксировано - это час-

тичное упорядочение по структурному уточнению с решеткой, свойства кото-

рой описаны выше. Упорядочение согласно требованию 1 - его можно назвать

упорядочением по расстоянию — не фиксировано. Оно зависит от данной

обобщенной системы и выбранного типа расстояния и определяется только вы-

числением несмещенных реконструкций и расстояний отдельных реконструк-

тивных гипотез.

Если используется расстояние, определяемое по формуле (Г.40)

для вероятностных систем [или по формуле (Г.42) для возможностных сис-

тем], которое является мерой количества информации, потерянной при замене

обобщенной системы реконструктивной гипотезой, то существует опреде-

ленное предупорядочение по расстоянию: информационное расстояние моно-

тонно не убывает с увеличением уточнения реконструктивных гипотез.

Кроме того, оба варианта информационного расстояния аддитивны для

любого пути на используемой решетке уточнения. Это значит, что

D (f

, f

) =D (f

, f

) + D (f

, f

) (Г.43)

для любых трех реконструктивных гипотез х, у, z одной обобщенной сис-

темы, таких, что x ≥ y ≥ z. Свойства предупорядоченности и аддитивности

очень полезны при решении задачи реконструкции и придают особую важ-

ность информационному расстоянию. В дальнейшем при обсуждении задачи

реконструкции всегда будет предполагаться, что используется соответст-

вующая версия информационного расстояния (то есть вероятностная или

возможностная, базовая или порождающая).

Сочетание упорядочения по расстоянию с упорядочением по уточнению

образует объединенное упорядочение для задачи реконструкции. Теперь

множество решений задачи реконструкции характеризуется с помощью этого

комбинированного упорядочения следующим образом: это множество пред-

289

ставляет собой такое подмножество реконструктивных гипотез, в которое не

входят гипотезы, худшие, чем любая другая гипотеза. Слово «худшие» ис-

пользуется здесь в обычном смысле: гипотеза h

хуже гипотезы h

тогда

и только тогда, когда или h

является менее уточненной и ее расстояние

не меньше, чем у h

или у h

, большее расстояние, чем у h

, и в то же время

она не является более уточненной, чем h

. Элементы этого множества реше-

ний будем называть подходящими реконструктивными гипотезами.

Теперь видно совершенное сходство задачи реконструкции с дву-

мя рассмотренными выше задачами - задачей определения подходящих сис-

тем с поведением (раздел В.4 и В.6) и задачей определения подходящих уп-

рощений заданной системы с поведением (раздел В.9). Если упорядочение

по нечеткости и упорядочение по сложности из этих задач сопоста-

вить соответственно с упорядочением по расстоянию и упорядочением

по уточнению из задачи реконструкции, то сходство этих трех задач станет

очевидным. Предоставляем читателю использовать это сходство для фор-

мального определения комбинированного упорядочения и множества реше-

ний для задачи реконструкции.

Структурные Обобщенная

ограничения система В

Средстда порождения

Рисунок Г.25 - Общая схема процесса решения задачи реконструкции

Мы видим, что задачи, связанные с подъемом по эпистемологической ие-

рархии систем, а также с упрощением систем, образуют важнейшую кате-

горию задач, имеющих следующие общие черты:

ДАНО:

множество X рассматриваемых систем;

Процедура порождения

реконструктивных гипотез

еконструктидные

гипотезы

Процедуры оценки рекон-

структивных гипотез

Средства оценки и критерии

Вывод

еконструктивная систе

и ее характеристики

Процедуры принятия ре-

шения

Кр

ите

ии п

инятия

ешения

родолжение работы с

ножеством реконст-

уктидных гипотез X

Стоп

290

множество отношений порядка

≤

cba

,, на X.

МНОЖЕСТВО РЕШЕНИИ:

)},yxxy)(Xy(|Xx{X

≤

⇒∈∀∈=

где

≤

- объединенный порядок предпочтения на X, определенный для

всех х, у∈Х следующим образом:

≤

тогда и только тогда, когда yx

≤

и yx

≤

, и yx

≤

, и ...

В процессе решения задачи реконструкции необходимы три

набора процедур:

1) процедуры порождения всех нужных реконструктивных гипотез;

2) процедуры оценки и сравнения порожденных реконструктивных ги-

потез с точки зрения целей задачи реконструкции;

3) процедуры, которые на соответствующих этапах процесса решения

задачи принимают решение о том, какие из порожденных реконструктив-

ных гипотез должны быть включены в множество решений, какие исполь-

зованы для дальнейшего порождения реконструктивных гипотез и должен

ли процесс решения продолжаться или закончиться.

На рисунке Г.25 показано, каким образом эти три набора процедур

объединяются в единый процесс решения. Ядром процесса является порож-

дение всех подходящих реконструктивных гипотез. Удобно это делать,

порождая соответствующие структуры, которые затем интерпретируются

как реконструктивные гипотезы для заданной обобщенной системы. Ин-

терпретация эта сводится к установлению соответствия между перемен-

ными обобщенной системы и целыми числами, которыми идентифицированы

узлы структур, а также к вычислению, если нужно, проекций обобщенной

функции поведения. Порожденные структуры можно разными способами

сократить, что уменьшает время вычислений и их цену, а также, возможно,

и по другим соображениям. Например, можно выбрать подмножество со-

ответствующих G-, С- или L-структур или ограничиться рассмотрением

только тех уровней уточнения (классов l-эквивалентности), для которых

потеря информации не превышает некоторого заданного пользователем зна-

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

жет быть ограничен либо набором рассматриваемых структур, либо огра-

ничениями на способ порождения.

Для достижения гибкости в решении задачи реконструкции УРСЗ

должен располагать разнообразным набором способов порождения, но

этот вопрос находится за пределами проблем, связанных с архитектурой

УРСЗ. Это способы порождения соответствующих уточнений (или укрупне-

ний) имеющихся реконструктивных гипотез, примерами чему служат RG-

процедура и RС-процедура (и их укрупняющие аналоги).

Как уже говорилось выше, порождение структур также может быть

организовано на нескольких уровнях вычислений. Так, например, RС-