f(x,y) 的最小化，其中 x 和 y 是整数
我想知道是否有人对最小化函数 f(x,y) 有任何建议，其中 x 和 y 是整数。 我研究了很多最小化和优化技术，比如 BFGS 和 GSL 中的其他技术，以及 Numerical Recipes 中的东西。 到目前为止，我已经尝试实施几种不同的方案。 第一个方法是选择最大下降方向 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)
}
I was wondering if anyone had any suggestions for minimizing a function, f(x,y), where x and y are integers. I have researched lots of minimization and optimization techniques, like BFGS and others out of GSL, and things out of Numerical Recipes. So far, I have tried implenting a couple of different schemes. The first works by picking the direction of largest descent f(x+1,y),f(x-1,y),f(x,y+1),f(x,y-1), and follow that direction with line minimization. I have also tried using a downhill simplex (Nelder-Mead) method. Both methods get stuck far away from a minimum. They both appear to work on simpler functions, like finding the minimum of a paraboloid, but I think that both, and especially the former, are designed for functions where x and y are real-valued (doubles). One more problem is that I need to call f(x,y) as few times as possible. It talks to external hardware, and takes a couple of seconds for each call. Any ideas for this would be greatly appreciated.
Here's an example of the error function. Sorry I didn't post this before. This function takes a couple of seconds to evaluate. Also, the information we query from the device does not add to the error if it is below our desired value, only if it is above
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)
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
这里有很多很多的解决方案。 事实上，有基于该主题的完整书籍和学科。 我现在正在阅读一篇精彩的文章：如何解决它：现代启发式 。
没有一种解决方案是正确的 - 根据您的功能的具体知识，不同的解决方案具有不同的优势。 甚至已经证明，没有一种启发式方法能够在所有优化任务中表现最好。
如果您知道您的函数是二次函数，则可以使用 牛顿高斯 一步求出最小值。 遗传算法可以是一个很好的通用工具，或者您可以尝试模拟退火，这不太复杂。
There are many, many solutions here. In fact, there are entire books and academic disciplines based on the subject. I am reading an excellent one right now: How to Solve It: Modern Heuristics.
There is no one solution that is correct - different solutions have different advantages based on specific knowledge of your function. It has even been proven that there is no one heuristic that performs the best at all optimization tasks.
If you know that your function is quadratic, you can use Newton-Gauss to find the minimum in one step. A genetic algorithm can be a great general-purpose tool, or you can try simulated annealing, which is less complicated.
你看过遗传算法吗？ 他们非常非常擅长寻找最小值和最大值，同时避免局部最小值/最大值。
Have you looked at genetic algorithms? They are very, very good at finding minimums and maximums, while avoiding local minimum/maximums.
你如何定义 f(x,y) ？ 最小化是一个难题，具体取决于函数的复杂性。
遗传算法可能是一个不错的选择。
资源：
搜索、优化和机器学习中的遗传算法
在 C# 中实现遗传算法
简单的 C# GA
How do you define f(x,y) ? Minimisation is a hard problem, depending on the complexity of your function.
Genetic Algorithms could be a good candidate.
Resources:
Genetic Algorithms in Search, Optimization, and Machine Learning
Implementing a Genetic Algorithms in C#
Simple C# GA
如果它是一个任意函数，则没有巧妙的方法来执行此操作。
假设我们有一个函数定义为：
任何算法如何才能真正找到 (100, 100) 作为最小值？ 它可以是任何可能的值组合。
您对您正在测试的功能了解任何吗？
If it's an arbitrary function, there's no neat way of doing this.
Suppose we have a function defined as:
How could any algorithm realistically find (100, 100) as the minimum? It could be any possible combination of values.
Do you know anything about the function you're testing?
您通常寻找的是数学中的优化技术。 一般来说，它们适用于实值函数，但许多可以适用于积分值函数。
特别是，我建议研究非线性编程和梯度下降。 两者似乎都非常适合您的应用。
如果您可以提供更多详细信息，我也许可以提出更具体的建议。
What you are generally looking for is called an optimisation technique in mathematics. In general, they apply to real-valued functions, but many can be adapted for integral-valued functions.
In particular, I would recommend looking into non-linear programming and gradient descent. Both would seem quite suitable for your application.
If you could perhaps provide any more details, I might be able to suggest somethign a little more specific.
乔恩·斯基特的回答是正确的。 即使 f 处处连续，您确实需要有关 f 及其导数的信息。
理解你所要求的困难（仅在整数值处最小化 f）的最简单方法就是考虑一个变量的 f：R->R（f 是实数的实值函数），该变量使得很大各个整数之间的偏移。 您可以轻松构造这样一个函数，使得实线上的局部最小值与整数处的最小值之间不存在相关性，并且与一阶导数没有关系。
对于任意函数，除了暴力之外，我看不出有什么办法。
Jon Skeet's answer is correct. You really do need information about f and it's derivatives even if f is everywhere continuous.
The easiest way to appreciate the difficulties of what you ask(minimization of f at integer values only) is just to think about an f: R->R (f is a real valued function of the reals) of one variable that makes large excursions between individual integers. You can easily construct such a function so that there is NO correllation between the local minimums on the real line and the minimums at the integers as well as having no relationship to the first derivative.
For an arbitrary function I see no way except brute force.
那么让我们用数学的方式来看看你的问题。 这一切都假设我理解
你的问题完全。 如果我错了，请随时纠正我。
我们想要最小化以下内容：
\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^*))。
现在你说你的函数可能很难评估。 已有工具存在
为此，这不是基于启发式的。 名称为“Derivative-Free”
优化。 人们使用这些工具根据模拟来优化目标（我有
甚至听说过目标函数基于作物播种产量的情况！）
这些方法中的每一种都有不同的属性，但总的来说，它们试图
不仅要最小化目标，还要最小化目标函数评估的数量。
So let's look at your problem in math-speak. This is all assuming I understand
your problem fully. Feel free to correct me if I am mistaken.
we want to minimize the following:
\sqrt((a-a_desired)^2 + (b-b_desired)^2 + (c-c_desired)^2)
or in other notation
||Pos(x - x_desired)||_2
where x = (a,b,c) and Pos(y) = max(y, 0) means we want the "positive part"(this accounts
for your if statements). Finally, we wish to restrict ourself
to solutions where x is integer valued.
Unlike the above posters, I don't think genetic algorithms are what you want at all.
In fact, I think the solution is much easier (assuming I am understanding your problem).
1) Run any optimization routine on the function above. THis will give you
the solution x^* = (a^*, b^*,c^*). As this function is increasing with respect
to the variables, the best integer solution you can hope for is
(ceil(a^*),ceil(b^*),ceil(c^*)).
Now you say that your function is possibly hard to evaluate. There exist tools
for this which are not based on heuristics. The go under the name Derivative-Free
Optimization. People use these tools to optimize objective based on simulations (I have
even heard of a case where the objective function is based on crop crowing yields!)
Each of these methods have different properties, but in general they attempt to
minimize not only the objective, but the number of objective function evaluations.
抱歉，之前的格式太糟糕了。 这是误差函数的示例
Sorry the formatting was so bad previously. Here's an example of the error function