局部搜索算法

局部搜索算法
局部搜索算法不关注路径，而是从单个当前节点只移动到他的邻近状态。局部搜索算法也常用于解决最优化问题。

1. 爬山法(Hill-climbing)
贪心局部搜索，每次向值最优的邻接状态移动。当所有邻点的值都不超过当前结点时终止。

随即重启爬山法(random restart hill climbing): 每次随机生成一个初始状态开始爬山。
随机爬山法(random sideway moves): 随机选择下一步，被选中的概率依目标函数增益而定。

2. 模拟退火(Simulated annealing)
随机选择一个后继结点。
如果该移动对函数值有增益，则接受。否则，如果损失为\(\Delta E\), 以\(e^{\frac{\Delta E}{T}}\)的概率选择。T为超参数。

3. 局部束搜索(Local Beam Search)
局部束搜索是对束搜索(Beam Search)的改版，每次记录k个状态而不是1个。
每步搜索从当前k个结点的全部后继中选择最好的k个进行更新。
注意，这并不等同于k个相同的搜索算法并行，因为可能会有同一个结点的多个后继被纳入新的维护结点中，同时也可能有结点因为所有后继都不够好而被放弃。

    所属分类：人工智能     发表于2022-05-18