爬山算法的实例应用

下面是一个用爬山算法求解问题的例子动画中展示了算法的搜索过程以及目标函数值随迭代步数的变化。上面的算法顺利的通过了所有测试用例但是这依赖于一个假设“该问题是一个凸优化问题”从上面的目标函数变化曲线可以看出来曲线是一直在下降的直到停留在最低点。幸运的是这个问题确实是一个凸优化问题证明过程在本题的官方题解里面。假如我们没法证明这是个凸优化问题是否存在一种更通用的算法来解决该问题呢答案是有的就是模拟退火算法模拟退火算法的思路也很简单就是为算法引入一定的随机性让它有一定的能力去跳出局部最优解。让我们对前面爬山算法的伪代码稍作改造# 模拟退火算法伪代码 cur_sol init() while not stop: for new_sol in neighbor(cur_sol): delt obj(new_sol) - best_obj可以看到在算法刚开始运行时 noise 的值较大那么当前解的变化趋向于随机移动。但随着 noise 的降低算法接受较差的解的概率逐渐减小最终退化成前面的爬山算法。这样做的目的是使算法能够更充分的探索解空间所以对于非凸优化的问题模拟退火算法通常能够比爬山法找到更优的解在实际生活中也有着更加广泛的应用。