1、实验目标
解决问题:旅行推销员问题(TSP)即给定有限个城市以及每两个城
市之间旅行的费用,需要找出花费尽量少的旅游路线,该路线满足每
个城市都能到达且仅到达一次后回到出发点。本次实验中要求解的
TSP 问题为选自 TSPLIB 中的一个 52 城市的 TSP 问题 berlin52。此问
题中有 52 个城市,各个城市之间的坐标以文本文档的方式给出。
开发语言: C++
平台:Visual Studio 2015
2、算法设计
总体流程:如图 1 所示,遗传算法的整体流程是首先将旅行商问题抽
象为 52 个二维坐标之间的路径规划问题,目的是找到使遍历 52 个二
维坐标的路径距离最小。用大小为 52 的染色体表示 52 个城市,染色
体序列即表示城市遍历顺序。然后在规定进化代数之内根据种群大小
形成初始种群,对种群进行遗传操作,即交叉、变异。进化完成后将
路径写入文档。