遗传算法可视化项目（4）：遗传算法

昨天讲了一下关于距离的计算，没有看昨天或者之前的文章，点一下历史消息或者这里：

遗传算法可视化项目（1）：概述

遗传算法可视化项目（2）：获取信息

遗传算法可视化项目（3）：创建图的数据结构

遗传算法可视化项目（插曲）：关于距离的计算

今天首先介绍遗传算法（genetic algorithm，GA）。

遗传算法是一种进化算法，其基本原理是模仿自然界中的生物“物竞天择，适者生存”的进化法则，把问题参数编码为染色体，再利用迭代的方式进行选择、交叉、变异等运算法则来交换种群中染色体的信息，最终生成符合优化目标的染色体。

在遗传算法中，染色体对应的是数据或者数组，通常是由一维的串结构数据来表示，串上各个位置对应基因的的取值。基因组成的串就是染色体，或者称为基因型个体。一定数量的个体组成了种群，种群中个体数目的大小称为种群大小，也称为种群规模，而各个个体对环境的适应程度称为适应度。

标准遗传算法的步骤如下：

（1）编码：遗传算法在搜索解空间之前需要将解数据表示成遗传空间的基因型串结构数据，这些串结构数据的不同组合构成了不同的染色体。

（2）初始化：即生成初始种群。具体的做法是随机生成N个初始的染色体（解空间的解），每一个染色体其实就相当于一个个体，N个个体构成了一个初始种群。遗传算法以这N个个体作为初始值开始进化。

（3）适应度评估：适应度表明个体或者解的优劣性。不同的问题，定义适应度函数的方式也不同。比如如果是求一个函数的最大值，那么一般某个解对应的函数值越大，那么这个个体（解）的适应度也就越高。

（4）选择：选择的目的是为了从当前种群中选出优良的个体，使它们有机会成为父代繁殖下一代子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或者多个后代的概率大。这体现了达尔文的适者生存原则。

（5）交叉：交叉操作是遗传算法中最主要的遗传操作。通过交叉可以得到新一代个体，新个体组合了其父代的个体特征。交叉体现了信息交换的思想。

（6）变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率（通常是比较小的概率，这与自然界一致，自然界的变异都是小概率事件）随机改变染色体中某个基因的值。

有的时候除了选择选择、交叉、变异这三种操作之外，我们还会针对具体的问题加入其它的操作（比如逆转之类），但是选择、交叉、变异是所有的遗传算法都共同的拥有的遗传操作。

其次介绍一下TSP问题。TSP（traveling salesman problem，旅行商问题）是典型的NP完全问题，即其最坏情况下的时间复杂度随着问题规模的增大按指数方式增长，到目前为止还没有找到一个多项式时间的有效算法。TSP问题可以描述为：已知n个城市之间的相互距离，某一旅行商从某一个城市出发，访问每个城市一次且仅一次，最后回到出发的城市，如何安排才能使其所走的路线最短。换言之，就是寻找一条遍历n个城市的路径，或者说搜索自然子集X={1,2,...,n}（X的元素表示对n个城市的编号）的一个排列P(X)={V1,V2,....,Vn},使得Td=∑d(Vi,Vi+1)+d(Vn,V1)取最小值，其中d(Vi,Vi+1)表示城市Vi到Vi+1的距离。TSP问题不仅仅是旅行商问题，其他许多NP完全问题也可以归结为TSP问题，如邮路问题，装配线上的螺母问题和产品的生产安排问题等等，也使得TSP问题的求解具有更加广泛的实际意义。

　　再来说针对TSP问题使用遗传算法的步骤。

　　（1）编码问题：由于这是一个离散型的问题，我们采用整数编码的方式，用1~n来表示n个城市，1~n的任意一个排列就构成了问题的一个解。可以知道，对于n个城市的TSP问题，一共有n!种不同的路线。

　　（2）种群初始化：对于N个个体的种群，随机给出N个问题的解（相当于是染色体）作为初始种群。这里具体采用的方法是：1,2,...,n作为第一个个体，然后2,3,...,n分别与1交换位置得到n-1个解，从2开始，3,4,...,n分别与2交换位置得到n-2个解，依次类推。（如果这样还不够初始种群的数量，可以再考虑n,n-1,...,1这个序列，然后再按照相同的方法生成等等）

　　（3）适应度函数：设一个解遍历初始行走的总距离为D，则适应度fitness=1/D，即总距离越高，适应度越低，总距离越低（解越好），适应度越高。

　　（4）选择操作：个体被选中的概率与适应度成正比，适应度越高，个体被选中的概率越大。这里仍然采用轮盘赌法。

　 （5）交叉操作：交叉操作是遗传算法最重要的操作，是产生新个体的主要来源，直接关系到算法的全局寻优能力，这里采用部分映射交叉。比如对于n=10的情况，对于两个路径：

1 2 4 5 6 3 9 10 8 7

3 9 7 6 8 10 5 1 2 4

随机产生两个[1,10]之间的随机数r1，r2，代表选择交叉的位置，比如r1=2，r2=4，将第一个个体r1到r2之间的基因（即城市序号）与第二个个体r1到r2之间的基因交换，交换之后变为：

1 9 7 6 6 3 9 10 8 7

3 2 4 5 8 10 5 1 2 4

这个时候会发现可能交叉过来的基因与原来其他位置上的基因有重复，容易直到，第一个个体重复基因的数目与第二个个体重复基因的数目是相同的（这里都是3个），只需要把第一个个体重复的基因与第二个个体重复的基因做交换，即可以消除冲突。消除冲突之后的解如下：

1 9 7 6 5 3 2 10 8 4

3 2 4 5 8 10 6 1 9 7

（6）变异操作：变异操作采取对于一个染色体（即个体）随机选取两个基因进行交换的策略。比如对于染色体：

2 4 6 10 3 1 9 7 8 5

随机选取了两个位置p1=3，p2=8，交换这两个位置的基因，得到新的染色体为：

2 4 7 10 3 1 9 6 8 5

（7）进化逆转操作：这个是标准的遗传算法没有的，是我们为了加速进化而加入的一个操作。这里的进化是指逆转操作具有单向性，即只有逆转之后个体变得更优才会执行逆转操作，否则逆转无效。具体的方法是，随机产生[1,10]（这里仍然以10个城市为例）之间的两个随机数r1和r2（其实也是允许相同的，只是r1，r2相同之后，逆转自然无效,设置交叉变异都是无效的，但是这不会经常发生）,然后将r1和r2之间的基因进行反向排序。比如对于染色体：

1 3 4 2 10 9 8 7 6 5

r1=3，r2=5，它们之间的基因反向排列之后得到的染色体如下：

1 3 10 2 4 9 8 7 6 5

说了这么多，接下来就是代码实现了，还是打开之前VS2017创建的项目：在解决方案资源管理器右击头文件→添加→新建项，然后在弹出的窗口点击头文件，取个名字（我这里就叫GA.h了），最后确定就行，首先是包含头文件，宏定义（最大进化代数，种群数目，交叉概率，变异概率大佬可以随便改，但小白菜鸟建议还是用我给的数），定义全局变量和函数声明，代码如下：

接下来就是每一个函数的实现，首先是init函数，实现代码如下：

然后是距离函数和最小值函数，代码如下：

接着是路径总长度函数，代码如下：

目前为止，进入选择，交叉，变异三大基本操作的实现了，首先是选择操作，代码如下：

然后就是最复杂的代码最多（多到我连图都不能一次截完

）的交叉操作，代码如下：

然后是变异操作，代码如下：

目前为止三大基本操作结束了，还差一个逆转操作，逆转操作代码如下：

最后还差一步计算并把结果传给昨天创建的图，代码如下：