遗传算法是由美国密歇根大学的 Holland教授创立于20世纪六七十年代，受达尔文“进化论”思想的启发而设计实现。遗传算法不是通过暴力搜索解的方法，而是通过模拟种群的基因交叉和突变，经过种群一代一代的适者生存的方式寻找问题优解的方法，这在解决组合优化时解空间组合爆炸中应用广泛。

一、如何理解遗传算法

我们可以这样形象地理解遗传算法，假设我们现在需要找到一个最能抵抗寒冷的人类，那么遗传算法是这样设计的：首次创造一个较寒冷生活环境(问题的限制条件)，在这个环境中投入一批各种各样的人类(初始种群)，让人类在这种寒冷的环境中生存。人类一代一代的生活，周围环境也设置得越来越寒冷，同时人类在产生下一代的时候也伴随着基因的交叉和变异(遗传算法的迭代过程)。正是随着基因交叉和突变，慢慢的产生了极少数可以抵抗寒冷的基因，慢慢的拥有可以抵抗寒冷基因的人更加适应环境而得以发展，慢慢的能够适应寒冷的人类生存了下来，其它不适应环境的被淘汰了，这个过程就是解空间的慢慢趋于优的过程，遗传算法就是模拟这一过程 。
遗传算法很好理解，但是需要说明一下，遗传算法是一种寻优的方案，一种算法思想，所以遗传算法针对具体的问题需要具体的设计。

二、遗传算法

遗传算法按照其进化的思想，将算法的实施分为四个部分，编码、选择、交叉和变异。

2.1编码

编码问题是遗传算法首先要解决的问题，这是一个从基因向表现型的表达过程，是模仿基因表达的过程。如双眼皮\单眼皮由某一段基因控制，那么就说这段基因表达到了眼皮这个表现型上。编码就是建立基因与表现型的映射，编码形式主要有三种：二进制编码、整数编码和浮点数编码，三种编码各有特点。

二进制编码采用0/1数字串代表基因，如果011011中每两个0/1数字串代表一个表现型，那么表现型就是1,2,3，如果用来解决TSP问题的话，就代表选择1->2->3这条路径。

二进制编码使用方便，能够轻松处理基因交叉和变异过程，但是，二进制编码容易造成编码过剩和在交叉与变异过程中产生不稳定的新数据导致搜索结果难以收敛。

整数编码的基因和表现型一致，在TSP问题中，基因串1,2,3的表现型就是1,2,3，就代表了1->2->3这条路径。因此，整数编码很方便处理TSP问题，但是，基因交叉的过程中会带来路线中站点重复的问题。浮点数编码适应于浮点数问题，涉及较少。

2.2选择

选择的作用是将适应环境能力强的个体挑选出来，对于算法来说就是将更加满足优化条件的解挑选出来，并且在下一代中保留更多优解，这就是对搜索的启发。适应环境能力就对应着优化条件，越优的条件越强的适应能力。对于TSP问题的优化条件就是希望路径最短，即：

arg Min(distance(X))，对应arg Max(1/distance(X))

将适应函数取为：f(X)=1/distance(X)，X代表一条路径。对于适应度函数，当f(X)越大，适应度越大，distance(X)也越小，这是我们所期望的。

在选择的过程中希望，适应环境能力强能够更多的选择，常常会采用轮盘赌的方式来按照体个的适应能力，按比例的选择下一代的个体。轮盘赌的方式需要求出一下概率矩阵：

轮盘赌的实施过程为：当要进行选择时，随机的产生一个概率，假如概率为0.4，那么这个处于个体1和个体2的累计概率之间，那么个体2将被选中。按照轮盘赌的方式可以按照个体的适应度的比例挑选下一代。

轮盘赌中，适应度高，对应的选择的面积大，被选中的概率高。

2.3交叉和变异

交叉和变异是模拟生物基因行为的方法，是产生新物种的途径，对应到算法中就是跳出局部最优向其它解空间搜索的方式。交叉是指两条染色体的部分片段交叉互换，变异是指染色体中的基因发生了变化，改变了原来的结构。

如果采用二进制编码的基因发生交叉的话，就是如下表中的两端基因的加粗部分的基因串交换，同时，两端基因的表现型也将发生变化。

如果采用整数编码的基因发生交叉的话，还需要考虑是否需要通过映射去重。

同样，如果采用二进制编码的基因发生变异的话，基因串中的某一个0变成1，或者1变成0，其表现型也将发生变化。

三、解决什么问题

在实际的生活中常常会遇到NP难问题，尤其是组合优化问题，随着组合的增加解的空间也指数的增加。因为无法在可接受的时间内搜索得到问题最优解，这时就需要采用启发式搜索优解的方法，在可接受的时间范围内得到较优解甚至最优解。遗传算法可以派上用场了，可以解决组合优化问题，如：排课问题、生产计划规划、旅行商问题等。

本文的版权归算法卡农所有，抄袭等侵权行为必究！

喜欢我的话，加个关注吧，有更加精彩的内容等着大家。