python - 寻找一种算法，也可以返回局部最小值

Question

我知道的所有黑盒函数优化算法，如模拟退火或贝叶斯优化，都提供了全局最小值。

我正在寻找一种 python 算法，它可以将全局和所有局部最小值返回给我。

有没有解决这个任务的算法？

或者是否有任何全局最小算法也可以返回局部最小值？

标签： pythonmathematical-optimizationgenetic-algorithmbayesiansimulated-annealing

Answer 1

或者是否有任何全局最小算法也可以返回局部最小值？

我不明白你所说的全局最小算法是什么意思，但既然你提到了模拟退火，我会假设你在谈论具有全局搜索能力的元启发式算法。

无法保证经常用于解决 NP 难题的元启发式算法会探索整个搜索空间，因此无法保证找到每个局部最小值。但是，我假设您知道这一点并且您想要的是以一种方法来修改它，而不仅仅是一种解决方案（最好找到），一个在查找全局最小值的过程中找到的局部最小值列表。

基于单一解决方案的算法，如禁忌搜索、迭代局部搜索等，都是基于局部搜索工作的。他们执行局部搜索，直到找到局部最优解，然后，他们应用各自的规则试图摆脱局部最小值。让我们考虑迭代局部搜索，它执行局部搜索，直到解决方案S局部最优，然后它扰动当前的局部最优以摆脱它并在搜索空间中获取另一个点再次执行局部搜索，直到满足条件。在您的情况下，您应该每次在搜索过程中找到一个局部最优解。

下面的伪代码是修改后的 ILS 算法，以保留在搜索过程中找到的所有局部最优解。

HillClimbing(S)
   while S is not locally optimal do
       S ← best(N(S)) // best solution in neighborhood N of solution S
   Return S

IteratedLocalSearch()
    L ← {} // set of locally optimal solutions
    G ← randomSolution()
    S ← G
    while criterionIsNotMeet() do
        HillClimbing(S)
        Add S to L // add the current local
        if S.objective < G.objective do // minimization
            G ← S // best solution found
        perturbateSolution(Copy(S))

这种算法很容易实现。如果您决定自己实现，请获得一份好的参考论文，如果这还不够，您可以尝试在 GitHub 或 Mathworks 发现上找到一个好的实现来作为您编码的基础。