Автомат Буша-Мостеллера

Стратегия поиска точки глобального минимума х* по алгоритму F20*с помощью автомата Буша—Мостеллера сводится к следующей последовательности действий.

1. Задаются одинаковые значения вероятностей выбора состояний автомата pj(r) = 1/М, j = 1,2, …, М, и принимается Qj* = A для всех j = 1, 2, …, М, где A — положительное большое число.

2. Согласно распределению вероятностей р (r) генерируется случайное состояние автомата S (к) = Si, для которого из подынтервала [xi — ω/2, xi + ω/2] выбирается (по одному из методов одномерного поиска F1 — F6 или случайно по равновероятному закону распределения f = 1/ω) значение выхода х (r) = xi (r).

3. В точке xi (r) проводится испытание Qi = Q (xi (r)) и вычисляется параметр Q* = min Qj*.

4. Определяется реакция среды на действие автомата xi(r):

y(r+1) = 1, если Qi ≤ Q*
y(r+1) = 0 — в противном случае.

5. Принимается Qi* = min (Qi*, Q (xi (r))).

6. Если у (r + 1) = 1, то принимается Λi(r) = 1 и Λj(r) = 0, j= 1, 2, …, M, j ≠ i. При у(r + 1) = 0 значения Λj(r) = pj(r), j = 1, 2, …, М.

7. Формируется новая структура стохастического автомата путем изменения вероятностей выбора состояний Sj, j = 1, 2, …, М:

р(r + 1) = λIр(r) + (1 — λ)(Λ(r) Λ (r) … Λ (r)) р(r), где 0 ≤ λ ≤ 1

8. Все действия повторяются в п. 2 до тех пор, пока о заданной точностью не выполнятся условия целесообразного (4.86) или асимптотически оптимального (4.85) поведения.

В качестве примера на рис. 4.10 приведены гистограммы вероятностей появления выходов автомата pi(r), i = 1, 2, …. 6, полученные после 25 и 100 шагов поиска, а на рис. 4.11 графики изменения вероятностей p1(r), р3(r) и р6(r) от числа r шагов поиска точки глобального минимума х* функции Q (x) = x/10 + cos x, 2 ≤ x ≤ 11.



Рис. 4.10. Гистограмма вероятностей появления выходов автомата при минимизации функции Q(x) = x/10 + cos x после r = 0,25 и 100 шагов поиска

Из рис. 4.11 видно, что вероятность p1(r), которая характеризует подынтервал [0, 2], содержащий точку x*, стремится к единице, а все остальные вероятности pj(r), j = 2, …, 6, приближаются к нулю.



Рис. 4.11. Зависимости вероятностей выбора первого (p1), третьего (р3) и шестого (р6) состояний, автомата Буша—Мостеллера от числа шагов поиска r при минимизации функции Q(x) = x/10 + cos x;

Другой подход К формированию структуры стохастического автомата связан с преобразованием его вектора вероятностей выбора состояний р (r) по информации о средних значениях минимизируемой функции.

В связи с тем, что испытание xi(r) может быть проведено в любой точке подынтервала [xi — ω/2, xi + ω/2], предположим, что истинное минимальное значение Qi*, характеризующее i-й подынтервал, определяется с некоторой случайной ошибкой ε, которая имеет нулевое среднее значение (М(ξ) = 0) и конечную дисперсию (D{ξ} ≠ 0):

Q(xi(r)) = Qi* + ξ. (4.88)

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

zi(r)= 1/[Qi(r)]γ, (4.89)

где Qi(r) = Q(хi(r)) — значение функции Q (х), полученное в момент r для выхода автоматах x(r) = xj(r); γ ≥ 1 — параметр, определяющий надежность локализации точки глобального минимума х*. При γ = 1 в силу предположения (4.88) значение zi(r) в i-м подынтервале, не содержащем точку x*, может превысить значение zj(r) в j-м подынтервале, содержащем точку х*. В то же время выбор значения параметра γ больше единицы приводит к возрастанию обратной величины zj(r) в j-м подынтервале на большую величину, чем в i-м подынтервале.

Например, пусть Q(xi(r)) = 1, 0, а Q(хj(r)) = 1,1. Тогда при γ = 1 имеем Δr = zj(r) — zi(r) = 0, 1, а при γ = 16 — Δz = 0,53. Очевидно, что для равновероятных ошибок ξ наилучшей оценкой после проведения k испытаний в i-м подынтервале будет среднее арифметическое значение, которое, учитывая (4.88), можно записать так

M{Q(xi(r))} = Qi* + 1/k ∑ ξ(r).

Действительно, так как при r → ∞ математическое ожидание ошибки М{ξ} = 1/k ∑ ξ(r) стремится к нулю, то M{Q (хi(r))} будет стремиться к истинному минимальному значению Q*. Поэтому в дальнейшем для каждого k-гo испытания, проводимого в t-м подынтервале, будем оценивать среднее значение функции (4.89):

zi*(k) = 1/k ∑zi(r). (4.90)

где к — общее число испытаний, проведенных в i-м подынтервале. Из уравнения (4.90) видно, что с ростом числа испытаний к влияние новой информации zi(k) падает, поскольку вес ее по сравнению о более ранними испытаниями убывает.

В процессе поиска точки глобального минимума х* среда (минимизируемая функция Q(x)) на каждом r-м шаге воздействует на автомат значением zi(r), изменяя его структуру путем перераспределения вероятностей выбора состояния автомата

pj (r+1) = zj(r+1)/∑zk(r+1), j=1,2,…, M

Рассмотренная модель стохастического автомата обладает асимптотически-оптимальным поведением, если в процессе поиска средние значения zk(r) вычисляются правильно для каждого из подынтервалов [xi — ω/2, xi + ω/2]. Это требование можно выполнить за счет соответствующего выбора значения параметра γ.


Оставить комментарий





Статистика

Рейтинг@Mail.ru