干货 | 嘿！你和遗传算法的距离也许只差这一文(附C++代码和详细代码注释)
遗传算法
概念
遗传算法（Genetic Algorithm，简称GA）起源于对生物系统所进行的计算机模拟研究，是一种随机全局搜索优化方法，它模拟了自然选择和遗传中发生的复制、交叉(crossover)和变异(mutation)等现象，从任一初始种群（Population）出发，通过随机选择、交叉和变异操作，产生一群更适合环境的个体，使群体进化到搜索空间中越来越好的区域，这样一代一代不断繁衍进化，最后收敛到一群最适应环境的个体（Individual），从而求得问题的优质解。
常用术语
- 染色体(Chromosome)：又可称为基因型个体(individuals)，一定数量的个体组成了群体(population)，群体中个体的数量叫做群体大?。╬opulation size）。
- 位串(Bit String)：个体的表示形式。对应于遗传学中的染色体。
- 基因(Gene)：染色体中的元素，用于表示个体的特征。
- 特征值( Feature)：在用串表示整数时，基因的特征值与二进制数的权一致；
- 适应度(Fitness)：各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。这个函数通?；岜挥美醇扑愀鎏逶谌禾逯斜皇褂玫母怕省?/li>
- 基因型(Genotype)：或称遗传型，是指基因组定义遗传特征和表现。对于于GA中的位串。
- 表现型(Phenotype)：生物体的基因型在特定环境下的表现特征。对应于GA中的位串解码后的参数。
基本遗传算法
SGA是一种群体型操作，该操作以群体中的所有个体为对象，只使用基本遗传算子(Genetic Operator)：选择算子(Selection Operator)、交叉算子(Crossover Operator)和变异算子(Mutation Operator)，是其它一些遗传算法的基础。
SGA表示方法
个体的编码方法、个体适应度评价函数、初始种群、种群大小、选择算子、交叉算子、变异算子、遗传运算终止条件
GA步骤
- 染色体编码
编码：解空间中的解在遗传算法中的表示形式
常见的编码方法有二进制编码、格雷码编码、 浮点数编码、各参数级联编码、多参数交叉编码等。
解码：遗传算法染色体向问题解的转换 - 初始种群的生成
随机生成M个个体作为初始化群体P0 - 适应度值评估检测
适应度函数表明个体或解的优劣性。
适应度尺度变换：指算法迭代的不同阶段，能够通过适当改变个体的适应度大小，进而避免群体间适应度相当而造成的竞争减弱，导致种群收敛于局部最优解
尺度变换常用方法有线性尺度变换、乘幂尺度变换以及指数尺度变换 - 选择遗传算子
选择操作从旧群体中以一定概率选择优良个体组成新的种群，以繁殖得到下一代个体 - 交叉遗传算子
交叉操作是指从种群中随机选择两个个体，通过两个染色体的交换组合，把父串的优秀特征遗传给子串，从而产生新的优秀个体
常用的交叉算子有单点交叉、双点交叉或多点交叉、均匀交叉、算术交叉等 - 变异遗传算子
为了防止遗传算法在优化过程中陷入局部最优解，在搜索过程中，需要对个体进行变异
在实际应用中，主要采用单点变异，也叫位变异，即只需要对基因序列中某一个位进行变异 - 终止判断条件
GA流程图
