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

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

Если в качестве ξ

взять орты, т. е. ξ

= е

, то эта оценка при т = п,

как легко заметить из (3.3.22), дает точное значение градиента.

Обе описанные оценки градиента могут эффективно приме-

няться при любых значениях т, в том .числе и при т<п, что

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

вания (3.3.22), для которого строго т = п. Это же обстоятельство

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

чайными (см. конец подраздела 3.3.1). Приведем еще пример такого

обобщения.

Градиентный поиск (3.3.21) является частным случаем по крайней

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

где ξ — по-прежнему единичный случайный q-мерный вектор. Это

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

Второй алгоритм имеет вид (3.3.23), но оценка градиента вы-

числяется по формуле

При l=0, как легко заметить, оба алгоритма вырождаются. в

градиентный алгоритм поиска (3.3.21).

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

ширением, продолжением и обобщением известных регулярных

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

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

широкие возможности для его эффективного применения, явля-

ется использование оператора случайного шага ξ в качестве сто-

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

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

ров {U}.

Так, алгоритм случайного поиска с линейной тактикой (3.3.12)

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

спуска:

в которой случайный вектор ξ моделирует оценку градиента. Лю-

бопытно, что подобную «оценку» нельзя даже назвать грубой, так

как ее стохастические свойства и не напоминают свойств

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

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

более эффективен, чем алгоритм наискорейшего спуска. Здесь

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

градиента, например, по формуле (3.3.22).

Следующей особенностью случайного поиска, выгодно отлича-

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

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

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

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

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

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

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

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

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

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

особенно важно при оптимизации объектов с неизвестной структурой,

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

возможно (хотя и не ожидается) наличие нескольких экстремумов.

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

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

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

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

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

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

пользователи.

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

влекательным в первую очередь для потребителей [229]. Опыт

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

лишь «канвой», на которой пользователь в каждом конкретном

случае «вышивает узоры» новых алгоритмов, отражающих не

только его вкусы и наклонности (что нельзя не учитывать), но и

специфику оптимизируемого объекта. Последнее создает

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

алгоритм должен конструироваться «под объект». Наконец,

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

простоту его аппаратурной реализации. Это не только дает

возможность строить простые, компактные и надежные оптими-

заторы с неограниченным числом оптимизируемых параметров [183],

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

на ЭВМ [142].

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

В основе этих алгоритмов лежит понятие автомата. Рассмотрим

это понятие подробнее. Автоматом традиционно называют пятерку

A = ‹Q, W, V, µ(q,w), v(q,w)›, (3.3.28)

где Q = {q

, ..., q

} — алфавит входов; W = {w

, ..., w

} — алфавит

внутренних состояний автомата; V = {v

, ..., v

} — алфавит его

выходов; w' = µ (q, w) — функция переходов, определяющая, в какое

состояние w' переходит автомат из состояния w под действием

входного сигнала q; v = v (q, w) — функция выхода — определяет

значение выхода v автомата, находящегося в состоянии w при входе q.

Эти функции могут быть стохастическими, тогда и автомат будет

стохастическим. Если автомат находится в какой-то среде, то v

представляет собой его воздействие на среду, a q — воздействие среды

на автомат.

Представим алгоритм поиска в виде такого автомата. Средой в

этом случае является объект оптимизации, преобразующий оп-

тимизируемые параметры U в значение функции Q(U). Входом

автомата поиска является значение Q (или приращение ∆Q), а выходом

будет U (или шаг ∆U).

Введем следующие упрощающие условия:

1. Автомат поиска ∆U = F(U) декомпозируется на q автома

тов ∆u

= F

(U) (i = 1, ..., q), каждый из которых воздействует

на один оптимизируемый параметр

i, N+1

= u

+ ∆u

i, N+1

. (3.3.29)

2. Алфавит входов автомата поиска имеет лишь два (k = 2)

знака:

Q={q

, q

где q

= 0 («нештраф») соответствует ∆Q < 0, a q

= 1 («штраф»)

соответствует ∆Q≥O.

3. Алфавит выходов также имеет два знака:

= {v

, v

где v

= a

> 0 и v

= —a

, т. е. каждый автомат делает шаг величиной

в одну или другую сторону. Пусть для простоты a

= 1

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

алгоритм случайного поиска задается видом функций µ и v. Здесь

целесообразно, различать два варианта:

1) µ — стохастическая функция, v — детерминированная;

2) µ — детерминированная функция, v — стохастическая.

Первый случай соответствует направлению оптимизации с

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

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

[181]. Рассмотрим каждое направление отдельно.

3.3.3.1. Коллектив оптимизирующих автоматов

с целесообразным поведением [140, 141]

Такой . коллектив автоматов характеризуется следующими

функциями.

Функция выхода v определяется простым выражением

(3.3.30)

Значит, в первых m/2

состояниях автомата (т четное) выход автомата поиска равен v

1 (значение соответствующего оптимизируемого параметра

уменьшается), а в остальных v

=1 (оптимизируемый параметр

увеличивается).

Функция переходов µ(q, w) в этом случае является стохастической

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

(3.3.31)

Эти матрицы

определяют вероятность р

переходов из одного состояния w

другое w

при той или иной реакции на рабочий шаг. Обычно

матрицы диагональны, т. е. граф переходов имеет вид,

показанный на рис. 3.3.9. Здесь значения вероятностей р > 1/2 и q > 1/2

однозначно определяют матрицы. Как видно, при ∆Q < 0, т. е. в случае

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

удаче, и наоборот, при ∆Q ≥ 0 он стремится к смене неудачного

действия на обратное. Таково свойство обоих графов на рис. 3.3.9

при р, q > 1/2.

Естественно возникает мысль: а не лучше ли сделать

автомат детерминированным, т. е. положить р = q =1? Ведь тогда

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

происходить

Рис. 3.3.9. Графы поведения автоматного алгоритма случайного поиска при

удаче (а — х = 0) и неудаче (б — х = 1).

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

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

останавливается. Значит, условие

(3.3.32)

является необходимым для эффективной работы

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

случае просто невозможна.

Параметры р, q и т каждого автомата, очевидно, определяют

эффективность его работы в различных условиях. Так как нет

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

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

адаптацию (см. шестую главу настоящей книги).

3.3.3.2. Автоматный случайный поиск с самообучением [181]

Автоматный поиск с самообучением отличается тем, что

функция µ детерминированна, т. е. является регулярной

зависимостью нового состояния w' от результата х и предыдущего со-

стояния w. Ee можно представить, например, в виде двух детер-

минированных графов, показанных на рис. 3.3.10.

Функция выхода v (•,•) автомата поиска здесь случайная

и задается, как и (3.3.30), на состояниях w

(j = 1, ..., т) в виде

вероятности шага в положительном направлении:

(3.3.33)

где ψ (j) — монотонно-

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

(3.3.34)

Рис. 3.3.10. Графы алгоритма

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

мообучением при различных

ситуациях: а — ∆u

∆Q≥0, б —

∆u

∆Q<0.

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

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

организмов (опыты с мышью в лабиринте и т. п.). Более подробно

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

поведение живых существ, будут рассмотрены в §3.7.

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

ботают при оптимизации сложных объектов. Их эффективность в

одинаковых условиях одинакова. Однако коллектив оптимизи-

рующих автоматов еще имеет возможность эволюционировать (см

§3.7).

В заключение отметим, что здесь описаны лишь основные ал-

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

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

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

§ 3.4. Учет ограничений

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

Проблема многопараметрической оптимизации

(3.4.1)

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

е. связана с обязательным выполнением ограничений S, имеющих

прежде всего ресурсный характер. Разные методы решения этой

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

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

сведением условной задачи (3.4.1) к безусловной, т. е. методы типа

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

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

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

Рассмотрим поэтому методы, учитывающие и выявляющие

специфику и особенность ограничений [169].

Случайный поиск как метод решения условной задачи (3.4.1)

отличается рядом преимуществ по сравнению с детерминированными

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

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

может иметь ни один детерминированный метод решения задачи

(3.4.1).

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

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

по сравнению с регулярными методами. Именно этому посвящен

данный параграф.

Прежде всего рассмотрим различные виды ограничений. Они

могут иметь троякий характер.

3.4.1. Типы ограничений

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

функции от оптимизируемых параметров U = (u

, ..., u

: h

(U) > 0 (i = 1, ..., m), (3.4.2)

где h

(•) — заданные скалярные функции, которые удобно пред-

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

H (U) = (h

(U), ..., h

(U) ). (3.4.3)

Тогда ограничения типа неравенства (3.4.2) записываются в виде

: H (U) ≥ 0. (3.4.4)

Во-вторых, ограничения могут иметь характер равенств:

: g

(U) = 0 (j = 1,..., п<q), (3.4.5)

где g

(•) — заданные скалярные функции. Для. удобства введем

векторную функцию

G (U) = (g

(U), ..., g

(U) ), (3.4.6)

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

: G (U) = 0. (3.4.7)

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

функций от оптимизируемых параметров:

(3.4.8)

где f

(•) — заданные

функции, a f

(l)

— l-е заданное значение, которое может принимать Z-я

функция. В частном случае при. f

(U) = u

получаем

(3.4.9)

где u

(l)

— значения (например, целочисленные), которые может

принимать Z-я переменная. Введем обозначения

F (U) = ( f

(U), ..., f

(U) ). (3.4.10)

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

(3.4.11)

где D — заданное конечное множество значений,

которые может принимать векторная функция F(U).

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

различных комбинаций пересечения областей S

, S

и S

— при

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

(так, пересечение S

и S

может не иметь ни одного элемента).

Поэтому разумными комбинациями в общем случае являются лишь

две.

Первая —

S = S

∩ S

, (3.4.12)

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

программирования, а вторая —

S = S

∩ S

(3.4.13)

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

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

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

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

ограничений различного рода. Методы типа штрафных функций [225]

рассматривать не будем, хотя и при этом появление овраж-ности и

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

эффективнее и проще, чем детерминированными методами (см. § 3.6).

3.4.2. Случай S = S

Ограничения типа неравенств образуют обычно область S

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

налом о необходимости учета ограничений S. При случайном поиске

это можно осуществить множеством способов. Рассмотрим наиболее

эффективные из них.

3.4.2.1. Использование возврата

Этот способ отличается тем, что нарушение ограничений

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

качества (∆Q≥0), для чего вводится оператор воз-

Рис. 3.4.1. Графы алгоритмов поиска с линейной (а) и не-

линейной (б) тактикой: «ξ» — оператор случайного шага, «+»

— оператор «так же» (∆U

N+1

= ∆U

), «—» — оператор возврата

(∆U

N+1

= — ∆U

врата. Таким образом, в процессе поиска различаются лишь две

ситуации — удачный и неудачный шаг:

(3.4.14)

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

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

показатель качества. Неудачным шагом (β) считается такой, при

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

качества.

Реакцией на β в этом случае является возврат в предыдущее

состояние (∆U

N+1

= —∆U

). На рис. 3.4.1 показаны графы двух

алгоритмов поиска с линейной (а) и нелинейной (б) тактикой,

реализующие этот подход. Работоспособность их очевидна [302].

3.4.2.2. Использование самообучения в виде

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

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

неравенств. Пусть W — вектор памяти:

W = M (ξ), (3.4.15)

где M — знак математического ожидания, а ξ — случайный шаг. Это

означает, что плотность распределения р(ξ) случайных шагов ξ не

равномерна и имеет «снос» W. Тогда адаптация этого сноса в форме

N+1

= kw

+γδ∆U

N+1

, (3.4.16)

где 0≤k≤1 — параметр забывания, δ>0 — параметр скорости

самообучения, а γ — фактор, учитывающий удачность случайного

шага:

(3.4.17)

решает задачу учета ограничений S=S

. Как легко

заметить, формула (3.4.16) является естественным обобщением

самообучения случайного поиска (см. § 3.5) при нарушении ограни-

чений S.

3.4.2.3. Адаптация величины шага

Такая адаптация (см. также § 3.5) в алгоритме с нелинейной

тактикой (3.3.20) позволяет получить алгоритм, сходящийся при

наличии ограничений и отсутствии помех. Он имеет вид

(3.4.18)

Алгоритм адаптации

(3.4.19)

где γ

>1, γ

<1, причем γ

>l (вопрос выбора

параметров γ

и γ

рассмотрен подробно в работе [214]).

3.4.3. Случай S=S

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

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

Его можно осуществить путем воздействия на вероятностные

свойства случайного шага: организовать изменение распределе-

ния p(ξ) так, чтобы случайные шаги ξ производились преиму-

щественно в окрестности области S

, размерность которой равна q - n.

Такую задачу решает, например, следующий способ. Пусть

(i = l, ..., q - n + 1) и Q(U

)≥Q(U

i+1

). Образуем линейное

подпространство размерности q — n, натянутое на эти точки:

(3.4.20)