3 日前読了時間: 9分

Processing 遺伝的アルゴリズム

こんにちは、NUMです。

今回はProcessingで遺伝的アルゴリズムを実装していきます。

昨今AIが普及していますが、生物界のアルゴリズムも進化アルゴリズムというジャンルで

AIのモデルに組み込まれているそうです。今回は遺伝的アルゴリズムの仕組みを解明していこうと思います。

目次

生物の進化
概要
実装
まとめ

生物の進化

同じ種でも見た目が異なる動物が沢山います。これは環境に適応するために独自の進化を遂げた結果になります。

生物の性質は「遺伝⼦」によって決まり、親となる2個体の染色体が「交叉」することで

遺伝子が交わりそれぞれの特徴が子に受け継がれます。

生物は個体間で競争(餌、生殖、魅力など)に勝ち残った個体が次世代に子孫を残せます。子供は優れた遺伝子を持つので、競争に勝つ確率も当然高まるわけです。つまり世代が進むほど、何かしらの特徴が色濃く残ります。

ただし「突然変異」という可能性もあり、より環境に適応した個体が生まれる可能性もあれば、その逆もあります。

「遺伝子」「交叉」「選択（環境に適応した個体）」「突然変異」という生物進化のメカニズムを最適化問題に応用したアルゴリズムを遺伝的アルゴリズムと言います。

今回は毎度お馴染みNature Of Codeのプログラムを参考に遺伝的アルゴズムを実装していきます。

概要

このプログラムでは個体はメンバ変数として文字列を持ち、

ターゲット文字列「to be or not to be」に近いほど適応度が高いとします。

個体同士が交叉すると次世代には親の文字列が子に受け継がれる仕組みを実装していきます。

個体生成：ランダムな文字列を保持
適応度評価：ターゲット文字列との類似度を評価
選択：トーナメント選択による親の選定
交叉：親の遺伝子を組み合わせて子孫を生成
突然変異：遺伝的多様性を維持するためにランダムな遺伝子変更

実装

Main：


String target = "to be or not to be"; // ターゲット文字列
char[] targetArr; // ターゲット文字列配列
int populationSize = 100; //個体群数
DNA[] population; // 個体群
DNA[] nextPopulation; // 次世代個体群
ArrayList<DNA> mattingPool; // 交配プール
float mutationRate = 0.01; // 突然変異率

void setup() {
  initialize(); // 初期化処理
  evolve(1000); // 進化のシミュレーション
}

/**
 * ターゲット文字列の配列、初期個体群の生成
 */
void initialize(){
  // 配列化することで文字を処理しやすくする
  targetArr = new char[target.length()];
  for (int i = 0; i < targetArr.length; i++) {
    targetArr[i] = target.charAt(i);
  }
  
  // 初期個体群の生成
  population = new DNA[populationSize];
  for (int i = 0; i < populationSize; i++) {
    population[i] = new DNA();
    population[i].randomizeGenes();
    population[i].calculateFitness();
  }
}

/**
 * 遺伝的アルゴリズムの主要な進化プロセスを実行
 * 指定世代まで、または最適解が見つかるまで進化を続ける
 * 
 * @param 指定世代
 */
void evolve(int maxGeneration) {
  for (int generation = 0; generation < maxGeneration; generation++) {
    // 交配プールの作成
    mattingPool = new ArrayList<DNA>();
    createMattingPool();
    
    // 次世代の個体群生成
    nextPopulation = new DNA[populationSize];
    for (int i = 0; i < populationSize; i++) {
      // 親の選択とランダム交配
      DNA parentA = mattingPool.get(int(random(mattingPool.size())));
      DNA parentB = mattingPool.get(int(random(mattingPool.size())));
      
      // 子の生成、突然変異、適応度計算
      DNA child = parentA.crossOver(parentB);
      child.mutate();
      child.calculateFitness();
      
      nextPopulation[i] = child;
    }
    
    // 世代の更新
    population = nextPopulation;
    
    // 最適解の発見
    for (DNA dna : population) {
      if (dna.fitness == 1.0) {
        println("遺伝子配列: " + arrayToString(dna.genes));
        println("適応度: " + dna.fitness);
        return;  // 最適解が見つかったら終了
      }
    }
  }
}

/**
 * 適応度に基づいて交配プールを作成
 * 適応度の高い個体ほど多くの子孫を残せるようにする
 */
void createMattingPool() {
  mattingPool.clear();
  int tournamentSize = 5;  // トーナメントに参加する個体数

  for (int i = 0; i < populationSize; i++) {
    DNA best = selectTournamentWinner(tournamentSize);
    mattingPool.add(best);
  }
}

/**
 * トーナメント選択
 * 
 * @param  トーナメントサイズ
 * @return 適応度の高いDNA
 */
DNA selectTournamentWinner(int tournamentSize) {
  DNA bestDNA = null;
  for (int i = 0; i < tournamentSize; i++) {
    DNA candidate = population[int(random(populationSize))];
    if (bestDNA == null || candidate.fitness > bestDNA.fitness) {
      bestDNA = candidate;
    }
  }
  return bestDNA;
}

/**
 * 文字配列を文字列に変換するユーティリティメソッド
 * 
 * @param  変換する文字配列
 * @return 変換後の文字列
 */
String arrayToString(char[] arr) {
  StringBuilder sb = new StringBuilder();
  for (char c : arr) {
    sb.append(c);
  }
  return sb.toString();
}

DNA：


class DNA {
  char[] genes;  // 遺伝子（文字配列）
  float fitness; // 適応度スコア
  
  /**
   * コンストラクタ
   */
  DNA() {
    genes = new char[targetArr.length]; // 遺伝子配列の初期化
  }
  
  /**
   * 遺伝子をランダムな文字で初期化
   * ASCII文字範囲（32-128）からランダムに選択
   */
  void randomizeGenes() {
    for (int i = 0; i < genes.length; i++) {
      genes[i] = (char)(random(32, 128));
    }
  }
  
  /**
   * 個体の適応度を計算
   * ターゲット文字列との一致度を評価
   */
  void calculateFitness() {
    int matchCount = 0;
    for (int i = 0; i < genes.length; i++) {
      if (genes[i] == targetArr[i]) {
        matchCount++;
      }
    }
	  // 一致数を全量で割ることで適応度を計算
    fitness = float(matchCount) / genes.length;
  }
  
  /**
   * 交叉（クロスオーバー）処理
   * 2つの親の遺伝子情報を組み合わせて子孫を生成
   * 
   * @param partner 交配相手のDNA
   * @return 新しく生成された子孫のDNA
   */
  DNA crossOver(DNA partner) {
    DNA child = new DNA();
    
    // それぞれの親の遺伝子をランダムな位置から取得し、子供の遺伝子に設定
    int midPoint = int(random(genes.length));
    for (int i = 0; i < genes.length; i++) {
      child.genes[i] = (i < midPoint) ? this.genes[i] : partner.genes[i];
    }
    
    return child;
  }
  
  /**
   * 突然変異プロセス
   * 設定された突然変異率に従って遺伝子をランダムに変更
   */
  void mutate() {
    for (int i = 0; i < genes.length; i++) {
      if (random(1) < mutationRate) {
        genes[i] = (char)(random(32, 128));
      }
    }
  }
}

遺伝的アルゴリズムにおいて重要な箇所を解説していきます。

/**
 * 遺伝子をランダムな文字で初期化
 * ASCII文字範囲（32-128）からランダムに選択
 */
void randomizeGenes() {
  for (int i = 0; i < genes.length; i++) {
    genes[i] = (char)(random(32, 128));
  }
}

このプログラムでは遺伝子を文字列配列で表現しています。 DNAオブジェクトを生成した際、ランダムな文字列を配列に格納します。


/**
 * 個体の適応度を計算
 * ターゲット文字列との一致度を評価
 */
void calculateFitness() {
  int matchCount = 0;
  for (int i = 0; i < genes.length; i++) {
    if (genes[i] == targetArr[i]) {
      matchCount++;
    }
  }
  // 一致数を全量で割ることで適応度を計算
  fitness = float(matchCount) / genes.length;
}

DNAオブジェクトはメンバ変数に適応度を保持します。

式：一致文字数 ÷ 配列サイズ = 適応度

遺伝子とターゲット文字列を比較して一致した数をカウントし、配列サイズで割る事で適応度を計算します。


/**
 * 適応度に基づいて交配プールを作成
 * 適応度の高い個体ほど多くの子孫を残せるようにする
 */
void createMattingPool() {
  mattingPool.clear();
  int tournamentSize = 5;  // トーナメントに参加する個体数

  for (int i = 0; i < populationSize; i++) {
    DNA best = selectTournamentWinner(tournamentSize);
    mattingPool.add(best);
  }
}

/**
 * トーナメント選択
 * 
 * @param  トーナメントサイズ
 * @return 適応度の高いDNA
 */
DNA selectTournamentWinner(int tournamentSize) {
  DNA bestDNA = null;
  for (int i = 0; i < tournamentSize; i++) {
    DNA candidate = population[int(random(populationSize))];
    if (bestDNA == null || candidate.fitness > bestDNA.fitness) {
      bestDNA = candidate;
    }
  }
  return bestDNA;
}

個体群から適応度の高い個体を選択します。

選択方法は様々な手法がありますが、今回はトーナメント選択を使用します。

理由はルーレット選択に比べて少ない計算量で最適解に辿り着くからです。

トーナメント選択

個体群（population）からランダムに個体を選択
最適個体（bestDNA）と候補個体（candidate）の適応度を比較し、適応度の高い個体を入れ替える。ループの最初は最適個体が選択されていない（bestDNA == null）のため、そのまま選択されます。
1、2をトーナメントサイズ分ループして最終的に残った最適個体を返却

上記の通り、トーナメント選択はループ回数が最大でもトーナメントサイズになるので、ルーレット選択のようなO(n)のアルゴリズムより効率が良いです。

ただし、トーナメントサイズが小さかったり、候補個体の適応度が全て小さいと、最適解に辿りつきにくくなる可能性があります。


/**
 * 遺伝的アルゴリズムの主要プロセス（選択、交配、突然変異）を実行
 * 指定世代まで、または最適解が見つかるまで進化を続ける
 * 
 * @param 指定世代
 */
void evolve(int maxGeneration) {
  for (int generation = 0; generation < maxGeneration; generation++) {
    // 交配プールの作成
    mattingPool = new ArrayList<DNA>();
    createMattingPool();
    
    // 次世代の個体群生成
    nextPopulation = new DNA[populationSize];
    for (int i = 0; i < populationSize; i++) {
      // 親の選択
      DNA parentA = mattingPool.get(int(random(mattingPool.size())));
      DNA parentB = mattingPool.get(int(random(mattingPool.size())));
      
      // 子の生成、突然変異、適応度計算
      DNA child = parentA.crossOver(parentB);
      child.mutate();
      child.calculateFitness();
      
      nextPopulation[i] = child;
    }
    
    // 世代の更新
    population = nextPopulation;
    
    // 最適解の発見
    for (DNA dna : population) {
      if (dna.fitness == 1.0) {
        println("遺伝子配列: " + arrayToString(dna.genes));
        println("適応度: " + dna.fitness);
        return;  // 最適解が見つかったら終了
      }
    }
  }
}

最適解もしくは指定世代に到達するするまで交配、選択、突然変異を実行し続けます。

まずは交配プールを作成します。createMattingPool関数の説明でもありましたが、交配プールには適応度の高い個体が多く入っており、その中から親個体をランダムで2つ選択して交配させます。


/**
 * 交叉（クロスオーバー）処理
 * 2つの親の遺伝子情報を組み合わせて子孫を生成
 * 
 * @param partner 交配相手のDNA
 * @return 新しく生成された子孫のDNA
 */
DNA crossOver(DNA partner) {
  DNA child = new DNA();
  
  // それぞれの親の遺伝子をランダムな位置から取得し、子供の遺伝子に設定
  int midPoint = int(random(genes.length));
  for (int i = 0; i < genes.length; i++) {
    child.genes[i] = (i < midPoint) ? this.genes[i] : partner.genes[i];
  }
  
  return child;
}

交配は2個体の遺伝子それぞれをランダムな位置から結合させます。結合させた遺伝子を持つ子（child）を返却します。


/**
 * 突然変異プロセス
 * 設定された突然変異率に従って遺伝子をランダムに変更
 */
void mutate() {
  for (int i = 0; i < genes.length; i++) {
    if (random(1) < mutationRate) {
      genes[i] = (char)(random(32, 128));
    }
  }
}

子を生成した後に突然変異を一定の確率で発生させます。確率はmutationRateで制御します。突然変異とは遺伝子の特定要素をランダムな文字列に変更します。

これまでの遺伝的アルゴリズムの主要プロセスを指定世代分まで実行させます。

最終的に最適解が見つかるとコンソール上に適応度と最適解文字列を表示させます。

まとめ

今回は遺伝的アルゴリズムを実装しました。名前だけ見ると難しそうですが、分解していけば意外と簡単なことしかしておらず

選択、交叉、突然変異というシンプルな仕組みとなっています。

このアルゴリズムを作品に組み込みたいですが、適応度とは「正解」という意味合いになると思いますが、芸術において正解を定義するのはかなり難しいです。

そもそも見る人にとって感じ方はそれぞれですし、あえて正解を定義してしまうと鑑賞方法が制限されてしまいそうです、、

何か面白い使い方を探っていこうと思うので、出来上がったら発表しようと思います！

最後まで読んでいただきありがとうございました。

Processing 遺伝的アルゴリズム

最新記事

Comments