连续空间的局部搜索

4.4 连续空间的局部搜索

在第二章中，我们解释了离散和连续空间的区别，指出大多数现实世界环境都是连续的。不过，我们描述过的算法没有一个能够处理连续状态空间——在大多数情况下后继函数将返回无限多个状态！这一节将对一些在连续状态空间上寻找最优解的局部搜索技术进行非常简要的介绍。关于这个主题的文献很多；许多基本技术起源于17 世纪，在牛顿和莱布尼兹发明微积分之后[19]。我们会在本书的一些地方发现这些技术的应用，包括在学习、视觉和机器人技术这几章。简而言之，就是任何涉及现实世界的方面。

让我们从一个例子开始。假设我们想在罗马尼亚建三个新机场，使地图上（图3.2）每个城市到离它最近的机场的距离平方和最小。那么问题的状态空间就由机场的坐标来定义：(x1, y1)，(x2, y2)和(x3, y3)。这是一个六维空间；我们也可以说状态空间由六个变量定义。（一般来讲，状态是由一个 n 维的变量向量x来定义的。）在这个状态空间中移动相当于在地图上移动一个或多个机场的位置。对于一个特定的状态一旦计算出最近的城市，目标函数f(x1, y1, x2, y2, x3, y3)就很容易计算出来了，但是要一般化描述却比较麻烦。

一个简单的避免连续性问题的途径就是将每个状态的邻接状态离散化。例如，我们一次只能将一个飞机场按照x方向或y方向移动一个固定的量±δ。对于6个变量，每个状态有12个后继。然后我们就可以应用之前描述过的任何一个局部搜索算法。也可以不离散化空间就直接应用随机爬山法和模拟退火。这些算法随机地选择后继，通过随机生成长度为δ的向量来完成。

有很多办法试图利用地形图的梯度来找到最大值。目标函数的梯度是一个向量∇ f，它给出了最陡斜面的大小和方向。对于我们的问题，有

在一些情况下，我们可以通过解方程 ∇ f = 0来找到最大值。（这是可以做到的，例如，如果我们只放一个飞机场；那么解就是所有城市坐标的算术平均值。）然而在很多情况下，这个等式不能用封闭的形式解决。例如，当有三个飞机场时，梯度的表达式依赖于当前状态下哪些城市离各个机场最近。这意味着我们只能局部地计算梯度而不能全局地计算。即使这样我们仍然可以通过下述公式更新当前状态来执行最陡上升爬山法：

x←x+α∇ f(x)，

其中α 是一个很小的常数。在其它情况下，目标函数可能根本不能用微分形式表示——例如，特定的机场位置集合的值要通过运行某个大规模经济仿真程序包来决定。在这些情况下，一个所谓的经验梯度可以通过评价每个坐标上的小增减量引起的反应来决定。经验梯度搜索在离散化的状态空间中和最陡上升爬山法是一样的。

在习惯用语“α 是一个很小的常数”背后，隐藏着非常大量的调整α 的不同方法。基本的问题是，如果α 太小，就需要太多的步骤；如果α 太大，搜索容易错过最大值。线搜索技术试图通过扩展当前的梯度方向——通常通过反复使α 加倍——来克服这个困境，直到f开始再次下降。发生的点成为新的当前状态。关于在这点上应该如何选择新方向有几个不同学派的思想。

对于许多问题，最有效的算法是古老的牛顿-拉夫森方法（牛顿，1671；拉夫森，1690）。这是一个找到函数的根的一般方法——即求解形如g(x) = 0的方程式。它根据牛顿公式计算根x的一个新的估计值

x←x – g(x)/g ' (x)。

为了找到f的最大或最小值，我们需要找到梯度为0的x（就是说∇ f(x)＝0）。因此，牛顿公式中的g(x)就变成∇ f(x)，并且更新过的等式可以写成矩阵向量形式

其中Hf(x)是二阶导数的Hessian矩阵，矩阵中的元素Hi j由∂2 f / ∂xi∂xj给出。由于Hessian矩阵有n2个元素，牛顿-拉夫森方法在高维空间中消耗非常大，很多近似方法被开发出来。

局部搜索算法在连续状态空间和离散状态空间一样受到局部极大值、山脊和高原的影响。随机重新开始和模拟退火都可以使用，而且经常比较有用。然而高维的状态空间很容易使这种算法迷失。

最后一个讨论的有用话题是约束最优化。如果问题的解必须满足某些对于每个变量值的严格约束，那么这个最优化问题是受约束的。例如，在我们的机场选址问题中，我们可以限制机场的位置是在罗马尼亚境内，并且是在旱地上（而不是在湖中央）。约束最优化问题的难点取决于约束和目标函数的本性。最著名的一种约束最优化问题是线性规划问题，其约束必须是线性不等式并且能够组成一个凸多边形区域，同时目标函数也是线性的。线性规划问题可以在与变量数有关的多项式时间内求解。有不同类型的约束和目标函数的问题也已经被研究过——二次规划，二阶二次曲线规划，等等。