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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Здесь

Q*= min Q_j*; Q_j*= min [A_∞Q(x_j(r — 1))];

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

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

x_j = ω(j — 1/2).

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

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

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

р_k(r+1)= max P_i(r + 1). (4.84)

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

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

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

p_k(r) > p_j(r), если Q(х_k(r)) < Q(х_j(r)), (4.86) j = 1,2, …, j ≠ k.

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

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

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

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

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

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

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