algorithm - n维空间中的爬山：寻找邻居

Question

在 1 维的爬山中，我尝试了两个邻居 - 我当前点左侧的一个小增量和一个右侧的小增量，然后保留提供更高目标函数值的那个。如何将其扩展到 n 维空间？如何为 n 维空间定义邻居？我是否必须尝试 2^n 个邻居（应用于每个维度的增量）？

Answer 1

您不需要比较每对邻居，您需要计算一组邻居，例如在半径为 delta 的圆（更高维度的球体/超球体）上，然后将具有最高值的那个“爬上”。在任何情况下，您都将离散化当前解决方案的邻域并计算每个邻域的得分函数。当您可以区分您的功能时，基于梯度上升/下降的算法可能会解决您的问题：1）计算梯度（最陡上升的方向） 2）向梯度方向迈出一小步 3）如果解决方案没有，则停止改变

这些算法的一个常见问题是，您通常只能找到局部最大值/最小值。你可以在这里找到关于梯度下降/上升算法的一个很好的概述：http: //sebastianruder.com/optimizing-gradient-descent/

Answer 2

如果您使用的是 IEEE-754 浮点数，那么显而易见的答案就是(2^52*(log_2(delta)+1023))^(n-1)+1if delta>=2^(-1022)（或多或少取决于您的搜索空间...），因为这是您可以确定没有更多相邻解决方案的唯一方法的距离delta。

即使假设您取而代之的是在给定的 delta 距离内对所有点进行随机固定大小的样本，假设 delta=.1，您仍然会遇到问题，如果与局部最优的距离为 0.0001，则找到改进的概率仅在一维中会小于，.0001/.1/2=0.05%因此当您接近局部最优值（您不知道其值......）时，您将需要越来越多的随机样本。

显然，爬山不适用于实数空间或具有无限度的理论图空间。您应该改为使用全局搜索算法。

Answer 3

仅需要 O(n) 个邻居而不是 O(2^n) 个邻居的多维搜索算法的一个示例是多向搜索：并行机器的直接搜索算法(1989) 中描述的 Torczon 单纯形法。我选择了这个而不是更广为人知的 Nelder-Mead 方法，因为 Torczon 单纯形法具有收敛证明（在某些合理条件下收敛到局部最优）。