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

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。

这是我编程遗传算法的方法：

1. 创建一个随机的100个代理人群
2. 让他们随机玩1000场比赛替换。
3. 让父母成为表现最佳的代理人，其中一些表现较差的代理人参与遗传多样性。
4. 随机养育一些父母来创造孩子。 *育种过程：我们将孩子定义为其父母权重的平均值。即childWeight = 0.5（father.w + mother.w）
5. 新的人口由父母和新创造的孩子组成。
6. 按如下方式随机改变1％的人口：newWeight = agent.x + random.uniform（-0.01,0.01）并考虑平凡边界情况（即适当地小于零且大于一）。
7. 进化10次（即重复新种群）

我的问题：请评估上面的粗体点。特别是，有没有人有更好的方式来繁殖（而不是简单地平均父权重），并且有没有人有更好的方法来变异，而不是仅仅添加random.uniform（-0.01,0.01）？

Answer 1

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

您将注意到的是，您的代理人不会陷入局部最小值，因为有时一个小的遗传变化可以极大地改变表型/重量。

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

假设你在基数10中有42的权重。这将是二进制的101010。现在，您已在二进制表示的每个位上实现了1％的突变率。让我们说最后一位是翻转的。然后我们有二进制的101011，或十进制的43。没有这么大的变化。另一方面，对第二位执行相同操作会为您提供二进制或111010十进制的58。注意大跳。这就是我们想要的，让您的代理人群更快地搜索解决方案空间的更大部分。

关于繁殖。你可以试试交叉。让我们假设您有许多权重，每个权重都有遗传编码。如果您将整个基因组（所有二进制数据）表示为一个长二进制字符串，您可以组合两个父母基因组的部分。示例，再次。以下是“父亲”和“母亲”的基因组和表型：

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

你可以做的是在同一个地方通过两个基因组绘制任意行，并将这些段任意分配给孩子。这是交叉版本。

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发生了巨大的变化。

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

编辑：有关处理权重/二进制表示的更多信息：

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

Answer 2

自从我被提及以来。

我没有对父权重求平均，而是使用父权重作为最小值/最大值来选择随机数。我还发现我必须稍微扩大范围（当我平均两个均匀随机数，或者sqrt（2），但我可能并不精确）时，我必须补偿标准差的减少，以抵抗平均值的拉动。否则人口趋向平均而无法逃脱。

因此，如果父母的体重分别为0.1和0.2，则可以选择0.08和0.22之间的随机数作为儿童体重。

后期编辑：当时我不知道的一种更被接受，研究，理解的方法是“差异进化”。