游戏代理启发式评价函数优化的遗传算法

Question

这是对这个问题中给出的答案的回应： How to create a good evaluation function for a game?，特别是@David（这是第一个答案）。

背景：我正在使用遗传算法优化正在使用 minimax / alpha beta 修剪（迭代加深）的游戏代理中的超参数。特别是，我想使用遗传算法优化启发式（评估）函数参数。我使用的评价函数是：

f(w) = w * num_my_moves - (1-w) * num_opponent_moves

唯一要优化的参数是 [0,1] 中的 w。

下面是我编写遗传算法的方法：

创建一个随机群体，比如 100 个代理人
让他们随机玩 1000 场游戏并进行替换。
让 parent 成为表现最好的代理人，并混入一些表现较差的代理人以实现遗传多样性。
随机繁殖一些 parent 来创造 children。 * 育种过程：我们定义一个child是其parent个体重的平均值。 即 child权重 = 0.5(father.w+ mother.w)
新人口由parent人和新创建的child人组成。
按如下方式随机变异 1% 的人口：newWeight = agent.x + random.uniform(-0.01,0.01) 并考虑微不足道的边界情况（即小于零并且大于一，适当地）。
进化 10 次（即对新种群重复）

我的问题：请评价以上加粗点。特别是，有没有人有更好的繁殖方式（而不是简单地平均 parent 权重），有没有人有更好的变异方式，而不是仅仅添加 random.uniform(-0.01,0.01) ？

Answer 1

看起来您实际上并没有将 genetic-algorithm 应用于您的代理，而只是直接在 phenotype/weights 上进行简单的进化。我建议你尝试引入 genetic representation 的权重，然后进化这个基因组。一个例子是将您的权重表示为二进制字符串，并对字符串的每一位应用进化，这意味着每一位都有可能发生变异。这称为点突变。您可以应用许多其他突变，但它可以作为一个开始。

您会注意到，您的智能体不会陷入局部最小值，因为有时一个小的基因变化会极大地改变 phenotype/weights。

好吧，这听起来可能很复杂，但事实并非如此。让我举个例子：

假设您的权重 42 以 10 为基数。这将是二进制的 101010。现在您已经对二进制表示的每一位实施了 1% 的突变率。假设最后一位被翻转。然后我们有 101011 二进制，或 43 十进制。没有这么大的变化。另一方面，对第二位执行相同操作会得到 111010 二进制或 58 十进制。注意大跳跃。这就是我们想要的，并让您的代理群体更快地搜索解决方案的大部分 space。

关于育种。你可以尝试交叉。让我们假设你有很多权重，每个权重都有一个遗传编码。如果将整个基因组（所有二进制数据）表示为一个长二进制字符串，则可以组合两个 parents 基因组的部分。再举个例子。以下是"father"和"mother"的基因组和表型：

Weight Name:          W1     W2     W3     W4     W5
Father Phenotype:     43     15     34     17     14
Father Genome:    101011 001111 100010 010001 001110
Mother Genome:    100110 100111 011001 010100 101000
Mother Phenotype:     38     39     25     20     40

你可以做的是在同一位置通过两个基因组绘制任意线，并将这些片段任意分配给 child。这是一个交叉版本。

Weight Name:          W1     W2     W3     W4     W5
Father Genome:    101011 00.... ...... .....1 001110
Mother Genome:    ...... ..0111 011001 01010. ......
Child Genome:     101011 000111 011001 010101 001110
Child Phenotype:      43      7     25     21     14

这里前8位和后7位来自父亲，中间来自母亲。请注意重量 W1 和 W5 完全来自父亲，而 W3 完全来自母亲。而 W2 和 W4 是组合。 W4几乎没有什么变化，而W2变化很大

我希望这能让您对如何进行遗传算法有所了解。也就是说，我建议使用现代库而不是自己实现它，除非你这样做是为了学习。

编辑：更多关于处理weights/binary表示的信息：

如果你需要分数，你可以通过将分子和分母分开作为不同的权重来实现，或者将其中之一作为常数，例如，42 和 10 给出 4.2.)
大于 0 的约束是免费的。要实际获得负数，您需要取负权重。
通过将权重除以该位串长度的最大可能值，您可以获得少于 1 个约束。在上面的示例中，您有 6 位，最多可以达到 63。如果您在突变后得到一个二进制字符串 101010 或 42，基数为 10，则 42/63 得到 0.667 和当 63/63 时，最高只能达到 1.0。
两个权重之和等于1？如果你得到 W1 和 W2 的 101010 和 001000，它给出 42 和 8，那么你可以去 W1_scaled = W1 / (W1 + W2) = 0.84 和 W2_scaled = W2 / (W1 + W2) = 0.16。这应该总是给你 W1_scaled + W2_scaled = 1。

Answer 2

自从提到我。

我没有对 parent 权重进行平均，而是使用 parent 权重作为 min/max 选择了随机数。我还发现我必须稍微扩大范围（当我对两个均匀的随机数或 sqrt(2) 取平均值时补偿标准偏差的减少，但我可能不准确）以抵制对平均值的拉动。否则人口向平均收敛，无法逃脱。

因此，如果 parent 的权重为 0.1 和 0.2，它可能会为 child 权重选择一个介于 0.08 和 0.22 之间的随机数。

后期编辑： 一种我当时不知道的更被接受、研究和理解的方法叫做 "Differential Evolution"。

游戏代理启发式评价函数优化的遗传算法

Genetic algorithm for optimization in game playing agent heuristic evaluation function

optimization

artificial-intelligence

game-theory

depth-first-search

genetic-algorithm