Аппроксимация функции

Question

У меня есть функция,

P(x0, x1, ..., xn)

это принимает 100 целых чисел в качестве входных данных и выдает на выходе целое число.P - это медленная функция для оценки (она может варьироваться от 30 секунд до пары минут).

Мне нужно знать, какие значения точек максимизируют полученное значение из P.

Какие методы я могу использовать для достижения этой цели?Я знаю, что обычно люди используют для этого генетические алгоритмы, но я боюсь, что потребуется много времени, чтобы вычислить это с их помощью, поскольку даже при небольшой популяции и нескольких поколениях (скажем, population = 50, generations = 50) P настолько медленный, что для его вычисления потребуется более 40 часов.

Есть ли какой-нибудь более дешевый способ сделать это?Может быть, итеративный процесс?Мне не нужно, чтобы он был действительно оптимальным, но у меня нет никаких идей о том, как он ведет себя (я пробовал линейный / квадратичный / экспоненциальный, но, похоже, это не дает никаких хороших значений.Я знаю, что P может возвращать значения как минимум в 5-10 раз лучше, чем то, что я получаю).

Это должно быть что-то, что проще реализовать (т. Е. я должен реализовать это сам).

Спасибо

Редактировать:P - это случайный процесс.

Answer 1

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

Если вы знаете что-то о структуре вашего 100-мерного пространства, с помощью SA вы можете выбрать хорошую отправную точку, и это может оказать большое влияние на качество вашего результата.Также с помощью SA вы можете контролировать "скорость охлаждения", которая влияет как на время выполнения, так и на качество ваших результатов - естественно, в противоположных направлениях.Обычно я сначала запускаю с относительно высокой скоростью охлаждения, чтобы найти хорошие стартовые векторы, а затем замедляю скорость охлаждения в последующих запусках, чтобы улучшить результаты.Своего рода метод meta-SA, который может быть автоматизирован.

Я успешно использовал SA для максимизации функции очень высокой размерности, используемой в прошлом при моделировании нейтронно-протонных взаимодействий.

Кроме того, я бы постарался уменьшить размерность P(), если это возможно.Для вашей конкретной проблемы необходимы ли все 100 переменных?Если вы сможете исправить 1/2 из них, вы ускорите работу любого оптимизатора и в конечном итоге получите лучшие результаты.

(И SA легко реализовать.)

Answer 2

Имитированный отжиг, тесно связанный с Цепь Маркова Монте-Карло (MCMC).Вариант, который вы, вероятно, хотите, это Метрополис-Гастингс.Когда ты привыкаешь к этому, это довольно приятно.Возможно, есть несколько способов оптимизировать это, потому что все ваши входные данные и результат являются целыми числами.Это требует больших вычислительных затрат и может потребовать некоторой настройки, но оно достаточно надежное, и я не уверен, что другие методы могли бы работать лучше.

Вот какой-нибудь безмозглый код для этого:

const int n = 100; // length of vector to optimize
int a[n]; // the vector to optimize
double P(a){..} // Get the probability of vector a.
                // This is the function to optimize.
// for a large number of a samples
for (i = 0; i < large_number; i++){
  // get P(a)
  double p = P(a);
  // for each element of vector a
  for (j = 0; j < n; j++){
    // get an amount by which to change it. This choice has to be symmetric.
    // this is called the Proposal Distribution
    int step = uniform_random_choice_from(-2, -1, 1, 2);
    // make the change to a[j], and get p1, the new value of p
    a[j] += step;
    double p1 = P(a);
    bool bKeepTheStep = true;
    // if p1 is better than p, keep the step
    // if p1 is worse than p, then keep the step p1/p of the time
    if (p1 < p){
      bKeepTheStep = (unif(0,1) < p1/p);
    }
    if (bKeepTheStep) p = p1;
    else a[j] -= step;
  }
  // now a is a sample, and p is its value
  // record a and p
}
// what you have now is a large random sampling of vectors from distribution P
// now you can choose the best one, the average, the variance,
// any statistic you like

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

И, во что бы то ни стало, профиль P.Это должно быть как можно быстрее. Вот мой любимый способ сделать это.

Answer 3

Может быть, значительная часть вашего алгоритма распараллеливаема?Если да, рассматривали ли вы возможность распараллеливания своего кода?

Answer 4

Посмотрите на различные перечисленные методы стохастической оптимизации здесь.Я рекомендую имитированный отжиг.

Answer 5

Существует множество хорошо известных алгоритмов глобальной оптимизации (имитированный отжиг, стохастическое туннелирование и т.д.), Которые МОГУТ найти глобальный максимум, но ни один из них не гарантирует его нахождения в течение разумного промежутка времени без принятия предположений о форме функции.

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

Answer 6

Еще один не совсем серьезный ответ, но пища для размышлений:

Эта проблема выглядит настолько серьезной, что по праву вам должно понадобиться что-то вроде SETI@Home для ее решения.Тысячи компьютеров выполняют достаточно легкую работу такого рода.Но я не уверен, как вы могли бы охватить тысячи пользователей компьютеров, чтобы получить доступ к их компьютерам.

На самом деле, я знаю.Пожалуйста, потерпите меня минутку, игнорируя законность всего этого.

Существуют ботнеты, которыми управляют некоторые люди, прячущиеся за бывшим Железным занавесом.Недавно я видел предложение арендовать ботнет за 70 долларов на 24 часа.Только подумайте, тысячи компьютеров 0wned готовы выполнить ваши требования!Вместо того чтобы использовать их для DDOS-атак на интернет-сайтах, вы могли бы заставить их работать над вашей проблемой.:)

Однако два последних совета по этому поводу:

• Не платите им своей собственной кредитной картой :)
• Не обращайтесь за юридической консультацией к незнакомым людям по SO :)

Удачи вам!

Answer 7

Предположения:

Во-первых, переменные должны быть целочисленными.
Во-вторых, целевая функция P() является нелинейной.

Наблюдение:

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

Существуют общие методы неограниченной оптимизации.Один из подходов, который исходит из экспериментального проектирования, называется "методология поверхности отклика".Очень полезно, когда стоимость эксперимента значительна.Подход заключается в проведении набора экспериментов, начиная с одной точки и отклоняя каждый из ваших входных данных на заданное приращение.Затем вы вычисляете градиент для каждого входного сигнала и делаете шаг в этом направлении для каждого, затем повторяете.Fletcher - Практические методы оптимизации и статистика Box Hunter & Hunter для экспериментаторов - это то, на что стоит обратить внимание.

Answer 8

Нейронные сети :D или Серия Тейлора ?

Answer 9

Если у вас есть доступ к matlab, вы можете распараллелить свой код довольно быстро и довольно легко.Даже он может сделать простые линейные циклы for параллельными своему циклу parfor

Answer 10

Если возможно использовать решение Microsoft, ознакомьтесь Решающий Фундамент.Я слышал об этом в подкасте Скотта Хансельмана (#191).