批量随机搜索
在这种方法中，我决定将我的25个实验预算分成5批，每批5个实验。 查找（x，y）值在每个批次内是随机的。 同时，在每个批次结束时，优胜者会被挑出来进行特殊处理。 采用对象不是在空间中任何地方生成的点，而是在这些点周围绘制一个窗口，并且仅从这些空间进行采样。 在每次迭代时，窗口会进行几何收缩。我试图寻找到目前为止找到的最优点的邻域中的点，希望这个搜索将产生更多的最优点。 同时，我保留剩余的实验探索空间，希望我可能找到另一个最佳点。 其代码如下所示：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 | def cooling_schedule(n, k): ''' 每次运行时减少窗口的大小 n – 批次数目 k – 当前批次的索引号 返回 乘数(0..1) 的大小 ''' return (n - k) / n
results, winners = [], [] for bid in range(5): print('Batch #: {:d}'.format(bid), end='')
# 计算窗口大小 window_size = int(0.25 * cooling_schedule(5, bid) * SIZE)
# 计算出优胜者并把其值加入结果中 # 只保持最优的两点 for x, y, _, _ in winners: if x < SIZE // 2: # 中左区 xleft = max(x - window_size // 2, 0) xright = xleft + window_size else: # 中右区 xright = min(x + window_size // 2, SIZE) xleft = xright - window_size if y < SIZE // 2: # 下半区 ybot = max(y - window_size // 2, 0) ytop = ybot + window_size else: # 上半区 ytop = min(y + window_size // 2, 0) ybot = ytop - window_size xnew = np.random.randint(xleft, xright, 1)[0] ynew = np.random.randint(ybot, ytop, 1)[0] znew = terrain[xnew, ynew] results.append((xnew, ynew, znew, bid))
# 添加剩余随机点 for i in range(5 - len(winners)): x = np.random.randint(0, SIZE, 1)[0] y = np.random.randint(0, SIZE, 1)[0] z = terrain[x, y] results.append((x, y, z, 2))
# 找出最优两点 winners = sorted(results, key=operator.itemgetter(2))[0:2] print(' best: ', winners[0])
best_xyz = sorted(results, key=operator.itemgetter(2))[0] print(best_xyz)
xvals = [r[0] for r in results] yvals = [r[1] for r in results]
plt.title('batched random search') contour = plt.contour(terrain, linewidths=2) plt.ylim(max(plt.ylim()), min(plt.ylim())) plt.scatter(xvals, yvals, color='b', marker='o') plt.scatter([best_xyz[0]], [best_xyz[1]], color='b', s=200, facecolors='none', edgecolors='b') plt.colorbar(contour) |
结束时此空间中的全局最小点坐标（707,682），值为20。
显然，并不是所有的运行都是如此顺利的，也很有可能从上述任何方法发现的点只是一个局部最小值。 此外，没有理由假定网格搜索可能不优于随机搜索，因为随机地形可能在其中一个均匀布置的点下面具有其全局最小点，并且随机搜索可能错过该点。
为了检查这个假设，我对1000个随机地形批量运行上面的代码。 对于每个地形，我为3种方法中的每一种运行25个实验，并为每个方法找到最低（最优）点。我这样做了两次，以确保结果的客观性。代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | TERRAIN_SIZE = 1024 NUM_HILLS = 200
NUM_TRIALS = 1000 NUM_SEARCHES_PER_DIM = 5 NUM_WINNERS = 2
nbr_random_wins = 0 nbr_brand_wins = 0 for i in range(NUM_TRIALS): terrain = build_terrain(TERRAIN_SIZE, NUM_HILLS) grid_result = best_grid_search(TERRAIN_SIZE, NUM_SEARCHES_PER_DIM) random_result = best_random_search(TERRAIN_SIZE, NUM_SEARCHES_PER_DIM**2) batch_result = best_batch_random_search(TERRAIN_SIZE, NUM_SEARCHES_PER_DIM, NUM_SEARCHES_PER_DIM, NUM_WINNERS) print(grid_result, random_result, batch_result) if random_result < grid_result: nbr_random_wins += 1 if batch_result < grid_result: nbr_brand_wins += 1
print('# times random search wins: {:d}'.format(nbr_random_wins)) print('# times batch random search wins: {:d}'.format(nbr_brand_wins)) |
执行结果如下：
1 2 3 4 5 6 7 8 9 | Run-1 ------ #-times random search wins: 619 ‘随机搜索优胜次数 #-times batch random search wins: 638 ‘随机批量搜索优胜次数
Run-2 ------ #-times random search wins: 640 ‘随机搜索优胜次数 #-times batch random search wins: 621随机批量搜索优胜次数 |
结果表明随机搜索似乎比网格搜索稍好（因为第一个数字超过500）。 此外，批量版本不一定更好，因为纯随机搜索在第二次运行有更好的结果。
以上是我实验的结果。在这个过程中，我学习了一个有趣的算法来生成地形，也为自己解除了困惑。如果你想亲自尝试，不妨阅读本文核心笔记（链接）以及批处理运行Python版本代码（链接）。
作者简介：
Sujit Pal是一名程序员，在Healline Networks担任技术管理。喜好研究编程语言Java和Python，喜欢从多角度研究和解决问题。
本文由北邮@爱可可-爱生活 老师推荐，阿里云云栖社区组织翻译。
文章原标题《Random vs Grid Search: Which is Better?》，作者：Sujit Pal ，译者：伍昆
苏公安网备 32011402010933号