genetic-programming - 如何从树中获取随机节点？

Question

看起来很简单，但我发现实现起来很棘手。对于我试图实现的一个简单的遗传编程问题，我需要它。该函数应该，给定一个节点，返回节点本身或其任何子节点，使得选择节点的概率相对于其深度呈正态分布（因此该函数应该主要返回中间节点，但有时返回根本身或最低那些-但是如果这使它变得更加复杂，那并不是真正必要的，如果以相等的概率选择所有任何节点，那就足够了）。

谢谢

Answer 1

对于统一的情况，如果你知道每个节点的深度，你可以用概率大小（左）/大小（这个）向左，概率大小（右）/大小（这个）向右，否则选择当前节点。每个节点的一个随机数就足够了：

int r = rand() % size(this);
if (r < size(left)) { /* go left */ }
else if (r > size(left)) { /* go right */ }
else { /* pick this node */ }

事实上，通过一些调整，您可能可以向下传递一个随机数，以便在每个节点上使用。经过一番思考，是的，您可以：如果您向左走，请使用r未修改的；如果你走对了，减去(size(left) - 1)。r

对于正态分布，只需使用一个平均值为一半深度的正态分布随机变量来预先选择要走多深，然后回退到上面的算法。请注意，这将根据子树的相对大小在中间节点之间分布，而不是均匀分布。