Python实现爬山算法：局部最优与随机重启策略详解

爬山算法的核心逻辑与局限

爬山算法（Hill Climbing）模拟了登山者寻找最高点的过程。在数学优化中，它通过在当前解的邻域内搜索，若发现更优解则移动至该点，否则停止。其最大的局限性在于收敛到局部最优。一旦算法到达一个比所有邻域点都“高”（即目标函数值更大）的位置，即使该位置并非全局最高点，算法也会停止搜索。

Python实现步骤详解

1. 定义目标函数与搜索空间

首先，我们需要定义一个待优化的目标函数以及变量的定义域。在示例中，我们使用了一个包含三角函数的复杂函数，这通常具有多个局部极值点，非常适合测试爬山算法的性能。

• 目标函数：$F(x) = \sin(x^2) + 2.0\cos(2.0x)$
• 定义域：$x \in [5, 8]$
• 搜索步长：$DELTA = 0.01$，用于控制搜索的精细程度。

2. 核心爬山逻辑

算法通过两个方向的迭代来寻找局部最大值：

1. 正向搜索：检查 $x + DELTA$ 处的函数值是否大于当前 $x$ 处的值，且未超出定义域上限。若是，则更新 $x$。
2. 反向搜索：检查 $x - DELTA$ 处的函数值是否大于当前 $x$ 处的值，且未超出定义域下限。若是，则更新 $x$。

当两个方向的移动都无法使函数值增加时，算法认为已到达局部最高点并返回该点的坐标及函数值。

3. 随机重启策略（Random Restart）

为了解决局部最优问题，代码引入了随机重启机制。具体操作如下：

• 在定义域 $[5, 8]$ 内随机生成 100 个初始点（$GENERATION = 100$）。
• 对每个初始点独立执行一次爬山算法。
• 记录所有运行结果中函数值最大的那个解作为最终结果。

这种策略通过增加搜索的多样性，显著提高了找到全局最优解的概率。

import numpy as np
import matplotlib.pyplot as plt
import math

# 搜索步长
DELTA = 0.01
# 定义域x从5到8闭区间
BOUND = [5,8]
# 随机取乱数100次
GENERATION = 100

def F(x):
  return math.sin(x*x)+2.0*math.cos(2.0*x)

def hillClimbing(x):
  # 向正方向搜索
  while F(x+DELTA)>F(x) and x+DELTA<=BOUND[1] and x+DELTA>=BOUND[0]:
    x = x+DELTA
  # 向负方向搜索
  while F(x-DELTA)>F(x) and x-DELTA<=BOUND[1] and x-DELTA>=BOUND[0]:
    x = x-DELTA
  return x,F(x)

def findMax():
  highest = [0,-1000]
  for i in range(GENERATION):
    # 在定义域内随机生成初始点
    x = np.random.rand()*(BOUND[1]-BOUND[0])+BOUND[0]
    currentValue = hillClimbing(x)
    print('current value is :',currentValue)
    
    # 更新全局最高值
    if currentValue[1] > highest[1]:
      highest[:] = currentValue
  return highest

[x,y] = findMax()
print('highest point is x :{},y:{}'.format(x,y))

结果分析与验证

运行上述代码后，程序会打印出每次随机初始点经过爬山算法收敛后的结果。最终输出的 `highest point` 即为在100次随机重启中找到的最佳解。由于目标函数 $F(x)$ 在区间 $[5, 8]$ 内存在多个局部峰值，随机重启策略能够有效避免算法过早锁定在一个较低的局部峰值上。

注意事项

• 步长选择：步长 $DELTA$ 过小会导致收敛速度慢，过大则可能跳过最优解附近区域。可根据具体函数特性调整。
• 随机种子：若需复现结果，可设置 `np.random.seed()`。
• 全局最优性：随机重启不能保证100%找到全局最优解，但能大幅提高概率。对于更复杂的优化问题，可考虑模拟退火或遗传算法。

以上就是Python实现爬山算法的思路详解，更多关于Python算法优化的资料请关注本站其它相关文章！