一、三者的共同身份元启发式局部搜索它们解决的是同一类问题组合优化 / 非凸连续优化即搜索空间巨大、不可微、存在大量局部最优梯度法失效的场景。共同框架伪代码骨架x 初始化() while 未满足停止条件: N 生成邻域(x) # 三种算法的分歧点从这里开始 x 选择(N, x, 历史, 温度) return x集束搜索 Beam Search禁忌搜索 Tabu Search模拟退火 Simulated Annealing核心机制保留前 k 个候选记忆 禁止回头概率接受差解记忆无只记当前层有禁忌表无马尔可夫性随机性通常无确定性贪心弱可加随机扰动强Metropolis跳出局部最优的方式靠宽度 k 保留多条路径强制走暂时变差的路以概率接受变差典型场景序列生成翻译、摘要、ASR调度、排产、TSP、图着色TSP、布局、参数调优、连续优化理论保证无不完备无但防循环有对数降温可收敛到全局最优但不实用二、集束搜索Beam Search1. 思想在树/图搜索的每一层不展开所有节点只保留得分最高的 B 个束宽其余剪掉。B1 时退化为贪心搜索时退化为广度优先搜索。2. 关键细节打分通常是路径累计得分 \sum_t \log P(y_t \mid y_{t}, x)。由于长序列得分天然更小实际要用长度归一化\text{score} \frac{\sum_{t1}^{|y|} \log p_t}{|y|^{\alpha}},\quad \alpha \in [0.5, 1]早熟问题束宽 B 再大一旦某条好路径在某层被挤出前 B就永远找不回来不可回溯。这是它与 TS/SA 最本质的区别。多样性退化多个束容易坍缩成同一条路径的微小变体 → 常用多样性惩罚n-gram 重复惩罚或随机集束搜索按概率采样而非取 top-B。3. 与后两者的关系Beam Search没有接受更差解的机制它靠的是横向保留多个选项。因此它适合有明确层次结构、可逐步构造解的问题如逐词生成不适合解没有自然层级的问题如 TSP 的交换邻域那种场合用 TS 或 SA 更合适。三、禁忌搜索Tabu Search,TS1. 思想允许接受比当前解更差的邻居但禁止在若干步内走回头路从而强制算法离开刚离开的局部最优。2. 三个核心组件(1) 邻域与移动Move例如 TSP 中交换城市 i,j 的位置一个移动 m 把 x 变成 x m(x)。(2) 禁忌表Tabu List记录最近使用过的移动或解的属性有效期称为禁忌期tenure。太短 → 循环回原处太长 → 搜索空间被过度封锁退化成随机搜索。工程上常用动态禁忌期频率记忆长期记忆记录每个移动被使用的次数。(3) 藐视准则Aspiration Criterion最常用的规则如果一个被禁的移动能产生优于历史最优的解则无视禁忌直接采用。这是 TS 的安全阀防止禁忌表挡住真正的最优解。3. intensification / diversification强化搜索回到历史优质解附近做精细搜索多样化搜索当长时间无改进时重置到一个远离已探索区域的新起点。这一思想与前面讲的小生境高度相关TS 的长期频率记忆本质上就是在做空间隔离避免种群全挤在一个峰上。4.代码下面是一个用 Python 实现的禁忌搜索算法完整例子以经典的TSP旅行商问题为例代码加了详细注释方便理解import numpy as np import random ​ # 1. 问题定义 def calc_distance(tour, dist_matrix): 计算一条路径的总距离目标函数 dist 0 for i in range(len(tour) - 1): dist dist_matrix[tour[i]][tour[i1]] dist dist_matrix[tour[-1]][tour[0]] # 回到起点 return dist ​ # 2. 邻域生成 def get_neighbors(tour): 通过交换两个城市的位置生成邻域解 neighbors [] n len(tour) for i in range(1, n - 1): for j in range(i 1, n): neighbor tour.copy() neighbor[i], neighbor[j] neighbor[j], neighbor[i] # 交换 neighbors.append(neighbor) return neighbors ​ # 3. 禁忌搜索主算法 def tabu_search(dist_matrix, max_iter100, tabu_tenure10): 禁忌搜索求解 TSP :param dist_matrix: 城市间距离矩阵 :param max_iter: 最大迭代次数 :param tabu_tenure: 禁忌期限一个移动被禁止的步数 n len(dist_matrix) ​ # 初始解随机生成一条路径 current_tour list(range(n)) random.shuffle(current_tour) best_tour current_tour.copy() best_distance calc_distance(current_tour, dist_matrix) ​ # 禁忌表记录每个交换操作 (i, j)剩余被禁忌的步数 tabu_list {} ​ for iteration in range(max_iter): neighbors get_neighbors(current_tour) best_neighbor None best_neighbor_dist float(inf) best_move None ​ # 遍历所有邻域解 for neighbor in neighbors: # 找出被交换的两个位置即移动 diff [(i, j) for i in range(n) for j in range(i1, n) if neighbor[i] ! current_tour[i] and neighbor[j] ! current_tour[j]] move tuple(sorted(diff[0])) if diff else None ​ dist calc_distance(neighbor, dist_matrix) ​ # 特赦准则如果该解优于全局最优即使被禁忌也接受 if dist best_distance: best_neighbor neighbor best_neighbor_dist dist best_move move break ​ # 检查是否在禁忌表中 if move in tabu_list and tabu_list[move] 0: continue # 被禁忌跳过 ​ # 否则选邻域中最好的非禁忌解 if dist best_neighbor_dist: best_neighbor neighbor best_neighbor_dist dist best_move move ​ # 如果没找到可接受的解所有邻域都被禁忌终止 if best_neighbor is None: print(f第 {iteration} 次迭代无可用邻域提前终止。) break ​ # 接受最佳邻域解 current_tour best_neighbor current_distance best_neighbor_dist ​ # 更新全局最优 if current_distance best_distance: best_tour current_tour.copy() best_distance current_distance ​ # 更新禁忌表将新移动加入禁忌表并让所有旧禁忌的剩余步数减1 for move in list(tabu_list.keys()): tabu_list[move] - 1 if tabu_list[move] 0: del tabu_list[move] # 过期移出禁忌表 if best_move: tabu_list[best_move] tabu_tenure ​ print(fIter {iteration1}: 当前距离 {current_distance:.2f}, f最优距离 {best_distance:.2f}, 禁忌表大小 {len(tabu_list)}) ​ return best_tour, best_distance ​ # 4. 运行示例 if __name__ __main__: np.random.seed(42) num_cities 10 ​ # 随机生成10个城市的坐标和距离矩阵 coords np.random.rand(num_cities, 2) * 100 dist_matrix np.zeros((num_cities, num_cities)) for i in range(num_cities): for j in range(num_cities): dist_matrix[i][j] np.linalg.norm(coords[i] - coords[j]) ​ print( 禁忌搜索求解 TSP ) print(f城市数量: {num_cities}) ​ best_tour, best_dist tabu_search(dist_matrix, max_iter50, tabu_tenure5) ​ print(f\n最优路径: {best_tour}) print(f最优距离: {best_dist:.2f})四、模拟退火Simulated AnnealingSA1. Metropolis 准则核心公式物理来源固体退火时原子处于能量状态 E 的概率服从Boltzmann 分布。两个状态的概率比为Metropolis 等人据此提出升温时系统可跨越能垒缓慢降温则可落入全局最低能态。SA 就是把目标函数 f 当作能量把温度 T 当作控制探索强度的旋钮。T 很高时Metropolis 接受差解的概率算法在解空间中近乎全收地自由探索不易困在局部最优T 很低时几乎只接受更优解算法收敛到局部最优附近精细搜索。因此缓慢降温温度曲线的成败决定了 SA 能否在初期够随机、后期够精准之间平稳过渡。2. 温度的取值工程做法接受概率反推法推荐随机采样估计平均劣化量设定期望初始接受率 P_0例→。指数降温。终止或连续若干轮无改进。五、把它们和前面几轮知识点接起来1. 定义域 dom(x)三种算法都会产生越界解必须做边界处理截断简单但会在边界堆积反射越界部分折回重新生成丢弃并重采SA 中最常用。2. 约束怎么处理罚函数法拉格朗日的近似实现前面推导过拉格朗日函数与 KKT 条件。但在 SA/TS 这类黑箱搜索里解方程组不现实工程上直接把约束打进目标函数这就把有约束问题骗成了无约束问题然后照常用基准测试函数那套流程跑。缺点太大导致地形崎岖、太小导致约束形同虚设通常需要自适应调整。3. 用什么验证算法对不对基准测试函数写好自己的 SA/TS 后别急着上真实数据先在标准地形上跑一遍Sphere先验正确性——应该快速收敛到 0Rosenbrock测精细微调能力——看能不能爬进香蕉谷Rastrigin / Schwefel测跳出局部最优能力——这正是 SA 的温度机制和 TS 的禁忌机制要解决的问题Easom测定位精度。4. 什么时候停机公式 A.37注意这条判据只对连续、可求导的问题有意义。对纯组合问题TSP、调度应改用连续 K 轮无改进 温度下限作为停止条件。5. 要找多个解怎么办小生境如果问题是多解问题定义 A.9单个 SA 或单条 TS 轨迹只能给出一个峰。解决方案多起点并行 SA 解之间距离去重小生境禁忌搜索禁忌表里不仅记移动还记已占领的峰区域迫使搜索开辟新峰适应度共享拥挤区域的解被降权天然留出空间给其他峰。六、选型速查你的问题特征建议解可以一步步构造序列、路径前缀Beam Search要加长度归一化 多样性惩罚组合优化、邻域清晰、需要稳定可复现的结果Tabu Search首选工程上最稳实现要简单、问题地形粗糙、愿意多次重启Simulated Annealing调好 T_0 和 \alpha既要质量又要鲁棒性混合SA 做全局探索 TS 做局部精修即模拟退火式禁忌搜索有多个等价最优解都要找任一算法 小生境机制