Название работы	Кол-во страниц	Размер
Исследование алгоритма для решения задач многокритериальной условной...	1	27.64kb.
Новый Алгоритм Кластеризации grid-рерурсов для Оптимизации Информационного...	1	238.52kb.
Автоматическое распараллеливание программ для распределенных систем.	1	265.35kb.
Н. В. Нуждин, В. В. Пекунов, С. Г. Сидоров, Л. П. Чернышева, Ф.	1	14.79kb.
6 Создание среды распределенных вычислений и интенсивных операций...	1	47.57kb.
Отчет по лр№1: «Решение систем линейных алгебраических уравнений...	1	64.28kb.
Интегрированная инфраструктура, инструменты и методы для поддержки...	1	41.51kb.
Программа по курсу: методы параллельной обработки данных (базовый)	1	50.04kb.
Задача рентабельности затрат на производство изделий:. Задача рентабельности...	1	29.28kb.
Структура f-замыканий в среде ride м. О. Бахтерев	1	44.3kb.
Сравнительный анализ работы адаптивного генетического алгоритма при...	1	93.61kb.
Программа дисциплины «Оптимизация в дискретных системах»	1	67.45kb.
Викторина для любознательных: «Занимательная биология»	1	9.92kb.

АДАПТАЦИЯ АЛГОРИТМА УСЛОВНОЙ ОПТИМИЗАЦИИ
КОМПЛЕКСНЫМ МЕТОДОМ БОКСА ДЛЯ СИСТЕМ
РАСПРЕДЕЛЁННЫХ ВЫЧИСЛЕНИЙ

Р.Ю. Жничков, И.А. Бойко, А.Н. Савин
Саратовский государственный университет им. Н.Г. Чернышевского,
Саратов, Россия
В настоящее время большое количество технических задач требует поиска экстремума некоторой целевой функции на строго заданной области определения, то есть применяется условная оптимизация. Существует множество алгоритмов и методов оптимизации, реализованных в компьютерных программах. Однако в некоторых случаях при многопараметрической условной оптимизации и наличии многих локальных экстремумов целевой функции выполнение такой программы на современном компьютере может быть неэффективно ввиду ограниченной вычислительной мощности последнего. В таких случаях представляется актуальной модификация существующих алгоритмов условной оптимизации для выполнения расчетов на параллельных вычислительных машинах [1].

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

Постановка задачи условной оптимизации

Задача условной оптимизации состоит в минимизации функции

,

где , а определяется явными ограничениями

, при ,

а также неявными ограничениями

, при .

Решение задачи условной оптимизации при нахождении локальных экстремумов возможно, например, с помощью комплексного метода Бокса [3].

На рис. 1 приведена блок-схема модифицированного метода Бокса, исключающего зацикливание алгоритма в случае локальной невыпуклости области ограничений и, соответственно, позволяющего находить глобальные экстремумы [2].

Р
ис. 1. Блок-схема модифицированного алгоритма оптимизации комплексным методом Бокса. Пунктиром выделен участок, исключающий зацикливание алгоритма при наличии локальных экстремумов.

Адаптация модифицированного алгоритма оптимизации
комплексным методом Бокса для использования на параллельной вычислительной системе

Анализ алгоритма модифицированного метода Бокса (рис. 1) показывает, что процедура инициализации комплекса подразумевает обновление центра уже определенных точек и дальнейшее его использование на каждой итерации, следовательно, распараллеливание данного участка алгоритма представляется невозможным; в основном процессорное время расходуется на многократное вычисление целевой функции. Следовательно, наиболее ценным является распараллеливание участка алгоритма, осуществляющего «улучшение» точек построенного комплекса.

Пусть параллельная вычислительная система содержит вычислительных узлов (вопрос выбора оптимального числа вычислительных узлов рассматривается далее при анализе результатов экспериментов).

Основная идея адаптации алгоритма оптимизации комплексным методом Бокса состоит в возможности одновременного улучшения худших точек (один выделенный узел осуществляет начальную инициализацию структур данных, построение комплекса, выработку заданий по улучшению точек комплекса).

Итерационная процедура адаптированного комплексного метода представлена в виде следующей блок-схемы (рис. 2).

Рис. 2. Итерационная процедура распараллеленного алгоритма оптимизации модифицированным комплексным методом Бокса. Пунктиром выделена параллельная часть алгоритма.

Программная реализация адаптированного для параллельного выполнения комплексного метода Бокса осуществлена на языке программирования Java с использованием продуктов Oracle Coherence [4] и GigaSpaces eXtreme Application Platform [5] в программной оболочке, разработанной Eclipse Foundation [6]. Построение приложения основывается на парадигме «мастер-рабочий», подразумевающей, что выделен один процесс, являющийся главным («процесс-мастер»), который производит начальную инициализацию структур данных, построение комплекса, выработку заданий по улучшению точек комплекса для процессов, осуществляющих вычисления на узлах («процессов-рабочих»).

Тестирование приложения, реализующего комплексный метод
условной оптимизации Бокса

При тестировании метода использовались следующие функции.

1. 
   Число параметров оптимизации равно четырем:
   
   где , , , .
   
2. 
   Число параметров оптимизации равно шести:
   
   где , , , , , .
   
3. 
   Число параметров оптимизации равно восьми:
   где , , , , , , , .
   

Очевидно, данные функции имеют глобальный минимум при нулевых значениях каждого из аргументов.

В качестве оценки эффективности работы разработанного приложения был использован счетчик итераций главного цикла «процесса-мастера». Данный критерий был применен в виду того, что стандартный параметр - количество вычислений целевой функции - использовать нецелесообразно, так как порядок этой величины будет одним и тем же для данной функции, но, в зависимости от количества «процессов-рабочих», время выполнения программы будет различным в силу параллелизма вычислений. Тестирование полученного приложения для каждой из вышеуказанных функций было проведено при различном числе «процессов-рабочих». Результаты отображены на рис. 3, 4.

Анализ приведённых на рис. 3, 4 зависимостей позволяет сделать вывод, что для разработанного алгоритма оптимизации наиболее эффективным с точки зрения точности вычислений и скорости сходимости будет расчет минимума при количестве «процессов-рабочих», равном количеству параметров оптимизации.

Рис. 3. Зависимость количества итераций алгоритма от количества «процессов-рабочих» при различном числе параметров оптимизации.

Рис. 4. Зависимость точности вычислений от количества процессов-рабочих.

Удовлетворительные по точности результаты за большее число итераций и, как следствие, большее время выполнения, можно также получить, используя количество «процессов-рабочих», меньшее числа параметров оптимизации (см. рис. 3). Использование количества «процессов-рабочих», большее числа параметров оптимизации не рекомендуется, так как при этом сильно возрастает погрешность вычислений (см. рис. 4), что обусловлено особенностями алгоритма (в этом случае одновременно «улучшаются» более половины точек комплекса, что приводит к погрешности при вычислении новых точек комплекса относительно центра тяжести лучших точек).

В ходе дальнейшего тестирования приложения выяснилось, что распараллеленный таким образом алгоритм не обеспечивает стабильности результатов, то есть, высока вероятность ошибки. После углубленного анализа метода Бокса был сделан вывод о целесообразности увеличения числа точек комплекса. Экспериментально было установлено, что требуемая точность вычислений и стабильность результатов достигается при числе точек комплекса , а не , как в исходном алгоритме (см. рис. 1). Результаты работы алгоритма с числом точек комплекса приведены в табл. 1 ( – количество параметров оптимизации, – количество итераций алгоритма при выполнении программы на оптимальном числе вычислительных узлов, – время выполнения программы на оптимальном числе вычислительных узлов, - найденное минимальное значение функции).

Таблица 1.

Результат тестирования программной реализации распараллеленного

метода Бокса с числом точек комплекса, равном .

4	180808	112	-1.3999999999999120
4	173273	111	-1.3999999999998975
4	213943	131	-1.3999999999999941
6	276544	176	-1.3999999999999715
6	287924	182	-1.3999999999999460
6	279295	177	-1.3999999999998964
8	387129	246	-1.3999999999999206
8	384586	245	-1.3999999999999506
8	401009	256	-1.3999999999999297

Как видно из табл. 1, выбор числа точек комплекса позволил получать стабильные результаты с заданной точностью. Экспериментально было установлено, что при меньших значениях результаты получаются нестабильными.

Для оценки времени работы разработанного приложения в указанные целевые функции была добавлена инструкция задержки выполнения на 0.5 секунды. Для каждой из целевых функций выполнялся поиск минимума на одном вычислительном узле и на оптимальном числе вычислительных узлов, при этом отмечалось количество итераций алгоритма и общее время выполнения программы; по результатам тестов подсчитывался коэффициент ускорения работы программы, равный отношению времени выполнения на одном вычислительном узле ко времени выполнения при оптимальном числе вычислительных узлов. Результаты сравнения времени выполнения программы на одном и на оптимальном количестве узлов приведены в табл. 2 ( – количество параметров оптимизации, – количество итераций алгоритма при выполнении программы на одном вычислительном узле, – количество итераций алгоритма при выполнении программы на оптимальном числе вычислительных узлов, – время выполнения программы на одном вычислительном узле, – время выполнения программы на оптимальном числе вычислительных узлов, – коэффициент ускорения времени выполнения).

Таблица 2.

Результаты сравнения времени выполнения программной реализации распараллеленного метода Бокса на одном и оптимальном количестве узлов.

			, мс	, мс
4	435	112	671774	180808	3.7
6	1287	177	1994684	279295	7.1
8	1392	246	2171954	387129	5.6

Как видно из табл. 2, коэффициент ускорения времени выполнения распараллеленного алгоритма на оптимальном количестве узлов составляет в среднем 5.5.

Заключение

Таким образом, предложенный адаптированный для параллельного выполнения алгоритм условной оптимизации на основе комплексного метода Бокса позволяет в несколько раз уменьшить время вычисления экстремума целевой функции, а также значительно повысить надёжность нахождения глобального экстремума за счёт одновременного исследования целевой функции в нескольких областях факторного пространства.

Список литературы

1. 
   Орлянская И.В. Современные подходы к построению методов глобальной оптимизации // Электронный журнал «Исследовано в России». –С. 2097-2108. http://zhurnal.ape.relarn.ru/articles/2002/189.pdf (19.05.2009).
   
2. 
   Савин А.Н., Шараевский Ю.П., Тимофеева Н.Е. Модификация комплексного метода условной оптимизации Бокса для определения размеров замедляющих систем по заданным электродинамическим характеристикам // 15-я Международная Крымская конференция «СВЧ-техника и телекоммуникационные технологии», 2005. –С. 779-780.
   
3. 
   Банди Б. Методы оптимизации // М.: Радио и связь, 1988. – 128 с.
   
4. 
   Oracle Coherence // http://www.oracle.com/technology/products/coherence/index.html (19.05.2009).
   
5. 
   GigaSpaces eXtreme Application Platform (XAP) // http://www.gigaspaces.com/xap (19.05.2009).
   
6. 
   About the Eclipse Foundation // http://www.eclipse.org/org/ (19.05.2009).