有关遗传编程的介绍及其作用.pptVIP

* 有关遗传编程的介绍及其作用 几年前我将自己在中学时便知道的一款纸牌游戏变成了手机应用。我为这款游戏编写 了 AI，但却不满意它的技术水平。因为不确信它是否值得通过进一步的手动编码而寻找更 好的解决方法，我便着眼于 AI 算法并最终选定了遗传编程（GP）。简而言之，这帮助 AI 能够更加有效地运行。从概念上来讲 GP 很容易理解，并且从基本水平来看也很容易执行， 而这便是本篇文章的要点。我还需要提醒读者们的是，这篇文章并不是为了教授你们如何编 写程序。 本文由两部分组成：第一部分是介绍 GP，而另一部分则是描写例子项目。 介绍 GP GP 是从“遗传”开始，因为它是受到名为进化的自然过程的启发。这是通过树图处理“编 程”的遗传算法（GA）的子类。通过运行一个遗传程序，你可以执行计算，作决策或广泛地 执行一些事件序列。以下便是计算 A + B * 7 的一个遗传程序。 ccs（from gamedev） 以下是另一个遗传程序，即执行了 8 个《星际争霸 2》创建次序介绍（免责声明：这 是我基于 SC2 网站上的描述自己理解的）。我们可以注意到这仍是一个树型，尽管它是基 于一个非标准模式。除了决策节点外（其条件较难执行），对于这棵树的评估应该直截了当； “高破坏潜能”是一个模糊的概念。 ccs（from gamedev） “遗传”部分是源自这些树/程序可以被当成基于多种方式“突变”的基因组。通过不同基因 组/程序连续突变，并使用适应度/选择标准，我们便能够影响怎样的任务能够推动遗传程序 变成有效的解决方法。让这些独立程序解决任务将很大影响着下一代—-这便是解决方法！ 下图呈现的是 4 个个体通过随机颜色变化和节点添加/删除而经历了 5 代的进化，这里 的任务是关于获取更多蓝色节点。当然了，这是基于我们知道如何创造一颗巨大的蓝色之树 的人为例子。 ccs（from gamedev） 需要注意的是最棒的树型可能是克隆的也可能是遭受到突变，所以可能/不可能创造出 一个更健康的孩子。克隆能够确保好的树型可以在不变的形式下幸存下来，但却会减慢突变 （巨大的种群克隆是不必要的）。同样需要注意的是选择规则并非 100%公正；这点并不重 要。 最后，让我明确 GP 不同于遗传算法的原因。从整体上来看 GA 是关于通过进化而优 化参数，这是一种随机有哪些信誉好的足球投注网站形式。这些参数是如何结合并不是 GA 所担忧的，除了像 GP 这 样的特殊例子。另一方面 GP 能够提供一种不仅会进化参数值，同时还能传达这些参数值是 如何结合的方法，使其成为一种更强大的学习方法。即使你不知道一个特定计算的表达式， GP 将为你掌握该表达式，而不只是优化一套输入参数。 关于 GP 树可传达什么的例子 算术树 我想最简单也是最常用的 GP 用法便是让程序传达算术运算式，即基于“真实”数字的最 常见表达方式。我们在很早前便着眼于这一点，但我想说的是基于一些目的而演变数学函数 是一种非常强大的能力。以下是 Lua 面向我的游戏中的一个“中等”AI 进化的评估函数： (((((env.rounds)+((env.suit)*(env.rank)))+(env.safe))+((env.block)*(env.block)))*(((-4. 0745883)+(0.025403308))+((((env.selfblock)*(env.dist))+((env.selfblock)*(env.safe)))+(m ath.random())))) 需要注意的是这里存在终止节点，如 env.rounds，mathrandom()和常量，以及二进制 非终结符+和*。注意算术树中的非终结符通常都不需要任何额外的参数—-只将其当成是输 入分支。在一个线性文本文件中看到这么多括号真的太让人困惑了，所以让我们绘制出这棵 树： ccs（from gamedev） 这棵树的形状是储存在内存中，并在此运行进化和模拟；线性码只是面向我的目标游 戏进行优化的一个输出内容。另外一个需要注意的是常量将产生-4.0745883 + 0.025403308 计算，如多余或过度增长将受到适应度函数的控制。 执行树 另外一个选择便是让一个遗传程序基于更加传统的意义代表一个计算机程序，如控制 流图像。当然了，一个主要的限制与一个常见的计算机程序相比较便明确了图像必须是一棵 树的事实。这可能/不可能是个问题，并且也有方法通过创造性节点类型而解决缺少循环的 情况。 之前的《星际争霸 2》建置指令例子便是有关执行树的典例；该例子中的执行是从根 到树叶，并在中间维系着一些决策。节点可能是决策（需要带有注释的参数）或只是执行带 有线性结果的指令，如“建造工人”。有些指令节点可能根本就没有孩子，因此也可以扮演树