language-agnostic - 函数逼近

Question

我有一个功能，

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

它将 100 个整数作为输入并给出一个整数作为输出。P 是一个评估缓慢的函数（范围从 30 秒到几分钟不等）。

我需要知道哪些点值将使 P 的产生值最大化。

我可以使用哪些技术来完成此任务？我知道人们通常会为此使用遗传算法，但我担心用它们计算它需要很长时间，因为即使人口少且世代数少（比如说，人口 = 50，世代 = 50），P 也是如此慢，计算它需要 40 多个小时。

有没有更便宜的方法呢？也许是一个迭代过程？我不需要它真的是最优的，但我不知道它的行为方式（我尝试过线性/二次/指数，但它似乎没有产生任何好的值。我知道 P 可以返回价值至少比我得到的好5-10倍）。

它应该是更容易实现的东西（即，我必须自己实现它）。

谢谢

编辑：P 是一个随机过程。

score 4 · Accepted Answer

模拟退火，与马尔可夫链蒙特卡罗 (MCMC)密切相关。您可能想要的变体是Metropolis-Hastings。当你掌握它的窍门时，它非常好。可能有一些方法可以优化它，因为您的输入和结果都是整数。它是计算密集型的，可能需要一些调整，但它非常强大，我不确定其他方法可以做得更好。

这是一些脑死代码：

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。它需要尽可能快。这是我最喜欢的方法。

score 2 · Accepted Answer

也许你的算法的很大一部分是可并行的？如果是这样，您是否考虑过并行化您的代码？

score 2 · Accepted Answer

2

查看此处列出的各种随机优化技术。我推荐模拟退火。

于 2009-12-11T14:37:50.477 回答

score 2 · Accepted Answer

有许多著名的全局优化算法（模拟退火、随机隧道等）可以找到全局最大值，但没有一个可以保证在合理的时间内找到它而不对形状做出假设功能。

您不会找到一种快速/简单的方法来优化 100 维的非平凡函数。您将需要大量的处理能力和时间。假设您不想自己编写优化代码（根据您的问题），您还需要一些好的数学软件（例如 Mathematica）。

score 2 · Accepted Answer

另一个不完全严肃的答案，但值得深思：

这个问题看起来如此之大，以至于您应该需要像 SETI@Home 这样的努力来解决它。数以千计的计算机对这类事情进行了相当轻松的工作。但我不确定您如何让成千上万的计算机用户使用他们的计算机。

事实上，我愿意。请容忍我一会儿，忽略这一切的合法性。

有些人在前铁幕后面运行僵尸网络。我最近看到一个 70 美元 24 小时租用僵尸网络的报价。试想一下，成千上万的 0wned PC 已准备好为您出价！您可以让他们在您的问题上搅动，而不是让他们 DDOS Internet 站点。:)

不过，关于此的最后两条建议：

不要用您自己的信用卡付款 :)
不要在 SO 上听取陌生人的法律建议 :)

祝你好运！

score 1 · Accepted Answer

作为此类问题的第一线算法，我会推荐模拟退火。SA 是一个很好的首选，因为您可以清楚地控制起点和运行时间。

如果您对 100 维空间的结构有所了解，那么使用 SA，您可以选择一个好的起点，这会对您的结果质量产生重大影响。此外，使用 SA，您可以控制影响运行时间和结果质量的“冷却速度” - 自然是相反的方向。我通常首先以相对较快的冷却速度运行以寻找良好的起始向量，然后在随后的运行中减慢冷却速度以改善结果。一种可以自动化的元 SA 技术。

我已经成功地使用 SA 来最大化过去用于建模中子质子相互作用的非常高维函数。

另外，如果可能的话，我会考虑在维度上减少 P() 。对于您的特定问题，是否需要全部 100 个变量？如果您可以修复其中的 1/2，您将加速任何优化器并最终获得更好的结果。

（而且 SA 很容易实现。）

score 1 · Accepted Answer

假设：

首先 - 变量必须是整数。
其次 - 目标函数 P() 是非线性的。

观察：

一般来说，非线性整数规划很难求解。实际上，如上所述，通过放宽整数限制对解决方案进行四舍五入可能会有所帮助。

有可用的通用无约束优化技术。来自实验设计的一种方法称为“响应面方法”。当实验成本很高时非常有用。该方法是通过从一个点开始并将每个输入偏离一组增量来运行一组实验。然后计算每个输入的梯度，并在每个输入的方向上迈出一步，然后重复。Fletcher - 优化的实用方法和 Box Hunter & Hunter Statistics for Experimenters 值得一看。

score 0 · Accepted Answer

0

神经网络：D 还是泰勒级数？

于 2009-12-11T14:23:35.723 回答

score 0 · Accepted Answer

如果您可以访问 matlab，则可以非常快速且轻松地并行化您的代码。甚至它可以使简单的线性 for 循环与 parfor 循环并行

score 0 · Accepted Answer

如果可以选择 Microsoft 解决方案，请查看Solver Foundation。我在 Scott Hanselman 的播客 ( #191 )上听说过。

language-agnostic - 函数逼近

10 回答 10

Related

Reference