遺伝的アルゴリズムの基本概念と実装（Java 実装例付き）

上図（左）に示すように、個体が複数の染色体で構成され、各染色体が複数の遺伝子で構成されている場合に遺伝的アルゴリズムが使用されます。上の図（右）は染色体がどのように分割され、結合されるかを示しています。

自然選択の概念

自然選択のプロセスは、グループ内の環境に最も適応した個体を選択することから始まります。子孫は親の特徴を継承し、その特徴は次の世代に追加されます。親の適応度が高ければ、その子孫が生き残る可能性が高くなります。この自然選択のプロセスを繰り返し実行することで、最終的には環境に最も適応した個体で構成される世代が得られます。

この概念は検索問題に適用できます。私たちは問題に対する多くの解決策を検討し、最善のものを探します。

遺伝的アルゴリズムは次の 5 つのステップで構成されます。

初期化
個別評価（適応度関数の計算）
操作を選択
クロスオーバー操作
突然変異操作

初期化

このプロセスは、集団内の個体の集合から始まります。各個体は、解決すべき問題に対する候補となる解決策です。

個体は遺伝子と呼ばれる一連のパラメータ（変数）によって特徴付けられ、遺伝子が連結されて染色体（問題の解決策）を形成します。

遺伝的アルゴリズムでは、単一の個体のゲノムは文字列の形式で表されます。通常はバイナリ (1 と 0 の文字列) エンコーディングを使用できます。つまり、バイナリ文字列は染色体文字列を表します。したがって、遺伝子列または候補ソリューションの特性を染色体にエンコードしていると言えます。

集団、染色体、遺伝子

個別評価（適応度関数の計算）

個体評価では、適応度関数を使用して、個体の環境への適応度 (他の個体と競争する能力) を評価します。各個体には適応度スコアがあり、個体が繁殖のために選択される可能性はその適応度スコアによって決まります。適合関数の値が大きいほど、ソリューションの品質が高くなります。適応度関数は遺伝的アルゴリズムの進化の原動力であり、自然選択の唯一の基準です。適応度関数の設計は、解決する問題の要件に基づいて行う必要があります。

操作を選択

選択操作の目的は、最も適応度の高い個体を選択し、その遺伝子を次の世代に受け継ぐことです。適応度スコアに基づいて、優れた個体（親）のペアを複数選択します。適応度の高い個体は、繁殖のために選択される可能性、つまり、より優れた親の遺伝子を次の世代に伝える可能性が高くなります。

クロスオーバー操作

交差操作は遺伝的アルゴリズムにおいて最も重要な段階です。それぞれの親のペアごとに、遺伝子にはランダムに選択された交差ポイントがあります。

例えば、次の図の交点は 3 です。

子孫は、交差点の前に親の間で遺伝子が交換されることによって生成されます。

親の間で遺伝子が交換され、その結果生まれた新しい子孫が集団に加えられます。

突然変異操作

新たに形成された子孫の中には、その遺伝子の一部が低確率の突然変異因子の影響を受けるものもあるかもしれません。これは、バイナリビット文字列の一部のビットが反転される可能性があることを意味します。

突然変異操作の前後

突然変異操作は、集団内の多様性を維持し、早期の収束を防ぐために使用できます。

終了

アルゴリズムは、集団が収束すると終了します (集団内に前の世代と大きく異なる子孫が生成されなくなります)。つまり、遺伝的アルゴリズムは一連の問題に対する解決策を提供します。
ケース実装

人口の規模は一定です。新しい世代が形成されると、適応度の最も低い個体は、次の世代のために場所を空けるために死にます。これらの段階のシーケンスが何度も繰り返され、以前の世代よりも優れた新しい世代が生み出されます。

この反復プロセスの疑似コード:

始める
初期人口を生成する
フィットネスを計算する
繰り返す
 選択
 クロスオーバー
 突然変異
 フィットネスを計算する
人口が収束するまで
停止

Javaでの実装例

以下は、Java での遺伝的アルゴリズムのサンプル実装です。自由にコードをデバッグおよび変更できます。 5 つの遺伝子のセットがある場合、各遺伝子は 0 または 1 のバイナリ値を保持できます。ここでの適応度はゲノム内の 1 の数です。ゲノムに 1 が 5 つある場合、個体の適応度は最大値に達します。ゲノムに1がない場合、個体の適応度は最小になります。遺伝的アルゴリズムは、適応度を最適化し、最も高い適応度を持つ個体で構成されるグループを提供することを目的としています。注: この例では、交差と突然変異の操作の後、最も適応度の高い個体が、最も適応度の高い新しい子孫に置き換えられます。

java.util.Random をインポートします。

 /**
 *
 * @author ヴィジニ
 */

 //メインクラス
パブリッククラスSimpleDemoGA {

 人口 population = new Population();
 適者生存;
 個々のsecondFittest;
 世代カウント = 0;

 パブリック静的voidメイン(String[] args) {

 ランダム rn = new Random();

 SimpleDemoGA デモ = 新しい SimpleDemoGA();

 //人口を初期化する
 デモ.population.initializePopulation(10);

 //各個体の適応度を計算する
 デモ: 人口統計を計算します。

 System.out.println("世代: " + demo.generationCount + " 適合度: " + demo.population.fittest);

 //集団は最大の適応度を持つ個体を獲得する
 (demo.population.fittest < 5) の間 {
 ++デモ.世代数;

 //選択を行う
 デモ.選択();

 //クロスオーバーを行う
 デモ.クロスオーバー();

 //ランダムな確率で突然変異を行う
 （rn.nextInt()%7 < 5）の場合{
 デモ.mutation();
 }

 //最も適応した子孫を集団に追加する
 デモ:

 //新しい適合度値を計算
 デモ: 人口統計を計算します。

 System.out.println("世代: " + demo.generationCount + " 適合度: " + demo.population.fittest);
 }

 System.out.println("\n世代 " + demo.generationCount で解決策が見つかりました);
 System.out.println("フィットネス: "+demo.population.getFittest().fitness);
 System.out.print("遺伝子: ");
 (int i = 0; i < 5; i++) の場合 {
 System.out.print(demo.population.getFittest().genes[i]);
 }

 System.out.println("");

 }

 //選択
 void 選択() {

 //最も適応度の高い個体を選択する
 人口統計

 // 2番目に適応度の高い個体を選択する
 人口統計データ
 }

 //クロスオーバー
 void クロスオーバー() {
 ランダム rn = new Random();

 //ランダムなクロスオーバーポイントを選択する
 int crossOverPoint = rn.nextInt(population.individuals[0].geneLength);

 //親の間で値を交換
 (int i = 0; i < クロスオーバーポイント; i++) {
 temp = fittest.genes[i];
 fittest.genes[i] = secondFittest.genes[i];
 secondFittest.genes[i] = temp;

 }

 }

 //突然変異
 void ミューテーション() {
 ランダム rn = new Random();

 //ランダムな突然変異点を選択する
 int 変異ポイント = rn.nextInt(population.individuals[0].geneLength);

 //突然変異ポイントで値を反転する
 （fittest.genes[mutationPoint] == 0）の場合{
 fittest.genes[変異ポイント] = 1;
 } それ以外 {
 fittest.genes[変異ポイント] = 0;
 }

 変異ポイント = rn.nextInt(population.individuals[0].geneLength);

 if (secondFittest.genes[mutationPoint] == 0) {
 secondFittest.genes[変異ポイント] = 1;
 } それ以外 {
 secondFittest.genes[変異ポイント] = 0;
 }
 }

 //最も適応力のある子孫を得る
 個体 getFittestOffspring() {
 （fittest.fitness > secondFittest.fitness）の場合{
 最も適したものを返します。
 }
 secondFittest を返します。
 }


 //最も適応度の低い個体を最も適応度の高い子孫から置き換える
 void addFittestOffspring() {

 //子孫の適応度値を更新する
 fittest.calcFitness();
 計算フィットネス();

 //最も適合度の低い個体のインデックスを取得する
 最小適合指数 = population.getLeastFittestIndex();

 //最も適応度の低い個体を最も適応度の高い子孫から置き換える
 population.individuals[leastFittestIndex] = getFittestOffspring();
 }

 }


 //個別のクラス
クラス 個人 {

 int フィットネス = 0;
 int[] 遺伝子 = 新しい int[5];
 int 遺伝子の長さ = 5;

 パブリック個人() {
 ランダム rn = new Random();

 //各個体の遺伝子をランダムに設定する
 (int i = 0; i < genes.length; i++) の場合 {
 遺伝子[i] = rn.nextInt() % 2;
 }

 フィットネス = 0;
 }

 //フィットネスを計算する
 パブリック void calcFitness() {

 フィットネス = 0;
 (int i = 0; i < 5; i++) の場合 {
 遺伝子[i] == 1の場合{
 ++フィットネス;
 }
 }
 }

 }

 //人口クラス
クラス人口 {

 整数ポップサイズ = 10;
 個体[] 個体 = 新しい個体[10];
 int 適合度 = 0;

 //人口を初期化する
 パブリック void 初期化人口 (int サイズ) {
 (int i = 0; i < 個人.長さ; i++) {
 個人[i] = 新しい個人();
 }
 }

 //最も適応度の高い個体を取得する
 パブリック個人 getFittest() {
 int maxFit = Integer.MIN_VALUE;
 (int i = 0; i < 個人.長さ; i++) {
 （maxFit <= 個人[i].fitness）の場合{
 最大フィット = i;
 }
 }
 最も適している = 個人[maxFit].fitness;
 個体[maxFit]を返します。
 }

 // 2番目に適応度の高い個体を取得する
 パブリック個人 getSecondFittest() {
 整数maxFit1 = 0;
 整数maxFit2 = 0;
 (int i = 0; i < 個人.長さ; i++) {
 （個人[i].フィットネス > 個人[maxFit1].フィットネス）{
 最大フィット2 = 最大フィット1;
 最大フィット1 = i;
 } そうでない場合 (individuals[i].fitness > individuals[maxFit2].fitness) {
 最大フィット2 = i;
 }
 }
 個体[maxFit2]を返します。
 }

 //最も適合度の低い個体のインデックスを取得する
 パブリック int getLeastFittestIndex() {
 最小フィット = 0;
 (int i = 0; i < 個人.長さ; i++) {
 minFit >= 個人[i].適応度)の場合{
 最小フィット = i;
 }
 }
 minFit を返します。
 }

 //各個体の適応度を計算する
 パブリック void 計算フィットネス() {

 (int i = 0; i < 個人.長さ; i++) {
 個人[i].calcFitness();
 }
 getFittest();
 }

 }