Новые эффективные методы и программы для вычислительно-трудоемких задач принятия решений с использованием суперкомпьютерных систем рекордной производительности

Проект Российского научного фонда №16-11-10150 «Новые эффективные методы и программы для вычислительно-трудоемких задач принятия решений с использованием суперкомпьютерных систем рекордной производительности» по приоритетному направлению деятельности РНФ «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами».

Номер государственной регистрации AAAA-A16-116060110025-3 от 01.06.2016.

Цели и задачи проекта

Целью настоящего проекта является разработка интегрированной системы моделей, методов и программных средств для исследования сложных проблем рационального выбора, формулируемых как задачи многокритериальной многоэкстремальной оптимизации. Указанные задачи имеют общий характер и широко распространены в приложениях (оптимальное проектирование, идентификация параметров и др.) и обладают высокой вычислительной трудоемкостью. Коллектив заявителей проекта имеет значительный (более 40 лет) опыт исследований по данному направлению в составе известной в России и за рубежом Нижегородской школы глобальной оптимизации. Участник проекта В.В. Торопов (в настоящий момент – профессор School of Engineering and Materials Science, Queen Mary University of London) является признанными в Великобритании специалистом в области решения сложных задач оптимального выбора. В.В. Торопов – выпускник ННГУ им. Н.И. Лобачевского, с 1983 по 1992 год – доцент ННГУ.

Достижение заявленной цели проекта подразумевает разработку комплекса математических моделей, методов и программных средств, охватывающих как известные, так и новые постановки задач оптимизации (с частично вычислимыми, не всюду определенными, разрывными функционалами). Основной особенностью разрабатываемых моделей будет возможность изменения постановок проблемы выбора в процессе вычислений. Все разработанные алгоритмы будут теоретически обоснованы и экспериментально апробированы при решении тестовых и прикладных задач. Разработанные методы и их программная реализация позволят существенно повысить сложность решаемых оптимизационных задач.

В результате выполнения проекта будет разработан прототип параллельной программной системы для решения задач оптимального выбора. Указанная программная система будет ориентирована на работу в суперкомпьютерных системах. Научные результаты, полученные в ходе выполнения проекта, будут внедрены как в образовательный процесс ННГУ (разработка специальных курсов для магистратуры), так и в систему подготовки высококвалифицированных кадров (разработка программ повышения квалификации).

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

Коллектив исполнителей

  • Гергель Виктор Павлович – руководитель проекта, доктор технических наук, директор Института информационных технологий, математики и механики ННГУ им. Н.И. Лобачевского.
  • Торопов Василий Владимирович – основной исполнитель проекта, профессор, Queen Mary University of London.
  • Стронгин Роман Григорьевич – основной исполнитель проекта, доктор физико-математических наук, президент ННГУ им. Н.И.Лобачевского.
  • Сысоев Александр Владимирович – участник проекта, кандидат технических наук, доцент, ННГУ им. Н.И.Лобачевского.
  • Баркалов Константин Александрович – участник проекта, кандидат физико-математических наук, доцент, ННГУ им. Н.И.Лобачевского.
  • Козинов Евгений Александрович – участник проекта, ассистент, ННГУ им. Н.И.Лобачевского.
  • Лебедев Илья Генадьевич — участник проекта, аспирант, ННГУ им. Н.И.Лобачевского.
  • Горячих Алексей Сергеевич – участник проекта, аспирант, ННГУ им. Н.И.Лобачевского.
  • Соврасов Владислав Валерьевич – участник проекта, аспирант, ННГУ им. Н.И.Лобачевского.
  • Кочеганова Мария Анатольевна – участник проекта, ассистент, ННГУ им. Н.И.Лобачевского.

Публикации по проекту

Первый этап (2016 год)

  1. Баркалов К.А., Николаев К.А. Распределение вычислительной нагрузки при параллельном решении серии задач оптимизации Суперкомпьютерные дни в России: Труды международной конференции (26-27 сентября 2016 г., г. Москва)  
  2. Gergel V.P., Kozinov E.A. Accelerating multicriterial optimization by the intensive exploitation of accumulated search data AIP Conference Proceedings  
  3. Гергель В.П., Козинов Е.А. Параллельные вычисления при поиске эффективных вариантов в задачах многокритериальной оптимизации Суперкомпьютерные дни в России: Труды международной конференции (26-27 сентября 2016 г., г. Москва)
  4. Gergel V.P., Kozinov E.A., Linev A.V., Shtanyk A.A. Educational and Research Systems for Evaluating the Efficiency of Parallel Computations Lecture Notes in Computer Science  
  5. Gergel V.P., Kustikova V.D. Internet-Oriented Educational Course «Introduction to Parallel Computing» Communications in Computer and Information Science 
  6. Гергель В.П., Кустикова В.Д. Интернет-ориентированный учебный курс «Основы параллельных вычислений»: понятно о сложном Суперкомпьютерные дни в России: Труды международной конференции (26-27 сентября 2016 г., г. Москва)  
  7. Zhbanova A.S. Development of Parallel Block Multistage Scheme of Dimension Reduction for Globalizer Lite Parallel Software System Procedia Computer Science  
  8. Sovrasov V.V. Local Tuning in Peano Curves-based Global Optimization Scheme Procedia Computer Science 
  9. Strongin R.G., Barkalov K.A., Nikolaev K.A. New approach to parallel solving a set of global optimization problems AIP Conference Proceedings 
  10. Toropov V.V., Ollar J., Jones R.D. Sub-space Metamodel-based Multidisciplinary Optimization of an Aircraft Wing subjected to Bird Strike AIAA SciTech-2017 

Второй этап (2017 год)

  1. Barkalov K.A., Lebedev I.G. Comparing Two Approaches for Solving Constrained Global Optimization Problems Lecture Notes in Computer Science
  2. Barkalov K.A., Lebedev I.G. Parallel Algorithm for Solving Constrained Global Optimization Problems Lecture Notes in Computer Science 
  3. Баркалов К.А., Лебедев И.Г. Исследование масштабируемости алгоритма глобальной оптимизации на классе задач варьируемой сложности Суперкомпьютерные дни в России: Труды международной конференции (25-26 сентября 2017 г., г. Москва). – М.: Изд-во МГУ, 2017. – 904 c.  
  4. Barkalov K.A., Strongin R.G. Solving a set of global optimization problems by the parallel technique with uniform convergence Journal of Global Optimization 
  5. Barkalov K.A., Strongin R.G. Test Problems for Parallel Algorithms of Constrained Global Optimization Lecture Notes in Computer Science  
  6. Gergel V.P. An Approach for Generating Test Problems of Constrained Global Optimization Lecture Notes in Computer Science  
  7. Gergel V.P., Goryachih A.S. Global Optimization Using Numerical Approximations of Derivatives Lecture Notes in Computer Science   
  8. Gergel, V., Kozinov, E. Accelerating Parallel Multicriterial Optimization Methods Based on Intensive Using of Search Information Procedia Computer Science  
  9. Gergel, V., Kozinov, E. Efficient methods of multicriterial optimization based on the intensive use of search information Springer Proceedings in Mathematics and Statistics
  10. Gergel, V., Kozinov, E. Parallel computing for time-consuming multicriterial optimization problems Lecture Notes in Computer Science
  11. Goryachih A.S. A Class of Smooth Modification of Space-Filling Curves for Global Optimization Problems Springer Proceedings in Mathematics and Statistics 
  12. Калюлин С.Л., Модорский В.Я., Баркалов К.А., Гергель В.П., Лаптева Ю.А., Козинов Е.А. Интеграция программных комплексов Globalizer и Ansys для оптимизации процессов охлаждения капли в потоке газа Научно-технический вестник Поволжья  
  13. Kalyulin S.L.,Shavrina E.V., Modorskii, V.Y., Barkalov K.A., Gergel V.P. Optimization of Drop Characteristics in a Carrier Cooled Gas Stream Using ANSYS and Globalizer Software Systems on the PNRPU High-Performance Cluster Communications in Computer and Information Science  
  14. Коледина К.Ф., Сысоев А.В., Губайдуллин И.М., Ахметов А.Ф., Зайнуллин Р.З., Гергель В.П. Многомерный алгоритм глобального поиска при решении обратной кинетической задачи и его параллельная схема Параллельные вычислительные технологии – XI международная конференция, ПаВТ’2017, г. Казань, 3–7 апреля 2017 г. Челябинск: Издательский центр ЮУрГУ, 2017. 552 с.
  15. Korolev Y.M., Toropov V.V., Shahpar S. Design Optimization Under Uncertainty Using the Multipoint Approximation Method IAA/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference   
  16. Ollar J., Mortished Ch., Jones R., Sienz J., Toropov V.V. Gradient based hyper-parameter optimisation for well conditioned kriging metamodels Structural and Multidisciplinary Optimization 
  17. Sovrasov V.V. Parallel Multi-Objective Optimization Method for Finding Complete Set of Weakly Efficient Solutions CEUR Workshop Proceedings 
  18. Sysoyev A.V., Barkalov K.A., Lebedev I.G., Sovrasov V. V., Gergel, V.P. Solving Time-Consuming Global Optimization Problems with Globalizer Software System Communications in Computer and Information Science   
  19. Sysoyev A.V., Barkalov K.A., Sovrasov V.V., Lebedev I.G., Gergel V.P. Globalizer – A Parallel Software System for Solving Global Optimization Problems Lecture Notes in Computer Science
  20. Sysoyev A.V., Zhbanova A.S., Barkalov K.A., Gergel V.P. Globalizer Lite: A Software System for Solving Global Optimization Problems Communications in Computer and Information Science 

Третий этап (2018 год)

  1. Баркалов К.А., Гергель В.П. Высокопроизводительные вычисления в задачах глобальной оптимизации. Сборник трудов конференции ИТНТ-2018.
  2. Gergel V.P., Barkalov K.A., Kozinov E.A.,Toropov V.V. Parallel Multipoint Approximation Method for Large-Scale Optimization Problems. Communications in Computer and Information Science
  3. Gergel V., Barkalov K., Sysoyev A. A novel supercomputer software system for solving time-consuming global optimization problems. Numerical Algebra, Control and Optimization
  4. Gergel V., Kozinov E. Efficient multicriterial optimization based on intensive reuse of search information. Journal of Global Optimization
  5. Candelieri A., Giordani I., Archetti F., Barkalov K., Meyerov I., Polovinkin A., Sysoyev A., Zolotykh N. Tuning hyperparameters of a SVM-based water demand forecasting system through parallel global optimization Computers and Operations Research
  6. Raheel M., Toropov V. Topology optimization of an aircraft wing with an outboard X-stabilizer. Multidisciplinary Analysis and Optimization Conference
  7. Sovrasov V.V. Comparison of dimensionality reduction schemes for derivative-free global optimization algorithms. Procedia Computer Science
  8. Strongin R.G., Gergel V.P., Barkalov K.A., Sysoyev A.V. Generalized Parallel Computational Schemes for Time-Consuming Global Optimization Lobachevskii Journal of Mathematics
  9. Toropov V., Korolev Y., Barkalov K., Kozinov E., Gergel V. HPC Implementation of the Multipoint Approximation Method for Large Scale Design Optimization Problems Under Uncertainty. Proceedings of the 6th International Conference on Engineering Optimization

Четвертый этап (2019 год)

  1. Barkalov K.A., Lebedev I.G. Parallel Global Optimization for Non-Convex Mixed-Integer Problems // Communications in Computer and Information Science
  2. Gergel V.P., Grishagin V.A., Israfilov R.A. Adaptive Dimensionality Reduction in Multiobjective Optimization with Multiextremal Criteria // Lecture Notes in Computer Science 
  3. Gergel V.P., Grishagin V.A., Israfilov R.A. Parallel Dimensionality Reduction for Multiextremal Optimization Problems // Lecture Notes in Computer Science
  4. Gergel V.P., Kozinov E.A. A Highly Parallel Approach for Solving Computationally Expensive Multicriteria Optimization Problems // Communications in Computer and Information Science
  5. Gergel V.P., Kozinov E.A. Comparative Analysis of Parallel Computational Schemes for Solving Time-Consuming Decision-Making Problems // Communications in Computer and Information Science
  6. Sovrasov V.V. Comparison of Several Stochastic and Deterministic Derivative-Free Global Optimization Algorithms // Lecture Notes in Computer Science
  7. Barkalov K.A., Lebedev I.G. Adaptive Global Optimization Based on Nested Dimensionality Reduction // Advances in Intelligent Systems and Computing
  8. Gergel V.P., Kozinov E.A. Multistage Global Search Using Various Scalarization Schemes in Multicriteria Optimization Problems // Advances in Intelligent Systems and Computing

Пятый этап (2020 год)

  1. Barkalov K.A., Lebedev I.G., Kocheganova M.A., Gergel V.P. Combining Local and Global Search in a Parallel Nested Optimization Scheme // Communications in Computer and Information Science
  2. Barkalov K.A., Lededev I.G., Toropov V.V. Adaptive Global Optimization Using Graphics Accelerators // Communications in Computer and Information Science
  3. Gergel V.P., Grishagin V.P., Israfilov R.A. Multiextremal Optimization in Feasible Regions with Computable Boundaries on the Base of the Adaptive Nested Scheme // Lecture Notes in Computer Science
  4. Gergel V.P., Kozinov E.A. Multilevel Parallel Computations for Solving Multistage Multicriteria Optimization Problems // Lecture Notes in Computer Science
  5. Gergel V.P., Kozinov E.A. Parallel Computations for Various Scalarization Schemes in Multicriteria Optimization Problems // Lecture Notes in Computer Science
  6. Strongin R.G., Barkalov K.A., Bevzuk S.A. Acceleration of Global Search by Implementing Dual Estimates for Lipschitz Constant // Lecture Notes in Computer Science
  7. Strongin R.G., Barkalov K.A., Bevzuk S.A. Global optimization method with dual Lipschitz constant estimates for problems with non-convex constraints // Soft Computing
  8. Соврасов В.В., Баркалов К.А. Параллельный алгоритм для получения равномерного приближения решений множества задач глобальной оптимизации с нелинейными ограничениями // Вестник Южно-Уральского Государственного Университета
  9. Баркалов К.А., Усова М.А. Параллельный алгоритм минимизации многоэкстремальных функций, имеющих разрывы // Параллельные вычислительные технологии (ПаВТ’2020). Короткие статьи и описания плакатов.

Основные результаты

Направление 1. Разработка и исследование новых математических моделей задач оптимального выбора и методов их решения.

В данной части работ по проекту были выполнены исследования по разработке общей математической модели рационального выбора, которая позволяла бы осуществлять адекватное моделирование процессов принятия решений для самых сложных задач выбора оптимальных вариантов.

Во многих прикладных задачах крайне затруднительно определение одного единственного критерия эффективности для сравнения различных выбираемых вариантов. Тем самым, для адекватного формального описания рассмотренных ситуаций выбора необходимо использование постановок многокритериальных задач оптимизации (МКО), в которых оценка качества выбираемых вариантов осуществляется с помощью векторного критерия эффективности.

Принципиальной особенностью задач многокритериальной оптимизации является возможная противоречивость частных критериев эффективности, в результате чего достижение оптимальных (наилучших) значений одновременно по всем частным критериям является невозможным. Как правило, улучшение показателей эффективности по одним частным критериям приводит к ухудшению качества выбираемых вариантов по другим критериям. В таких ситуациях решение задачи МКО состоит в нахождении некоторых компромиссных вариантов, в которых согласовано достижение наилучших значений по отдельным частным критериям. Важно отметить, что в ходе вычислений может измениться представление о целесообразном компромиссе, что может потребовать последовательное нахождение нескольких различных эффективных решений – в предельном случае, всего множества неулучшаемых вариантов (области Парето).

В рамках выполненных работ по проекту была предложена общая математическая модель выбора оптимальных вариантов, которая объединяет основной набор частных постановок оптимизации (с линейными, выпуклыми и невыпуклыми функционалами). Данная модель состоит в следующем.

  1. Перед началом решения проблемы выбора формулируется модель объекта оптимизации, включающая набор варьируемых параметров, область их возможных значений и вектор-функцию характеристик оптимизируемого объекта. Предполагается, что характеристики объекта могут быть многоэкстремальными и для их определения может потребоваться большой объем вычислений. Также предполагается, что в процессе вычислений модель объекта оптимизации остается постоянной и не изменяется.
  2. Далее на основе модели объекта формулируется задача многокритериальной оптимизации, включающая векторный критерий эффективности, вектор-функцию ограничений и область изменения параметров. Предложенная схема охватывает многие существующие постановки оптимизационных задач. При единственном критерии и отсутствии ограничений данная общая постановка становится задачей глобальной оптимизации. При единственном критерии и наличии ограничений общая постановка приводится к задаче нелинейного программирования.
  3. В ходе решения проблемы выбора задача МКО, сформированная на этапе 2, может быть скорректирована при изменении представлений об оптимальности. Для этого отдельные частные критерии могут быть переведены в ограничения и, наоборот, часть ограничений могут быть переведены в ограничения, допуска на ограничения могут быть усилены или ослаблены и т.д. Возможность такой вариации позволяет более точно определить требования к оптимальности.

Тем самым, в рамках предложенного подхода процесс выбора оптимального варианта представляет собой многоэтапную процедуру, в которой на каждом этапе проводится последовательное уточнение постановки задачи МКО и последующего решения этих задач. Разработанный подход позволяет говорить о формировании нового класса задач многократного многокритериального глобального поиска (ММГП), порождаемых при решении сложных проблем оптимального выбора.

Результаты отражены в работах [2, 18, 19].

Направление 2. Реализация схем повторного использования накопленной поисковой информации, получаемой в процессе решения задачи оптимального выбора.

Широко используемый способ указания желаемых компромиссных вариантов состоит в скаляризации векторного критерия задачи МКО, когда частные критерии комбинируются (свертываются) в единый обобщенный критерий эффективности. При таком подходе коэффициенты свертки могут рассматриваться как показатели важности частных критериев – чем больше значение коэффициента какого-либо критерия, тем больше вклад этого частного критерия в общий скалярный критерий.

Необходимость нахождения нескольких (или всего множества) эффективных вариантов существенно повышает сложность вычислений при решении задач МКО. Кроме того, частные критерии могут иметь сложный многоэкстремальный вид, а вычисление значений критериев может оказаться вычислительно трудоемким. В таких условиях нахождение даже одного компромиссного варианта требует значительных вычислительных затрат, определение же нескольких (или всего множества) эффективных вариантов становится проблемой исключительной вычислительной сложности. В рамках выполнения проекта для преодоления вычислительной сложности задач МКО был предложен подход, основанный на повторном использовании поисковой информации.

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

Отметим, что в поисковой информации запоминаются вычисленные значения частных критериев исходной задачи МКО. Наличие подобной информации позволяет привести текущие значения скалярного критерия к значениям критерия очередной скалярной подзадачи при переходе к новым значениям коэффициентов свертки, не прибегая к повторным трудоемким вычислениям значений частных критериев. В результате подобного пересчета при переходе к решению очередной скалярной подзадачи накопленная ранее поисковая информация может использоваться алгоритмами многократного глобального поиска без каких-либо трудоемких вычислений. При этом объем поисковой информации будет постоянно пополняться по мере решения отдельных частных скалярных подзадач. Наличие поисковой информации большого объема будет способствовать сокращению количества итераций глобального поиска, необходимого для достижения условия остановки.

Доказано, что построенный алгоритм является устойчивым. А именно, при переходе от решения одной скалярной подзадачи при некоторых коэффициентах свертки к решению очередной подзадачи при иных коэффициентах свертки значение критерия в точке глобального минимума будет отличаться от известного значения из предыдущей задачи лишь на некоторую величину, зависящую от константы Липшица скалярной функции. Одновременно с этим дана верхняя оценка числа итераций, требующихся для решения очередной скалярной подзадачи. Данная оценка показывает, что при достижении достаточно высокой плотности испытаний в интервалах области поиска за счет повторного использования поисковой информации при решении очередных подзадач количество дополнительных итераций будет постоянно уменьшаться. Проведены вычислительные эксперименты на суперкомпьютере «Лобачевский», подтверждающие теоретические положения. Так, даже при решении задач МКО сравнительно невысокой размерности с помощью последовательного алгоритма достигается сокращение количества итераций в 8-10 раз. При использовании же параллельных алгоритмов эффект становится еще более существенным – при использовании всего 25 вычислительных ядер ускорение становится больше 220. Результаты представлены в публикациях [20, 35].

Направление 3. Исследование моделей и методов организации параллельных вычислений для задач оптимального выбора, применимых на суперкомпьютерных системах.

Обычно существующие методы (как последовательные, так и параллельные) предназначены для решения одной, выделенной оптимизационной задачи. Если же требуется решить некоторую серию из q задач, то задачи из данной серии решаются одна за другой, последовательно. Тем самым, оценка оптимума в i-й задаче серии является неопределенной до момента полного решения всех предшествующих ей задач с номерами 1, 2, …, i-1. В случае ограниченности вычислительных ресурсов оценки оптимума в задачах i+1, …, q не будут получены, если исчерпание вычислительного ресурса произойдет при решении i-й задачи.

Целью проведенных работ являлась разработка метода параллельного решения серии задач глобального поиска, который обеспечивал бы равномерную сходимость к решениям всех задач серии. Результаты выполненных исследований состоят в следующем.

Предложен новый метод для решения серии задач оптимизации как развитие многомерного обобщенного алгоритма глобального поиска, разработанного ранее Р.Г. Стронгиным. Решающие правила метода были модифицированы таким образом, чтобы сохранились все его ранее доказанные свойства, и одновременно метод можно было бы применять для решения нескольких задач одновременно. В отличие от традиционной схемы распределения задач между процессорами/ядрами (при которой может возникать дисбаланс вычислительной нагрузки), разработанный алгоритм позволяет адаптивно управлять нагрузкой на процессоры, обеспечивая 100% загрузку системы.

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

Проведены вычислительные эксперименты на суперкомпьютере «Лобачевский», подтверждающие доказанные теоретические свойства. Результаты экспериментов также показали, что разработанный алгоритм, одновременно с равномерной сходимостью к решениям серии задач, обеспечивает и равномерную вычислительную загрузку задействованных процессоров.

Для решения задач оптимального выбора экзафлопсного уровня вычислительной сложности предложена общая вычислительная схема параллельных алгоритмов. Разработанный подход включает схему конкурентных параллельных вычислений для вычислительных систем с общей памятью, распределенных параллельных вычислений с использованием множественных отображений для редукции размерности и многоуровневую декомпозицию параллельных вычислений для суперкомпьютерных вычислительных систем рекордной производительности. Одновременно с использованием общей и распределенной памяти проработана схема использования ускорителей вычислений на основе сопроцессоров Intel Xeon Phi и графических ускорителей.

В целом, предложенная вычислительная схема обеспечивает возможность эффективного применения для решения сверхсложных задач глобальной оптимизации суперкомпьютерных вычислительных систем с большим количеством (десятки и сотни тысяч) ядер/процессоров. Кроме того, данная общая схема может быть использована для организации параллельных вычислений для широкого спектра алгоритмов решения вычислительно-трудоемких задач оптимального выбора (в частности, для характеристически-представимых алгоритмов). Выполненные вычислительные эксперименты подтверждают перспективность предложенного подхода. Так, например, были проведены эксперименты, в которых одновременно использовалось 32 вычислительных узла суперкомпьютера, на каждом из которых было установлено по 3 ускорителя NVIDIA Kepler K20Х (2688 потоковых процессора). Таким образом, всего было задействовано более 250 тысяч вычислительных ядер с суммарной производительностью 115.8 TFlop/s.

Результаты представлены в серии публикаций [1, 9, 14, 39, 43].

Направление 4. Развитие методов решения многопараметрических задач оптимального выбора с трудоемкими критериями, основанных на построении аппроксимаций функций задачи.

В данной части работ проводились исследования по возможности применения полученных теоретических результатов при решении прикладных задач оптимального проектирования. Одной из ключевых проблем данного направления работ является высокая размерность сложных задач оптимального проектирования, для решения которых характерен значительный объем вычислений.

Исследуемый метод основан на новом способе построения аппроксимаций функций, предложенном В.В. Тороповым и получившим название «Метод многоточечной аппроксимации» (multipoint approximation method, MAM). В задачах с числом переменных порядка 100 метод МАМ подтвердил свою эффективность (результаты решения прикладных задач представлены в работах В.В. Торопова 2010-х годов). Данный метод является итерационным и основан на решении серии вспомогательных задач, построенных в доверительной области. Доверительная область представляет собой подобласть исходной области изменения параметров, в которой вычислены значения критериев и ограничений на некотором наборе точек. Данное множество значений (а также некоторое подмножество значений, вычисленных на предыдущих итерациях) используется для построения метамоделей критериев и ограничений, которые считаются корректными в рамках данной доверительной области. На следующей итерации поиска размер и положение доверительной области может измениться, обеспечивая сходимость к решению задачи.

Предложенный метод построения аппроксимаций был апробирован при решении ряда тестовых задач. Тестовые примеры были как с аналитической формулировкой (для проверки методологии и корректности реализации), так и в форме задач оптимизации со вычислительно-трудоемким критерием, моделирующих реальные приложения [10].

В качестве дальнейшего развития данного направления были разработаны новые способы построения аппроксимаций исходных функций задачи, основанные на идеях кригинга. Также была предложена стратегия изменения доверительной области, которая может учитывать численные погрешности и случайные сбои в процессе моделирования, необходимого для вычисления значений критериев и ограничений.

Была реализована параллельная версия метода многоточечной аппроксимации (Parallel MAM, PMAM), способная за приемлемое время решать задачи с числом параметров порядка 1000. В процессе разработки были проанализированы различные способы распараллеливания, которые можно применить для рассматриваемого метода.

Во-первых, можно распараллеливать вычисление функций, описывающих оптимизируемый объект. Данный путь является как очевидным, так и необходимым, т.к. в задачах оптимального проектирования расчет даже одного значения функции может занимать несколько часов. Однако данный способ является специфичным для каждой конкретной задачи. Вопросы распараллеливания тут решаются на уровне пакетов прикладных программ, в которых выполняется инженерное моделирование (например, Ansys, OpenFOAM, и т.п.).

Во-вторых, можно скорректировать алгоритм с целью параллельного вычисления нескольких значений целевой функции и ограничений в разных точках области поиска. В соответствии с правилами MAM на каждой итерации в текущей доверительной области формируется набор точек, значения функций в которых можно вычислять параллельно на разных процессорах (узлах). Данный способ был успешно реализован в работах В.В. Торопова и показал хорошую эффективность, т.к. при числе параметров порядка ста основное время затрачивается на вычисление значений функций задачи, работа самого метода MAM (в последовательном режиме) вносит незначительные накладные расходы.

Однако, когда число переменных становится порядка тысячи, работа последовательной части MAM начинает оказывать ощутимое влияние на общее время решения задачи (в предположении, что время вычисления значений целевой функции не меняется). Так, для рассмотренных модельных задач время проведения одной итерации метода увеличилось в более чем 2000 раз (с 4 до 9000 секунд) при увеличении числа переменных в задаче с 100 до 1000. Поэтому в рамках проведенного исследования был реализован третий подход к распараллеливанию алгоритма. Были распараллелены вычислительные правила МАМ, обеспечивающие построение аппроксимации, решение аппроксимированной задачи и выбор следующей доверительной области.

Перспективные результаты были получены при применении метода многоточечной аппроксимации к задачам оптимизации c зашумленными параметрами (задачи с неопределенностью). Подобного рода неопределенность возникает в задачах инженерной оптимизации как в случае, когда часть параметров имеет случайную природу, так и в случае детерминированных параметров, значения которых невозможно задать точно (а лишь с некоторой случайной погрешностью). В задачах данного типа предполагается, что функции принимают на вход значение (x+u), где x – точное значение параметра, а u – случайная величина с известным законом распределения (например, распределенная нормально). Была предложена модификация метода MAM, которая может работать с зашумленными параметрами. Данная модификация основана на минимизации меры риска, которая ставит в соответствие функции случайных параметров детерминированную функцию.

С целью выявления наиболее трудоемких мест программной реализации алгоритма были использованы инструменты из пакета Intel Parallel Studio XE, в частности VTune Amplifier. Проведенный анализ показал, что наиболее трудоемкими операциями в реализации MAM являются матричное умножение и решение СЛАУ при построении аппроксимации, а также решение аппроксимированной задачи методом SQP. Матричное умножение и решение СЛАУ являются стандартными операциями, реализованными во многих высокопроизводительных библиотеках. Здесь были использованы соответствующие параллельные методы из библиотеки Intel MKL. Метод SQP был распараллелен самостоятельно с использованием технологии OpenMP. Эффективность распараллеливания была оценена на классической тестовой задаче оптимального проектирования – минимизации объема балки, состоящей из набора прямоугольных элементов. Число параметров варьировалось от 100 до 1000, число ограничений – от 200 до 2000. При использовании одного узла кластера время решения задачи сократилось более чем в пять раз. Отметим, что одновременно с этим методу МАМ требуется на порядок меньше вычислений значений функции и ограничений по сравнению с методом SQP, примененным к исходной (не аппроксимированной) задаче.

Результаты отражены в публикациях [32, 40].

Направление 5. Разработка параллельной программной системы для решения задач оптимального выбора на суперкомпьютерах рекордной производительности.

Разработана параллельная программная система Globalizer, предназначенная для решения задач глобальной оптимизации на современных суперкомпьютерах с гетерогенной архитектурой. Система Globalizer реализует предложенную в рамках проекта общую схему параллельного решения задач глобально-оптимального выбора с использованием широкого спектра вычислительных систем: с общей и распределенной памятью, графическими процессорами NVIDIA и сопроцессорами Intel Xeon Phi.

Разработанная система состоит из следующих основных блоков:

  • Блок вычисления значений функционалов (критериев и ограничений) решаемой задачи оптимизации (осуществляет взаимодействие между внешним вычислителем и Globalizer в соответствии с установленным интерфейсом);
  • Подсистема оптимизации, которая обеспечивает решение задач глобального поиска, нелинейного программирования, многокритериальной оптимизации и общих задач оптимального выбора (обеспечивает последовательную схему взаимодействия реализованных в ней компонент – задачи оптимального выбора решаются с использованием блока многокритериальной оптимизации, который, в свою очередь, использует блок нелинейного программирования, и т.д.);
  • Блок накопления и обработки поисковой информации, получаемой в процессе вычислений;
  • Блок редукции размерности (использует комбинированную схему, сочетающую редукцию размерности с использованием кривых, заполняющих пространство, и редукцию по схеме вложенной оптимизации);
  • Блок управления параллельными процессами при выполнении глобального поиска (обеспечивает, в том числе, распределение процессов между вычислительными элементами, проводит балансировку вычислительной нагрузки, и т.п.);
  • Подсистема диалогового взаимодействия с пользователем для постановки исходной задачи оптимизации и возможной смены ее постановки, настройки параметров используемых методов, визуальной демонстрации процесса поиска;
  • Набор средств для визуальной демонстрации результатов глобального поиска (позволяет обеспечить наглядное представление результатов глобального поиска пользователю).

Отличительной особенностью системы Globalizer является эффективное использование ресурсов современных суперкомпьютерных систем – данная ключевая характеристика системы подтверждается, в частности, выполненными вычислительными экспериментами с использованием более 250 тысяч вычислительных ядер.

Система Globalizer может использоваться в двух вариантах:

  • Вариант Globalizer Pro является исследовательской версией системы, обеспечивает полный набор возможностей и ориентирован на решение наиболее сложных задач оптимального выбора.
  • Вариант Globalizer Lite представляет собой ограниченную версию системы, доступен для свободного использования для решения задач среднего уровня сложности.

Описание программной системы представлено в серии публикаций [7, 28, 29, 30, 34].

Направление 6. Решение модельных и прикладных задач оптимального выбора для практической апробации разработанной программной системы

Классический подход к проведению вычислительных экспериментов для оценки эффективности оптимизационных алгоритмов основан на решении этими методами множества модельных задач, выбираемых случайным образом из некоторого сконструированного класса. Решение множества задач позволяет оценивать операционные характеристики методов (вероятности корректного определения глобального экстремума за заданное число шагов поиска) и, тем самым, характеризовать эффективность каждого конкретного алгоритма. В рамках выполнения проекта было предложено два новых подхода к построению модельных задач условной глобальной оптимизации.

Подход 1. Как правило, известные генераторы порождают задачи без ограничений. Поэтому представляет интерес разработка генератора тестовых задач условной глобальной оптимизации. Была предложена схема, позволяющая построить генератор G, порождающий задачи с m ограничениями, на основе заданного способа генерации функций F. Разработанный генератор задач позволяет формировать задачу условной глобальной оптимизации таким образом, что:

  • можно регулировать объем допустимой области по отношению ко всей области изменения параметров;
  • точка глобального минимума целевой функции с учетом ограничений известна заранее;
  • глобальный минимум целевой функции без учета ограничений находится вне допустимой области (с целью имитации поведения ограничений и целевой функции в прикладных задачах условной оптимизации).

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

Разработанные классы тестовых задач были использованы при проведении вычислительных экспериментов на суперкомпьютере «Лобачевский». Результаты экспериментов показали хорошее (близкое к линейному) ускорение процесса решения задач глобальной оптимизации на суперкомпьютерных системах. Описание разработанных генераторов тестовых задач представлено в [15, 16, 33]. Результаты суперкомпьютерных экспериментов на разработанных классах тестовых задач опубликованы в [11,12,13].

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

В решаемой задаче предполагается, что система состоит из подвижного основания и закрепленного на нем посредством виброизолятора объекта защиты. Виброизолятор представляет собой многомассовую механическую систему, состоящую из нескольких материальных точек, связанных гасящими вибрации элементами. Цель решения задачи заключается в определении количества гасящих вибрацию элементов и их расположения с точки зрения стоимости и качества гашения колебаний. Математической моделью механической системы является система дифференциальных уравнений с управлением. Для поиска оптимального управления формулируются несколько критериев и ставится задача многокритериальной оптимизации.

Поставленная задача многокритериальной оптимизации была решена с использованием алгоритмов, разработанных в рамках выполнения проекта. Найдено 50 недоминируемых решений, каждое из которых соответствует одному из возможных управлений. Выбор конкретного управления позволяет предложить конфигурацию виброизолирующего устройства, сохраняющего целостность объектов, находящихся в зонах риска.

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

Современные водопроводные сети большого города представляют собой сложную систему, управление которой требует решения многих задач принятия решений. Одной из подобных задач является оптимизация работы насосов с целью снижения затрат энергии при одновременном удовлетворении спроса на воду. В случае, если в сети есть резервуары для хранения воды, то снижение издержек может быть достигнуто за счет планирования работы большей части насосов в течение временных окон, соответствующих низкой цене электроэнергии, и использования хранимой воды в оставшиеся часы дня.

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

В проведенном исследовании рассматривалась задача оптимизации параметров системы прогнозирования, в которой решается задача восстановления SVM-регрессии с ядром, использующим радиальные базисные функции. Данная задача является задачей глобальной оптимизации с целевой функцией вида «черный ящик»; и для ее решения была использована разработанная в рамках проекта система Globalizer. Результаты показали ускорение расчетов от 9 до 16 раз при использовании одного узла вычислительного кластера по сравнению с аналогичным расчетом, выполненным в последовательном режиме. 

Другие примеры решенных прикладных оптимизационных задач представлены в [22,23,24].

 

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

Во-первых, во многих прикладных задачах встречается ситуация, когда некоторые из параметров характеризуются дискретностью (в частности, целочисленностью). Целочисленные параметры имеют, как правило, небольшое число значений и могут определять, например, марку используемого материала, вариант типовой компоновки деталей и т.п.

Для оценки перспектив обобщения разработанных в рамках проекта алгоритмов на задачи с частично-целочисленными параметрами было проведено предварительное исследование. Был предложен способ учета целочисленности параметров, основанный на построении и одновременном решении множества задач, каждая из которых соответствует своему набору дискретных параметров. Разработан соответствующий модуль в системе Globalizer. Экспериментальное сравнение с известными алгоритмами решения задач многоэкстремальной оптимизации с частично-целочисленными параметрами, реализованными в MATLAB Global Optimization Toolbox, показало перспективность предложенного подхода. 

Во-вторых, для широкого класса задач аппроксимации можно предположить, что трудоемкость вычисления функций задачи, а также вид функции (многоэкстремальная, унимодальная) зависят от выбора конкретного набора компонент вектора параметров. В этом случае в задаче можно выделить связанные между собой «вычислительно-сложную» и «вычислительно-легкую» части. Тогда решение «сложной» части задачи (для которой требуется реализация трудоемких вычислительных алгоритмов для проведения испытаний) можно провести на центральном процессоре (CPU), использовав эффективные методы глобальной оптимизации. «Легкую» же часть задачи (реализация которой не требует сложных алгоритмов и легко портируется на быстрые процессоры специального назначения) можно решить на графических процессорах (GPU) с использованием простых алгоритмов, обеспечивающих всюду плотное покрытие области поиска. Очевидно, что при этом на GPU будет проведено значительно больше испытаний, чем на CPU, но из-за различия в сложности подзадач, решаемых на разных устройствах, ожидается ускорение алгоритма в целом. 

В-третьих, важным является направление исследований, связанное с минимизацией функций, имеющих разрывы. Разработанные при выполнении проекта методы многоэкстремальной многокритериальной оптимизации существенным образом используют предположение об ограниченности разностей значений функций задачи некоторой мерой разности соответствующих значений их аргументов. Однако в ряде прикладных задач данное предположение может нарушаться, а точнее, выполняться не во всей области изменения параметров.

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

Наконец, перспективным направлением продолжения исследований является обобщение разработанных методов многопараметрической оптимизации с использованием аппроксимаций функций для решения задач многодисциплинарной топологической оптимизации. Задачи данного класса характеризируются:

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

Указанные особенности задач многодисциплинарной топологической оптимизации делают возможным обобщение параллельного метода многоточечной аппроксимации, разработанного в рамках проекта, для решения подобных задач за время, приемлемое в практических приложениях.

Пример решенной задачи топологической оптимизации рассмотрен в статье В.В. Торопова. Рассматривалась задача оптимизации формы крыла самолета с x-образным стабилизатором. Критические нагрузки на крыло были рассчитаны с помощью трудоемкого CFD-моделирования. В результате проведенного расчета была предложена форма крыла с x-образным стабилизатором, обеспечивающая минимальный вес при ограничениях на прочность конструкции при всех видах нагрузки, испытываемых в полете.

В целом по итогам выполнения проекта подготовлено 36 публикаций в изданиях, индексируемых Web Of Science и/или Scopus, 7 публикаций, индексируемых РИНЦ. Результаты докладывались на 18 международных научных конференциях, в том числе:

  • International Conference on Computational Science (2017 – Цюрих, Швейцария).
  • Russian Supercomputing Days (2016, 2017, 2018 – Москва).
  • Parallel Computational Technologies (2017 – Казань, 2018 – Ростов-на-Дону).
  • Parallel Computing Technologies (2017 – Н.Новгород).
  • Multidisciplinary Analysis and Optimization (2017 – Атланта, США).
  • International Conference on Engineering Optimization (2018 – Лиссабон, Португалия).
  • Learning and Intelligent Optimization (2017 – Н.Новгород, 2018 – Каламата, Греция).
  • Young Scientists Conference in Computational Science (2016 – Краков, Польша, 2017 – Котка, Финляндия, 2018 – Ираклион, Греция).
  • International Workshop on Global Optimization (2018 – Лейден, Нидерланды).