寻找一种算法，也可以提供局部最小值

Question

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

我正在寻找一种 python 算法，它可以向我提供全局和所有本地最小值。

有没有解决此任务的算法？

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

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 discovery 上找到一个好的实现来作为你的编码基础。