1前書き

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

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

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


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

  • 遺伝的アルゴリズムは進化的コンピューティング** の一部であり、進化し続ける人工知能分野です。

アルゴリズムは、

母集団

と呼ばれる

一連の解



個体

で表される)で始まります。新しい母集団が古い母集団よりも優れている可能性があるので、1つの母集団からの解が取り出され、

新しい母集団

を形成するために使用されます。

新しい解決法(

子孫

)を形成するために選ばれた個人は、その

適応度

に従って選択されます。


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

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


3.1. 初期化

初期化ステップでは、最初の解決策として役立つランダムなPopulationを生成します。最初に、

Population

がどのくらい大きくなるか、そして私たちが期待する最終的な解決策は何かを決める必要があります。

SimpleGeneticAlgorithm.runAlgorithm(50,
  "1011000100000100010000100000100111001000000100000100000000001111");

上記の例では、

Population

sizeは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++;
}

私たちがどのようにして最適な

個別

を得るかを説明することから始めましょう。

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つの個別のオブジェクトを少しずつ比較します。完璧な解決策が見つからない場合は、次のステップに進む必要があります。それは

Population

の進化です。


3.3. 子孫

このステップでは、新しい

Population

を作成する必要があります。まず、

Populationから2つの親

Individual

オブジェクトを、それらの適応度に従って

選択

する必要があります。現在の世代からの最善の

個別の__を、変更されずに次の世代に引き継ぐことを許可することが有益であることに注意してください。この戦略は

エリート主義と呼ばれます。

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

2つの最良の

個別のオブジェクトを選択するために、


https://en.wikipedia.org/wiki/Tournament



selection[トーナメント選択戦略] を適用します。

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;
}

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

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);
        }
    }
}

ミューテーションとクロスオーバーのすべてのタイプは、このチュートリアルではhttp://www.obitko.com/tutorials/genetic-algorithms/crossover-mutation.phpにうまく説明されています。

その後、終了条件、たとえば最善の解決策に達するまで、3.2項および3.3項からの手順を繰り返します。


4ヒントとコツ

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


  • クロスオーバー率



    80%-95%程度


  • 突然変異率



    0.5%-1%

    前後の非常に低い値です。


  • 人口の大きさ

    – よい人口の大きさは

    20-30

    ですが、

いくつかの問題ではサイズ50-100が良い


選択** – 基本


https://en.wikipedia.org/wiki/Fitness


proportionate

selection[

roulette
ホイール選択

]は

elitism

の概念で使用することができます


クロスオーバーと突然変異の種類** – それはエンコーディングと問題によります

チューニングの推奨事項は、多くの場合、遺伝的アルゴリズムに関する実証的研究の結果であり、提案された問題に基づいて変わる可能性があります。


5結論

このチュートリアルは遺伝的アルゴリズムの基本を紹介します。あなたは遺伝的アルゴリズムについて学ぶことができます

この分野の予備知識

なしで、基本的なコンピュータープログラミングスキルのみ。

このチュートリアルのコードスニペットの完全なソースコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-genetic[GitHubプロジェクトで入手可能]です。

ゲッターとセッターを生成するためにhttps://projectlombok.org/[Lombok]を使用することにも注意してください。 IDEリンク:/intro-to-project-lombok(この記事の中)でそれを正しく設定する方法を確認できます。

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

  • 遺伝的アルゴリズムを設計する方法? (これです)

  • link:/巡回セールスマンのためのjavaシミュレートアニーリング

Javaのセールスマン問題]