迭代局部搜索算法原理与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(projection='3d') axis.plot_surface(x, y, results, cmap='jet') 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, 1e+10 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_processes=4): 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, key=lambda 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(maxsize=1024) 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 混合离散-连续问题
通过适当修改扰动策略
在实际应用中，我发现迭代局部搜索算法特别适合那些具有多个局部最优解的问题，其中好的解往往聚集在搜索空间的特定区域。通过合理设置扰动尺度，可以在探索和开发之间取得良好平衡。一个实用的技巧是先用较大的扰动尺度进行全局探索，随着搜索进行逐渐减小扰动尺度以提高局部搜索精度。