Растригин Л.А. Адаптация сложных систем

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

2.2.4.1. Адаптивный выбор

программы сортировки массивов

Задача сортировки поступающего массива, т. е. упорядочения

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

задач в BC. Существует несколько методов сортировки, реали-

зованных в виде программ (2.2.5), которыми располагает BC.

Критерием эффективности (2.2.6) сортировки массива P

с помощью

алгоритма A

является, например, время сортировки. Если поток

поступающих на сортировку массивов имеет некоторую

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

р(P) и для этого распределения имеется наилучший метод А*

сортировки, то естественно найти такой метод, используя

альтернативную адаптацию.

Более того, если плотность распределения р(P) массивов

изменилась, что повлекло за собой изменение оптимальной прог-

раммы A*, то необходимо в процессе адаптации найти новую

программу и перейти к ней. Решение этой задачи рассмотрено

в пятой главе (§5.5).

2.2.4.2. Адаптация способов кодирования информации

в канале передачи данных вычислительной системы

Известно, что выбор оптимального метода (программы) коди-

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

свойств состояния канала. Пусть P — это состояние. Располагая

информацией о р(Р), т. е. о статистических свойствах состояния

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

время передачи одного бита информации, вероятность ошибки и т.

д.) выбрать код А*, наилучший из альтернативных А

, ..., А

. Так и

поступают в теории оптимального кодирования.

Однако свойства р(Р) реального канала связи изменяются во

времени непредвиденным образом и в широких пределах. Поэтому

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

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

имеющегося состояния P канала, и переходить к другой, оптимальной

при изменении состояния канала связи. Эта задача решается

методами альтернативной адаптации и рассмотрена в пятой главе (§

5.4).

Рассмотрим теперь системный уровень адаптации в BC.

2.2.5. Системная адаптация вычислительной системы

Эта адаптация затрачивает системное обеспечение BC, для того

чтобы повысить эффективность функционирования BC при

различных условиях эксплуатации.

Пусть P — условия эксплуатации BC, U — управляемый фактор

BC, который может изменяться целенаправленно в процессе ее

работы, а

q = q (P, U) (2.2.9)

— критерий функционирования BC, характеризующий эффективность

ее работы в условиях P при управлении U. Выражение (2.2.9) задается

алгоритмически, т. е. в виде правила оценки эффективности q

реальной (а не модельной) BC при различных P и U. Это

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

критерия

(2.2.10)

необходимого для синтеза

оптимального управления U*, решающего задачу

(2.2.11)

Здесь р(P) — статистические свойства условий

эксплуатации BC (плотность распределения этих условий), которые

обычно неизвестны.

Поэтому задачу поддержания BC в оптимальном состоянии

следует решать методами адаптации, т. е. изменять управляемый

фактор U, руководствуясь только наблюдениями значений критерия

(2.2.9).

Рассмотрим несколько конкретных задач адаптации BC на

системном уровне.

2.2.5.1. Адаптивная сегментация памяти

системного математического

обеспечения вычислительной

системы

Для нормального функционирования BC следует вводить в ее

оперативную память необходимую рабочую информацию, т. е.

программы, данные и т. д. Эта информация расположена во внешней

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

объема. Вызов информации в оперативную память производится

сегментами. Процесс обращения к внешней памяти занимает

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

(рассматривается однопрограммный режим работы BC). Отсюда

вытекает, что сегментация, т. е. объединение имеющихся блоков

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

обращения к внешней памяти была минимальной.

Оптимальная сегментация внешней памяти дает возможность

повысить КПД BC за счет увеличения процессорного времени. Однако

обращаемость (частота обращения) к внешней памяти зависит от

специфики решаемых задач, точнее, от последовательности

используемых блоков информации. Поэтому для различных задач

оптимальная сегментация внешней памяти будет различной.

Естественно изменять (адаптировать) эту сегментацию с изменением

потока решаемых ВС задач.

Формализуем задачу. Пусть р(P) — статистические свойства

вариантов P обращения к блокам информации внешней памяти, a U —

сегментация, т. е. определенное объединение блоков в сегменты. Тогда

свойства р(P) генерируют свойства межсегментных связей, т. е.

статистические свойства переходов от одного сегмента к другому.

Критерием эффективности (2.2.9) сегментации для данной задачи

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

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

Q(U) — эффективность сегментации (2.2.10). Однако для вычисления

необходимо знать р(P) — вероятностные свойства потребности в

информации, хранящейся во внешней памяти для обслуживания того

или иного потока задач, что обычно неизвестно.

Именно это обстоятельство заставляет обращаться к адаптивной

сегментации внешней памяти как способу отыскания оптимальной

сегментации при наличии статистической устойчивости р(P). Более

того, при изменении р(P) необходимо иметь возможность изменить

сегментацию — пересегментировать память, для чего также

необходимо обращение к процедуре адаптации.

Методы, используемые при этом, связаны с эволюционными

алгоритмами адаптации. Решение задачи адаптивной сегментации

методами эволюционной адаптации приведено в шестой главе (§ 6.2).

2.2.5.2. Адаптация

расположения информационных

блоков на магнитных дисках

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

минимизацией времени механического движения считывающих

головок от одного цилиндра к другому. Здесь роль сегментов вы-

полняют цилиндры, причем расстояние между ними разное, что

необходимо учитывать при расположении информационных блоков.

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

статистические свойства последовательности обращения к блокам, но

и взаимное расположение сегментов-блоков. Так, активно

взаимодействующие блоки следует хранить если не на

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

минимизировать время перемещения головок.

Аппаратом решения этой задачи являются методы эволюционной

адаптации, описанные в шестой главе, а само решение приведено в §

6.2.

2.2.5.3. Адаптивное распределение памяти

в многомашинной вычислительной системе (сети)

При решении задач с помощью многомашинной BC встает

проблема распределения памяти по отдельным ЭВМ BC. Вся

необходимая информация хранится в центральном банке данных,

реализованном на одной или нескольких ЭВМ. Кроме того, каждая

ЭВМ системы имеет собственный небольшой банк данных, где

хранится информация, часто используемая этой ЭВМ. Обращение к

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

порядок больше времени обращения к собственному банку.

Отсюда возникает задача об организации локальных банков

данных и использовании их при распределении задач между ЭВМ

BC.

Адаптивная процедура организации локального банка данных

очевидна: здесь следует хранить наиболее часто требуемую

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

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

эффективную дисциплину направления задач на ту ЭВМ, банк

которой содержит максимум необходимой информации. Заметим, что

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

банков данных, что, естественно, повышает эффективность всей BC.

Таким образом, подобная адаптация локальных банков дает

возможность повысить эффективность многомашинной BC.

Аппаратом решения этой задачи является эволюционная

адаптация, применение которой описано в шестой главе (§ 6.3).

2.2.5.4. Адаптивные дисциплины

распределения задач

в многомашинной вычислительной

системе

Синтез оптимальной дисциплины распределения задач на

многомашинной BC не представляет принципиальных трудностей,

если известны все параметры потока задач и пропускные возмож-

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

но и все время изменяются неопределенным образом. В таких

условиях следует построить оптимальную дисциплину и изменять ее

необходимым образом, чтобы поддерживать заданный критерий в

экстремальном состоянии.

Заметим, что решить эту задачу без применения процедуры

адаптации невозможно. Адаптация здесь имеет альтернативный

характер и заключается в построении правила перехода от одной

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

прийти к оптимальной в сложившейся ситуации дисциплине,

экстремизирующей заданный критерий эффективности функцио-

нирования BC (например, среднее время решения задачи, суммарную

длину очередей и т. д.).

2.2.5.5. Адаптация

многомашинной вычислительной

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

пользователю

Если активные пользователи BC обладают статистической

устойчивостью своих интересов по отношению к BC, то естественно

закреплять их за определенной ЭВМ. Это можно осуществить

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

альтернативной ЭВМ в BC к другой. Такой процесс адаптации должен

заканчиваться выбором ЭВМ, на которой задачи данного пользователя

решаются наилучшим в заданном смысле образом. Для достижения

поставленной цели естественно вос- пользоваться алгоритмом

альтернативной адаптации.

Таким образом, системный уровень в BC представляет широкое

поле для приложения методов адаптации.

В целом же BC является типичным примером сложного объекта,

эффективное функционирование которого просто невозможно без

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

неопределенности в самой BC и ее среде, т. е. потоке решаемых задач.

§ 2.3. Процессы обучения

Стандартная задача обучения состоит обычно в том, чтобы

обучаемый наилучшим образом запомнил определенные порции

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

единицами. Примером таких единиц являются операторы

алгоритмического языка, слова иностранного языка, грамматические

правила и т. д.

Алгоритм обучения представляет собой правило выбора порции

обучающей информации U, которую необходимо заучить. Эф-

фективность Q такого обучения — например, число известных

ученику лексических единиц — можно оценивать по результатам

периодического контроля обучаемого. Очевидно, что эффективность

зависит от алгоритма обучения U и самого ученика:

Q = Q (U, ω), (2.3.1)

где со — индивидуальные свойства ученика как объекта обучения.

Очевидно, что эти свойства априори неизвестны в явном виде

и могут быть получены лишь в результате довольно громозд-

кого процесса идентификации.

Процесс обучения естественно сделать адаптивным, т. е. при

спосабливающимся к индивидуальным особенностям со обучае

мого, которые, вообще говоря, могут изменяться в процессе обу

чения, т. е.

ω = ω(t). (2.3.2)

Это можно осуществить путем соответствующего выбора порции

t/ обучения, т. е. решая задачу адаптации

(2.3.3)

где U*

(t) — оптимальная порция обучения, зависящая от инди-

видуальных черт ω(t) ученика.

Вид зависимости (2.3.1) обычно неизвестен, но иногда можно

оценивать Q, т. е. иметь наблюдения функции (2.3.1) в определенные

моменты времени. Поэтому для решения задачи (2.3.3) можно

воспользоваться методами адаптации, т. е. такого изменения

порции U в процессе обучения, чтобы поддерживать критерий (2.3.1) в

экстремальном состоянии в течение всего процесса обучения. Если

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

алгоритма, оптимального в данный момент для данного ученика,

решается методами структурной или, точнее, альтернативной

адаптации. Здесь число альтернатив равно числу конкурирующих

алгоритмов обучения.

Однако такой подход нельзя считать эффективным. Естест-

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

ется синтез модели (2.3.2) ученика как объекта управления (обу-

чения). Синтез модели нужно проводить адаптивно, т. е. не

нарушая процесса обучения. Параметризуем модель (2.3.2):

ω = φ (С, t), (2.3.4)

где φ — выбранный оператор модели, a C=(c

,...,c

) — параметры

модели конкретного ученика, которые обычно оцениваются в

процессе обучения методами адаптации. Для решения этой задачи

необходимо воспользоваться методами параметрической

адаптации (см. § 4.2). Теперь, располагая моделью (2.3.4) и критерием

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

оптимизации (2.3.3), определить оптимальное обучение U* в виде

порции информации, которую следует выучить данному ученику

(точнее: ученику с данной моделью).

Эффективность такого подхода очевидна (подробнее он рассмот

рен в § 4.2).

Если нужно выбрать между различными альтернативными

структурами модели φ

,...,φ

, то для этого следует воспользоваться

альтернативной адаптацией. Как видно, задача эффективного

обучения связана с решением задачи адаптации алгоритма обучения и

модели пользователя с целью максимизации эффективности процесса

обучения на всех его стадиях [297].

§ 2.4. Графы

Граф является очень характерным математическим объектом

адаптации. Покажем это на примере задачи о его агрегации.

Задача об агрегации графа, которую часто называют задачей о

сегментации или разрезании графа, довольно широко распространена

в приложениях. Содержание ее состоит в следующем.

Пусть задан граф с вершинами и ребрами, имеющими различные

веса, которые, вообще говоря, могут изменяться во времени. Следует

так объединить эти вершины в сегменты, чтобы:

а) суммарный вес вершин, попавших в один сегмент, не

превышал некоторую постоянную этого сегмента («объем сег

мента»),

б) суммарный вес связей между сегментами был мини

мальным.

Легко видеть, что число возможных агрегаций графа при за

данных объемах сегментов достаточно велико. Из этого мно

жества допустимых вариантов агрегации» следует выбрать наи

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

сегментами.

Сформулируем эту задачу как задачу дискретного програм-

мирования..

Пусть веса вершин графа равны а

,...,а

веса ребер — b

(i,

j=l,...,n), а объем сегментов — c

(l=1, ..., m<n). Очевидно, что a

, b

>0.

Агрегация задается характеристической матрицей

(2.4.1)

имеющей m строк (по числу сегментов) и п

столбцов (по числу вершин графа). Элементами этой матрицы

являются двоичные числа

(2.4.2)

указывающие на принадлежность (u

=1) или непринадлежность

=0) j-й вершины i-му сегменту.

Очевидно, что при этом должно выполняться следующее условие:

(2.4.3)

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

один сегмент. В результате матрица (2.4.1) содержит лишь п единиц, а

остальные ее элементы — нули.

Теперь задачу об оптимальной агрегации графа можно записать в

виде следующей квадратичной задачи дискретного про-

граммирования:

2.4.4) где S — область

допустимых значений матрицы U:

(2.4.5)

а φ(٠,٠) —

характеристическая функция вида

(2.4.6)

Решение U* этой задачи и является искомой оптимальной

агрегацией графа.

Реализация точного решения (2.4.4) связана в той или иной

степени с перебором, что не позволяет решать задачи даже средней

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

люционной адаптации дает возможность получать вполне при-

менимые оценки точного решения U* за допустимое время.

Решение рассмотренной задачи об адаптивной агрегации графа

будет рассмотрено в § 6.2.

§ 2.5. Дисциплины обслуживания

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

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

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

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

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

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

неизбежна при желании поддерживать систему в оптимальном режиме

независимо от изменений, происходящих в среде и системе.

Пусть X — контролируемое состояние среды, E — ее неконт-

ролируемое состояние. Таким образом, пара

‹Х, E› (2.5.1)

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

обслуживания. Например, X — паспортные данные заявок на

обслуживание, a E — интенсивность их поступления. Аналогично пара

‹Y, H› (2.5.2)

описывает состояние системы: Y — ее контролируемые, а H —

неконтролируемые факторы. Например, Y — очереди в пунктах

обслуживания, а H — интенсивность обслуживания.

Критерий эффективности системы обычно имеет экстремальный и

векторный характер. Он определен на контролируемых состояниях

системы и среды:

Q = Q (Y, X). (2.5.3)

Примером таких критериев являются среднее время пребывания

заявки в системе, среднее время ожидания обслуживания, средняя

длина очереди к пунктам обслуживания и т. д. — в зависимости от

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

Состояние системы Y, в свою очередь, зависит от упомянутых X, E

и H, а также от дисциплины обслуживания U:

Y = F (X, E, H, U), (2.5.4)

где F — оператор системы.

Здесь под дисциплиной обслуживания U подразумевается ре-

шающее правило распределения заявок по системе на основе

информации о состоянии среды и системы:

U = U (X, Y). (2.5.5)

Оптимальность дисциплины U связана с экстремизацией критерия

функционирования (2.5.3). Это означает, что для синтеза оптимальной

дисциплины U* необходимо решить следующую оптимизационную

задачу:

(2.5.6)

где S — ограничения, накладываемые на выбор дисциплины об-

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

принятия решения (2.5.5), которое не должно быть больше заданной

величины, и т. п.

Хорошо видно, что решать задачу (2.5.6) на стадии проекти-

рования невозможно ввиду того, что априори неизвестны факторы

E и H. Осреднение по этим факторам вводить нельзя, так как

они имеют нестационарный характер.

Поэтому задачу синтеза оптимальной дисциплины U* следует

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

в режиме ее нормальной эксплуатации. Тогда адаптация

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

(2.5.7)

по локальным наблюдениям оценок значения

критерия Q при различных дисциплинах:

(2.5.8)

Алгоритм адаптации должен

указывать последовательность переходов от одной дисциплины к

другой

→U

→...→U

→..., (2.5.9)

которая стремится к решению U*, оптимальному в данной ситуации.

Если структура дисциплины определена априори:

U = f (X, Y, C), (2.5.10)

где f — заданный алгоритм дисциплины обслуживания; C = = (c

,...,c

)

— параметры этой дисциплины, то ее адаптация, связана с

определением параметров С, т. е. с решением задачи

(2.5.11)

где S

— множество допустимых параметров дисциплины об-

служивания f.