2. 爬山算法：基本原理、算法流程、优缺点分析、代码实现与可视化

各位同学，咱们今天聊聊爬山算法。这名字听着挺休闲的，像是周末去郊游。但说白了，它是最直观、最容易理解的局部搜索算法。我刚开始接触全局优化时，第一个上手的就是它。为什么？因为它简单到让你觉得“就这？”。但别小看它，很多复杂算法的基础思想，都能在它身上找到影子。

2.1 基本原理：往高处走，别回头

想象一下，你被蒙上眼睛，扔在一片连绵起伏的山脉里。你的任务是找到最高峰。你会怎么做？

正常人都会伸脚探探周围的地势。哪边高，就往哪边迈一步。然后重复这个过程，直到发现四周都是下坡路，那你就站在了山顶上。

爬山算法就是这个逻辑。它只关心当前点的“邻居”里，有没有比它更好的解。有，就跳过去；没有，就停下来。它从不考虑全局，也不做长远规划。说白了，就是“贪心”的局部搜索。

这里有个关键概念——邻域。对于连续函数，邻域就是当前点周围的一小片区域；对于离散问题，比如旅行商问题，邻域就是交换两个城市的顺序。我见过不少新手，算法跑不出好结果，最后发现是邻域定义得太小或太大。太小容易陷入局部最优，太大又变成了随机搜索。

2.2 算法流程：三步走

爬山算法的流程非常简洁。我习惯把它总结成三步：

1. 初始化：随机生成一个初始解，或者根据经验指定一个。
2. 迭代搜索：在当前解的邻域内，寻找一个更优的解。找到了就替换当前解，然后重复这一步。
3. 终止判断：如果邻域内没有更优解，或者达到了最大迭代次数，就停止。

嗯，这里要注意一个细节。第二步里“寻找更优解”有两种常见策略：

策略	做法	特点
最速上升	遍历整个邻域，找到最好的那个	收敛快，但计算量大
随机上升	随机找一个邻居，只要比当前好就接受	计算量小，但可能走弯路

我个人习惯在早期用随机上升，因为快；后期用最速上升，因为稳。你可以根据问题规模灵活切换。

下面这张图展示了爬山算法的完整流程：

2.3 优缺点分析：成也局部，败也局部

爬山算法的优点非常突出：

• 简单直观：代码量少，逻辑清晰，适合入门。
• 收敛快：对于单峰函数，它很快就能找到最优解。
• 内存占用小：只需要保存当前解，不需要记录历史信息。

但它的缺点同样致命：

• 容易陷入局部最优：这是它最大的问题。一旦爬到一个小山包，四周都是下坡，它就以为到了珠穆朗玛峰。
• 对初始解敏感：起点不同，结果可能天差地别。我曾经在一个多峰函数上测试，跑了10次，每次结果都不一样。
• 无法处理“高原”：如果邻域内所有解都一样好，算法就会陷入随机徘徊。

2.4 代码实现与可视化

光说不练假把式。咱们用Python实现一个简单的爬山算法，并可视化它的搜索过程。

这里我选了一个经典的一维测试函数：f(x) = x * sin(10 * pi * x) + 1。它在区间[-1, 2]上有多个局部最优。

import numpy as np
import matplotlib.pyplot as plt

def objective_function(x):
    """目标函数：多峰函数"""
    return x * np.sin(10 * np.pi * x) + 1

def hill_climbing(start_x, step_size=0.01, max_iter=1000):
    """爬山算法实现"""
    current_x = start_x
    current_y = objective_function(current_x)
    history = [(current_x, current_y)]

    for i in range(max_iter):
        # 生成左右两个邻居
        left_x = current_x - step_size
        right_x = current_x + step_size

        left_y = objective_function(left_x)
        right_y = objective_function(right_x)

        # 选择更好的邻居
        if left_y > current_y and left_y >= right_y:
            current_x = left_x
            current_y = left_y
        elif right_y > current_y and right_y > left_y:
            current_x = right_x
            current_y = right_y
        else:
            # 没有更好的邻居，停止
            break

        history.append((current_x, current_y))

    return current_x, current_y, history

# 测试
start_x = 0.5
best_x, best_y, history = hill_climbing(start_x)

print(f"初始点: x={start_x:.4f}")
print(f"最优解: x={best_x:.4f}, y={best_y:.4f}")
print(f"迭代次数: {len(history)}")

# 可视化
x_vals = np.linspace(-1, 2, 1000)
y_vals = objective_function(x_vals)

plt.figure(figsize=(12, 6))
plt.plot(x_vals, y_vals, 'b-', label='目标函数', linewidth=2)
plt.scatter([h[0] for h in history], [h[1] for h in history], 
            c=range(len(history)), cmap='hot', s=50, label='搜索路径')
plt.plot([h[0] for h in history], [h[1] for h in history], 
         'r--', alpha=0.5, linewidth=1)
plt.scatter(start_x, objective_function(start_x), c='green', s=100, 
            marker='o', label='起点', zorder=5)
plt.scatter(best_x, best_y, c='red', s=150, marker='*', 
            label='终点', zorder=5)
plt.xlabel('x')
plt.ylabel('f(x)')
plt.title('爬山算法搜索过程可视化')
plt.legend()
plt.grid(True, alpha=0.3)
plt.show()

运行这段代码，你会看到算法从起点出发，一步步往高处爬。但最终停下的位置，往往不是全局最高点，而是离起点最近的那个“山头”。

你想想看，如果把这个函数想象成真实的山脉，爬山算法就像一个近视眼，只能看到脚下几米的范围。它永远不知道远处还有更高的山峰。