求解TSP问题的遗传算法

简介

目标：在 ga 库的基础上实现遗传算法（Genetic algorithms）针对旅行推销商问题设计开发一个计算最短路径的程序，产生该 TSP 问题的较好旅行路线。
语言：C++
平台：Windows + Microsoft Visual Studio 2022

染色体的编码方案染色体的编码方式采用路径表示法，对于数据集 Berlin52，染色体为 52 个整数的序列，表示推销员访问城市的顺序。
遗传算法的整体流程
1. 用 52 个整数(城市)的序列表示染色体, 定义适应度函数为路线欧式距离之和
2. 开始迭代进化, 每一代选取 2 个染色体,用交叉算子和变异算子对染色体进行操作, 并将生成的染色体加入到种群中
3. 重复 2, 并采样记录每次的最优解, 直到达到迭代次数(500000)
评估操作使用旅行路线上城市两两之间的欧氏距离取整之和评估染色体质量。
交叉操作使用两点交叉策略，从父代染色体中随机选择两个交叉点, 交叉点之间的基因序列进行交换, 并将交换过的基因标记为已访问，将生成子代的染色体中未访问的基因按照父代染色体的顺序插入到子代染色体中未交换的位置。
变异操作 50%的概率使用相互交换变异，将染色体上的两条边相互交换, 50%的概率使用反转变异，将染色体上的一段路径反转
选择操作每次选择前都会对所有染色体进行评估，从所有染色体中随机选出一对染色体，评估分数越高的染色体被选中概率越大。

对于最短旅行商问题，本算法在较短的时间里可以找到一个可接受的但不一定是最优的解，遗传算法强大灵活但是容易陷入局部最优，另外也难以确定合适的参数。