Функциональное приближение

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

Моделирование отжига , тесно связанное с Монте-Карло цепи Маркова (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. Он должен быть таким же как можно быстрее. Вот мой любимый способ сделать это.

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

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

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

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

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

Есть ботнеты, которыми управляют некоторые люди, прячущиеся за бывшим железным занавесом. Недавно я увидел предложение арендовать ботнет за 70 долларов на 24 часа. Подумать только, тысячи разошедшихся ПК готовы делать ваши ставки! Вместо того, чтобы иметь их сайты DDOS в Интернете, вы можете заставить их заниматься вашей проблемой. :)

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

• Не платите им своей кредитной картой :)
• Не слушайте юридических советов от незнакомцев на SO:)

Удачи !

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

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

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

Если решение Microsoft является вариантом, проверьте Solver Foundation . Я слышал об этом в подкасте Скотта Хансельмана ( # 191 ).

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

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

Наблюдение:

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

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