Описывается алгоритм и параллельная программа поиска минимума скалярной функции многих переменных.

Алгоритм

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

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

В качестве основы для параллельного алгоритма был выбран широко известный метод Хука-Дживса [1], который хорошо себя показал в ряде практических задач. Этот метод состоит из шагов поиска вокруг базовой точки и поиска по образцу. Во время поиска вокруг базовай точки происходит ``нащупывание'' направления движения в сторону минимума по фазовой плоскости. При поиске по образцу происходит движение в выбранном направлении, причем направление в некоторых пределах корректируется. Практика использования этого алгоритма показала, что в ряде случаев было бы полезно увеличить переборную компоненту на этапе поиска вокруг базовой точки.

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

В случае алгоритмов 2 и 3 не имеет большого смысла распараллеливать поиск вокруг точки образца, поэтому процедура поиска оставлена такой же, как в оригинальном методе Хука-Дживса. В алгоритме 1 поиск вокруг точки образца совпадает с алгоритмом поиска вокруг базовой точки.

Распараллеливание ведется по схеме мастер-рабочий. Мастер отвечает за работу макроалгоритма поиска минимума, за раздачу заданий рабочим, вычисляет часть точек при поиске вокруг базовой точки, осуществляет весь поиск по образцу при вычислениях по алгоритмам 2 и 3. Рабочий получает от мастера пакет с заданием обработать некоторое количество точек, вычисляет в них значения функции и посылает мастеру координаты точки, в которой значение функции меньше, чем в остальных точках пакета, и само значение функции в этой точке.

Метод Монте-Карло

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

Параллельная программа

На основе предложенных алгоритмов была разработана параллельная программа на языке ``Си'' для вычислителей МВС-100/1000 под операционную систему Router [3, 4].

С помощью этой программы решалось несколько задач: построение брахистохроны в условиях трения (как тестовая задача), построение брахистохроны в центральном поле тяготения [5], определение констант скоростей химической реакции [6].

В зависимости от конкретной задачи размерность аргумента минимизируемой функции менялась от 5 до 50. При этом оптимальное число используемых в задаче процессоров было от 8 до 64.

Анализ эффективности различных вариантов реализации метода Монте-Карло проводился статистическими методами.

Интересно, что при применении элементов метода Монте-Карло в ряде запусков программы была получена эффективность распараллеливания, превышающая единицу! Например, задача на восьми процессорах выполнялась быстрее, чем на одном, более чем в восемь раз. Этот парадоксальный результат объясняется применением разных алгоритмов при работе в однопроцессорном и многопроцессорном режимах. В однопроцессорном режиме работает только метод Хука-Дживса, и не выполняются вычисления по методу Монте-Карло, который и способствовал наблюдаемому ускорению сходимости.

References

[1]

Банди Б. Методы оптимизации. Вводный курс. М.: Радио и связь, 1988.

[2]

Тятюшкин А.И. Параллельные вычисления в многометодной оптимизации // Распределенные системы: оптимизация и приложения в экономике и науках об окружающей среде. Сборник докладов к Международной конференции (DSO'2000). Екатеринбург: УрО РАН, 2000. C. 333-336.

[3]

Лацис А.O. Операционная среда ROUTER для транспьютерных систем. Документация по МВС-100.

[4]

Игумнов А.С., Коновалов А.В., Самофалов В.В., Шарф С.В. Развитие и адаптация системного программного обеспечения МВС-100 // Алгоритмы и программные средства параллельных вычислений: [Сб. науч. тр. Вып. 2.]. Екатеринбург: УрО РАН, 1998. C. 123-133.

[5]

Иванов А.Г. Применение параллельной программы поиска минимума функции многих переменных к задаче о брахистохроне в центральном поле тяготения² // Алгоритмы и программные средства параллельных вычислений: [Сб. науч. тр. Вып. 3]. Екатеринбург: УрО РАН, 1999, С. 81-94.

[6]

Иванов А.Г., Краснов В.П., Кумков С.И. Информационные множества констант скоростей химической реакции // Материалы конференции "Высокопроизводительные вычисления и их приложения". Черноголовка, 2000.

Footnotes:

¹ Работа выполнена при поддержке Российского фонда фундаментальных исследований (проекты 00-01-00348, 99-07-90441).

² Электронный вариант статьи размещен по адресу: http://home.imm.uran.ru/iagsoft/trasbo99.html.

Главное меню | Публикации | Электронные публикации | Обо мне |