人工智能/搜索/迭代改进/爬山法

爬山法作为一种优化技术

爬山法是一种用于解决计算难题的优化技术。它最适合用于具有“状态描述本身包含解决问题所需所有信息”特性的问题（Russell & Norvig, 2003）。 该算法在内存效率方面表现出色，因为它不维护搜索树：它只关注当前状态和直接的未来状态。

爬山法尝试通过评估函数迭代改进当前状态。“考虑所有[可能的]状态，它们分布在景观表面上。景观上任意点的海拔高度对应于该点状态的评估函数值”（Russell & Norvig, 2003）。

与其他迭代改进算法相比，爬山法始终尝试进行改进当前状态的更改。换句话说，只有当邻近景观中存在更高点时，爬山法才能前进。

迭代改进和爬山法

爬山法可能遇到的主要问题是局部最大值问题。当算法停止向最优解前进时就会出现这种情况；主要原因是邻近状态中缺乏立即改进。

可以通过多种方法避免局部最大值问题：模拟退火通过允许一些步骤降低当前状态的立即最优性来解决此问题。模拟退火等算法“有时会做出使情况变得更糟的更改，至少是暂时性的”（Russell & Norvig, 2003）。 这使得能够避免搜索路径中的死胡同。

随机重启爬山法

解决局部最大值问题的另一种方法涉及对问题空间进行反复探索。“随机重启爬山法从随机生成的初始状态开始进行一系列爬山搜索，并在每个搜索停止或没有明显进展时运行”（Russell & Norvig, 2003）。 这使得能够比较许多优化试验，从而使找到最优解成为一个使用足够迭代次数来处理数据的问题。

伪代码算法

function HILL-CLIMBING(problem) returns a solution state
     inputs: problem, a problem
     static: current, a node
         next, a node
     current <— MAKE-NODE(INITIAL-STATE[problem])
     loop do
         next— a highest-valued successor of current
         if VALUE[next] < VALUE[current] then return current
         current *—next
     end

(Russell & Norvig, 2003)

计算复杂度

由于使用的评估只关注当前状态，因此爬山法不会遇到计算空间问题。其计算复杂度的来源是探索问题空间所需的时间。

对于大多数问题空间，随机重启爬山法可以在多项式时间内找到最优解。但是，对于一些 NP 完全问题，局部最大值的数量可能是导致指数级计算时间的因素。为了解决这些问题，一些研究人员已经研究使用概率论和局部抽样来指导爬山算法的重启。（Cohen, Greiner, & Schuurmans, 1994）。

应用

爬山法可以应用于任何当前状态允许使用准确评估函数的问题。例如，旅行推销员问题、八皇后问题、电路设计以及各种其他现实世界问题。爬山法已被用于归纳学习模型中。其中一个例子是 PALO，这是一个概率爬山系统，它模拟归纳学习和加速学习。该系统的一些应用已被纳入“基于解释的学习系统”和“效用分析”模型。（Cohen, Greiner, & Schuurmans, 1994）。

爬山法也被用于机器人技术中，以管理多机器人团队。其中一个例子是 Parish 算法，它允许在多机器人系统中进行可扩展且高效的协调。研究小组设计了“一个机器人团队[它]必须协调其行动，以保证定位熟练的逃避者。”（Gerkey, Thrun, & Gordon, 2005）。

他们的算法通过使用爬山法允许机器人选择是单独工作还是团队合作。因此，执行 Parish 的机器人“根据局部进度梯度集体爬山，但随机进行横向或向下移动，以帮助系统摆脱局部最大值。”（Gerkey, Thrun, & Gordon, 2005）。