LINUX.ORG.RU

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

 , , многокритериальная оптимизация, , парето


1

3

Надо тут провести многокритериальную многопараметрическую оптимизацию, т.е. найти фронт Парето (критериев три, параметров около 7). Хочу для этих целей по максимуму задействовать готового и на Python.

Нашёл список либ для этих целей (https://www.quora.com/What-are-the-current-multi-objective-optimization-libra...)

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

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

UPDATE: см. мой комментарий от 1 апреля и не верь глазам своим :)

★★★★☆

Последнее исправление: Sahas (всего исправлений: 2)

А набор данных для аппроксимации на регулярной (прямоугольной, картезианской или по нашенски декартовой) 7ми мерной сетке задан?

AntonI ★★★★
()
Ответ на: комментарий от Sahas

У… то есть сначала надо провести триангуляцию (что то типа разбиения вороного), натянуть на них какую то неструктурированную сетку, а потом уже строить сплайны?

Я не специалист по оптимизации (в т.ч. в питоне), ничего кроме scipy.optimize.curve_fit не использовал. Его конечно можно прикрутить и к семимерному пространству, но все равно нужно заранее знать вид аппроксимирующей функции - тогда он подберет коэффициенты.

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

AntonI ★★★★
()
Ответ на: комментарий от AntonI

scipy.optimize.curve_fit

Ему ещё начальное приближение желательно как можно лучше задать, если функция нелинейная.

thunar ★★★★★
()
Ответ на: комментарий от AntonI

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

ну, вдруг это уже всё есть и работает «из коробки»...

В данном случае я бы сначала подумал о каком то бессеточном методе для аппроксимации

типа нейронной сети? Что-то такое я в интернетах находил...

Но если данных много то я бы это таки сделал на плюсах в виде отдельного модуля

данных как раз не очень много (пока). Может, и какими-нибудь многомерными полиномами Лагранжа обойтись можно...

Sahas ★★★★☆
() автор топика
Ответ на: комментарий от thunar

функция слабо нелинейная... наверное :)

Sahas ★★★★☆
() автор топика
Ответ на: комментарий от Sahas

ну, вдруг это уже всё есть и работает «из коробки»…

Может и есть, хотя семимерное пространство это несколько экзотично;-)

типа нейронной сети? Что-то такое я в интернетах находил…

Нет. Но я че то сходу не соображу как это сделать, все равно все к делоне/воронову сходится;-(

данных как раз не очень много (пока).

Немного это сколько?

AntonI ★★★★
()
Ответ на: комментарий от Sahas

Не, данные довольно «хаотически» разбросаны

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

Zodd ★★★★★
()
Ответ на: комментарий от peregrine

Там часы уходят на получение одного значения функции. Может это результаты эксперимента или еще чего…

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

AntonI ★★★★
()
Ответ на: комментарий от Zodd

При линейной аппроксимации минимум будет в одном из известных значений функции;-)

Можно взять какие нить бета-сплайны, их не бьет.

AntonI ★★★★
()
Ответ на: комментарий от AntonI

Ну ему либо ждать, либо портить данные упрощениями до приемлемого качества, либо менять алгоритм на более быстрый. Другого не дано.

peregrine ★★★★★
()
Ответ на: комментарий от peregrine

Ну чудес то не бывает…

Мне вот стало интересно, можно ли натянуть что-то а-ля сплайн на неструктурированные данные? То есть понятно что можно, во что это выльется в пространстве высокой размерности?

AntonI ★★★★
()
Ответ на: комментарий от Zodd

Если не знаешь что ты делаешь, делай это острожно!(с)

Бета-сплайны значения испортят. Но осцилляции при поиске минимума и правда хуже.

AntonI ★★★★
()
Ответ на: комментарий от AntonI

Можно еще сеточный метод использовать, там точно не будет осцилляции. Потом нужную область снова разбить на более мелкую сетку.

Zodd ★★★★★
()
Ответ на: комментарий от AntonI

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

Т.е. вычисляешь f(xi, yi), где xi, yi пробегают значения с заданным шагом по области поиска оптимальной точки. Найдя оптимальные параметры x_opt, y_opt. Заново разбиваешь область вокруг этой точки и уточняешь значение оптимальной точки.

Zodd ★★★★★
()
Последнее исправление: Zodd (всего исправлений: 1)
Ответ на: комментарий от Zodd

Это как то называется в теории оптимизации, я забыл. В обычных вычислениях это AMR.

Есть нюансы:

  1. можно проскочить интересующую область

  2. у ТС 7ми мерное пространство, это немножко дофига

  3. у ТС исходно данные не ложатся на равномерную сетку.

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

AntonI ★★★★
()
Ответ на: комментарий от AntonI

Я тоже забыл как называется метод.

У каждого метода есть возможность получить локальный минимум. В этом подходе не надо Якобиан вычислять.

Zodd ★★★★★
()

Это называется surrogate model.

Пробовал пользовать перцептрон для такой цели. Но не на питоне, а на R.

luka83
()
Ответ на: комментарий от AntonI

ИМХО можно, но результат зависит от данных и того что хочется получить в итоге

peregrine ★★★★★
()

Хочу для этих целей по максимуму задействовать готового и на Python.

CVXOPT Python Software for Convex Optimization ©.
Scipy.optimize ©.

критериев три, параметров около 7

Ежели ничего не поможет, то: «Ударим автопробегом по бездорожью и разгильдяйству!»
«Ударим стохастической оптимизацией © по критериям и параметрам!» :)

quickquest ★★★★★
()
Ответ на: комментарий от quickquest

Если я правильно понял, это именно инструменты для минимизации уже имеющейся функции. А мне её ещё построить надо...

Sahas ★★★★☆
() автор топика
Ответ на: комментарий от AntonI

Про кривую Гильберта слышал, но не думал, что её можно применить к задаче оптимизации :)

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

Sahas ★★★★☆
() автор топика
Ответ на: комментарий от peregrine

Сколько у тебя там данных что оно часы жрёт?

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

Sahas ★★★★☆
() автор топика
Ответ на: комментарий от AntonI

там в статье написано, что просто использовали суперкомпьютер :)

(т.е. не аппроксимировали данные функцией)

Sahas ★★★★☆
() автор топика
Ответ на: комментарий от Sahas

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

Я не думаю, что аппроксимация функции (как Вы изначально писали) это панацея.

AntonI ★★★★
()
Ответ на: комментарий от AntonI

Я не думаю, что аппроксимация функции (как Вы изначально писали) это панацея.

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

Sahas ★★★★☆
() автор топика
Ответ на: комментарий от Sahas

А, на фронт я внимания не обратил, виноват;-(

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

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

Еще конечно можно ускорить код считающий одну точку, тут я наверное смогу помочь если он самописный;-)

В любом случае, напишите пожалуйста тут чем закончится - интересно же!

AntonI ★★★★
()
Ответ на: комментарий от Sahas

надеюсь, достаточно будет хоть какой-то аппроксимации

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

Но ежели это не важно, то python’щики изобретают всяческие «оболочечные эвристики», типа ©.

quickquest ★★★★★
()
Ответ на: комментарий от Sahas

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

luka83
()
Ответ на: комментарий от quickquest

Но ежели это не важно, то python’щики изобретают всяческие «оболочечные эвристики», типа ©.

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

Sahas ★★★★☆
() автор топика
Ответ на: комментарий от AntonI

Тогда Вам наверное надо искать какого то специалиста по оптимизации/глубоко лезть в теорию, потому что семимерное пространство и несколько часов на точку это дофига

Поэтому я и хочу применить многоуровневую оптимизацию, когда оптимизируется аппроксимирующая функция, которая затем уточняется.

линейная аппроксимация Вас явно не устроит

кстати, для определения фронта Парето вполне устроит, я тут подумал

Еще конечно можно ускорить код считающий одну точку, тут я наверное смогу помочь если он самописный

вот тут, к сожалению, вряд ли получится ускорить, поскольку и так уже упрощено донельзя... Кстати, для расчётов используется OpenFOAM

В любом случае, напишите пожалуйста тут чем закончится - интересно же!

мне тоже интересно, закончится ли успешно, на что я очень надеюсь :)

Sahas ★★★★☆
() автор топика
Ответ на: комментарий от luka83

К счастью, геометрия «квадратно-гнездовая», поэтому с ней всё просто

Sahas ★★★★☆
() автор топика
Ответ на: комментарий от Sahas

вот тут, к сожалению, вряд ли получится ускорить, поскольку и так уже упрощено донельзя… Кстати, для расчётов используется OpenFOAM

У меня пока не дошли руки до конкретных сравнений, но по общим ощущениям OF довольно медленный. Так что пространство для маневра тут тоже может быть.

luka83
()
Ответ на: комментарий от AntonI

Это верно, но мне надо не просто узлы с минимумами, а чтобы они на фронте лежали. А это, вроде как, не обязательно только узлы...

Sahas ★★★★☆
() автор топика
Ответ на: комментарий от luka83

У меня пока не дошли руки до конкретных сравнений, но по общим ощущениям OF довольно медленный

по сравнению с чем? В любом случае, солвер там практически самописный, и уж его-то менять точно никто не будет пока

Sahas ★★★★☆
() автор топика
Ответ на: комментарий от Sahas

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

AntonI ★★★★
()
Ответ на: комментарий от Sahas

По сравнению с ручной реализацией на каком-нибудь фортране.

luka83
()
Ответ на: комментарий от Sahas

Я с OF не работал, но судя по словам о химии пр. у Вас там много всего накручено.

Минусы таких пакетов - все очень универсально и удобно, но что бы где то что то соптимизировать надо наизнанку вывернуться.

AntonI ★★★★
()

проблема в том, что для получения значения функции от каждого набора параметров надо ждать очень долго (часы)

Не знаю насколько это ок в данном случае, но сейчас такие проблемы часто решают через покупку скольки-то-тысяч-ядер-в-облаке и запуске там какого-нибудь hyperopt или optuna. Они внутри себя аппроксимации тоже делают, afair. Возможно есть смысл посмотреть какие там алгоритмы. Ещё из такого есть яндексовый REP.

ei-grad ★★★★★
()
Последнее исправление: ei-grad (всего исправлений: 1)
Ответ на: комментарий от Sahas

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

psv1967 ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.