2. 局部搜索算法：爬山法原理、优缺点分析、适用场景

好，咱们正式开始聊局部优化。说到局部搜索，爬山法绝对是最经典、最直观的入门算法。我当年刚接触优化问题时，第一个上手的就是它。说白了，它的思路特别简单——就像你在浓雾里爬山，只能看到脚下几步的路，那就哪边高往哪边走。

2.1 爬山法的核心原理

爬山法是一种贪心的局部搜索算法。它从一个初始解出发，每一步都尝试在当前解的“邻居”中找一个更好的，然后移动过去。重复这个过程，直到找不到更好的邻居为止。

嗯，这里有个关键点——“邻居”怎么定义？这取决于你的问题。比如在连续优化里，邻居可能是当前点周围某个小半径内的点；在离散问题里，比如旅行商问题，邻居可能是交换两个城市的顺序。

function HillClimbing(problem):
    current = initial_solution(problem)
    while True:
        neighbors = get_neighbors(current)
        if not neighbors:
            break
        best_neighbor = argmax(neighbors, fitness)
        if fitness(best_neighbor) <= fitness(current):
            break
        current = best_neighbor
    return current

你看，逻辑就这么几行。但别小看它，我在实际项目中见过不少人把爬山法用得很巧妙。有一次做芯片布局优化，初始解随便给，爬山法跑几十轮就能得到一个可用的布局——虽然不一定最优，但比手工排布强太多了。

2.2 爬山法的三种常见变体

实际用的时候，爬山法有好几个“变种”。我习惯把它们分成三类：

我个人最常用的是首选爬山法。为什么？因为最陡爬山法每次都要算所有邻居，如果邻居数量很大（比如几万个），那代价太高了。随机爬山法又太“随缘”，有时候明明有近路却绕远。首选爬山法找到一个更好的就动，效率和质量比较平衡。

2.3 爬山法的优缺点分析

咱们不绕弯子，直接说优缺点。

优点

• 简单易懂：代码量少，逻辑清晰，新手也能快速上手。
• 计算效率高：每一步只评估少量邻居，内存占用也低。
• 容易实现：不需要复杂的数学推导，调参也少。

缺点

• 容易陷入局部最优：这是最大的坑。爬山法只能看到局部信息，一旦走到一个“小山坡”顶，就以为到了珠穆朗玛峰。
• 对初始解敏感：起点不同，结果可能天差地别。我曾经在一个项目里试了10个不同的初始点，结果收敛到了5个不同的局部最优解。
• 无法处理“高原”或“山脊”：如果邻居都一样好，算法会卡住；如果最优解在一条狭窄的山脊上，爬山法很容易错过。

2.4 爬山法的适用场景

那什么时候该用爬山法？我总结了几个典型场景：

• 问题规模大，但解的质量要求不高：比如快速原型验证，先跑个爬山法看看大概什么水平。
• 目标函数是单峰的：如果确定只有一个最优解，爬山法就是最优选择。
• 计算资源有限：嵌入式设备、实时系统里，爬山法轻量级的优势就体现出来了。
• 作为更复杂算法的“局部优化器”：比如遗传算法里，每个个体最后用爬山法微调一下，效果往往更好。

2.5 爬山法的核心逻辑图

下面这张图展示了爬山法的完整流程，从初始解到最终收敛：

2.6 一个简单的代码示例

光说不练假把式。咱们用 Python 实现一个最简单的爬山法，用来优化一个一维函数 f(x) = -x^2 + 10x，这个函数在 x=5 处有最大值。

import random
import math

def fitness(x):
    return -x**2 + 10*x

def hill_climbing(initial_x, step_size=0.1, max_iter=1000):
    current_x = initial_x
    current_val = fitness(current_x)
    
    for i in range(max_iter):
        # 生成两个邻居：向左和向右
        left_x = current_x - step_size
        right_x = current_x + step_size
        
        left_val = fitness(left_x)
        right_val = fitness(right_x)
        
        # 选更好的邻居
        if left_val > current_val and left_val >= right_val:
            current_x = left_x
            current_val = left_val
        elif right_val > current_val:
            current_x = right_x
            current_val = right_val
        else:
            # 没有更好的邻居，停止
            break
    
    return current_x, current_val

# 测试
initial = random.uniform(0, 10)
best_x, best_val = hill_climbing(initial)
print(f"初始解: {initial:.2f}")
print(f"最优解: x={best_x:.2f}, f(x)={best_val:.2f}")

你试试看，不管初始解是多少，只要步长合适，最终都会收敛到 x=5 附近。但如果你把函数改成 f(x) = -x^4 + 10x^3 - 20x^2 + 15x，这个函数有两个局部最优，爬山法就可能掉进坑里了。

2.7 小结

爬山法就像一把小刀——轻便、锋利，但只适合干精细的活。用它之前，先想想你的问题是不是“单峰”的，或者你能不能接受一个“还不错”的解。如果答案是肯定的，那爬山法就是你的好帮手。