1

我有两种算法用于在树中返回一个随机节点，其中一个节点可以有 0-N 个子节点（当前节点是node，节点的第一个子节点是node[1]等）。第一个算法，统一选择，从树中统一选择一个随机节点。它存储一个要返回的节点，当它沿着树向下移动时，这个节点被替换为它当前所在的节点，概率为 1/（到目前为止看到的节点数）。Lua 代码如下。

function uniformSelect(node)
    local chosen = node

    function choose(node, counter)
        counter = counter + 1
        local probability = 1/counter
        if math.random() < probability then
            chosen = node
        end

        for i = 1, node.arity do
            choose(node[i], counter)
        end
    end

    choose(node, 0)
    return chosen
end

第二个算法沿着树向下移动，查看它当前所在的节点并以给定的概率 P 返回它。如果没有返回这个节点，那么移动到节点的子节点的概率是 P1, P2 ... PN最多 1. Lua 代码如下。

function select(node, prob)
    local r = math.random()
    if r < prob or node.arity == 0 then
        return node
    end

    local p = {}
    if node.arity == 1 then
        table.insert(p, 1)
    else
        local total = count(node) -- total number of nodes below this one
        for i = 1, node.arity do
            -- insert probability of moving to child i into p
            table.insert(p, (count(node[i])+1)/total)
        end

    end
    -- move to a child node chosen by roulette wheel selection
    return select(node[roulette(p)], prob)
end

这些算法用于遗传编程框架。当我使用第一个算法，统一选择时，它首先在速度和内存方面运行良好。然而，第二个不能用于多代的大量人口，它使用的内存会爆炸。我在下面绘制了这种内存增长，蓝线“prob”是第二种算法，select.

内存使用

对我来说，select看起来它是尾递归的。我还尝试明确调用垃圾收集器，看看是否有帮助，它会稍微减慢增长，但增长仍然很大。

谁能告诉我造成这种差异的原因是什么？

4

1 回答 1

1

我绘制了正在生产的树木的平均深度并找到了答案。与函数的交叉操作select增加了种群中树的平均深度，导致程序变慢并使用更多的内存。

在此处输入图像描述

于 2013-03-22T23:27:14.893 回答