题

我有一个功能，

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

以 100 个整数作为输入，并给出一个整数作为输出。P 是一个计算速度较慢的函数（其范围可以从 30 秒到几分钟）。

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

我可以使用什么技术来实现这一目标？我知道人们通常会为此使用遗传算法，但恐怕用它们来计算它需要很长时间，因为即使人口很少且世代数很少（比方说，人口 = 50，世代 = 50），P 也是如此速度慢，计算起来需要40多个小时。

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

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

谢谢

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

有帮助吗？

解决方案

作为第一线算法这种类型的问题，我建议模拟退火。 SA是一个伟大的选择，因为你可以清楚地控制你的出发点和运行时间。

如果你了解你的100维空间的结构，SA你可以选择一个很好的起点，并且可以对您的结果的质量有很大的影响。另外随着SA可以控制的“冷却速度”，这同时影响运行时间和您的结果的质量 - 自然方向相反。我通常以相对较快的冷却速度运行首先要寻找好的开始向量，然后减缓后续运行的冷却速度来改善结果。元-SA技术，该技术可以实现自动化的种类。

我用SA成功最大化，在过去的建模中子质子相互作用使用了非常高维函数。

此外，我想看看在尺寸上减少P（）如果可能的话。为了您的具体问题，都在100个变量需要？如果你能解决这些的1/2，你会加快优化任何与更好的结果告终。

（和SA是容易实现。）

其他提示

模拟退火, 密切相关 马尔可夫链蒙特卡罗 (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。它需要尽可能快。 这是我最喜欢的方法。

也许你的算法的显著部分是并行？如果是这样，你有没有考虑并行代码？

看列出此处各种随机优化技术。我建议模拟退火。

有很多著名的全球优化算法（模拟退火，随机隧道，等...），可以发现，全球最大的，但都不是，保证在合理的时间量内发现未做有关的假设形状函数的

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

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

这个问题看起来太大了，按理说你应该需要类似 SETI@Home 的努力来解决它。数以千计的计算机可以轻松完成此类任务。但我不确定如何接触成千上万的计算机用户以获取他们的计算机的使用权。

事实上，我愿意。请暂时容忍我无视这一切的合法性。

僵尸网络是由一些隐藏在前铁幕后面的人运行的。我最近看到有人以 70 美元租用僵尸网络 24 小时。试想一下，数以千计的 0wned PC 已准备好执行您的命令！您可以让它们来解决您的问题，而不是让它们成为 DDOS 互联网站点。:)

不过，对此还有最后两条建议：

  • 不要用您自己的信用卡付款:)
  • 不要接受陌生人的法律建议:)

祝你好运！

假设：

首先 - 变量必须是整数，点击。 第二 - 目标函数P（）是非线性的

观察：

在一般情况下，非线性的整数规划是非常难以解决。在现实中，如上文所建议，四舍五入通过放松整数限制可以帮助的溶液中。

有可用的一般的无约束优化技术。是来自实验设计的一种方法是调用“响应曲面法”。当实验的成本显著非常有帮助。该方法是用一个点开始，由一组增量偏离您的每一个投入运行一组实验。然后，计算每个输入的梯度，并采取在为每个方向迈出的一步，然后重复。弗莱彻 - 优化和实验者盒亨特亨特统计的实用方法是地方去寻找

如果你有机会到MATLAB，您可以并行代码非常快而且很容易地。甚至它可以使简单的线性for循环以其PARFOR环parallell

如果一个Microsoft的解决方法是一个选项，检查出求解基金会。我听到斯科特Hanselman的播客（＃191 ）。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top