寻找一个算法，可返回局部最小值

Question

所有我所知的针对黑盒函数的优化算法，如模拟退火或贝叶斯优化，都会返回全局最小值。

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

是否有任何算法可以解决这个任务？

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

- user7468395

---

你提到的那些方法尝试返回一些全局最小值，但我怀疑很多库都无法给出保证（一个著名的例外是Couenne）。这是有原因的：潜在问题通常是NP难题。这种复杂性归结为：可能存在指数级数量的局部最小值。仍然希望枚举所有最小值吗？即使假设时间无限，情况也会变得更糟，因为枚举可能性需要一些合理而完整的证明系统来推理最小值枚举状态。拥有不以指数级内存增长的证明系统通常在时间上更糟。 - sascha

假设您获得了所有20'000'000个本地最小值的列表。对此，您想要做什么？ - maxy

@maxy：我正在寻找解决我的问题的任何方案，问题描述在这里：https://stackoverflow.com/q/57375144/10698244 - user7468395

不太容易，特别是对于没有梯度的黑盒函数。可以使用网格并针对每个区域进行优化。 - Erwin Kalvelagen

Answer 1

你是否在问是否有一些全局最小值算法也可以返回局部最小值？

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

不能保证元启发式算法（通常用于解决NP难问题）将探索整个搜索空间，因此不能保证找到每个局部最小值。然而，我假设你已经知道这一点，你想要的是修改一种方法，使其在寻找全局最小值的过程中提供一个局部最小值列表，而不仅仅是一个找到的最佳解决方案。

基于单解决方案的算法，如Tabu搜索、迭代局部搜索等，是基于局部搜索的。它们执行局部搜索，直到找到局部最优解，然后应用各自的规则尝试逃离局部最小值。让我们考虑迭代局部搜索，它执行局部搜索直到找到局部最优解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上找到一个好的实现来作为编码的基础。

- WillEnsaba