欢迎点击「算法与编程之美」↑关注我们!
本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。
为更好理解本文,强烈建议优先阅读:
问题描述
首先来看一个线性方程组的求解问题。
已知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 |
具体的交叉方式是:
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 | |
---|---|---|---|---|---|---|
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 | |
---|---|---|---|---|---|---|
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 团队
微信号:算法与编程之美
温馨提示:点击页面右下角“写留言”发表评论,期待您的参与!期待您的转发!