遗传算法解决TSP问题
一.前言二.什么是遗传算法？1.不妨先看个小故事2. 从故事中发现到规律3. 悟出实际的“遗传算法”(1) 初始化种群(2).计算适应度(3) *选择操作(Select): 赌轮选择 + 精英保留策略(4) *交叉（Crossover）(5) *变异（Mutation）(6) 产生下一代种群(7) 遗传算法的意义三.知其所以然：TSP问题到底怎么和遗传算法联系起来？四.理论与代码结合五.实验结果六.源代码七.个人理解及总结一.前言
题目：以N个节点的TSP（旅行商问题）问题为例，应用遗传算法进行求解，求出问题的最优解。
旅行商问题（Traveling Salesman Problem,
TSP），又译为旅行推销员问题、货担郎问题，简称为TSP问题，是最基本的路线问题。假设有n个可直达的城市，一销售商从其中的某一城市出发，不重复地走完其余n-1个城市并回到原出发点，在所有可能的路径中求出路径长度最短的一条。
首先，本菜鸡在网上看了很多形形色色关于遗传算法解决TSP问题的文章，包括python、C++、甚至没碰过的Matlab，都看得不是很懂。大家都说得很理论，而且也很少有人能说清楚“遗传算法”和“TSP”这个问题之间有什么联系，很多都是介绍完遗传算法就直接抛出个代码，没有详细地讲解。基于这一点，本人打算自己肝一篇通俗易懂，奶奶都看得懂的遗传算法解决TSP的文章。
本人也是参考一篇C++的文章，其中的代码也是参考这篇文章的（不过他存在点小错误），当然我也根据自己的理解修改了一部分。非常感谢这位大佬！但是在我自己写的这篇文章，代码的详解、思路完全是本人的理解，希望大家能耐心一点，跟着我的思路走下去！
二.什么是遗传算法？
1.不妨先看个小故事
什么是遗传算法？百度一堆，但是在我的主场，我还是希望用自己的语言描述出来。所以大家不妨先看个小故事来了解一下先。
该算法是根据大自然中生物体进化规律而设计提出的。
就从我们人这个种群举个生动形象的例子来理解吧，在很久以前，我们的种群还是一群猴子的时候，假设这一群猴子都只能吃植物，因为他们不够力气。众所周知，种群的繁衍是需要雄猴子与雌猴子交配的，因此他们有许多许多的后代，但是他们的后代大部分都是没有力气去拿起石头的。然后有一天他们走在海边在他们的后代中有年轻猴子突然脑抽，尝试去捡起石头，结果他很轻松地就举起了石头，并且可以利用石头去撬开贝壳等壳类海鲜。
从未吃过如此美味的食物的猴子们纷纷都羡慕这位大力士，雌猴子都说他很man，纷纷都想和他去生猴子，在交配的过程中就选择了他。
猴子们都纷纷议论，问fit man：“你为什么能那么大力？” fit man回答：“我也不知道呀，我就是天生神力啊（此处@常威）。”其实当时的他们不知道，其实fit man自己变异了，所以就变成了大力士了。
因此，不出所料，fit man的后代个个也都很fit，很大力，都能举起石头。而雌猴子们都纷纷不愿意和 其他那些fat man 没力气的雄猴子交配，那么这些fat man 也在这个不断繁衍的种群里逐渐淘汰。
2. 从故事中发现到规律
在上面的例子，我们可以看到几个关键词：选择、交配、变异
选择（select）： 在交配过程中，雌性动物肯定会选那些条件好的，挑fit man而不是fat man。而且fat man在生存中会逐渐被欺负而可能逐渐被淘汰。因此好条件的就会留下来，不好的就会被淘汰，这里除了雌性的选择，其实也有包括大自然的选择，fat man容易被其他动物欺负，而fit man由于很强壮则能很好的生存下来。这也体现了“适者生存，物竞天择”。
交配（crossover）：学过生物的我们都知道，实际上就是猴子之间的染色体进行交叉操作，然后得到一条新的染色体。这样就有了后代。因此我们也可以称之为交叉。
变异（mutation）：实际上就是染色体的某个基因进行了突变，比如上面的fat基因突变成了fit基因。
因此在每一代的种群的繁衍中，都会进行这三个操作 “ 选择” ，“交叉”，“变异”。这是个规律！
3. 悟出实际的“遗传算法”
我们先来看一下遗传算法的流程图吧：
那么我们用上面那个猴子的例子来走一遍这个流程图，
开始 -->
(1) 初始化种群
在初始化操作中，我们往往需要对种群的染色体进行编码，因为染色体上有许多的等位基因，有控制体毛颜色的基因，有控制身高的基因、当然还有控制刚刚fit or fat的基因（假设有这个基因）等等。
Q：那么我们如何将这些基因通过计算机来表示呢？
A：我们可以将这些基因在计算机中编码为0，1，甚至是float型的小数。
例如一条染色体，我们可以编码为00110100
于是，每个个体都有对应的染色体了，并且能够通过计算机来表示所对应的基因。这样我们就得到初始种群的所有染色体了。
(2).计算适应度
什么是适应度？你可以理解为是这个生物对环境的适应能力。
适应度越高，说明你对环境的适应能力越好。
在上面的例子中，fit man天生大力，当受到其他动物的攻击的时候有能力去反击抵挡，适应能力高；而fat man由于手无缚鸡之力，虽然能苟且偷生，但也非常容易地受其他动物攻击，因此适应能力就低。
所以我们就需要计算每个个体的适应度（包含雌性，同时雄性也要选择雌性嘛）。
一般我们会有一个目标函数f(x),你可以理解为f(x)就是用来优化的，是优化函数。在群体进化中，个体的适应度通常依赖于个体的目标函数值f(x)，所以一般很多文章都是将适应度直接等于目标函数值或设一些和目标函数相关依赖的函数，比较好计算。
(3) *选择操作(Select): 赌轮选择 + 精英保留策略
选择操作其实体现了进化论上的“优胜劣汰”，其执行主要依赖于个体适应度，这很容易理解，适应度高的自然就能生存下来，而适应度低的就会逐渐淘汰。
一般来说，适应度高的个体被选择的概率大；相反，适应度低的的个体被选择的概率小。
Q：那我们一般要怎么实现选择这个过程呢？
A：选择的方式（选择算子）：赌轮选择和联赛选择
一般我们大多数会选择赌轮选择的方法。
@什么是赌轮选择？
大家都知道商场搞活动的时候会拿个奖品轮盘，按常识，我们知道面积占得越大，被选中的概率就会越大，这也是赌轮盘里面的一个朴素的思想：被选中的概率与个体在总体中所占比例成正比。
假设我们不是用“一等奖”或“二等奖”这种定性的指标描述，而是给每个个体 xix_ixi一个适应度的值f(xi)f(x_i)f(xi)，则使用轮盘赌算法选择该个体的流程为：
步骤一：计算每个个体适应度占总群适应度总和的比例，即每个个体的选择概率
p(x)=p(x)=p(x)=f(xi)∑j=1Nxj{f(x_i)}\over{\sum_{j=1}^N{x_j}}∑j=1Nxjf(xi)
步骤二：计算每个个体的累积概率，相当于转盘上的“跨度”，“跨度”越大越容易选到。
sumi=sum_i=sumi=∑j=1if(xj)\sum_{j=1}^i{f(x_j)}∑j=1if(xj)
即要求”当前个体“之前的所有个体的选择概率之和，相当于概率论中的概率分布函数F(x)。
步骤三：随机产生一个[0,1]之间的随机数rand。将rand逐一与sumisum_isumi（i = 1,2,…,N）进行比较，若sumisum_isumi>rand，则选择xix_ixi。
例如rand=0.456，sum4sum_4sum4 = 0.398，而sum5sum_5sum5 = 0.560，则说明sum5sum_5sum5>rand，此时选择x5x_5x5。
通过这三个步骤，我们即完成我们的选择（select）操作的大部分啦！（另一部分在下面介绍：精英保留策略）
但需要说明的是，每执行上述步骤一次，仅选择一个个体。因此，如果要选择N个个体构造父代个体集，则需要执行上述步骤N次。
这里我给大家看看书上的小栗子：
我相信看到这里大家肯定会有个几个疑问点：
Q1: 既然要选择，在有很多个个体的前提下，为什么不直接选择最好的那几个，即选择适应度比较高的前几个，然后将其他的都抛弃，这不直接省事了吗？
A1： 说实话，我一开始也有这样的想法，不过请同学们拉上去再重新看一下这个小节的刚开始是怎么描述的。（我加粗了）一般来说，适应度高的被选择的概率大，概率大 ≠\neq= 一定会被选择； 同样的，概率小也不一定会被抛弃，还是有机会被选择的。
所以说，山鸡到后面会变凤凰 ，大家也说不准。个人认为，主要还是要保留这个种群的多样性吧。
--------------------------------------$----------------------------------------
Q2：这个累计概率sum到底有什么用呢？我不是都求出了适应度占总适应度的比例了吗，直接用这个概率来选择不香吗？
A2: 我刚学习的时候也百思不得其解，经过和同学的激烈讨论终于得出了答案。请大家细品下面这一段话：
你知道这个概率，但是在现实中你怎么将这个概率转化为一个实质性的东西，而这个实质性的东西就是代表这个概率背后的实体。举个很简单的例子，就像我们玩骰子，每个面都是1/6，怎么代表说这个1/6是代表一面还是二面，还是五面六面。这时候累计概率就派上用场了，我们可以将概率累计起来，然后说(0,1/6)这个区间内的数字代表一面，(1/6,2/6)这个区间的数字代表二面，依此类推…看到这里你应该明白累计概率sum有什么用了。
大家可以用这个思想再去看上面那个小栗子的图片，下面我画了个C1,C2,C3区间，再多加思考！
精英保留策略：
刚刚上面同学有个天真的想法：“为什么不直接选最好的，不香吗？”
其实科学家们也有这种想法，但用了另外比较巧妙的方法，就是精英保留策略。
Q：什么是精英保留策略？
A：为了从理论上保证全局收敛性，并且在实际执行中提高优化性能，遗传算法通常采用精英保留策略。精英保留策略是指当前群体中具有最高适应度的个体直接进入下一代群体，并且不参与交叉和变异（交叉变异后面会介绍）。通俗来讲，最好的个体直接晋级，不需要被选择。
做法：
1.找出最高适应度和最差适应度的两个个体。
2.将最差的直接淘汰。
3.将最好的直接复制一份来代替那份最差的。
4.此时相当于有两份最优的直接进入下一代，而其余个体则进行交叉变异等操作。
例如 ：有10个个体，有最高和最低的适应度，我们将最低的淘汰，最高的复制多一份，此时这两个最优的直接进入子代（下一代）个体的集合当中，而其余8个则需要进行把交叉变异操作来进入下一代的个体集合。
意义：精英保留策略既保留了种群的多样性，也保证了群体质量不会退化。
总结：到这里，选择操作就完成啦，其实就这两个操作“赌轮”+“精英保留策略”！
----------------------------------------------------------------
(4) *交叉（Crossover）
经过了被大自然的选择，首先恭喜fit man活下来了。 然后又到了交配的季节，于是他选择了个靓妹进行交配。学过生物的我们都知道，他们的后代中在减数分裂前期Ⅰ的双线期，同源染色体交叉在一起。通俗来讲，就是染色体之间的信息交换。
因此，交叉（crossover）：指的是通过个体之间的信息交换来模仿自然界中的交配过程。
对于群体中随机选择的两个个体，会以一个交叉概率pc对它们执行交叉操作。
一般交叉概率我们会选择得比较大，保证后代的多样性，提供多种选择。
通常使用的交叉分为：一点交叉和两点交叉 （个人觉得甚至可以三点）
下面就是交叉的操作，比较简单。
一点交叉：选择一个交叉点CPoint，然后在[0,1]之间产生rand，若pc >
rand，则进行在CPoint右半部分交换信息。（如下图1）
二点交叉：和一点交叉大同小异，选两个交叉点CPoint1，CPoint2（CPoint1<CPoint2），然后也是若pc >
rand，则进行两点之间的信息进行交换（如下图2）
总结：交换还是比较简单的，主要是模拟自然界的交配行为。
-----------------------------------------------------------------------------
(5) *变异（Mutation）
变异：顾名思义，就是染色体上的基因突变了。可能fat man变fit man，当然fit man 也有可能变回fat man，存在很多变数。
每个个体的变异概率我们设为pm。一般来说，pm是取得很小的。
具体实现：
一条染色体有n个基因位，用各种0，1来表示。然后我们对于这n个基因位分别设置随机数randirand_irandi(i = 1,2…,n)。若randirand_irandi< pm,则对第i个二进制位执行取反操作，即0变1、1变0；
-----------------------------------------------------------------------------------
(6) 产生下一代种群
到了这一步，种群经过了选择、交叉、变异 这三个操作，已经得到子代的个体集了。然后种群的迭代次数G+1，若G还未达到所要求的迭代次数，则又进行开始计算适应度、选择、交叉…等操作了。就这样不断循环，直到我们得到我们所需要的最佳方案，此时就可以退出啦！
所以整个遗传算法就是这样子啦！
-----------------------------------------------------------------------------------
(7) 遗传算法的意义
意义：
初始群体经选择、交叉和变异，下一代群体的最高适应度优于初始群体的最高适应度，这表明遗传算法的选择、交叉和变异能够有效提高群体的适应度。因此，通过不断地执行这三个操作，群体最后有望收敛于全局最优解。而且，精英保留策略直接让群体中的最好个体进入下一代群体，保证了群体质量不被退化。
三.知其所以然：TSP问题到底怎么和遗传算法联系起来？
到了现在，很多同学都知道了遗传算法的流程，但是这到底和TSP问题怎么联系起来呢？染色体和城市之间有半毛钱关系吗？交叉变异又与我城市之间的距离有关系吗？
相信这也是很多同学的困惑之处，带着这些问题，我一个个来解释。
不过先请大家拉到最上面重温一下题目，这里简单阐述一下：有10个城市，要不重复地走完所有城市，并保证距离最短，求最短距离以及城市顺序。
首先，TSP的数学模型（即目标函数，其实就是距离总和）可以表示为如下形式：
∑i=1n−1(di,i+1+dn,1)\sum_{i=1}^{n-1}{(d_{i,i+1}+d_{n,1})}i=1∑n−1(di,i+1+dn,1)
其中，di,i+1d_{i,i+1}di,i+1表示地点i与i+1之间的距离。
疑惑一：染色体代表什么?
解惑：这其实是一个编码环节，我们可以想象，一个城市序列就对应一条染色体，而一条染色体里面有10个基因，而基因就代表着城市。因此一条染色体自然就代表着这个商人走的城市的顺序，比如[5,3,7,6,4,2,1,8,0,9] ,商人从 城市5 依次按这个序列走到 城市9。
因此，我们初始的时候可以设10条染色体（也可以设很多条，个人选择，设越多条可能性越大，这里为了讲解先设10条），即有10条不同的“路径”，这10条染色体就为一个种群。到这为止，就解决了我们第一个疑惑。
-------------------------
疑惑二：适应度要怎么表示？
解惑：一般来说，我们在将适应度直接等于目标函数值或设一些和目标函数相关依赖的函数。
在这里我们的目标函数就是城市距离之和，因为我们的目标是要求序列城市的距离最短，但是我们需要的是适应度高的，这时候我们可以弄一个反比，令适应度等于一个式子：
fiti=1SumDistancei(i=1,2,.,n)fit_i=\frac{1}{SumDistance_i} (i=1,2,.,n)fiti=SumDistancei1(i=1,2,.,n)
此处 fitifit_ifiti为第i条路径（染色体）的适应度，SumDistanceiSumDistance_iSumDistancei代表为第i条路径里的城市(按顺序)的距离总和，就像上面的序列Sum = d[5][3]+d[3][7]+…+d[0][9]+d[9][5]。
这样的话，距离越短，适应度就越高，符合我们的预期！
-------------------------
疑惑三：选择，交叉，变异分别如何与之联系
解惑：
1. 选择操作：赌轮选择+精英保留策略
首先是赌轮选择：一共10条染色体，后代也设为是10条(即10个父代产生10个子代)，每条染色体都有对应的sum累积概率。
然后进行10次循环，
在每一次的循环中：设一个rand随机数，然后用累积概率sum来比对，此时就选择刚好比sum小的那条染色体（还记得累积概率的作用吗？可以拉到上面去重温一下）。
就这样如此循环10次，选择出10条染色体，这10条中可能会有重复的，不用担心，这是正常的，适应度大的染色体 被选择的概率就大。
其次就是精英保留策略：在刚刚赌轮选择中选择出的10条染色体，我们挑出一条适应度最高的和一条适应度最低的染色体（路径最短和路径最长的）。然后直接淘汰掉适应度最低的染色体，将适应度最高的染色体复制多一份，这样经过精英保留策略后的10条染色体中，有两条是适应度最高的。此两条在后面的不用进行交叉变异操作，直接进入下一代的子集中。
2. 交叉操作
在刚刚经过选择后，除了最优的两条，其余8条染色体则进入交叉环节。这时候我们一般使用两点交叉的方法。随机选出两个点Point1，Point2。这两个点其实就代表着某个位置。例如Point1在第三个位置，Point2在第七个位置（注意：不是第三个城市，是位置）。然后就在区间[2,6] （包含2、6）进行两点交叉的方法将信息交换。
但大家需要注意一个地方：就是信息交换后会有“同一染色体下出现有城市重复”的情况，此时就需要消重。
消重的操作：
在染色体0，染色体1中分别选中交换的A,B两个片段B的交换片段需要交换到A来，则需要将染色体0 中除了片段A以外的其他信息与片段B进行对比，若有相同，则将相同的先去掉。然后将比对后剩余的城市放在染色体的前头集中，再紧跟加上B片段的所有信息。最后剩余的空位就放10个城市中没出现过的。这样就完成了染色体0的消重操作，染色体1的亦是如此。
3. 变异操作
变异的操作其实有很多种，这里介绍一种：
设置两个随机数，第一个随机数rand1rand_1rand1，目的是：“挑哪个染色体进行变异”。第二个随机数 rand2rand_2rand2，目的是：“挑上一步选中的染色体里的哪个位置进行变异”，挑到一个位置后，比如说位置3。就将这个序列的位置 n-3 的内容与 位置3的内容 进行互换。这样就得到一条变异后的染色体了。^ 详情看下图
四.理论与代码结合
1.染色体（城市序列）表示：
struct group {int city[11]; //一共有10个城市，然后最后那个11的位置就令他与位置0相等//这样一条路径就构成回路double p;//占总群的概率double fit;//适应度double sum_p; //累计概率}group[10];
2.全局变量：
double dis[10][11]; //城市之间的距离int generation, die; //generation为最优的那一代，die表示需要迭代多少代int cities[2][10];//记录城市坐标 ，cities[][],一维中的0代表x坐标，1代表y坐标；二维代表城市int citynum = 10;//10个城市int groupbest[11]; // 用于保存最优解染色体double groupbestp; // 最优解的占总群的概率double groupbestfit; //最优解的适应度fitint changebest; // 是否用最优解代替新种群
3.函数总体：
void init_group();/* 初始种群和城市坐标，计算距离*/void calculation(); /*用来计算种群的p、fit */void savebest(); /*保存最优解*/void change_bestgroup();/*精英保留策略，用最优解代替新种群中的最差的染色体*/void select();/*选择--复制*/void crossover();/*交叉*/void mutation(); /*变异*/
4.所有运算的核心 - 函数calcuation()：
每次都要计算：
(1).各个染色体（城市序列路径）的总距离s
(2).计算各个染色体的适应度fit = 1.0 / s
(3).适应度占总适应度的比例
(4).累加概率
void calculation()/*用来计算种群的p、fit */{int i, k;double ss, s;s = 0.0;ss = 0.0;for (k = 0; k < 10; k++){for (i = 0; i < citynum; i++){s += dis[group[k].city[i]][group[k].city[i + 1]];}group[k].fit = 1.0 / s;//计算适应度。反比，距离越小，适应度越大ss += group[k].fit;//将每组数据的适应度相加，得到一个适应度总和s = 0.0; //每次计算完记得置0}s = 0.0;for (i = 0; i < 10; i++){group[i].p = group[i].fit / ss;//计算个体适应度占总适应度的比例s += group[i].p; //累加group[i].sum_p = s;//从第一个个体开始，对适应度比例进行累加}}
5.难点：交叉操作中的消重
声明一下：我这里交叉率是100%，因为交叉率一般都是很高的，你们也可以设置一下0.9，0.8之类的，这个很灵活的。
步骤一：选定交换片段
步骤二：第0条染色体的除交换片段A以外的城市与片段B消重
步骤三：将第0条染色体剩下的往前集中并且紧跟片段B
步骤四：分别补全即可，第1条染色体的消重也是重复步骤一到三。
大家可以结合上面“知其所以然的疑惑三”的内容看。下面是我的草稿，可以参考一下，也希望大家可以手推一下。
void crossover()/*交叉*/{int point1, point2; //交叉点1，交叉点2int temp, i, j, k, temp2[2][10], temp3[2][10], num, write;srand((unsigned)time(NULL));point1 = rand() % 10;point2 = rand() % 10;if (point1 > point2) /*保证point1小于point2*/{temp = point1;point1 = point2;point2 = temp;}//交换，每2条交换if (point1 != point2){for (j = 1; j < 10; j = j + 2){memset(temp3, -1, sizeof(temp3)); //初始化内存空间memset(temp2, -1, sizeof(temp2));k = 0;for (i = point1; i <= point2; i++){temp2[0][k] = group[j].city[i]; //temp2[0]存放 第1条染色体的交换片段Btemp2[1][k] = group[j - 1].city[i];//temp3[0存放] 第0条染色体的交换片段A//标记数字已经存在temp3[0][temp2[0][k]] = 1; temp3[1][temp2[1][k]] = 1;k++;group[j].city[i] = -1; // 将要交换的片段的城市位置都标为-1group[j - 1].city[i] = -1;}num = point2 - point1 + 1; //交换了多少个基因//消重/*第0条染色体的消重*/for (k = 0; k < point1; k++) {if (temp3[0][group[j - 1].city[k]] == 1)group[j - 1].city[k] = -1;elsetemp3[0][group[j - 1].city[k]] = 1;}for (k = point2 + 1; k < citynum; k++){if (temp3[0][group[j - 1].city[k]] == 1)group[j - 1].city[k] = -1;elsetemp3[0][group[j - 1].city[k]] = 1;}/*第1条染色体的消重*/for (k = 0; k < point1; k++){if (temp3[1][group[j].city[k]] == 1)group[j].city[k] = -1;elsetemp3[1][group[j].city[k]] = 1;}for (k = point2 + 1; k < citynum; k++){if (temp3[1][group[j].city[k]] == 1)group[j].city[k] = -1;elsetemp3[1][group[j].city[k]] = 1;}//第0条染色体的“将城市往前集合”并且“紧随交换片段”的操作write = 0;for (i = 0; i < 10; i++){while (write < 10 && group[j - 1].city[write] == -1){write++; //遇到-1的位置就+1。}if (write < 10){temp = group[j - 1].city[i];group[j - 1].city[i] = group[j - 1].city[write];group[j - 1].city[write] = temp; write++;}else{write = 0;for (k = i; k < 10; k++){group[j - 1].city[k] = temp2[0][write++];if (write == num)break;}break;}}//第1条染色体的“将城市往前集合”并且“紧随交换片段”的操作write = 0; for (i = 0; i < 10; i++){while (write < 10 && group[j].city[write] == -1){write++;}if (write < 10){temp = group[j].city[i];group[j].city[i] = group[j].city[write];group[j].city[write] = temp;write++;}else{write = 0;for (k = i; k < 10; k++){group[j].city[k] = temp2[1][write++];if (write == num)break;}break;}}// 第0条染色体的补全k = 0;for (i = 0; i < citynum; i++){if (group[j - 1].city[i] == -1){while (temp3[0][k] == 1 && k < 10){k++;}group[j - 1].city[i] = k++;}}//第1条染色体的补全k = 0;for (i = 0; i < citynum; i++){if (group[j].city[i] == -1){while (temp3[1][k] == 1 && k < 10){k++;}group[j].city[i] = k;k++;}}group[j].city[10] = group[j].city[0];group[j - 1].city[10] = group[j - 1].city[0];}//end of jcalculation();savebest();change_bestgroup();}//end of if (!)}
6.函数联系图：
这里说明一下：这里我在选择、交叉、变异的最后都用了change_bestgroup()，即精英保留策略。本来这个只是在选择用的，但其实三个操作都用也无伤大雅，都会保证种群的进化。
五.实验结果
第一次吃鸡：
连续吃鸡：
运气好的时候，很快就能吃鸡了，今天我写文章的时候尝试运行几次，结果一分钟吃了三次鸡，分享一下哈哈。
六.源代码
#include "pch.h"#include <iostream>#include<string>#include<cmath>#include<ctime>#include<fstream>#include <cstdlib>#include <vector>#include <algorithm>using namespace std;double dis[10][11]; //城市之间的距离int generation, die; //多少代int cities[2][10];//记录城市坐标 ，cities[][],一维中的0代表x坐标，1代表y坐标；二维代表城市int citynum = 10;//10个城市int groupbest[11]; //最优解染色体double groupbestp; //最优解的pdouble groupbestfit; //最优解的fitint changebest; // 是否用最优解代替新种群struct group {int city[11];//一维记录城市序号，二三维记录坐标double p;//占总群的概率double fit;//适应度double sum_p; //累计概率}group[10];void init_group();/* 初始种群和城市坐标，计算距离*/void calculation(); /*用来计算种群的p、fit */void savebest(); /*保存最优解*/void change_bestgroup();/*精英保留策略，用最优解代替新种群中的最差的染色体*/void select();/*选择--复制*/void crossover();/*交叉*/void mutation(); /*变异*/int main(){int j, flag;int out = 1; //退出double distancenum;while (out){distancenum = 0.0;flag = 1;init_group();while (flag){cout << "请输入种群繁衍代数（1000以内）：";cin >> die;if (die <= 1000)flag = 0;}while (die--){cout << die << endl;select();//选择crossover();//交叉mutation();//变异}cout << "最优种群是：" << endl;for (j = 0; j < citynum + 1; j++){cout << groupbest[j] << " ";if (j < citynum){distancenum += dis[groupbest[j]][groupbest[j + 1]];}}cout << "距离为 : " << distancenum << ",适应度为 : " << groupbestfit << ",代数为 : " << generation << endl;cout << "\n若要继续产生新种群请输入1，退出请输入0：";cin >> out;cout << endl;}}void init_group()/* 初始种群和城市坐标，计算距离*/{int i, j, random, flag, k;double ss;cities[0][0] = 87;//初始化坐标 cities[0][0]城市0的横坐标cities[1][0] = 7; //cities[1][0]城市0的纵坐标 ，前面第一维表示横纵坐标，第二维代表城市ncities[0][1] = 91;cities[1][1] = 38;cities[0][2] = 83;cities[1][2] = 46;cities[0][3] = 71;cities[1][3] = 44;cities[0][4] = 64;cities[1][4] = 60;cities[0][5] = 68;cities[1][5] = 58;cities[0][6] = 83;cities[1][6] = 69;cities[0][7] = 87;cities[1][7] = 76;cities[0][8] = 74;cities[1][8] = 78;cities[0][9] = 71;cities[1][9] = 71;memset(groupbest, -1, sizeof(groupbest));groupbestp = 0.0; //初始最优解的pgroupbestfit = 0.0; //初始最优解的fitchangebest = 0;for (i = 0; i < citynum; i++)for (j = 0; j <= i; j++){if (j == i)dis[i][j] = 0.0;else{dis[i][j] = sqrt(pow(cities[0][i] - cities[0][j], 2.0) + pow(cities[1][i] - cities[1][j], 2.0)); //欧氏距离，sqrt平方根dis[j][i] = dis[i][j];}}srand((unsigned)time(NULL)); //随机数的种子ss = 0;for (k = 0; k < 10; k++) //group[0],[1]....代表第n个城市所对应到各个城市的向量{//一个数量为10的种群，和10个城市环for (i = 0; i < citynum; i++){flag = 1;while (flag){random = rand() % citynum; //产生随机数[0,9] for (j = 0; j < i; j++){if (group[k].city[j] == random){break;}}if (j == i){group[k].city[i] = random;flag = 0;}}}group[k].city[10] = group[k].city[0];}//以上产生了10个种群，分别有不重复的染色体calculation();savebest();cout << "初始种群为：" << endl;for (i = 0; i < 10; i++){for (j = 0; j < citynum + 1; j++)cout << group[i].city[j] << " ";cout << "| | 适应度：" << group[i].fit << "\t占总群的概率：" << group[i].p << endl;}}void calculation()/*用来计算种群的p、fit */{int i, k;double ss, s;s = 0.0;ss = 0.0;for (k = 0; k < 10; k++){for (i = 0; i < citynum; i++){s += dis[group[k].city[i]][group[k].city[i + 1]];}group[k].fit = 1.0 / s;//计算适应度。反比，距离越小，适应度越大ss += group[k].fit;//将每组数据的适应度相加，得到一个适应度总和s = 0.0; //每次计算完记得置0}s = 0.0;for (i = 0; i < 10; i++){group[i].p = group[i].fit / ss;//计算个体适应度占总适应度的比例s += group[i].p; //累加group[i].sum_p = s;//从第一个个体开始，对适应度比例进行累加}}void savebest() /*保存最优解*/{int i, j, flag = 0;double fit = groupbestfit;j = 0; //标记更好的解的位置for (i = 0; i < 10; i++){if (group[i].fit > fit){j = i;fit = group[i].fit;flag = 1; //标记已经有更好的}}if (flag){generation = die;//将当前的代数赋值给generationfor (i = 0; i < citynum + 1; i++) //保存最优解{groupbest[i] = group[j].city[i];}groupbestp = group[j].p;changebest = 0;groupbestfit = group[j].fit;}elsechangebest = 1; //说明新生成的解还不如原来的好，要进行替换}void change_bestgroup()/*用最优解代替新种群中的最差的染色体*/{//精英保存策略，保证了群体质量不被退化//即替代后，最优的有两份。int i, j;double fit = group[0].fit;j = 0;//最差染色体的位置if (changebest){for (i = 1; i < 10; i++){if (group[i].fit < fit){fit = group[i].fit;j = i;}}for (i = 0; i < citynum + 1; i++){group[j].city[i] = groupbest[i];}calculation(); //计算}}void select()/*选择--复制*/{int i, j, temp[10][11], k;double t;srand((unsigned)time(NULL));for (i = 0; i < 10; i++)//选10条染色体出来复制，赌轮{t = rand() % 10000 * 1.0 / 10000;for (j = 0; j < 10; j++){if (t < group[j].sum_p ) {for (k = 0; k < citynum + 1; k++)temp[i][k] = group[j].city[k];break;}}}//拷贝新种群for (i = 0; i < 10; i++)for (j = 0; j < citynum + 1; j++){group[i].city[j] = temp[i][j];}calculation();savebest();change_bestgroup();}void crossover()/*交叉*/{int point1, point2; //交叉点1，交叉点2int temp, i, j, k, temp2[2][10], temp3[2][10], num, write;srand((unsigned)time(NULL));point1 = rand() % 10;point2 = rand() % 10;if (point1 > point2) /*保证point1小于point2*/{temp = point1;point1 = point2;point2 = temp;}//交换，每2条交换if (point1 != point2){for (j = 1; j < 10; j = j + 2){memset(temp3, -1, sizeof(temp3)); //初始化内存空间memset(temp2, -1, sizeof(temp2));k = 0;for (i = point1; i <= point2; i++){temp2[0][k] = group[j].city[i]; //temp2[0]存放 第1条染色体的交换片段Btemp2[1][k] = group[j - 1].city[i];//temp3[0存放] 第0条染色体的交换片段A//标记数字已经存在temp3[0][temp2[0][k]] = 1; temp3[1][temp2[1][k]] = 1;k++;group[j].city[i] = -1; // 将要交换的片段的城市位置都标为-1group[j - 1].city[i] = -1;}num = point2 - point1 + 1; //交换了多少个基因//消重/*第0条染色体的消重*/for (k = 0; k < point1; k++) {if (temp3[0][group[j - 1].city[k]] == 1)group[j - 1].city[k] = -1;elsetemp3[0][group[j - 1].city[k]] = 1;}for (k = point2 + 1; k < citynum; k++){if (temp3[0][group[j - 1].city[k]] == 1)group[j - 1].city[k] = -1;elsetemp3[0][group[j - 1].city[k]] = 1;}/*第1条染色体的消重*/for (k = 0; k < point1; k++){if (temp3[1][group[j].city[k]] == 1)group[j].city[k] = -1;elsetemp3[1][group[j].city[k]] = 1;}for (k = point2 + 1; k < citynum; k++){if (temp3[1][group[j].city[k]] == 1)group[j].city[k] = -1;elsetemp3[1][group[j].city[k]] = 1;}//第0条染色体的“将城市往前集合”并且“紧随交换片段”的操作write = 0;for (i = 0; i < 10; i++){while (write < 10 && group[j - 1].city[write] == -1){write++; //遇到-1的位置就+1。}if (write < 10){temp = group[j - 1].city[i];group[j - 1].city[i] = group[j - 1].city[write];group[j - 1].city[write] = temp; write++;}else{write = 0;for (k = i; k < 10; k++){group[j - 1].city[k] = temp2[0][write++];if (write == num)break;}break;}}//第1条染色体的“将城市往前集合”并且“紧随交换片段”的操作write = 0; for (i = 0; i < 10; i++){while (write < 10 && group[j].city[write] == -1){write++;}if (write < 10){temp = group[j].city[i];group[j].city[i] = group[j].city[write];group[j].city[write] = temp;write++;}else{write = 0;for (k = i; k < 10; k++){group[j].city[k] = temp2[1][write++];if (write == num)break;}break;}}// 第0条染色体的补全k = 0;for (i = 0; i < citynum; i++){if (group[j - 1].city[i] == -1){while (temp3[0][k] == 1 && k < 10){k++;}group[j - 1].city[i] = k++;}}//第1条染色体的补全k = 0;for (i = 0; i < citynum; i++){if (group[j].city[i] == -1){while (temp3[1][k] == 1 && k < 10){k++;}group[j].city[i] = k;k++;}}group[j].city[10] = group[j].city[0];group[j - 1].city[10] = group[j - 1].city[0];}//end of jcalculation();savebest();change_bestgroup();}//end of if (!)}void mutation()/*变异*/{int t1, t2, temp, t, s = 3;srand((unsigned)time(NULL));t = rand() % 10; //0~9随机数if (t > 2) //变异率为7/10{//挑1个不同的变异，只交换一位t1 = rand() % 10; //种群,挑一条染色体，第n条染色体t2 = rand() % 10;//这一条染色体里的变换位置//t2的位置和9-t2的位置调换temp = group[t1].city[t2];group[t1].city[t2] = group[t1].city[9 - t2];group[t1].city[9 - t2] = temp;group[t1].city[10] = group[t1].city[0];}calculation();savebest();change_bestgroup();}
七.个人理解及总结
Q：为什么变异率设置到0.7高？
A：个人理解，因为我们迭代次数低，且种群只有10条染色体，因此，设置到0.7，可以比较好地丰富染色体多样性。如果有条件，大家可以尝试一下设置多一点迭代次数，然后减少变异率，以达到效果。
总结：我个人认为比较重要的还是一开始的编码环节，就是我们要怎么样将遗传算法的东西与TSP问题中的参数进行联系呢，这也是值得思考的地方。遗传算法可以修改的地方很多，不同的变异率、交叉率、迭代次数、初始种群数甚至算法都会影响这程序的结果。我这份代码其实算不上最好，有更多更好更简洁的代码可以借鉴（其实py，matlab也很香，还有好看的图，可惜我不会[呲牙]）。
不足之处：初始种群设为10还好，大家可以设多几条染色体，20、30甚至50都是可以的。待完善之处其实就是大家的“迭代次数、交叉率、变异率”，找到你认为所适合的参数，肯定有更优的修改，欢迎大家在评论区讨论噢。
终于肝完啦！喜欢这篇文章的朋友记得点个赞噢！
-----------------------------------------
附上30个城市的结果，
迭代次数：10万
交叉率：100%
变异率：0.3
参考：
/studylyn/p/5097238.html
/p/64472762
如果觉得《（c++ 遗传算法解决TSP问题）不是吧 这就是遗传算法吗？爱了爱了》对你有帮助，请点赞、收藏，并留下你的观点哦！
