Численные методы решения оптимизационных задач


The Presentation inside:

Slide 0

Численные методы решения оптимизационных задач Ю.Г. Евтушенко, М.А. Посыпкин Вычислительный центр РАН


Slide 1

План лекции Постановка и виды задач оптимизации Метод неравномерных покрытий (МНП) Безусловная оптимизация Математическое программирование Эффективная реализация МНП на современных архитектурах


Slide 2

Постановка задачи оптимизации Экстремум берется относительно порядка заданного на Y


Slide 3

Классификация по структуре допустимого множества - безусловная оптимизация - дискретная оптимизация математическое программирование Линейное программирование Нелинейное программирование частично-целочисленное программирование (оптимизация)


Slide 4

Классификация по числу критериев Скалярная оптимизация (один критерий) Многокритериальная оптимизация (более одного критерия)


Slide 5

Классификация по локальности минимума Локальная оптимизация Глобальная оптимизация


Slide 6

Классификация по гарантии оптимальности Эвристические методы (не дают информацию о точности найденного решения) Детерминированные методы (гарантируют оптимальность с заданной точностью) Оптимум Приближенное решение


Slide 7

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


Slide 8

Метод Неравномерных Покрытий Предложен Ю.Г. Евтушенко в 1971 году Позволяет решать задачи без ограничений, с нелинейными ограничениями, частично-целочисленные задачи с одним и несколькими критериями Гарантирует оптимальность с заданной точностью (детерминированный метод)


Slide 9

Метод неравномерных покрытий Предложен для безусловной оптимизации в 1971 Ю. Г. Евтушенко, “Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке)”, Ж. вычисл. матем. и матем. физ., 11:6 (1971), 1390–1403 Расширен на случай многих критериев в 1986 Евтушенко Ю. Г., Потапов М. А. «Методы численного решения многокритериальных задач.» ДАН СССР, Т. 291, N 1, 1986, С. 25-39. Расширен на задачи математического программирования в 1992 Yu. G. Evtushenko, M. A. Potapov, V. V. Korotkikh. Numerical methods for global optimization. In "Recent advances in global optimization”, Princeton University Press, pp. 274-297. 1992. Первая параллельная реализация 2007 Ю. Г. Евтушенко, В. У. Малкова, А. А. Станевичюс. Распараллеливание процесса поиска глобального экстремума. Автоматика и телемеханика, № 5. С. 46-58, 2007. Новая техника для задач математического программирования 2011 Ю. Г. Евтушенко, М. А. Посыпкин. Варианты метода неравномерных покрытий для глобальной оптимизации частично-целочисленных нелинейных задач. Доклады Академии наук. Т: 437. № 2. С. 168–172.


Slide 10

Безусловная оптимизация: постановка задачи Требуется найти точку


Slide 11

Упрощение постановки От безусловной переходим к оптимизации с простыми (параллелепипедными) ограничениями («box-constrained») Требуется найти -оптимальное решение


Slide 12

Метод неравномерных покрытий для одномерной безусловной оптимизации [ a ] b ] a’ [ b’ Миноранта Лебеговское множество Целевая функция


Slide 13

Метод неравномерных покрытий для одномерной безусловной оптимизации [ a ] b


Slide 14

Общий случай: основная теорема 15 L2 L3 L4 L5 L6 - совокупность множеств Теорема. Если выполнено то - совокупность допустимых точек


Slide 15

Основные составляющие МНП Построение покрытия (системы покрывающих множеств) Построение последовательности рекордных точек


Slide 16

Липшицева Миноранта 1-го порядка Условие Липшица: Миноранта: представляет собой шар радиуса с центром в точке .


Slide 17

Липшицева миноранта 2-го порядка Градиент удовлетворяет условию Липшица Миноранта - шар радиуса с центром в точке Этот шар может быть исключен из дальнейшего рассмотрения.


Slide 18

Реализация МНП: метод бисекций


Slide 19

Реализация МНП: метод бисекций


Slide 20

Реализация МНП: метод бисекций


Slide 21

Реализация МНП: метод бисекций


Slide 22

Реализация МНП: метод бисекций


Slide 23

Реализация МНП: метод бисекций


Slide 24

Реализация МНП: метод бисекций


Slide 25

Реализация МНП: метод бисекций Похож на метод ветвей и границ


Slide 26

27


Slide 27

Нахождение хорошего рекорда Использование локальных и эвристических методов позволяет найти хороший рекорд и может существенно ускорить процесс нахождения минимума


Slide 28

Задачи с ограничениями: постановка непрерывные Найти:


Slide 29

МНП для задач с ограничениями Допустимая область ограничена Ищется приближенное -решение


Slide 30

Расширение допустимого множества


Slide 31

Оптимизация с ограничениями: основная идея Если - миноранта для j-го ограничения на множестве : то множество можно отбросить как не содержащее допустимых точек.


Slide 32

Оптимизация с ограничениями: основная теорема 33 L2 L3 L4 L5 L6 - совокупность множеств Теорема. Если выполнено то - совокупность -допустимых точек


Slide 33

Учет целочисленности Множество, исключаемое из рассмотрения, расширяется до целочисленных границ


Slide 34

35 Частично целочисленные задачи Требуется минимизировать затраты f(x) на производство при соблюдении технологических ограничений g1-g4.


Slide 35

Результаты расчетов


Slide 36

Метод ветвей и границ ДЕРЕВО ВЕТВЛЕНИЯ ВЕТВЛЕНИЕ ПОДЗАДАЧА ОТСЕЯННАЯ ПОДЗАДАЧА: НЕ ИМЕЕТ РЕШЕНИЙ ОПТИМУМ НАЙДЕН ОПТИМУМ НЕ ЛУЧШЕ РАНЕЕ НАЙДЕННОГО (РЕКОРДА)


Slide 37

Проблемы распараллеливания МВГ дерево ветвления не является сбалансированным; структура дерева ветвления не известна до начала решения задачи и формируется динамически; ГРАФ АЛГОРИТМА


Slide 38

Разбалансировка нагрузки УП РП 1 РП 2


Slide 39

Разделение проблемно-зависимых и независимых частей ПРОБЛЕМНО-НЕЗАВИСИМЫЕ Организация хранения подмножеств и допустимых решений Общая схема вычислений ПРОБЛЕМНО-ЗАВИСИМЫЕ Способ ветвления Правила отсева


Slide 40

Реализация для различных архитектур: повторное использование многопроцессорные с распределенной памятью однопроцессорные многопроцессорные с общей памятью архитектуры методы МВГ для ранца МВГ для коммивояжера МВГ для непрерывной оптимизации КАРКАСЫ


Slide 41

Структура пакета BNB-Solver (С ++) БАЗОВЫЕ ВЫЧИСЛИТЕЛЬНЫЕ ПРИМИТИВЫ БАЗОВЫЕ КОММУНИКАЦИОННЫЕ ПРИМИТИВЫ КАРКАС ДЛЯ ОБЩЕЙ ПАМЯТИ КАРКАС ДЛЯ РАСПРЕДЕЛЕННОЙ ПАМЯТИ МЕТОД НЕРАВНОМЕРНЫХ ПОКРЫТИЙ МВГ ДЛЯ РАНЦА КАРКАС ДЛЯ ПОСЛЕД. АРХИТЕКТУР МВГ ДЛЯ ЗАДАЧИ КОММИВОЯЖЕРА Солвер НЛП для общей памяти СОЛВЕРЫ ПОДСИСТЕМА УПРАВЛЕНИЯ ПАМЯТЬЮ


Slide 42

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


Slide 43

Адаптивная балансировка нагрузки РП выполняет Tb ветвлений, после чего посылает УП (не более) Ts вершин. РП процесс, завершивший обработку назначенной вершины, посылает запрос УП. В ответ УП посылает рабочему процессу одну вершину. РП получает ее и начинает выполнять итерации МНП. Если на УП скапливается более Um вершин, УП посылает сообщение всем РП чтобы они прекратили посылку вершин. Если на УП меньше Lm вершин, то УП посылает сообщение всем РП, чтобы они возобновили посылку вершин. УП РП РП РП РП УП – управляющий процесс, РП – рабочий процесс; Tb – пороговое значение числа ветвлений на рабочем процессе; Ts – пороговое значение числа пересылаемых вершин на управляющий процесс; Um(Lm) – максимальное (минимальное) число вершин на управляющем процессе


Slide 44

ПАРАЛЛЕЛЬНАЯ РЕАЛИЗАЦИЯ МНП Обобщенная функция Розенброка Суперкомпьютер MVS 100K


Slide 45

Современные проблемы МНП Усовершенствование метода Новые способы построения покрытий Ускорение получения рекордов Решение многокритериальных задач


Slide 46

Проблемы эффективной реализации Преодоление 100 TFLOPS: совершенствование балансировки Перенос на гибридные архитектуры (распределенная память + общая память + GPU) Реализация в распределенной среде (BOINC-проекты: [email protected])


Slide 47

Спасибо за внимание!


×

HTML:





Ссылка: