Проект РНФ
Конкурс РНФ:
Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами.
Проект:
Новые эффективные методы и программы для вычислительно-трудоемких задач принятия решений с использованием суперкомпьютерных систем рекордной производительности
Руководитель проекта:
Гергель Виктор Павлович, директор института ИТММ, д.т.н., проф.
Цель проекта
Целью проекта является разработка интегрированной системы моделей, методов и программных средств для исследования сложных проблем рационального выбора, формулируемых как задачи многокритериальной многоэкстремальной оптимизации. Указанные задачи имеют общий характер и широко распространены в приложениях (оптимальное проектирование, идентификация параметров и др.) и обладают высокой вычислительной трудоемкостью.
Отличительными особенностями проблем рационального выбора, на исследование которых ориентирован предлагаемый проект, являются следующие принципиальные моменты:
- Допустимость изменения постановки задач многокритериальной многоэкстремальной оптимизации в процессе поиска оптимальных вариантов, когда может потребоваться скорректировать набор критериев и ограничений, варьируемых параметров, области поиска и т.п.
- Многоэкстремальность функционалов задач рационального выбора, что является характерным для наиболее сложных (ключевых) проблем выбора оптимальных вариантов в широком спектре научных и технических приложений.
- Существенная вычислительная сложность планируемых к исследованию задач рационального выбора в силу того, что вычисление значений критериев и ограничений осуществляется, как правило, в результате объемного вычислительного анализа сложных математических моделей изучаемых явлений и систем.
Краткая аннотация проекта
Достижение цели проекта подразумевает разработку комплекса математических моделей, методов и программных средств, охватывающих как известные, так и новые постановки задач оптимизации (с частично вычислимыми, не всюду определенными, разрывными функционалами).
Новизна проводимых исследований состоит в разработке параллельных вычислительных схем, эффективно масштабируемых вплоть до использования сотен тысяч вычислительных ядер, значительно расширяющих класс решаемых задач на основе использования вычислительных мощностей суперкомпьютерных систем транспетафлопсного уровня производительности.
Все разработанные при выполнении проекта алгоритмы будут теоретически обоснованы и экспериментально апробированы при решении тестовых и прикладных задач с использованием суперкомпьютера «Лобачевский».
Дополнительная информация о проекте
Значимость решаемой проблемы
Задачи оптимального выбора имеют широкое распространение в научной и технической деятельности человека. Примерами практических задач, в которых необходим оптимальный выбор оптимальных решений, могут служить, например, проблемы автоматизированного проектирования, управления, планирования, и другие подобные задачи.
В задачах оптимального выбора постановки глобальной или многоэкстремальной оптимизации относятся к числу наиболее сложных проблем. В этом случае допускается, что оптимизируемый критерий имеет несколько локальных оптимумов в области поиска, которые имеют различные значения. Наличие нескольких локальных оптимумов существенно усложняет поиск глобального оптимума, так как требует исследования всей допустимой области поиска. Объем вычислений при решении задач глобальной оптимизации может экспоненциально возрастать при увеличении числа варьируемых параметров.
Кроме того, постановки задач глобальной оптимизации используются, как правило, в наиболее трудных ситуациях оптимального выбора, когда проводится, например, автоматизированное проектирование сложных технических объектов, изделий и систем. В таких задачах показатели эффективности в большинстве случаев являются нелинейными, области поиска могут несвязными и, самое главное, вычислительная сложность функционалов, лежащих в основе оптимизируемых критериев и ограничений, может быть очень значительной.
Дополнительным ключевым моментом в задачах оптимального выбора является принципиальная сложность определения одного единственного критерия оптимальности. Как результат, во многих ситуациях оптимального выбора для оценки эффективности сравниваемых вариантов определяется набор частных критериев оптимальности (таких, например, как вес, стоимость, грузоподъемность и т.п.). Данные критерии в большинстве случаев являются противоречивыми, когда улучшение качества принимаемых решение по одному критерию может приводить к ухудшению эффективности по другому критерию (так, например, снижение веса в летальных аппаратах приводит, как правило, к снижению дальности полета). В таких ситуациях, как правило, задаются те или иные коэффициенты важности частных критериев, что позволяет согласовывать вклад каждого частного критерия в итоговое компромиссное решение задачи оптимального выбора. Определение значений коэффициентов важности тоже представляет собой отдельную проблему и, как результат, задачи оптимального выбора часто приходится решать многократно для получения разных компромиссных вариантов выбора.
Ключевые особенности подхода
В основу выполнения проекта положены следующие основные положения.
- Принцип последовательной декомпозиции решаемых задач к решению одной или несколько задач меньшей сложности. В рамках данного подхода:
- Решение задачи выбора оптимальных (наилучших) вариантов сводится к решению одной или нескольких задач многокритериальной оптимизации;
- Решение многокритериальной задачи сводится к решению скалярных задач нелинейного программирования;
- Решение задач нелинейного программирования сводится к решению безусловных задач многоэкстремальной оптимизации.
Такой единый подход позволяет исследовать возникающие оптимизационные задачи в рамках единой теории анализа сходимости и эффективности вычислений. Кроме того, принципиальный момент состоит в том, что все порождаемые семейства задач оптимизации являются информационно связанными и, как результат, при решении каждой очередной задачи оптимизации будет использоваться вся поисковая информация, полученная на всех предыдущих этапах вычислений (это будет приводить, в частности, что решение очередных задач будет требовать постоянно уменьшающего объема вычислений).
- Редукция размерности с использованием разверток Пеано для сведения решения многомерных оптимизационных задач к решению одной или нескольких связанных одномерных задач. Данный подход позволяет существенно снизить остроту проблемы «проклятия размерности» (значительное увеличение объема вычислений при повышении размерности решаемых задач) и является одним из наиболее продуктивным направлением разработки новых эффективных методов многоэкстремальной оптимизации.
- Применение высокопроизводительных параллельных алгоритмов глобального поиска, разработанных в рамках информационно-статистической теории многоэкстремальной оптимизации, которая представляет собой один из ключевых результатов Нижегородской научной школы многоэкстремальной оптимизации. Данные алгоритмы относятся к числу лидирующих по эффективности методов глобального поиска и показали свою высокую продуктивность при решении многих сложных задач многоэкстремальной оптимизации.
Ожидаемые результаты
Основным результатом выполнения проекта будет являться разработка параллельных вычислительных схем, эффективно масштабируемых вплоть до использования сотен тысяч вычислительных ядер, значительно расширяющих класс решаемых задач на основе использования вычислительных мощностей суперкомпьютерных систем нового — транспетафлопсного — уровня производительности.
Достижение основного результата проекта включает разработку следующих моделей, методов и программных средств решения сложных задач оптимального выбора:
- Математическая модель выбора оптимальных (наилучших) вариантов, охватывающая многие известные постановки задач оптимизации. Данный результат представляется значимым, поскольку позволит сформировать единый подход для решения задач выбора вместо использования множества частных постановок.
- Математическая модель процесса поиска оптимальных (наилучших) вариантов, предусматривающая возможность изменения постановки задачи выбора (набора критериев и ограничений, варьируемых параметров, области поиска). Формулирование такой модели позволит более адекватно проводить моделирование процессов поиска оптимальных (неулучшаемых) вариантов в сложных ситуациях выбора.
- Новый подход к решению задач многокритериальной оптимизации с многоэкстремальными критериями и нелинейными ограничениями, позволяющий получать как частные, так и полные оценки множества неулучшаемых (оптимальных по Парето) вариантов. Значимость данного результата состоит в том, что при решении новых возникающих скалярных задач оптимизации будет использоваться поисковая информация, получаемая на всех предшествующих этапах вычислений. Данный подход позволит существенно сократить требуемый объем вычислений, что даст возможность анализа более широкого спектра вариантов для выбора наиболее соответствующих понятию оптимальности.
- Модель информационного сопровождения процесса поиска оптимальных (наилучших) вариантов, обеспечивающая накопление, хранение, эффективную обработку и повторное использование всей получаемой в процессе вычислений поисковой информации. Данный результат является одним из ключевых в рамках проекта, поскольку обеспечивает практическую основу для применимости всех разрабатываемых моделей и методов. Решение даже единственной постановки задачи выбора является чрезвычайно сложной вычислительной проблемой – решение же всех возникающих при изменении постановок задач является полное повторное использование все поисковой информации, получаемой в процессе вычислений.
- Интегрированное семейство методов решения задач многокритериальной многоэкстремальной оптимизации с невыпуклыми ограничениями, допускающие повторное использование имеющейся поисковой информации и которые могут быть эффективно распараллелены для суперкомпьютерных систем с качественно новым уровнем возможного параллелизма (вплоть до миллионов вычислительных устройств). Проблема практического использования вычислительного потенциала современных суперкомпьютерных систем имеет принципиальное значение практически для всего спектра вычислительных наук.
- Схема параллельных вычислений в задачах многокритериальной многоэкстремальной оптимизации, ориентированных на массовый параллелизм для суперкомпьютерных систем нового – транспетафлопсного – уровня производительности. Данный результат относится к числу особо значимых в рамках проекта, поскольку позволит практически использовать колоссальный вычислительный потенциал современных суперкомпьютерных задач. Разработанные модели и методы совместно со схемой организации эффективных параллельных вычислений позволит повысить не менее чем на порядок сложность решаемых задач выбора оптимальных (наилучших) вариантов.
- Интегрированная программная система, реализующая разработанные в рамках проекта модели и методы для решения задач выбора оптимальных (наилучших) вариантов. Новизна создаваемой программные системы состоит прежде всего в ее математическом и алгоритмическом наполнении. Поддерживаемые в результате использования систем процессы поиска оптимальных (наилучших) вариантов будут более адекватно соответствовать теории и практики решения задач выбора. Возможность использования значительного числа вычислительных элементов (вплоть до сотен тысяч вычислительных ядер) представляет значимый результат и будет превышать все достигнутые результаты российскими и зарубежными исследователями в области теории и практики проблем выбора вариантов. Разработанная программная система будет доведена по промышленного использования для решения актуальных практических задач выбора в разных областях приложений (например, в составе систем автоматизированного проектирования).