Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Лекция 15. Параллельные методы многоэкстремальной оптимизации Образовательный комплекс Введение в методы параллельного программирования Гергель В.П., профессор, д.т.н. Кафедра математического обеспечения ЭВМ

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 2 из 43 Введение Постановка задачи Обзор методов Решение одномерных задач (последовательный индексный алгоритм) Редукция размерности задачи Использование множественных отображений Решение многомерных задач (параллельный индексный алгоритм) Заключение Содержание

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 3 из 43 Введение Задачи минимизации некоторой функции при ограничениях типа неравенств встречаются во многих областях науки и техники Нахождение минимума является трудоемкой операцией, ее сложность экспоненциально растет с ростом размерности задачи Методы оптимизации представляют собой современную динамично развивающуюся область применения параллельных вычислений

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 4 из 43 Найти минимум функции (y) : где - (y) – минимизируемая функция (критерий), - g j (y), 1 j m – функциональные ограничения, - D – область поиска, - y – вектор варьируемых параметров Постановка задачи… Допустимая область

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 5 из 43 Априорная информация о задаче – предположение о выполнимости условия Липшица Постановка задачи…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 6 из 43 g 1 (y)=0.01[(y 1 2.2) 2 +(y 2 1.2) ] 0 g 2 (y)=100[1 (y 1 2) 2 /1.44 (0.5y 2 ) 2 ] 0 g 3 (y)=10[y sin(2 (y ))] 0 Пример задачи глобальной условной оптимизации Критерий: Ограничения: Область поиска: D={y R 2, 0y 1 4, 1y 2 3} Постановка задачи…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 7 из 43 D y*y* (y)=const g j (y)=0 Постановка задачи

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 8 из 43 Локальная оптимизация Используется идея локального спуска В многоэкстремальных задачах схема локального спуска, вообще говоря, не приводит к решению. Мультистарт – запуск локального метода из нескольких точек. Низкая эффективность мульти- стартовых схем в существенно многоэкстремальных задачах, т.к. одно и то же локальное решение может быть найдено несколько раз. Обзор методов…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 9 из 43 Обзор методов… Глобальная оптимизация Построение случайных или детерминированных покрытий области поиска. Количество узлов равномерной сетки увеличивается экспоненциально с увеличением размерности задачи.

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 10 из 43 Глобальная оптимизация Построение неравномерных адаптивных покрытий области поиска (алгоритм глобального поиска) Обзор методов… y*y* g 1 (y)=0 g 2 (y)=0 g 3 (y)=0 (y)=const Методы ориентированы на построение существенно более плотной сетки только в окрестности глобально- оптимального решения задачи, чем вне этой окрестности.

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 11 из 43 Учет нелинейных ограничений Классический подход: методы штрафных и барьерных функций Вычисление всех значений ограничений в точке, включая нарушенные. Проблема подбора коэффициентов штрафа. Решение серии безусловных подзадач. Новый подход: индексная схема учета ограничений Обзор методов

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 12 из 43 Рассмотрим одномерную задачу глобальной оптимизации (x * ) min (x) g m+1 (x) x a,b, g j (x) 0, 1 j m и предположим, что функции задачи удовлетворяют условию Липшица |g j (x 1 ) g j (x 2 )| L j | x 1 x 2 |, 1 j m+1. Частичная вычислимость: функция g j (x) вычислима лишь в соответствующей подобласти Q j a,b], 1 j m, где Q 1 a,b, Q j+1 x Q j g j (x) 0, 1 j m. Исходная задача может быть приведена к виду (x * ) min g m+1 (x): x Q m+1. Индексная схема учета ограничений…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 13 из 43 Индексная схема учета ограничений… a b g1(x)g1(x) (x) g2(x)g2(x) g2(x)g2(x) Q3Q3 Q3Q3 x1x1 x2x2 x3x3 (x 3 ) g1(x1)g1(x1) Q1Q1 Q2Q2 Q2Q2 Пример Критерий: (x) cos(18x 3)sin(10x 7)+1.5 Ограничения: g 1 (x) exp( x/2)sin(6x 1.5)0, g 2 (x) |x|sin(2 x 0.5)0. Область поиска: x 0.6,2.2 Приведены дуги функций задачи и соответствующие области Q j,1 j 3, в предположении частичной вычислимости

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 14 из 43 Индексная схема учета ограничений… a b (x) g2(x)g2(x) g1(x)g1(x) g1(x)g1(x) g2(x)g2(x) x*x* Введем классификацию точек x из области поиска a,b с помощью индекса (x), где 1 есть число ограничений, которые выполняются в этой точке. Указанный индекс определяется условиями g j (x) 0, 1 j 1, g (x)>0, где последнее неравенство несущественно, если =m+1. «Индексная» функция f(x) Данная классификация порождает функцию f(x) g (x), (x), определенную и вычислимую всюду в a,b

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 15 из 43 Индексная схема учета ограничений a b x*x* (x 3 ) (x 3 ) |x x 3 | x1x1 x2x2 x3x3 x4x4 Оценка оптимальной точки: объединение выделенных отрезков не содержит решения задачи Исходная задача преобразуется к виду (x * ) min (x): x [a,b], где, M max (x):x a,b. Схема исключает влияние априори неизвестных констант Липшица L, 1 m+1, и глобального минимума.

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 16 из 43 Последовательный алгоритм… Характеристическая схема алгоритма:… Первые два испытания: x 0 a и x 1 b. 1.Упорядочить точки по координате: a x 0 … x i … x k b. 2.Классифицировать точки по индексу, т.е. построить множества I i 1 i k, = (x i ), 1 m 1. 3.Вычислить текущие нижние оценки для априори неизвестных констант Липшица L,1 m 1,

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 17 из 43 Характеристическая схема алгоритма:… 4. Для каждого (x i 1,x i ), 1 i k, вычислить характеристику R(i), где длина интервала, r >1, 1 m 1, параметры метода. 5. Определить интервал с максимальной характеристикой R(t) max R(i) 1 i k. Последовательный алгоритм…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 18 из 43 Характеристическая схема алгоритма: 5. Провести очередное испытание во внутренней точке интервала (x t,x t ) 6. Проверить условие остановки: x t x t, где заданная точность поиска глобального минимума. Последовательный алгоритм…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 19 из 43 Результаты вычислительных экспериментов –Рассмотрим одномерную задачу Критерий: (x) cos(18x 3)sin(10x 7)+1.5 Ограничения: g 1 (x) exp( x/2)sin(6x 1.5)0, g 2 (x) |x|sin(2 x 0.5)0. Область поиска: x 0.6,2.2 –Точность поиска минимума 10 5, решение x * =2.0795, (x * )=0.565 k1k1 k2k2 k3k3 Перебор по равномерной сетке Метод штрафных функций375 Индексный метод k i – число вычислений значений i-й функции. Последовательный алгоритм…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 20 из 43 Последовательный алгоритм Результаты вычислительных экспериментов =1 =2 ab g1(x)g1(x) (x) g2(x)g2(x) g2(x)g2(x) =3 Координаты точек испытаний, осуществленных алгоритмом, отмечены тремя рядами вертикальных штрихов. Штрихи верхнего ряда соответствуют точкам с единичным индексом, второго – точкам, индексы которых равны 2; точки, отмеченные штрихами нижнего ряда, являются допустимыми. Дуги функций задачи в предположении частичной вычислимости

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 21 из 43 Рассмотрим многомерную задачу глобальной оптимизации (y * ) min (y) y D, g j (y) 0, 1 j m, D y R N : a i y i b i, 1 i N. Пусть y(x) есть отображение Пеано области поиска D на отрезок [0,1] y(x) 0 x 1 y R N : y D Используя отображение y(x), многомерная задача может быть сведена к одномерной (y * ) min (y) y D, g j (y) 0, 1 j m min (y(x)) x [0,1], g j (y(x)) 0, 1 j m. Если (y) удовлетворяет условию Липшица, то (y(x)) удовлетворяет равномерному условию Гельдера Редукция размерности…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 22 из 43 Редукция размерности…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 23 из 43 Численные методы для построения приближений кривых Пеано рассмотрены в работах Стронгина Р.Г. (1978, 1992) и монографии Стронгина Р.Г., Сергеева Я.Д. (2000). Редукция размерности…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 24 из 43 Редукция размерности Программная реализация: –Функция mapd реализует прямое отображение: для заданной точки x [0,1], плотности развертки m и размерности пространства n вычисляется образ y(x) D. –Функция xyd реализует обратное отображение: для заданной точки y D, плотности развертки m и размерности пространства n вычисляется ее прообраз y 1 (x) [0,1]. Программа

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 25 из 43 Проблема. Близким образам y ' y(x ' ), y '' y(x '' ) могут соответствовать существенно далекие прообразы x ', x '' [0,1]. Подход. Использование множества отображений Y(x) {y 1 (x), y 2 (x), …, y l (x)}. Множественные отображения… Каждая кривая Пеано y i (x) из Y(x) может быть получена в результате некоторого сдвига вдоль главной диагонали гиперинтервала D.

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 26 из 43 Таким образом сконструированное множество кривых Пеано позволяет получить для любых близких образов y ', y '', отличающихся только по одной координате, близкие прообразы x ', x '' для некоторого отображения y i (x). Множественные отображения… Чтобы выделить область поиска D требуется введение в задачу дополнительного ограничения g 0 (y) = max { |y i | 2 1 : 1 i N }.

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 27 из 43 Множественные отображения Программная реализация: –Функция GetImage реализует прямое отображение: для заданной точки x [0,1], плотности развертки m, размерности пространства n и номера развертки l вычисляется ее образ y l (x); –Функция GetPreimages реализует обратное отображение: для заданной точки y из многомерного пространства, плотности развертки m, размерности пространства n и числа разверток L вычисляются все ее прообразы x 0, x 1,…, x L. Программа

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 28 из 43 Использование множества отображений приводит к формированию соответствующего множества одномерных многоэкстремальных задач min (y l (x)) x [0,1], g j (y l (x)) 0, 0 j m, 0 l L. Каждая задача может решаться независимо; при этом любое вычисленное значение z i g (y l (x i )) функции g (y) может быть преобразовано к значению z j g (y k (x j )) для любых задач l и k без повторных трудоемких вычислений функции g (y). Подобное информационное единство дает возможность оптимизации всего множества функций параллельно Принцип распараллеливания

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 29 из 43 Решающие правила алгоритма в целом совпадают с правилами последовательного алгоритма, кроме способа проведения испытания: После выбора точки очередной итерации поиска процессор информирует о произведенном выборе все остальные процессоры; Каждый процессор после проведения испытания в точке итерации передает полученный индекс и значение функции всем процессорам вычислительной системы; Перед началом очередной итерации каждый процессор использует все полученные данные для расширения имеющегося набора с поисковой информацией. Предлагаемая схема не содержит какого-либо единого управляющего процессора, что увеличивает надежность выполняемых вычислений. Параллельный алгоритм…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 30 из 43 Схема информационных обменов Параллельный алгоритм…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 31 из 43 Параллельный алгоритм… Результаты вычислительных экспериментов… Рассмотрим двумерную задачу глобальной оптимизации g 1 (y) 0.01[(y 1 2.2) 2 +(y 2 1.2) ] 0 g 2 (y) 100[1 (y 1 2) 2 /1.44 (0.5y 2 ) 2 ] 0 g 3 (y) 10[y sin(2 (y ))] 0 Ограничения: Область поиска : D={y R 2, 0y 1 4, 1y 2 3} Решение : y * (0.942, 0.944), (y * ) 1.489

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 32 из 43 l Вычислено значений g1g1 g2g2 g3g3 g l Вычислено значений g0g0 g1g1 g2g2 g3g3 g Всего Число процессоров Ускорение Результаты вычислительных экспериментов… Параллельный алгоритм… Два процессора/развертки Один процессор/развертка Сводная таблица Параметры метода Плотность развертки m 12 Точность поиска 10 3 Найдено решение y * (0.942, 0.945)

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 33 из 43 Параллельный алгоритм… y*y* g 1 (y)=0 g 2 (y)=0 g 3 (y)=0 (y)=const Расположение точек испытаний при использовании шести процессоров Результаты вычислительных экспериментов…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 34 из 43 Параллельный алгоритм Расположение точек испытаний при использовании шести процессоров Ускорение сходимости (использование адаптивных резервов) y*y* g 1 (y)=0 g 2 (y)=0 g 3 (y)=0 (y)=const

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 35 из 43 Предварительные замечания: –Рассматриваются задачи, в которых вычисление значения функции в точке является достаточно трудоемким; –Объем вычислений, выполняемый на каждой итерации индексного метода, может существенно отличаться; –Вычислительные узлы при параллельном выполнении программы могут иметь разную мощность. Вывод: эффективная параллельная реализация индексного метода может быть только асинхронной. Программная система Абсолют Эксперт позволяет решать (исследовать) задачи многомерной глобальной оптимизации. Основной режим работы системы – параллельное выполнение на кластере. Программная реализация…

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 36 из 43 Программная реализация… Оптимизация Очередь характеристик Страничная память Поисковая информация Обработка состояний Архив Функциональная структура комплекса Абсолют Эксперт

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 37 из 43 Подсистема Оптимизация – построение объекта оптимизации, постановка задачи, определение и настройка методов, назначение заданий и выполнение процесса поиска оптимального варианта Подсистема Поисковая информация – структуры данных и методы, обеспечивающие получение, хранение и анализ информации, генерируемой в ходе итераций поиска Подсистема Страничная память – структуры данных и методы для организации страничного представления оперативной памяти, используемой для обработки поисковых данных Подсистема Архив – предназначена для организации хранения поисковой информации во внешней памяти Подсистема Очередь характеристик – ускоряет работу алгоритмов при больших объемах поисковой информации Подсистема Обработка состояний – унифицированная схема контроля и наблюдения за состояниями системы Программная реализация

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 38 из 43 В разделе рассмотрен индексный метод учета функциональных ограничений в задачах глобальной оптимизации. Представлена постановка задачи, изложена схема работы индексного метода для решения одномерных задач, приведена его программная реализация. Изложена схема редукции размерности задачи, основанная на развертках Пеано, приведена программная реализация разверток. Представлен параллельный алгоритм, основанный на множественных отображениях Пеано. Приведена программная реализация множественных отображений. Дана общая характеристика программной системы Абсолют Эксперт. Представлены результаты вычислительных экспериментов. Заключение

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 39 из 43 Вопросы для обсуждения В чем состоит задача поиска оптимального решения? В чем заключается сложность определения оптимума в задачах глобальной оптимизации? Чем обоснована необходимость поиска глобального оптимума на неравномерном покрытии области поиска? В чем состоит индексная схема учета ограничений ? Опишите класс характеристических алгоритмов оптимизации. В чем заключаются недостатки использования единственной развертки Пеано при редукции размерности? Каким образом множественные отображения позволяют распараллелить индексный алгоритм? Чем вызвана необходимость реализации асинхронной схемы расчетов в параллельной модификации индексного алгоритма?

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 40 из 43 Литература Стронгин Р.Г. (1978).Численные методы в многоэкстремальных задачах. – М.: Наука. Strongin R.G. (1992) Algorithms for multi-extremal mathematical programming problems employing the set of joint space-filling curves. Journal of Global Optimization, 2. P. 357–378. Strongin R.G., Sergeyev Ya.D. (2000). Global optimization with non-convex constraints. Sequential and parallel algorithms. – Dordrecht: Kluwer Academic Publishers.

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 41 из 43 Следующая тема Программная система ПараЛаб для изучения и исследования методов параллельных вычислений

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 42 из 43 Гергель В.П., профессор, д.т.н., руководитель Гришагин В.А., доцент, к.ф.-м.н. Баркалов К.А., ст. преподаватель, к.ф.-м.н. (раздел 14) Сысоев А.В., ассистент (разделы 1) Лабутин Д.Ю., ассистент (система ПараЛаб) Абросимова О.Н., ассистент (раздел 10) Гергель А.В., аспирант (раздел 12) Лабутина А.А., магистр (разделы 7,8,9, система ПараЛаб) Сенин А.В. (раздел 11) Авторский коллектив

Н.Новгород, 2008 г. Основы параллельных вычислений: Параллельные методы многоэкстремальной оптимизации © Гергель В.П. 43 из 43 Целью проекта является создание образовательного комплекса "Многопроцессорные вычислительные системы и параллельное программирование", обеспечивающий рассмотрение вопросов параллельных вычислений, предусматриваемых рекомендациями Computing Curricula 2001 Международных организаций IEEE-CS и ACM. Данный образовательный комплекс может быть использован для обучения на начальном этапе подготовки специалистов в области информатики, вычислительной техники и информационных технологий. Образовательный комплекс включает учебный курс "Введение в методы параллельного программирования" и лабораторный практикум "Методы и технологии разработки параллельных программ", что позволяет органично сочетать фундаментальное образование в области программирования и практическое обучение методам разработки масштабного программного обеспечения для решения сложных вычислительно-трудоемких задач на высокопроизводительных вычислительных системах. Проект выполнялся в Нижегородском государственном университете им. Н.И. Лобачевского на кафедре математического обеспечения ЭВМ факультета вычислительной математики и кибернетики ( Выполнение проекта осуществлялось при поддержке компании Microsoft. О проекте