遗传算法（Genetic Algorithm, GA）起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。
模拟物竞天择的生物进化过程，通过维护一个潜在解的群体执行了多方向的搜索，并支持这些方向上的信息构成和交换。是以面为单位的搜索，比以点为单位的搜索，更能发现全局最优解。（在遗传算法中，有很多袋鼠，它们降落到喜玛拉雅山脉的任意地方。这些袋鼠并不知道它们的任务是寻找珠穆朗玛峰。但每过几年，就在一些海拔高度较低的地方射杀一些袋鼠，并希望存活下来的袋鼠是多产的，在它们所处的地方生儿育女。）（或者换个说法。从前，有一大群袋鼠，它们被莫名其妙的零散地遗弃于喜马拉雅山脉。于是只好在那里艰苦的生活。海拔低的地方弥漫着一种无色无味的毒气，海拔越高毒气越稀薄。可是可怜的袋鼠们对此全然不觉，还是习惯于活蹦乱跳。于是，不断有袋鼠死于海拔较低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有机会生儿育女。就这样经过许多年，这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上，可是在所有的袋鼠中，只有聚拢到珠穆朗玛峰的袋鼠被带回了美丽的澳洲。）
? ? ? ? 为此引入遗传算法来解决最优化问题：下面在x∈[?3,3],y∈[?3,3] 范围里的最大值为例子来详细讲解遗传算法的每一步。
? ? ? ? ?案例的函数定义如下：
遗传算法的实现过程实际上就像自然界的进化过程那样。首先寻找一种对问题潜在解进行“数字化”编码的方案。（建立表现型和基因型的映射关系）然后用随机数初始化一个种群（那么第一批袋鼠就被随意地分散在山脉上），种群里面的个体就是这些数字化的编码。接下来，通过适当的解码过程之后（得到袋鼠的位置坐标），用适应性函数对每一个基因个体作一次适应度评估（袋鼠爬得越高，越是受我们的喜爱，所以适应度相应越高）。用选择函数按照某种规定择优选择（我们要每隔一段时间，在山上射杀一些所在海拔较低的袋鼠，以保证袋鼠总体数目持平。）。让个体基因变异（让袋鼠随机地跳一跳）。然后产生子代（希望存活下来的袋鼠是多产的，并在那里生儿育女）。遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何去“找”最优解。（你不必去指导袋鼠向那边跳，跳多远。）而只要简单的“否定”一些表现不好的个体就行了。（把那些总是爱走下坡路的袋鼠射杀，这就是遗传算法的精粹！）
遗传算法中每一条染色体，对应着遗传算法的一个解决方案，一般我们用适应性函数（fitness function）来衡量这个解决方案的优劣。所以从一个基因组到其解的适应度形成一个映射。遗传算法的实现过程实际上就像自然界的进化过程那样。
下面我们用袋鼠跳中的步骤一一对应解释，以方便大家理解：
1.首先寻找一种对问题潜在解进行“数字化”编码的方案。（建立表现型和基因型的映射关系）
2.随机初始化一个种群（那么第一批袋鼠就被随意地分散在山脉上），种群里面的个体就是这些数字化的编码
3.接下来，通过适当的解码过程之后（得到袋鼠的位置坐标）
4.用适应性函数对每一个基因个体作一次适应度评估（袋鼠爬得越高当然就越好，所以适应度相应越高）
5.用选择函数按照某种规定择优选择（每隔一段时间，射杀一些所在海拔较低的袋鼠，以保证袋鼠总体数目持平）
让个体基因变异（让袋鼠随机地跳一跳）
6.然后产生子代（希望存活下来的袋鼠是多产的，并在那里生儿育女）
由此我们可以得出遗传算法的一般步骤：?
1.随机产生种群
2.根据策略判断个体的适应度，是否符合优化准则，若符合，输出最佳个体及其最优解，结束。否则，进行下一步
3.依据适应度选择父母，适应度高的个体被选中的概率高，适应度低的个体被淘汰
4.用父母的染色体按照一定的方法进行交叉，生成子代
5.对子代染色体进行变异
由交叉和变异产生新一代种群，返回步骤2，直到最优解产生
? ? ? ? 第一步：随机产生种群
? ? ? ? 第二步：解码
? ? ? ? 解码的目的是将上述生成的个体的二进制编码表示通过一个映射，映射到x,y∈[?3,3]这个范围（要根据实际问题的约束范围调整），首先先将x , y x,yx,y的取值范围用一个变量表示：
为将二进制个体映射到指定范围，首先先将二进制数按权展开，将二进制数转化为十进制数，然后将转换后的实数压缩到[0,1]之间的一个小数，通过以上这些步骤所有二进制串表示都可以转换为[0,1]之间的小数，现在只需要将[0,1] 区间内的数映射到我们要的区间即可。假设区间[0,1]内的数称为num，转换在python语言中可以写成：
以下为解码过程的python代码：
DNA_SIZE=24（一个实数DNA长度），两个实数x,y一共用48位二进制编码，同时将x和y编码到同一个48位的二进制串里，每一个变量用24位表示，奇数24列为x的编码表示，偶数24列为y的编码表示。
? ? ? ? 第三步：适应度计算
我们已经得到了一个种群，现在要根据适者生存规则把优秀的个体保存下来，同时淘汰掉那些不适应环境的个体。现在摆在我们面前的问题是如何评价一个个体对环境的适应度？在我们的求最大值的问题中可以直接用可能解（个体）对应的函数的函数值的大小来评估，这样可能解对应的函数值越大越有可能被保留下来，以求解上面定义的函数F的最大值为例，python代码如下：
?pred是将可能解带入函数F中得到的预测值，因为后面的选择过程需要根据个体适应度确定每个个体被保留下来的概率，而概率不能是负值，所以减去预测中的最小值把适应度值的最小区间提升到从0开始，但是如果适应度为0，其对应的概率也为0，表示该个体不可能在选择中保留下来，这不符合算法思想，遗传算法不绝对否定谁也不绝对肯定谁，所以最后加上了一个很小的正数。
有了求最大值的适应度函数求最小值适应度函数也就容易了，python代码如下:
根据适者生存规则在求最小值问题上，函数值越小的可能解对应的适应度应该越大，同时适应度也不能为负值，先将适应度减去最大预测值，将适应度可能取值区间压缩为[np.min(pred）?np.max(pred),0]，然后添加个负号将适应度变为正数，同理为了不出现0，最后在加上一个很小的正数。?
? ? ? ? 第四步：选择
有了评估的适应度函数，下面可以根据适者生存法则将优秀者保留下来了。选择则是根据新个体的适应度进行，但同时不意味着完全以适应度高低为导向（选择top k个适应度最高的个体，容易陷入局部最优解），因为单纯选择适应度高的个体将可能导致算法快速收敛到局部最优解而非全局最优解，我们称之为早熟。作为折中，遗传算法依据原则：适应度越高，被选择的机会越高，而适应度低的，被选择的机会就低。 在python中可以写做：
np.random.choice()函数的参数p描述了从np.arange(POP_SIZE)里选择每一个元素的概率，概率越高约有可能被选中，最后返回被选中的个体即可。?
? ? ? ? 第五步：交叉、变异
通过选择得到了当前看来“还不错的基因”，但是这并不是最好的基因，我们需要通过繁殖后代（包含有交叉+变异过程）来产生比当前更好的基因，但是繁殖后代并不能保证每个后代个体的基因都比上一代优秀，这时需要继续通过选择过程来让试应环境的个体保留下来，从而完成进化，不断迭代上面这个过程种群中的个体就会一步一步地进化。
具体地繁殖后代过程包括交叉和变异两步。交叉是指每一个个体是由父亲和母亲两个个体繁殖产生，子代个体的DNA（二进制串）获得了一半父亲的DNA，一半母亲的DNA，但是这里的一半并不是真正的一半，这个位置叫做交配点，是随机产生的，可以是染色体的任意位置。通过交叉子代获得了一半来自父亲一半来自母亲的DNA，但是子代自身可能发生变异，使得其DNA即不来自父亲，也不来自母亲，在某个位置上发生随机改变，通常就是改变DNA的一个二进制位（0变到1，或者1变到0）。
交叉和变异不是必然发生，而是有一定概率发生。先考虑交叉，最坏情况，交叉产生的子代的DNA都比父代要差（这样算法有可能朝着优化的反方向进行，不收敛），如果交叉是有一定概率不发生，那么就能保证子代有一部分基因和当前这一代基因水平一样；而变异本质上是让算法跳出局部最优解，如果变异时常发生，或发生概率太大，那么算法到了最优解时还会不稳定。交叉概率，范围一般是0.6~1，突变常数（又称为变异概率），通常是0.1或者更小。
