TSP优化算法对比实验系统

这是一个完整的旅行商问题(TSP)优化算法对比实验系统，实现了多种元启发式算法并提供详细的性能分析。

项目概述

本项目实现了四种经典的元启发式优化算法：

• 遗传算法 (GA) - 带有精英选择和局部搜索优化
• 模拟退火 (SA) - 多种邻域操作和自适应冷却策略
• 禁忌搜索 (TS) - 强化与分散策略相结合
• 蚁群算法 (ACO) - 精英信息素更新和局部搜索

支持三个标准TSPLIB数据集：

• berlin52 (52个城市，最优解：7542)
• kroA100 (100个城市，最优解：21282)
• kroA200 (200个城市，最优解：29368)

编译说明

Windows系统

1. 确保安装了MinGW-w64或类似的C++编译器
2. 将编译器路径添加到系统PATH环境变量
3. 在项目根目录执行：

build.bat

Linux/Mac系统

1. 确保安装了g++编译器
2. 在项目根目录执行：

make          # 编译优化版本
make debug    # 编译调试版本
make clean    # 清理编译文件
make help     # 显示帮助信息

使用说明

基本用法

将data目录下的.tsp文件放在项目根目录，运行以下命令：

# 运行所有算法在所有数据集上（每个算法运行20次）
./bin/tsp_solver

# 在Windows上
bin\tsp_solver.exe

命令行参数

选项：
  -h, --help           显示帮助信息
  -d, --data <path>    指定数据文件目录（默认：当前目录）
  -o, --output <path>  指定结果输出目录（默认：./results/）
  -r, --runs <count>   每个算法的运行次数（默认：20）
  -a, --algorithm <alg> 只运行指定算法（GA/SA/TS/ACO）
  -f, --file <name>    只在指定数据集上运行

使用示例

# 只运行遗传算法在berlin52数据集上
./bin/tsp_solver -a GA -f berlin52.tsp

# 每个算法运行10次
./bin/tsp_solver -r 10

# 指定输出目录
./bin/tsp_solver -o my_results

# 只运行模拟退火算法
./bin/tsp_solver -a SA

# 显示帮助
./bin/tsp_solver -h

算法实现特色

遗传算法 (GA)

• 编码方式：整数序列编码
• 选择策略：锦标赛选择
• 交叉操作：顺序交叉(OX)
• 变异操作：交换变异
• 改进策略：精英保留 + 2-opt局部搜索

模拟退火 (SA)

• 邻域操作：2-交换、插入、逆转三种操作随机选择
• 冷却策略：指数冷却
• 接受准则：Metropolis准则
• 改进策略：自适应邻域选择 + 局部搜索

禁忌搜索 (TS)

• 邻域结构：2-opt移动
• 禁忌机制：固定长度禁忌表
• 渴望准则：接受被禁忌但优于历史最优的解
• 改进策略：强化搜索 + 分散重启

蚁群算法 (ACO)

• 构造策略：轮盘赌选择
• 信息素更新：全局更新 + 精英蚂蚁强化
• 启发式信息：距离倒数
• 改进策略：2-opt局部搜索

实验结果

系统会生成以下输出文件：

1. detailed_results.csv - 所有实验的详细结果
2. summary_statistics.csv - 统计汇总表
3. {dataset}_{algorithm}.csv - 按数据集和算法分组的结果

结果包含指标

• 平均值：20次实验的平均路径长度
• 最优值：20次实验中的最好结果
• 最差值：20次实验中的最差结果
• 标准差：结果稳定性指标
• 误差率：相对于已知最优解的误差百分比
• 运行时间：算法执行时间

输出结果

性能调优

算法参数

所有算法参数都在experiment.cpp中的相应创建函数中定义，可以根据需要调整：

// 遗传算法参数
params.populationSize = 100;
params.maxGenerations = 500;
params.crossoverRate = 0.8;
params.mutationRate = 0.02;

// 模拟退火参数
params.initialTemperature = 1000.0;
params.coolingRate = 0.995;
params.maxIterations = 50000;

编译优化

使用-O3优化级别和-march=native针对本机CPU优化：

make release  # 使用优化编译
make debug    # 使用调试编译

扩展功能

添加新算法

1. 在src/目录创建新的头文件和实现文件
2. 在experiment.h中添加新的算法类型
3. 在ExperimentManager中添加创建函数
4. 更新Makefile和build.bat

添加新数据集

只需将符合TSPLIB格式的.tsp文件放入项目目录，系统会自动识别：

./bin/tsp_solver -f your_dataset.tsp

自定义实验参数

修改experiment.cpp中的参数设置函数，或扩展命令行参数支持。

技术特点

• 面向对象设计：清晰的类层次结构，易于扩展
• 高效实现：预计算距离矩阵，避免重复计算
• 内存管理：使用智能指针和RAII原则
• 错误处理：完善的异常处理和输入验证
• 跨平台：支持Windows、Linux、Mac系统
• 标准兼容：使用C++17标准，兼容性好

依赖要求

• C++17兼容编译器（g++ 7.0+, clang++ 5.0+, MSVC 2017+）
• 标准库支持<filesystem>（如果编译器不支持，会自动退回到兼容模式）