Метод Монте-Карло в параллельной программе минимизации

Иванов А.Г.¹

Рассматривается задача минимизации скалярной функции многих переменных:

f(x1, x2, ... xn) → min.

При этом предполагается что значение функции f(·) вычисляется не по явным формулам, а является результатом счета некоторой подпрограммы. Для поиска минимума такой функции имеет смысл применять методы прямого поиска (производные функции не доступны для прямого вычисления, а при численном вычислении производных мы получаем одну из разновидностей метода прямого поиска).

В качестве основы для параллельного алгоритма был взят метод Хука-Дживса [1]. Метод состоит из последовательности шагов исследующего поиска по базовой точке и шагов поиска по образцу. Алгоритм метода является существенно последовательным: координаты каждой последующей точки становятся известными только после получения значения текущей точки. Для распараллеливания был изменен алгоритм поиска вокруг базовой точки. Разработано три варианта алгоритма различающиеся степенью перебора.

Алгоритм 1 ближе остальных к исходному алгоритму Хука-Дживса: в нем варьируются координаты базовой точки по координатным осям, число вычисляемых точек при однократном поиске вокруг базовой точки равно 2n (в оригинальном методе от n до 2n), где n -- размерность минимизируемой функции. В этом методе поиск по образцу совпадает с алгоритмом поиска вокруг базовой точки.

Алгоритм 2 отличается большей степенью перебора: перебираются вершины гиперкуба с центром в базовой точке, число точек при однократном поиске равно 2ⁿ. Поиск по образцу в этом алгоритме совпадает с поиском по образцу в оригинальном методе Хука-Дживса и не распараллеливался.

Алгоритм 3 реализует огромный перебор: перебираются вершины гиперкуба и середины всех его граней меньших размерностей, число точек равно 3ⁿ - 1. Поиск по образцу, как и в алгоритме 2, совпадает с оригинальным.

Подробно алгоритм распараллеливания и результаты изложены в [2].

В конце поиска вокруг базовой точки существует момент, когда задача-мастер простаивает в ожидании прихода результатов от рабочих. В этот момент удобно ввести в алгоритм элементы метода Монте-Карло: вычисление случайной точки и обработка результатов счета наравне с другими точками (см. [2]).

Рассматривались различные варианты вычисления случайной точки. В результате численных экспериментов был выбран следующий вариант: случайная точка генерируется на границе гиперкуба, окружающего базовую точку, вычисление случайных точек прекращается, когда большинство рабочих уже вернули результаты.

Результаты сравнения времени счета тестовой задачи на десяти процессорах для исходного алгоритма (норма) и для алгоритма с элементами метода Монте-Карло (MMK12) приведены в таблице

Параметры: N - число запусков, T_ср -- среднее время счета, T_min, T_max -- минимальное и максимальное времена счета, σ -- среднеквадратичное отклонение.

Литература

PostScript-версия публикации (67K)