1700507711
数据科学家养成手册 [:1700503587]
1700507712
11.7.3 遗传算法
1700507713
1700507714
不管是低维函数还是高维函数，都可能出现“多峰”的情况，就是在函数图像上出现很多“褶皱”。这种情况下不容易用一般的梯度下降法求解极值问题。因为任意一个初始点都会收敛到最近的一个极小值的位置，而这个极小值有很大概率不是要求的最优解，甚至距离最优解的位置非常远（如图11-19和图11-20所示）。
1700507715
1700507716
1700507717
1700507718
1700507719
1700507720
图11-19 图像 图11-20 图像 遗传算法作为梯度下降法的一种增强形式，可以以比较高的效率解决高维空间上的极小值查找问题，以及离散数学中的NP问题(6)。它的思路就是：在这个候选解出现的高维平面上撒下大量的“种子”，比较这些“种子”的评价函数值，淘汰较小的“种子”；通过基因交叉的方式产生下一代“种子”，比较各代“种子”的评价函数值，再淘汰较小的“种子”；如此反复，直到连续几代出现的“种子”所具备的最大评价函数值不再增加，即可考虑判断收敛。这同样是迭代法的应用。
1700507721
1700507722
在解决这种有限定义域内高维多峰函数的极值问题时，使用遗传算法就比较合适，前提是这个多峰函数在任何一个维度内都是连续的。
1700507723
1700507724
1700507725
以函数z=xsin2x+ycos2y为例，。
1700507726
1700507727
第1步：基因编码
1700507728
1700507729
这个环节以满足当前场景的精度要求为宜。如果精度为10-5，那么用一个20位的二进制数字作为基因编码即可。因为221=2097152，其能够允许的精度已经满足了-10.00000到10.00000之间20000001个最小单位的需求。
1700507730
1700507731
设计一个映射函数
1700507732
1700507733
1700507734
1700507735
1700507736
1700507737
x是21位的二进制编码，例如。F(x)是二进制编码到十进制实数的映射函数。
1700507738
1700507739
第2步：设计初始群体
1700507740
1700507741
1700507742
设计一定量的群体，每个个体都用一个二进制编码来表示，使用程序循环生成N个21位二进制编码，当发现时就进行舍弃并重新生成，直到生成N个满足要求的21位二进制编码。
1700507743
1700507744
第3步：遴选与生育
1700507745
1700507746
首先，比较当前N个H(x)的值。然后，将其从大到小排序，选择最大的前M个对象作为可以生育后代的备选。最后，在这M个备选对象中进行两两之间的基因重组（如图11-21所示）。
1700507747
1700507748
1700507749
1700507750
1700507751
图11-21 基因重组
1700507752
1700507753
1700507754
根据排列组合，每一代会产生个下一代对象。在两两组合的过程中，可能会在这21位中的第1位后到第21位前的任意位置断开然后重组，这个位置是随机的。
1700507755
1700507756
以2个基因组为例：
1700507757
1700507758
101010101010101010101
1700507759
1700507760
000011110000111100001