det*_*tly 5 python mathematical-optimization
我的问题是:是否存在最小化算法,最好用Python实现,可以在一个慢速(~1-10s)的函数上运行,并从实时系统中获取数据,这不需要花费几个小时才能完成？
我有一个FPGA,它运行一些传感器数据的过滤器,并使用该过滤器的输出来提高另一个设备的性能.我想找到最佳的过滤器.我对系统建模和使用各种信号处理技术的尝试没有产生足够的结果,所以现在我将尝试在实时系统本身上解决这个问题(如果有的话,只是为了证明这样的最佳滤波器是可能的).
可以通过串行线对滤波器进行编程,并且可以通过串行线测量其他器件的性能.
所以我可以构造一个函数:
这意味着我有一个可以用作最小化目标的函数.以下是问题:
要对滤波器进行编程大约需要1.5秒,要获取数据来测量滤波器的良好性大约需要6s.总而言之,每个函数调用接近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中的最小化例程,但由于许多参数都是未记录的或相互依赖的,所以它在黑暗中有点散步(每个步骤需要几个小时).
令我感到震惊的是,我真正需要的是一种已知在最少数量的函数调用中工作的优化算法; 虽然可能还有另一种我没有考虑过的方法.
我认为这是Metropolis 优化的合理用例。这是马尔可夫链蒙特卡罗的早期示例之一，可以或多或少不变地应用于您的用例。
在每个步骤中，您在参数空间中提出一个随机步骤，并将适应度定义为exp(-(1/thing_to_minimize))。接受任何建议的适应度增长的步骤，而其他步骤则随机增长一小部分current_fitness/previous_fitness。运行一段时间后，简单地开始平均参数空间中的位置。
您可以通过减小平均步长作为时间的函数来添加模拟退火方面，以实现额外的装饰。
我之前曾在 Stack Overflow 上写过几次有关此内容的文章，但您可以在Software to Tune/Calibrate Properties for Heuristic Algorithms上找到我最完整的描述。