12

我正在构建一个脚本，该脚本生成输入数据 [参数] 供另一个程序计算。我想优化结果数据。以前我一直在使用 numpy powell 优化。伪代码看起来像这样。

def value(param):
     run_program(param)
     #Parse output
     return value

scipy.optimize.fmin_powell(value,param)

这很好用；但是，它非常慢，因为程序的每次迭代都可能需要数天才能运行。我想做的是粗粒度并行化这个。因此，它不会一次运行一次迭代，而是一次运行（参数数量）*2。例如：

Initial guess: param=[1,2,3,4,5]

#Modify guess by plus minus another matrix that is changeable at each iteration
jump=[1,1,1,1,1]
#Modify each variable plus/minus jump.
for num,a in enumerate(param):
    new_param1=param[:]
    new_param1[num]=new_param1[num]+jump[num]
    run_program(new_param1)
    new_param2=param[:]
    new_param2[num]=new_param2[num]-jump[num]
    run_program(new_param2)

#Wait until all programs are complete -> Parse Output
Output=[[value,param],...]
#Create new guess
#Repeat

变量的数量可以从 3 到 12 不等，因此这样的事情可能会将代码从一年缩短到一周。所有变量都相互依赖，我只是从最初的猜测中寻找局部最小值。我已经开始使用 hessian 矩阵实现；但是，这涉及很多。有没有什么可以做到这一点，有没有更简单的方法，或者有什么建议可以开始？

所以主要问题如下：是否有一种算法可以先进行猜测，生成多个猜测，然后使用这些多个猜测来创建新的猜测，然后重复直到找到阈值。只有解析导数可用。什么是解决这个问题的好方法，是否已经建立了可以做到这一点的东西，还有其他选择吗？

感谢您的时间。

作为一个小更新，我确实通过计算每个维度的三个点的简单抛物线，然后使用最小值作为下一个猜测来完成这项工作。这似乎工作得很好，但不是最佳的。我仍在寻找其他选择。

当前最好的实现是并行化鲍威尔方法的内循环。

谢谢大家的意见。不幸的是，对于这个特定问题，似乎没有一个简明的答案。如果我开始实施一些可以做到这一点的东西，我会把它贴在这里；但是，由于该项目不是特别重要或需要紧迫的结果，我可能会满足于让它占用一个节点一段时间。

4

7 回答 7

3

我在大学时遇到了同样的问题，我们有一个 fortran 算法来计算基于一组变量的引擎的效率。当时我们使用 modeFRONTIER，如果我没记错的话，没有一个算法能够产生多个猜测。

正常的方法是有一个 DOE，并在那里有一些算法来生成 DOE 以最适合您的问题。之后，我们将并行运行单个 DOE 条目，并且算法将“观察”显示当前最佳设计的优化的发展。

旁注：如果您没有集群并且需要更多计算能力，HTCondor 可能会帮助您。

于 2012-12-14T01:00:34.543 回答
1

估计梯度有两种方法，一种容易并行化，一种不能：

  • 围绕单个点，例如 (f( x + h 方向i ) - f(x)) / h；这很容易并行到 Ndim
  • “行走”梯度：从 x 0沿方向 e 0走到x 1，然后从 x 1沿方向 e 1走到x 2 ...；这是顺序的。

使用梯度的最小化器高度发达，功能强大，二次收敛（在足够平滑的函数上）。用户提供的梯度函数当然可以是一个并行梯度估计器。
一些最小化器使用“行走”梯度，其中包括 Powell 方法，请参阅Numerical Recipes p。509.
所以我很困惑：你如何并行化它的内部循环？

我建议使用并行梯度估计器的 scipy fmin_tnc ，可能使用中心差异，而不是单边差异。
（Fwiw， 这 比较了两个 10 维函数上的一些 scipy 无导数优化器；ymmv。）

于 2012-12-11T13:55:38.753 回答
1

您的目标函数的导数是否可用？如果是，您可以使用梯度下降（旧的、缓慢但可靠的）或共轭梯度。如果不是，您可以使用有限差分来近似导数，并且仍然使用这些方法。我认为一般来说，如果对导数使用有限差分近似，那么使用共轭梯度而不是牛顿法会好得多。

更现代的方法是SPSA，它是一种随机方法，不需要导数。对于某些表现良好的问题，SPSA 需要对相同收敛速度的目标函数的评估比对共轭梯度的有限差分逼近要少得多。

于 2012-12-10T09:24:01.360 回答
0

我认为您想要做的是使用 python 内置的线程功能。只要您的工作功能具有或多或少相同的运行时间，无论参数如何，它都会很有效。

在池中创建 8 个线程，运行 8 个函数实例，获得 8 个结果，运行优化算法以更改具有 8 个结果的参数，重复.... 利润？

于 2012-12-08T02:11:23.010 回答
0

您可以在两个部分进行并行：1）并行计算单次迭代或 2）并行开始 N 初始猜测。

在 2) 上，您需要一个作业控制器来控制 N 个初始猜测发现线程。

请在您的程序中添加一个额外的输出：“下限”，表示当前输入参数的输出值不会低于此下限。

初始的N个猜测线程可以相互竞争；如果任何一个线程的下限高于现有线程的当前值，则您的作业控制器可以删除该线程。

于 2012-12-14T03:04:01.440 回答
0

如果我没有弄错您的要求，那么您当时正试图最小化您的函数一个参数。

您可以通过创建一组单个参数的函数来获得它，其中对于每个函数，您冻结除一个之外的所有参数。

然后您继续循环优化每个变量并更新部分解决方案。

这种方法可以通过许多参数的大量函数来加速，其中能量景观不是太复杂（参数之间的依赖性不是太强）。

给定一个函数

energy(*args) -> value

您创建猜测和函数：

guess = [1,1,1,1]
funcs = [ lambda x,i=i: energy( guess[:i]+[x]+guess[i+1:] ) for i in range(len(guess)) ]

比你把它们放在一段时间循环中进行优化

while convergence_condition:
    for func in funcs:
        optimize fot func
        update the guess
    check for convergence

这是简化最小化任务的一种非常简单但有效的方法。我真的不记得这个方法是如何被调用的，但是仔细查看关于最小化的维基百科条目应该可以解决问题。

于 2012-12-10T00:15:37.793 回答
0

并行化局部优化器本质上是有限的：它们从单个初始点开始并尝试下坡工作，因此后面的点取决于先前评估的值。尽管如此，还是有一些途径可以添加适量的并行化。

  • 正如另一个答案指出的那样，如果您需要使用有限差分方法评估您的导数，最好使用自适应步长，这可能需要多次函数评估，但每个变量的导数可能是独立的；您可能会获得两倍于问题维度数量的加速。如果您的处理器数量超出了您的了解，您可以使用需要更多（并行）评估的高阶准确梯度公式。
  • 一些算法，在某些阶段，使用有限差分来估计 Hessian 矩阵；这需要大约一半的矩阵维数平方，并且所有这些都可以并行完成。

一些算法还可以以适度的算法成本使用更多的并行性。例如，准牛顿方法尝试构建 Hessian 矩阵的近似值，通常通过评估梯度来更新它。然后他们向最小值迈出一步，并评估一个新的梯度来更新 Hessian。如果您有足够的处理器，以便评估 Hessian 与评估一次函数一样快，您可能可以通过在每一步评估 Hessian 来改进这些。

就实现而言，恐怕你有点不走运。那里有许多聪明和/或经过良好测试的实现，但据我所知，它们都是单线程的。您最好的选择是使用需要梯度并并行计算您自己的算法。编写一个并行运行并为其数值导数选择合理步长的自适应算法并不难。

于 2017-07-07T16:17:41.190 回答