Задача многокритериальной оптимизации

Для всех, кому интересно, продолжение истории.

Нашёл такую библиотеку для Питона: https://smt.readthedocs.io/en/latest/

Цитата с сайта: «The surrogate modeling toolbox (SMT) is an open-source Python package consisting of libraries of surrogate modeling methods (e.g., radial basis functions, kriging), sampling methods, and benchmarking problems.»

«Поигравишись» с различными аппроксимирующими функциями, составил для себя следующие выводы по некоторым вариантам (для своего набора данных):

• RBF (Radial basis functions) — очень плохая экстраполяция (улетает в бесконечность) и сильная чувствительность к d0 (basis function scaling parameter in exp(-d^2 / d0^2)).
• IDW (Inverse-distance weighting) — замечательная «аккуратная» аппроксимация с одним «маленьким» недостатком — экстраполирует к константе, в результате чего процедура оптимизация (см. ниже) даёт несколько «тривиальные» результаты.
• RMTS (Regularized minimal-energy tensor-product splines) — какой-то очень навороченный подход с мульёном опций... До конца не разобрался, ибо сильная чувствительность к значению параметров метода...
• LS (Least-squares approximation) — собственно, линейная аппроксимация. Для моей задачи не подходит совсем.
• QP (Second-order polynomial approximation) — квадратичная аппроксимация, тоже плоха для моего случая.
• KRG (Kriging) — пожалуй, один из наиболее надёжных и хороших методов. Использую его как основной. Даёт более-менее правильный тренд (кстати, можно также явно указывать функцию тренда из constant, linear или quadratic; constant и linear даёт близкие результаты, quadratic обычно не работает :). Есть загадочный параметр метода theta0 (Initial hyperparameters), который может быть один на все измерения (коих у меня 7 штук) или для каждого свой. Значение по умолчанию (0.01) даёт иногда странные результаты... Мои опыты показали, что надо брать 1e-5 или меньше, при значениях порядка 1e-10 и меньше тренд превращается почти в линейный, что тоже плохо. Если брать больше 1e-5, то экстраполяция может «улететь в бесконечность», что совсем нехорошо. Попытка «поиграть» разными значениями theta0 для разных переменных особых улучшений не дала...
• KPLS (KPLS is a kriging model that uses the partial least squares (PLS) method) — тоже очень неплохой метод, обладает меньшей чувствительностью к theta0, чем KRG. Правда, иногда результаты оптимизации, полученные с его помощью, выглядят «странно» (подробности см. далее).
• KPLSK — какой-то двухшаговый метод на базе KPLS, на тестовом примере у меня работал хорошо, а на реальных данных — не всегда, поэтому не использую.
• GEKPLS и GENN (Gradient-Enhanced Neural Networks) — требуют для построения функции значения производных, коих у меня нема...

Для задачи оптимизации я использую библиотеку Platypus https://platypus.readthedocs.io/en/latest/. Цитата с сайта: «Platypus is a framework for evolutionary computing in Python with a focus on multiobjective evolutionary algorithms (MOEAs). It differs from existing optimization libraries, including PyGMO, Inspyred, DEAP, and Scipy, by providing optimization algorithms and analysis tools for multiobjective optimization.»

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

На моём (пока ограниченном) наборе данных из ~40 точек эта связка (SMT + Platypus) работает очень быстро, порядка десятков секунд. Выдаёт что-то, что я пытаюсь как-то интерпретировать. В целом могу отметить, что полученные в результате оптимизации значения параметров после запуска расчётов действительно дают что-то более оптимальное, чем исходные параметры.

Из особенностей/недостатков:

• При использовании метода IDW оптимизация даёт немного странные наборы оптимальных параметров. В пространстве моих критериев (3 штуки) это выглядит как набор линий, недалеко ушедших от исходных данных и «приходящих» в один из уже известных из исходных данных оптимальных наборов. В общем, совсем не похоже на фронт Парето, как его обычно малюют :)
• При использовании методов KRG, KPLS, KPLSK иногда возникают такие ситуации: 1) аппроксимирующие функции слишком быстро возрастают, поэтому результаты оптимизации получаются «нефизическими»; 2) вместо «поверхности Парето», которая должна получаться в 3D, имеется «линия Парето», что, на мой взгляд, говорит о некорректности аппроксимации.
• Функции, получаемые при помощи методов KRG, KPLS, KPLSK, выглядят как бы немного «зашумлёнными». Пока не разобрался, в чём причина.

Ну и вместо заключения: работа пока ещё в процессе, оптимизация идёт (пусть пока и вполне «очевидным» образом :)

P.S. Если кому интересно, могу выложить свой питоновский код, он совсем небольшой

Для всех, кому интересно, продолжение истории.

Спасибо, мне интересно, жду следующих серий;-)

Так тебе просто «активный эксперимент» нужен получается. Начав с какой то точки многомерной получаешь градиент и делаешь шаг по нему. Там куча просто планов есть разной степени навороченности.

так можно делать, если критерий один (ищем минимум одной функции). А у меня — несколько, посему куда именно шагать не всегда ясно

Как куда? Просто в виде «фронта Парето для градиентов» их все сводим вместе. И пусть шагает туда куда голосует «фронт».

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

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

P.S. В случае локального минимума такая ситуация может означать, что точка уже на фронте, но, по-видимому, не всегда...

Это признак границы (см. фронт Парето), поздравляю ты дошел до него, теперь «иди вдоль фронта» до очередной нелинейности которая изменит поведение системы.

Все решения на фронте являются оптимальными и выбираешь из них по дополнительному критерию (например близость текущего состояния системы которую надо привести «в оптимум»).