《Biomimetics》：Evolutionary, Neural, or LLM-Driven Heuristic Generation? A Unified Ant Colony Optimization Benchmark for Nature-Inspired Routing Heuristics on the TSP and CVRP
编辑推荐：
仿生优化将生物信息处理机制转移到计算系统。蚁群优化（ACO）是一个典型例子：人工蚂蚁在功能上抽象了信息素介导的stigmergy、分散探索、通过算法蒸发实现的路径衰减以及自适应路径强化。基于这一功能生物类比，研究人员提出了一种受控的跨范式路由启发式生成评估。一
仿生优化将生物信息处理机制转移到计算系统。蚁群优化（ACO）是一个典型例子：人工蚂蚁在功能上抽象了信息素介导的stigmergy、分散探索、通过算法蒸发实现的路径衰减以及自适应路径强化。基于这一功能生物类比，研究人员提出了一种受控的跨范式路由启发式生成评估。一个标准化接口将人类设计规则、遗传编程超启发式GHPP、资源受限的DeepACO-MLP代理以及离线ReEvo风格代理嵌入到同一ACO求解器中。这些方法在保留的TSP和CVRP实例上，从解质量、报告生成或训练成本、可解释性以及匹配分布下的跨尺度行为方面进行评估。GHPP在所有测试尺度上获得最短路径；ReEvo离线代理和强人类设计规则通常构成第二梯队，而资源受限的神经代理随问题规模增大显著退化。这些结果并未建立全能力范式的内在排名。相反，它们表明方法选择取决于操作约束和证据来源：较长的本地测量离线搜索有利于GHPP，而可审计的显式规则则表征了人类和ReEvo离线代理。通过固定蚁群启发式执行机制并改变启发式信息源，该基准阐明了进化、神经和LLM风格设计策略如何与共同仿生基质相互作用。
**论文解读**
**研究背景与问题**
组合优化问题在运筹学和人工智能领域具有重要意义，旅行商问题（TSP）和容量受限车辆路径问题（CVRP）是物流、路径规划、生产调度等领域的基础模型。精确求解器（如Concorde）和强启发式方法（如HGS-CVRP）在小规模实例上表现良好，但随着问题规模增大，精确求解和手动调参难以同时满足解质量、计算时间和可解释性。这促使自动生成启发式方法的研究。
仿生学通过将生物系统的功能、机制和组织原则转移到技术设计，在计算优化中，信息处理策略（而非物理形态）被转移。蚁群优化（ACO）是典型例子：人工蚂蚁通过模拟信息素介导的stigmergy、分散探索、路径衰减和自适应路径强化，实现群体搜索。然而，不同启发式生成范式（人类设计、进化超启发式、神经学习、大语言模型（LLM）驱动的进化）通常在其自身惯例下评估，使用不同实例分布、求解器参数和指标，缺乏统一比较。因此，关键问题在于：在受控变量下，哪种启发式生成范式在解质量、成本和可解释性之间取得最佳权衡？三大障碍阻碍了该问题的回答：输出异质性（表达式树、网络权重、代码函数无法直接比较）；公平性陷阱（各研究使用不同实例尺度和超参数）；缺失维度（多数研究仅报告平均路径长度，未量化搜索成本、可解释性和跨尺度稳定性）。
**研究内容与结论**
为解决上述问题，研究人员设计了一个标准化启发式适配器，将异构输出映射到同一ACO求解器，并在相同实例、相同求解器和四维指标系统上比较人类设计启发式、GHPP（遗传编程）、DeepACO-MLP代理（资源受限）和ReEvo离线代理（LLM风格）。主要结论：GHPP在所有测试尺度上获得最短路径；ReEvo离线代理和强人类规则构成第二梯队；资源受限的DeepACO-MLP代理随问题规模增大显著退化。这些结果不表明全能力范式的内在排名，而是说明方法选择取决于操作约束和证据来源：较长的本地测量离线搜索有利于GHPP，可审计的显式规则表征人类和ReEvo离线代理。该基准通过固定蚁群执行机制并改变启发式信息源，阐明了进化、神经和LLM风格设计策略如何与共同仿生基质交互。论文发表在《Biomimetics》。
**主要技术方法**
研究人员采用统一ACO评估框架，将所有启发式生成方法连接到同一ACO求解器，状态转移概率为信息素与启发式信息的加权乘积。比较方法包括：人类设计启发式（逆距离、最近邻加权、储蓄启发式）；GHPP（使用锦标赛选择、交叉和变异生成表达式规则）；资源受限的DeepACO-MLP代理（隐藏维度64、20个训练实例、50个epoch）；ReEvo离线代理（筛选预先生成的候选规则，不重新运行LLM进化）。所有方法在随机生成的TSP和CVRP实例上测试，训练集和测试集由不同种子生成，测试实例规模为TSP 50/100/200/500节点，CVRP 20/50/100/200节点。评估指标包括解质量（平均路径长度）、实例级离散度、近似比较显著性（Welch t检验和Holm校正）、单次生成或训练成本、匹配分布下跨尺度变化。
**研究结果**
**5.1 TSP性能比较**：GHPP在所有四个尺度上获得最短路径。ReEvo离线代理和人类NNWeighted构成紧密的第二梯队，其四尺度平均差距相对于GHPP分别为12.7%和12.8%。资源受限的DeepACO-MLP代理随尺度增大显著恶化。相对于LKH近似最优解，GHPP的差距为+3.1%（TSP50）和+7.8%（TSP100），ReEvo离线代理为+7.9%和+20.4%，人类NNWeighted为+8.1%和+20.6%，DeepACO-MLP代理为+251.9%和+458.2%。
**5.2 CVRP性能比较**：GHPP在所有四个尺度上获得最短路径。人类DepotProx和ReEvo离线代理构成统计上相似的第二梯队，其四尺度平均差距相对于GHPP分别为31.3%和31.5%。两者均优于资源受限的DeepACO-MLP代理。
**5.3 统计显著性检验**：八个预设的GHPP对第二梯队比较均达到原始p<0.001，且经Holm校正后仍显著（pHolm<0.001）。Cohen's d值表明所有比较均为大效应。
**5.4 诊断敏感性和来源审计**：共享ACO主干参数（信息素权重α、启发式权重β、蚂蚁数量n_ants）的敏感性分析表明，α=1处于稳定区域，30只蚂蚁为质量-时间折中。GHPP和ReEvo风格规则具有不同成本来源：GHPP本地评估种群50代30代，耗时585.21分钟；ReEvo离线代理仅筛选缓存候选规则，耗时2.18分钟（TSP）和3.68分钟（CVRP）。小训练池（5、10、20实例）的探索性敏感性显示，测试均值在有限范围内适度变化，但未建立饱和点。
**5.5 计算成本与可解释性分析**：GHPP和DeepACO-MLP代理训练时间在本地CPU测量；ReEvo离线代理的外部生成时间（5分钟，0.20美元）来自源研究。可解释性方面，ReEvo离线代理候选和人类基线提供可读的Python或代数规则，GHPP产生显式表达式，DeepACO-MLP代理存储于神经网络权重，可审计性较低。
**5.6 匹配分布下的跨尺度行为**：DeepACO-MLP代理在两种任务中增长最陡峭，GHPP保持最低绝对路径长度，显式规则第二梯队接近。描述性跨尺度变化：ReEvo离线代理四尺度TSP平均差距12.7%，人类NNWeighted 12.8%，人类InvDist 21.4%，人类Savings 106.2%，DeepACO-MLP代理591.5%，以GHPP为0%。
**讨论与结论**
**讨论**：GHPP在TSP和CVRP上表现最佳，但代价是585.21分钟本地搜索，适用于离线搜索而非快速重新设计。ReEvo离线代理产生显式可检查规则，与强人类规则接近，但本地实验未执行LLM驱动的进化。DeepACO-MLP代理结果不能推广到原始GNN架构，它反映的是容量受限的MLP、有限训练实例和简化训练实现。理论上，该基准提供了受控接口和报告协议，而非普遍范式排名。实际应用中，当优先考虑路径质量且可接受较长离线搜索时，选择GHPP；人类设计规则和ReEvo离线代理是透明的第二梯队基线。未来工作需扩展适配器至更丰富路由约束、测试真实分布偏移、重现完整GNN和LLM生成流程，并跨独立种子重复随机方法生成。
**结论翻译**：本文提出一个受控的跨范式接口，用于评估同一仿生ACO执行层内的异构启发式表示。修订版本明确了范围：GHPP和人类规则是本地执行的基线，神经结果是资源受限的DeepACO-MLP代理，LLM风格结果是ReEvo离线代理（不重新运行LLM进化）。在存档的保留实例上，GHPP在所有测试的TSP和CVRP尺度上获得最短平均路径。ReEvo离线代理和强人类规则构成第二梯队，相对于GHPP的校正四尺度平均差距为12.7%（TSP）和约31%（CVRP）。所有八个预设的GHPP对第二梯队比较在Holm校正后仍显著（条件于固定启发式实现）。资源受限的DeepACO-MLP代理随尺度显著退化，但这不能推广到原始GNN架构。可辩护的结论并非一个启发式生成范式普遍占优，而是公平的仿生基准必须保持蚁群启发的基质固定、精确标注代理实现、分离本地测量阶段与外部估计，并报告实际观察到的不确定性。未来工作将扩展可行性适配器至更丰富的路由约束、测试真实分布偏移、重现完整GNN和LLM生成流程，并跨独立种子重复随机方法生成。
