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

Проект Российского научного фонда № Н-277-2 «Суперкомпьютерные вычисления для интеллектуального глобального поиска в задачах выбора наилучших решений большой вычислительной сложности» по приоритетному направлению деятельности РНФ «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами».

Номер государственной регистрации AAAA-A21-121052800031-5 от 28.05.2021.

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

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

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

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

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

В результате выполнения проекта будут разработаны и исследованы:

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

Планируемые итоги выполнение проекта – модели, методы и программные средства на их основе – обеспечат достижение научно значимого результата: возможность решения задач принятия решений повышенной размерности. Данный результат будет обеспечен на основе синергии разрабатываемого авторами подхода для моделирования и решения сложных задач глобального поиска и методов машинного обучении и искусственного интеллекта. Разработанные программные средства могут быть использованы для решения актуальных задач выбора оптимальных параметров для сложных объектов и процессов, рассмотрение которых ранее не представлялся возможным в силу их большой вычислительной сложности.

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

  • Гергель Виктор Павлович – руководитель проекта (до 01.07.2021), доктор технических наук, профессор, зав. кафедрой программной инженерии института ИТММ, ННГУ им. Н.И. Лобачевского.
  • Баркалов Константин Александрович – руководитель проекта (с 01.07.2021), основной исполнитель проекта, доктор технических наук, доцент, ННГУ им. Н.И.Лобачевского.
  • Квасов Дмитрий Евгеньевич – основной исполнитель проекта, кандидат физико-математических наук, научный сотрудник, ННГУ им. Н.И.Лобачевского.
  • Сысоев Александр Владимирович – основной исполнитель проекта, кандидат технических наук, доцент, ННГУ им. Н.И.Лобачевского.
  • Гришагин Владимир Александрович – основной исполнитель проекта, кандидат физико-математических наук, доцент, ННГУ им. Н.И.Лобачевского.
  • Козинов Евгений Александрович – участник проекта, преподаватель, ННГУ им. Н.И.Лобачевского.
  • Лебедев Илья Генадьевич – участник проекта, программист, ННГУ им. Н.И.Лобачевского.
  • Кудрявцев Евгений Владимирович – участник проекта, преподаватель, ННГУ им. Н.И.Лобачевского.
  • Усова Марина Андреевна – участник проекта, программист, ННГУ им. Н.И.Лобачевского.
  • Карчков Денис Александрович – участник проекта, аспирант института ИТММ, ННГУ им. Н.И.Лобачевского.
  • Кольтюшкина Янина Вадимовна – лаборант, студентка института ИТММ, ННГУ им. Н.И.Лобачевского.
  • Кудрявцев Александр Сергеевич – лаборант, студент института ИТММ, ННГУ им. Н.И.Лобачевского.

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

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

  1. Баркалов К.А., Гергель В.П., Гришагин В.А., Козинов Е.А. (Barkalov K.A, Gergel V.P., Grishagin V.A., Kozinov E.A.) An Approach for Simultaneous Finding of Multiple Efficient Decisions in Multi-objective Optimization Problems Lecture Notes in Computer Science (2021 г.). doi: 10.1007/978-3-030-77876-7_9
  2. Баркалов К.А., Усова М.А, (Barkalov K.A., Usova M.A.) A Search Algorithm for the Global Extremum of a Discontinuous Function Communications in Computer and Information Science (2021 г.). doi: 10.1007/978-3-030-92711-0_3
  3. Губайдуллин И.М., Еникеева Л.В., Баркалов К.А., Лебедев И.Г. (Gubaydullin I.M., Enikeeva L.V., Barkalov K.A., Lebedev I.G.) Parallel Global Search Algorithm for Optimization of the Kinetic Parameters of Chemical Reactions Communications in Computer and Information Science (2021 г.).

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

В 2021 г. при выполнении очередного этапа проекта были получены следующие научные результаты.

1. Разработана модель решения задач многокритериальной оптимизации, позволяющая одновременно решать множество порождаемых задач скалярной оптимизации. Использование данной модели вычислений позволяет существенно снизить трудоемкость решения каждой задачи в отдельности. Подобный эффект достигается в силу того, что все порождаемые скалярные задачи основываются на одной и той же многокритериальной задаче и, следовательно, все вычисленные значения критериев исходной задачи МКО могут быть приведены к значениям критерия любой из решаемых скалярных задач без каких-либо трудоемких вычислений. Результаты, полученные в данном направлении, представлены в публикации [1].В задачах многокритериальной оптимизации порождаемые скалярные задачи могут характеризоваться разным типом зависимости от разных параметров. Например, зависимость по некоторым переменным может быть локальной, по другим переменным может иметься небольшое число экстремумов (слабая многоэкстремальность), по остальной части параметров зависимость может быть существенно многоэкстремальной. Использование информации о характере зависимости может существенно сократить вычислительные затраты на решение задачи в целом за счет выбора соответствующего метода оптимизации. При выполнении первого этапа работ была предложена модель и на ее основе разработан подход к разделению параметров скалярных задач оптимизации на основе использования методов машинного обучения. Подход основан на оценке меры схожести между значениями, вычисленными по регрессионной модели (функции, унимодальной по части параметров) и значениями исходной оптимизируемой функции.Разрабатываемые методы основаны на предположении о липшицевости оптимизируемых функций. Однако возникающие скалярные функции (которые соответствуют сложным процессам в моделируемых объектах) могут не удовлетворять условию Липшица в силу наличия скачкообразных изменений значений функции в некоторых точках области поиска. Причинами подобных скачков могут являться резкие изменения характеристик оптимизируемого объекта при малых изменениях его параметров. В рамках выполнения первого этапа проекта была предложена модель и детерминированный алгоритм на ее основе, ориентированный на решение оптимизационных задач как с заданными, так и не заданными точками разрывов. Данный алгоритм разработан на основе «непрерывного» алгоритма глобального поиска и обеспечивает поиск глобального оптимума. Результаты, полученные в данном направлении, представлены в публикации [2].

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

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

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

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

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

5. Все предложенные в рамках первого этапа алгоритмы были реализованы в виде программных модулей на языке C++ с возможностью запуска на параллельных вычислительных системах. Реализованные алгоритмы были экспериментально апробированы при решении сложных тестовых и прикладных задач. Для апробации и сравнения алгоритмов решения задач непрерывной глобальной оптимизации был разработан генератор классов многомерных тестовых задач с невыпуклыми ограничениями. Одновременно с решением серий тестовых задач разработанные алгоритмы применялись и для решения прикладных задач выбора оптимальных параметров. В частности, совместно с институтом нефтехимии и катализа РАН исследовался процесс предриформинга пропана в газ, обогащенный метаном, в присутствии никелевого катализатора. Данный процесс является промышленно важным химическим процессом, т.к. составляет часть экономически оправданных технологий переработки попутного газа с малодебитных скважин. Была успешно решена обратная задача химической кинетики, в результате чего были идентифицированы кинетические параметры процесса предриформинга пропана в присутствии катализатора. Решение обратной задачи химической кинетики проводилось на суперкомпьютере «Лобачевский» (операционная система – CentOS 7.2, система управления – SLURM, на узле – 2 CPU Intel Sandy Bridge E5-2660 2.2 GHz, 64 Gb RAM). Результаты представлены в публикации [3].

По итогам выполнения первого этапа проекта подготовлено 3 публикации в изданиях, индексируемых Web of Science и/или Scopus. Результаты докладывались в пяти докладах на четырех международных конференциях, проводимых в России и за рубежом (в связи с пандемией COVID-19 все конференции проводились в дистанционном режиме):

  1. Международная конференция Mathematical Optimization Theory and Operations Research (MOTOR 2021, Иркутск, 5-10 июля 2021 г., https://conference.icc.ru/event/3/); секционный доклад «An Approach for Simultaneous Finding of Multiple Efficient Decisions in Multi-objective Optimization Problems» (К.А. Баркалов, Е.А, Козинов, В.А, Гришагин, В.П. Гергель).
  2. Международная конференция Optimization and Applications (OPTIMA-2021, 27 сентября – 1 октября, Петровац, Черногория, http://agora.guru.ru/OPTIMA-2021); секционный доклад «A Search Algorithm for the Global Extremum of a Discontinuous Function» (К.А. Баркалов, М.А. Усова)
  3. International Conference of Numerical Analysis and Applied Mathematics (ICNAAM-2021, 20-26 сентября, Родос, Греция, https://icnaam.org); секционные доклады «Possible Extensions to the DIRECT Global Optimization Algorithm Based on Space-Filling and Diagonal Curves» (Д.Е. Квасов) и «Simulation and Optimization of Injector Parameters with OpenFOAM and Globalizer Tools» (К.А. Баркалов, И.Г. Лебедев)
  4. Международная конференция «Суперкомпьютерные дни в России» (Москва, 27-28 сентября 2021 г., http://russianscdays.org ), секционный доклад «Parallel Global Search Algorithm for Optimization of the Kinetic Parameters of Chemical Reactions» (К.А. Баркалов, И.Г. Лебедев)