本文档属于类型a，即报告了一项原创性研究成果。以下是针对该研究的学术报告：

动态事件如何改变旅行商问题（TSP）的适应性地形

1. 主要作者及发表信息

本研究由Hao Tong（香港岭南大学数据科学学院及英国伯明翰大学计算机学院）、Mqing Li（伯明翰大学计算机学院，IEEE高级会员）、Jialin Liu（香港岭南大学数据科学学院，IEEE高级会员）和Xin Yao（香港岭南大学及伯明翰大学计算机学院，IEEE Fellow）共同完成。研究论文已获IEEE Transactions on Evolutionary Computation录用，将于2025年正式发表（DOI: 10.1109/TEVC.2025.3538547）。

2. 学术背景

旅行商问题（Traveling Salesman Problem, TSP）是组合优化领域的经典问题，在物流规划、电路设计、DNA测序等领域均有广泛应用。现实世界中的TSP常受动态事件（如交通拥堵、路况变化、新增/取消节点）影响，形成动态TSP（Dynamic TSP, DTSP）。传统研究集中于设计动态优化算法（如蚁群算法、遗传算法），但鲜有工作系统分析动态事件如何改变TSP的适应性地形（Fitness Landscape）——即解空间的拓扑结构（如局部最优的分布、搜索空间的崎岖性）。

本研究填补了这一空白，通过适应性地形分析（Fitness Landscape Analysis, FLA），量化比较三类动态事件（节点增加、节点删除、权重变化）对TSP适应性地形的具体影响，为动态优化算法的设计提供理论依据。

3. 研究流程

3.1 实验设计

• 基准实例生成：使用PortGen工具随机生成50个10节点的TSP实例，并通过以下方式构造DTSP实例：
  
  • 节点增加：随机新增1个节点（共11节点）
    
  • 节点删除：随机移除1个节点（共9节点）
    
  • 权重变化：按公式 ( c’{ij} = c{ij} \times t{ij} ) 调整边权重，其中 ( t{ij} ) 服从正态分布 ( N(0,1) )。
    
• 搜索空间枚举：由于问题规模较小（10节点TSP的解空间为 ( 10! )），可穷举所有可行解。
  

3.2 适应性地形分析

采用2-opt邻域结构和爬山算法（Hill-Climbing）识别所有局部最优解，并分析以下两类属性：

（1）整体结构

• 密度状态（Density States）：解的适应度分布（通过偏度、峰度量化）；
  

• 崎岖性（Ruggedness）：通过自相关长度（Correlation Length）衡量，反映局部搜索的难度。

  （2）最优性属性

• 局部最优数量及分布

• 全局最优的适应度距离相关性（Fitness Distance Correlation, FDC）：衡量解质量与距全局最优解距离的关系；

• 吸引盆（Basin of Attraction, BoA）：全局最优解在解空间中的“势力范围”；

• 动态适应性：动态事件前后全局最优解的偏移距离。

3.3 统计验证

通过生成多个动态实例（每类事件10组），对比动态事件前后各指标的显著性差异。

4. 主要结果

4.1 整体结构

• 密度状态：原始TSP的解分布接近正态分布，动态事件仅轻微改变其偏度（权重变化使分布左偏）。
  
• 崎岖性：
  
  • 节点增加使地形更平滑（自相关长度↑）；
    
  • 节点删除使地形更崎岖（自相关长度↓）；
    
  • 权重变化影响不显著。
    

4.2 最优性属性

• 权重变化影响最大：
  
  • 局部最优解数量显著增加（图6），且多数远离全局最优（图7）；
    
  • FDC值降低（图9），解质量与距离的关联性减弱；
    
  • 全局最优的吸引盆缩小（图11），算法更易陷入次优解。
    
• 节点变化影响较小：局部最优数量与分布基本不变。
  
• 动态适应性：权重变化导致全局最优解的偏移距离最大，但整体偏移量仍较小（图13），表明基于原最优解的动态 adaptation 策略仍有效。
  

5. 研究结论

• 理论价值：首次系统揭示了动态事件对TSP适应性地形的影响机制，证明权重变化会显著增加问题难度（更多局部最优、更弱FDC、更小吸引盆），而节点变化的影响较温和。
  
• 应用价值：
  
  • 对权重变化类动态事件，需设计强探索能力的算法（如增加多样性机制）；
    
  • 对节点变化类事件，可优先采用动态适应策略（如基于记忆的优化），而非完全重启搜索。
    

6. 研究亮点

• 方法创新：首次将FLA应用于DTSP，提出量化动态地形变化的完整框架；
  
• 发现创新：明确权重变化是导致地形复杂化的主要因素，为算法设计提供优先级指导；
  
• 可扩展性：方法可推广至其他动态组合优化问题（如背包问题、调度问题）。
  

7. 其他价值

• 补充实验验证了结论在多动态事件叠加、部分解执行等复杂场景下的稳健性；
  
• 开源实验数据与代码（未在正文提及，但可通过DOI链接获取）。
  

该研究为动态优化领域提供了重要的理论基础，未来可延伸至高维TSP或其他邻域结构（如3-opt）的验证。