1

我想开发一个基因程序，可以解决一般问题，比如在电脑游戏中生存。由于这是为了娱乐/教育，我不想使用现有的库。

我想出了以下想法：

输入是一个包含 N 个整数的数组。遗传程序由多达 N 个 AST 组成，每个 AST 从一些数组元素中获取输入，并将其输出写入单个特定数组元素。

AST 可以是任意复杂的，并且仅包含四个算术运算符（+、-、*、/），并且可以对给定数组的常量和固定元素进行操作（无随机访问）。

所以对于 [N=3]，我们有 3 个 AST，例如：

a[0] = {a[0] + 1}
a[1] = {a[0] + a[1]}
a[2] = {a[0] * 123 + a[1]}

N AST 一个接一个地执行，并且无限重复。

现在我的问题是，这个系统是否足够“强大”（图灵完备？）还是无法解决游戏 AI 常见的一些问题？

4

2 回答 2

3

从我的角度来看，系统的图灵完备性并不是这里的主要问题。当使用遗传算法进化某种应用于某些游戏环境的策略时，该算法的一个特征——这将是有帮助的——是——我相信——解决方案的“基因组”的微小变化会导致行为的相当小的变化。如果这不是真的，那么每个突变或交叉都可以产生一个行为完全不同的实体，在这种情况下，遗传算法达到某个最优值可能是有问题的——因为适应度函数的情况不够连续.

话虽如此，尝试以某种方式在基因组中编码一种决策树并对其进行进化对我来说是有意义的。然而——根据我的经验——游戏人工智能中的遗传算法在用于“计算”某些特定行为的某些参数的最优值然后“进化”行为本身时效果最好。

于 2018-11-09T10:58:17.610 回答
1

抽象语法树 (AST) 等同于以特定领域语言制定的程序流。如果语言由可能的命令组成：上、左、下、右，则可能的 AST 将是：上、上、上、左。基因编程试图做的是进化 AST，这意味着找出许多不同的程序流程来解决游戏。与其只改进 AST，不如改进语法。这意味着，修改制定 AST 的领域特定语言。例如，通过添加一个额外的命令，如“gocenter”。新语言现在包含 5 种可能的动作：gocenter、up、left、down、right，并且可以测试新的种群。为了系统地发展语法，需要通过交互来学习语法。这意味着，我们从一个空的语法开始，然后小心地添加新的可能的动作命令。在文献中，这被描述为“语法归纳”，意味着从人类交互中获取输入流并从头开始生成新语言。有了这个语法，就有可能进化出可能的 AST。

引用：“语法进化 (GE) 是一种基于语法的遗传编程形式，它通过上下文无关语法指定可能解决方案的语法”来源：Perez、Diego 等人。“使用语法进化为马里奥人工智能比赛进化行为树。” 欧洲进化计算应用会议。施普林格，柏林，海德堡，2011。

于 2018-11-12T20:58:30.570 回答