深入理解遗传算法(一)

欢迎点击「算法与编程之美」↑关注我们！

本文首发于微信公众号："算法与编程之美"，欢迎关注，及时了解更多此系列文章。

首先来看一个线性方程组的求解问题。已知n元一次方程

其中给定 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的值如下：

w1

w2

w3

w4

w5

w6

2.4

0.7

8

-2

5

1.1

计算 y’ = 4w1 - 2w2 + 7w3 + 5w4 + 11w5 + w6

= 110.3

y = 44.1

定义|y’ - y| 为预测值y’与真实值y之间的误差error，可以得到上面的误差为：

error = |y’ - y| = |110.3 - 44.1| = 66.2

接下来，再观察另外一组随机给定的w值。

w1

w2

w3

w4

w5

w6

-0.4

2.7

5

-1

7

0.1

计算 y’ = 4w1 - 2w2 + 7w3 + 5w4 + 11w5 + w6

= 100.1

error = | y’ - y| = |100.1 - 44.1| = 56

方案二的误差56比方案一的误差66.2要小，因此方案二的w取值更好。

通过方案一和方案二的示例可以看出，给定任意的一组w值，期望y’的值越接近y则这组值越好，这就是评估w值的好坏的方法。

方案一和二都是通过随机的给定一组w值，接着计算y’的值，最后通过评估|y’ -y|的差值来判断当前选取的w值的好坏。如果按照这种方式继续进行下去，则不能保证每一次随机的取值都能更好的缩小误差，也许上一次选取的w值更好。

要想求的一组w值，使得y'无限接近于y，没有办法一次性就可以得到想要的结果，通常情况都需要经过多次的迭代，总是希望每一次迭代后的结果比上一次要好，即|y'-y|的值越来越小。这样经过多次迭代就可以慢慢的逼近y，进而求得最优的值。

如何达到上述目的，下一讲将介绍遗传算法的不一样的思路，敬请持续关注。