当前位置:首页 > 舞蹈 > 【人工智能】深入浅出遗传算法、快速交付机器学习项目

【人工智能】深入浅出遗传算法、快速交付机器学习项目

关键词:   发布时间:2019-07-30 08:00:01

深入浅出遗传算法


来源:数学与人工智能  

           



经典算法研究系列


深入浅出遗传算法




1

初探遗传算法


Ok,先看维基百科对遗传算法所给的解释:

遗传算法是计算数学中用于解决最优化的搜索算法,是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传、突变、自然选择以及杂交等。


遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题,一定数量的候选解(称为个体)的抽象表示(称为染色体)的种群向更好的解进化。传统上,解用二进制表示(即0和1的串),但也可以用其他表示方法。进化从完全随机个体的种群开始,之后一代一代发生。在每一代中,整个种群的适应度被评价,从当前种群中随机地选择多个个体(基于它们的适应度),通过自然选择和突变产生新的生命种群,该种群在算法的下一次迭代中成为当前种群。


光看定义,可能思路并不清晰,咱们来几个清晰的图解、步骤、公式:

基本遗传算法的框图:



所以,遗传算法基本步骤是:

1)  初始化   t←0进化代数计数器;T是最大进化代数;随机生成M个个体作为初始群体    P(t);

2)  个体评价 计算P(t)中各个个体的适应度值;

3)  选择运算 将选择算子作用于群体;

4)  交叉运算 将交叉算子作用于群体;

5)  变异运算 将变异算子作用于群体,并通过以上运算得到下一代群体P(t + 1);

6)  终止条件判断  t≦T:t← t+1 转到步骤2;

        t>T:终止 输出解。 


好的,看下遗传算法的伪代码实现:

▲Procedures  GA:   伪代码


2

深入遗传算法


1、智能优化算法概述

智能优化算法又称现代启发式算法,是一种具有全局优化性能、通用性强且适合于并行处理的算法。

这种算法一般具有严密的理论依据,而不是单纯凭借专家经验,理论上可以在一定的时间内找到最优解或近似最优解。 

遗传算法属于智能优化算法之一。 


常用的智能优化算法有:

遗传算法 、模拟退火算法、禁忌搜索算法、粒子群算法、蚁群算法。

(本经典算法研究系列,日后将陆续阐述模拟退火算法、粒子群算法、蚁群算法。)


2、遗传算法概述

遗传算法是由美国的J. Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的。

借鉴生物界自然选择和自然遗传机制的随机化搜索算法。 

模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象。


在每次迭代中都保留一组候选解,并按某种指标从解群中选取较优的个体,利用遗传算子(选择、交叉和变异)对这些个

体进行组合,产生新一代的候选解群,重复此过程,直到满足某种收敛指标为止。 


基本遗传算法(Simple Genetic Algorithms,GA)又称简单遗传算法或标准遗传算法),是由Goldberg总结出的一种最基本的遗传算法,其遗传进化操作过程简单,容易理解,是其它一些遗传算法的雏形和基础。


3、基本遗传算法的组成

(1)编码(产生初始种群)

(2)适应度函数

(3)遗传算子(选择、交叉、变异)

(4)运行参数


接下来,咱们分门别类,分别阐述着基本遗传算法的五个组成部分:

1)编码

遗传算法(GA)通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。

正如研究生物遗传是从染色体着手,而染色体则是由基因排成的串。

基本遗传算法(SGA)使用二进制串进行编码。 


初始种群:基本遗传算法(SGA)采用随机方法生成若干个个体的集合,该集合称为初始种群。

初始种群中个体的数量称为种群规模。


2)适应度函数 

遗传算法对一个个体(解)的好坏用适应度函数值来评价,适应度函数值越大,解的质量越好。

适应度函数是遗传算法进化过程的驱动力,也是进行自然选择的唯一标准,

它的设计应结合求解问题本身的要求而定。 


3.1、选择算子

遗传算法使用选择运算对个体进行优胜劣汰操作。

适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体,被遗传到下一代群体中的概率小。

选择操作的任务就是从父代群体中选取一些个体,遗传到下一代群体。


基本遗传算法(SGA)中选择算子采用轮盘赌选择方法。


Ok,下面就来看下这个轮盘赌的例子,这个例子通俗易懂,对理解选择算子帮助很大。



轮盘赌选择方法
轮盘赌选择又称比例选择算子,其基本思想是:
各个个体被选中的概率与其适应度函数值大小成正比。

设群体大小为N,个体xi 的适应度为 f(xi),则个体xi的选择概率为:



轮盘赌选择法可用如下过程模拟来实现:

(1)在[0, 1]内产生一个均匀分布的随机数r。
(2)若r≤q1,则染色体x1被选中。
(3)若qk-1<r≤qk(2≤k≤N), 则染色体xk被选中。 
其中的qi称为染色体xi (i=1, 2, …, n)的积累概率, 其计算公式为:


积累概率实例: 


轮盘赌选择方法的实现步骤:
(1)计算群体中所有个体的适应度值;
(2)计算每个个体的选择概率;
(3)计算积累概率;
(4)采用模拟赌盘操作(即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配)
来确定各个个体是否遗传到下一代群体中。

例如,有染色体
s1= 13 (01101)
s2= 24 (11000) 
s3= 8   (01000)
s4= 19 (10011)

假定适应度为f(s)=s^2 ,则
f (s1) = f(13) = 13^2 = 169
f (s2) = f(24) = 24^2 = 576
f (s3) = f(8) = 8^2 = 64
f (s4) = f(19) = 19^2 = 361

染色体的选择概率为:


染色体的累计概率为:



根据上面的式子,可得到:



例如设从区间[0, 1]中产生4个随机数: 


   r1 = 0.450126,    r2 = 0.110347 

   r3 = 0.572496,    r4 = 0.98503 



3.2、交叉算子

交叉运算,是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因,
从而形成两个新的个体。

交叉运算是遗传算法区别于其他进化算法的重要特征,它在遗传算法中起关键作用,
是产生新个体的主要方法。
基本遗传算法(SGA)中交叉算子采用单点交叉算子。

单点交叉运算


3.3、变异算子 

变异运算,是指改变个体编码串中的某些基因值,从而形成新的个体。
变异运算是产生新个体的辅助方法,决定遗传算法的局部搜索能力,保持种群多样性。

交叉运算和变异运算的相互配合,共同完成对搜索空间的全局搜索和局部搜索。
基本遗传算法(SGA)中变异算子采用基本位变异算子。

基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。
对于二进制编码符号串所表示的个体,若需要进行变异操作的某一基因座上的原有基因值为0,
则将其变为1;反之,若原有基因值为1,则将其变为0 。

基本位变异算子的执行过程:


4)运行参数

(1)M  :种群规模 
(2)T  : 遗传运算的终止进化代数 
(3)Pc  :交叉概率 
(4)Pm :变异概率



3

浅出遗传算法


遗传算法的本质

遗传算法本质上是对染色体模式所进行的一系列运算,即通过选择算子将当前种群中的优良模式遗传
到下一代种群中,利用交叉算子进行模式重组,利用变异算子进行模式突变。
通过这些遗传操作,模式逐步向较好的方向进化,最终得到问题的最优解。

遗传算法的主要有以下八方面的应用:
(1)组合优化      (2)函数优化 (3)自动控制      (4)生产调度 
(5)图像处理      (6)机器学习 (7)人工生命      (8)数据挖掘



4

遗传算法的应用


遗传算法的应用举例、透析本质(这个例子简明、但很重要)

已知x为整数,利用遗传算法求解区间[0, 31]上的二次函数y=x2的最大值。


[分析]

原问题可转化为在区间[0, 31]中搜索能使 y 取最大值的点 a 的问题。
个体:[0, 31] 中的任意点x
适应度:函数值f(x)=x2 
解空间:区间[0, 31]

这样, 只要能给出个体x的适当染色体编码, 该问题就可以用遗传算法来解决。

[解]

(1) 设定种群规模,编码染色体,产生初始种群。
将种群规模设定为4;用5位二进制数编码染色体;取下列个体组成初始种群S1

s1= 13 (01101),  s2= 24 (11000)
s3= 8 (01000),    s4= 19 (10011) 

(2) 定义适应度函数, 取适应度函数
f (x)=x^2

(3) 计算各代种群中的各个体的适应度, 并对其染色体进行遗传操作,
直到适应度最高的个体,即31(11111)出现为止。

首先计算种群S1中各个体:
s1= 13(01101),    s2= 24(11000)
s3= 8(01000),      s4= 19(10011)
的适应度f (si), 容易求得:
f (s1) = f(13) = 13^2 = 169
f (s2) = f(24) = 24^2 = 576
f (s3) = f(8) = 8^2 = 64
f (s4) = f(19) = 19^2 = 361

再计算种群S1中各个体的选择概率:

由此可求得
P(s1) = P(13) = 0.14
P(s2) = P(24) = 0.49
P(s3) = P(8) = 0.06
P(s4) = P(19) = 0.31

再计算种群S1中各个体的积累概率:



选择-复制 

设从区间[0, 1]中产生4个随机数如下:
r1 = 0.450126,     r2 = 0.110347 
r3 = 0.572496,     r4 = 0.98503


于是,经复制得群体:
s1’ =11000(24),  s2’ =01101(13) 
s3’ =11000(24)(24被选中俩次),  s4’ =10011(19)



交叉

设交叉率pc=100%,即S1中的全体染色体都参加交叉运算。
设s1’与s2’配对,s3’与s4’配对。
s1’ =11000(24),  s2’ =01101(13)
s3’ =11000(24),  s4’ =10011(19)
分别交换后两位基因,得新染色体:
s1’’=11001(25),  s2’’=01100(12)
s3’’=11011(27),  s4’’=10000(16)


变异 

设变异率pm=0.001。
这样,群体S1中共有
5×4×0.001=0.02
位基因可以变异。
0.02位显然不足1位,所以本轮遗传操作不做变异。

于是,得到第二代种群S2:
s1=11001(25),   s2=01100(12)
s3=11011(27),   s4=10000(16)

第二代种群S2中各染色体的情况:



假设这一轮选择-复制操作中,种群S2中的4个染色体都被选中,则得到群体:
 s1’=11001(25),  s2’= 01100(12)
 s3’=11011(27),  s4’= 10000(16)

做交叉运算,让s1’与s2’,s3’与s4’ 分别交换后三位基因,得 
  s1’’=11100(28),    s2’’ = 01001(9)
  s3’’ =11000(24),   s4’’ = 10011(19)

这一轮仍然不会发生变异。
于是,得第三代种群S3:
 s1=11100(28),  s2=01001(9)
 s3=11000(24),  s4=10011(19)

第三代种群S3中各染色体的情况:

设这一轮的选择-复制结果为:

s1’=11100(28),   s2’=11100(28)

s3’=11000(24),   s4’=10011(19)


做交叉运算,让s1’与s4’,s2’与s3’ 分别交换后两位基因,得

  s1’’=11111(31),  s2’’=11100(28)

  s3’’=11000(24),  s4’’=10000(16)


这一轮仍然不会发生变异。


于是,得第四代种群S4: 

s1=11111(31)(出现最优解),  s2=11100(28)

s3=11000(24),  s4=10000(16)


显然,在这一代种群中已经出现了适应度最高的染色体s1=11111。


于是,遗传操作终止,将染色体(11111)作为最终结果输出。

然后,将染色体“11111”解码为表现型,即得所求的最优解:31。

将31代入函数y=x2中,即得原问题的解,即函数y=x2的最大值为961。 


所以,综合以上各代群的情况,如下:



快速交付机器学习项目:ML工程循环指南

原创:weakish   论智    



来源:Medium
编译:weakish


编者按:Insight Data Science AI负责人Emmanuel Ameisen和前百度硅谷人工智能实验室主管Adam Coates分享了快速交付机器学习项目的经验。

由于机器学习(ML)日益成为每个产业的重要组成部分,对机器学习工程师的需求增长迅猛。机器学习工程师结合机器学习技术与软件工程知识,为给定的应用寻求表现优异的模型,同时处理随之而来的实现的挑战——从创建训练基础设施到为部署模型做准备。虽然网上不断出现训练工程师创建ML模型并解决遇到的各种软件挑战的资源,而新ML团队最常遇到的一个障碍却是保持和传统软件工程同等水准的进度。

这一挑战最关键的原因是开发新ML模型的过程从一开始就是高度不确定的。毕竟,在最后的训练完成之前,很难知晓模型表现有多好,更别说大量的调参和采用不同的建模假定对模型表现有什么影响了。

多种职业人士面临类似的情况:软件和商业开发者,寻求产品-市场契合的初创企业,处于信息有限的演习之中的飞行员。每种职业人士采用一种常见框架以帮助团队在不确定的情况下高效作业:软件开发的敏捷原则,精益创业,美国空军的OODA循环。机器学习工程师可以遵循类似的框架,应对不确定性,迅速交付伟大的产品。


ML工程循环


本文将介绍机器学习的OODA循环:ML工程循环,其中ML工程师不断进行以下四个步骤:

  1. 分析

  2. 选型

  3. 实现

  4. 测量

从而快速、高效地发现最佳模型,并适应未知数据。此外,我们也为每个阶段提供了具体的窍门,并将介绍如何优化整个过程。

ML团队的成功常常意味着交付满足给定限制的表现优异的模型——例如,在满足内存占用、推理时间、公平性等限制的前提下,达到较高的预测精确度。表现是由和最终产品最相关的测度定义的,不管它是精确度,速度,还是输出的多样性。出于简单性,下文的表现测度我们选择了最小化“误差率”。

刚开始着手一个新项目时,你应该精确地定义成功标准,之后将其转换为模型测度。用产品术语来说,服务需要具备什么级别的表现才有用?例如,如果新闻平台向用户分别推荐5篇文章,其中需要多少篇用户相关的文章,我们又如何定义相关性?给定表现标准和现有数据,你可以创建的最简单的模型是什么?

ML工程循环的目的是提供一个开发过程中牢记的心智模型,简化决策过程,以集中精力处理下一个重要步骤。随着从业者经验的积累,这一过程变为从业者的第二本能,可以快速果断地在分析和实现间切换。话是这么说,不过,当不确定性增加时,即使是最有经验的工程师也会发现这一框架价值非凡——例如,模型出乎意料地没能满足需求,团队目标突然调整(例如,为了体现产品需求的变动,测试集做了改动),团队进程因缺乏目标而停滞。


开始


为了启动这一循环,你应该先从一个基本不涉及不确定性的最小实现开始。通常我们想要尽可能快地“得到一个数字”——创建一个足以评估表现并开始迭代的系统。这通常意味着:

  1. 开始设置训练、验证、测试集。

  2. 实现一个可以工作的简单模型

例如,如果我们需要创建一个树检测器以调查某一区域的树木,我们也许可以使用相关Kaggle竞赛中现成的数据作为训练集,并使用我们自行收集的一组目标区域的照片作为验证集和测试集。我们接着可以在原始像素上运行逻辑回归,或者在训练图像上运行预训练好的网络(比如ResNet)。这里的目标不是一下子完结这个项目,而是开启我们的迭代循环。下面是一些有助于你达成这一点的窍门:

窍门

关于良好的测试集:

  • 由于团队的目标是在测试集上取得较优表现,测试集实质上描述了团队的目标。因此,测试集应当反映产品或业务的需求。例如,如果你正创建一个基于自拍检测皮肤状况的应用,你可以在任意图像上训练,但需确保测试集包含光照和画质不佳的图像,因为一些自拍很可能出现这类情况。

  • 改变测试集意味着调整团队的目标,所以最好及早固定测试集,仅当项目、产品、业务目标发生变动时才改动测试集。

  • 尽量使测试集和验证集足够大,这样才能得到足够精确的表现测度,从而很好地区分不同的模型。如果测试集太小,你最终将基于噪声数据得出结论。

  • 类似地,你应该在实际情况允许的情况下,尽可能确保测试集和验证集的标签和标注足够精确。错误标注的测试集差不多等于没有正确说明的产品需求。

  • 了解人类或现存/竞争系统在测试集上的表现很有帮助。这给出了最优误差率的界限,也就是你可能取得的最佳表现。

  • 对许多任务而言,达到和人类相当的水平经常是一个很好的长期目标。在任何情况下,最终目标都是使测试表现尽可能接近我们猜测的最佳表现。

关于验证集和训练集:

  • 验证集是测试表现的代理,可用于调整超参数。因此,验证集的分布应当和测试集一致。不过,理想情形下,验证集和测试集应该来自不同组别的用户/输入,这可以避免数据泄露。确保这一点的一个好办法是首先积累大量样本,然后打乱顺序,之后将其分割为验证集和测试集。

  • 如果在你的设想中,产品数据会有很多噪声,确保训练集考虑到了噪声问题(比如使用数据增强或数据劣化)。你不能期望完全在锐利图像上训练的模型能很好地推广到模糊图像。

实现了初始原型之后,你应该在训练集、验证集、测试集上测试它的表现。这标志着你度过了循环的第一个(退化的)周期。评估测试表现和有用的产品所需表现之间的差距。现在到了开启迭代的时刻了!


分析


识别表现瓶颈

在实践中,可能有许多交叉的问题导致了当前的结果,但你的目标是首先找出最明显的问题,这样你就可以快速解决它。不要拘泥于试图完全理解所有缺陷——转而理解最关键的因素,因为在你改进模型之后,许多小问题会改变,甚至消失。

我们下面列出了一些常见的诊断。选择从哪方面开始多多少少是门手艺,但随着ML工程循环的进行,你将逐渐获得尝试哪个的直觉。

对所有分析而言,一个很好的起点是查看训练集、验证集、测试集上的表现。我们建议你写代码在每次试验后自动进行这一比较,养成习惯。平均来说,我们有:训练集误差 <= 验证集误差 <= 测试集误差 (如果三个数据集中的数据遵循同一分布)。基于上一次试验的训练、验证、测试误差率,你可以快速地获知哪个因素是当前最大的限制。例如,如果训练误差和验证误差存在一定差距,那么训练误差是提升表现的瓶颈。

诊断

如果训练集误差是当前的限制因素,那么可能的问题有:

  1. 优化算法(例如,深度神经网络的梯度下降)没有调整准确。看看学习曲线,损失有没有下降。检查下是否能够过拟合一个小很多的数据集(例如,在单个minibatch甚至单个样本上训练)。你可以可视化神经元反应的直方图,看看它们有没有饱和(这可能会导致梯度消失)。

  2. 训练集可能有标注错误或毁坏的数据。在传给训练算法前,手工检查一些训练样本。

  3. 模型可能过小、过于简单。例如,如果你在高度非线性的问题上应用线性回归,你的模型无法很好地拟合数据。我们称为高偏差欠拟合

如果验证集误差是当前的限制因素,那么可能的问题有:

  1. 模型可能过大、过于复杂,或者正则化不够。我们称为高方差过拟合

  2. 训练数据不足。

  3. 训练数据的分布和验证集、测试集分布不同。

  4. 模型的超参数设得不好。如果你搜索最佳超参数(比如特征集、正则项),那可能是搜索方法难以找到较好的选择。

  5. 模型编码的“归纳先验”和模型匹配不好。例如,如果数据集用一个线性函数表示更自然,使用最近邻方法也许很难推广,除非你有海量训练数据。

如果测试集误差是当前的限制因素,这常常是因为验证集太小,或者团队在多次尝试的过程中过拟合验证集了。

不管是上面哪种情况,你都可以通过手工检查一组模型出错的随机样本,理解模型的缺陷(一般情况下你不应该在测试集上这么做,以避免在测试样本上“训练”系统)。

  1. 通过可视化数据尝试识别常见类型的误差。然后检查样本,记录每种类型的误差出现的频率。分类问题可以看下混淆矩阵,找出表现最差的分类。接着你就可以集中精力解决导致最多错误的那类误差。

  2. 有些样本可能错误标注了,或者有多种合理的标签。

  3. 有些样本可能比其他样本更难判断,或者缺乏做出判断需要的上下文。在若干种误差同样常见的时候,将一些样本标记为“很难”也许有助于你将精力花在容易得到改进的地方。类似地,将一些样本标记为“很容易”也许有助于你找出系统中细小的错误,导致模型在容易的情形上犯错。这有点像在数据的不同子集上估计“最优误差率”,接着深入进展空间最大的子集。

注意,上面的许多诊断有着直接、明显的解决方案。例如,如果训练数据太少了,那就获取更多训练数据!我们发现在心智上分隔分析阶段和(下面的)选型阶段是有帮助的,因为我们很容易陷入随机尝试各种方法,而没有真正分析背后问题的状况。另外,保持开阔的思路,勤于返回误差分析阶段,经常能够揭示有用的洞见,有助于改善你的决策。

相关内容
分享 2019-07-30 08:00:01

0个评论

文明上网理性发言,请遵守新闻评论服务协议