本文介绍如何利用 numba 加速 tsp 路径长度计算，将原始 python 循环实现从 28.5 微秒降至 0.6 微秒，大幅提升遗传算法中路径评估效率。
本文介绍如何利用 numba 加速 tsp 路径长度计算，将原始 python 循环实现从 28.5 微秒降至 0.6 微秒，大幅提升遗传算法中路径评估效率。
在旅行商问题（TSP）的遗传算法实现中，频繁评估候选路径的总长度是性能瓶颈。原始方法使用 itertools.pairwise 和 Python 级循环累加邻接矩阵元素，虽逻辑清晰但开销显著——尤其当种群规模大、迭代次数高时，路径长度计算极易成为拖慢整体收敛速度的关键环节。
核心优化思路：避免 Python 解释器开销与对象动态查找，转为编译型静态执行。
Numba 的 @njit 装饰器可将纯数值计算函数即时编译为机器码，跳过 CPython 的字节码解释过程，并支持高效的内存连续访问（如 NumPy 数组索引）。以下为推荐实现：
import numba as nb
import numpy as np
# 预编译多签名版本，兼容 int32/int64 邻接矩阵和 int64 路径
@nb.njit(['float64[:,:](int32[:,:], int64[:])',
'float64[:,:](int64[:,:], int64[:])',
'float64(int32[:,:], int64[:])',
'float64(int64[:,:], int64[:])'])
def get_path_len(adj_mat, path):
n = path.size
if n == 0:
return 0.0
total = 0.0
# 累加 path[0]→path[1], path[1]→path[2], ..., path[n-2]→path[n-1]
for i in range(n - 1):
total += adj_mat[path[i], path[i + 1]]
# 闭合回路：path[n-1] → path[0]
total += adj_mat[path[n - 1], path[0]]
return total✅ 关键优势说明：
-
零拷贝索引：
path[i]和adj_mat[a,b]直接映射到内存地址，无 Python 对象封装开销； - 循环展开与向量化提示：Numba 自动应用底层优化（如 SIMD 指令），尤其在长路径（如 100+ 城市）下收益明显；
- 类型特化：通过签名声明明确数组 dtype，避免运行时类型推断延迟；
- 首次调用后即热启动：后续调用完全以原生速度执行。
⚠️ 使用注意事项：
- 确保
path中所有索引均在[0, adj_mat.shape[0])范围内，Numba 不做越界检查（调试阶段可临时启用@nb.njit(boundscheck=True)）； - 若邻接矩阵含浮点权值（如
float32/float64），需在签名中显式添加对应类型（如'float64(float64[:,:], int64[:])'）； - 避免在
@njit函数中调用非 Numba 兼容函数（如print,len()以外的内置函数、NumPy 高级操作等）。
经实测（i5-9600KF，NumPy 2.1.3），对 100×100 随机整数邻接矩阵与全排列路径：
- 原始
pairwise方案：≈28.5 µs - Numba 加速版：≈0.6 µs（提速约 47×）
该优化可无缝集成至遗传算法的适应度评估模块，显著提升每代进化效率。建议在初始化阶段完成函数编译（如首次调用 get_path_len(mat, path)），后续所有路径评估均享受毫秒级响应。
