该项目为本人离散数学学科的课程设计，并将该项目传到博客以作交流学习与备份。该文档已作为论文上传。
1. 旅行商问题介绍
1.1 旅行商问题
旅行推销员问题（Travelling salesman problem, TSP）问题是指给定一系列城市的坐标，或每对城市之间的距离，要求访问每一座城市且只访问一次，并最终回到起始城市，求此过程的最短回路。从图论的角度来看，TSP问题实质上是在一个带权完全无向图中找到一个权值最小的Hamilton回路。
1.2旅行商问题的几种解法
1.2.1最近邻点法（Nearest Neighbor Procedure）
最近邻点法思路是通过不断寻找离当前顶点最近的顶点，连接起来组成最终回路。这个方法是一种贪心算法，较为简单，容易实现，时间复杂度是O(n^2)，远低于其他算法的时间复杂度。但是，最近邻点法得到的是近似解而非最优解，因此其精度较低，很难收敛到最优解，因此可能会在局部最优解附近徘徊，在许多情况下只能找到近似解，无法找到最优解。
1.2.2节省法（ClarkandWright Saving）
节省的基本原理是比较路线节省量。已知两边之和大于第三边，节省量就是将这两个顶点相连所节省的费用。将所有顶点对之间的距离按照其节省量从大到小排序，并逐个加入路径，这样可以保证每次加入路径都能使总费用最小。
节省法只需要对所有顶点对之间的距离排序，然后逐个加入路径即可，实现起来比较简单。时间复杂度为O(n^2 log n)，相比其他算法更为高效，并且该算法能够找到较优解，即使不能找到最优解，结果也是较优的。然而，该算法并不能保证找到最优解该算法只能找到较优解，且需要排序，所以不能用于离散化问题，同时需要使用堆和链表等数据结构，可能导致空间复杂度较高。
1.2.3模拟退火（Simulated annealing algorithm）
模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。该算法的流程如下：首先选取一个初始解作为当前解，并设定初始温度。在每一次循环中，生成一个新解作为候选解，并计算其费用，如果新解的费用更优，则直接接受新解作为当前解；如果新解的费用不优，则以一定的概率接受新解作为当前解，按照一定的降温策略降低温度，当温度降至一定值或达到最大循环次数时，终止循环，最后输出当前解作为最优解。
模拟退火算法可以找到全局最优解，并且不易陷入局部最优解，可以适用于各种类型的优化问题，并且算法简单实现，易于理解。但是，求解的速度较慢，对大规模问题的求解效率较低，也可能在低温时陷入局部最优解，需要设置合适的降温策略，并且终止条件不好设定。
1.2.4禁忌搜索（Tabu Search）
禁忌搜索（Tabu Search）算法禁忌搜索算法是一种启发式算法。它从一个初始可行解出发，使用禁忌表来记录之前搜索过的解决方案，并在之后的搜索中避免重复访问这些解决方案。禁忌表中的每一项都是一组禁忌规则，表示不能在某个城市之后继续前往另一个城市。通过这种方式，禁忌搜索算法可以有效地避免环路的产生，从而找到TSP问题的最优解。
禁忌搜索算法可以有效地避免重复访问之前搜索过的解决方案，从而提高搜索效率，可以根据具体问题设置不同的禁忌规则，提高算法的适用性，它具有一定的启发式性质，可以通过禁忌规则来引导搜索，有可能得到全局最优解。但是，禁忌表需要预先分配足够的空间来存储禁忌规则，这会增加空间复杂度，禁忌搜索算法的复杂度因为受禁忌规则的影响可能难以预估，并且它只是一种启发式算法，并不能保证找到全局最优解。
1.2.5 蚁群算法(Ant Clony Optimization)
蚁群算法(Ant Clony Optimization)是一种仿生学算法，原理类似于自然界中蚂蚁觅食的行为。在自然界中，蚂蚁在寻找食物时会在沿途释放信息素，信息素浓度的大小表征路径的远近，信息素浓度越高，表示对应的路径距离越短。蚂蚁会根据信息素的浓度来选择路径，并释放一定信息素，进而使蚂蚁能够找到一条由巢穴到食物最近的路径。在蚁群算法中，每只蚂蚁都是一条路径，在搜索过程中不断地更新路径的质量。蚂蚁们之间的信息交流通过在路径上留下的信息素来实现。最终，所有蚂蚁搜索出来的路径中最优解的路径就是最优解。该算法可以解决如 TSP 问题等多种组合优化问题，其结果可与模拟退火，遗传算法等通用的启发式算法相媲美 [1] 。
蚁群算法能快速收敛到最优解，能在全局范围内搜索最优解，同时具有很高的并行性，可以利用多核处理器来加速计算，也能够很好的解决那些具有局部最优解的问题。然而，蚁群算法对参数设置非常敏感，如果参数设置不当可能会导致收敛到局部最优解，其实现也较为复杂，需要对算法的运行过程进行细致的设计，在搜索时需要维护大量的蚂蚁，空间复杂度较大，而对于大规模的问题，蚁群算法的收敛速度可能较慢。
2.遗传算法求解旅行商问题
2.1遗传算法
2.1.1 背景
在学习数据结构的过程中，搜索是一类重要且应用广泛的算法，最为熟悉的是建立在图的数据结构基础上的深度优先搜索和广度优先搜索，以及算法设计中的回溯算法。其本质是在定义的解空间结构上按照一定顺序进行枚举，加入一些优化策略缩小搜索范围，从而找到最优解。然而在搜索规模巨大时，以上诸种方法将面临不可接受的时间复杂度。于是，遗传算法应运而生。
2.1.2 遗传算法概述
在许多问题中，由于解空间规模巨大，采取缩小可能解的策略仍然无法得到满意的搜索范围，只能够在一定程度上牺牲解的最优性，来换取可接受的搜索时间。因此，遗传算法的主要思想是借鉴于达尔文的自然选择下的进化论模型，将要解决的问题模拟成一个生物进化的过程，通过复制、交叉、突变等操作产生下一代的解，并逐步淘汰掉适应度函数值低的解，增加适应度函数值高的解，以得到较优解。算法可以分成三个步骤：生成个体、形成种群——选择淘汰——种群繁殖，后两个步骤不断循环，最后得到较满意的解。算法思想的核心是使用合适的编码方式将问题的解用向量的形式进行表示，用于模拟物种个体的基因。使用合适的适应度函数对解的优劣进行评估，模拟自然选择的过程保留较优解、抛弃不优解。最后模拟种群的繁殖中基因的交换、变异过程，使得已有解可以有机会生成更优解。遗传算法适用于解决难以对算法的时间复杂度进行进一步优化的NP难问题。
2.2遗传算法旅行商问题中的应用
在旅行商问题上应用遗传算法，可以很好地体现遗传算法的思想精华，在遗传算法的一般情况上也存在一些针对性的调整。首先需要对问题的解进行编码表示为向量形式，模拟基因结构，在一般问题中常用二进制编码进行构造。在前述旅行商问题描述中，解应该是一个哈密顿回路中结点的排列，二进制编码表示并不方便，适合用结点标号的排列进行表示，例如旅程（3-2-7-8-6-4-9-1-5）可以直接表示为（3 2 7 8 6 4 9 1 5），这是第一处调整。在一般问题中基因往往允许重复，而哈密顿回路中一个结点仅允许出现一次，同一个染色体上不允许出现重复基因，这是第二处不同之处。
在编码之后，随机产生基因的排序作为染色体，本次研究性学习中采取20作为默认染色体数量。随机生成的染色体的集合构成初始种群。
在选择之前需要设计合适的适应度函数，旅行商问题可以用总路程和的倒数作为评价解优劣程度的标准，也体现了该个体对于环境的适应程度。在自然选择的过程中采取轮盘赌策略，适应度大的个体有更大的生存概率，其数值为该染色体适应度/该种群所有染色体适应度之和，采用随机数生成的方式对个体进行选择。选择得到当代个体中的优胜者，进行繁殖期望得到更优解。
繁殖的环节存在交叉、变异两个环节：交叉环节使用父亲DNA和母亲DNA的某段相同位置的片段进行交换，模拟自然界的交叉互换。在旅行商问题中由于同一回路不能出现相同基因，所以在交换过程中使用映射的方式对重复基因进行处理：在交换的片段间建立映射关系，交换后对重复单元按照映射关系再次替换，解决重复情况。变异操作则相对简单，按照设定的变异概率，从随机的位置选择一对基因进行交换，同时满足了随机和不重复的要求。在一代代反复选择、繁殖的过程中，逐渐得到较优解，实现旅行商问题的解决。
2.3代码实现
2.3.1 程序框架
主体框架的抽象层次为：基因——染色体——种群。程序中设计了Chro类（chromosome缩写）模拟染色体，包含基因字段gene、该染色体适应度字段fits，实现了随机生成序列、繁殖过程中染色体交换、变异以及其他计算相关操作；设计了Population类模拟种群，是染色体的集合，包含染色体数组chromoesomes、种群适应度之和sum_f、选择概率数组P，实现了种群层面的选择、繁殖操作。同时定义了结构体City用于接收坐标形式的城市位置输入。
2.3.2 具体实现
将选择、交换、变异三部分实现过程在文中展示如下，具体代码细节见附录。
选择部分在种群层面实现，采用轮盘赌策略，首先计算染色体被选择的概率，数值为该染色体适应度/该种群所有染色体适应度之和，将种群中所有染色体的概率存入数组中。然后计算积累概率（类似于概率论中的分布函数），对染色体进行编号，每一位的数值等于编号小于该位的染色体概率之和，形成概率区间。然后生成随机数模拟区间投针，对投中的区间所表示的染色体进行选择。
交换部分在染色体层面实现，先随机选择交换位数和交换位置，再解决基因重复问题。确定位数位置使用随机函数生成，解决基因重复问题分为两个步骤：建立映射、按照映射替换。首先根据交换区域的对应基因建立映射关系，再在非交换区域找到与交换区域重复的基因，按照交换前建立的映射关系进行反向替换，剔除重复基因。
变异部分在染色体层面实现，设定变异概率，按照变异概率随机选择变异染色体和变异位置，将变异位置前后的两个基因进行交换，这样既满足随机位置基因变化的需要，又满足了基因不重复的要求。
2.4结果展示
按照程序提示输入旅行商问题城市数、遗传算法中染色体数、城市坐标、遗传代数后，即可得到染色体的具体信息、每一代的最优解信息。具体成果展现如下：
3.旅行商问题的拓展及应用
3.1基于旅行商问题的多旅行商问题
多旅行商问题（Multiple Traveling Salesman Problem, MTSP）是旅行商问题的延伸，多旅行商问题定义为：给定一个n座城市的城市集合，指定m个推销员，每一位推销员从起点城市出发访问一定数量的城市，最后回到终点城市，要求除起点和终点城市以外，每一座城市都必须至少被一位推销员访问，并且只能访问一次，需要求解出满足上述要求并且代价最小的分配方案，其中的代价通常用总路程长度来代替，当然也可以是时间、费用等。
解决MTSP的常用方法是将MTSP转化为TSP求解。然而，转化后的MTSP求解并不等同于TSP的求解，转化过程中还会带来很多问题，如TSP维度的增加和如何用TSP的描述方式有效的表示MTSP等[2]。将MTSP 转化为TSP的基本策略最早是由Gorenstein提出，其主要思想是基于旅行商的个数m，增加 m -1个虚拟城市，用来对不同的旅行商访问的城市进行间隔，并且将这些城市之间的直达距离设为无穷[3]。
MTSP问题在现实中的主要应用有应急物资输送等。如在地震、泥石流等自然灾害发生后，如何安排物资运送车在最短时间内将物资送达各个地点[4]。
3.2基于旅行商问题的配送\收集旅行商问题
随着物流行业的发展，人们逐渐倾向于线上购物，各个公司也将自己的物流服务外包给第三方物流公司。对于物流公司来说，每天面对着大量的物流订单，遍布全国各地，此时，如何安排运送车辆就成为了节约运营成本、提高运营效率的关键问题。因此，配送＼收集旅行商问题（traveling salesman problem with pickup and delivery,TSPD）对于物流企业而言是至关重要的，具有很高的研究价值。
根据配送需求与收集需求的先后关系，TSPD可分为三类：配送同时收集，即每个顾客点既有配送需求，又有收集需求；在服务所有有配送需求的顾客后，再服务有收集需求的顾客；混合配送和收集，允许在某些配送需求前满足一些收集需求[5]。
4.总结与展望
旅行商问题具有重要的实际意义和工程背景。它一开始是为交通运输而提出的，如：用来规划配送路线，以便在最短时间内到达所有客户；用来规划旅游路线，以便在最短时间内游览所有景点；用来规划物流运输路线，以便在最短时间内将货物运送到所有目的地；用来规划航线，以便在最短时间内将货物运往所有港口。此外，TSP在许多其他领域中也有应用，如电路设计、晶体结构分析、天文观测等。
在电路设计方面，旅行商问题（TSP）可以用来规划路径，以便在最短时间内把信号传递到所有节点。这在许多应用中都很重要，例如在芯片设计中，路径规划可以用来减少延迟和提高性能。在通信网络设计中，TSP可以用来规划最短路径以便传递数据包。在计算机网络中，TSP可以用来规划路由表，以便在最短时间内将数据包传递到目的地。还有一种应用就是在布线路径规划中。 在印刷电路板（PCB）设计中，TSP可以用来规划路径，以便在最短时间内将电线连接到所有元件。在这种情况下，TSP可以用来最小化布线长度和避免线路的交叉。
在晶体结构分析中，旅行商问题（TSP）可以用来规划最短路径，以便在最短时间内从一个原子到达另一个原子。这在晶体结构模拟中很有用，因为它可以帮助研究人员更好地理解材料的性质和行为。其中一个应用是在晶体缺陷检测中。晶体缺陷是指晶体结构中不符合点群对称性的地方，它们可能导致材料性能下降。TSP可以用来规划缺陷检测路径，以便在最短时间内检测到所有缺陷。另外一种应用就是在结构优化中。在晶体结构优化中，TSP可以用来规划移动原子的路径，以便在最短时间内使晶体结构达到最优状态。这可以帮助研究人员提高材料的性能和寿命。
在天文学中，旅行商问题（TSP）有多种应用。其中一些常见的应用如下：TSP可以用来规划望远镜的观测路线和卫星的轨道，以便在最短时间内观测到所有目标，使得观测效率更高，燃料、人力耗费最少，更好的获取数据。此外，TSP在许多其他天文学领域中也有应用，如星系演化模拟、太阳能系探测器路径规划等。
实际上很多组合优化问题如背包问题、分配问题、车间调度问题都和TSP一样属于NP完全问题，难度是一样的。如果其中一个能用多项式确定性算法解决，那么其他所有的NP完全问题也能用多项式算法解决。故而，对于TSP问题解决方案的不断优化也在推动其他NP问题的解决。
附录:
本研究性学习实现的完整代码如下：
#include<iostream>
#include<cmath>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<Windows.h>
#include <algorithm>
#include <algorithm>
#include<sys/timeb.h>
#define ERROR -1
#define MAX_CITY_NUM 50
#define DEFAULT_GENE_SUM 9
#define DEFAULT_CHRO_SUM 20
using namespace std;
typedef struct City {
int x, y; //记录城市坐标
}City;
City cities[MAX_CITY_NUM]; //先定义50个，实际可能用不到这么多
double distance(int a, int b) // 计算a城与b城之间的距离
{
return sqrt(pow(cities[a].x - cities[b].x,2) + pow(cities[a].y - cities[b].y,2));
}
int gene_sum = DEFAULT_GENE_SUM; // 染色体上的基因数，实际可能不止9个
class Population; // 种群类，这里先定义好让染色体类引用
class Chro // 染色体类 Chromoesome
{
public:
Chro(); // 构造函数，默认初始适应度为0
void RandomInit(); // 随机初始化染色体上的基因序列
double fx(); // 计算适应度的函数fx
void display(); // 展示染色体上的基因序列
void copy(Chro s); // 从染色体s复制到该染色体
void exchange(Chro& s); //将该染色体与s染色体交叉互换
void variation(); // 基因变异函数
friend int findx(int gene[], int start, int end, int x); // 寻找基因x在染色体上的位置
friend class Population; // 定义为友元类，使种群类Population可以访问其中某条染色体的私有成员
private:
int* gene; //基因序列数组，用指针定义可以修改长度
double fits; //该染色体的适应度
};
Chro::Chro()
{
gene = new int[gene_sum]; //创建了基因序列数组gene，长度为gene_sum
fits = 0; //初始适应度为0
}
void Chro::RandomInit() // 随机初始化染色体上的基因序列
{
int i;
time_t t;
for (i = 0; i < gene_sum; i++) {
gene[i] = i;
}
struct timeb timeSeed;
ftime(&timeSeed);
srand(timeSeed.time * 1000 + timeSeed.millitm);
//srand((int)time(&t)); // 确保不会生成重复的随机数
for (i = 0; i < 1 + int(gene_sum / 2); i++) {
swap(gene[i], gene[i + rand() % (gene_sum - i)]);
}
fx(); //可删去？
Sleep(1); //睡眠1s以产生随机差异
}
double Chro::fx() //计算适应度
{
double f = 0;
for (int i = 0; i < gene_sum; i++) { //计算该序列的总距离
f += distance(gene[i], gene[(i + 1) % gene_sum]);
}
fits = 1.0 / f; // 适应度是总距离的倒数，距离越小适应度越强
return fits;
}
void Chro::display() // 展示基因序列和该染色体适应度
{
cout << " [";
for (int i = 0; i < gene_sum; i++) {
cout << " " << gene[i];
}
cout << " ], fits= " << fx() << ", distance= " << 1 / fx();
}
void Chro::copy(Chro s) //染色体复制
{
for (int i = 0; i < gene_sum; i++) {
gene[i] = s.gene[i];
}
fits = fx(); // 重新计算适应度
}
int findx(int gene[], int start, int end, int x)// 在gene序列中查找x基因的位置并返回
{
for (int i = start; i <= end; i++) {
if (gene[i] == x) {
return i;
}
}
return ERROR;
}
void Chro::exchange(Chro& s) //将当前染色体与另一染色体s进行基因片段交换
{
int i, j = 0, k = 0, repeat; // repeat用于记录交叉后重复的基因
int pos = rand() % (gene_sum - 4); // 随机选择交叉位置（这里选择交换3或4个基因，交叉位置只能在[1，n-4]内）
int num = 3 + rand() % 2; // 随机选择交叉的基因数，最小为3，最大为4
/*
cout << endl; 查看发生交换的位置和位数
cout << "pos: " << pos << ", num: " << num << endl;*/
int* segment1 = new int[gene_sum]; // 用于记录交换后当前染色体上的基因
int* segment2 = new int[gene_sum]; // 用于记录交换后另一染色体上的基因
for (i = 0; i < gene_sum; i++) {
if (i >= pos && i < pos + num) {
segment1[i] = s.gene[i];
segment2[i] = gene[i];
}
else {
segment1[i] = gene[i];
segment2[i] = s.gene[i];
}
}
int* mapping1 = new int[4]; // 当前染色体中间段的映射
int* mapping2 = new int[4]; // 另一染色体中间段的映射
for (i = 0; i < 4; i++) {
mapping1[i] = ERROR; // 初值全部为-1
mapping2[i] = ERROR;
}
for (i = pos; i < pos + num; i++) {
repeat = findx(segment1, pos, pos + num - 1, gene[i]);
if (repeat == ERROR) {
mapping1[j++] = gene[i];
}
repeat = findx(segment2, pos, pos + num - 1, s.gene[i]);
if (repeat == ERROR) {
mapping2[k++] = s.gene[i];
}
}
/* 查看映射
cout << "map1 " << "map2" << endl;
for (k = 0; k < 4; k++) {
cout << mapping1[k] << " " << mapping2[k] << endl;
}*/
j = k = 0;
for (i = pos; i < pos + num; i++) {// 将重复的基因替换为映射中的基因
repeat = findx(gene, 0, pos - 1, segment1[i]);
if (repeat != ERROR) {
segment1[repeat] = mapping1[j++];
}
repeat = findx(gene, pos + num, gene_sum - 1, segment1[i]);
if (repeat != ERROR) {
segment1[repeat] = mapping1[j++];
}
repeat = findx(s.gene, 0, pos - 1, segment2[i]);
if (repeat != ERROR) {
segment2[repeat] = mapping2[k++];
}
repeat = findx(s.gene, pos + num, gene_sum - 1, segment2[i]);
if (repeat != ERROR) {
segment2[repeat] = mapping2[k++];
}
}
for (i = 0; i < gene_sum; i++) {
gene[i] = segment1[i]; // 交叉后的该染色体
s.gene[i] = segment2[i];// 交叉后的另一染色体
}
delete segment1;
delete segment2;
delete mapping1;
delete mapping2;
}
void Chro::variation() //变异
{
int pos = rand() % (gene_sum - 1); // 随机选择变异位置
int temp = gene[pos]; // 将被选中的基因和后面一位基因交换
gene[pos] = gene[pos + 1];
gene[pos + 1] = temp;
}
Chro solution; // 最终解（满足条件的适应度最高染色体）
int best_generation = 0; // 用于记录最好的染色体所在的代数
int chro_sum = DEFAULT_CHRO_SUM; // 种群中染色体数，默认先设为20
class Population
{
public:
Population(); // 构造函数
void best_fit();// 查找适应度最高的染色体
void select(); // 选择
void cross(); // 交叉
void variation();// 种群变异
void display(); // 显示种群内染色体
int generation; // 种群代数
private:
Chro* chromoesomes; // 染色体数组
double sum_f; // 种群适应度之和
double* P; // 选择概率数组,为每个染色体被选中的概率,其数值为该染色体适应度/该种群所有染色体适应度之和
};
Population::Population()
{
int i;
generation = 1; //初始代数为1
chromoesomes = new Chro[chro_sum]; //染色体数组用于记录种群中染色体
for (i = 0; i < chro_sum; i++) {
chromoesomes[i].RandomInit();
}
sum_f = 0;
P = new double[chro_sum];
for (i = 0; i < chro_sum; i++) {
sum_f += chromoesomes[i].fits;
}
for (i = 0; i < chro_sum; i++) {
P[i] = chromoesomes[i].fits / sum_f;
}
}
void Population::best_fit() // 查找适应度最大的染色体并返回其编号
{
int best = 0;
for (int i = 1; i < chro_sum; i++) {
if (chromoesomes[best].fx() < chromoesomes[i].fx()) {
best = i;
}
}
if (chromoesomes[best].fx() > solution.fits) {
solution.copy(chromoesomes[best]);
best_generation = generation;
}
cout << " The best fit in generation" << generation << " is: " << endl;
cout << " chromoesomes" << best + 1 << ": ";
chromoesomes[best].display();
cout << endl;
}
void Population::select() // 种群选择
{
int i, j;
int* selected = new int[chro_sum]; // 用于记录被选中的染色体号
double r;
double* q = new double[chro_sum]; // 用于记录积累概率
Chro* cp = new Chro[chro_sum];
q[0] = P[0]; // 积累概率
cout << endl;
cout << " Accumulation of probabilities" << endl; // 打印积累概率
cout << " q1= " << q[0] << endl;
for (i = 1; i < chro_sum; i++) {
q[i] = q[i - 1] + P[i];
cout << " q" << i + 1 << "= " << q[i] << endl;
}
cout << "\n Roulette wheel" << endl; // 轮盘赌，产生随机数（类似于区间投针）
srand(time(NULL)); //设置随机数种子，使每次产生的随机序列不同
for (int i = 0; i < chro_sum; i++) {
r = rand() % (10000) / (double)(10000);
cout << " r" << i + 1 << "= " << r << endl;
if (r <= q[0]) {
selected[i] = 0; // 选中第一个染色体
}
for (j = 0; j < chro_sum - 1; j++) {
if (q[j] <= r && r <= q[j + 1]) {
selected[i] = j + 1; // 选中第j+1个基因
}
}
cp[i].copy(chromoesomes[i]); //被选中的可以存活
}
for (i = 0; i < chro_sum; i++) {
chromoesomes[i].copy(cp[selected[i]]); //将存活的染色体重新复制回染色体数组
}
delete selected;
delete q;
delete cp;
}
void Population::cross() // 种群交叉
{
for (int i = 0; i < chro_sum; i += 2) { //每两个相邻染色体交叉
chromoesomes[i].exchange(chromoesomes[i + 1]);
}
}
void Population::variation() // 种群变异
{
int probability = rand() % 100; // 种群出现变异的概率为1%
if (probability == 1) {
int x = rand() % chro_sum; // 随机选择一个染色体变异
cout << " The chromoesome " << x << " is variated!" << endl;
chromoesomes[x].variation();
}
generation++; // 种群完成一次进化，迭代一次
}
void Population::display()// 依次输出每一条染色体
{
cout << endl;
int i;
for (i = 0; i < chro_sum; i++) {
cout << " chromoesomes" << i + 1 << ": ";
chromoesomes[i].display();
cout << endl;
}
cout << endl;
}
int main() {
cout << "请输入城市数(>=8)： ";
cin >> gene_sum; //城市数作为基因数
cout << "请输入预定的染色体数(一般20)： ";
cin >> chro_sum;
cout << "输入城市坐标： " << endl;// 输入每个城市坐标(x, y)
for (int i = 0; i < gene_sum; i++) {
cout << "\t" << i + 1 << ": ";
cin >> cities[i].x >> cities[i].y;
}
Population P0;
cout << "\n 代数=" << P0.generation << endl; //显示种群代数
P0.display();
P0.best_fit();
int T; // 进化的代数
cout << " 输入要进化的代数: ";
cin >> T;
for (int i = 0; i < T; i++) {
cout << endl << " 选择后的种群: "; // 选择
P0.select();
P0.display();
cout << endl << " 交叉后的种群: "; // 交叉
P0.cross();
P0.display();
cout << endl << " 变异后的种群: ";// 变异
P0.variation();
cout << " 代数=" << P0.generation << endl;
P0.display();
P0.best_fit();
system("pause");
system("cls");
}
cout << " 最短哈密顿回路为:" << endl; // 打印进化过程中最好的染色体，即解决方案
cout << " 在第 " << best_generation << " 代";
solution.display();
cout << endl;
system("pause");
return 0;
}
参考文献：
[1] 田贵超,黎明,韦雪洁.旅行商问题(TSP)的几种求解方法[J].计算机仿真,2006(08):153-157.
Tian Guichao, Li Ming, Wei Xuejie. Several Solving Methods for Traveling Salesman Problem [J]. Computer Simulation,2006(08):153-157.
[2] 俞庆生,林冬梅,王东.多旅行商问题研究综述[J].价值工程,2012,31(02):166-168.
Yu Qingsheng, Lin Dongmei, Wang Dong. Traveling salesman problem study review [J]. Value engineering, 2012, 31 (02) : 166-168.
[3] Samuel Gorenstein. Printing Press Scheduling for Multi-Edition Periodicals[J]. Management Science, 1970, 16(6) : B373-B383.
[4] 刘明,张培勇.求解多旅行商问题的新混合遗传算法:以应急物资配送为例[J].系统管理学报,2014,23(02):247-254.
Liu Ming, Zhang Peiyong. A new hybrid genetic algorithm for Multi-travel Salesman Problem: A case study of Emergency materials Distribution [J]. Journal of Systems Management,2014,23(02):247-254.
[5] 霍佳震,张磊.求解配送\收集旅行商问题的启发式算法[J].同济大学学报(自然科学版),2006(01):134-138.
Huo Jiazhen, Zhang Lei. A Heuristic Algorithm for Solving the Distribution/Collection Travel Salesman Problem [J]. Journal of Tongji University (Natural Science),2006(01):134-138.