Растригин Л.А. Адаптация сложных систем
Подождите немного. Документ загружается.
Л. А. РАСТРИГИН
Адаптация
сложных
систем
Методы
и приложения
РИГА «ЗИНАТНЕ» 1981
6S0.1 32.81
Р245 УДК
62-506
Р а с т р и г и н Л. А. Адаптация сложных систем. —
Рига: Зинатне, 1981. — 375 с.
Монография посвящена одному из бурно развивающихся
направлений современной кибернетики — методам
адаптации сложных объектов. В качестве алгоритмов адап-
тации описываются различные модификации случайного
поиска как наиболее эффективного средства управления
сложными объектами. Впервые рассматриваются алгоритмы
структурной адаптации (альтернативной и эволюционной),
позволяющие эффективно изменять структуру объекта в
процессе его функционирования. Приводятся многочислен-
ные примеры применения адаптивного подхода для решения
широкого класса научно-технических задач — таких, как
адаптация вычислительных систем и процессов обучения
иностранному языку; синтез оптимальных решающих пра-
вил, многопороговых логических элементов и планов экс-
перимента; агрегация (разрезание) графов, и других. Табл. 15,
ил. 115, библиогр. 304 назв.
Рецензенты:
д-р техн. наук Я. А. Гельфандбейн,
канд. техн. наук Л. П. Богомолов
Печатается по решению Редакционно-издательского совета
Академии наук Латвийской ССР от 28 декабря 1979 года.
30501—126
Р М811(11)— 81
24.81.1502000000
© Издательство «Зинатне», 1981
Оглавление
Предисловие ....................................................................................................... 9
Глава 1. ПРОБЛЕМА АДАПТАЦИИ......................................................... 13
§ 1.1. Адаптация в процессах управления сложным объектом . . . 13
1.1.1.Управление и его атрибуты ........................................ . . 14
1.1.2. Этапы управления сложным объектом......................................... 17
1.1.3. Адаптация системы управления .......................................... 25
§ 1.2. Постановка задачи адаптации ............................................................. 28
§ 1.3. Адаптация и оптимизация ................................................................... 32
§ 1.4. Адаптация и компенсация ................................................................... 35
§ 1.5. Типы адаптации.................................................................................... 38
1.5.1. Классификация типов адаптации.......................................... : 38
1.5.2. Параметризация структуры объекта............................................ 41
Глава 2. ОБЪЕКТЫ АДАПТАЦИИ ..................................................... . 45
§ 2.1. Сложная система как объект адаптации ....... 45
§ 2.2. Вычислительная система как объект адаптации ..... 47
2.2.1. Специфика вычислительных систем.............................................. 47
2.2.2. Уровни адаптации вычислительной системы ............................... 49
2.2.3. Алгоритмический уровень адаптации вычислительной системы 50
2.2.4. Программная адаптация вычислительной системы ... 52
2.2.4.1. Адаптивный выбор программы сортировки массивов 53
2.2.4.2. Адаптация способов кодирования информации в канале
передачи данных вычислительной системы .............................. 53
2.2.5. Системная адаптация вычислительной системы .... 53
2.2.5.1. Адаптивная сегментация памяти системного математиче
ского обеспечения вычислительной системы .......................................... 54
2.2.5.2. Адаптация расположения информационных блоков на маг
нитных дисках........................................................................... 55
2.2.5.3. Адаптивное распределение памяти в многомашинной вы
числительной системе (сети)...................................................... 56
2.2.5.4. Адаптивные дисциплины распределения задач в многома
шинной вычислительной системе ............................................... 56
2.2.5.5. Адаптация многомашинной вычислительной системы к кон-
кретному пользователю............................................................. 57
§ 2.3. Процессы обучения ............................................................................. 57
§ 2.4. Графы.................................................................................................... 59
§ 2.5. Дисциплины обслуживания ................................................................ 61
Глава 3. СЛУЧАЙНЫЙ ПОИСК В ЗАДАЧАХ ОПТИМИЗАЦИИ И
АДАПТАЦИИ ................................................................................... 65
§ 3.1. Рандомизация управления ................................................................... 65
§ 3.2. Предпосылки случайного поиска........................................................ 69
§ 3.3. Алгоритмы случайного поиска ........................................................... 81
3.3.1. Структура поискового метода...................................................... 81
3.3.2. Некоторые простейшие алгоритмы случайного поиска . . 85
3.3.2.1. Случайный поиск с линейной тактикой .................................... 85
3.3.2.2. Случайный поиск с нелинейной тактикой.................................. 88
3.3.2.3. Случайный поиск по наилучшей пробе.................................... 91
3.3.2.4. Метод стохастического градиента . ................................... 91
3.3.3. Автоматные алгоритмы случайного поиска ................................ 93
3.3.3.1. Коллектив оптимизирующих автоматов с целесообразным
поведением ................................................................................. 95
3.3.3.2. Автоматный случайный поиск с самообучением .... 96
§ 3.4. Учет ограничений в процессах случайного поиска ..... 97
3.4.1. Типы ограничений........................................................................ 98
3.4.2. Случай S=S
H.................................................................................................................................
99
3.4.2.1. Использование возврата ............................................................ 99
3.4.2.2. Использование самообучения в виде адаптации распреде
ления случайного шага............................................................... 100
3.4.2.3. Адаптация величины шага ........................................................ 101
3.4.3. Случай S=S
G................................................................................................................................
101
3.4.4. Случай S=S
H
∩S
G .....................................................................................................................
103
3.4.5. Случай S=S
D.................................................................................................................................
103
3.4.6. Случай S=S
D
∩S
H
. ....................................................................... 104
§ 3.5. Адаптация алгоритмов случайного поиска ........................................ 104
3.5.1. Анализ задачи адаптации поиска .......................................... . 104
3.5.2. Параметрическая адаптация алгоритмов случайного поиска . 105
3.5.2.1. Адаптация величины рабочего шага ......................................... 106
3.5.2.2. Адаптация распределения случайного шага ..... 107
3.5.3. Структурная адаптация алгоритмов поиска............................... 109
§ 3.6. Глобальный поиск ................................................................................ 111
3.6.1. « Набросовые» алгоритмы . . . . 112
3.6.1.1. Случайный наброс с локальным поиском........ 112
3.6.1.2. Адаптивный набросовый алгоритм........... 112
3.6.1.3. .Набросовый алгоритм глобального поиска с идентифика
цией распределений ....................................................... . 114
3.6.2. «Блуждающие» алгоритмы ..................................................... . 114
3.6.2.1. Метод «зашумления» градиента ................................................ 114
3.6.2.2. Метод сглаживания................................................................... 115
3.6.2.3. Метод направляющего конуса............... 117
§ 3.7. Бионические алгоритмы случайного поиска................................ 118
3.7.1. Эволюционные алгоритмы............................................................ 119
3.7.1.1. Эволюционный алгоритм случайного поиска...... 119
3.7.1.2. Популяционный алгоритм случайного поиска..... 120
3.7.2. Поведенческие алгоритмы............................................................ 122
3.7.3. Клеточные и субклеточные алгоритмы....................................... 125
Глава 4. ПАРАМЕТРИЧЕСКАЯ АДАПТАЦИЯ ...................................... 127
§ 4.1. Некоторые алгоритмы параметрической адаптации................... 127
4.1.1. Метод стохастической аппроксимации.......... 128
4.1.2. Сглаживание помех ..................................................................... 129
4.1.3. Стохастическое накопление .......................................................... 131
§ 4.2. Адаптация в процессах обучения........................................................ 134
4.2.1. Обучение как управление сложным объектом ............... 134
4.2.2. Этапы обучения ........................................................................... 136
4.2.2.1. Формулировка целей обучения ................................................ 136
4.2.2.2. Выделение объекта обучения из среды................................... 137
4.2.2.3. Структурный синтез модели объекта обучения.... 137
4.2.2.4. Идентификация параметров С модели объекта обучения . 139
4.2.2.5. Планирование экспериментов с объектом .............................. .140
4.2.2.6. Синтез оптимального обучения ................................................ 141
4.2.2.7. Реализация обучения.................... 142
4.2.2.8. Коррекция (адаптация) ............................................................ 143
4.2.3. Система обучения с адаптивной моделью ................................... 145
4.2.4. Модель ученика........................................................................... 146
4.2.5. Модельный анализ процесса обучения....................................... 149
4.2.6. Экспериментальное сопоставление различных моделей обу
чения ............................................................................................. 153
4.2.7. Обучение с использованием предложенной адаптивной
модели ..................................................................................... 160
§ 4.3. Адаптивный синтез многопороговых логических элементов мето
дом случайного поиска ..................................................................... 165
4.3.1. Пороговый логический элемент ........................................... 166
4.3.2. Многопороговый логический элемент......................................... 167
4.3.3. Анализ задачи синтеза оптимальных многопороговых логи
ческих элементов........... 169
4.3.4. Индексные зоны ........................................................................... 171
4.3.5. Экспериментальный синтез многопороговых логических эле
ментов ......................................................................................... 174
4.3.6. Вероятностные характеристики поиска...................................... 175
4.3.7. Синтез надежного многопорогового логического элемента 177
4.3.8. Многозначные многопороговые логические элементы 180
§ 4.4. Адаптивный синтез оптимальных планов эксперимента для ре
грессионной модели.......................................................................................... 186
4.4.1. Постановка задачи ................................................. ................. 186
4.4.2. Последовательный синтез плана................................................. 190
4.4.3. Диалоговый синтез плана ........................................................... 200
§ 4.5. Адаптация в процессах восстановления числовых таблиц.......... 203
§ 4.6. Адаптация алгоритмов распознавания........................................... 212
§ 4.7. Адаптивная идентификация параметров распределения............. 223
§ 4.8. Адаптивный синтез датчика случайных чисел с заданной авто-
корреляционной функцией........................................................ 231
Глава 5. АЛЬТЕРНАТИВНАЯ АДАПТАЦИЯ...................................... 239
§ 5.1. Алгоритмы альтернативной адаптации ............................................. 239
5.1.1. Постановка задачи...................................................................... 239
5.1.2. Алгоритмы-автоматы.................................................................... 240
5.1.2.1. Автоматы с целесообразным поведением............................... 242
5.1.2.2. Стохастические автоматы с переменной структурой.. 244
5.1.2.3. Алгоритм «многорукого бандита» ............................................ 245
§ 5.2. Исследование алгоритмов альтернативной адаптации ............... 248
§ 5.3. Альтернативная адаптация в процессах поисковой оптимизации.. 253
§ 5.4. Альтернативная адаптация в процессах передачи данных........... 264
5.4.1. Постановка задачи . ........................................................ 264
5.4.2. Двуальтернатнвный выбор кода ................................................ 266
5.4.3. Адаптация информационного поля протоколов связи.... 270
§ 5.5. Адаптация процессов сортировки массивов ................................ 274
Глава 6. ЭВОЛЮЦИОННАЯ АДАПТАЦИЯ ............................................. 277
§ 6.1. Алгоритмы эволюционной адаптации................................................ 277
6.1.1. Общая модель эволюции структуры....................................... 277
6.1.2. Эволюционная адаптация графа ............................................. 279
6.1:3: Эволюционная адаптация автомата......................................... 280
§ 6.2. Адаптивная агрегация графов . ........................................................... 282
6.2.1. Постановка задачи ............................... ............................. 282
6.2.2. Примеры практических задач агрегации графа .... 285
6.2.2.1. Компоновка электронной аппаратуры.................................. 285
6.2:2.2. Адаптивная сегментация программного обеспечения вы
числительной системы .................................... . . . 286
6.2.2.3. Адаптация расположения блоков информации на. магнит
ных дисках .............................................................................. 286
6.2.2.4. Обобщение предыдущей задачи........................................... 289
6.2.3. Адаптивная агрегация графа методами случайного поиска 289
6.2.3.1. Методы агрегации (разрезания) графа. . . . . 289
6.2.3.2. Операции преобразования агрегации ................................... 290
6.2.3.3. Алгоритм устранения нарушения ограничений .. 292
6.2.3.4. Локальная минимизация критерия при неизменной среде 294
6.2.3.5. Алгоритм глобальной минимизации критерия оптималь
ности Q(U) ............................................................................... 300
6.2.3.6. Адаптивная агрегация графа с переменными свойствами в
детерминированной среде ....................................................... 302
6.2.3.7. Стохастическая задача агрегации графа в соответствии с
решением (6.2.18) . . ..................................................... 303
6.2.3.8. Адаптивная агрегация графа, функционирующего в не
стационарной среде ................................. .....308
6.2.4. Некоторые обобщения задачи об агрегации графа ... 310
§ 6.3. Адаптация процессов распределения памяти в вычислительной
сети ............................................................................................................................... ..312
6.3.1. Формулировка задачи ............................................................... 312
6.3.2. Сведение задачи распределения памяти к задаче математи
ческого программирования ........................................................ 313
6.3.3. Адаптивное распределение памяти в сети ЭВМ ..................... 315
§ 6.4. Эволюционная адаптация структуры решающих правил . . . 319
6.4.1. Постановка задачи..................................................................... 320
6.4.2. Адаптация структуры перцептрона.......................................... 322
6.4.3. Оценка вероятности образования оптимальной структуры
перцептрона в процессе адаптации........................................ 325
6.4.4. Модельные эксперименты .......................................................... 328
6.4.5. Применение перцептрона с адаптивной структурой для ре
шения некоторых практических задач распознавания .. 331
6.4.5.1. Классификация объектов промышленного производства 331
6.4.5.2. Классификация в задачах технологического проектирова
ния ......................................................................................... 335
6.4.5.3. Прогнозирование активности химических соединений по их
структурным формулам .......................................................... 342
6.4.5.4. Прогнозирование месторождений полезных ископаемых 345
§ 6.5. Адаптивный синтез оптимальных факторных планов эксперимента 345
6.5.1. Постановка задачи ..................................................................... 345
6.5.2. Адаптация вероятностных характеристик поиска .. 346
6.5.3. Адаптивный синтез планов эксперимента методами случай
ного поиска с пересчетом и спуском....................................... 353
Заключение ...................................................................................................... 358
Список литературы ........................................................................................ 360
ПРЕДИСЛОВИЕ
В своих орудиях человек обладает
властью над внешней природой, тогда
как в своих целях он скорее подчи-
нен ей.
Гегель
Понятие адаптации как инструмента («орудия») целенаправ-
ленного воздействия на объект, столь распространенное в биологии и
социологии (известны и широко используются феномены
биологической и социальной адаптации), в последние 20 лет стало
фигурировать в математической, технической и особенно в
кибернетической литературе [4—11]. Трудно сказать определенно, с
чем связано пристрастие математиков и инженеров к биологической
терминологии. Может быть, это инерция давно начавшегося
процесса «биологизации» терминов кибернетики, который идет
одновременно с процессом обогащения биологии кибернетической
терминологией. Но возможно, что причины здесь более глубокие:
огромные возможности биологических систем, выгодно отличающие
их от самых совершенных технических устройств и вызывающие
пристальное внимание, восхищение и даже зависть инженеров.
Необходимость введения адаптации хорошо чувствует всякий
проектировщик, которому приходится создавать систему при зна-
чительной априорной неопределенности об условиях ее функ-
ционирования. Осреднение по этой неопределенности редко бывает
удачным. С другой стороны, всякое осреднение поведения среды
позволяет спроектировать систему, оптимально работающую только
при среднем состоянии среды. Всякое же отклонение среды от
среднего приводит к неоптимальности функционирования системы.
Именно поэтому так важно вводить в систему адаптирующие
подсистемы, которые будут ее изменять, с тем чтобы поддерживать
ее эффективность в оптимальном состоянии независимо от состояния
среды.
Как видно, термин «адаптация» уже прочно вошел в инженерный
лексикон и, следовательно, нуждается в более точном определении.
Действительно, разъяснение понятия адаптации как приспособления
к новым условиям, которое вполне удовлетворяет биологов и
социологов, совершенно неудовлетворительно с точки зрения
инженера. Для строгого определения этого понятия
следует рассмотреть процессы адаптации в биологии и социологии с
инженерных позиций.
В понятие адаптации как активного действия (управления)
обычно вкладывают два смысла: приспособление к фиксированной
среде (условно назовем пассивной адаптацией) и поиск среды,
адекватной данной системе (назовем соответственно активной
адаптацией). В первом случае адаптирующаяся система
функционирует так, чтобы выполнять свои функции в данной среде
наилучшим образом, т. е. максимизирует свой критерий
эффективности функционирования в данной среде. Активная
адаптация, наоборот, подразумевает либо изменение среды с
целью максимизации критерия эффективности, либо активный
поиск такой среды, в которой достижим желаемый комфорт.
Очевидно, что в действительности оба вида адаптации встре-
чаются одновременно и взаимодействуют друг с другом. Растения
обладают преимущественно пассивной адаптацией, а животные —
активной. В социальной жизни и та и другая адаптация проявляются,
по-видимому, в равной мере. В обоих случаях для осмысления
адаптации как процесса необходимо разобраться по крайней мере в
двух обстоятельствах:
1.Какова цель адаптации, т. е. что называть эффективным
функционированием системы?
2. Каков алгоритм адаптации, т. е. каким способом достига
ется поставленная цель?
Таким образом, задавая цель (какая бы она ни была) и
способ ее достижения, мы тем самым определяем адаптацию как
процесс.
Это означает, что адаптация ничем не отличается от управления
(в широком смысле). Действительно, адаптация, как и всякое
управление, есть организация такого целенаправленного
воздействия на объект, при котором достигаются заданные цели.
Отождествляя адаптацию и управление, необходимо определить
тип управления, к которому относится адаптация.
Распространено мнение, что адаптацию как управление следует
отнести к оптимизации в обстановке помех, в процессе которой
параметры объекта изменяются так, чтобы его показатель качества
стремился к экстремальному значению независимо от изменения
ситуации. Аналогичное определение приводится в книге Я. 3.
Цыпкина «Адаптация и обучение в автоматизированных системах»
(M., Наука, 1968): «...процесс изменения параметров и структуры
системы, а возможно, и управляющих воздействий на основе текущей
информации с целью достижения определенного, обычно
оптимального состояния системы при начальной неопределенности и
изменяющихся условиях работы». Здесь четко определено
требование оптимизации по заданному критерию.
Однако сложные системы (особенно биологические и социальные),
как правило, не имеют единственного критерия функционирования.
Такого рода системы функционируют в обстановке мно-
гокритериальности, причем эти критерии могут быть не только
экстремальными, но и иметь характер ограничений. Это побуждает
формулировать сразу несколько критериев и варьировать их
выбор в зависимости от сложившейся ситуации и внутренних
потребностей самой системы. Таким образом, уже выбор критериев
адаптации является процессом адаптивным и должен учитываться
при определении адаптации.
Поэтому, с учетом особенностей сложных систем, адаптацию в
широком смысле можно определить как процесс целенаправленного
изменения параметров и структуры системы, который состоит в
определении критериев ее функционирования и выполнении этих
критериев.
Это определение включает приведенное выше, но, кроме того,
позволяет изменять критерии функционирования системы, по ко-
торым оценивается эффективность ее работы при организации
адаптации. Введение процедуры выбора критерия оптимальности в
процессе адаптации расширяет понятие адаптации и сближает его с
биологическим и социологическим толкованием. Последнее
обстоятельство является очень важным.
Дело в том, что в технике пока очень мало эффективно рабо-
тающих адаптивных систем — во всяком случае, значительно
меньше, чем хотелось бы. Такая ситуация сложилась в результате
того, что реальные объекты не терпят поисковых воздействий,
необходимых для организации поиска экстремума критерия
оптимальности. Интерес, проявляемый в последнее время к так
называемым беспоисковым системам оптимизации, вызван
именно этим обстоятельством. Однако далеко не все процессы
адаптации могут быть выполнены беспоисковым способом, тре-
бующим информации о структуре объекта. Поэтому проблема
адаптации в технике сводится к снижению той высокой платы,
которую приходится платить за процесс адаптации.
Это можно сделать по крайней мере двумя путями — выбором
удачного алгоритма адаптации при фиксированном критерии и
удачным варьированием критериев при фиксированном алгоритме
адаптации. Третий путь довольно естественно образуется
варьированием алгоритмов и критериев. В технике применяется
только первый путь. Биологические и социальные системы широко
используют еще и второй путь адаптации — изменение целей, в чем,
по-видимому, и заключается причина удивительно гибкой
адаптивности этих систем, которой пока практически лишены
технические системы адаптации.
Основная цель изучения процессов адаптации должна со-
стоять именно в отыскании причин и механизмов гибкости
процессов адаптации в биологических и социальных системах с
целью их перенесения в технические системы. Именно это сообра-
жение заставляет анализировать процессы адаптации на разных
уровнях: от самого низкого — технического, до самого высокого—
социального.
К сожалению, пока далеко не все идеи биологической и со-
циальной адаптации могут быть формализованы и использованы в
технических системах (например, известные феномены мгновенной
адаптации и преадаптации). Однако то немногое, что уже
доступно, дает великолепные результаты (например, алгоритмы
адаптации, моделирующие биологическую эволюцию и поведение
живых существ). Именно это позволяет надеяться, что
следующий «прорыв» в области адаптивных систем будет именно в
направлении моделирования биологической и социальной адаптации.
Однако в данной книге затронутые проблемы не обсуждаются:
здесь пока слишком мало математически содержательных
результатов. Эта книга появилась как обобщение работ автора в
области адаптации и оптимизации сложных систем различного вида.
Спектр рассматриваемых систем достаточно широк — от
вычислительной сети до системы обучения иностранному языку. И
каждая из этих систем адаптируется с использованием алгоритмов
случайного поиска.
Применение случайного поиска для целей адаптации и опти-
мизации рассматриваемых систем имеет два основания. Во-первых,
случайный поиск является наиболее эффективным средством
адаптации сложных систем: он прост в реализации, легко моди-
фицируется и программируется, имеет высокое быстродействие. Это
объективные показатели, способствовавшие выбору случайного
поиска в качестве основного инструмента. Есть и субъективные
причины, связанные с предыдущими интересами автора, который
последние 20 лет занимался разработкой и пропагандой алгоритмов
случайного поиска. Естественно, что при решении прикладных задач
был выбран именно случайный поиск.
Кроме теоретических вопросов в книге рассмотрено более
десяти различных прикладных адаптационных и оптимизационных
задач, в решении которых принимал участие автор (отсюда несколько
субъективный отбор этих задач). Полученные результаты имеют
достаточно общий характер и легко распространяются на решение
других задач.
С книгой в рукописи ознакомились Я. 3. Цыпкин, С. 3. Кузьмин, E.
В. Маркова и A. H. Скляревич, которые сделали ряд полезных
замечаний, учтенных в окончательной редакции. Всем этим лицам
автор выражает свою глубокую признательность.
Пос. Межциемс (Рижский р-н)
23 июля 1979 года
Автор