GAT-PPO 增强的遗传算法求解TSP问题

本项目基于EAX（Edge Assembly Crossover）遗传算法，通过集成图注意力网络和近端策略优化（GAT-PPO）强化学习方法来增强交叉操作的决策能力，提高TSP问题的求解效率。

项目结构

• EAX/: EAX算法的核心实现
• GAT_PPO/: GAT-PPO模型实现和训练相关代码
  • model_interface.h/cpp: 模型接口，用于与Python模型交互
  • replay_buffer.h/cpp: 经验回放缓冲区，用于存储训练数据
  • trainer.h/cpp: 训练器，用于调用Python训练脚本
  • graph_data.h/cpp: 图数据结构，用于表示TSP实例
  • tensor_converter.h/cpp: 张量转换工具，用于C++与Python数据交换
  • train.py: Python训练脚本
  • models/: 存储训练好的模型文件

编译

mkdir build
cd build
cmake ..
make

使用方法

基本用法

./GA-TSP <max_trials> <dst_file> <pop_size> <num_kids> <tsp_file> [init_pop_file]

参数说明：

• max_trials: 最大尝试次数
• dst_file: 结果输出文件
• pop_size: 种群大小
• num_kids: 子代数量
• tsp_file: TSP问题文件
• init_pop_file: 初始种群文件（可选）

使用GAT-PPO增强版

./GA-TSP <max_trials> <dst_file> <pop_size> <num_kids> <tsp_file> [init_pop_file] --gat-ppo [--model-dir <dir>] [--python <path>] [--script <path>]

附加参数：

• --gat-ppo: 启用GAT-PPO模型
• --model-dir <dir>: 指定模型目录，默认为'GAT_PPO/models'
• --python <path>: 指定Python解释器路径，默认为'python'
• --script <path>: 指定训练脚本路径，默认为'GAT_PPO/train.py'

依赖项

C++依赖

• C++17或更高版本
• CMake 3.10或更高版本
• pybind11（用于C++与Python交互）

Python依赖

• Python 3.7或更高版本
• PyTorch 1.8或更高版本
• PyTorch Geometric
• NumPy
• Matplotlib（用于可视化，可选）

训练GAT-PPO模型

系统会自动在运行过程中收集经验数据并定期训练模型。您也可以手动触发训练：

python GAT_PPO/train.py <model_dir> <data_file> <batch_size> <ppo_epochs>

工作原理

1. 数据收集：在EAX算法执行过程中，系统会收集AB循环选择的经验数据
2. 模型训练：每生成一定数量的子代后，系统会自动触发模型训练
3. 模型应用：训练后的模型会用于指导AB循环的选择，提高算法效率

GAT-PPO方法说明

该方法结合了图注意力网络（GAT）和近端策略优化（PPO）：

• 图注意力网络：用于处理TSP问题的图结构，捕获城市之间的关系
• 近端策略优化：一种稳定的强化学习算法，用于优化AB循环选择策略

许可证

本项目使用MIT许可证 - 详见LICENSE文件