遗传算法如何模拟大自然的进化?

遗传算法 ( GA , Genetic Algorithm ) ,也称进化算法 。 遗传算法是受达尔文的进化论的启发,借鉴生物进化过程而提出的一种启发式搜索算法。因此在介绍遗传算法前有必要简单的介绍生物进化知识。见下表:

从上表中,我们可以看到遗传算法是通过对编码串类似自然进化的遗传操作,来完成新个体的产生。当新个体产生后,我们就可以根据个体的适应值,遵循自然选择法则,适者生存来选取优秀个体再次进化,直到进化完成。

其中,遗传算法的流程图如下:

举例讲解:

根据上述流程图我们来一步一步理解下:

1. 确定实际问题参数:

首先,我们假如问题是找出下式子的最大值:

很显然,在该范围内存在x=0时,f(x)=1最大。如下图

至此,我们已经确定了问题的参数,即在[-1,1]上找出f(x)的最大值。

2. 对参数进行编码

采用二进制编码,将某个变量值代表的个体表示为一个{0,1}二进制串。串长取决于求解的精度。如果确定求解精度到3位小数,由于区间长度为1-(-1)=2,必须将区间[-1,1]分为2×10^3等份。因为

所以编码的二进制串长至少需要11位。

二进制串转化为十进制:

例如 s=<01000110000>

x’=560;得x=-0.453

则 <00000000000>与<11111111111>表示区间的两个端点-1和1。

至此,我们对该问题进行了二进制串编码。

3. 初始化种群

一个二进制串叫做一个个体(individual)。有若干个个体组成个体的集合,称为种群(population),种群中含有的个体的数量叫做种群的规模(population size)。

随机生成初始种群:

S1=<11100011101>

S2=<01010001111>

S3=<00110011011>

S4=<10111100110>

S5=<10011011011>

S6=<01110110000>

S7=<11110011001>

S8=<00001001011>

4. 评价群体

要评价群体,就得必须有一个评价标准,遗传算法是根据个体的适应值进行评价个体是否进入下一代的。很显然这里的适应值函数就是我们的目标函数f(x),直接将目标函数作为适应值函数。有了适应值函数,可以对初始种群进行评估。

S1(0) = <11100011101>, f(s1)=f(x1)=0.393

S2 (0) =<01010001111> , f(s2)=f(x2)=0.870

S3 (0) =<00110011011> , f(s3)=f(x3)=0.642

S4 (0) =<10111100110> , f(s4)=f(x4)=0.774

S5 (0) =<10011011011> , f(s5)=f(x5)=0.954

S6 (0) =<01110110000> , f(s6)=f(x6)=0.994

S7 (0) =<11110011001> , f(s7)=f(x7)=0.189

S8 (0) =<00001001011> , f(s8)=f(x8)=0.141

5. 判断是否满足停止条件

在进化算法中,常见的进化停止算法有三种:

(1). 设置进化代数,当种群进化N代之后,进化停止,选出适应值最高的个体,该个体即是最优解。

(2). 设置评价次数,当种群进化过程中的评价次数达到M后,进化结束,输出适应值最高个体。

(3). 种群收敛,如果种群收敛,则输出最优个体,进化结束。

当然,如果没达到进化停止的条件,则对种群进行遗传操作,来产生新个体。

6 遗传操作

遗传操作一般分为三种:交叉,变异,复制

交叉:两个个体随机以某个点为交叉点进行交叉点后的基因互换。如下图,两条染色体将第四个基因后面的基因互换:

变异:在某个基因上随机选出一个变异位置,将该位置上的基因进行随机互换。如下图选择第一个基因将0变异成为1:

复制:复制就是将优秀的个体,原封不动的复制到下一代种群中,以保存优秀基因。

这里出现了一个问题:选择那些基因进行遗传操作呢?

和自然进化一样在选择的时候一般按照一个原则:适应值高的存活的概率大,即选中进行遗传操作的概率大。一般有以下几个方法进行选择:

(1). 轮盘赌选择法 (Roulette Wheel Selection):利用各个个体适应度所占比例的大小决定其子孙保留的可能性。

(2). 锦标赛选择法(tournament

selection): 每次随机选取几个个体之中适应度最高的一个个体遗传到下一代群体中,重复M次.

(3). 随机遍历选择法: 像轮盘赌一样计算选择概率,然后根据指针等距离地选择个体。

这样,适应值高的个体存活的概率大,进行遗传操作的概率高,产生后代的机会就大,符合自然进化的选择方法。

在进行遗传操作后,在保证种群大小不变的情况下进行淘汰适应值低的个体。然后进行下一代进化。直至进化结束,产生出最优个体为止。

免责声明:本文系网络转载。版权归原作者所有。如涉及版权,请联系删除!

原文发布于微信公众号 - 智能算法(AI_Algorithm)

原文发表时间:2017-03-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

利用向量积(叉积)计算三角形的面积和多边形的面积

利用向量积(叉积)计算三角形的面积和多边形的面积: 向量的数量积和向量积: (1)  向量的数量积 ? (1)  向量的向量积 两个向量a和b的叉积(向量积)可...

4379
来自专栏封碎

当今世界最为经典的十大算法 博客分类: 经典文章转载 算法数据结构网络应用数据挖掘J#

本文转载自July CSDN博客:http://blog.csdn.net/v_JULY_v/archive/2011/03/07/6228235.aspx

2232
来自专栏小樱的经验随笔

【机器学习笔记之一】深入浅出学习K-Means算法

摘要:在数据挖掘中,K-Means算法是一种 cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法。 ...

3019
来自专栏Vamei实验室

纸上谈兵: 数学归纳法, 递归, 栈

数学归纳法 数学归纳法(mathematical induction)是一种数学证明方法,常用于证明命题(命题是对某个现象的描述)在自然数范围内成立。随着现代数...

2616
来自专栏数据魔术师

干货 | 遗传算法(Genetic Algorithm) (附代码及注释)

6526

组和分组卷积

考虑一个正方形。它是对称的吗?它是如何对称的?它有多少对称性?它有什么样的对称性?

31710
来自专栏小小挖掘机

DQN三大改进(三)-Dueling Network

论文地址:https://arxiv.org/pdf/1511.06581.pdf 代码地址:https://github.com/princewen/tens...

2.3K6
来自专栏一名叫大蕉的程序员

大数据计数原理1+0=1这你都不会算(六)No.57

照例甩一波链接。 大数据计数原理1+0=1这你都不会算(一)No.47 <- HashSet 大数据计数原理1+0=1这你都不会算(二)No.5...

2096
来自专栏生信技能树

比较不同的对单细胞转录组数据聚类的方法

背景介绍 聚类之前必须要对表达矩阵进行normalization,而且要去除一些批次效应等外部因素。通过对表达矩阵的聚类,可以把细胞群体分成不同的状态,解释为什...

88212
来自专栏智能算法

遗传算法如何模拟大自然的进化?

遗传算法 ( GA , Genetic Algorithm ) ,也称进化算法 。 遗传算法是受达尔文的进化论的启发,借鉴生物进化过程而提出的一种启发式搜索算法...

3817

扫码关注云+社区

领取腾讯云代金券