Проект Российского научного фонда № Н-277-2 «Суперкомпьютерные вычисления для интеллектуального глобального поиска в задачах выбора наилучших решений большой вычислительной сложности» по приоритетному направлению деятельности РНФ «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами».
Номер государственной регистрации AAAA-A21-121052800031-5 от 28.05.2021.
Целью проекта является разработка методов решения задач принятия решений повышенной размерности. Данная проблема представляет собой задачу поиска оптимальной комбинации параметров для сложных систем, объектов и процессов, характеризующихся меняющимися требованиями к эффективности и существенной вычислительной сложностью расчета их функциональных характеристик по математической модели.
Выполнение проекта позволит получить качественно новые результаты в области разработки моделей, методов и программных средств для выбора оптимальных параметров сложных объектов и процессов. Научная новизна планируемых в рамках проекта исследований состоит в разработке синергетического подхода, позволяющего на основе сочетания разработанной исполнителями проекта теории решения задач глобального поиска и методов искусственного интеллекта и машинного обучения обеспечить решения задач многокритериальной многоэкстремальной оптимизации повышенной размерности.
Новые результаты в теории и практике глобальной оптимизации будут состоять в разработке и реализации новых комбинированных методов, (1) сочетающих эффективные алгоритмы глобального поиска и методы машинного обучения, (2) поддерживающих разработанные в рамках проекта схемы последовательной декомпозиции вычислений, (3) использующих различные стратегии оптимизации, учитывающие характерные особенности решаемых задач. Для достижения заявленных результатов планируется провести исследование и реализацию перспективных подходов:
В результате выполнения проекта будут разработаны и исследованы:
Планируемые итоги выполнение проекта – модели, методы и программные средства на их основе – обеспечат достижение научно значимого результата: возможность решения задач принятия решений повышенной размерности. Данный результат будет обеспечен на основе синергии разрабатываемого авторами подхода для моделирования и решения сложных задач глобального поиска и методов машинного обучении и искусственного интеллекта. Разработанные программные средства могут быть использованы для решения актуальных задач выбора оптимальных параметров для сложных объектов и процессов, рассмотрение которых ранее не представлялся возможным в силу их большой вычислительной сложности.
Первый этап (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 все конференции проводились в дистанционном режиме):