步长与局部导数成正比的Hill Climbing算法停滞问题排查

我正在实现一款步长与特定点的局部导数/梯度成正比的Hill Climbing算法，但算法出现了无法理解的停滞情况。例如从起点(1.0, 1.0)出发，路径为：(1.0, 1.0) -> (2.0, 0.0) -> (2.0, 3.5) -> (2.0, 3.8) -> (2.0, 5.5) -> (2.0 5.4)。

已测试过生成函数，确认其运行正常，代码如下：

import numpy as np

def generate_surrounding(pos: np.ndarray, delta: np.ndarray):
    dx, dy = delta
    x, y = pos

    dxs = [-dx, 0, dx]
    dys = [-dy, 0, dy]

    X, Y = np.meshgrid(dxs, dys)

    X = list(X.flatten())
    Y = list(Y.flatten())
    del X[len(X) // 2]
    del Y[len(Y) // 2]

    for x_dx, y_dy in zip(X, Y):
        if (x_dx + x) < 0.0 or (y_dy + y) < 0.0:
            continue
        else:
            yield np.array([x_dx + x, y_dy + y])

怀疑主循环代码存在问题，但无法定位具体位置，已确认变量赋值正确，猜测可能是字典推导部分出错，主循环代码如下：

cost_function = lambda x, y: 2 * np.sin(y) + 2 * np.cos(x)
delta = np.array([1.0, 1.0])
pos = np.array([1.0, 1.0])
cost = cost_function(*pos)

while abs(delta[0]) > 0.01 or abs(delta[1]) > 0.01:
    costs_dict = {cost_function(*coord): coord for coord in generate_surrounding(pos, delta)}
    new_cost = min(costs_dict.keys())
    new_pos = costs_dict[new_cost]
    d_cost = new_cost - cost
    d_pos_x, d_pos_y = new_pos[0] - pos[0], new_pos[1] - pos[1]
    delta[0] = abs(d_cost / d_pos_x) if not d_pos_x == 0 else delta[0]
    delta[1] = abs(d_cost / d_pos_y) if not d_pos_y == 0 else delta[1]
    pos = new_pos
    cost = new_cost

最后是用于调试和可视化代价函数的代码，当前使用的是自定义简单代价函数，实际会更复杂：

import numpy as np
import matplotlib.pyplot as plt

x = np.arange(1, 30, 0.25)
y = x.reshape(-1, 1)
h = 2*np.sin(y)+2*np.cos(x)

cs = plt.contourf(h)
cs.changed()
plt.colorbar()

问题根源分析 #

1. 字典键冲突丢失邻居信息
   用代价函数值作为字典键时，若不同坐标的代价相等，后出现的坐标会覆盖前一个，导致算法丢失潜在的更优搜索方向，甚至陷入无意义的循环。

2. 步长更新逻辑缺陷
   最小化代价时，d_cost = new_cost - cost为负值，用绝对值计算步长会丢失方向关联；当d_pos_x/d_pos_y=0时直接保留原步长，若此时该方向无更优邻居，算法会在该维度停滞，仅在另一维度来回跳动。

3. 局部最优无处理逻辑
   当所有邻居代价都不优于当前点时，算法未触发步长缩小的精细搜索，而是继续用原步长重复无效搜索，导致停滞。

修复方案 #

1. 解决字典键冲突 #

将字典键改为坐标，值为代价，确保所有邻居信息都被保留：

costs_dict = {tuple(coord): cost_function(*coord) for coord in generate_surrounding(pos, delta)}
new_pos = min(costs_dict, key=costs_dict.get)
new_pos = np.array(new_pos)
new_cost = costs_dict[tuple(new_pos)]

2. 修正步长更新与局部最优处理 #

当无更优邻居时主动缩小步长；步长更新基于近似导数绝对值，同时处理无位置变化的情况：

# 判断是否找到更优点
if new_cost >= cost:
    # 局部最优，缩小步长
    delta *= 0.5
    continue

# 更新步长
if d_pos_x != 0:
    grad_x = d_cost / d_pos_x
    delta[0] = abs(grad_x)
else:
    delta[0] *= 0.5

if d_pos_y != 0:
    grad_y = d_cost / d_pos_y
    delta[1] = abs(grad_y)
else:
    delta[1] *= 0.5

完整修正后主循环代码 #

cost_function = lambda x, y: 2 * np.sin(y) + 2 * np.cos(x)
delta = np.array([1.0, 1.0])
pos = np.array([1.0, 1.0])
cost = cost_function(*pos)

while abs(delta[0]) > 0.01 or abs(delta[1]) > 0.01:
    costs_dict = {tuple(coord): cost_function(*coord) for coord in generate_surrounding(pos, delta)}
    if not costs_dict:
        break  # 无合法邻居，终止循环
    
    new_pos = min(costs_dict, key=costs_dict.get)
    new_pos = np.array(new_pos)
    new_cost = costs_dict[tuple(new_pos)]
    
    if new_cost >= cost:
        delta *= 0.5
        continue
    
    d_cost = new_cost - cost
    d_pos_x, d_pos_y = new_pos[0] - pos[0], new_pos[1] - pos[1]
    
    if d_pos_x != 0:
        grad_x = d_cost / d_pos_x
        delta[0] = abs(grad_x)
    else:
        delta[0] *= 0.5
    
    if d_pos_y != 0:
        grad_y = d_cost / d_pos_y
        delta[1] = abs(grad_y)
    else:
        delta[1] *= 0.5
    
    pos = new_pos
    cost = new_cost
    print(f"当前位置: {pos}, 代价: {cost}, 步长: {delta}")

可视化代码修正 #

原代码未正确映射x/y坐标，修正后可准确显示代价函数分布：

import numpy as np
import matplotlib.pyplot as plt

x = np.arange(0, 10, 0.25)
y = np.arange(0, 10, 0.25)
X, Y = np.meshgrid(x, y)
h = 2*np.sin(Y) + 2*np.cos(X)

cs = plt.contourf(X, Y, h, cmap='viridis')
plt.colorbar(cs)
plt.xlabel('X')
plt.ylabel('Y')
plt.title('代价函数等高图')
plt.show()

内容的提问来源于stack exchange，提问作者Lyndon Alcock