深入理解遗传算法(三)

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

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

为更好理解本文,强烈建议优先阅读:

深入理解遗传算法(一)

深入理解遗传算法(二)

问题描述

首先来看一个线性方程组的求解问题。

已知N元一次方程y = w 1 x 1 + w 2 x 2 + w 3 x 3 + w 4 x 4 + w 5 x 5 + w 6 x 6

其中给定 x 1 , …, x 6 的数据如下:

x 1

x 2

x 3

x 4

x 5

x 6

y

4

-2

7

5

11

1

44.1

将列表中的x 1 , …, x 6 代入到上述方程得到

y’ = 4w 1 - 2w 2 + 7w 3 + 5w 4 + 11w 5 + w 6

试求出一组w 1 ,w 2 , …, w 6 使得y’的值尽可能的接近于y.

如何淘汰

假设现在有六组w值如下表所示并且给出了对应的y’的计算值,如何从这六组中选择最优的三组,即淘汰剩余三组?

w 1

w 2

w 3

w 4

w 5

w 6

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

1 - 2w 2 + 7w 3 + 5w 4 + 11w 5 + w 6

= 110.3

根据上述公式,可快速计算每一组w值的y’。

给出一个适应性函数定义如下:

则F(c)的值越大,|y’ - y|的差距越小,表明该组值的效果越好。

w 1

w 2

w 3

w 4

w 5

w 6

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)的大小,将保留最大的三组值,剩下的三组即为淘汰。

如何交叉

有了以上的三组存活的值,接下来将通过交叉方式生成三组新的值。

w 1

w 2

w 3

w 4

w 5

w 6

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

具体的交叉方式是:

  1. A的前三位和B的后三位;

w 1

w 2

w 3

w 4

w 5

w 6

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

  1. B的前三位和C的后三位;

w 1

w 2

w 3

w 4

w 5

w 6

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

  1. C的前三位和A的后三位;

w 1

w 2

w 3

w 4

w 5

w 6

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

通过上述的交叉方式,将可以得到新的三组解。

如何变异

接下来将对上述新产生的三组解进行变异,具体的变异方法为将第五位的值变为一半,最后得到的新值为:

w 1

w 2

w 3

w 4

w 5

w 6

-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

底下的三组解是通过交叉、变异产生的新的三组解。此处没有选择所有的值都变异,而继续保持上一代中的三个值不变,原因在于担心完全变异后的结果也许比上一代更差。

结语

遗传算法的核心就是定义一个适应性函数,从一组解中淘汰一部分,然后从存活下来的解中,实施交叉、变异操作生成新的解,然后再不断的重复此过程,直到满足某个阀值时结束。

拓展阅读:

深入理解遗传算法(一)

深入理解遗传算法(二)

从1到100求和学算法思维(一)

从1到100求和学算法思维(二)

从1到100求和学算法思维(三)

从1到100求和学算法思维(四)

从1到100求和学算法思维(五)

从1到100求和学算法思维(六)

where2go 团队

微信号:算法与编程之美

长按识别二维码关注我们!

温馨提示: 点击页面右下角 “写留言” 发表评论,期待您的参与!期待您的转发!

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章