Автоматная оптимизация

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

Каждый интервал [0, ci] изменения i-й переменной разделим на Ki отрезков равной длины

ωi = ci/Ki, i =1, 2, …, n. (6.35)

Этим самым n-мерный параллелепипед Dx = {х|, 0 ≤ xi ≤ ci, i = 1, …, n} разобьется, на

M = ∏Ki

подобластей одинакового объема

Vi = ∏ωi, l = 1, 2, …, М. (6.36)

Каждую подобласть Vi будем характеризовать центральной точкой xl с компонентами

xij = ωi(j — 1/2), i = 1, 2, …, n; j = 1, 2, …, Ki. (6.37)

Индекс l для вектора xl определяется с помощью следующего выражения:

l = j(x1j) + ∑({j(xrj — 1} ∏Kt), (6.37)

где j(x1j) — верхний индекс компоненты x2j, i = 1, 2, …, n.

Например, для двумерного случая со значениями K1 = 3 и К2 = 2 нумерация подобластей Vl определяется по формуле (рис. 6.8, а):

l = j(x1j) + [j(x2j) — 1],



Рис. 6.8. Нумерация подобластей Vl, полученная при разбиении параллелепипеда D на области одинакового объема для n=2 (а) и n=3 (б).

а для трехмерного случая K1 = 3 и K2 = K3 = 2 — по формуле (рис. 6.8, б):

l = j(x1j) + [j(х2j) — 1]3 + [j(x3j) — 1]6.

Полученное разбиение параллелепипеда Dx дает возможность поставить в соответствие каждой подобласти одинакового объема Vl состояние S(r) стохастического автомата и вероятность рl(r) выбора им на r-м шаге 1-й подобласти для проведения в ней очередного испытания x(r). Структура стохастического автомата изменяется после каждой итерации согласно соотношениям, рассмотренным в посте про поиск глобального минимума кривой с помощью стохастических автоматов;

pl(r+1) = zl*(r+1)/(∑zi*(r+1)), l = 1, 2, …, M;
zk*(r+1) = αzk*(r) + (1 — α)zk(r+1), 0 < α < 1; zj*(r+1) = αzj*(r), j = 1, 2, …, M, j ≠ k;
zk(r+1) = [1/Q(x'(r+1))]γ, (6.38)

где k — номер k-й подобласти объемом Vk, в которой на (r + 1)-м шаге было проведено испытание; Q(x'(r + 1)) — значение минимизируемой функции, вычисленное на (r + 1)-м шаге в точке х'(r + 1), которая принадлежит «исследуемой к-й подобласти.

Испытание в k-й подобласти осуществляется в точке х'(r + 1)∈Vk, компоненты которой выбираются по равновероятному закону распределения f = 1/ωk из подынтервала

хij(k) — ωi/2 ≤ xi‘(r + 1) ≤ хij(k) + ωi/2, k= 1, 2, …, n,

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

Выбор точки х'(r + 1)∈Vk может быть также проведен с помощью одного из методов унимодального поиска минимума многопараметрической функции Q (х). При этом в k-й подобласти делается столько итераций локального алгоритма, сколько раз она выбирается для проведения очередного испытания х(r + 1).

В связи с тем, что согласно (6.38) вероятности выбора состояний автомата Si(r), i = 1, 2, …, М, являются функциями выборочных средних zi*(r), начальные значения последних zi*(0), i = 1, 2, …, М, во многом определяют скорость и надежность поиска точки глобального минимума x* многопараметрической функции Q (х). Большие начальные значения zi*(0) замедляют процесс поиска, так как текущее значение zk(r + 1) может оказаться очень малым по сравнению со значением zk*(г + 1). Но в то же время назначение больших значений zi*(0) приводит к тому, что в процессе поиска испытания проводятся в большем числе различных подобластей, тем самым повышая вероятность локализации точки глобального минимума. Малые начальные значения zi*(0) повышают скорость поиска, но могут привести к неправильному определению подобласти, содержащей точку глобального минимума х*. Поэтому в качестве начальных значений zi(xi) можно рекомендовать значения zii), вычисленные в центральных точках xi каждой из подобластей объемом Vi:

zi*(0) = [1/Q(xi)]γ, i=1,2,…,M.

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

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

1. Для каждой переменной xi задается число равных отрезков Ki, на которое разбивается интервал [0, ci] и вычисляются параметры

ωi = ci/Ki i = 1,2, …, n.

2. Определяются число подобластей, на которые разбивается область Dx = {х|0 ≤ xi ≤ ci, i = 1, 2, …, n},

M = ∏Ki

и координаты центральных точек хl для каждой подобласти Vl, l = 1, 2, …, M:

xij = ωi(j — 1/2), i = 1, 2, …, n; j = 1, 2, …, Ki.

3. В центральных точках хl каждой подобласти Vl, где номер подобласти определяется по формуле

l = j(x1j) + ∑({j(xrj — 1}∏Kt),

вычисляется

zl(0) = [1/Q(xl)]γ, l = 1, 2, …, M.

4. Вычисляется начальное распределение вероятностей выбора
состояний стохастического автомата

pl (0) = zl*(0)/∑zk*(0), l = 1, 2, …, М.

5. Интервал [0, 1] разбивается на М отрезков, длина каждого из которых пропорциональна вероятности рi(r), l= 1,2, …, М (на первой итерации r = 0). По равновероятному закону выбирается число ξ∈[0, 1]. Подобласть Vk, в которой необходимо провести очередное испытание на (r + 1)-й итерации, соответствует номеру k-го подынтервала единичного отрезка, содержащего, число ξ.

6. По номеру к определяются вторые индексы ji(k) центральной точки xk подобласти Vk и проводится вычисление функции Q (х) в точке х'(k), каждая компонента которой выбирается по равновероятному закону распределения f= 1/ωi.

7. Пересчитьшаются, вероятности выбора состояний стохастичес-
кого автомата.

8. Поиск точки глобального минимума х* заканчивается, если вы-
полняется условие

max pl(r + 1) > p0,

где p0 — заданное положительное число (0 < p0 ≤ 1). В противном случае принимается r = r + 1 и все вычисления повторяются с п. 5.


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





Статистика

Рейтинг@Mail.ru