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

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

годом становится все острее. Число возникающих многоэкстре-

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

проектирования [21, 156, 209].

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

сделать тщательный анализ возникшей оптимизационной задачи и

заставляет свалить ее решение на «железные» плечи ЭВМ,

работающей по алгоритму глобального поиска.

Если относительно локального поиска еще высказывается порой

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

глобального поиска, пожалуй, все единодушны: он должен быть

стохастическим. Рассмотрим основные алгоритмы глобального

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

3.6.1. «Набросовые» алгоритмы

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

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

распределения пробных состояний объекта.

3.6.1.1. Случайный наброс с локальным поиском

На каждом i-м этапе из случайной начальной точки U

делается

локальный спуск в ближайший минимум U

* любым локальным

методом поиска. За глобальный минимум U** принимается тот, для

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

(3.6.1)

Очевидно, что при N→∞ вероятность .того,

что U**

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

единице, т. е.

(3.6.2)

При конечном N вероятность утери

глобального экстремума, т. е. U**

≠ U**, не равна нулю.

Однако использование локального поиска совершенно необя-

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

локальному поиску. Рассмотрим другие алгоритмы.

3.6.1.2. Адаптивный набросовый алгоритм

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

распределения наброса. Пусть p (U | W, σ) — плотность распреде-

ления, параметры которого определяются вектором W, равным,

математическому ожиданию случайного вектора U:

W = ∫ U

(U | W, σ) dU, (3.6.3)

и σ — некоторой скалярной мерой рассеяния этого распределения

(типа среднеквадратичного отклонения), такой, что при σ = 0

распределение вырождается в δ-функцию и имеем U = W, а с

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

всем направлениям пространства {U}. Алгоритм поиска заключается в

генерировании последовательности случайных точек; U1, ..., U

, ... и

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

аналогично (3.6.1):

(3.6.4)

При этом параметры W и а распределения

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

(3.6.5)

т. е. W

является лучшей

из всех предыдущих точек, и

(3.6.6)

где параметры γ

и γ

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

В случае γ

<l и γ

>1, т. е. при расширении зоны поиска с каждой

удачей и сужении — с неудачей, получаем локализирующийся

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

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

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

ближайший локальный экстремум; если же медленно, то шансы найти

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

В случае γ ≈ 1 вероятность отыскания глобального экстремума, при

N→∞ стремится к единице (при этом еще необходимо, чтобы р (U | W,

σ) ≠ 0 для любой точки, т. е. чтобы плотность вероятности-появления

любой допустимой точки не была равна нулю).

Возможен и иной подход к выбору параметров γ

и γ

. Если логику

адаптации (3.6.6) как бы «вывернуть наизнанку», т. е. положить γ

>l, а

<1, то получим несходящуюся процедуру, которая расширяет зону

поиска при неулучшении и сужает ее

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

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

конкретных свойств объекта.

3.6.1.3. Набросовый алгоритм глобального

поиска с идентификацией

распределений

Этот интересный алгоритм связан с восстановлением (иденти-

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

функции в случайных точках U

, равномерно распределенных в

области поиска S [135]. Если область поиска произвольно разделить на

две части и в каждой определить плотность p

(Q) и p

(Q), то наиболее

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

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

минимизации) простирается дальше. Для широкого класса сложных

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

логнормальным распределением, левый «хвост» которого ограничен.

Наименьшая из оценок этих границ и решает вопрос о выборе

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

исследования. Таким образом, рассекая область поиска S

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

глобального экстремума и определить его любым локальным методом.

3.6.2. «Блуждающие» алгоритмы

Многие интересные и эффективные алгоритмы глобального лоиска

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

3.6.2.1. Метод «зашумления» градиента

Если на оценку градиента в градиентном поиске наложить

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

(3.6.7)

где σ — некоторая постоянная. Запишем этот процесс в непрерывной

форме:

(3.6.8)

где ξ(t) — случайный векторный процесс

типа белого шума с единичными дисперсиями. При σ = 0 поиск

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

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

локальный минимум, т. е. поиск имеет локальный характер. При σ ≠ 0

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

типа броуновского. В результате образуется случайный процесс [232],

распределение вероятностей которого имеет вид

(3.6.9)

где с — нормирующий коэффициент.

Из этого выражения хорошо видно, что плотность вероятности

пребывания функции Q(U) в глобальном минимуме максимальна и

чем меньше Q, тем больше эта плотность.

Процесс такого поиска происходит следующим образом. Во время

блуждания точка U попадает в локальные экстремумы функции Q(U) и

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

Q(U) в соответствующем экстремуме. Если теперь медленно

уменьшать а, то в соответствии с (3.6.9) точка U попадает в зону

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

Как видно, этот алгоритм гарантирует отыскание глобального

экстремума лишь при очень медленном уменьшении параметра σ

(строго говоря, для этого нужна нулевая скорость убывания σ). Риск

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

уменьшения σ.

3.6.2.2. Метод сглаживания

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

рис. 3.6.1, а, т. е. образована путем наложения на «хорошую»

унимодальную функцию (см. пунктир на рисунке) мелких

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

мума можно воспользоваться идеей сглаживания [103, 152, 238].

Делается это следующим образом.

В районе точки U осредним функцию Q(U) с неотрицательным

весом ρ(Y), поведение которого показано на рис. 3.6.1, б. Получаем

(3.6.10)

Эта функция уже ближе к «хорошей»,

так как здесь несколько сглажена колебательная составляющая.

Однако определить этот q-кратный интеграл очень трудно.

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

воспользоваться методом Монте-Карло, рассмотренным в § 3.1.

Действительно, весовую

функцию ρ( ٠ ) всегда можно

выбрать так, чтобы она была

многомерной плотностью, т. е.

удовлетворяла условиям

∫ ρ(Y)dY = 1; ρ(Y)≥0.

Тогда, генерируя в соответствии с

этой плотностью случайные

векторы Y

,...,Y

, можно оценить

значение интересующего нас

интеграла следующим образом:

(3.6.11)

Выражение (3.6.11) есть монте-

карловская оценка, совпадающая с (3.6.10) при N→∞ и от-

личающаяся от (3.6.10) при конечном N на случайную величину с

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

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

чтобы свойства оценки (3.6.11) были приемлемыми.

На оценку (3.6.11) можно воздействовать и путем изменения

распределения ρ(٠). Так, если дисперсии этого распределения

уменьшаются (см. пунктир на рис. 3.6.1, б), то дисперсия оценки

(3.6.11) также уменьшается, причем, естественно, ухудшается

сглаживание. Поэтому выбор ρ(٠) и N должен зависеть от свойств

минимизируемой функции Q(U) и поставленных целей. Теперь,

располагая значением оценки (3.6.11) в любой точке и зная, что

функция унимодальна, можно обратиться к

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

(3.6.12)

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

(3.6.11), что, как видно, эквивалентно оптимизации в обстановке

случайных помех.

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

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

ис. 3.6.1. Сглаживание многоэкстре-

мальной функции.

а — многоэкстремальная функция,

образованная наложением случайных

колебаний на унимодальную функцию

(пунктирная линия); б — весовая

функция.

ρ(٠). Для этого преобразуем интеграл (3.6.10) с помощью подстановки

Z = U + Y к виду

3.6.13) Градиент функции Q(U) можно определить следующим

образом:

(3.6.14)

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

градиента осуществляется

аналитически. Оценивать (3.6.14) следует также методом Монте-

Карло:

(3.6.15)

где Z

— случайные

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

плотностью p(Z) ≠ 0 для .

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

здесь используются случайные шаги Z

. Эффективная организация

поиска требует изменения ρ(٠) и N в процессе поиска, т. е. их

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

было сильным, а N — малым и чтобы по мере приближения к

глобальному экстремуму N возрастало при уменьшении сглаживания.

3.6.2.3. Метод направляющего конуса

Очень часто глобальный экстремум находится на «дне» оврага

минимизируемой функции Q(U). Под оврагом принято понимать

ситуацию, отличающуюся следующей особенностью: почти вдоль

всех направлений функция Q(U) сильно увеличивается (это «склоны»

оврага), и только в сравнительно узком конусе направлений эта

функция слабо уменьшается (это направление «дна» оврага). Если

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

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

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

На специфическом дне конуса с вершиной в U

и осью W

( | W

= 1 ) делаются k случайных проб U

N+1

(1)

, ..., U

N+1

(k)

(рис. 3.6.2).

Следующее (N+1)-e состояние определяется по наилучшей пробе:

(3.6.16)

а ось следующего конуса —

(3.6.17)

т. е. вдоль сделанного рабочего шага. Легко

видеть, что эта процедура позволяет

отслеживать направление оврага независимо

от того, вверх или вниз идет овраг.

Угол между следующими друг за другом шагами не превышает

половины угла φ раскрытия направляющего конуса. Поэтому траекто-

рия поиска при малом φ имеет очень

плавный характер. При φ=2π получаем поиск

по наилучшей пробе, рассмотренный в

подразделе 3.3.2.3. Варьируя величину угла

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

поиска [94].

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

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

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

блужданием в пространстве оптимизируемых параметров {U}.

§ 3.7. Бионические алгоритмы

случайного поиска

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

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

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

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

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

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

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

приборов.

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

технику, — это широкое использование биологических аналогий, а

иногда и аллегорий, что тоже вполне оправдано, если дает

положительный эффект. Именно в таком бионическом направлении

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

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

организации — от популяционного, связанного со свойствами

биологической эволюции, до субклеточного, где тончайшие

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

ис. 3.6.2. К образованию

рабочего шага алгоритмом

случайного поиска с на-

авляющим кон

сом.

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

Рассмотрим алгоритмы случайного поиска, моделирующие

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

[270].

3.7.1. Эволюционные алгоритмы

Использование идеи биологической эволюции для синтеза

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

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

дификациях. Вот некоторые из них.

3.7.1.1. Эволюционный алгоритм случайного поиска

Простейший алгоритм глобального поиска моделирует эволюцию

следующим образом. Пусть U

, ..., U

— произвольные точки в q-

мерном пространстве оптимизируемых параметров — моделируют

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

определяется значением минимизируемой функции Q(U). Чем меньше

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

следовательно, тем больше у нее шансов на выживание.

Пусть имеем N выживших особей. Каждая из них дает потомство,

отличающееся от родителя случайным образом. Модель такого

потомка имеет вид

= U

+ ξ

(i = 1, ..., k

), (3.7.1)

где k

— число потомков j-й особи; ξ

— случайное отклонение,

моделирующее отличие i-го потомка от j-й родительской особи в силу

случайных мутаций. Это случайный вектор, модуль которого, a

= |ξ

отражающий интенсивность мутаций, обычно не слишком велик,

чтобы в соответствии с пословицей «яблочко падало недалеко от

яблоньки».

Теперь среди потомков вступает в действие «естест-

венный отбор», при котором с большей вероятностью вымирает

потомок, имеющий большее значение минимизируемой функции.

Моделируется это следующим образом.

Пусть вероятность «вымирания» пропорциональна значению

минимизируемой функции, т. е.

(3.7.2)

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

N «выживших» потомков. Популяция сформирована и может давать

потомство для следующего этапа отбора.

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

) позволяет очень эффективно оптимизировать

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

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

«вымирает» сразу независимо от значения Q(U

) [16, 154, 155].

Описанный глобальный поиск, эксплуатирующий эту грубую

модель эволюции, привлекателен еще и тем, что может легко усо-

вершенствоваться. Например, можно ввести прижизненную адап-

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

в точку

ближайшего локального экстремума (для этого можно использовать

любой из локальных методов поиска, описанных в § 3.2 и 3.3).

Целесообразно также моделировать изменение числа потомков k

особи и интенсивности случайных мутаций в зависимости от

приспособленности особи. Так, хорошие результаты в процессе

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

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

)

возрастает, а число потомков k

уменьшается.

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

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

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

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

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

те особи, которые в большей мере обладают необходимыми

свойствами.

В практической биологии этот феномен играет огромную роль и во

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

Рассмотренный в § 3.3 (подраздел 3.3.3.1) случайный поиск с

помощью коллектива независимых автоматов с целесообразным

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

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

некоторые из них [136].

3.7.1.2. Популяционный алгоритм случайного поиска

Пусть имеется некая популяция автоматов A

, ..., A

(N>q), каждый

из которых имеет свои параметры q

, ..., q

, характеризующие его

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

Эффективность каждого i-ro автомата определяется его анкетой, или

лицевым счетом:

Si = (s

, ..., s

) (i = l, ..., N), (3.7.3)

где компоненты анкеты определяют прошлую работу автомата на

каждом канале оптимизируемого объекта следующим образом:

В процессе оптимизации выбор автомата для работы на определенном

j-м канале зависит от величин s

, ..., s

и с большей вероятностью

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

больше.

Теперь введем скрещивание. Для этого надо оценить эффек-

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

(3.7.4)

Легко заметить, что чем больше эта

величина, тем лучше работает автомат. Поэтому величина α

определяет приоритет i-ro автомата в выборе пары. Первым,

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

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

большим α (как видно, этот алгоритм моделирует механизм

образования брачных пар в животном мире). Далее по тому же

принципу выбирает себе пару автомат с меньшим значением

эффективности и т. д. Естественно вводить и «холостые» автоматы,

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

Эта вероятность должна увеличиваться с уменьшением α, моделируя

«неприспособленность» автоматов с малым α.

После образования пар происходит скрещивание, т. е. образование

автомата-потомка. В соответствии с законами наследственности он

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

берет с определенной вероятностью у одного родителя, а другие — у

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

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

образуется путем осреднения анкет родителей (это моделирует

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

особи по их родителям), и сразу включается в процесс оптимизации.

Рождение новых автоматов сопровождается «гибелью» других,

моделирующей селекцию при искусственном отборе.