1

ノードが0〜Nの子を持つことができるツリーでランダムノードを返すための2つのアルゴリズムがあります（現在のノードは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

2 番目のアルゴリズムは、ツリーを下に移動し、現在のノードを調べて、指定された確率 P でそれを返します。このノードが返されない場合、ノードの子に移動する確率は P1、P2 ... PN であり、これを追加します。以下の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

これらのアルゴリズムは、遺伝的プログラミング フレームワークで使用されます。最初のアルゴリズムである一様選択を使用すると、最初は速度とメモリの点で問題なく動作します。ただし、2 番目のものは、何世代にもわたる大規模な集団では使用できず、使用するメモリが爆発します。このメモリの増加を以下にグラフ化しました。青い線の「prob」は 2 番目のアルゴリズムですselect。

メモリ使用量

私にselectは、末尾再帰のように見えます。また、ガベージ コレクターを明示的に呼び出して、それが役立つかどうかを確認してみました。成長がわずかに遅くなりますが、成長は依然として大規模です。

この違いの原因を誰か教えてもらえますか?

4

1 に答える 1

1

生産されている木の平均的な深さをグラフにして、答えを見つけました。関数を使用したクロスオーバー操作によりselect、母集団内のツリーの平均深度が増加し、プログラムの速度が低下し、より多くのメモリが使用されます。

ここに画像の説明を入力

于 2013-03-22T23:27:14.893 に答える