Автоматика и телемеханика, Л- 5, 2007
PACS 89.20.Ff
© 2007 г. Ю.Г. ЕВТУШЕНКО, академик РАН, В.У. МАЛКОВА, A.A. СТАНЕВИЧЮС, канд. экон. наук
(Вычислительный центр им. A.A. Дородницына РАН)
РАСПАРАЛЛЕЛИВАНИЕ ПРОЦЕССА ПОИСКА ГЛОБАЛЬНОГО ЭКСТРЕМУМА1
Разработан параллельный алгоритм поиска глобального экстремума функции многих переменных. Алгоритм основан па методе неравномерных покрытий. предложенном Ю.Г. Евтушенко для функций, удовлетворяющих условию Липшица. Алгоритм реализован па языке С в МР1-системе параллельного программирования с передачей сообщений. Для ускорения расчетов используются вспомогательные процедуры поиска локального экстремума. Работа алгоритма демонстрируется па примере расчета строения атомного кластера.
1. Введение
В подавляющем большинство оптимизационных задач требуется найти глобальный оптимум. Однако из-за большой сложности поиска глобального экстремума обычно ограничиваются отысканием локальных решений. Современные многопроцессорные ЭВМ существенно расширяют возможности решения задач глобальной оптимизации, позволяя использовать параллельные алгоритмы расчетов. Перенос последовательных алгоритмов и создание новых параллельных методов глобальной оптимизации становятся весьма актуальными. Обзор многочисленных публикаций по поиску глобального экстремума приведен в [1]. Проблемы распараллеливания вычислений подробно изложены в [2].
В 1971 г. в [3] был предложен и на языке АЛГОЛ-бО реализован метод неравномерных покрытий для нахождения глобального экстремума липшицовых функций. Дальнейшее развитие этот метод получил в [4. 5]. В данной работе рассматривается параллельный вариант метода неравномерных покрытий, дается информация о программной реализации его на языке С в MPI-систомо параллельного программирования с передачей сообщений (Message Passing Interface). Для ускорения расчетов используются вспомогательные процедуры поиска локального экстремума. Работа алгоритма демонстрируется на примере расчета строения атомного кластера. Вычислительные эксперименты проведены на вычислительных комплексах MVS 6000 и MVS 15000 [61.
1 Работа выполнена ири финансовой поддержке программы № 14 фундаментальных исследований Президиума РАН "Раздел 11: Высокопроизводительные вычисления и многопроцессорные системы" '2006 г., а также программы № 15 Президиума РАН "Исследование и создание научных приложений в распределенной среде суперкомпыотерпых вычислений па базе ВЦ РАН" '2006 г.
2. Постановка задачи, общая идея метода покрытий
Рассмотрим задачу отыскания глобального минимума функции /, определенной и непрерывной на компактном множестве Р С Нп
(1) /* = ё1оЬ шт / (х).
хЕР
Через X* обозначим множество решений задач и (1), через /* - минимальное значение целевой функции / (х). Введем множество е-оптимальных (приближенных) решений задачи (1):
(2) X* = {х е Р : /(х) < /* + е} .
Очевидно, X* С XI С Р. В большинстве практических задач достаточно найти хотя бы одну точку хг е XI и взять в качестве оптимального значения /* число /г = / (хг )■ Другими словами, надо с заданной точностью е определить величину глобального минимума функции и найти хотя бы одну точку хг, где это приближенное значение достигается.
Введем набор множеств Вт = [РьР2,...,Рт] из Еп и пабор п-мериых точек Мт = [с1,с2,... ,ст] таких, что сг е Рг С Р для всех 1 ^ г ^ ш. Объединение ш множеств Рг обозначим через
ит = Рг.
г=1
Рг Р
(3) Р = ит.
сг /
(4) Ет = шт /(сг) = /(сг)
определяется рекордная точка сг и рекорд Нт.
/ Рг х е Рг
полнено условие
(5) /(х) > Ет - е.
Основой метода неравномерных покрытий является следующее легко проверяемое
Утверждение 1. Пусть набор множеств Вт и функция / таковы, что ит = Р и выполнено условие (5) для всех 1 < г < т. Тогда рекордная точка сг е X*.
Рг Р
ка х* из X* будет принадлежать то крайней мере одном у из множеств Рг. Пусть х* е Р3, в ^ т, тогда, учитывая (5), получим
/* = /(х*) > Ет - е = /(сг) - е.
сг е
Данное утверждение выражает основную идею метода неравномерных покры-
Р
Р Рг
Рг /
условию Липшица со своей константой Ьг. В некоторых областях функция может оказаться выпуклой или дважды дифференцируемой. Все эти особенности целесообразно учитывать для ускорения расчетов.
При реализации метода наборы Вт и Кт строятся последовательно, после каж-
/
последнее вычисление / было выполнено в точке ст, рекордная точка была сг, а рекорд был Ет. Определим следующее лебегово множество:
(6) Ст = {х е Р : Ет - е < /(х)}.
Пусть глобальный минимум на Ст достигается в точке х^ Тогда Ет - /х) = = /(сг) - /(х1) ^ е и, следовательно, в результате глобальной минимизации на Ст рекорд Ет может быть уточнен не бол ее чем на е. Поэтому множество Ст не пред-
Р
Еслп после описанных вычислений условие Р = ит не выполнено, то поиск минимума продолжается на множестве Wm = Р\Пт. Пусть определены ст+1 е Рт+1 С С Wm, вычислены /(ст+1)и Ет+1. Если на Рт+1 выполнено условие /(х) ^ Ет+1 -е, то множество Рт+1 может быть исключено и поиск минимума продолжается па
Wm\Pm+1. В противном случае множество Рт+1 разбивается па несколько подмно-
/
некоторые подмножества исключаются, другие дробятся и т.д. Процесс заканчива-
Р
дов - монотонно убывающая. Последовательность лебеговых множеств Ст, напротив, расширяющаяся, т.е. Ст С и к > ^^^^^^^у при некотором в < т из Р было исключено множество Р^, то Р8 ^^^^ет бъпъ исключено из Р и при всех в ^ ш.
Лебегово множество С будет наибольшим, если в (6) взять Ет = /*. Однако /*
/Р
В тех точках сг е Р, где получено, что /(сг) < Ет, происходит улучшение рекорда, и есть основание полагать, что решая задачу локального поиска
1ос шт /(х),
хЕР
стартуя из точки сг, удастся найти другую точку с е Р, в которой /(с) < /(сг). Такой прием часто существенно ускоряет расчеты, позволяя улучшить рекорд и тем самым
Р
Наиболее трудным этапом в реализации алгоритма поиска экстремума является определение хотя бы некоторой части множества Ст. Здесь приходится налагать
/ /( х)
строить миноранту д(сг,х) такую, что для всех х,сг е Р выполнены неравенства
(7) д(сг,х) < / (х), д(сг, сг) = / (сг). Определим множество
(8) Кг = {х е Р : Ет - е < д(сг,х)}.
Из (7) следует, что Кг С Ст, поэтому множество Кг можно исключить из области поР
легко строятся. Пусть функция / удовлетворяет условию Липшица с константой Ь, х сг Р
(9) \/(х) - /(сг)\ < Ь\\х - с*||то.
Здесь и ниже используется p-я гельдеровская норма
1/p
Vj=1
которая при p = ж совпадает с чебышевской нормой ||v||TO = max \vj\.
l^j^n
Тогда для всех x G P имеем f (x) > f (ci) - LUx - cil
Поэтому можно взять удовлетворяющую (7) миноранту
(10) g(ci,x) = f (ci) - LUx - ciU Введем множество
(11) Ki = {x G Rn : Ux - dlln < Pim},
(12) Pim = (f (ci) - Rm + e)/L.
Здесь Ki - куб с центром в точке ci и главной диагональю 2pim (или если p = ж, то шар с центром в точке ci и радиус ом pim).
Если ci G P для всех 1 ^ i ^ m, то согласно (5) f (ci) ^ f (cr), поэтому радиус pim, задаваемый формулой (12), будет больше или равен e/L:
min g(ci,x) = f (ci) - L max Ux - q||to = f (ci) - Lpm > Rm - e.
x^Ki x^Ki
Ki P
кубов Ki, 1 ^ i ^ m, удовлетворяющих (10), покрывает множество P, то cr G X
Радиус шара Ki будет большим, если f (ci) ^ f (cr), и малым в областях, где f (ci) ~ f (cr)■ Благодаря этому возможно неравномерное покрытие множества P шарами различного радиуса.
Если, помимо (9), выполнено условие вида !f '(x) - f'(z)||1 ^ M!x - z||TO и а есть скалярное произведение векторов f '(ci) и x - ci, то
f (x) - f (ci) > а - m!x - > -!x - а! ■ !f'(ci)||1 - m!x - аЩ.
Объединяя это с (10), получим, что минорантой будет
g(ci,x) = f (ci) - Щ - c^ ■ min{L, ||f'(c^h + M^ - .
f
3. Алгоритм последовательного покрытия
При программной реализации метода вводятся дополнительные упрощающие предположения. Считается, что допустимое множество P — это n-мерный параллелепипед с гранями, параллельными координатным плоскостям:
P = {x G Rn, a < x < b}.
Здесь и ниже неравенство a ^ x означает, что aj ^ xj для всех 1 ^ j ^ п.
В процессе расчетов используются вспомогательные векторы ai,bi G Rn и порождаемые ими прямоугольные параллелепипеды с гранями, параллельными координатным плоскостям: Pi = {x G Rn : ai ^ x ^ bi}.
Будем считать, что все векторы ai ^ a и bi ^ b. Таким образом все параллелепипеды Pi С P. В качестве точек ci берутся центры параллелепипедов P'i:
cj = (aj + bj )/2, 1 < j < n.
Вектор главной диагонали di параллелепипеда Pi имеет компоненты dj = bj — aj, 1 ^ j ^ n.
Считаем, что функция f удовлетворяет условию Липшица (9) всюду на P с одной и той же константой L. Воспользуемся минорантой (10). Обозначим
(13) yi = min g(ci,x) = f (ci) — L max \\dl || = f (o) — L ||di||TO.
xEPi 2 l^j^n 2
Если yi ^ Rm — e, то параллелепипед Pi может быть исключен, так как глобальный минимум на нем не дает улучшения текущего рекорда Rm более чем на в, и поиск продолжается на множестве PВ противном случае если yi < Rm — e, Pi
на этих двух частях. Если главные диагонали одной или обеих частей меньше, чем 2e/L, то эти части исключаются из области поиска. В центрах оставшихся частей вычисляются значения f (x). При этом, если возможно, улучшается рекорд и проверяется условие покрытия обеих частей. Части, которые оказались покрытыми,
Pi
Pi
не будет покрыт. Возможны самые разнообразные способы покрытия параллелепи-P
реализовано послойное покрытие. Этот вариант использовался для решения задач глобальной оптимизации в случае, когда n ^ 15 Ниже, следуя [4], для покрытия P применим метод ветвей и границ. Аналогичный подход для задач ранцевого типа использовался в [7].
С каждым параллелепипедом Pi свяжем набор Si = (ci,di,yi). Совокупность наборов Si для всего набора непокрытых параллелепипедов Bm будем называть списком наборов и обозначать S = {Si,S2,...,Sm}. Запись S = 0 означает, что S
В следующей формулировке алгоритма буква к будет обозначать порядковый номер итерации основного цикла.
Начальные операции. Положить к = 1, m = 1, Pi = P. Задать e > 0,L и некоторую точку xo е P. Вычислить cu du f (ci), f (xo), yi, z = e/L, R = min {f (ci), f(xo)}. Положить N((i
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.