はじめに

この記事はGA(遺伝的アルゴリズム)をUnityで実装しようとした話 #1 の続きです。
ご覧になっていない方はぜひそちらからご覧ください。

#1 →　

前回の内容とその解決法の話

前回先生と相談した際に解決策を提案していただいて

もっと交叉数を増やしてみてはどうか
突然変異の数or発生数を増やすべきではないか
要素を分割し、それぞれを遺伝的アルゴリズムで実装したらいいのでは

といった点が挙げられました。

これらを実行してみたのですが...
結論から述べると 解決できませんでした...
結局「似た個体のみが生成され良い個体がほぼ生まれない」が解決されませんでした。

そこで遺伝的アルゴリズムのこの問題を解決できないか調べていたところ...

ただし、選択アルゴリズムを使うと初期収束の原因になったり
高い適応度の個体を残し過ぎると解の多様性が失われるなどの問題がある。
といった文面を発見。

これだなあ...
現在の選択は上位2つを抜き出していた。
これらから次世代を作成していたため、多様性がなくなっていたことが分かった。
上位2つを抜き出せばエリート選択みたいになるし大丈夫だと思ってたけどダメっぽい。

選択の問題の解決

ということで解決策を実装してみた

List<int> roulette = new List<int>();

for (int i = 0;i < 4;i++)
{
    for (int j = 0;j < geneScores[i]; jj++)
    {
        roulette.Add(i);
    }
}

no1 = roulette[UnityEngine.Random.Range(0, roulette.Count)];

while(true)
{
    no2 = roulette[UnityEngine.Random.Range(0, roulette.Count)];

    if (no1 != no2) break;
}

これで有利な要素を残しやすくなるルーレット選択にできたはず。
ただこれはこれで有利な要素が淘汰されるといった問題も抱えていた。

なので

List<int> roulette = new List<int>();

for (int j = 0;j < 4;j++)
{
    if (geneScores[j] == geneScores[no1])
    {
        int rand = UnityEngine.Random.Range(0,2);
        if (rand == 0) no1 = j;
    }
    else if (geneScores[j] > geneScores[no1])
    {
        no1 = j;
    }

    for (int k = 0;k < geneScores[j]; k++)
    {
        for (int l = 0;l < geneScores[j] * 10; l++)
        {
            roulette.Add(j);
        }
    }
}

while(true)
{
    no2 = roulette[UnityEngine.Random.Range(0, roulette.Count)];

    if (no1 != no2) break;
}

このように修正してみた。
最大値を必ず残すように直し、また交叉によって同じ水準の個体が作られた際も、50%の確率で残すようにした。
これでほぼ常に同じ個体で交叉を行うことを避けることに成功しました。

完成形

// 初期要素作成
for (int i = 0; i < 4; i++)
{
    UnityEngine.Random.InitState(DateTime.Now.Millisecond + i);

    pointsCopy = new List<Vector2Int>(points);
    genes.Add(new byte[100]);
    for (int j = 0; j < 100; j+)
    {
        genes[i][j] = (byte)UnityEngine.Random.Range(0, 4);
    }
}

for (int i = 0; i < roop; i++)
{
    // 適応度評価
    for (int j = 0;j < 4;j++)
    {
        position = new Vector2Int(5,5);
        pointsCopy = new List<Vector2Int>(points);
        geneScores[j] = 0;

        for (int k = 0;k < 100;k++)
        {
            Vector2Int moveValue = new Vector2Int();

            switch (genes[j][k])
            {
                case 0: moveValue = Vector2Int.left; break;
                case 1: moveValue = Vector2Int.right; break;
                case 2: moveValue = Vector2Int.down; break;
                case 3: moveValue = Vector2Int.up; break;
            }

            position = new Vector2Int(Mathf.Clamp(position.x + moveValue.x,0,9),Mathf.Clamp(position.y + moveValue.y,0,9));

            int searchIndex = pointsCopy.IndexOf(position);
            if (searchIndex < 0) continue;

            pointsCopy.RemoveAt(searchIndex);
            geneScores[j]++;

            if (pointsCopy.Count >= 1) continue;
            geneScores[j] += (byte)(100 - k);
            break;
        }
    }
    
    // 選択
    List<int> roulette = new List<int>();

    for (int j = 0;j < 4;j++)
    {
        if (geneScores[j] == geneScores[no1])
        {
            int rand = UnityEngine.Random.Range(0,2);
            if (rand == 0) no1 = j;
        }
        else if (geneScores[j] > geneScores[no1])
        {
            no1 = j;
        }

        for (int k = 0;k < geneScores[j]; k++)
        {
            for (int l = 0;l < geneScores[j] * 10; l++)
            {
                roulette.Add(j);
            }
        }
    }

    while(true)
    {
        no2 = roulette[UnityEngine.Random.Range(0, roulette.Count)];

        if (no1 != no2) break;
    }

    // 交叉(2点交叉)
    bool swap = false;

    for (int J = 0;J < 4;J++)
    {
        int randA = UnityEngine.Random.Range(0, 98);
        int randB = UnityEngine.Random.Range(randA + 1, 100);

        for (int j = 0; j < 4; j++)
        {
            if (no1 == j || no2 == j) continue;

            byte swapValue = 0;

            if (swap)
            {
                for (int k = 0; k < 100; k++)
                {
                    if (k >= randA && k <= randB)
                    {
                        swapValue = genes[no1][k];
                    }
                    else
                    {
                        swapValue = genes[no2][k];
                    }

                    genes[j][k] = swapValue;
                }
            }
            else
            {
                swap = true;

                for (int k = 0; k < 100; k++)
                {
                    if (k >= randA && k <= randB)
                    {
                        swapValue = genes[no2][k];
                    }
                    else
                    {
                        swapValue = genes[no1][k];
                    }

                    genes[j][k] = swapValue;
                 }
              }
        }
    }
    
    //突然変異
    if (i % 5 == 0)
    {
        for (int j = 0; j < 4; j++)
        {
            if (j == no1 || j == no2) continue;

            UnityEngine.Random.InitState(DateTime.Now.Millisecond + j);

            for (int k = 0;k < 5;k++)
            {
                int randIndex = UnityEngine.Random.Range(0,100);
                genes[j][randIndex] = (byte)UnityEngine.Random.Range(0,4);
            }
        }
    }
}

終わりに

これでひとまず完成です。
まだ完全なルートを生み出すには至りませんが、より良いルートを検索しながらできるようになったので、ループ回数でどうにかなるものだと思われます。
もうちょっとやりたかったけど忙しいので今回はここまで
いずれはAIとか作ってみたいなあ