1. 序章

このシリーズの目的は、遺伝的アルゴリズムの概念を説明することです。

遺伝的アルゴリズムは、自然界と同じプロセスを使用して問題を解決するように設計されています。つまり、選択、組換え、突然変異の組み合わせを使用して、問題の解決策を進化させます。

最も単純なバイナリ遺伝的アルゴリズムの例を使用して、これらのアルゴリズムの概念を説明することから始めましょう。

2. 遺伝的アルゴリズムのしくみ

遺伝的アルゴリズムは、急速に成長している人工知能の分野である進化的計算の一部です。

アルゴリズムは、母集団と呼ばれるソリューションのセット個人で表される)から始まります。 新しい母集団が古い母集団よりも優れている可能性があるため、1つの母集団からの解が取得され、新しい母集団を形成するために使用されます。

新しいソリューション(子孫)を形成するために選択された個人は、適合性に従って選択されます。適切であるほど、再現する必要があります。

3. バイナリ遺伝的アルゴリズム

簡単な遺伝的アルゴリズムの基本的なプロセスを見てみましょう。

3.1. 初期化

初期化ステップでは、最初のソリューションとして機能するランダムな母集団を生成します。 まず、人口の大きさと、予想される最終的な解決策を決定する必要があります。

SimpleGeneticAlgorithm.runAlgorithm(50,
  "1011000100000100010000100000100111001000000100000100000000001111");

上記の例では、 Population のサイズは50であり、正しい解は、いつでも変更できるバイナリビット文字列で表されます。

次のステップでは、目的のソリューションを保存し、ランダムなPopulationを作成します。

setSolution(solution);
Population myPop = new Population(populationSize, true);

これで、プログラムのメインループを実行する準備が整いました。

3.2. フィットネスチェック

プログラムのメインループでは、適応度関数によって各個人を評価します(簡単に言うと、個人が優れているほど、適応度関数の値が高くなります。 )::

while (myPop.getFittest().getFitness() < getMaxFitness()) {
    System.out.println(
      "Generation: " + generationCount
      + " Correct genes found: " + myPop.getFittest().getFitness());
    
    myPop = evolvePopulation(myPop);
    generationCount++;
}

どのようにして最も適切なIndividualを取得するかを説明することから始めましょう。

public int getFitness(Individual individual) {
    int fitness = 0;
    for (int i = 0; i < individual.getDefaultGeneLength()
      && i < solution.length; i++) {
        if (individual.getSingleGene(i) == solution[i]) {
            fitness++;
        }
    }
    return fitness;
}

観察できるように、2つのIndividualオブジェクトを少しずつ比較します。 完璧な解決策が見つからない場合は、次のステップに進む必要があります。これは、人口の進化形です。

3.3. 子孫

このステップでは、新しいPopulationを作成する必要があります。 まず、母集団から2つの親個々のオブジェクトを選択する必要があります。 現在の世代の最高のIndividualを、変更せずに次の世代に引き継ぐことができると便利であることに注意してください。 この戦略はエリート主義と呼ばれます:

if (elitism) {
    newPopulation.getIndividuals().add(0, pop.getFittest());
    elitismOffset = 1;
} else {
    elitismOffset = 0;
}

2つの最高のIndividualオブジェクトを選択するために、トーナメント選択戦略を適用します。

private Individual tournamentSelection(Population pop) {
    Population tournament = new Population(tournamentSize, false);
    for (int i = 0; i < tournamentSize; i++) {
        int randomId = (int) (Math.random() * pop.getIndividuals().size());
        tournament.getIndividuals().add(i, pop.getIndividual(randomId));
    }
    Individual fittest = tournament.getFittest();
    return fittest;
}

各トーナメントの勝者(最高のフィットネスを持つトーナメント)が次のステージ、つまりCrossoverに選ばれます。

private Individual crossover(Individual indiv1, Individual indiv2) {
    Individual newSol = new Individual();
    for (int i = 0; i < newSol.getDefaultGeneLength(); i++) {
        if (Math.random() <= uniformRate) {
            newSol.setSingleGene(i, indiv1.getSingleGene(i));
        } else {
            newSol.setSingleGene(i, indiv2.getSingleGene(i));
        }
    }
    return newSol;
}

クロスオーバーでは、ランダムに選択されたスポットで、選択された各Individualからビットを交換します。 プロセス全体は、次のループ内で実行されます。

for (int i = elitismOffset; i < pop.getIndividuals().size(); i++) {
    Individual indiv1 = tournamentSelection(pop);
    Individual indiv2 = tournamentSelection(pop);
    Individual newIndiv = crossover(indiv1, indiv2);
    newPopulation.getIndividuals().add(i, newIndiv);
}

ご覧のとおり、クロスオーバー後、新しい子孫を新しいPopulationに配置します。 このステップは受け入れと呼ばれます。

最後に、Mutationを実行できます。 突然変異は、人口のある世代から次の世代への遺伝的多様性を維持するために使用されます。 ビット反転タイプのミューテーションを使用しました。ここでは、ランダムビットが単純に反転されます。

private void mutate(Individual indiv) {
    for (int i = 0; i < indiv.getDefaultGeneLength(); i++) {
        if (Math.random() <= mutationRate) {
            byte gene = (byte) Math.round(Math.random());
            indiv.setSingleGene(i, gene);
        }
    }
}

このチュートリアルでは、すべてのタイプのミューテーションとクロスオーバーがうまく説明されています

次に、サブセクション3.2と3.3の手順を繰り返して、終了条件(たとえば、最良の解決策)に到達します。

4. ヒントとコツ

効率的な遺伝的アルゴリズムを実装するには、一連のパラメーターを調整する必要があります。 このセクションでは、最も重要なパラメータから始めるための基本的な推奨事項をいくつか示します。

  • クロスオーバー率–それは高くなければなりません。約 80 %-95%
  • 変異率–非常に低く、 0.5%-1%前後である必要があります。
  • 母集団のサイズ–適切な母集団のサイズは約 20-30 ですが、一部の問題では50〜100のサイズの方が適しています
  • 選択–基本的なルーレットホイール選択は、エリート主義の概念で使用できます。
  • クロスオーバーとミューテーションタイプ–エンコーディングと問題によって異なります

調整の推奨事項は、遺伝的アルゴリズムに関する経験的研究の結果であることが多く、提案された問題に基づいて異なる場合があることに注意してください。

5. 結論

このチュートリアルは、遺伝的アルゴリズムの基礎を紹介します。 この分野の予備知識がなくても遺伝的アルゴリズムについて学ぶことができ、基本的なコンピュータープログラミングスキルしかありません。

このチュートリアルのコードスニペットの完全なソースコードは、GitHubプロジェクト利用できます。

また、Lombokを使用してゲッターとセッターを生成していることにも注意してください。 この記事で、IDEで正しく構成する方法を確認できます。

遺伝的アルゴリズムのさらなる例については、私たちのシリーズのすべての記事をチェックしてください: