人工智能课程实验报告，仅供个人学习记录用 部分内容转自遗传算法入门详解

遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究，是一种随机全局搜索优化方法，它模拟了自然选择和遗传中发生的复制、交叉(crossover)和变异(mutation)等现象，从任一初始种群（Population）出发，通过随机选择、交叉和变异操作，产生一群更适合环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代不断繁衍进化，最后收敛到一群最适应环境的个体（Individual），从而求得问题的优质解。

基本遗传算法(也称标准遗传算法或简单遗传算法，Simple Genetic Algorithm，简称SGA)是一种群体型操作，该操作以群体中的所有个体为对象，只使用基本遗传算子(Genetic Operator)：选择算子(Selection Operator)、交叉算子(Crossover Operator)和变异算子(Mutation Operator)，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。选择、交叉和变异是遗传算法的3个主要操作算子，它们构成了遗传操作，使遗传算法具有了其它方法没有的特点。

解空间中的解在遗传算法中的表示形式。从问题的解(solution)到基因型的映射称为编码，即把一个问题的可行解从其解空间转换到遗传算法的搜索空间的转换方法。遗传算法在进行搜索之前先将解空间的解表示成遗传算法的基因型串(也就是染色体)结构数据，这些串结构数据的不同组合就构成了不同的点。

常见的编码方法有二进制编码、格雷码编码、 浮点数编码、各参数级联编码、多参数交叉编码等。

遗传算法染色体向问题解的转换。假设某一个体的编码，则对应的解码公式为

设置最大进化代数 T T T ，群体大小 M M M ，交叉概率 P c P_c Pc​ ，变异概率 P m P_m Pm​，随机生成 M M M 个个体作为初始化群体 P 0 P_0 P0​ 。

适应度函数表明个体或解的优劣性。对于不同的问题，适应度函数的定义方式不同。根据具体问题，计算群体P(t)中各个个体的适应度。

适应度尺度变换：一般来讲，是指算法迭代的不同阶段，能够通过适当改变个体的适应度大小，进而避免群体间适应度相当而造成的竞争减弱，导致种群收敛于局部最优解。

尺度变换选用的经典方法：线性尺度变换、乘幂尺度变换以及指数尺度变换。

遗传算法使用以下三种遗传算子：

选择操作从旧群体中以一定概率选择优良个体组成新的种群，以繁殖得到下一代个体。 个体被选中的概率跟适应度值有关，个体适应度值越高，被选中的概率越大。

交叉操作是指从种群中随机选择两个个体，通过两个染色体的交换组合，把父串的优秀特征遗传给子串，从而产生新的优秀个体。

为了防止遗传算法在优化过程中陷入局部最优解，在搜索过程中，需要对个体进行变异，在实际应用中，主要采用单点变异，也叫位变异，即只需要对基因序列中某一个位进行变异，以二进制编码为例，即0变为1，而1变为0。

若 t≤T ，则 t←t+1 ，转到步骤2；否则以进化过程中所得到的具有最大适应度的个体作为最好的解输出，终止运算。

遗传算法全过程图：

具体细节讲解在代码注释当中

一开始没有任何个体，需要有最初始的一代解作为迭代起点。采取随机生成的方法生成0~cityNum-1的排列，作为初始群体。

适应度表示该个体的适应程度（存活下去的概率）那么适应度越大，越容易存活下去，而我们的目标是最小化tsp距离，可以得到适应度与tsp距离成反比。所以我们先计算出每个个体的tsp距离（dis），然后适应度=1/dis

最后答案为每一代中的最优解的最优解，所以需要设计函数选择出每代的最优解。

选择适应度，随机选出存活下去的父代，保留这些父代。选择完以后再让他们进行杂交和突变操作从而生成新的子代。

以一定的概率发生交叉互换，不满足发生交叉概率的直接跳过。