5

遺伝的アルゴリズムを使用して 4 x 4 数独ソルバーを構築しようとしています。極小値に収束する値に問題があります。ランク付けされたアプローチを使用して、ランク付けされた下位 2 つの回答の可能性を削除し、ランク付けされた上位 2 つの回答の可能性の間のクロスオーバーに置き換えます。局所最小値を回避するための追加のヘルプとして、突然変異も使用しています。特定の世代内で答えが決定されない場合、私の母集団はまったく新しいランダムな状態値で満たされます。ただし、私のアルゴリズムは極小値で動けなくなっているようです。フィットネス関数として、私は以下を使用しています:

(開いている四角の合計数 * 7 (各四角、行、列、およびボックスでの違反の可能性)) - 違反の合計

集団は整数配列の ArrayList であり、各配列は入力に基づく数独の可能な最終状態です。適応度は、母集団内の各配列について決定されます。

私のアルゴリズムが極小値に収束する理由を判断するのを手伝ってくれる人や、極小値を回避するために使用する手法を推奨してくれる人がいますか? どんな助けでも大歓迎です。

フィットネス機能:

public int[] fitnessFunction(ArrayList<int[]> population)
{
    int emptySpaces = this.blankData.size();
    int maxError = emptySpaces*7;
    int[] fitness = new int[populationSize];

    for(int i=0; i<population.size();i++)
    {
        int[] temp = population.get(i);
        int value = evaluationFunc(temp);

        fitness[i] = maxError - value;
        System.out.println("Fitness(i)" + fitness[i]);
    }

    return fitness;
}

クロスオーバー機能:

public void crossover(ArrayList<int[]> population, int indexWeakest, int indexStrong, int indexSecStrong, int indexSecWeak)
{
    int[] tempWeak = new int[16];
    int[] tempStrong = new int[16];
    int[] tempSecStrong = new int[16];
    int[] tempSecWeak = new int[16];

    tempStrong = population.get(indexStrong);
    tempSecStrong = population.get(indexSecStrong);
    tempWeak = population.get(indexWeakest);
    tempSecWeak = population.get(indexSecWeak);
    population.remove(indexWeakest);
    population.remove(indexSecWeak);


    int crossoverSite = random.nextInt(14)+1;

    for(int i=0;i<tempWeak.length;i++)
    {
        if(i<crossoverSite)
        {
            tempWeak[i] = tempStrong[i];
            tempSecWeak[i] = tempSecStrong[i];
        }
        else
        {
            tempWeak[i] = tempSecStrong[i];
            tempSecWeak[i] = tempStrong[i];
        }
    }
    mutation(tempWeak);
    mutation(tempSecWeak);
    population.add(tempWeak);
    population.add(tempSecWeak);

    for(int j=0; j<tempWeak.length;j++)
    {
        System.out.print(tempWeak[j] + ", ");
    }
    for(int j=0; j<tempWeak.length;j++)
    {
        System.out.print(tempSecWeak[j] + ", ");
    }
}

変異機能:

public void mutation(int[] mutate)
{
    if(this.blankData.size() > 2)
    {
        Blank blank = this.blankData.get(0);
        int x = blank.getPosition();

        Blank blank2 = this.blankData.get(1);
        int y = blank2.getPosition();

        Blank blank3 = this.blankData.get(2);
        int z = blank3.getPosition();

        int rando = random.nextInt(4) + 1;

        if(rando == 2)
        {
            int rando2 = random.nextInt(4) + 1;
            mutate[x] = rando2;
        }
        if(rando == 3)
        {
            int rando2 = random.nextInt(4) + 1;
            mutate[y] = rando2;
        }
        if(rando==4)
        {
            int rando3 = random.nextInt(4) + 1;
            mutate[z] = rando3;
        }
    }
4

2 に答える 2

10

急速な収束が見られるのは、「交配」の方法論があまり良くないためです。スコア上位 2 個体の「交配」から常に 2 匹の子孫を生み出しています。新しい子孫の 1 つがあなたの最上位の個体と同じである場合に何が起こるか想像してみてください (たまたま、交叉も突然変異もなく、または少なくともフィットネスに影響を与えるものもありません)。これが発生すると、上位 2 人の個人が同一になり、クロスオーバーの有効性がなくなります。

より典型的なアプローチは、すべての世代ですべての個人を置き換えることです。ここにはさまざまなバリエーションが考えられますが、2 つの親の重み付けフィットネスをランダムに選択することもできます。

人口規模について: 遺伝的表現と適応度関数を考えると数独の問題がどれほど難しいかはわかりませんが、数十ではなく数百万の個体について考えるようお勧めします。

非常に難しい問題に取り組んでいる場合、集団を 2 次元グリッドに配置し、近くの個体からグリッド内の各ポイントの「親」を選択すると、遺伝的アルゴリズムがはるかに効果的になります。局所的な収束が得られますが、各局所性は異なる解に収束します。グリッドの局所的に収束した領域間の境界から生成される膨大な量の変動が得られます。

考えるかもしれない別の手法は、ランダムな母集団から収束するまで何度も実行し、各実行から上位の個体を保存することです。さまざまな極小ゲノムの束を構築した後、それらのトップ個体から新しいランダム集団を構築します。

于 2014-11-18T04:35:46.100 に答える
0

数独は順列問題だと思います。したがって、人口の初期化にランダムな順列番号を使用し、順列問題に対応するクロスオーバー法を使用することをお勧めします。

于 2014-11-24T12:48:34.640 に答える