深入理解遗传算法(二)

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

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

深入理解遗传算法(一)

强烈建议在开始本文阅读之前，请确保已经完成上述文章阅读。

物竞天择，适者生存

”物竞天择，适者生存。“这是达尔文关于生物进化论的著名观点，指的就是一个种群经过不断的发展，逐步淘汰不适应外部环境，而能够得以生存留下的都是能够适应环境的。

举一个例子来深入说明生物进化论里面的关键概念，假设某个种群初始只有六个个体（称为第0代即G0），经过一轮淘汰后只剩下三个(此时为第1代即G1)，如果达尔文进化论只是一味的淘汰个体，那么在经过第二轮后，这个种群就会消失。

因此想要维持种群的持续长久发展，在淘汰个体的同时也需要繁衍产生新的个体，保持新的种群数量至少能够维持不变。即第1代淘汰三个个体的同时，还需要再产生三个新的个体。

如何产生新的三个个体？一定是G0时代生存下来的三个个体，通过基因的交叉、变异，使得一方面能够遗传先人的优秀品质，另外也能够通过变异获得新的能力。

G0 → G1 → G2 → …

从G0到G1到G2一直持续，每一代都会留下三个最优秀的个体，然后通过这三个个体彼此间的交叉、变异产生新的三个个体，这六个人就构成了新的一代种群。

应用生物进化论

接下来将生物进化论的这种思想应用到上一讲的N元一次方程的求解问题。

第0代G0

随机初始化该方程组的六组w的值，计算|y’-y|的差值，从而可以选择三组效果最好的值保留，淘汰另外三组较差的。

第1代G1

将G0代这三组最好的w值，经过交叉、变异生成另外三组w值。G0代生存下来的三组w值，加上交叉、变异后生成的三组，一共六组构成了G1代。

…

今后的每一代都通过上述方式进行，从而可以保证后面每一代的结果，都优于上一代。

重要思考

每一代中如何淘汰？

因为每一代都有六组w值，每一组w值都可以计算y’，进而可以计算|y’-y|的值，由于差值越大，则效果越差。因此只保留每一代的排名前三的值，后面三组则直接淘汰。

每一代中如何交叉?

假设下述两组w值在竞争中存活，

则交叉是指可以通过选择第一组的前三个，第二组的后三个即-1, 2, 2, 2.4, 4.8, 0 这六个数组构成新的一组。

如何实现变异？

一行中倒数第二个变异为其原来的1/2即2.4.

因此，在上一代竞争中存活下来的两组w值，如下：

经过交叉、变异后就会得到一组新的值：

本讲主要介绍达尔文生物进化论的基本思想，并将其应用到上一讲的方程组求解案例，下一将将深入介绍其具体实现。

拓展阅读：

深入理解遗传算法(一)

从1到100求和学算法思维（一）

从1到100求和学算法思维（二）

从1到100求和学算法思维（三）

从1到100求和学算法思维（四）

从1到100求和学算法思维（五）

从1到100求和学算法思维（六）

where2go 团队

微信号：算法与编程之美

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