genetic-algorithm - 当只知道相对适应度时使用遗传算法？

Question

我正在研究国际象棋引擎，并且正在使用基因表达编程方法来改进评估函数。

由于国际象棋没有神谕，我的适应度函数只能找到两个人的相对适应度(通过进行国际象棋比赛)。

因为我没有绝对的适应度测量，我可能会以循环方式得到一些比彼此更好的个体($R_A_B(A)>R_A_B(B), R_B_C(B)>R_B_C(C ), R_A_C(C)>R_A_C(A)$ )

那么，在这种情况下，有哪些方法可以有效地进化个体，我又该如何避免陷入这种循环困惑呢？谢谢:)

Answer 1

循环方式(R_A_B(A)>R_A_B(B), R_B_C(B)>R_B_C(C), R_A_C(C)>R_A_C(A))无法完全避免，因为国际象棋游戏就是一个很好的例子无法非常准确地评估完美的 NP 问题和此类系统的详细行为。

让我们考虑一个棋盘位置P。让我们表示由个体 A 在棋盘中的位置 P 产生的变化，属于集合 Ap。让我们考虑另一个集合 Bp，其中 B 定义的评估函数用于获取该位置的变化。让我们定义一个函数 Q(x) 来测试随着游戏的进行任何个人提供的变化的质量。所以在 P 让 Q(Ap) > Q(Bp) 然后对于任何其他位置 p', Q (Bp') > Q(Ap')。

进化出一个能为所有位置产生最佳变化的个体是不可能的，因为您自己说过国际象棋没有神谕；
但这不会成为问题。在这里，我提出了一种可能有帮助的方法；与其试图在如此困惑的情况下为个人提供一个独特的等级，为什么不能平等对待他们呢？如果他们被平等对待，可能出现的一个问题是，前几代人可能会在很大程度上陷入这种循环困惑(会有太多的个体实力相当)。因此，为前几代使用不同的适应度函数来提高它们的效率足以解决基本的国际象棋难题(通过定义具有更简单端点的适应度函数)并没有错。后代陷入这种循环困惑的次数会更少，这不是问题。如果适应度函数取决于特定种群中两个个体之间的比赛结果，那么这会将此进化的终点设置为:达到假设函数 G(x) 的比赛强度(这是永远不可能的) .因此，生成的个体将尝试在更广泛的范围内进化，通​​过尝试在所有棋盘情况下变得完美(如果出现在初始世代中的个体的游戏实力较弱，这将减慢该过程)。

我建议的另一种方法是尝试定义一个常量函数 N(x)，它可以在更高的时间复杂度下工作(即，通过检查更多变化来评估比从特定世代中选择的个体更长的时间) .现在我们可以分别比较R_A_N(A)、R_B_N(B)、R_C_N(C)这三个值，对它们进行排序。没有必要为此创建一个唯一的常量评估函数，可以为此目的选择任何随机个体。

使用选择性的个体 N(用于搜索更大的深度)然后尝试找到 R_A_N(A)，更像是在图中选择原点，其中只有某些点的相对位置是已知的。在这里，人口是相对于选定的个人发展的； N 不必是具有固定参数的常量函数，它也可以是出现在这个循环困惑中的个体之一，可以在测试更多变量(更高搜索深度)的引擎中运行。如果个体 A 被选为 N，并让其在更深的深度上与自己比赛，那么很明显，深度更高的个体 A 击败了深度更低的 A。在这里，我们可以定义一个适应度函数，它取决于国际象棋比赛最终结果以外的因素；例如，

所以定义 R_A_N(A), R_B_N(B), ... 这种方式可以避免这种循环困惑。