使用Python和遗传规划(Genetic Programming)玩转Flappy Bird

使用Python和遗传规划(Genetic Programming)玩转Flappy Bird

[2019/03/25更新] 可以在repl.it上在线运行了,请猛击gpFlappyBird-repl.it。(不过当前repl.it尚不支持声音,所以没有游戏声音。)

近期在知乎看到一个问题GitHub 上有些什么好玩的项目?其中当时最高赞的回答推荐了一个用神经网络和遗传算法(也就是neuro-evolution)来玩Flappy Bird的。想到之前无聊时也做了一个玩Flappy Bird但用不同算法的玩具AI,就在此简单介绍下,但本文的主要意图是对进化计算特别是遗传规划做一些初步的介绍,从而让更多人知道这一工具,而将遗传规划用于flappy bird的AI制作则是因为这样的练习项目更加有趣。笔者的项目gpFlappyBird开源在

因为本文篇幅较长,在文首先展示基于遗传规划构建AI自动学习玩flappy bird的demo如下,以吸引读者的兴趣(如果有一点点感兴趣的话(>人<;))

基于遗传规划的AI自动学习玩鸟https://www.zhihu.com/video/1071491221112983552

与其它类似项目相比,本项目有如下特色:

  1. 游戏更加困难:柱子之间的水平距离与竖直距离均是随机的,而非固定值 。
  2. ‍ ‍ 进化效率更高:在进化中仅需非常小的种群(10左右),并且通常仅需少于50代即可达到一个很好的游戏表现。
  3. 可玩性更好:与其呆呆地看小鸟进化,不如参与到游戏中,一起玩鸟 !视频中的蓝色小鸟即代表人类玩家,可随时添加。很明显,我的水平远不如这个简易的AI 。
  4. 不使用神经网络:deep learning审美疲劳了,让我们玩个别的吧,不需要任何专门的库,也不需要GPU!



前言

在AI大火的如今,在媒体炒作下,似乎很多人眼中的AI已经等价于deep learning了。但是,我们需要明确,出尽风头的deep learning只是AI这一超大领域中的一个小分支。具体到用AI来玩flappy bird这一主题,毫无意外,在GitHub绝大多数项目都是用了神经网络(或深或浅)。在此,笔者并不想重复这一入门级的强化学习玩游戏项目,而是想另辟蹊径,不采用神经网络而是仅用进化计算的一个重要分支遗传规划来实现一个游戏AI。

本文目的并不是安利自己的GitHub仓库,而是想让更多人知道所谓的AI并不只有深度学习。了解其它的算法,哪怕是将其它算法结合到深度学习中,也很可能起到很好的效果,而不只是在碰到一个问题时,无脑套用各种网络模型。进化计算是一个发展比较成熟但仍在发展的领域,并在科研和工业界均得到了大量的应用。当前,进化算法有重新崛起的趋势,特别是在强化学习的网络训练中,比如Uber的系列文章Welcoming the Era of Deep Neuroevolution

大家可能都听过甚至用过进化计算的一个重要分支,遗传算法。但在本文中,笔者将介绍另外一个重要的分支,遗传规划(Genetic programming, GP)。通俗地说,遗传规划并不是用于优化模型数值参数,而是用于自动寻找模型,包括其结构和参数。从高大上的角度说,遗传规划的目的是实现自动编程

当理解了进化计算和遗传规划的基本工作原理后,在Python对其最简版本进行实现将会非常容易,因此本文并不讲解如何编写相应的Python代码。在接下来的文字中,笔者将由neuro-evolution讲到进化计算,进而谈到遗传规划,重点讲述遗传规划家族的一种算法笛卡尔遗传规划(CGP),并利用CGP实现一个flappy bird的AI。

GitHub上面向Flappy Bird的AI项目粗略总结

因为Flappy Bird游戏本身操作单一、逻辑简单,即使自己从零开始写这个小游戏原型也不用多少工作量,所以GitHub上有很多项目拿它来测试一些简单的AI。其中采用的AI算法可大致归为两类:neuro-evolution和强化学习。

  • 基于Neuro-evolution

比如FlappyLearning(使用Javascript)和上文提到的Machine-Learning-Flappy-Bird(使用HTML5)。

  • 基于强化学习(Reinforcement learning)

比如利用Deep Q-learning的DeepLearningFlappyBird(使用Python)和FlappyBirdRL(使用Javascript)。

因为在笔者的项目中,利用了进化计算家族的一种算法,所以在下面仅对有所关联的neuro-evolution这一类别做进一步介绍。

Neuro-evolution (神经进化)

在前述Flappy Bird游戏的应用中,AI模型的输入是一些小鸟的距离、高度等状态参数,比如在Machine-Learning-Flappy-Bird项目中使用了水平距离高度差两个参数,其GitHub上的截图如下:

Neuro-evolution: 利用遗传算法来优化网络权重

之后利用一个数学模型(在此是一个单隐藏层的神经网络)计算得到输出。如果这个输出值大于0.5,就控制小鸟拍打翅膀。从这一角度来看,这似乎是一个简单的二分类(binary classification)问题。但进一步思考就会发现,与传统的图片等二分类问题不同,我们难以直接定义一个可导的损失函数(loss function)。传统的监督分类问题都是基于一对一的“输入-输出”,即给定一组输入,有对应的一组输出,从而构成一个监督学习(supervised learning)问题。但在本游戏中,模型的表现好坏是由一系列的决策(即小鸟是否flap拍打翅膀)来决定的,换句话说,是由一系列输入得到最后的惟一输出,即小鸟的飞行距离。因此,从直观思路来说,这个问题背景更匹配强化学习,而非简单的神经网络拟合。

但是,我们仍然可以采用上图中所示的神经网络。由于缺乏一个可导的损失函数,最常用于训练神经网络的反向传播(backpropagation, BP)算法就无法使用,这也是采用neuro-evolution的主要原因。Wiki上对neuro-evolution的定义如下:

Neuroevolution, or neuro-evolution, is a form of artificial intelligence that uses evolutionary algorithms to generate artificial neural networks(ANN), parameters, topology and rules.[1] It is most commonly applied in artificial life, general game playing[2] and evolutionary robotics.

FlappyLearning等项目中,neuro-evolution主要用来训练神经网络的参数。在这种游戏场景下,Wiki上也直接指出了neuro-evolution相对于BP的优势,如下:

The main benefit is that neuroevolution can be applied more widely than supervised learning algorithms, which require a syllabus of correct input-output pairs. In contrast, neuroevolution requires only a measure of a network's performance at a task. For example, the outcome of a game (i.e. whether one player won or lost) can be easily measured without providing labeled examples of desired strategies.

从更广义的角度来说,梯度下降(gradient descent)和遗传算法均是用于优化数学模型参数的常用方法。当这个模型是神经网络时,两者就分别有了新称呼:反射传播(BP)和neuro-evolution。相比于梯度下降,遗传算法等基于进化思想的算法是更加通用的优化方法。它对系统的透明度要求更加低,不需要知道系统模型的具体形式,也不需要梯度等信息,惟一要求就是给定输入,系统给出一个(可以衡量好坏的)输出。因此,进化类算法可以应用于black-box optimization。(注:neuro-evolution有更广泛的用途,比如可以优化神经网络的结构。)

回到Flappy Bird这个游戏的AI设计,在neuro-evolution的背景下,系统的输入实际是网络的参数,可以简单理解为猜一组随机数;系统的输出则是小鸟飞行的距离。小鸟飞得越远,说明这组输入越好,在遗传算法框架下也就是有更高的适应度(fitness),从而代表这种输入的个体有更高的概率被选中,然后通过杂交(mutation)和变异(mutation)产生后代,将此个体的“优秀基因”传播下去,后代将会呈现出越来越优秀的趋势。很明显,这就是进化论中的“自然选择”思想,也是所有进化类算法的核心策略。

相比于梯度下降,尽管遗传算法能处理的情况更多,但如果存在可导的目标函数,很明显利用梯度信息将会有更高的效率。所以,遗传算法等进化算法的一个劣势就是计算量大、效率低。当然,它的优势就是几乎可以应用于所有的问题,不需要梯度信息,并且可以在一定程度上摆脱局部最优点。

Neuro-evolution是个历史悠久的研究主题,在出现BP算法后,有些销声匿迹了。但随着当前计算力的提升,特别是在2017年OpenAI发文宣布Evolution Strategies as a Scalable Alternative to Reinforcement Learning,指出简单直观的evolution strategy(进化策略,进化算法的一种)可以比标准的强化学习更好地训练其中使用的神经网络。随后,Uber团队也通过一系列文章发现遗传算法(进化计算的另一种)可以有效地训练深度神经网络,并宣称Welcoming the Era of Deep Neuroevolution!之后,在过去一年,各大顶会也出现了进化算法训练超大型神经网络的文章,特别是在RL应用的领域,在相关会议搜索evolution关键字即可,在此不再赘述。

因此,在当前deep learning大火的情况下,了解下进化计算的相关思想,并整合相关算法和工具到深度学习领域,也是一个很好的研究及应用方向。

Evolutionary computation (进化计算)

进化计算是一系列由自然界进化规则所启发得到的算法的统称。Wiki上对其定义如下:

In computer science, evolutionary computation is a family of algorithms for global optimization inspired by biological evolution, and the subfield of artificial intelligence and soft computing studying these algorithms. In technical terms, they are a family of population-based trial and error problem solvers with a metaheuristic or stochastic optimization character.

最为大家所熟悉的进化计算家族的成员应该是遗传算法。尽管进化计算包括数以百计的算法和变体,我们一般认为它们可以划分为三种基本类型:

  1. 遗传算法(genetic algorithm)
  2. 进化策略(evolution strategy)
  3. 遗传规划(genetic programming,有时也称为进化规划)
进化计算的主要分类及其主要创始人

在前文所述的neuro-evolution中,主要应用的是遗传算法和进化策略,用于对神经网络的参数(例如权重weight)进行优化。当然,神经网络的超参数也可以用这些方法来进行优化。与遗传算法相比,进化策略的一个重要特性就是其一般不采用杂交(crossover)操作,并且在选择selection时,后代将与父辈进行竞争(社会就是这么残酷! )。对本文后面部分探讨的Flappy Bird AI而言,则主要使用了第三类,即遗传规划(genetic programming)。

进化算法的核心思想来自于生物界的进化。尽管上述算法在实现细节上有所差异,核心算法框架则是简洁而统一的,如下图 (Source):

Framework of Evolutionary Algorithms

(注:在进化策略中,通常不使用crossover操作符。)

由于遗传规划的应用没有遗传算法等广泛,多数人对这一重要的进化算法的分支比较陌生,因此,在接下来的部分先对遗传规划做个简介。


遗传规划(genetic programming, GP)

John R. Koza于1994年出版了专著Genetic Programming: On the Programming of Computers by Means of Natural Selection,提出了这一新颖的基于进化思想的方法,用以automatic programming,即根据需要自动合成计算机程序。当然,即使到现在自动编程仍然是一个看上去很遥远的目标。因此,相比于自动编程,GP更成功地应用在了关于模型结构的自动设计和优化的领域,如电路设计、机械结构设计和生物学中药物分子设计等。在数据相关领域,GP则被广泛地应用在符号回归(symbolic regression)、特征提取和选择(即自动特特征工程)、数据挖掘等。感兴趣的读者可以参见Wiki Genetic Programming或者自行Google scholar。

遗传规划的两本重要参书

相比于主要应用于参数优化的遗传算法和进化策略,遗传规划的显著特点是它的搜索空间是“计算机程序”,或者称之为program space。更具体地说,遗传规划可以同时优化模型结构和模型参数。使用遗传规划时,我们并不需要预先选择模型的结构,比如简单的线性模型或者复杂的神经网络模型。反之,我们只需要指定基本的运算符operators和模型的可能输入变量,遗传规划将通过进化思想自动生成、选择和优化一个数学模型,使其在我们给定的目标函数上表现最优。因此,遗传算法非常适用于当前人类知识非常少的应用领域。例如,在2009年的Science文章Distilling free-form natural laws from experimental data中,作者只向一个GP系统提供实验数据,GP系统可以自行发现一些重要的物理定律。(注:当然,这些物理定律早已经被科学家总结出来了。)

经典的Koza-style GP(树形结构)

如前所述,在算法大框架上,遗传规划(GP)和遗传算法等差别很小。两者的本质区别在于问题解的表达形式,即进化中的个体(individual)的编码。在所有的进化算法中,我们均需要把问题的可能答案编码成一个容易被进化算法操纵的形式,比如在遗传算法中最常使用的二进制01编码。若采用生物学中的术语,则称之为表现型(phenotype)与基因型(genotype)之间的互相映射,如下图所示。

进化计算中个体的定义

在GP的最初版本中,个体的表示representation大量采用的是其创始人John R. Koza使用的树形结构。对CS领域的同学来说,应该对这种表达式树或者语法树是非常熟悉的。一个简单的expression tree如下所示

max⁡( + , +3 )的表达式树结构

容易联想,如果把这棵树换成一个语法树(abstract syntax tree, AST),那么它就可以编码一段程序,这也就是遗传规划可以用于进化计算机程序或者说自动编程的根本所在。

在GP的应用中,有几个重要的术语,定义如下:

  1. Function set:给出GP在构建模型时可以使用的所有基本算子,通常是一些简单的基础函数,如四则运算符
  2. Terminal set: 包括自变量(input variable),常数(如 \pi ),无须参数的函数等。其中后者通常用于产生随机常数,比如各种语言中都有rand函数。
  3. Primitive set: function set和terminal set的统称。


因此,在使用GP解决一个问题时,我们只需要指定primitive set及优化目标(objective),而模型的具体结构和其中的参数值则由GP自己去进化。(实际应用中,GP更适合进化模型结构,通常会在算法中嵌入一个更加高效的基于local search的参数优化器来优化参数值以提高进化效率。)

因此,在上图中,应用场景可能是,我们有一组输入与输出数据 \left\{ x_i\right\}_{i=1}^n和\left\{ y_i\right\}_{i=1}^n ,给定一个function set \left\{ +, -, *, /, max \right\} 和terminal set \left\{ 1, 2, \cdots, 10 \right\} ,优化目标是最小化 \sum_{i=1}^{n}{(y_i-f(x_i))^2} 。但与经典的机器学习方法相比,我们并不指定函数f的具体形式,而是由GP根据这些基本的算子来自动发现、挖掘。

基于树形结构的GP的交叉与变异操作

GP进化过程如下:

  1. 在初始化阶段,GP产生一些随机的初始解(个体)
  2. 对当前个体进行解码与求解目标值(evaluation),并根据一定规则做selection
  3. 以一定概率对选出的个体进行杂交(crossover),得到后代(offspring)
  4. 以一定概率对后代进行变异(mutation)
  5. 回到step 2直到优化目标值满足我们要求

其中较为复杂的是树形结构的杂交与变异,常用的是单点杂交与单点变异方法,如下图所示。具体细节请参见相关书籍,如A field guide to genetic programming [PDF].

GP中树形结构的杂交与变异

遗传规划的变体

上述树形结构是最初的GP中个体的编码形式,同时仍然是目前应用最广泛的形式。当然,与其它算法相似,GP也有很多变体,其中各种变体的主要特征在于如何编码个体。除了经典树形结构,还有线性结构及图结构等。其中,在采用线性染色体结构编码的变化中,较为出名的是基因表达式编程 (gene expression programming, GEP),此方法采用简单的定长染色体并可以包含多个基因。(注:在GP中,一个编码后的答案,即个体individual,也被称为染色体chromosome。)笔者也利用Python实现了一个GEP的库geppy,其构建于有名的进化计算框架DEAP之上,可以方便地进行GEP的快速实验。配备详细文档的geppy库链接如下:

使用图结构的GP的典型代表则是笛卡尔遗传规划(Cartesian Genetic Programming, CGP),也是笔者在Flappy Bird中使用的GP实现。在CGP之前,笔者也曾尝试过经典的树结构GP,但效果并不理想。在接下来的部分,将对CGP基本原理进行介绍。


笛卡尔遗传规划(Cartesian Genetic Programming, CGP): 基于图结构的GP

在上文陈述了进化计算的许多方面之后,终于谈到了笔者在Flappy Bird中使用的方法。简言之,CGP使用一个图来编码一段program。在多数应用场景下,这个program就是一个数学公式,即我们所说的符号回归 (symbolic regression)。CGP名称中含有”笛卡尔“,这是因为它用一个二维网格(而不是树)来编码一个GP中的个体(染色体)。CGP由University of York的Julian F. Miller教授于2000年正式提出。当前,Miller教授仍然在活跃地发展CGP方法,并且有一个官方网站I think therefore I CGP

Julian F. Miller教授和他的CGP专著

CGP中的结构

下图(source)描绘一个3输入变量、3输出变量和9个计算节点的CGP网格。(注:此处 9=3*3 仅是巧合。)

CGP二维网格示例

上述网格看着复杂,实际它只是表达了一个数据流,即如何由三个inputs经过逐步的计算到达三个outputs。如果读者有过SIMULINK或者LabVIEW的经验的话,应该很容易联想到data flow diagram。另一方面,如果读者对当前流行的深度学习库如TensorFlow和PyTorch等了解的话,也很容易联想到这些库的核心:计算图(computation graph)。总之,可以把CGP中编码答案的个体看作是一个数据流图或者计算图。CGP的基本形式如下(来自Miller教授的PPSN 2014 Tutorial):

与前一部分的树形结构的GP相类似,我们需要提供一个function set,那么网格中的计算节点 f_{i,j} 将从这个function set中随机选取。同时,指定terminal set,其中的n个输入量将作为n个输入节点单独列出,而所需要的m输出则对应到额外的m个输出节点。至于模型的常数值,则被储存为计算节点之间连线的权重。从这个角度来看,某一代的CGP图可以看作是一个”异形“的神经网络。当然,与神经网络相比,其有如下特点:

  1. 结构可变。通过随机改变计算节点间的连线(即进化计算的变异mutation),CGP的计算图会随着进化代数不断变化。
  2. 一个计算节点可以连接到在它之前的任意节点。通常,神经网络中第k层的神经元只与第k-1层的神经元相连。此外,在CGP中,其描述的是两个计算节点(node)间的连接关系,而非层与层(layer)间的连接关系。因此,CGP中的计算单元的拓扑关系是更加灵活的。
  3. 两个计算节点间的权重随机生成,而非由Backpropagation优化产生。这个特点一方面是CGP的劣势,与其它的GP变体相似,其在寻找精确的常数时效率很低,尽管可以通过嵌入一个local searcher来改善;另一方面,不利用梯度信息也是CGP的优势之一,这表明计算节点的函数(类比神经网络的activation function)可以任意选取,并不要求可导。


需要指出的是,尽管在应用CGP时,我们会预先指定计算节点的数量,比如 (100\times200) ,但与神经网络不同,这并不意味着所有的20000个节点均会参与到实际计算中。由于CGP网络中的连线是随机改变的,如果某个节点 f_{i,j} 的输出并没有传播到最终的输出节点(output node)中,那么 f_{i,j} 就不会出现在计算图中。从这个角度来说,一个CGP网络可以编码由简单到复杂 的近乎无穷种模型。一个具体的示例如下(来自Miller教授的PPSN 2014 Tutorial):

一个简单的CGP示例:注意图中节点6并未使用

CGP中的进化

当明确CGP中的个体表示后,剩下的问题就是如何进化每个个体,即通过随机的修改与有倾向性的选择,使整个种群的表现随着进化代数的增多不断变好。

与传统的基于树结构的GP不同,CGP一般采用进化策略(Evolution strategy, ES)(而非遗传算法)来进行优化。最简单的是 (1+1)-ES ,即

  1. 给定一个CGP个体p,根据一定变异概率随机改变每个计算单元的具体函数、计算节点之间的连线和每条连线的权重值,得到一个新个体q
  2. 将个体q所编码的答案作用于我们实际的问题,得到其优化目标值。
  3. q表现比p更好,则用q代替p。否则,仍然保留p
  4. 回到step 1,直到达到我们理想的目标值。


上述策略可以容易推广到 (\mu+\lambda)-ES ,从而得到更高的进化效率,当然其代价就是更高的计算量。


对神经网络说bye: 使用CGP来自动学习玩转Flappy Bird

如文章开头所说,在GitHub上有很多Flappy Bird AI。但几乎所有的项目都是利用了神经网络来拟合某个用于控制小鸟flap的函数,区别在于训练方法的不同。既如此,再多一个基于神经网络的flappy bird也并无多大意义。在本文中,笔者只使用了CGP这一遗传规划算法来构建一个玩转flappy bird的AI brain

这个方法的基本动机很直接。在之前neuro-evolution的讲解中,我们知道其中神经网络的作用是将小鸟当前的状态 \mathbb{x}=(x_1, x_2, \cdots)映射成一个二元输出 y\in\{0,1\} 以控制小鸟的动作,即是否拍打翅膀flap。换言之,我们要寻找一个模型 f 使得输出 y=f(\mathbb{x}) 可以控制小鸟动作使其飞得尽可能远。由于神经网络的universal approximation特性,在很多这样的场合,我们都会选择用神经网络来逼近这个 f 。但在Flappy Bird这个场景中,由于在游戏中小鸟的飞行轨迹是受物理定律支配的(至少近似是),那么笔者想到,是否存在一个直接的数学表达式 f 而非一个黑箱神经网络模型来达到前述目的

当然,我们并不想自己根据物理定律来计算得到这个表达式(如果真存在的话)。对于这种自动寻找一个公式(或者更广泛的地说,探求一个program,构建一个未知结构的模型)的需求,遗传规划GP是最先进入脑海的方案。

因此,本文的目的是利用GP(更具体地说是CGP)来进化一个模型(即一个数学函数) f 用于控制小鸟的运动,从而使其飞得尽可能远。同时,这也可以体现出GP相对于传统的机器学习算法的另外一个优势:模型可解释性。多数情况下,GP找到的数学模型比较简单,可以比较清楚的揭示出各个输入变量(即机器学习背景下的特征feature/attribute)相互作用及组合关系,而这对于探寻模型机理的领域,比如生物、医学及其他理工学科有极大的意义。上文提到的Science文章Distilling free-form natural laws from experimental data就是一个很好的例子。另外一个因素就是,与CV/NLP不同,在生物和医学等领域,训练数据集通常非常小,比如几百个甚者几十个样本。在这种小样本情况下,随便采用一个机器学习模型,都可以得到很不错的预测效果(至少在训练集上),但很多问题的目的并不是预测,而是想由这些非常有限的数据来探寻背后的机理,比如多种药物是如何协同作用以调控细胞/组织的活动的,这些问题是以神经网络为代表的黑箱模型不能给出答案的。在此,推荐一篇非常好的文章To Explain or to Predict?

Flappy bird AI使用的CGP设计

笔者首先利用pygame编写了基本的flappy bird游戏,本过程参考了FlappyLearning这一项目的Javascript实现。与GitHub上其它的flappy brid AI项目相比,笔者的游戏更具有挑战性,因为柱子间的水平距离和上下两根柱子间的距离均是随机而非固定的。鉴于此,本文中控制小鸟的模型也需要三个状态输入量而非两个,如下图所示

v: 竖直距离。h: 水平距离。g: 上下柱子间隔。

因此,我们想学习一个函数(数学表达式) y=f(v,h,g) 。控制律则是,当 y>0 时,小鸟拍翅膀。CGP的设计细节如下:

  • Function set:仅使用四则运算符 \{+,-,*,/\} 和求负(neg)。
  • Terminal set:三个输入变量 {v, h, g}
  • 网格结构1\times500 ,即实际上使用一个一维的结构。
  • 计算节点间的连接权重 :-1到1间的随机数。

因此,在上述设计下,我们可能得到的一个CGP计算图示意如下:

Flappy bird AI使用的进化策略

在前文中已经提到,在CGP中通常使用进化策略来做优化。我们采用 (\mu+\lambda)-ES ,即维持一个包括 \mu 个个体的种群,在每一代,这 \mu 个个体将产生 \lambda 个后代并进行竞争,其中优胜的\mu 个构成下一代。经过实验发现,对于flappy bird这个游戏,很少的数量如 \mu=5\lambda=8 就已经足够。

由于上文中已经对进化计算做了很多介绍,在此不再赘述,仅以下图表明进化流程

基于进化策略的CGP在Flappy Bird中的应用

适应度(Fitness)度量

进化计算中所谓的fitness,即相当于优化问题中的目标(objective)或者机器学习中的损失函数(loss function)。很明显,可以用总飞行距离来衡量一个flappy bird控制模型的适应度。

Python代码实现

游戏设计

使用简单易用的pygame实现。如果读者对pygame感兴趣,推荐一个很好的教程KidsCanCode.org(孩子都会编程 )。

CGP实现

本项目中仅使用了最基本版本的CGP,其原理已经在上文做了介绍。进化计算的一系列算法的一个优点就是实现相对简单,本项目的实现在cgp.py这一个文件中。其中Function类用于储存function set中的函数,Node类表示一个计算节点,而Individual类则是进化中的一个个体(它的每个实例与一只小鸟相绑定)。由于思路很直接,编码也简单,有兴趣的读者可自行参考本开源项目。


后话

笔者最后想指出,尽管本文中用遗传规划来玩flappy bird,但只是为了让入门学习看起来更加有趣。遗传规划GP除了做这种玩具AI,还有很大的用途。只从数据科学的角度说,GP可以被用于自动特征工程和自动神经网络结构设计(即现在很火的AutoML)。比如下列几篇文章:

[1] Muni, Durga Prasad, Nikhil R. Pal, and Jyotirmay Das. "Genetic programming for simultaneous feature selection and classifier design." (2006).

[2] Xue, Bing, and Mengjie Zhang. "Evolutionary feature manipulation in data mining/big data."ACM SIGEVOlution10, no. 1 (2017): 4-11.

[3] Zhang, Yang, and Peter I. Rockett. "A generic multi-dimensional feature extraction method using multiobjective genetic programming."Evolutionary Computation17, no. 1 (2009): 89-115.

[4] Guo, Hong, Lindsay B. Jack, and Asoke K. Nandi. "Feature generation using genetic programming with application to fault classification."IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)35, no. 1 (2005): 89-99.

[5] Rodriguez-Coayahuitl, Lino, Alicia Morales-Reyes, and Hugo Jair Escalante. "Towards Deep Representation Learning with Genetic Programming."arXiv preprint arXiv:1802.07133(2018).

还有很多的此类文章,在此不再列举。总之,遗传规划和范围更大的进化计算,也值得AI从业人员进行学习、探索与研究!

编辑于 2019-03-25 09:44