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

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

где. Следующую случайную точку U

будем выбирать в

этом пространстве — например, на расстоянии а от U

n-q+1

, т. е.

| U

— U

n-q+1

| = a. (3.4.21)

Теперь задача определения U

сводится к решению системы из

двух уравнений относительно q — n + 1 параметров λ

(3.4.22)

где λ

— случайные числа, например, распределенные

равномерно в пределах —1≤λ

≤1 (i = 1, ..., q - n + 1). Полученная таким

образом (3.4.20) новая точка U'

q-n+2

может, естественно, не при-

надлежать S. В этом случае ее следует спроектировать на S любым

локальным методом — например, градиентным методом (3.3.21):

3.4.23) т. е. решить минимизационную

задачу

(3.4.24)

решение которой ∆U*

q-n+2

и дает искомую точку

q-n+2

= U'

q-n+2

+ ∆U*

q-n+2

. (3.4.25)

Варьируя распределения p

(λ

) в системе уравнений (3.4.22), можно

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

q-n+2

Теперь из q — n + 2 точек отбрасывается худшая по критерию

оптимизации, а оставшиеся q — n + 1 точки переиндексируются так,

чтобы лучшей была U

q-n+1

, и т. д.

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

точек на S

. Одним из них является способ простого проецирования на

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

Гельфанда и Цетлина [55].

3.4.4. Случай S = S

∩ S

Учет такого рода ограничений в процессах случайного поиска не

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

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

случаях.

3.4.5. Случай S = S

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

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

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

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

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

случайный выбор точки в ε-окрестности исходной. Пусть ε-окрест-

ность исходной точки U

имеет вид

| U - U

| ≤ ε (3.4.26)

и пусть для простоты множество S

образовано целочисленными

векторами U. Иначе говоря, принимаем, что все координаты векторов

U имеют целочисленные значения (более общий случай легко

сводится к этому). Пусть D

— множество целочисленных точек,

попавших в ε-окрестность, т. е. удовлетворяющих условию (3.4.26).

Например, при ε=1 таких точек будет 2n и образуются они изменением

каждой из координат U

на ± 1.

Тогда процедура случайного поиска на (N+1)-м шаге будет связана

со случайным выбором такой точки множества D

, для которой

выполняются очевидные условия

Q (U

N+1

) < Q (U

); (3.4.27)

Введем случайное целочисленное единичное смещение ξ:

N+1

= U

+ ξ. (3.4.28)

Например, для ε = 1 вектор смещения ξ будет

ξ = (ξ

, ..., ξ

), (3.4.29)

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

нулю, т. е.

(3.4.30)

Можно сделать векторы ξ не равновероятными и изменять их

вероятности в соответствии с выбранным законом самообучения —

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

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

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

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

точек, с тем чтобы не повторять проверку условий (3.4.27) в одной и

той же точке.

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

при достаточно большом ε. Легко заметить, что при ε→∞ метод

вырождается в обычный случайный перебор. Поэтому величина ε не

должна быть слишком большой и в начале поиска ξ ≈ 1.

Очевидно, что этот процесс можно варьировать в широких

пределах — например, изменять характер меры в неравенстве (3.4.26)

или адаптировать ее в процессе поиска. Большинство существующих

эффективных методов решения дискретных задач оптимизации в той

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

[109, 200]).

3.4.6. Случай S = S

∩ S

Учет ограничений типа неравенств в задаче дискретной опти-

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

этом случае к условиям (3.4.27) добавляется еще одно:

(3.4.31)

которое легко проверяется.

§ 3.5. Адаптация алгоритмов случайного поиска 3.5.1.

Анализ задачи адаптации поиска

Имеются два источника причин, вызывающих необходимость

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

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

Многочисленные ситуации, складывающиеся в процессе опти-

мизации одного и того же объекта, — типа «холм», «яма», «плос-

когорье», «хребет», «овраг» и т. д. — заставляют искать средства

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

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

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

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

эффективность такой процедуры очевидны. Это один источник

адаптации.

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

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

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

решения какой-то новой задачи, отличающейся от предыдущих.

Совершенно ясно, что такая тенденция порочна и недолговечна, в

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

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

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

пытаясь как-то приспособить их к этим задачам. Успех здесь

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

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

Как правило, ничего хорошего из такой «кустарной адаптации» не

получается. Это и заставляет создавать специальные процедуры

адаптации алгоритмов оптимизации, благодаря которым алгоритмы

могут эффективно действовать в изменяющихся условиях. Как уже

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

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

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

повысить эффективность -поиска. Более того, есть алгоритмы —

например, метод наискорейшего спуска или метод Гаусса—Зейделя,

которые вообще не имеют параметров и поэтому не могут

адаптироваться параметрически. Эти обстоятельства обусловливают

переход к адаптации структуры алгоритма.

Таким образом, задача адаптации процесса поиска ставится

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

поддерживать его эффективность на необходимом уровне.

Эта задача всегда возникает при оптимизации и адаптации

сложных объектов, для которых нельзя заранее предугадать, в

какую ситуацию попадет алгоритм поиска. Такого рода неопре-

деленность и требует введения процедуры адаптации, т. е. приспо-

собления алгоритма поиска к новой ситуации путем его целена-

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

3.5.2. Параметрическая адаптация

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

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

величина рабочего шага ∆U (см. формулы (3.3.12), (3.3.20) и (3.3.23)) и

параметры плотности распределения р(ξ) случайного шага ξ. Заметим,

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

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

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

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

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

поиска.

Рассмотрим адаптацию по каждому из указанных факторов

отдельно.

3.5.2.1. Адаптация величины рабочего шага

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

шага по мере приближения к положению экстремума U*.

Программные алгоритмы изменения рабочего шага (типа условий

Дворецкого: [237]) не учитывают складывающу-

юся в процессе оптимизации ситуацию и поэтому, как показал опыт,

неэффективны при решении практических задач.

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

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

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

шаге и увеличить — при удачном. В основе такой эвристики лежат

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

свидетельствует о том, что цель где-то близко и искать ее следует

более мелкими шагами, а удачный — о том, что до цели далеко и

следует увеличить шаг. Конечно, эти соображения не более чем

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

алгоритм адаптации рабочего шага случайного поиска [184]:

(3.5.1)

где в соответствии с указанными

соображениями γ

>1, γ

<1. Элементарный анализ показывает, что при

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

экстремуму.

Зададим вопрос: какими должны быть значения γ

и γ

, чтобы как

можно, скорее попасть в точку экстремума U* или хотя бы в ее

достаточно малую окрестность? Это зависит от вероятности того, что

случайный шаг будет удачен, т. е. от вероятности события ∆Q<0. В

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

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

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

Тогда оптимальные значения γ

связаны следующим

соотношением [212]:

1-p*

= l, (3.5.2)

где величина р* с ростом п стремится к 0,27. Используя это вы-

ражение, можно добиться оптимального режима адаптации алго-

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

тимизации.

Однако условие (3.5.2) получено теоретически для довольно

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

мизации это соотношение иное и различно для каждого кон-

кретного объекта. Очевидно, что необходимо определять параметры

и γ

не заранее, а в процессе поиска, т. е. надо их адаптировать.

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

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

идеи. Ясно одно: без решения этой задачи не может быть

эффективной адаптации величины рабочего шага при оптимизации

достаточно сложных систем.

3.5.2.2. Адаптация распределения случайного шага

Этот вид адаптации заключается в том, что получаемая на

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

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

шага, при которой эффективность процесса поиска возрастает.

Пусть р(ξ) — плотность распределения случайного шага ξ.

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

математическое ожидание Мξ. Изменяя Мξ, можно эффективно

воздействовать на процесс поиска. Практически это сведется к

прибавлению вектора W к ξ

— случайному вектору с нулевым

математическим ожиданием:

ξ = ξ

+ W, . (3.5.3)

откуда получаем Мξ =W.

Вектор W, как видно, определяет «снос» случайного блуждания в

процессе поиска. Естественно, что этот снос должен быть направлен в

сторону цели, т. е. искомого положения экстремума U*. Вектор W

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

перспективное направление движения при оптимизации.

Деформация распределения р(ξ) представлена на рис. 3.5.1.

Исходное равномерное по всем направлениям распределение слу-

чайного вектора (рис. 3.5.1, а) взаимодействует по (3.5.3) с вектором

памяти W (рис. 3.5.1, б), в результате чего полученное распределение

р(ξ) имеет явную тенденцию (снос) в сторону W (рис. 3.5.1, в). Как

видно, все сводится к разумной организации вектора W и его

оперативному изменению.

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

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

причем удачные шаги (∆Q<0) следует брать с положительными

весами, а неудачные — с отрицательными. Предпочтение должно

отдаваться более свежей информации. Эта эвристика реализу-

ется, например, такой простой рекуррентной формулой измене-

ния W в процессе поиска:

= kW

N-1

— δ∆U

∆Q

, (3.5.4)

где 0≤k≤l — коэффициент забывания, а δ>0 — коэффициент

интенсивности учета новой информации. Это и есть алгоритм

адаптации распределения.

Легко показать, что такая организация изменения W отражает

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

смотрим крайние случаи. При отсутствии новой информации,

т. е. при ∆U

= 0, в силу k<1 вектор W

→0, т. е. поиск становится

равновероятным, что естественно в данных условиях. Если

«забыть» всю предысторию (k=0), то W

N+1

= —δ∆U

∆Q

, т. е. снос

будет происходить либо в направлении предыдущего удачного

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

разумно.

В общем случае взаимодействие векторов W

и ∆U

будет таким,

что при удаче W

N+1

будет разворачиваться в сторону удачного шага, а

при неудаче — в сторону, противоположную неудачному.

Можно показать, что в неизменной ситуации направление век-

тора W будет стремиться к антиградиенту, т. е. в сторону наиболее

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

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

3.5.2).

Как видно, вектор W интегрально отражает предысторию поиска,

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

поиск, снабженный адаптацией вероятностных свойств,

обладает, как правило, повышенным быстродействием.

ис. 3.5.1. Образование плотности распределения случайного

шага со сносом.

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

вектора сноса со случайным вектором, в — результирующее

асп

еделение со сносом.

Рис. 3.5.2. Корреляция вектора предыстории при удачном

(а) и неудачном (б) шагах поиска, а — ∆Q<0, б — ∆Q>0.

Чтобы такая адаптация была успешной, ситуация, которая скла-

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

быстро, иначе она станет «неуловимой» для адаптации. Поэтому

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

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

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

(а), забывания (k) и запоминания (δ) взаимосвязаны и для

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

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

задача адаптации параметров адаптации, т. е. адаптация

следующего уровня. Плодотворных подходов к ее решению пока нет,

но совершенно ясно, что ее необходимо решать, т. е. нужно построить

алгоритм изменения параметров k и δ, с тем чтобы процесс

оптимизации протекал наилучшим образом.

Более полное изложение методов параметрической адаптации

случайного поиска имеется в монографии [135].

3.5.3. Структурная адаптация алгоритмов поиска

Адаптация структуры алгоритмов поисковой оптимизации в

соответствии с общей классификацией (см. рис. 1.5.2) может осу-

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

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

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

образом.

Пусть

} (i = l, ..., q) (3.5.5)

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

линейная комбинация

(3.5.6)

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

, ..., u

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

различной

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

структуру всех алгоритмов F=F

(i=1, ..., q). Кроме того, снимая

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

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

алгоритма поиска в виде графа. Для этого достаточно воспользоваться

автоматной моделью, аналогичной (3.3.28):

‹ {∆Q}, {W}, {∆U}, µ (∆Q, W), υ (∆Q, W) ›, (3.5.7)

где {∆Q} — конечный алфавит входов автомата поиска (это

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

вызванных воздействием ∆U автомата поиска); {W} — конечный

алфавит внутренних состояний автомата; {∆U} — конечный алфавит

выходов автомата (это множество изменений входа объекта U); µ —

функция перехода:

W'= µ (∆Q, W), (3.5.8)

определяющая новое состояние W' автомата, в которое он переходит

из состояния W при входе ∆Q; υ — функция выхода:

∆U = υ (∆Q, W), (3.5.9)

определяющая выход автомата в зависимости от его состояния W и

входа ∆Q.

Граф этого автомата определяется следующим образом. Мно-

жество вершин графа образуется состояниями {W} автомата, а его

ребра определяются функцией перехода µ.

Эволюционная адаптация такого алгоритма сводится к эволюции

графа, которая будет рассмотрена в § 6.1. Здесь функция выхода υ

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

значения шагов поиска {∆U}.

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

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

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

главе. Там же (§ 5.3) будет исследовано применение методов

альтернативной адаптации для адаптации алго-

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

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

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

сопровождаться подстройкой параметров алгоритма, т. е. пара-

метрической адаптацией. Однако, так как не могут работать од-

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

— работающий. Поэтому в новой ситуации новый включающийся

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

малоэффективным. Здесь возникает важная проблема: как

адаптировать «безработные» алгоритмы по наблюдениям за одним

работающим? В этом направлении, от развития которого почти

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

еще очень мало.

В заключение отметим, что проблема адаптации алгоритмов

поисковой оптимизации является сейчас наиболее острой в оп-

тимизации. Разработано много методов поиска, а их адаптация к

конкретному объекту оптимизации пока находится на полукустарном

уровне.

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

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

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

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

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

речивые задачи: нужно искать каждый конкретный минимум и

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

Эта двойственность глобального поиска отражается и на затратах,

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

Другой специфической чертой глобального поиска является

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

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

глобальный экстремум может, вообще говоря, оказаться в любой точке

области 5 поиска, всегда существует риск утери этого экстремума в

процессе поиска. И лишь при неограниченном увеличении времени

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

Это неизбежное обстоятельство породило несколько пессими-

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

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

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

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

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

чего проблема глобального поиска с каждым