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

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

Вероятность сохранения автомата при селекции пропорциональна

его эффективности а, что естественно при реализации искусствен-

ного отбора.

Эксперименты с алгоритмами случайного поиска [136], моде-

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

зали их большую гибкость, надежность и эффективность.

3.7.2. Поведенческие алгоритмы

Многие алгоритмы случайного поиска моделируют поведение

живых организмов в неизвестной среде. В данном случае моде-

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

к комфортным ситуациям и уклоняться от некомфортных. Эта

способность, выработанная эволюцией, глубоко рациональна и

широко используется в процессах управления. Используется она

и в случайном поиске. Назовем прежде всего алгоритм с линей-

ной тактикой, рассмотренный в § 3.3 (3.3.12). Этот алгоритм

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

рой могут быть для него комфортными и некомфортными. По-

падая в такого рода среду, животное и человек обучаются: у

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

состоит линейность их поведения. (Линейность поведения ши-

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

Поощрение в процессах воспитания дает результат именно бла-

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

Рассмотрим модель поведения мыши в Т-образном лабиринте

(рис. 3.7.1). Подобные эксперименты неоднократно проводились в

различных лабораториях. Мышь здесь должна выбрать одно из

двух направлений. Пусть p

— вероятность ее поворота влево в i-м

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

ис 3.7.1. Варианты экспериментов по выработке определенного

поведения:

а — с поощрением, б — с наказанием, в — сочетание поощрения с

аза

ни

экспериментов. В первом эксперименте (рис. 3.7.1, а) зверек обучится

устойчиво поворачивать влево (р=1) в результате поощрения,

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

обучения выражается следующей рекуррентной формулой [39]:

i+1

= (l - α) p

+ α. (3.7.5)

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

α(1— p

), т. е. p

i+1

= p

+ α (l — р

), где 0<α<1 — параметр обучения при

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

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

описываться несколько иначе:

i+1

= (1 - α) p

, (3.7.6)

т. е. вероятность будет уменьшаться, так как 1-α < 1.

Совершенно иначе построен второй эксперимент (рис. 3.7.1, 6), в

котором для обучения используется наказание (удар тока). Мышь и

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

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

i+1

= = (1 — β) р

+ β, где

0<р<1 — также параметр обучения, который, вообще говоря, не

совпадает с α.

И, наконец, тот же результат будет получен при обучении по

«принципу кнута и пряника» (рис. 3.7.1, в), но с иным параметром

обучения γ.

Как видно, одного и того же поведения — поворота влево —

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

наказанием и их, сочетанием.

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

организации случайного поиска следующим образом. Пусть p

—

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

шаге поиска:

= Вер (∆u

> 0) (3.7.7)

(пусть величина смещения будет равна единице, т. е. | ∆u

| = l).

Естественно эту вероятность изменять так, чтобы увеличить число

удачных шагов, для которых ∆Q<0.

Здесь можно применить все три рассмотренные выше схемы

обучения:

1. Обучение только поощрением (только при ∆Q<0):

j,i+1

= (1 - α) p

+ α sg u

(j = 1, ..., q), (3.7.8)

где

Хорошо видно, что эта вероятность увеличивается, если шаг ∆u

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

логично. В случае неудачи (∆Q≥0) p

j,i+1

(j = 1, ..., q), т. е.

вероятности, естественно, не изменяются. При оптимизации

алгоритмом поиска

(3.7.9)

процесс поиска будет иметь

выраженный глобальный характер. Его будет «нести» в направлении

первого же удачного шага, пока не будет сделан другой удачный,

изменяющий направление «сноса», и т. д.

2. Обучение только наказанием (при ∆Q≥0):

j,i+1

= (1 - β) p

+ β sg (-∆u

) (j = l, ..., q). (3.7.10)

При удаче (∆Q<0) p

j,i+1

= p

j,i

(j = 1, ..., q), т. е. вероятности не

изменяются.

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

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

локального экстремума.

3. Обучение поощрением и наказанием можно построить дво

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

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

j,i+1

= (1- γ) p

+ γ sg (-∆u

∆Q) (j = 1, ..., q). (3.7.11)

Однако более гибка и интересна другая схема, объединяющая

обучение по формуле (3.7.8) при ∆Q<0 и по формуле (3.7.9) при ∆Q≥0.

Уровень поощрения и наказания может быть различным (при α=β=γ

эта схема вырождается в (3.7.11)). Здесь, варьируя величины α и β

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

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

(точнее — дрессировки).

Любопытно, что при α>β, т. е. при более интенсивном поощрении,

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

более широкой области, чем при β<α, когда поиск имеет локальный

характер. Сильное наказание сужает область поиска зоной

ближайшего локального экстремума.

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

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

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

3.7.3. Клеточные и субклеточные алгоритмы

Спонтанная активность сети нейронов и стохастическое пове-

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

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

делирующих эти известные биологические феномены.

В такой сети в процессе поиска изменяются матрица параметров

связи нейронов и их пороги чувствительности. При этом считается,

что минимизируемая целевая функция Q(U) определяется

управляющим нервным центром и ее значение по эфферентному

каналу сообщается каждому нейрону в сети.

Анализ этих феноменов дал возможность создать новый алгоритм

случайного поиска, названный матричным [72, 73]. Матричный

алгоритм отличается тем, что случайно возмущается матрица

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

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

Траектории спуска полученного таким образом алгоритма

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

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

Выше приведено несколько примеров успешного использования

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

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

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

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

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

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

развивается представление о «случайно-поисковом» характере

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

минимизирующих энергетические затраты на внутриклеточную

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

стохастическое поведение микроструктурных образований («эн-

доплазматического ретикулума») клетки, которое создает режим

случайного поиска ее состояния, соответствующего энергетически

наиболее экономичному обеспечению специфической функции

клетки [71].

Именно на этих фактах было основано предложение ввести в

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

значений ее основных параметров — коэффициентов чувст-

вительности специфических (синаптических) входов.

Модель клетки, в которую включен механизм случайного

поиска, оптимизирующего эти параметры [69, 71], позволяет ми-

нимизировать «дискомфорт» этой клетки в данной среде. Не-

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

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

соответствие наблюдаемым нейроцитохимическим и нейрофизио-

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

обусловлено именно включением в нее механизмов случайного

поиска.

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

качественно новой форме — как объяснительное начало, оказывая тем

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

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

процессах в биосфере [269].

Приведенный в этой главе материал имеет обзорный характер,

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

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

основе которых лежит обобщающая сила случайного поиска (см. п.

3.3.1). Автор убежден, что создание общей теории адаптации

возможно именно на этом пути. Залогом являются прежде всего

бионические предпосылки: ведь природа «работает» методом

случайного поиска, и все естественные тончайшие механизмы

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

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

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

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

детерминированных закономерностей как живой, так и неживой

природы.

Параметрическа

я адаптация

...Звуки умертвив,

Музыку я разъял, как труп. Поверил Я

алгеброй гармонию.

Пушкин. Моцарт и Сальери

В тех случаях, когда объект удается «разъять» до параметров, т. е.

параметризировать, адаптацию ввести наиболее просто. В этой

области имеются хорошая математическая теория и множество

практических приложений. Однако опыт использования па-

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

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

свойства адаптивного процесса на заданном уровне.

Данная глава посвящена решению прикладных задач пара-

метрической адаптации объектов различной природы. Здесь рас-

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

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

случайных чисел с заданными свойствами. Указанные задачи

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

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

эффективность этих алгоритмов.

§ 4.1. Некоторые алгоритмы

параметрической адаптации

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

функции Q(U) в обстановке случайных помех, т. е. по ее наблюдениям,

зашумленным аддитивной помехой:

Q'(U) = Q(U) + ε(σ), (4.1.1)

где U — вектор оптимизируемых параметров, а ε(σ) — незави

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

и дисперсией σ

, которая может быть неизвестна. Для решения

задачи оптимизации функции

(4.1.2)

заданной лишь своими наблюдениями (4.1.1),

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

рассмотрены

в предыдущей главе (см., например, § 3.3, 3.5—3.7). Рассмотрим

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

(4.1.2).

4.1.1. Метод стохастической аппроксимации

Этот метод является по сути дела градиентным методом с

программно изменяемыми пробными и рабочими шагами:

4.1.3) где компоненты оценки градиента имеют вид

(4.1.4)

Здесь e

— i-й орт (i = 1, ..., q). Для сходимости этой процедуры при

достаточно широком классе функций Q(U) необходимо, чтобы

коэффициенты рабочего (a

) и пробного (g

) шагов удовлетворяли

следующим соотношениям [41, 237]:

(4.1.5)

Первое из

этих соотношений требует, чтобы величина a

уменьшалась не

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

значительно медленнее рабочего. Условиям (4.1.5) удовлетворяют,

например, следующие соотношения:

(4.1.6)

где 0<α≤1; β>0; 2(α-β)>1.

Хотя сходимость этого метода доказана строго математически, его

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

удовлетворяет пользователя. Дело здесь в том, что указанная

сходимость метода проявляется при N→∞, что, естественно, не играет

роли при практических расчетах. На практике необходимо в процессе

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

экстремума заданного критерия. С другой стороны, программный

характер изменения параметров (4.1.6) не учитывает ситуации,

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

эффективность процесса поиска. Наконец, условия (4.1.5) не

учитывают дрейф

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

Указанными обстоятельствами и объясняется, что стохастическая

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

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

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

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

4.1.2. Сглаживание помех

Идея сглаживания [132, 102], примененная в § 3.6 к решению

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

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

(4.1.7)

позволяет избавиться не только от

локальных экстремумов, но и от случайных помех.

Для исследования сглаживания помех представим сглаженную

функцию (4.1.7), как и в § 3.6, в виде суммы, полученной методом

Монте-Карло:

(4.1.8)

где Y

— случайные реализации вектора Y

в соответствии с его заданной плотностью распределения ρ(Y).

Подставив в сумму (4.1.8) выражение (4.1.1), получим:

(4.1.9)

Легко видеть, что

случайная составляющая сглаженной функции (4.1.9) имеет

пониженную дисперсию:

(4.1.10)

Пусть распределение р(٠) конечно и его

границы достаточно близки. В этом случае Q(U+Y

) можно

представить в виде линейной формы по Y:

(4.1.11)

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

(4.1.12)

где

(4.1.13)

Отсюда вытекает, что

при центрированном распределении р(•), т. е. при М(Y) = 0,

(4.1.14)

Это означает, что оценка (4.1.8) состоятельна

(разумеется, в случае справедливости линейного представления

(4.1.11)). Указанное обстоятельство обеспечивает фильтруемость

случайной помехи при использовании оператора сглаживания (4.1.7).

Аналитическая форма задания плотности распределения р(•) дает

возможность [166] оценить градиент «зашумленной» функции (4.1.1).

Для этого достаточно продифференцировать (4.1.7) по U. Представим

(4.1.7) в виде

(4.1.15)

где Z = U + Y. Теперь операция

вычисления градиента сглажен-

ной функции осуществляется

очень просто:

4.1.16) где — градиент по вектору U:

(4.1.17)

Производные

(4.1.18)

образующие компоненты

вектора градиента, вычисляются аналитически. При вычислении

интеграла (4.1.16) естественно также воспользоваться методом Монте-

Карло. Для этого запишем (4.1.16) в виде

(4.1.19)