«РИГА ЗИНАТНЕ 1981 6S0.1 32.81 Р245 УДК 62-506 Р а с т р и г и н Л. А. Адаптация сложных систем. — Рига: Зинатне, 1981. — 375 с. Монография посвящена одному из бурно развивающихся направлений современной кибернетики — ...»

Адаптация

сложных

Л. А. РАСТРИГИН

систем

Методы

и приложения

РИГА «ЗИНАТНЕ» 1981

6S0.1 32.81

Р245 УДК

62-506

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

Рига: Зинатне, 1981. — 375 с.

Монография посвящена одному из бурно развивающихся

направлений современной кибернетики — методам

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

Рецензенты:

д-р техн. наук Я. А. Гельфандбейн, канд. техн. наук Л. П. Богомолов Печатается по решению Редакционно-издательского совета Академии наук Латвийской ССР от 28 декабря 1979 года.

30501— Р М811(11)— 81 24.81.1502000000 © Издательство «Зинатне», Оглавление Предисловие

Глава 1. ПРОБЛЕМА АДАПТАЦИИ

§ 1.1. Адаптация в процессах управления сложным объектом... 1. 1. 1. Управление и его атрибуты

1.1.2. Этапы управления сложным объектом

1.1.3. Адаптация системы управления

§ 1.2. Постановка задачи адаптации

§ 1.3. Адаптация и оптимизация

§ 1.4. Адаптация и компенсация

§ 1.5. Типы адаптации

1.5.1. Классификация типов адаптации

1.5.2. Параметризация структуры объекта

Глава 2. ОБЪЕКТЫ АДАПТАЦИИ

§ 2.1. Сложная система как объект адаптации....... § 2.2. Вычислительная система как объект адаптации..... 2.2.1. Специфика вычислительных систем

2.2.2. Уровни адаптации вычислительной системы

2.2.3. Алгоритмический уровень адаптации вычислительной системы 2.2.4. Программная адаптация вычислительной системы... 2.2.4.1. Адаптивный выбор программы сортировки массивов 2.2.4.2. Адаптация способов кодирования информации в канале передачи данных вычислительной системы

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

2.2.5.2. Адаптация расположения информационных блоков на маг нитных дисках

2.2.5.3. Адаптивное распределение памяти в многомашинной вы числительной системе (сети)

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

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

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

§ 2.4. Графы

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

Глава 3. СЛУЧАЙНЫЙ ПОИСК В ЗАДАЧАХ ОПТИМИЗАЦИИ И АДАПТАЦИИ

§ 3.1. Рандомизация управления

§ 3.2. Предпосылки случайного поиска

§ 3.3. Алгоритмы случайного поиска

3.3.1. Структура поискового метода

3.3.2. Некоторые простейшие алгоритмы случайного поиска.. 3.3.2.1. Случайный поиск с линейной тактикой

3.3.2.2. Случайный поиск с нелинейной тактикой

3.3.2.3. Случайный поиск по наилучшей пробе

3.3.3.1. Коллектив оптимизирующих автоматов с целесообразным 3.4.2. Случай S=SH

3.4.2.2. Использование самообучения в виде адаптации распреде 3.4.3. Случай S=SG

3.4.4. Случай S=SHSG

3.4.5. Случай S=SD

§ 3.6. Глобальный поиск

3.6.1.3..Набросовый алгоритм глобального поиска с идентифика § 4.1. Некоторые алгоритмы параметрической адаптации

4.2.2. Этапы обучения

4.2.2.1. Формулировка целей обучения

4.2.2.2. Выделение объекта обучения из среды

4.2.2.6. Синтез оптимального обучения

4.2.2.8. Коррекция (адаптация)

4.2.3. Система обучения с адаптивной моделью

4.2.4. Модель ученика

4.2.5. Модельный анализ процесса обучения

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

4.2.7. Обучение с использованием предложенной адаптивной модели

§ 4.3. Адаптивный синтез многопороговых логических элементов мето дом случайного поиска

4.3.1. Пороговый логический элемент

4.3.2. Многопороговый логический элемент

4.3.3. Анализ задачи синтеза оптимальных многопороговых логи 4.3.4. Индексные зоны

4.3.5. Экспериментальный синтез многопороговых логических эле ментов

4.3.6. Вероятностные характеристики поиска

§ 4.4. Адаптивный синтез оптимальных планов эксперимента для ре грессионной модели

4.4.1. Постановка задачи

4.4.2. Последовательный синтез плана

4.4.3. Диалоговый синтез плана

§ 4.6. Адаптация алгоритмов распознавания

§ 4.8. Адаптивный синтез датчика случайных чисел с заданной автокорре ляцио нно й ф у н к ц и е й

Глава 5. АЛЬТЕРНАТИВНАЯ АДАПТАЦИЯ

§ 5.1. Алгоритмы альтернативной адаптации

5.1.1. Постановка задачи

5.1.2. Алгоритмы-автоматы

5.1.2.3. Алгоритм «многорукого бандита»

5.4.1. Постановка задачи.

5.4.2. Двуальтернатнвный выбор кода

6.2:2.2. Адаптивная сегментация программного обеспечения вы 6.2.2.3. Адаптация расположения блоков информации на. магнит 6.2.3.5. Алгоритм глобальной минимизации критерия оптималь 6.2.3.6. Адаптивная агрегация графа с переменными свойствами в детерминированной среде

6.2.3.7. Стохастическая задача агрегации графа в соответствии с 6.2.3.8. Адаптивная агрегация графа, функционирующего в не 6.2.4. Некоторые обобщения задачи об агрегации графа... § 6.3. Адаптация процессов распределения памяти в вычислительной сети

6.3.2. Сведение задачи распределения памяти к задаче математи ческого программирования

6.3.3. Адаптивное распределение памяти в сети ЭВМ

6.4.1. Постановка задачи

6.4.2. Адаптация структуры перцептрона

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

6.4.4. Модельные эксперименты

6.4.5. Применение перцептрона с адаптивной структурой для ре 6.4.5.2. Классификация в задачах технологического проектирова ния

6.4.5.3. Прогнозирование активности химических соединений по их структурным формулам

§ 6.5. Адаптивный синтез оптимальных факторных планов эксперимента 6.5.1. Постановка задачи

6.5.2. Ада пта ция вероятно стных хара кте ристик поис ка.. 6.5.3. Адаптивный синтез планов эксперимента методами случай ного поиска с пересчетом и спуском

Заключение

Список литературы

ПРЕДИСЛОВИЕ

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

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

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

Именно поэтому так важно вводить в систему адаптирующие подсистемы, которые будут ее изменять, с тем чтобы поддерживать ее эффективность в оптимальном состоянии независимо от состояния среды.

Как видно, термин «адаптация» уже прочно вошел в инженерный лексикон и, следовательно, нуждается в более точном определении.

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

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

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

1. Какова цель адаптации, т. е. что называть эффективным функционированием системы?

2. Каков алгоритм адаптации, т. е. каким способом достига ется поставленная цель?

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

Это означает, что адаптация ничем не отличается от управления (в широком смысле). Действительно, адаптация, как и всякое управление, есть организация такого целенаправленного воздействия на объект, при котором достигаются заданные цели.

Отождествляя адаптацию и управление, необходимо определить тип управления, к которому относится адаптация.

Распространено мнение, что адаптацию как управление следует отнести к оптимизации в обстановке помех, в процессе которой параметры объекта изменяются так, чтобы его показатель качества стремился к экстремальному значению независимо от изменения ситуации. Аналогичное определение приводится в книге Я. 3.

Цыпкина «Адаптация и обучение в автоматизированных системах»

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

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

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

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

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

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

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

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

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

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

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

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

Применение случайного поиска для целей адаптации и оптимизации рассматриваемых систем имеет два основания. Во-первых, случайный поиск является наиболее эффективным средством адаптации сложных систем: он прост в реализации, легко модифицируется и программируется, имеет высокое быстродействие. Это объективные показатели, способствовавшие выбору случайного поиска в качестве основного инструмента. Есть и субъективные причины, связанные с предыдущими интересами автора, который последние 20 лет занимался разработкой и пропагандой алгоритмов случайного поиска. Естественно, что при решении прикладных задач был выбран именно случайный поиск.

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

С книгой в рукописи ознакомились Я. 3. Цыпкин, С. 3. Кузьмин, E.

В. Маркова и A. H. Скляревич, которые сделали ряд полезных замечаний, учтенных в окончательной редакции. Всем этим лицам автор выражает свою глубокую признательность.

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

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

§ 1.1. Адаптация в процессах управления сложным В процессах управления сложными объектами адаптация занимает почетное место. (Определение сложного объекта будет дано во второй главе, здесь же достаточно интуитивного представления о сложном объекте.) Дело в том, что без адаптации совершенно невозможно эффективно управлять сложным объектом (простым — можно), т. е. цели управления без адаптации не достигались бы. Не будь адаптации, пришлось бы ограничить управление самыми простыми объектами, типа объектов автоматического регулирования [265, 266].

Для того чтобы показать это, рассмотрим специфику управления сложным объектом. Прежде всего о термине «управление» [172].

1.1.1. Управление и его атрибуты Под управлением будем понимать процесс организации такого целенаправленного воздействия на объект, в результате которого этот объект переводится в требуемое (целевое) состояние.

Объектом управления будем называть ту часть окружающего нас мира, состояние которой нас интересует и на которую можно целенаправленно воздействовать — управлять. Состояние объекта изменяется под воздействием среды, в которой он находится. Пусть X — состояние среды, взаимодействующей с объектом, а Y — состояние объекта (рис. 1.1.1). Тогда объект можно представить как преобразователь F0 состояния среды в состояние объекта:

где F0 — пока неизвестный оператор связи входа X и выхода Y объекта, характеризующий специфику его работы. (Здесь X уже выступает как вход, а Y — как выход объекта.) Говоря об управлении как о целенаправленном процессе, нельзя обойти того, чьи цели реализуются в процессе управления. Для этого необходимо ввести понятие «субъекта», который является источником целей, реализуемых управлением. Эти цели возникают у субъекта под давлением потребностей, связанных с его жизнедеятельностью и взаимодействием со средой и объектом управления. Заметим, что под субъектом совершенно необязательно подразумевать какую-то личность; это может быть группа людей, объединенная по какому-то признаку, и даже все человечество, если рассматривается управление глобальными объектами — такими, как окружающая среда, космос и т. д.

Если состояние Y объекта удовлетворяет потребностям субъекта, взаимодействующего с этим объектом и эксплуатируРис. 1.1.1. Блок-схема объекта как преобразователя причины X в следствие Рис. 1.1.2. Блок-схема взаимодействия субъекта и объекта управления.

ющего его, то никакого управления не нужно. Если же состояние объекта почему-либо не удовлетворяет потребностей субъекта, то последний должен организовать такое воздействие на объект, которое перевело бы объект в новое состояние, удовлетворяющее субъекта. Это и есть управление.

Так как фигура субъекта важна для управления, «выделим» его из среды (рис. 1.1.2). Здесь Dx и DY — система «датчиков» (его рецепторы, сенсоры), с помощью которых он воспринимает среду и объект. Информация ‹X', Y'› образует сенсорную среду субъекта, т. е.

ту часть среды ‹Х, Y›, которую он способен воспринять своими сенсорами.

Удобно (хотя это и не соответствует действительности) считать, что субъект всегда по поводу любого объекта формулирует свою цель (цели) Z*, реализация которой в объекте приведет, по мнению субъекта, к удовлетворению его потребностей. Эта цель представляет собой набор требований, предъявляемых субъектом к состоянию У объекта. Будем обозначать выполнение целевых требований Z* в объекте равенством а невыполнение — неравенством В последнем случае (при отсутствии управления) цели субъекта не реализуются. В результате субъекту приходится решать дилемму:

1) либо смириться с существующим положением, выражен ным неравенством (1.1.3), и тем самым терпеть определенный ущерб, связанный с неудовлетворением своих потребностей;

2) либо создать систему управления, которая реализовала бы его цели Z* в объекте, т. е. добиваться выполнения равенства (1.1.2), но при этом затратить неизбежные средства и усилия на ее создание и эксплуатацию.

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

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

Во всяком случае, для реализации управления необходима создать канал управления U, с помощью которого можно влиять на состояние объекта управления:

где F0 — по-прежнему оператор работы объекта, но учитывающий наличие фактора управления U. Теперь можно создавать систему управления, под которой будем понимать совокупность алгоритмов обработки информации и средств их реализации, объединенных для достижения заданных целей управления в объекте. (Заметим, что система управления далеко не всегда воплощается «в металле». Она может представлять собой систему правил, договоров и обязательств, которые реализуются в процессе управления.) Блок-схема системы управления показана на рис. 1.1.3. Здесь DX и DY — датчики, измеряющие состояние среды и объекта соответственно. Результаты измерений X' = DX (X);

Y' = DY (Y) поступают на управляющее устройство (УУ), которое вырабатывает команды управления U. Эти команды должны быть обработаны исполнительными механизмами (ИМ), с тем чтобы изменить состояние управляемого входа U' объекта.

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

Рис. 1.1.3. Блок-схема системы управления объектом.

Рис. 1.1.4. Последовательность этапов управления сложным объектом.

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

Такой алгоритмический анализ управления является основой для принятия решения о создании системы управления, форме ее реализации и степени автоматизации.

1.1.2. Этапы управления сложным объектом Управление сложным объектом можно подразделить на следующие этапы (рис. 1.1.4).

I. Формулировка целей управления. На этом этапе определяются цели (множество целей), которые должны быть реализованы в процессе управления. Слово «цель» - здесь используется в смысле модели потребного будущего субъекта, т. е. некоторого определенного состояния среды, которое желательно потребителю и которое в определенном смысле «неестественно», т. е. нереализуется естественным образом без вмешательства извне (без управления).

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

Таким образом, субъект воспринимает окружающую среду ;как конечный или бесконечный набор ее параметров каждый из которых интересует субъекта и может быть им изменен.

Иначе говоря, воспринимаемая субъектом ситуация всегда управляема:

где U — управление субъекта.

Введем понятие пространства ситуаций {S}, которое образуется указанными параметрами si (i=1,...,e). Каждая точка этого пространства определяет какую-то конкретную ситуацию, сложившуюся вокруг субъекта (рис. 1.1.5). Через это ситуационное пространство {S} субъект и воспринимает окружающие его оперировать иными, свойстPuc. 1.1.5. Пространство ситуаций. венными ему понятиями (назовем их целевыми). Пусть эти целевые понятия описываются вектором где каждый целевой параметр zi однозначно определяется ситуацией S, т. е.

а функции i (•) определяют связь состояния среды I и целевого параметра zi. В векторной форме эта связь выражается в виде Z=(S), (1.1.11) где — некоторая определенная вектор-функция.

Преобразование информации в форму Z необходимо еще и потому, что субъект обычно формулирует свои цели в терминах к понятиях, связанных с измеряемыми, но не тождественных им. В частном случае может оказаться, что Z = Y (k = m), но это бывает редко. Например, при управлении температурным режимом объекта достаточно измерять температуру, т. е. z = y = t0, так как цель сформулирована в терминах измерений. Однако при создании оператору комфортных условий необходимо измерять температуру и влажность, в то время как цель формулируется в виде определенного ограничения на определенную их комбинацию.

Рассмотрим k-мерное пространство целей {Z}, которое образуется точками (1.1.9). Это пространство удобно субъекту тем, что по поводу каждой координаты он может высказать свое требование (цель), выполнение которого, по мнению субъекта, приведет к удовлетворению какой-то одной или нескольких его потребностей.

Свою цель субъект формулирует в виде вектор-цели где z*i — i-e требование к состоянию среды S, выраженное с помощью функции i(S). Эти цели-требования могут иметь различный характер, но форма их должна быть унифицирована.

Рассмотрим унифицированный вид целей Z*. Они могут выражаться различным образом. Однако для формализации их необходимо свести к одной из следующих форм:

1) z*i («приравнять»): zi=ai это требование означает, что i-я целевая переменная zi=i(S) должна быть равна заданной величине ai;

2) z*j («ограничить»): zjbj это требование, накладыва емое на j-ю целевую переменную, — она не должна быть меньше заданного порога bj;

3) z*v («минимизировать») : zvmin, т. е. v-я целевая пере менная должна быть минимальной.

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

Однако практика показывает, что к такого рода требованиям («приравнять», «ограничить», «минимизировать») можно свести почти все ситуации, которые встречаются субъекту, особенно в научно-технической сфере.

Таким образом, процесс формулировки целей Z* субъекта связан, во-первых, с определением вектор-функции (S) (1.1.12) и, вовторых, с выработкой требований, накладываемых на каждую составляющую этого вектора.

Рассмотрим, как отражается цель Z* в пространство ситуаций {S}.

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

Точка или область S*, удовлетворяющая этим требованиям, и является тем состоянием среды, которого добивается субъект.

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

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

Теперь рассмотрим взаимодействие целевой зоны S* и траектории изменения среды S(t) под воздействием внешних факторов (см. рис.

1.1.5), т. е. дрейф ситуации. Если траектория дрейфа S(t) проходит через зону, никакого управления субъекту не нужно. Ему остается ждать, когда внешние обстоятельства приведут к тому, что S(t) принадлежит S*. Однако рассчитывать на подобное маловероятное совпадение неразумно, хотя в принципе оно возможно. Именно поэтому субъект предпочитает управлять ситуацией, т. е. целенаправленно воздействует на среду:

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

Таким образом, управление U необходимо субъекту для того, чтобы:

1) добиться поставленной цели управления Z*, т. е. реали зовать условие (1.1.18);

2) компенсировать дрейф ситуации, который, как правило, нарушает целевое условие (1.1.18).

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

Заметим, что под параметрами среды S здесь и в дальнейшем подразумеваются измеряемые параметры собственно среды X и параметры объекта Y, взаимодействующего со средой. Таким образом, Однако дифференциация 5 возникает лишь после выделения объекта из среды. Процедура такого выделения представляет собой следующий этап управления сложным объектом.

II. Определение объекта управления связано с выделением той части среды, состояние которой интересует потребителя в связи с реализацией сформулированных им целей.

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

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

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

Если бы мы располагали формальным описанием среды, то процесс выделения объекта из этой среды в принципе не представлял бы трудностей. Действительно, «высекая» различные «куски» среды и называя их объектом, мы всегда могли бы проверить на модели, достигаются ли цели управления в данном объекте или нет. Если нет, то можно было бы оценить численно, какова степень неуправляемости этого варианта объекта. Повторив эту процедуру для других вариантов высечения, мы остановились бы на том, который позволяет получить максимальную (желательно 100%ную) управляемость.

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

На стадии определения объекта это единственно возможный подход.

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

III. Структурный синтез модели [178]. Под структурой будем понимать вид, характер зависимости F состояния объекта Y от его входов — неуправляемого X и управляемого U:

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

Условно можно считать, что модель F состоит из структуры и параметров:

где St - структура модели F, C = (с1,..., сk) — ее параметры. Таким образом, целью третьего этапа является определение структуры St объекта управления. Например, категории линейности, статичности, детерминированности, дискретности являются структурными категориями. Так, линейная статичная непрерывная детерминированная структура однозначно определяет следующий вид для F: у = с1x1+...+спхп, причем на стадии структурного, синтеза конкретные значения параметров c i,..., с п пока неважны. Важен лишь вид зависимости F от этих параметров и входов объекта.

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

1. Определение входов и выходов объекта, т. е. синтез мо дели на уровне «черного ящика».

2. Экспертное ранжирование входов и выходов объекта.

3. Декомпозиция модели.

4. Выбор структурных элементов модели.

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

IV. Параметрический синтез модели связан с определением параметров C = (с1,..., ck) модели где выбранная на предыдущем этапе структура St отражена в модельном операторе F.

Для определения параметров С модели, очевидно, необходимо иметь информацию о поведении входов X, U и выхода У объекта. В зависимости от того, как получена эта информация, различают два подхода — идентификацию и планирование экспериментов с объектом.

IV.1. Идентификация [178] параметров модели F объекта связана с оценкой численных значений искомых параметров в режиме нормального функционирования объекта, т. е. без организации специальных управляющих воздействий на него. Исходной информацией для идентификации являются структура St и наблюдения за поведением входа X(t) и выхода Y(t) объекта при его взаимодействии со средой.

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

Однако не все входы объекта (X и U) изменяются в процессе его нормальной эксплуатации. Так, наверняка не изменяются те параметры из U, на которые не влияет состояние среды. Для выяснения зависимости выхода объекта У от параметров такого рода необходимо преднамеренно их варьировать, т. е. необходим эксперимент с объектом. Однако всякого рода эксперименты нарушают режим нормального функционирования объекта, что всегда нежелательно. Поэтому эксперимент, которого нельзя избежать, следует проводить, минимально возмущая объект, но так, чтобы получить максимальную информацию о влиянии варьируемых параметров на выход объекта. Здесь приходят на помощь методы планирования эксперимента.

IV.2. В процессе планирования эксперимента синтезируется специальный план эксперимента, позволяющего в заданных ограничениях с максимальной эффективностью определить параметры С модели объекта управления. Например, для статического объекта этот план представляет собой набор состояний управляемого входа объекта U1,..., UN, принадлежащих заданной допустимой области варьирования, в которых определяется его выход Y1,...,YN, т. е. Yi = F (Ui) (i=1,...,N). Полученные N пар ‹Ui, Yi› (i=1,...,N) являются исходной информацией для определения необходимых параметров модели.

Поскольку в процессе проведения экспериментов на объекте получается новая информация, то могут измениться представления о структуре модели (например, первоначальная гипотеза о линейности модели сменится на нелинейную). Это обстоятельство заставляет снова обращаться к структурному синтезу, точнее, вводить коррекцию структуры модели. Сказанное несколько «размывает» понятие этапа планирования эксперимента, распространяя его и на процессы выбора и коррекции структуры.

После того как выяснено влияние на выход объекта Y неуправляемого X и управляемого U входов, задачу синтеза модели, которой были посвящены два последних этапа (третий и четвертый), можно считать выполненной. Полученная модель является исходной для процесса синтеза управления.

V. Синтез управления связан с принятием решения о том, каково должно быть управление U, чтобы в сложившейся си туации S достигнуть заданной цели управления Z* в объекте.

Это решение опирается на имеющуюся модель объекта F, за данную цель Z*, полученную информацию о состоянии среды X и объекта Y, а также на выделенные ресурсы R управления, ко торые представляют собой ограничения, накладываемые на уп равление U в связи со спецификой объекта и возможностями си стемы управления. Синтез управления сводится к решению ва риационной задачи, которая получается из (1.1.14) путем соот ветствующих преобразований и свертки, необходимых для преодоления многокритериальности.

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

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

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

Если управление реализовано, а его цель не достигнута (напомним, что рассматривается управление сложным объектом), приходится возвращаться к одному из предыдущих этапов. Даже в самом лучшем случае, когда поставленная цель достигнута, необходимость обращения к предыдущему этапу вызывается изменением состояния среды X или сменой цели управления Z*. Таким образом, при самом благоприятном стечении обстоятельств следует обращаться к этапу синтеза управления (стрелка 1 на рис. 1.1.4), на котором определяется новое управление, отражающее новую, сложившуюся в среде ситуацию. Так функционирует стандартный контур управления, которым пользуются при управлении простыми объектами.

VII. Специфика сложного объекта управления требует расширения описанного цикла за счет введения этапа адаптации, т.

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

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

1. Параметрическая адаптация связана с коррекцией, подстройкой параметров С модели. Необходимость в такого рода адаптации возникает ввиду дрейфа характеристик управляемого объекта. Адаптация позволяет подстраивать модель на каждом шаге управления, причем исходной информацией для нее является рассогласование откликов объекта и модели, устранение которого и реализует процесс адаптации (стрелка 2 на рис. 1.1.4).

Такого рода адаптивное управление часто называют управлением с адаптивной (или адаптирующейся) моделью объекта.

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

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

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

е. двойственным. Здесь путем специальной организации управления сразу достигаются две цели — управления и адаптации модели.

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

2. Структурная адаптация. Далеко не всегда адаптация модели путем коррекции ее параметров позволяет получить адекватную модель объекта. Неадекватность возникает при несовпадении структур модели и объекта. Если в процессе эволюции объекта его структура изменяется, то такая ситуация складывается постоянно.

Указанное обстоятельство заставляет обращаться к адаптации структуры модели, что реализуется методами структурной адаптации. Например, здесь можно воспользоваться процедурой перехода от одной альтернативной модели к другой. При этом альтернативы могут различаться числом и характером входоввыходов модели, вариантами декомпозиции и структурой элементов модели.

Альтернативные модели нуждаются в идентификации параметров, что осуществляется отмеченными выше методами параметрической адаптации.

Методически структурная адаптация модели использует алгоритмы структурного синтеза. Поэтому ее реализация в алгоритме осуществляется путем, показанным на рис. 1.1.4 стрелкой 3.

3. Адаптация объекта. Если и структурная адаптация модели не позволяет повысить эффективность функционирования (на пример, какие-то цели управления не реализуются в объекте), то следует адаптировать объект управления (стрелка 4 на рис.

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

4. Адаптация целей управления. Наконец, если и эта мера неэффективна, следует обратиться к адаптации целей управления (стрелка 5 на рис. 1.1.4). В этом случае определяется новое мно жество целей {Z*}', достижение которых обеспечивается создан ной системой управления. Ввиду того что объект эволюционирует (вместе со средой), изменяется и множество достигаемых им целей. Важно знать, какие именно цели могут быть поставлены перед системой управления. Такую информацию можно получить путем адаптации целей. В результате этого процесса фактически адаптируется субъект, который изменяет свои потребности так, чтобы они удовлетворялись путем реализации нового множества целей, достигаемых системой управления в данный период вре мени. Поэтому адаптацию целей следует считать адаптацией потребностей субъекта, пользующегося услугами созданной си стемы управления и поставленного перед необходимостью такой адаптации.

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

Каждый последующий уровень адаптации имеет постоянную времени на несколько порядков выше, чем предыдущий, т. е.

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

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

§ 1.2. Постановка задачи адаптации Рассмотрим задачу адаптации объекта F0 (рис. 1.2.1) как задачу управления. Объект погружен в среду, состояние которой X влияет на его состояние Y, Кроме того, состояние Y объекта может изменяться с помощью его адаптируемых факторов U:

Цель Z* адаптации определяет требования к критериям, заданным на состоянии Y объекта. Эти требования могут иметь троякую структуру аналогично (1.1.14).

1. Критерии-неравенства:

2. Критерии-равенства:

3. Минимизируемые критерии:

где p (X) — плотность распределения состояний X среды.

Очевидно, что критерии адаптации представляют собой функционалы, определенные на состояниях У объекта как средние значения функций h'i(), g'j() и q'k(), которые должны быть заданы.

Цель адаптации заключается в решении задачи F0 и распределении р(Х) называют задачами стохастического программирования [248], которые отличаются тем, что минимизируемые функционалы и функционалы ограничений являются стохастическими, т. е. математическими ожиданиями. Трудность решения этих задач очевидна.

Однако задачи адаптации осложняются еще и тем, что нет модели объекта F и отсутствует информация о распределении р(X) состояний среды X. Более того, эти факторы изменяются во времени непредсказуемым образом.

Следовательно, даже располагая алгоритмом решения задачи (1.2.9.) с ограничениями (1.1.10) в виде нельзя считать задачу адаптации решенной. Необходимо еще идентифицировать изменяющийся объект F0 и статистические свойства среды, чтобы получить где Ft — модель объекта, a pt (X) — плотность распределения X. Эти обстоятельства заставляют отказаться от попыток искать алгоритм решения поставленной задачи адаптации, так как для сложного объекта адаптации зависимости Ft и pt(X) весьма сложны, что исключает даже определение функционалов.

(1.2.2) — (1.2.4), образующих решаемую задачу (1.2.9).

Именно поэтому для решения задачи (1.2.9) приходится обращаться к алгоритмам адаптации, использующим лишь значения функций h'i(), g'j() и q'k() (i=1,...,s; j=1,...,s; k= =1,...,l) в определенные моменты времени, т. е. в общем случае адаптации;

алгоритма адаптации.

Синтез конкретных алгоритмов адаптации для решения различных задач будет рассмотрен в главах 4—6; Здесь же введем некоторые упрощения общей постановки задачи адаптации (1.2.9).

Прежде всего будем предполагать, что задача однокритери-.альна, т. е. имеется свертка критериев (1.2.4), что позволяет считать l = 1, a Q'() — скалярной функцией.

Далее, будем рассматривать лишь дискретные моменты времени N = 0,1,..., когда измеряются критерии и изменяются адаптируемые параметры объекта.

И наконец, будем предполагать, что состояния X среды образуют во времени случайный процесс типа белого шума. Это приводит к тому, что функционалы (1.2.5) — (1.2.7) связаны со значениями функций (1.2.15) следующими довольно очевидными соотношениями:

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

Теперь рассмотрим наиболее интересные частные случаи задачи адаптации (1.2.9).

Это эквивалентно решению задачи оптимизации в обстановке помех при случайно блуждающей точке экстремума по наблюдениям Q'(U) = Q(U) +, где — случайная помеха вида (1.2.16).

2. l = s = 0, т. е. задача решения системы неравенств в обста новке помех:

Эта задача сводится к предыдущей (1.2.17) следующим простым где ai — значимость i-ro ограничения.

3. р = 1 = 0, s = q, т. е. задача решения системы уравнений в обстановке помех. Эта задача сводится к (1.2.17) следующим образом:

где f(•) — неотрицательная четная унимодальная функция, например (•)2; bj — вес j-го ограничения.

Аналогичным образом можно свести к (1.2.17) и другие задачи, которые получаются из (1.2.9). Так, сама задача (1.2.9) сводится к (1.2.17) следующим образом:

т. е. путем введения соответствующих штрафов.

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

§ 1.3. Адаптация и оптимизация Как показано выше, задача адаптации возникает в том случае, если отсутствует информация, необходимая для оптимизации объекта. Однако задачи адаптации и оптимизации тесно взаимосвязаны. Покажем это.

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

где q (X, Y) — мгновенная оценка эффективности объекта при данных состояниях X среды и Y объекта. Располагая моделью F объекта F0, связывающей его выход Y с состоянием X среды и оптимизируемыми факторами U объекта F0 и подставляя Y = = F (X, U) в (1.3.1), получаем — выражение для оптимизируемого функционала. На стадии оптимального проектирования, располагая моделью F объекта и моделью статистических свойств р(Х) среды, можно решить задачу оптимизации (1.2.9). Однако в реальных условиях при функционировании сложных объектов обычно отсутствует информация о моделях среды и объекта и необходимо решать задачу (1.2.9) путем соответствующей подстройки параметров U объекта, располагая лишь наблюдениями X и Y.

Пусть для простоты объект и наблюдение непрерывны. Оценим в этом случае функционал (1.3.2) на интервале времени [0; T] в процессе функционирования объекта:

При T и неизменных свойствах объекта и среды получаем и для решения задачи адаптации можем воспользоваться методами оптимизации. Однако временные затраты будут неприемлемы. Эти затраты уменьшаются при уменьшении базы наблюдений Г, но одновременно снижается и эффективность каждого шага, так как оценка (1.3.3) становится очень грубой. При T = 0 получаем адаптацию.

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

На рис. 1.3.1 показаны обе схемы, причем пунктиром обозначена схема оптимизации. Как видно, схемы адаптации и оптимизации отличаются незначительно — базой оценки минимизируемого функционала объекта Q(U).

Таким образом, и на стадии оптимального проектирования, и при адаптации решается одна и та же задача (1.2.9), но с разной исходной информацией. При оптимальном проектировании следует вычислить Q(U), а в процессах адаптации можно ограничиться оценкой. Это обстоятельство позволяет довольно просто строить модели адаптации, которые по сути дела являются моделями оптимизации в обстановке помех.

Рассмотрим наиболее характерные модели, используемые ниже.

Пусть Q(U, U*) — скалярная функция векторного аргумента U = (u1,...,uq), экстремум которой расположен в точке U*. Тогда моделью функции, минимизируемой при адаптации, является следующая зависимость:

где U*(t) — случайный дрейф экстремума U* в пространстве адаптируемых параметров {U}; a(t) — случайный дрейф градиента минимизируемой функции; (t) — случайная функция, моделирующая помеху с нулевым средним и дисперсией t, зависящей, вообще говоря, от времени. Блок-схема модели (1.3.4) показана на рис.

1.3.2.

Таким образом, модель объекта адаптации задается четверкой Рассмотрим некоторые простейшие модели.

1. Стационарная модель:

где f — унимодальная функция с минимумом в нуле, например f() = ()2, где U* и неизменны во времени. Это модель со стационарной помехой и без дрейфа экстремума. По мере приближения к экстремуму U* при f() = ()2 отношение сигнал/шум уменьшается и при U = U* равно нулю.

Это означает, что трудности продвижения к оптимуму U* возрастают по мере приближения к нему.

2. Нестационарная модель без помех (дрейф экстремума):

где U*(t) — модель дрейфа, которая может быть линейной и диффузионной. Линейный дрейф описывается естественным соотношением где U*0 — исходное положение экстремума, А — вектор скорости (направления и интенсивности) дрейфа (A принадл. {U}). Диффузионная модель дрейфа представляется рекуррентным выражением которое описывает случайный процесс с независимыми случайными приращениями а, где — единичный случайный вектор, равномерно распределенный в пространстве {U}, а — интенсивность дрейфа.

3. Нестационарная модель (случайный дрейф градиента):

где а(t)>0 — случайная функция, моделирующая дрейф градиента минимизируемого критерия, которая задается своей автокорреляционной функцией.

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

Следует заметить, что здесь управление U варьируется в пределах заданного множества возможностей S, которое определяется типом дискретным, конечным, что и определяет тип адаптации (см. § 1.5).

§ 1.4. Адаптация и компенсация Задача управления сложным объектом, рассмотренная в первом параграфе этой главы, редко решается во всей полноте своей сложности. Чаще рассматриваются два ее варианта, которые удобно назвать компенсацией и адаптацией. При этом блок-схема системы управления как бы «разрезается» вертикально на две половины. Левая представляет собой блок-схему компенсации (рис. 1.4.1, а), а правая — адаптации (рис. 1.4.1, б).

Формальное отличие этих схем заключается в различных источниках информации для управляющего устройства. В случае компенсации исходной информацией для синтеза управления U является только состояние X среды. Для адаптации же управление U синтезируется на основе информации лишь о состоянии Y объекта. Это отличие определяет ряд существенных черт и особенностей процессов компенсации и адаптации, которые целесообразно рассмотреть специально.

Компенсация как управление связана с достижением целей {Z*} при известном состоянии среды. Совершенно очевидно, что Рис. 1.4.1. Схемы компенсации (а) и адаптации (б).

при отсутствий обратной связи компенсация возможна, если известна модель F объекта, связывающая входы X и U с выходом Y:

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

экстремальных критериев, Полученная задача (1.4.4) с заданными функциями Q, G и H является задачей математического программирования. Ее решение U*X зависит естественным образом от состояния X среды, которое контролируется при компенсации.

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

1) знать состояние X среды, 2) иметь модель F (X, U) объекта, 3) уметь решать задачу математического программирования Понятие «компенсации» здесь используется потому, что такой тип управления как бы компенсирует влияние среды и позволяет добиваться поставленной цели Z* независимо от состояния среды и без наблюдения за состоянием Y объекта.

Такое управление иногда называют программным. В этом случае программой является цель Z*, которая реализуется в процессе компенсации с учетом состояния X среды.

Теперь с этих позиций рассмотрим адаптацию (см. рис. 1.4.1, б). Здесь задача синтеза управления (1.1.14) записывается в виде (1.4.2), а после преобразования — в форме (1.4.4). Но она не является задачей математического программирования, так как ни состояние X среды, ни модель F объекта неизвестны. Доступны для наблюдения лишь оценки значений функционалов Q, G и H (1.2.15), на которые, вообще говоря, накладываются случайные помехи вида (1.2.16).

Располагая этой скудной информацией, необходимо решить задачу (1.4.4).

Такова ситуация, складывающаяся в процессе решения задачи адаптации. Эта ситуация может усложниться тем, что цель — а с нею и структура функционалов Q, G и H — иногда изменяется в соответствии с изменением потребностей субъекта.

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

Адаптация как специальный процесс управления обладает рядом специфических черт. Прежде всего это стабильный характер целей адаптации. Это означает, что экстремизируемый критерий Q и ограничения S либо не изменяются, либо изменяются, но крайне медленно или редко.

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

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

§ 1.5. Типы адаптации Как уже говорилось, адаптация является частным случаем управления и заключается в изменении управляемого фактора U таким образом, чтобы поддерживать некие заданные функционалы объекта в требуемом состоянии независимо от действия всякого рода внешних и внутренних воздействий. При этом специфика объекта накладывает на управление требование где S — множество допустимых управлений. Структура этого множества определяется двумя факторами — целевыми ограничениями Z* и самим объектом. В данном случае нас будет интересовать специфика объекта, так как именно она через структуру множества определяет тип адаптации. Исходя из этого можно классифицировать различные типы адаптации [170].

1.5.1. Классификация типов адаптации Если объект таков, что его изменение в процессе адаптации удобно осуществлять с помощью параметров u1,..., un, т. е.

то такую адаптацию естественно назвать параметрической. Тогда каждый параметр u i может принимать бесконечное или конечное число значений. В первом случае т. е. множество S является континуумом, во втором где D — дискретное множество значений управления U.

Однако очень часто адаптацию объекта удобно осуществлять не путем изменения его параметров, а модификацией его структуры, т. е. вводя структурную адаптацию. Для этого представим фактор управления U в виде пары где W — структурные факторы, с помощью которых можно изменять структуру объекта адаптации, a C = (с1,..., ck) — адаптируемые параметры объекта (это параметры (1.5.2), с помощью которых реализуется параметрическая адаптация).

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

Такая декомпозиция управления U на структурные W и параметрические С факторы позволяет более эффективно решать задачи адаптации сложных объектов, для которых параметрическая адаптация малоэффективна.

Теперь задачу адаптации (1.2.9) следует записать в виде допустимых структур W; ECW — множество допустимых параметров С, соответствующих структуре, определяемой W; W* — оптимальная структура; C*W* — оптимальные параметры этой структуры. (Так как W однозначно определяет структуру объекта, то можно W условно называть структурой.) Очевидно, что т. е. множество S допустимых управлений при адаптации (1.2.10) образуется как произведение множеств допустимых структур EW и параметров ECW этих структур.

задачи (1.5.6) показана на рис.

1.5.1, из которого хорошо виден иерархический характер адаптации. На верхнем уровне производится адаптация структуры W, а на нижнем — параметров С этой структуры. Очевидно, что эти Два контура адаптации Работают в разных вре- Рис. 1.5.1. Двухконтурная схема структур:

менных режимах: темп па- ной адаптации.

Рис. 1.5.2. Классификация типов адаптации.

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

Очевидно, что методы решения задач структурной и параметрической адаптации различны, что и заставляет обращаться к такой дифференциации. Ее можно продолжить. На рис. 1.5. показана схема классификации различных типов адаптации.

Прежде всего структурную адаптацию удобно подразделить на альтернативную и эволюционную [113].

Альтернативная адаптация отличается тем, что множество допустимых структур EW невелико и содержит две — пять альтернативных структур.

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

где µ = const, а под нормой вариации структуры ||W|| следует понимать число, характеризующее степень изменения структуры этой вариацией W. Например, при графическом описании структуры W нормой такой вариации может быть число новых введенных или «выброшенных» вершин или ребер графа, описывающего структуру адаптируемого объекта.

«Мутации» структуры W u правило отбора, позволяющее выявлять ее благоприятные вариации, и образуют механизм эволюции, с помощью которого строится последовательность улучшающихся структур обладающих свойством очевидный смысл:

Заметим, что иногда допустимы нарушения соотношения (1.5.11) — например, в случае, когда вариацией структуры Wi не удается получить лучшую, чем Wi, по критерию (1.5.11). Тогда выбирают лучшую из «мутированных» структур, что нарушает (1.5.11), но обеспечивает процедуре эволюции глобальные свойства, очень ценные в задачах структурной адаптации.

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

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

следующей оптимизационной задаче с двоичными переменными:

где вектором компоненты которого определяют наличие (1) или отсутствие (0) соответствующего ребра графа:

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

где графе U.

Как видно, полученные задачи являются параметрическими с дискретным множеством допустимых параметров (1.5.4). Подходи к решению задач такого рода рассмотрены в § 3.4.

Эти задачи можно свести к непрерывным путем введения штрафной функции:

штрафа, а множество S' уже непрерывно и получается из (1.5.19) путем исключения требования двоичности (1.5.17) вектора U.

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

Критерий Q(U) в этом случае заменяется на его среднее значение при заданном P:

вектора U и введены обозначения Функционал (1.5.24) называют рандомизированным или сглаженным [96] функционалом Q(U). Действительно, если Q(U) определен лишь в вершинах q-мерного гиперкуба, то Q(P) — во всем этом гиперкубе, причем в вершинах оба функционала совпадают.

Следовательно, естественно считать сглаживанием Q(U) путем введения рандомизации, характеризующейся непрерывным вектором P.

Решение непрерывной задачи оптимизации как легко заметить, состоит из нулей и единиц и совпадает с искомым U*, т. е.

Процесс поиска P* производится с помощью оценок значений минимизируемого функционала (1.5.24) методом Монте-Карло (см. § 3.2):

вектора (1.5.2), имеющего вероятностные свойства P.

Такой подход позволяет эффективно решать многие задачи с двоичными переменными [52, 74, 96, 98, 99, 240]. Однако получаемые при этом задачи имеют, как правило, многоэкстремальный характер, что, безусловно, значительно затрудняет их решение. Это обстоятельство и заставляет обращаться к изысканию новых путей решения задач структурной адаптации, минуя этап параметризации.

Такие новые подходы рассмотрены в главах 5 и 6 настоящей книги.

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

Здесь нужно искать новые пути постановки задач и их решения.

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

Залогом эффективного управления является хорошая модель объекта.

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

Одним из наиболее важных и интересных для нас объектов является вычислительная система (ВС) с многочисленными задачами адаптации на разных уровнях ее организации. В качестве других примеров рассмотрены процессы обучения, сегментация графа и выбор дисциплины обслуживания в системах массового обслуживания.

§ 2.1. Сложная система Понятия «сложная система» и «сложный объект управления» до настоящего времени не имеют строгого определения. Возможно, что такое определение никогда и не появится, поскольку в нем, по сути дела, нет острой необходимости. Интуитивное представление о сложной системе довольно точно соответствует тому, которое используется в теории управления. Это представление носит неформальный характер. Однако некоторые черты (но не формальные признаки) сложной системы можно привести.

Рассмотрим основные из них.

1. Отсутствие необходимого математического описания явля ется обязательной чертой сложного объекта управления. Под математическим описанием подразумевается наличие алгоритма F вычисления состояния объекта Y по наблюдениям его вхо дов — управляемого U и неуправляемого X, т. е. Y = F (X, U).

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

Любой сложный объект имеет много такого рода «неожиданностей», которые являются свидетельством его сложности. Таковы биологические, социальные, технологические системы и многие другие.

3. «Нетерпимость» к управлению является, пожалуй, самой досадной чертой сложной системы. Дело в том, что она сущест вует, грубо говоря, вовсе не для того, чтобы ею управляли. Она «не любит» управления по причине «независимости» своего су ществования от целей субъекта, желающего управлять ею.

Трудно рассчитывать на то, что «собственные» цели сложной системы совпадут с целями управления. Скорее они будут про тиворечить друг другу. Это и вызывает «негативную» реакцию сложной системы на управление, цель которого с ней «не согла сована».

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

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

5. Невоспроизводимость экспериментов со сложной системой также является ее важной чертой. Она связана прежде всего с зашумленностью и нестационарностью сложной системы. Прояв ляется эта черта в различной реакции системы на одну и ту же ситуацию или управление в различные моменты времени. Слож ная система как бы все время перестает быть сама собой. Эта черта накладывает специальные требования на процессы син теза и коррекции модели системы. Перечень особенностей слож ной системы можно было бы продолжить. Однако в любом случае следует помнить, что мы называем лишь черты, свойственные сложной системе, но ни в коей мере не формальные признаки.

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

объект управления вообще и адаптации в частности.

Теперь рассмотрим несколько конкретных примеров сложных объектов, процедуры адаптации которых описаны в последующих главах.

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

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

Однако состояние дестабилизирующих факторов, как правило, неизвестно, что практически исключает применение методов оптимального управления для объектов типа BC и неизбежно, приводит к адаптации [292].

2.2.1. Специфика вычислительных систем Рассмотрим специфические черты BC как объекта адаптации.

Можно выделить четыре такие черты.

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

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

Таким образом, зависимость BC oт средовых воздействий решаемых задач значительно больше, чем обычных, традиционных адаптируемых систем, и поэтому она больше других нуждается в адаптации.

2. Значительная априорная неопределенность среды BC. Ин формация о специфике потока задач, как правило, очень трудно предвидится и выявляется не заранее, а во время «обслужива ния» — особенно в BC коллективного пользования, потребителями которой являются научные работники.

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

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

3. Нестационарность среды BC является существенным фак тором, который требует введения адаптации. Эта нестационар ность вызывается по крайней мере тремя обстоятельствами:

1) изменением вероятностных свойств потока решаемых за дач, неизбежным в связи с эволюцией потребностей среды (изме нение старых и появление новых задач и т. д.);

2) эволюцией самой BC в связи с ее ростом и модернизацией;

3) амортизацией BC и нестационарностью потока неисправ ностей в BC как сложной системе.

Эти обстоятельства приводят к тому, что поведение среды BC — внешней и внутренней — имеет ярко выраженный нестационарный характер, что делает адаптацию совершенно необходимой мерой по поддержанию BC в оптимальном соответствии со средой.

4. Наконец, существенная черта BC как объекта адаптации — необходимость вариации ее структуры. Это, разумеется, не ис ключает адаптации параметров BC, например, при вариации ее дисциплин обслуживания. Однако структурные вариации при адаптации BC обладают значительно большим эффектом, чем параметрические. Дело здесь в том, что в BC «гораздо больше структуры, чем параметров», в силу чего структурная адаптация почти всегда более эффективна, чем параметрическая. Это и обусловливает развитие структурной адаптации как нового эффективного способа адаптации BC.

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

2.2.2. Уровни адаптации вычислительной системы BC как объекты управления вообще и адаптации в частности рассматривались мало. Причинами этого, по-видимому, являются новизна, большая сложность такого рода систем и — как следствие — отсутствие хороших моделей. Управление здесь в настоящее время сводится к выявлению критических ситуаций к выработке правил принятия оптимальных решений в этих ситуациях.

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

В настоящее время назрела необходимость в организации более тонких подходов к управлению многомашинной BC. Таким подходом и является адаптация.

Как всякое управление, адаптацию следует рассматривать с позиций функционирования объекта адаптации. Рассмотрим задачи адаптации BC с этой точки зрения.

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

1. Аппаратурный уровень, предполагающий адаптацию уста вок, параметров и структуры аппаратурных средств BC (напри мер, параметров фильтров в каналах связи машин и т. д.).

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

3. Программный уровень адаптации должен осуществлять процесс адаптации при выборе программ работы BC из альтер нативного множества (например, при выборе программы сорти ровки для обработки данного массива или программы опти мизации).

4. Системный уровень адаптации призван улучшать функцио нирование системного обеспечения BC (например, адаптация дисциплин обслуживания, распределения памяти и т. д.).

5. Сетевой уровень адаптации связан с адаптацией процессов передачи информации по BC (например, при определении марш рута сообщения).

Конечно, указанные уровни не исчерпывают всех «этажей»

адаптации, которые встречаются или целесообразны в BC. Возможна иерархия и по другим признакам, например по этапам управления BC как сложным объектам (см. §1.1).

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

О сетевом уровне адаптации см. также работы [202; 203, с. 221— 225; 299; 300].

Рассмотрим несколько конкретных задач адаптации, возникающих на различных уровнях BC.

2.2.3. Алгоритмический уровень адаптации вычислительной системы Здесь речь идет об адаптации алгоритмов обработки информации в BC. Цель такой адаптации — приспособить алгоритмы к специфике решаемых задач.

Критериями эффективности обычно являются среднее время решения задачи, точность этого решения, объем занимаемой памяти в BC, вероятность ошибки и т. д.

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

Построим модель этого явления. Пусть — решаемые ВС задачи, отличающиеся структурой (i) и параметрами (i). Рассмотрим задачи одной структуры :

— значение критерия эффективности решения задачи Pi алго ритмом, имеющим параметры C = (с1,..., сk).

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

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

Адаптация параметров алгоритма решения задачи возможна не только от задачи к задаче, но и в процессе решения одной задачи, что применимо для рекуррентных методов, когда возможна оценка эффективности одного цикла — например, в процессах поисковой оптимизации. Покажем это.

Алгоритм оптимизации, т. е. алгоритм решения задачи представляет собой оператор F перехода от одного состояния XN оптимизируемого объекта к другому XN+1, более предпочтительному по заданному критерию Q:

XN+1 = XN + XN+1, где XN = F (XN, C), a C — параметры оператора оптимизации.

Очевидно, что параметры С должны изменяться так, чтобы про цесс оптимизации протекал наиболее успешно. Иначе говоря, необходима адаптация этих параметров:

CN+1 = CN + CN+1, где CN+1 = (CN, XN) — алгоритм адаптации. Такого рода параметрическая адаптация алгоритмов случайного поиска описана в следующей главе (§ 3.5), а подробнее — в работе [182].

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

Такие алгоритмы альтернативной адаптации лежат в основе адаптивного пакета программ оптимизации, рассмотренного в пятой главе (§ 5.3).

2.2.4. Программная адаптация вычислительной системы Программная адаптация связана с манипулированием отдельными программами и выбором той, которая работает наилучшим образом в смысле заданного критерия. Алгоритмически программная адаптация реализуется в виде альтернативного варианта структурной адаптации. Формализуем эту задачу.

Пусть имеются альтернативные программы решающие определенный класс задач (2.2.2) в BC. Как и выше, определен критерий эффективности решения конкретной задачи Pj с помощью i-й программы:

Это означает, что, решив задачу, всегда можно оценить критерий апостериорно; априорных соображений обычно не имеется.

Задача состоит в том, чтобы для имеющегося потока задач P выбрать программу, минимизирующую интегральный критерий критерия (2.2.6).

Эту задачу следует решать методами альтернативной адаптации, т. е. так переходить от одной программы (2.2.5) к другой, чтобы процесс привел к программе А*, оптимальной по выбранному критерию (2.2.7) в сложившейся ситуации.

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

2.2.4.1. Адаптивный выбор программы сортировки массивов Задача сортировки поступающего массива, т. е. упорядочения его элементов, является одной из наиболее распространенных задач в BC. Существует несколько методов сортировки, реализованных в виде программ (2.2.5), которыми располагает BC.

Критерием эффективности (2.2.6) сортировки массива Pj с помощью алгоритма Ai является, например, время сортировки. Если поток поступающих на сортировку массивов имеет некоторую статистическую устойчивость в виде плотности распределения р(P) и для этого распределения имеется наилучший метод А* сортировки, то естественно найти такой метод, используя альтернативную адаптацию.

Более того, если плотность распределения р(P) массивов изменилась, что повлекло за собой изменение оптимальной программы A*, то необходимо в процессе адаптации найти новую программу и перейти к ней. Решение этой задачи рассмотрено в пятой главе (§5.5).

2.2.4.2. Адаптация способов кодирования информации в канале передачи данных вычислительной системы Известно, что выбор оптимального метода (программы) кодирования по заданному критерию зависит от статистических свойств состояния канала. Пусть P — это состояние. Располагая информацией о р(Р), т. е. о статистических свойствах состояния канала связи, можно по заданному критерию (например, среднее время передачи одного бита информации, вероятность ошибки и т.

д.) выбрать код А*, наилучший из альтернативных А 1,..., Ат. Так и поступают в теории оптимального кодирования.

Однако свойства р(Р) реального канала связи изменяются во времени непредвиденным образом и в широких пределах. Поэтому необходимо эксплуатировать в канале ту программу кодирования, которая экстремизирует выбранный критерий эффективности для имеющегося состояния P канала, и переходить к другой, оптимальной при изменении состояния канала связи. Эта задача решается методами альтернативной адаптации и рассмотрена в пятой главе (§ 5.4).

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

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

Пусть P — условия эксплуатации BC, U — управляемый фактор BC, который может изменяться целенаправленно в процессе ее работы, а — критерий функционирования BC, характеризующий эффективность ее работы в условиях P при управлении U. Выражение (2.2.9) задается алгоритмически, т. е. в виде правила оценки эффективности q реальной (а не модельной) BC при различных P и U. Это обстоятельство исключает возможность вычисления интегрального критерия оптимального управления U*, решающего задачу эксплуатации 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 (например, среднее время решения задачи, суммарную длину очередей и т. д.).