遗传算法

模仿自然界生物进化机制发展起来的随机全局搜索和优化方法 其本质是一种高效、并行、全局搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最佳解。

基因型(genotype) 表现型(phenotype) 进化(evolution) 适应度(fitness) 选择(selection) 复制(reproduction) 交叉(crossover) 变异(mutation) 编码(coding) 解码(decoding) 个体（individual） 种群（population）

• 寻路问题

• 8数码问题

• 囚犯困境

• 动作控制

• 找圆心问题

• TSP问题

• 生产调度问题

• 人工生命模拟等

1. 爬山法（最速上升爬山法）：
从搜索空间中随机产生邻近的点，从中选择对应解最优的个体，替换原来的个体，不断重复上述过程。
因为爬山法只对“邻近”的点作比较，所以目光比较“短浅”，常常只能收敛到离开初始位置比较近的局部最优解上面。对于存在很多局部最优点的问题，通过一个简单的迭代找出全局最优解的机会非常渺茫。（在爬山法中，袋鼠最有希望到达最靠近它出发点的山顶，但不能保证该山顶是最高的，或者是一个非常高的山峰。因为一路上它只顾上坡，没有下坡。）

2. 模拟退火：
这个方法来自金属热加工过程的启发。在金属热加工过程中，当金属的温度超过它的熔点（Melting Point）时，原子就会激烈地随机运动。
与所有的其它的物理系统相类似，原子的这种运动趋向于寻找其能量的极小状态。在这个能量的变迁过程中，开始时，温度非常高， 使得原子具有很高的能量。随着温度不断降低，金属逐渐冷却，金属中的原子的能量就越来越小，最后达到所有可能的最低点。
利用模拟退火的时候，让算法从较大的跳跃开始，使到它有足够的“能量”逃离可能“路过”的局部最优解而不至于限制在其中，当它停在全局最优解附近的时候，逐渐的减小跳跃量，以便使其“落脚 ”到全局最优解上。
（在模拟退火中，袋鼠喝醉了，而且随机地大跳跃了很长时间。运气好的话，它从一个山峰跳过山谷，到了另外一个更高的山峰上。但最后，它渐渐清醒了并朝着它所在的峰顶跳去。）

3. 遗传算法：
模拟物竞天择的生物进化过程，通过维护一个潜在解的群体执行了多方向的搜索，并支持这些方向上的信息构成和交换。
是以面为单位的搜索，比以点为单位的搜索，更能发现全局最优解。（在遗传算法中，有很多袋鼠，它们降落到喜玛拉雅山脉的任意地方。这些袋鼠并不知道它们的任务是寻找珠穆朗玛峰。但每过几年，就在一些海拔高度较低的地方射杀一些袋鼠，并希望存活下来的袋鼠是多产的，在它们所处的地方生儿育女。）
（或者换个说法。从前，有一大群袋鼠，它们被莫名其妙的零散地遗弃于喜马拉雅山脉。于是只好在那里艰苦的生活。海拔低的地方弥漫着一种无色无味的毒气，海拔越高毒气越稀薄。可是可怜的袋鼠们对此全然不觉，还是习惯于活蹦乱跳。于是，不断有袋鼠死于海拔较低的地方，而越是在海拔高的袋鼠越是能活得更久，也越有机会生儿育女。就这样经过许多年，这些袋鼠们竟然都不自觉地聚拢到了一个个的山峰上，可是在所有的袋鼠中，只有聚拢到珠穆朗玛峰的袋鼠被带回了美丽的澳洲。😆）
遗传算法的实现过程
遗传算法的实现过程实际上就像自然界的进化过程那样。
首先寻找一种对问题潜在解进行“数字化”编码的方案。（建立表现型和基因型的映射关系）
然后用随机数初始化一个种群（那么第一批袋鼠就被随意地分散在山脉上），种群里面的个体就是这些数字化的编码。
接下来，通过适当的解码过程之后（得到袋鼠的位置坐标），用适应性函数对每一个基因个体作一次适应度评估（袋鼠爬得越高，越是受我们的喜爱，所以适应度相应越高）。
用选择函数按照某种规定择优选择（我们要每隔一段时间，在山上射杀一些所在海拔较低的袋鼠，以保证袋鼠总体数目持平。）。
让个体基因变异（让袋鼠随机地跳一跳）。然后产生子代（希望存活下来的袋鼠是多产的，并在那里生儿育女）。
遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何去“找”最优解。（你不必去指导袋鼠向那边跳，跳多远。）而只要简单的“否定”一些表现不好的个体就行了。（把那些总是爱走下坡路的袋鼠射杀，这就是遗传算法的精粹！）
遗传算法的一般步骤：
▶️开始循环直至找到满意的解。
1.评估每条染色体所对应个体的适应度。
2.遵照适应度越高，选择概率越大的原则，从种群中选择两个个体作为父方和母方。
3.抽取父母双方的染色体，进行交叉，产生子代。
4.对子代的染色体进行变异。
5.重复2，3，4步骤，直到新种群的产生。
⏹结束循环。
详细地剖析遗传算法过程的每一个细节。
编制袋鼠的染色体----基因的编码方式
01编码
受到人类染色体结构的启发，我们可以设想一下，假设目前只有“0”，“1”两种碱基，我们也用一条链条把他们有序的串连在一起
因为每一个单位都能表现出 1 bit的信息量，所以一条足够长的染色体就能为我们勾勒出一个个体的所有特征。这就是二进制编码法，染色体大致如下：

010010011011011110111110

01编码的明显缺点：当个体特征比较复杂的时候，需要大量的编码才能精确地描述，相应的解码过程将过分繁复
改进：浮点数编码
浮点数编码下，一条染色体可以被表示为

1.2 –3.3 – 2.0 –5.4 – 2.7 – 4.3

如何利用这两种编码方式来为袋鼠的染色体编码呢？
编码的目的：建立表现型到基因型的映射关系。
表现型一般就被理解为个体的特征。
比如人的基因型是46条染色体所描述的却能解码成一个眼，耳，口，鼻等特征各不相同的活生生的人。
所以我们要想为“袋鼠”的染色体编码，我们必须先来考虑“袋鼠”的“个体特征”是什么。
袋鼠的特征很多，比如性别，身长，体重。
但具体在解决这个问题的情况下，我们应该进一步思考：无论这只袋鼠是长短，肥瘦，黑白只要它在低海拔就会被射杀，同时也没有规定身长的袋鼠能跳得远一些，身短的袋鼠跳得近一些。当然它爱吃什么就更不相关了。
我们由始至终都只关心一件事情：袋鼠在哪里。因为只要我们知道袋鼠在那里，我们就能做两件必须去做的事情：
1. 通过查阅喜玛拉雅山脉的地图来得知袋鼠所在的海拔高度（通过自变量求适应函数的值。）以判断我们有没必要把它射杀。
2. 知道袋鼠跳一跳（交叉和变异）后去到哪个新位置。
 
如果我们一时无法准确的判断哪些“个体特征”是必要的，哪些是非必要的，我们常常可以用到这样一种思维方式：比如你认为袋鼠的爱吃什么东西非常必要，那么你就想一想，有两只袋鼠，它们其它的个体特征完全同等的情况下，一只长得黑，另外一只长得不是那么黑。你会马上发现，这不会对它们的命运有丝毫的影响，它们应该有同等的概率被射杀！只因它们处于同一个地方。（值得一提的是，如果你的基因编码设计中包含了袋鼠黑不黑的信息，这其实不会影响到袋鼠的进化的过程，而那只攀到珠穆朗玛峰的袋鼠黑与白什么的也完全是随机的，但是它所在的位置却是非常确定的。）
必须把具体问题抽象成数学模型，突出主要矛盾，舍弃次要矛盾。只有这样才能简洁而有效的解决问题。
既然确定了袋鼠的位置作为个体特征，具体来说位置就是横坐标。那么接下来，我们就要建立表现型到基因型的映射关系。就是说如何用编码来表现出袋鼠所在的横坐标。
由于横坐标是一个实数，所以说透了我们就是要对这个实数编码。
回顾我们上面所介绍的两种编码方式
• 对于二进制编码方式来说，编码会比较复杂
• 对于浮点数编码方式来说，则会比较简洁。
 
下面介绍如何建立二进制编码到一个实数的映射。
明显地，一定长度的二进制编码序列，只能表示一定精度的浮点数。譬如我们要求解精确到六位小数，由于区间长度为2 – (-1) = 3 ,为了保证精度要求，至少把区间[-1,2]分为等份→所以编码的二进制串至少需要22位（）。
把一个二进制串（b0,b1,....bn)转化为区间里面对应的实数值通过下面两个步骤。
3. 将一个二进制串代表的二进制数转化为10进制数
4. 对应区间内的实数

• 生物间的搏斗

• 生物与客观环境的。