Ускорение многокритериальной оптимизации: адаптивные суррогатные модели на службе эволюционных алгоритмов

Автор: Денис Аветисян

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

"Покупай на слухах, продавай на новостях". А потом сиди с акциями никому не известной биотех-компании. Здесь мы про скучный, но рабочий фундаментал.

Бесплатный Телеграм канал

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

Предлагаемый подход использует суррогатные модели для эффективной аппроксимации функций пригодности и ускорения исследования пространства решений в алгоритмах NSGA-II и MOEA/D.

Многоцелевая оптимизация, несмотря на эффективность эволюционных алгоритмов, часто сталкивается с вычислительными ограничениями при решении дорогостоящих задач. В данной работе, посвященной ‘Adaptive Surrogate-Based Strategy for Accelerating Convergence Speed when Solving Expensive Unconstrained Multi-Objective Optimisation Problems’, предложена адаптивная стратегия, использующая суррогатные модели для ускорения сходимости современных алгоритмов многоцелевой оптимизации. Предложенный подход позволяет значительно сократить время поиска оптимальных решений за счет эффективной аппроксимации целевых функций. Каковы перспективы применения подобных суррогатных моделей для решения еще более сложных и ресурсоемких задач в различных областях науки и техники?

Вызов оптимизации: цена эффективности

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

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

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

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

Построение суррогатных моделей: разнообразие подходов

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

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

Время обучения суррогатных моделей незначительно, что позволяет минимизировать накладные расходы. Согласно проведенным измерениям, Gaussian Process Regression (GPR) обучается за 1 минуту 52 секунды, Random Forest Regression (RFR) — за 3 минуты 46 секунд, а Convolutional Neural Network (CNN) — за 3 минуты 49 секунд. Данные показатели демонстрируют, что время, затрачиваемое на обучение суррогатной модели, существенно меньше времени, требуемого для непосредственного выполнения дорогостоящих вычислений, что делает использование суррогатных моделей эффективным решением для задач оптимизации и анализа.

Сравнение с облегчёнными суррогатными моделями, предложенными в работе [Zavoianu2022], демонстрирует сопоставимые результаты.

Оценка эффективности оптимизации: метрики и эталоны

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

Индикаторы гиперобъема (Hypervolume Indicator) и обратного поколения (Inverse Generational Distance — IGD) являются ключевыми метриками для оценки эффективности многокритериальной оптимизации. Индикатор гиперобъема измеряет объем пространства, доминируемого не-доминируемым фронтом Парето, представляя собой показатель как сходимости к истинному фронту, так и разнообразия полученных решений. Более высокое значение гиперобъема указывает на лучшее качество и распределение решений. IGD, в свою очередь, оценивает максимальное расстояние между решениями на полученном фронте Парето и точкой на истинном фронте, тем самым отражая разнообразие и сходимость алгоритма. Низкое значение IGD свидетельствует о хорошем покрытии истинного фронта Парето и, следовательно, о высокой эффективности алгоритма.

Использование суррогатных моделей позволило значительно сократить время вычислений при оптимизации. В частности, задача, требующая 50 000 оценок целевой функции и изначально занимавшая более 1000 дней, была выполнена за 11 дней при использовании кластера HTCondor. Данное снижение вычислительных затрат достигнуто за счет аппроксимации дорогостоящей функции оценки суррогатной моделью, что позволило уменьшить количество прямых вычислений исходной функции.

Сравнение алгоритма MOEA/D и его улучшенных версий с использованием суррогатных моделей на различных тестовых задачах показало, что нормализованное обратное поколенческое расстояние [latex]IGD(PF_{c})[/latex] является эффективным показателем производительности. — Сравнение алгоритма MOEA/D и его улучшенных версий с использованием суррогатных моделей на различных тестовых задачах показало, что нормализованное обратное поколенческое расстояние $IGD(PF_{c})$ является эффективным показателем производительности.

Улучшение оптимизации: адаптивность и алгоритмы

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

Многокритериальные эволюционные алгоритмы, такие как NSGA-II и MOEA/D, эффективно используются в задачах оптимизации, использующих суррогатные модели, благодаря их способности работать с несколькими целями одновременно. В сложных задачах, где необходимо найти компромисс между различными критериями, эти алгоритмы позволяют оценить множество решений и сформировать Парето-фронт, представляющий оптимальные варианты. Использование суррогатных моделей в сочетании с этими алгоритмами снижает вычислительные затраты, поскольку суррогатная модель аппроксимирует сложную целевую функцию, позволяя алгоритму быстрее исследовать пространство решений и находить высококачественные решения без необходимости выполнения дорогостоящих вычислений исходной функции.

Сурогатные модели функционируют в течение примерно 5 поколений, прежде чем происходит их деактивация в процессе оптимизации. Комбинирование суррогатных моделей с адаптивными стратегиями и многоцелевыми эволюционными алгоритмами, такими как NSGA-II и MOEA/D, позволяет эффективно исследовать пространство решений и находить высококачественные решения. Данный подход обеспечивает сбалансированное использование вычислительных ресурсов, поскольку деактивация модели происходит при снижении ее вклада в процесс оптимизации, что повышает общую эффективность поиска оптимальных решений в сложных задачах.

Использование суррогатных моделей в алгоритмах NSGA-II и MOEA/D-DRA значительно повышает их среднюю производительность при решении задачи KSW.

Реальное воздействие и будущие направления

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

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

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

Использование суррогатной модели в алгоритме NSGA-II значительно повышает его эффективность при оптимизации на тестовом наборе Haddock.

Исследование демонстрирует, что адаптивное использование суррогатных моделей позволяет значительно ускорить сходимость многокритериальных эволюционных алгоритмов, таких как NSGA-II и MOEA/D. По сути, предлагаемый подход позволяет эффективнее исследовать пространство решений, минимизируя вычислительные затраты. Блез Паскаль однажды заметил: «Все великие вещи требуют времени». Однако, данная работа показывает, что время, необходимое для достижения оптимальных решений в сложных задачах оптимизации, можно существенно сократить, не умаляя при этом качества полученных результатов. Архитектура, лишенная истории адаптации к изменяющимся условиям, действительно хрупка, и предложенный метод позволяет создать более устойчивый и эффективный процесс оптимизации.

Что дальше?

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

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

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

Оригинал статьи: https://arxiv.org/pdf/2601.21885.pdf

Связаться с автором: https://www.linkedin.com/in/avetisyan/

Смотрите также:

2026-01-31 10:11