迭代局部搜索算法原理与Python实现

1. 迭代局部搜索算法原理与实现迭代局部搜索(Iterated Local Search, ILS)是一种随机全局优化算法它通过反复对先前找到的良好解进行修改并应用局部搜索来寻找更优解。这种算法可以看作是带有随机重启的随机爬山算法的智能版本。1.1 算法核心思想迭代局部搜索的基本直觉是随机重启可以帮助定位问题中的许多局部最优解而更好的局部最优解通常靠近其他局部最优解。因此对现有局部最优解进行适度扰动可能会找到更好甚至是最优的解决方案。算法的关键优势在于它同时考虑了两种搜索策略局部搜索爬山算法专注于在当前解的邻域内寻找改进全局扰动重启策略允许探索搜索空间的不同区域1.2 与相关算法的比较与基本的随机爬山算法相比ILS的主要区别在于随机爬山容易陷入局部最优随机重启爬山从完全随机的点重新开始搜索ILS从当前最优解的扰动版本重新开始搜索这种设计使得ILS能够更有效地在搜索空间中探索多个局部最优解增加了找到全局最优解的可能性。2. Ackley测试函数实现为了验证ILS算法的效果我们使用Ackley函数作为测试基准。这是一个典型的多峰函数具有一个全局最优和多个局部最优。2.1 Ackley函数定义Ackley函数的数学表达式为 f(x,y) -20 * exp(-0.2 * sqrt(0.5*(x²y²))) - exp(0.5*(cos(2πx)cos(2πy))) e 20在Python中实现如下def objective(v): x, y v return -20.0 * exp(-0.2 * sqrt(0.5 * (x**2 y**2))) - exp(0.5 * (cos(2 * pi * x) cos(2 * pi * y))) e 202.2 可视化Ackley函数我们可以使用matplotlib创建Ackley函数的三维可视化from numpy import arange, meshgrid from matplotlib import pyplot from mpl_toolkits.mplot3d import Axes3D # 定义输入范围 r_min, r_max -5.0, 5.0 xaxis arange(r_min, r_max, 0.1) yaxis arange(r_min, r_max, 0.1) # 创建网格 x, y meshgrid(xaxis, yaxis) results objective([x, y]) # 绘制3D图 figure pyplot.figure() axis figure.gca(projection3d) axis.plot_surface(x, y, results, cmapjet) pyplot.show()这个可视化清楚地展示了函数的多个局部极小值验证了它作为优化算法测试基准的适用性。3. 基础爬山算法实现在实现ILS之前我们需要先构建基础的随机爬山算法。3.1 随机爬山算法原理随机爬山算法的工作流程生成随机初始解在当前解附近生成扰动候选解如果候选解更好则接受它作为新解重复步骤2-3直到满足终止条件3.2 Python实现from numpy.random import randn, rand def in_bounds(point, bounds): 检查点是否在搜索范围内 for d in range(len(bounds)): if point[d] bounds[d, 0] or point[d] bounds[d, 1]: return False return True def hillclimbing(objective, bounds, n_iterations, step_size): 随机爬山算法实现 # 生成初始解 solution None while solution is None or not in_bounds(solution, bounds): solution bounds[:, 0] rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0]) # 评估初始解 solution_eval objective(solution) # 执行爬山搜索 for i in range(n_iterations): # 生成候选解 candidate None while candidate is None or not in_bounds(candidate, bounds): candidate solution randn(len(bounds)) * step_size # 评估候选解 candidte_eval objective(candidate) # 如果更好则接受 if candidte_eval solution_eval: solution, solution_eval candidate, candidte_eval print(f迭代 {i} f({solution}) {solution_eval:.5f}) return [solution, solution_eval]3.3 算法测试我们可以这样测试爬山算法from numpy import asarray from numpy.random import seed # 设置随机种子 seed(1) # 定义搜索边界和参数 bounds asarray([[-5.0, 5.0], [-5.0, 5.0]]) n_iterations 1000 step_size 0.05 # 执行搜索 best, score hillclimbing(objective, bounds, n_iterations, step_size) print(f最终结果: f({best}) {score})测试结果通常会收敛到某个局部最优解验证了基本爬山算法的局限性。4. 随机重启爬山算法为了克服基本爬山算法的局限性我们可以实现随机重启策略。4.1 修改爬山算法首先修改爬山算法以接受初始点作为参数def hillclimbing(objective, bounds, n_iterations, step_size, start_pt): 可指定起点的爬山算法 solution start_pt solution_eval objective(solution) for i in range(n_iterations): candidate None while candidate is None or not in_bounds(candidate, bounds): candidate solution randn(len(bounds)) * step_size candidte_eval objective(candidate) if candidte_eval solution_eval: solution, solution_eval candidate, candidte_eval return [solution, solution_eval]4.2 随机重启实现def random_restarts(objective, bounds, n_iter, step_size, n_restarts): 随机重启爬山算法 best, best_eval None, 1e10 for n in range(n_restarts): # 生成随机起点 start_pt None while start_pt is None or not in_bounds(start_pt, bounds): start_pt bounds[:, 0] rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0]) # 执行爬山搜索 solution, solution_eval hillclimbing(objective, bounds, n_iter, step_size, start_pt) # 更新最佳解 if solution_eval best_eval: best, best_eval solution, solution_eval print(f重启 {n}, 当前最佳: f({best}) {best_eval:.5f}) return [best, best_eval]4.3 测试随机重启算法# 参数设置 n_restarts 30 # 执行搜索 best, score random_restarts(objective, bounds, n_iterations, step_size, n_restarts) print(f最终最佳: f({best}) {score})随机重启策略通常会找到比单次爬山更好的解但效率仍然不高。5. 迭代局部搜索完整实现现在我们可以实现完整的迭代局部搜索算法。5.1 算法设计ILS与随机重启爬山的关键区别在于不是完全随机重启而是从当前最优解的扰动版本开始使用更大的步长进行扰动全局探索使用较小步长进行局部搜索局部开发5.2 Python实现def iterated_local_search(objective, bounds, n_iter, step_size, n_restarts, perturbation_scale): 迭代局部搜索算法实现 # 生成初始随机解 best None while best is None or not in_bounds(best, bounds): best bounds[:, 0] rand(len(bounds)) * (bounds[:, 1] - bounds[:, 0]) best_eval objective(best) # 执行多次迭代 for n in range(n_restarts): # 生成扰动后的起点 start_pt None while start_pt is None or not in_bounds(start_pt, bounds): start_pt best randn(len(bounds)) * perturbation_scale # 执行局部搜索 solution, solution_eval hillclimbing(objective, bounds, n_iter, step_size, start_pt) # 更新最佳解 if solution_eval best_eval: best, best_eval solution, solution_eval print(f迭代 {n}, 当前最佳: f({best}) {best_eval:.5f}) return [best, best_eval]5.3 参数选择与测试# 参数设置 perturbation_scale 0.5 # 比局部搜索步长大10倍 # 执行ILS best, score iterated_local_search(objective, bounds, n_iterations, step_size, n_restarts, perturbation_scale) print(f最终结果: f({best}) {score})5.4 结果分析在Ackley函数上ILS通常能够比基本爬山算法找到更好的解比随机重启策略更快收敛更可靠地接近全局最优6. 算法优化与调参建议6.1 关键参数影响局部搜索步长(step_size)控制局部搜索的精细程度太小会导致收敛慢太大可能错过好的解扰动尺度(perturbation_scale)控制全局探索的范围通常设为局部步长的5-10倍迭代次数(n_iter)每次局部搜索的深度需要在计算成本和搜索质量间平衡6.2 自适应参数调整更高级的实现可以考虑# 自适应步长示例 if solution_eval best_eval: step_size max(step_size * 0.9, 0.01) # 成功时缩小步长 else: step_size min(step_size * 1.1, 0.2) # 失败时增大步长6.3 并行化实现ILS天然适合并行化可以同时运行多个局部搜索from multiprocessing import Pool def parallel_ils(objective, bounds, n_iter, step_size, n_restarts, perturbation_scale, n_processes4): with Pool(n_processes) as p: results p.starmap(ils_worker, [(objective, bounds, n_iter, step_size, perturbation_scale) for _ in range(n_restarts)]) return min(results, keylambda x: x[1])7. 实际应用中的注意事项7.1 边界处理策略除了简单的拒绝采样还可以考虑# 替代边界处理方式 def reflect_bounds(point, bounds): new_point point.copy() for d in range(len(bounds)): if new_point[d] bounds[d, 0]: new_point[d] bounds[d, 0] (bounds[d, 0] - new_point[d]) elif new_point[d] bounds[d, 1]: new_point[d] bounds[d, 1] - (new_point[d] - bounds[d, 1]) # 如果仍然越界则夹紧 new_point[d] max(bounds[d, 0], min(bounds[d, 1], new_point[d])) return new_point7.2 记忆化优化对于计算昂贵的目标函数可以添加缓存from functools import lru_cache lru_cache(maxsize1024) def cached_objective(point): return objective(np.array(point))7.3 算法变体定向扰动根据搜索历史智能调整扰动方向多尺度扰动同时尝试不同尺度的扰动混合策略结合其他全局优化方法8. 性能评估与比较8.1 测试方案设计为了系统评估算法性能我们可以固定随机种子确保可重复性多次运行统计成功率记录收敛速度和最终解质量8.2 结果分析示例典型结果可能显示基本爬山60%陷入不良局部最优随机重启找到较好解但计算成本高ILS以中等成本获得高质量解8.3 可视化比较可以绘制收敛曲线进行比较# 记录搜索历史 history [] def tracked_objective(point): val objective(point) history.append(val) return val # 运行后绘制 pyplot.plot(history) pyplot.xlabel(函数评估次数) pyplot.ylabel(目标函数值) pyplot.show()9. 扩展到更高维度虽然我们在2D Ackley函数上演示但ILS可以轻松扩展到更高维度9.1 高维实现要点调整步长与问题维度相适应可能需要增加迭代次数考虑维度间的相关性9.2 示例调整# 高维步长调整 dim len(bounds) step_size 0.1 / sqrt(dim) # 随维度缩放步长10. 其他应用场景虽然我们以Ackley函数为例但ILS适用于10.1 组合优化问题如旅行商问题(TSP)、调度问题等10.2 连续优化如神经网络超参数优化、工程设计优化10.3 混合离散-连续问题通过适当修改扰动策略在实际应用中我发现迭代局部搜索算法特别适合那些具有多个局部最优解的问题其中好的解往往聚集在搜索空间的特定区域。通过合理设置扰动尺度可以在探索和开发之间取得良好平衡。一个实用的技巧是先用较大的扰动尺度进行全局探索随着搜索进行逐渐减小扰动尺度以提高局部搜索精度。