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

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

изменения параметров алгоритма С (см. § 3,5, где описаны методы

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

распределения случайного шага). Этот вид адаптации имеет ярко

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

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

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

трудностей [182].

Однако эффект от параметрической адаптации часто бывает не

столь высок, как необходимо. Именно это обстоятельство заставляет

обращаться к адаптации структуры S алгоритма F. Тогда приходится

решать задачу, которая получается путем декомпозиции из (5.3.11):

(5.3.14)

решением которой является оптимальная структура S

алгоритма F,

естественным образом зависящая от ситуации L. Здесь ES —

множество допустимых структур алгоритма F, a E

— множество

допустимых параметров алгоритма, имеющего структуру S.

Как видно, задача (5.3.14) адаптации структуры является

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

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

— задача структурной адаптации (медленный контур) (рис. 5.3.1). Это

означает, что каждый шаг структурной адаптации должен

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

адаптации. В противном случае решение, принятое на верхнем уровне,

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

данной структуры оказалось

неоптимизированным по параметрам

этой структуры.

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

подходы к решению задачи структурной

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

1. Идентификация ситуации из

конечного множества [74, 84, 120]

опирается на заранее описанное

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

ситуаций

} (j = 1, ..., z<∞) (5.3.15)

типа «яма», «овраг», «долина» и т. д.

По выбранному критерию

ис. 5.3.1. Двухконтурная си-

стема адаптации алгоритма по-

а.

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

горитмов:

} (i = 1, .., q), (5.3.16)

т. е. имеет место определенное соответствие между сложившейся

ситуацией и оптимальной структурой алгоритма: L

→S

, которое

реализуется функцией i=φ(j) (i = l, ..., q; j = 1, ..., z). Задание (или

определение) функции φ однозначно решает задачу адаптации

структуры. Теперь она сводится к идентификации ситуации L, т. е. к

отнесению имеющейся ситуации к одной из множества (5.3.15).

Процедура идентификации должна использовать прежде всего

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

тесты, наиболее быстро выявляющие принадлежность текущей

ситуации к одной из (5.3.15). 2. Идентификация ситуации из

континуального множества. В этом случае каждую ситуацию удобно

кодировать вектором

L = (p

, ..., p

) (5.3.17)

в u-мерном пространстве. Каждой точке L этого пространства

соответствует лучший алгоритм U

, определяемый из очевид

ного соотношения

(5.3.18)

Таким образом, имеет место q-классовая задача распознавания

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

‹ L

, U

› (j = 1, ..., N), (5.3.19)

элементы которой получены заранее путем N-кратного решения

оптимизационной задачи

(5.3.20)

где L

(j=1,...,N) — ситуации, представляющие различные части

пространства {L}.

Пример [165, 167]. Рассмотрим два алгоритма случайного поиска

и U

(т. е. две альтернативные структуры S

и S

): с нелинейной

тактикой —

(5.3.21) (5.3.22)

с линейной тактикой

—

где ξ — случайный шаг. Пространство ситуаций {L} двумерно (u=2) и

образуется двумя вероятностями:

= Вер (∆Q

< 0 | ∆X = ξ) (5.3.23)

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

= Вер (∆Q

< 0 | ∆Q

N-1

< 0, ∆X

= ∆X

N-1

) (5.3.24)

— вероятностью того, что шаг в удачном направлении удачен.

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

т. е. средним числом неудачных шагов, то пространство (точ

нее, квадрат) {L} ситуаций (0≤p

, p

≤1) разбивается пара

болой p

= p

— p

+ l на две части, соответствующие ситуациям,

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

ритмов:

(5.3.25)

При p

= p

- p

+ 1 оба алгоритма по

критерию среднего штрафа эквивалентны. Как видно, располагая

значениями вероятностей (5.3.23), и (5.3.24), можно «включить»

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

. Этим

задача адаптации сводится к задаче оценивания вероятностей p

и р

на каждом шаге поиска.

Исходная информация для этой оценки — показатель d:

(5.3.26)

Определяющим является либо

последний повторный шаг (d = 1),

либо случайный (d = 0), либо возвратный (d = —1). Располагая парой

‹ c

, d

› (5.3.27)

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

следующим рекуррентным формулам:

(5.3.28)

где 0<γ

<1 (i = 1, ..., 4) — параметры, отражающие интенсивность

изменения ситуации L = (p

, p

) в оптимизируемом объекте в процессе

поиска.

Однако предварительная идентификация несвойственна процессам

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

использовать алгоритмы, описанные в § 5.1.

3. Начнем с алгоритмов, реализуемых автоматами с целесо-

образным поведением (см. п. 5.1.2.1). Приведем примеры реализации

различных алгоритмов адаптации поиска [215].

Пусть в моменты времени N

, ..., N

, ... происходит выбор

алгоритма оптимизации. Определим функцию

(5.3.29)

которая является

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

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

функции. Тогда под удачей (с=0) понимаем событие K(i)<0, а под

неудачей (с=1) — событие K(i)>0. Заметим, что функцию K(i) можно

ввести и другим образом.

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

такого подхода к альтернативной адаптации алгоритмов поиска [215].

В первой серии экспериментов в качестве алгоритмов опти-

мизации были выбраны два одинаковых алгоритма «с пересчетом» с

адаптацией величины рабочего шага [184]:

(5.3.30)

(5.3.31)

где ξ

— случайные

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

сфере; γ

>l, 0<γ

<1. Эти алгоритмы отличались друг от друга только

параметром р, согласно которому выбирались коэффициенты γ

и γ

исходя из рассмотренного в § 3.5 равенства: γ

1-p

= 1.

В работах [184, 215] было доказано (см. также § 3.5), что Для

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

асимптотически стремится к 0,27, а для небольших п приблизительно

равна 0,2. Поэтому естественно в одном алгоритме

взять р = 0,2, а во втором, неоптимальном, — р = 0,45. Работа

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

(5.3.32)

При начальном условии х

= (10, 0, ..., 0) моменты

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

= iK, т. е. через К тактов. На рис. 5.3.2 показано осредненное на базе

десяти экспериментов поведение минимизируемой функции при n=8,

l=3 и K=3; 5; 10. Видно, что K

опт

= 5 и эффективность поиска

незначительно уступала эффективности оптимального алгоритма

(напомним, что l — глубина памяти автомата).

На рис. 5.3.3 представлены аналогичные данные для п = 8, K=5 и

l=2; 3; 5. Как видно, лучшие результаты дает l=2—3, т. е.

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

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

адаптивных алгоритмов. На рис. 5.3.4 представлены результаты

расчетов для случая п=8, K=5, l=3. Здесь даны лучший и худший (по

останову) результаты из десяти и осредненная траектория. Хорошо

видно, что разброс невелик и худший

Рис. 5.3.2. Результаты оптимизации адаптивным двуальтерна-

тивным алгоритмом при различных значениях параметра такт-

ности К. Для сравнения приведены результаты работы альтер-

нативных алгоритмов в отдельности (р=0,2; 0,45).

Рис. 5.3.3. Результаты оптимизации адаптивным двуальтерна-

тивным алгоритмом при различной глубине памяти l автомата.

Для сравнения приведены результаты работы альтернативных

алгоритмов в отдельности (р=0,2; 0,45).

Рис. 5.3.4. Результаты оптимизации адаптивным двуальтерна-

тивным алгоритмом.

I — худшая траектория, II — лучшая траектория. Точками

обозначена осредненная траектория. Для сравнения приведены

результаты работы альтернативных алгоритмов в отдельности (р=0,2;

0,45).

вариант адаптивного алгоритма всегда лучше худшего алгоритма (р =

0,4) из двух его составляющих, а в среднем он примерно совпадает с

лучшим.

Вторая серия экспериментов проводилась с тремя аналогичными

алгоритмами случайного поиска. Значения р выбирались следующие:

р = 0,07; р = 0,2 и р = 0,45. Результаты экспериментов полностью

повторили данные предыдущей серии: совместная работа трех

алгоритмов не хуже, чем работа одного оптимального алгоритма.

В третьей серии экспериментов рассмотрена совместная работа

«реальных» поисковых алгоритмов — метода Давидона— Флетчера—

Пауэлла (ДФП) [233] и метода случайного поиска «с пересчетом» с

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

случайных векторов [182, 220]. В качестве класса минимизируемых

функций было выбрано множество функций вида

(5.3.33)

где ; 0<a

min

≤a

max

<∞

(i=1,...,n). Мно-

жества I

и I

и начальная точка X

разыгрывались случайно.

Переключение алгоритмов проводилось через K итераций.

Для функций, в которых присутствуют члены второй суммы

(5.3.33), метод ДФП не является сходящимся, но для функции (5.3.32)

он имеет неоспоримые преимущества перед рассматриваемым

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

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

структурной адаптации по сравнению с отдельными алгоритмами: для

всех функций минимум находился с заданной точностью.

4. Рассмотрим теперь эксперименты по использованию стоха-

стического автомата с переменной структурой (см. п. 5.1.2.2) для

целей альтернативной адаптации поиска [174]. Альтернативные

алгоритмы были те же, что и ранее — (5.3.30) и (5.3.31), но с другими

значениями параметра р: U

= U

опт

: р = = р* = 0,2; U

: p = 0,45. Таким

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

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

работа алгоритма обеспечивалась лишь при дополнительном

сглаживании вида

(5.3.34) (5.3.35)

где

a ∆Q

(i)

— приращение

показателя качества на N-м

этапе при работе i-ro

алгоритма U

(i = l, 2).

Параметрами альтер-

нативной адаптации яв-

лялись:

— число К тактов, об-

разующих один этап поис-

ка, за время которого про-

исходит оценка

(5.3.36)

(в течение одного этапа

алгоритм поиска не. изме-

няется);

— параметр µ сглажи

вания оценок (5.1.31) —

(5.1.34);

— параметр β сглажи

вания в формуле (5.3.34).

Результаты экспери-

ментов, осредненные по

десяти реализациям, пред-

ставлены на рис. 5.3.5, где

показано поведение деся-

тичного логарифма мини-

мизируемой функции в

процессе оптимизации.

Параметры алгоритма

адаптации были следую-

щими:

Случа

µ β

1 0,9 0,2

5 0

1 0

5 0

9 0

Рис. 5.3.5. Результаты экспериментов. а—г —

динамика оптимизации для различных

значений параметров адаптации. Пунктир —

неоптимальный алгоритм (A

), штрихпунктир

— оптимальный (А

); сплошная линия —

алгоритм со структурной адаптацией, д —

диаграмма переключения алгоритмов для

случая «г».

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

всегда лучше худшего в данной ситуации алгоритма. Более того, при

удачном выборе параметров адаптации этот алгоритм может работать

как лучший (см. рис. 5.3.5, г) или Даже лучше него (см. рис. 5.3.5, в).

Дело в том, что алгоритм переключения включает наилучший по

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

параметрической адаптации случайно таким наилучшим может

оказаться худший в среднем (р = 0,45) алгоритм, который и внесет

свой вклад в процесс поиска. Это объяснение подтверждается тем, что,

хотя в среднем всюду U

, структурная адаптация не исключала

полностью U

, что ожидалось в экспериментах (см. рис. 5.3.5, д). Как

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

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

оптимизации, и тем самым значительно повысить эффективность

процесса поиска.

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

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

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

позволяет существенно повысить эффективность работы пакета

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

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

§ 5.4. Альтернативная адаптация в

процессах передачи данных

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

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

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

ределенных факторов в виде нестационарного уровня случайных

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

электрическими источниками (атмосферными, техническими и т. д.),

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

непредсказуемыми изменениями загрузок и пропускной способности

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

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

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

факторов, является адаптация как метод управления [170]. Среди задач,

решаемых адаптивными методами, выделим:

а) задачу выбора маршрутов передачи данных («адаптив

ная маршрутизация»);

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

связи в условиях нестационарных помех.

Отметим следующие результаты. Вопросы адаптации для

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

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

когда загрузка линий связи и конфигурация сети изменяются в

широких пределах, рассматривались в работах [74, 203]. Среди

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

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

распределенных (децентрализованных) системах и оперативно

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

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

передачи данных. Адаптация процесса направления потоков

данных в сети с коммутацией сообщений была рассмотрена в работе

[121]. Предложенные алгоритмы предназначены для автономного

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

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

линейной фильтрации предыдущих наблюдений.

Интересно предложение использовать стохастические обу-

чающиеся автоматы, обладающие свойством быстрого приспо-

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

маршрутизации вызовов в сети телефонной связи [121]. С помощью

модельного эксперимента показано преимущество адаптивного

рандомизированного выбора направления прохождения телефонных

вызовов по сравнению с регулярными способами выбора

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

Простейший детерминированный адаптивный способ управления

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

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

представлен в работе [51]. Для этого предлагается использовать два

кода, корректирующих ошибки, которые обладают различной

помехозащищенностью. Система переходит к более

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

случае обнаружения ошибки в сообщении, т. е. по запросу

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

случае отсутствия ошибок. Такая оперативная реакция на состояние

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

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

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

основанные на оперативном использовании информации о текущем

состоянии управляемого объекта (процесса), могут быть успешно

применены в децентрализованных сложных системах. передачи

данных с высоким уровнем неопределенности. Рассмотрим этот

вопрос подробнее.

В процессе передачи данных вероятность искажения сообщения

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

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

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

к другим, альтернативным кодам. Для учета этого

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