6

我想知道是否有人对最小化函数 f(x,y) 有任何建议，其中 x 和 y 是整数。我研究了很多最小化和优化技术，比如 BFGS 和 GSL 中的其他技术，以及数值食谱中的东西。到目前为止，我已经尝试实施几个不同的方案。第一种方法是选择最大下降的方向 f(x+1,y),f(x-1,y),f(x,y+1),f(x,y-1)，然后按照该方向与线最小化。我也尝试过使用下坡单纯形（Nelder-Mead）方法。这两种方法都离最小值很远。它们似乎都适用于更简单的函数，例如找到抛物面的最小值，但我认为两者，尤其是前者，都是为 x 和 y 是实值（双精度值）的函数而设计的。另一个问题是我需要尽可能少地调用 f(x,y) 。它与外部硬件对话，每次通话需要几秒钟。对此的任何想法将不胜感激。

这是错误函数的示例。抱歉，我之前没有发过这个。这个函数需要几秒钟来评估。此外，如果我们从设备查询的信息低于我们的期望值，它不会添加到错误中，只有当它高于

double Error(x,y)
{
  SetDeviceParams(x,y);
  double a = QueryParamA();
  double b = QueryParamB();
  double c = QueryParamC();
  double _fReturnable = 0;
  if(a>=A_desired)
  {
    _fReturnable+=(A_desired-a)*(A_desired-a);
  }
  if(b>=B_desired)
  {
    _fReturnable+=(B_desired-b)*(B_desired-b);
  }
  if(c>=C_desired)
  {
    _fReturnable+=(C_desired-c)*(C_desired-c);
  }
  return Math.sqrt(_fReturnable)
}
4

8 回答 8

4

这里有很多很多解决方案。事实上，有基于该主题的整本书和学科。我现在正在读一本优秀的书：如何解决它：现代启发式。

没有一种解决方案是正确的 - 根据您对功能的具体了解，不同的解决方案具有不同的优势。甚至已经证明，没有一种启发式算法在所有优化任务中表现最好。

如果你知道你的函数是二次的，你可以使用牛顿-高斯一步找到最小值。遗传算法可以是一个很好的通用工具，或者您可以尝试不那么复杂的模拟退火。

于 2009-07-24T14:46:11.987 回答
3

你看过遗传算法吗？他们非常非常擅长寻找最小值和最大值，同时避免局部最小值/最大值。

于 2009-07-24T14:39:19.813 回答
2

如果它是一个任意函数，那么就没有巧妙的方法可以做到这一点。

假设我们有一个函数定义为：

f(x, y) = 0 for x==100, y==100
          100 otherwise

任何算法如何实际找到 (100, 100) 作为最小值？它可以是任何可能的值组合。

你知道你正在测试的功能吗？

于 2009-07-24T14:40:46.007 回答
2

你如何定义 f(x,y) ？最小化是一个难题，具体取决于函数的复杂性。

遗传算法可能是一个很好的候选者。

资源：

搜索、优化和机器学习中的遗传算法

在 C# 中实现遗传算法

简单的 C# GA

于 2009-07-24T14:40:48.407 回答
1

您通常正在寻找的东西称为数学中的优化技术。通常，它们适用于实值函数，但许多可以适用于整数值函数。

特别是，我建议研究非线性编程和梯度下降。两者似乎都非常适合您的应用程序。

如果您可以提供更多详细信息，我也许可以提出更具体的建议。

于 2009-07-24T14:51:24.863 回答
1

Jon Skeet 的回答是正确的。您确实需要有关 f 及其导数的信息，即使 f 处处是连续的。

理解您所问问题的困难的最简单方法（仅在整数值处最小化 f）就是考虑一个 f：R->R（f 是实数的实数值函数），一个变量会产生大的偏移个别整数之间。您可以轻松地构造这样一个函数，以便实线上的局部最小值与整数的最小值之间没有相关性，并且与一阶导数没有关系。

对于任意函数，我认为除了蛮力之外别无他法。

于 2009-07-24T15:26:28.270 回答
1

所以让我们看看你的数学问题。这一切都假设我完全理解你的问题。如果我错了，请随时纠正我。

我们希望最小化以下内容：

\sqrt((a-a_desired)^2 + (b-b_desired)^2 + (c-c_desired)^2)

或其他表示法||Pos(x - x_desired)||_2

其中 x = (a,b,c) 和 Pos(y) = max(y, 0) 表示我们想要“积极的部分”（这说明了您的 if 语句）。最后，我们希望将自己限制在 x 为整数值的解决方案中。

与上述海报不同，我认为遗传算法根本不是您想要的。
事实上，我认为解决方案要容易得多（假设我理解你的问题）。

1) 对上述函数运行任何优化例程。这将为您提供解决方案 x^* = (a^*, b^*,c^*)。由于这个函数随着变量的增加而增加，你可以期望的最佳整数解是 (ceil(a^*),ceil(b^*),ceil(c^*))。

现在您说您的功能可能难以评估。存在不基于启发式的工具。名称为无衍生优化。人们使用这些工具来优化基于模拟的目标（我什至听说过目标函数基于农作物产量的案例！）

这些方法中的每一种都具有不同的属性，但通常它们不仅试图最小化目标，而且还试图最小化目标函数评估的数量。

于 2009-08-13T00:36:40.450 回答
0

抱歉，之前的格式太差了。这是错误函数的示例

double Error(x,y)
{
SetDeviceParams(x,y);
double a = QueryParamA();
double b = QueryParamB();
double c = QueryParamC();
double _fReturnable = 0;
if(a>=A_desired)
{
  _fReturnable+=(A_desired-a)*(A_desired-a);
}
if(b>=B_desired)
{
 _fReturnable+=(B_desired-b)*(B_desired-b);
}
if(c>=C_desired)
{
  _fReturnable+=(C_desired-c)*(C_desired-c);
}
return Math.sqrt(_fReturnable)
}
于 2009-07-24T15:26:58.053 回答