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

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

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

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

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

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

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

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

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

Метод неравномерных покрытий 1.Предложен для безусловной оптимизации в 1971 Ю. Г. Евтушенко, Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке), Ж. вычисл. матем. и матем. физ., 11:6 (1971), 1390– Расширен на случай многих критериев в 1986 Евтушенко Ю. Г., Потапов М. А. «Методы численного решения многокритериальных задач.» ДАН СССР, Т. 291, N 1, 1986, С Расширен на задачи математического программирования в 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 Первая параллельная реализация 2007 Ю. Г. Евтушенко, В. У. Малкова, А. А. Станевичюс. Распараллеливание процесса поиска глобального экстремума. Автоматика и телемеханика, 5. С , Новая техника для задач математического программирования 2011 Ю. Г. Евтушенко, М. А. Посыпкин. Варианты метода неравномерных покрытий для глобальной оптимизации частично-целочисленных нелинейных задач. Доклады Академии наук. Т: С. 168–172.

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

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

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

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

Общий случай: основная теорема 15 L1L1 L2L2 L3L3 L4L4 L5L5 L6L6 - совокупность множеств Теорема. Если выполнено то - совокупность допустимых точек

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

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

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

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

Похож на метод ветвей и границ

27

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

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

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

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

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

Оптимизация с ограничениями: основная теорема 33 L1L1 L2L2 L3L3 L4L4 L5L5 L6L6 - совокупность множеств Теорема. Если выполнено то - совокупность -допустимых точек

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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