最小化一个缓慢、嘈杂、定义不清的目标函数
我的问题是：有没有一些最小化算法，最好是用Python实现的，能够处理一个运行比较慢（大约1-10秒）并且从实时系统获取数据的函数，而且完成时间不超过几个小时？
我有一个FPGA，它对一些传感器数据进行滤波，并利用这个滤波的输出改善另一个设备的性能。我想找到最佳的滤波器。我之前尝试建模系统并使用各种信号处理技术，但结果不太理想，所以现在我打算在实时系统上解决这个问题（至少是为了证明这样的最佳滤波器是可能的）。
这个滤波器可以通过串口编程，而另一个设备的性能也可以通过串口测量。
所以我可以构建一个函数，它：
- 接受定义滤波器的参数
- 通过串口编程滤波器
- 通过串口获取数据
- 计算滤波器的好坏（越小越好）
这意味着我有一个可以用作最小化目标的函数。不过，这里有几个问题：
运行很慢
编程滤波器大约需要1.5秒，获取数据以测量滤波器的好坏大约需要6秒。总共，每次调用这个函数大约需要8秒。换句话说，仅仅调用500次就需要超过一个小时。即使加快通信和计算速度，也可能不会有太大改善。
定义不明确
（注意，下面的x是我目标函数的参数空间中的一个向量。）
简单来说，x1 == x2 并不意味着 f(x1) == f(x2)。由于系统的噪声，在参数空间的同一点上采样目标函数f(x)可能会因为系统的噪声而得到不同的结果。
我想到的第一个办法是让目标函数实际平均多个测量值，并增加我正在运行的最小化程序的容差值。但根据实际数据，在最坏的情况下，f(x)的（均值）值在整个参数范围内可能变化2.0，而样本标准差是1.6。这意味着如果我想将标准误差（s/sqrt(n)）降低到0.1，我需要测量同一点250次，这样每次测量就需要30分钟。太棒了。
我可以采取一些技巧来改善这个，比如在参数范围内获得约20的波动，并在任何给定点的标准差为0.25。但这些技巧在时间上也有其他的权衡。
妥协
好消息是，在整个优化空间中绘制函数（大幅平均后）（我已经做过以确认确实存在全局最小值）显示这个函数实际上相当平滑，最小值也不是太尖锐。另一个好消息是，这个指标只需要优化到两到三个有效数字。如果不是这么慢，优化起来就简单多了。
我开始查看SciPy中的最小化程序，但由于许多参数没有文档说明或相互依赖，这让我有点摸不着头脑（每一步都需要几个小时）。
我觉得我真正需要的是一种已知能在最少函数调用次数下工作的优化算法；不过也许还有其他我没有考虑到的方法。
3 个回答
这不是一个解决方案，而是一些需要考虑的事项。我会使用类似下面的步骤：用N个样本来近似你的函数，然后根据这个近似值选择一个新的点，并不断重复这个过程。我在处理带有大量参数的噪声数据时也用过类似的方法。下面是一些更详细的说明：
用N个值来近似你的函数（可能会以某种方式加权）。可以选择的方式有：
- RANSAC
- 最小二乘法近似
- 最大似然估计
你选择哪种方法取决于你对误差行为的预期。
根据近似的函数选择一个新的样本位置，并把这个值放入N中，同时丢掉其他N个点中的一个。这样做的方法有很多，部分取决于你选择的近似函数。一些选项包括：
- 直接跳到近似函数的最小值。
- 进行一步最陡下降（速度慢，但收敛性好）。
- 进行一步共轭梯度（收敛速度更快，但不一定总能收敛）。
还有很多其他的选择。
至于如何丢掉N个点中的一个，也有很多讨论的空间。可以选择的方式包括：
- 随机选择一个
- 选择最旧的
- 选择离最新样本最远的
- 选择离“最佳”点最远的
- 选择与近似模型偏差最大的那个。
这个叫做scikit-optimize（简称skopt）的工具包就是为了处理这种情况而设计的：慢慢的、带有噪声的目标函数。它使用一种叫做高斯过程的数学方法来模拟目标函数，并在不确定的点（为了改善模型）和可能表现不错的点之间切换进行评估。他们的例子中大约需要进行100次评估才能找到最小值。这个工具包甚至有一个专门针对物理实验的接口，它会建议一些试验值，你进行实验后把结果反馈给它，然后它会再建议更多的试验值。
我觉得这是一个合理的使用场景，可以用Metropolis优化来解决。这是早期的马尔可夫链蒙特卡洛方法的一个例子，可以基本不变地应用到你的情况中。
在每一步中，你会在参数空间中随机提出一个新的步骤，并把适应度定义为exp(-(1/thing_to_minimize))。对于适应度提高的步骤，你都可以接受；而对于其他步骤，则以current_fitness/previous_fitness的比例随机接受。运行一段时间后，你可以开始对参数空间中的位置进行简单的平均。
你还可以通过随着时间的推移减少平均步长的大小，来增加一个模拟退火的效果，让过程更有趣。
我之前在Stack Overflow上写过几次相关内容，但你可以在软件调优/校准启发式算法属性中找到我最完整的描述。