Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с
ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНЫХ
жүктеу/скачать 1,64 Mb. Pdf көрінісі
|
Seminar 1
| ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ ПАРАЛЛЕЛЬНЫХ
РЕКУРСИВНЫХ СХЕМ РЕДУКЦИИ РАЗМЕРНОСТИ * В.А.Гришагин, В.В.Песков Нижегородский государственный университет им. Н.И.Лобачевского Рассмотрим конечномерную задачу оптимизации: N R Q y y f ⊆ ∈ → min, ) ( , (1) , ) ( : { 0 ≤ ∈ = y g D y Q j } m j ≤ ≤ 1 , (2) } ], , [ : { N i b a y R y D i i i N ≤ ≤ ∈ ∈ = 1 , (3) в которой требуется найти глобальный минимум многоэкстремальной целевой функции ) ( y f в области Q , задаваемой координатными (3) и функциональными (2) ограничениями на выбор допустимых точек (векторов) ) ,..., , ( N y y y y 2 1 = . Многоэкстремальные оптимизационные задачи являются пробле- мами высокой вычислительной сложности, причем значительное влияние на сложность задачи (1)–(3) оказывает ее размерность N. Так, в случае, когда минимизируемая функция f(y) удовлетворяет в области поиска условию Липшица '' ' ) '' ( ) ' ( y y L y f y f − ≤ − , Q y y ∈ '' ,' , (4) для задач указанного класса характерен экспоненциальный рост вы- числительных затрат при увеличении размерности. В связи с этим ес- тественно использовать ресурсы параллельных вычислительных сис- тем для ускорения процесса анализа и расширения круга исследуемых задач, которые без использования потенциала параллелизма решены быть не могут. Одним из эффективных подходов к численному решению задач (1)–(3) является подход, основанный на использовании схемы вложен- * Работа выполнена при поддержке РФФИ (грант № 01-01-00587) 57 ной рекурсивной оптимизации (многошаговой схемы редукции раз- мерности) [1,2], согласно которой решение исходной многомерной задачи заменяется решением семейства рекурсивно связанных одно- мерных подзадач, что позволяет применить для решения многомерной задачи известные методы одномерного глобального поиска. Применение в качестве одномерных алгоритмов оптимизации па- раллельных характеристических методов глобального поиска [3] по- зволило построить эффективные параллельные алгоритмы для реше- ния многомерных многоэкстремальных задач. Эти алгоритмы позво- ляют при использовании 2 N процессоров в случае трудновычислимых задач (когда время вычисления функционалов задачи значительно пре- вышает времена обменов данными) добиться эффективности решения, близкой к 95–97%, т.е. экспоненциально ускорить решение задачи за счет, разумеется, экспоненциального увеличения ресурсов (числа про- цессоров), обеспечивающих процедуру решения. Настоящая работа предлагает новый механизм формирования од- номерных подзадач в структуре многошаговой схемы, позволяющий сократить количество испытаний (вычислений функционалов задачи) и тем самым ускорить решение, сохранив при этом эффективность распараллеливания при многопроцессорной реализации. Поясним идею алгоритма на примере двумерной задачи (1) при от- сутствии функциональных ограничений (2), т.е. для прямоугольной области Q = D. Согласно многошаговой схеме, ) , ( min min ) ( min 2 1 2 2 2 1 1 1 жүктеу/скачать 1,64 Mb. Достарыңызбен бөлісу:
|