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


Многопроцессорные ЭВМ открывают возможность одновременной оценки нескольких независимых значений функции Q (х) путем распараллеливания вычислений. В связи с чем для минимизации унимодальных функций могут быть построены параллельные алгоритмы поиска, в которых на каждом i-м шаге часть испытаний ni ≤ N проводится одновременно в заданной совокупности точек х1, х2, …, хn.

Наиболее простыми алгоритмами данного класса являются алгоритмы, реализующие методы пассивного поиска, в которых расположение точек испытаний хi, i = 1,2,…, N, выбирается заранее до проведения первого вычисления функции Q (х):

а ≤ х1 < х2 < ... < xN-1 < хi ≤ b.

В алгоритме F7, реализующем метод равномерного поиска, испытания проводятся в точках, которые определяются путем равномерного деления априорного интервала неопределенности [a, b] на (N + 1)-у часть:

хi = а + i (b — a)/(N + 1), i = 1, 2, …, N. (3.75)

В полученных точках xi оцениваются значения функции Q (х), из которых выбирается наименьшее:

Q(xk)= min Q(xi).

В связи с унимодальностью функции Q (х) подынтервалы [а, хk-1] и [хk+1, b] исключаются, а длина апостериорного интервала неопределенности [хk-1, хk+1], содержащего точку минимума х*, определяется выражением:

lN (F7) = bN — aN = 2(b- a)/(N + 1). (3.76)

Другим вариантом стратегии пассивного поиска является алгоритм F8, реализующий метод равномерного дихотомического поиска, основная идея которого заключается в том, что испытания проводятся парами, которые при четном числе испытаний N = 2m (m ≥ 1), равномерно располагаются на интервале [а, b] согласно формулам:

x2i-1= a + i (b — a)/(m + 1), (3.77)

х2i = x2i-1 + δ, i = 1, 2, …, m,

где

0 < δ < (b — а)/(m + 1) — число, достаточное для того, чтобы различить, какая из точек в паре лучше по значению функции Q (х). После проведения m пар испытаний апостериорный интервал неопределенности определяется выражением:

lN (F8) = bN — aN = (b — a)/(0.5N+1) + δ. (3.7.8)

Недостатком методов F7 и F8 является то, что в них выбор точек испытаний xi, i = 1, 2, …, N, осуществляется без учета информации о значениях функции Q (х), вычисленных в этих точках. Этот недостаток устранен в методах блочного поиска, которые сочетают в себе пассивные и последовательные стратегии поиска. При этом N испытаний разделяются на l блоков, в каждом из которых проводится одновременно ni испытаний, т. е. блок — это совокупность из нескольких испытаний, которые проводятся одновременно. (В частном случае блок может состоять из одного испытания.) Результаты, полученные в (k — 1)-м блоке, становятся известными перед началом проведения испытаний в k-м блоке и определяют стратегию выбора точек очередных испытаний xi, i = 1, 2, …, nk, в этом блоке.

Введем следующие обозначения:

xt,j — расположение точки j-го испытания в t-м блоке (Qt,j = Q (xt,j));

xt,k — точка, обеспечивающая в t-м блоке минимальное значение функции Q (х) среди всех проведенных испытаний;

at = xt, k-1; bt = хt, k+1 — границы интервала неопределенности, которые получаются после проведения всех испытаний в t-м блоке.

Для заданного числа испытаний N рассмотрим алгоритм F9, реализующий блочную стратегию поиска, которая состоит из l блоков постоянной длины ni = n, i = 1, 2, …, l. При четном числе испытаний в блоке n = 2m (m ≥ 1) процедура поиска сводится к следующей последовательности действий.

Испытания в первом блоке (t = 1) одновременно проводятся в точках (рис. 3.10,а).



Рис.3.10 Расположение точек испытаний в алгоритме F9 при четном числе испытаний в блоке

xt, 2j = jAl-1, j = 1, 2, …, m; (3.79)
xt, 2j+1 = xt, 2j — δ. j = 0, 1, …, m-1.

Здесь Аl (n) = (n+2)/2 Al-1 (n), А0 (n) = 1 — числа Авриэла для четных n, первые несколько значений.которых для различных l и n приведены в табл. 3.3.


Таблица 3.3

Если длина априорного интервала неопределенности [а, b] не превышает числа Авриэла Аl(n), то алгоритм F9 позволяет локализовать точку минимума х* в апостериорном интервале неопределенности [аN, bN] единичной длины. Другими словами, длина апостериорного интервала неопределенности определяется выражением:

lN(F9) = bN — aN = (b — a)/Al(n). (3.84)

При l ≥ 2 и n = 1 делается последовательно l испытаний, так как алгоритм F9 состоит из l блоков, в каждом из которых проводится только одно испытание. В этом случае по формулам для чисел Авриэла можем записать

Аl(1) = Al-1 (1) + Al-2(1);
A0(1) = A1(1) = 1.

Полученные рекуррентные соотношения определяют числа Фибоначчи, следовательно, bN — aN = (b — a)/Al(l) = (b — a)/ul, т.е. алгоритм F9 совпадает с методом Фибоначчи.

При l = 1 и n ≥ 2 делается одновременно n испытаний, так как алгоритм F9 состоит из одного блока, в котором проводится n испытаний. В этом случае по формулам для чисел Авриэла можем записать

Аl(n) = (n+1)/2 для нечетных n;
Аl(n) = (n+2)/2 для нечетных n;

Из полученного выражения для апостериорного интервала неопределенности следует, что при l = 1 Для нечетных n алгоритм F9 совпадает с методом F1, а для четных n — с методом F8.

В тех случаях, когда общее число испытаний N = ln постоянно, метод Фибоначчи является более эффективным, чем метод блочного поиска F9. Это связано с тем, что при фиксированном числе испытаний в методе F2 информация о проведенных испытаниях используется полностью. В методе же блочного поиска F9 часть информации о значениях функции Qt,j, полученных при пассивном поиске внутри t-го блока, не используется при формировании стратегии поиска в (t + 1)-м блоке.

Недостатком метода F9, реализующего блочный алгоритм поиска, является то, что число блоков l в нем должно быть задано перед началом поиска. В связи с этим рассмотрим алгоритм F10, реализующий блочный метод золотого сечения, который лишен этого недостатка.


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




Статистика