Skip to main content
 首页 » 编程设计

python之寻找一种也能返回局部最小值的算法

2024年11月24日10虾米哥

我所知道的黑盒函数的所有优化算法,如simulated annealing或 Bayesian optimization提供全局最低返回。

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

是否有解决此任务的算法?

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

请您参考如下方法:

Or is there any of the global minimum algorithms that deliver also the local minima back?

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

不能保证通常用于解决 NP-hard 问题的元启发式算法会探索整个搜索空间,因此,不能保证找到每个局部最小值。但是,我假设您知道这一点,并且您想要的是以一种方法提供的方式修改方法,而不仅仅是一个解决方案(最佳找到),即在查找全局最小值的过程中找到的局部最小值列表。

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