深入理解遗传算法(三)
欢迎点击「算法与编程之美」↑关注我们！
本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。
为更好理解本文，强烈建议优先阅读：
问题描述
首先来看一个线性方程组的求解问题。
已知N元一次方程y = w1x1 + w2x2 + w3x3 + w4x4 + w5x5 + w6x6
其中给定 x1, …, x6的数据如下:
x1 | x2 | x3 | x4 | x5 | x6 | y |
|---|---|---|---|---|---|---|
4 | -2 | 7 | 5 | 11 | 1 | 44.1 |
将列表中的x1, …, x6代入到上述方程得到
y’ = 4w1 - 2w2 + 7w3 + 5w4 + 11w5 + w6
试求出一组w1,w2, …, w6使得y’的值尽可能的接近于y.
如何淘汰
假设现在有六组w值如下表所示并且给出了对应的y’的计算值，如何从这六组中选择最优的三组，即淘汰剩余三组？
w1 | w2 | w3 | w4 | w5 | w6 | y’ |
|---|---|---|---|---|---|---|
2.4 | 0.7 | 8 | -2 | 5 | 1.1 | 110.3 |
-0.4 | 2.7 | 5 | -1 | 7 | 0.1 | 100.1 |
-1 | 2 | 2 | -3 | 2 | 0.9 | 13.9 |
4 | 7 | 12 | 6.1 | 1.4 | -4 | 127.9 |
3.1 | 4 | 0 | 2.4 | 4.8 | 0 | 69.2 |
-2 | 3 | -7 | 6 | 3 | 3 | 3 |
y’ = 4w1 - 2w2 + 7w3 + 5w4 + 11w5 + w6
= 110.3
根据上述公式，可快速计算每一组w值的y’。
给出一个适应性函数定义如下：
则F(c)的值越大，|y’ - y|的差距越小，表明该组值的效果越好。
w1 | w2 | w3 | w4 | w5 | w6 | y’ | F(c) |
|---|---|---|---|---|---|---|---|
2.4 | 0.7 | 8 | -2 | 5 | 1.1 | 110.3 | 0.015 |
-0.4 | 2.7 | 5 | -1 | 7 | 0.1 | 100.1 | 0.018 |
-1 | 2 | 2 | -3 | 2 | 0.9 | 13.9 | 0.033 |
4 | 7 | 12 | 6.1 | 1.4 | -4 | 127.9 | 0.012 |
3.1 | 4 | 0 | 2.4 | 4.8 | 0 | 69.2 | 0.0398 |
-2 | 3 | -7 | 6 | 3 | 3 | 3 | 0.024 |
根据F(c)的大小，将保留最大的三组值，剩下的三组即为淘汰。
如何交叉
有了以上的三组存活的值，接下来将通过交叉方式生成三组新的值。
w1 | w2 | w3 | w4 | w5 | w6 | |
|---|---|---|---|---|---|---|
A | -1 | 2 | 2 | -3 | 2 | 0.9 |
B | 3.1 | 4 | 0 | 2.4 | 4.8 | 0 |
C | -2 | 3 | -7 | 6 | 3 | 3 |
具体的交叉方式是：
- A的前三位和B的后三位;
w1 | w2 | w3 | w4 | w5 | w6 | |
|---|---|---|---|---|---|---|
A | -1 | 2 | 2 | -3 | 2 | 0.9 |
B | 3.1 | 4 | 0 | 2.4 | 4.8 | 0 |
C | -2 | 3 | -7 | 6 | 3 | 3 |
- B的前三位和C的后三位;
w1 | w2 | w3 | w4 | w5 | w6 | |
|---|---|---|---|---|---|---|
A | -1 | 2 | 2 | -3 | 2 | 0.9 |
B | 3.1 | 4 | 0 | 2.4 | 4.8 | 0 |
C | -2 | 3 | -7 | 6 | 3 | 3 |
- C的前三位和A的后三位;
w1 | w2 | w3 | w4 | w5 | w6 | |
|---|---|---|---|---|---|---|
A | -1 | 2 | 2 | -3 | 2 | 0.9 |
B | 3.1 | 4 | 0 | 2.4 | 4.8 | 0 |
C | -2 | 3 | -7 | 6 | 3 | 3 |
通过上述的交叉方式，将可以得到新的三组解。
如何变异
接下来将对上述新产生的三组解进行变异，具体的变异方法为将第五位的值变为一半，最后得到的新值为：
w1 | w2 | w3 | w4 | w5 | w6 |
|---|---|---|---|---|---|
-1 | 2 | 2 | -3 | 2 | 0.9 |
3.1 | 4 | 0 | 2.4 | 4.8 | 0 |
-2 | 3 | -7 | 6 | 3 | 3 |
-1 | 2 | 2 | 2.4 | 2.4 | 0 |
3.1 | 4 | 0 | 6 | 1.5 | 3 |
-2 | 3 | -7 | -3 | 1 | 0.9 |
底下的三组解是通过交叉、变异产生的新的三组解。此处没有选择所有的值都变异，而继续保持上一代中的三个值不变，原因在于担心完全变异后的结果也许比上一代更差。
结语
遗传算法的核心就是定义一个适应性函数，从一组解中淘汰一部分，然后从存活下来的解中，实施交叉、变异操作生成新的解，然后再不断的重复此过程，直到满足某个阀值时结束。
拓展阅读：
where2go 团队
微信号：算法与编程之美
温馨提示：点击页面右下角“写留言”发表评论，期待您的参与！期待您的转发！