学习TSP项目教程

1. 项目介绍

learning-tsp 是一个开源项目，旨在通过神经网络解决旅行商问题（TSP）。该项目基于论文《Learning TSP Requires Rethinking Generalization》，该论文在2021年的国际约束编程会议（CP 2021）上被接受。项目的主要目标是探索和改进神经网络在解决大规模TSP问题时的泛化能力。

项目的主要特点包括：

• 使用图神经网络（GNN）进行图嵌入。
• 提供多种解码策略，包括非自回归解码和自回归解码。
• 支持监督学习和强化学习两种训练方式。
• 开源框架和数据集，鼓励社区进一步研究和开发。

2. 项目快速启动

环境准备

首先，确保你已经安装了以下软件和库：

• Ubuntu 16.04
• Python 3.6.7
• PyTorch 1.2.0
• CUDA 10.0

推荐使用Anaconda进行环境配置：

# 克隆项目仓库
git clone https://github.com/chaitjo/learning-tsp.git
cd learning-tsp

# 创建并激活新的conda环境
conda create -n tsp python=3.6.7
source activate tsp

# 安装所有依赖项和Jupyter Lab
conda install pytorch=1.2.0 cudatoolkit=10.0 -c pytorch
conda install numpy scipy cython tqdm scikit-learn matplotlib seaborn tensorboard pandas
conda install jupyterlab -c conda-forge
pip install tensorboard_logger

# 下载数据集并解压到/data/tsp目录
pip install gdown
gdown https://drive.google.com/uc?id=152mpCze-v4d0m9kdsCeVkLdHFkjeDeF5
tar -xvzf tsp-data.tar.gz -C /data/tsp/

训练模型

使用以下命令进行模型训练：

CUDA_VISIBLE_DEVICES=<available-gpu-ids> python run.py --problem tsp --model attention --encoder gnn --baseline rollout --min_size 20 --max_size 50 --batch_size 128 --train_dataset data/tsp/tsp20_train_concorde.txt --val_datasets data/tsp/tsp20_val_concorde.txt data/tsp/tsp50_val_concorde.txt --lr_model 1e-4 --run_name <custom_run_name>

模型评估

使用以下命令进行模型评估：

CUDA_VISIBLE_DEVICES=<available-gpu-ids> python eval.py data/tsp/tsp10-200_concorde.txt --model outputs/<custom_run_name>_<datetime>/ --decode_strategy greedy --eval_batch_size 128 --width 1

3. 应用案例和最佳实践

应用案例

learning-tsp 项目可以应用于各种需要解决旅行商问题的场景，例如：

• 物流配送路径优化
• 制造业中的生产调度
• 计算机网络中的路由优化

最佳实践

• 数据集选择：根据实际问题选择合适的数据集进行训练和评估。
• 模型选择：根据问题的复杂度和规模选择合适的模型架构和解码策略。
• 超参数调优：通过实验调整学习率、批量大小等超参数，以获得最佳性能。

4. 典型生态项目

• Concorde TSP Solver：一个经典的TSP求解器，用于生成高质量的TSP数据集。
• Attention, Learn to Solve Routing Problems：另一个基于注意力机制的TSP求解项目，提供了不同的模型架构和训练方法。
• Graph Neural Networks for Combinatorial Optimization：一个专注于使用图神经网络解决组合优化问题的项目，提供了多种GNN架构和应用案例。

通过结合这些生态项目，可以进一步扩展和优化 learning-tsp 的功能和性能。