Поиск глобального минимума кривой с помощью стохастических автоматов

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

Под автоматом будем понимать динамическую систему, которая в дискретные моменты времени r = 1, 2 ,3, …, воспринимая на входе сигнал у(r), изменяет свое внутреннее состояние S (r) согласно уравнению:

S(r) = φ1[у(r), S (r — 1)] S(0) = S0. (4.75)

Каждое состояние автомата S(r) определяет некоторое действие, характеризуемое переменной х(r) на его выходе;

x(r) = φ2[S(r)]. (4.76)

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

Si(r), i = 1, 2, …, М,

и каждому из них соответствует только одно определяемое из (4.76) значение переменной xi(r).

Пусть автомат функционирует во внешней среде, реагирующей на его действия случайным образом, т. е. входная переменная автомата (вход) в момент r является случайной функцией его выхода в предыдущий момент:

y(r) = φ3[x(r — 1)]. (4.77)

Будем считать, что переменная у(r) принимает только два значения: у(r) = 1, соответствующее классу благоприятных реакций среды (выигрыш), и у (r) = 0, соответствующее классу неблагоприятных реакций среды (штраф). Тогда уравнение (4.75) можно задать с помощью двух матриц переходных вероятностей ||pij(1)|| и ||pij(0)||, которые определяют смену состояния автомата под воздействием реакции среды у(r). Если вероятности рij перехода автомата из состояния i в состояние под воздействием реакции среды у(r) удовлетворяют условиям:

0 ≤ pij ≤ 1, i, j = 1, 2, …, M; ∑pi = 1: i = 1, 2, …, М, (4.78)

то автомат называется стохастическим (вероятностным) автоматом. Стохастический автомат, который в период между сменой состояний изменяет свои матрицы переходных вероятностей так, чтобы они сохраняли свойство стохастичности (4.78), называется вероятностным автоматом в переменной (формируемой) структурой. Меняя свою структуру, стохастический автомат в некотором смысле может приспосабливаться к той среде, в которой он функционирует. Говорят, что автомат с переменной структурой обладает целесообразным поведением, если математическое ожидание выигрышей у него больше, чем математическое ожидание выигрышей у автомата, который выбирает свои действия равновероятно и независимо от реакции среды. Автомат с целесообразным поведением, который в процессе функционирования добивается максимального значения математического ожидания выигрышей, называется асимптотически-оптимальным автоматом, т. е. такой автомат при r → ∞ производит всегда то действие xi(r), при котором вероятность выигрыша максимальна:

lim pi(r) =1; lim pj(r) = 0, j = 1, 2, …, М, j ≠ i. (4.79)

Введем следующую интерпретацию характеристик стохастического автомата с переменной структурой, соответствующую понятиям задачи поисковой оптимизации. Разобьем интервал [а, b], на котором определена минимизируемая функция Q(х), на М подынтервалов равной ширины ω = (b — a)/M. Каждому подынтервалу, который характеризуется точкой

xi = ω(i — 1/2), i = 1, 2, …, М, (4.80)

поставим в соответствие единственное состояние автомата Si, i = 1, 2, …, М. Тогда на r-м шаге поиска состоянию S(r) = Si будет соответствовать выход автомата xi(r), принадлежащий подынтервалу

xi — ω/2 ≤ xi(r) ≤ xi + ω/2. (4.81)

В момент r состоянию Si(r) соответствует только один конкретный выход автомата xi(r), который выбирается из подынтервала (4.81) либо случайным образом по разновероятному закону распределения вероятностей f = 1/ω, либо при помощи одного из методов унимодального поиска. В последнем случае всякий раз, когда надо провести испытание в подынтервале [xi — ω/2, xi — ω/2], точка xi(r) выбирается пo стратегии унимодального поиска с учетом информации о уже проведенных в данном подынтервале испытаниях. Состояние Si, 1 = 1,2, …, М, на r-м шаге поиска характеризуется распределением вероятностей:

pi(r) > 0, i = 1, 2, …, М; ∑pi(r) = 1,

согласно которому выбирается очередное состояние S(r + 1) на последующем шаге. В начале поиска, когда отсутствует априорная информация о форме кривой Q(x), эти вероятности считаются одинаковыми:

рi(0) = 1/M, f = 1, 2, …, М.

Средой, в которой функционирует автомат, является произвольная кривая Q (х), которая реагирует на действия xi(r — 1) следующим образом:

y(r) = 1, если Q(xi(r — 1)) ≤ Q* (выигрыш);
y(r) = 0, если Q(xi(r — 1)) > Q* (штраф).

Здесь

Q*= min Qj*; Qj*= min [AQ(xj(r — 1))];

A — положительное большое число (например, верхняя оценка для значений функции Q (х));

Q (xj (r — 1)) — наименьшее из значений функции Q (х), полученное на предыдущих шагах поиска в подынтервале с внутренней точкой

xj = ω(j — 1/2).

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

р(r + 1) = Tр(r); ∑pi(r + 1) = 1,(4.83)

чтобы состояние Sk, соответствующее подынтервалу [xk — ω/2, xk + ω/2], который содержит точку глобального минимума х*, имело максимальное значение вероятности:

рk(r+1)= max Pi(r + 1). (4.84)

Выполнение условия (4.84) обеспечивает асимптотически-оптимальное поведение автомата, заключающееся в том, что с заданной точностью ε выполняется система неравенств:

|Pk(r) — 1| ≤ ε, если Q(хk(r)) < Q (xj(r));
pj(r) ≤ ε для всех j = 1, 2, …, М, j ≠ k. (4.85)

Менее сильное свойство рассмотренного автомата — этo его целесообразное поведение, которое при r → ∞ характеризуется следующим условием:

pk(r) > pj(r), если Q(хk(r)) < Q(хj(r)), (4.86) j = 1,2, …, j ≠ k.

Условия (4.85) и (4.86) могут быть использованы в качестве условий окончания поиска точки глобального минимума х* с помощью вероятностных автоматов.

Конкретный тип алгоритма данного класса зависит от процедуры T преобразования вектора вероятностей p(r) на каждом шаге поиска, т. е. от способа формирования структуры вероятностного автомата.

Рассмотрим алгоритм F20, в котором изменение вектора вероятностей p(r) связано о линейной моделью автомата Буша — Моотеллера;

p(r + 1) = Tр(r). (4.87)

Здесь T = λТ — (1 — λ)A(r) — матрица ||tjj||, реализующая преобразование Буша — Мостеллера; I — единичная матрица; λ — постоянная величина, определяющая размер шага поиска (0 ≤ λ ≤ 1); А (r) = [Λ(r), Λ(r), …, Λ(r)] — матрица одинаковых столбцов; Λ(r) — вектор, который определяет структуру автомата и вычисляется на каждом шаге поиска.

При выигрыше вероятности выбора состояний Sj, j = 1, …, М, перераспределяются таким образом, чтобы увеличить вероятность появления r-го состояния и уменьшить вероятность остальных состояний. При штрафе вероятности выбора состояний Sj, j = 1, 2, …, М, остаются без изменения.


Комментарии запрещены.





Статистика

Рейтинг@Mail.ru