大自然有种神奇的力量,它能够将优良的基因保留下来,从而进化出更加强大、更加适合生存的基因。遗传算法便基于达尔文的进化论,模拟了自然选择,物竞天择、适者生存,通过N代的遗传、变异、交叉、复制,进化出问题的最优解。遗传算法看似神奇,但实现思路却较为简单。本文先跟大家介绍遗传算法的基本思想,然后用遗传算法来解决一个实际问题,最后给出遗传算法的代码实现和解析。废话不多说,现在就开始吧~
遗传算法
在开始之前,我们先来了解下遗传算法中的几个概念。
概念1:基因和染色体
在遗传算法中,我们首先需要将要解决的问题映射成一个数学问题,也就是所谓的“数学建模”,那么这个问题的一个可行解即被称为一条“染色体”。一个可行解一般由多个元素构成,那么这每一个元素就被称为染色体上的一个“基因”。
比如说,对于如下函数而言,[1,2,3]、[1,3,2]、[3,2,1]均是这个函数的可行解(代进去成立即为可行解),那么这些可行解在遗传算法中均被称为染色体。
3x+4y+5z<100
这些可行解一共有三个元素构成,那么在遗传算法中,每个元素就被称为组成染色体的一个基因。
概念2:适应度函数
在自然界中,似乎存在着一个上帝,它能够选择出每一代中比较优良的个体,而淘汰一些环境适应度较差的个人。那么在遗传算法中,如何衡量染色体的优劣呢?这就是由适应度函数完成的。适应度函数在遗传算法中扮演者这个“上帝”的角色。
遗传算法在运行的过程中会进行N次迭代,每次迭代都会生成若干条染色体。适应度函数会给本次迭代中生成的所有染色体打个分,来评判这些染色体的适应度,然后将适应度较低的染色体淘汰掉,只保留适应度较高的染色体,从而经过若干次迭代后染色体的质量将越来越优良。
概念3:交叉
遗传算法每一次迭代都会生成N条染色体,在遗传算法中,这每一次迭代就被称为一次“进化”。那么,每次进化新生成的染色体是如何而来的呢?——答案就是“交叉”,你可以把它理解为交配。
交叉的过程需要从上一代的染色体中寻找两条染色体,一条是爸爸,一条是妈妈。然后将这两条染色体的某一个位置切断,并拼接在一起,从而生成一条新的染色体。这条新染色体上即包含了一定数量的爸爸的基因,也包含了一定数量的妈妈的基因。
那么&