遺伝的アルゴリズム Genetic Algorithm(GA)のC++実装

海洋ロボコンをやってた人です。

今回はメタヒューリスティクスの中でよく使用される手法の遺伝的アルゴリズム：Genetic Algorithmについての概要から、Simple GAのC++実装例までを書いていこうと思います。

経緯としては、PSOやMRFOはフルスクラッチ実装したのに対し、遺伝的アルゴリズムGAはフルスクラッチ実装していなかったので、挑戦してみようと思ったためです。

また自分自身の備忘録にもなっていますので、わかりにくい箇所があるかもしれません。
予めご容赦いただきますようお願いします。

"もっとこうすれば簡単に実装できるよ" や "ここは違うよ"というご意見がありましたら、是非ご教授いただけますと幸いです。

GA: Genetic Algorithmの構成

遺伝的アルゴリズムは生物の進化の遺伝子的法則を工学的にモデル化したメタヒューリスティクス手法の一つで、世代ごとに各個体の中から、目標関数の適応度の高い個体が生存していくように進化していく手法です。

ランダムに生成した遺伝子に対して

• 評価: evaluate
• 選択: selection
• 交叉・突然変異: crossover/mutation
• 世代交代: generation alternation

を繰り返すことで最適解を求めていきます。

これら、「評価」、「選択」、「交叉」、「突然変異」、「世代交代」の仕様によって最適解の収束性が変化します。

GAのフローチャートイメージは以下（TDだと場所を取るためLR表示）。

選択：selection

「選択」は以下のような方法があります。

• ルーレット選択: roulette wheel selection
• ランキング選択: ranking selection
• トーナメント選択: tournament selection
• エリート選択: elite selection

詳しくは、Reference「1」をご覧ください。

交叉: crossover

「交叉」は以下のような方法があります。

• 一点交叉: single point crossover
• 二点交叉: two-point crossover
• 多点交叉: multi-point crossover
• 一様交叉: uniform crossover

詳しくは、Reference「1」をご覧ください。

突然変異: mutation

「突然変異」は以下のような方法があります。

• 置換: substitution, ランダム箇所の遺伝子を対立バイナリ(0/1)に変更
• 摂動: perturbation, ランダム箇所の遺伝子に微量値を加減算(実数)
• 交換: swap, ランダム箇所の遺伝子を入れ替える
• 逆位: inversion, ランダム箇所の2点間の遺伝子を逆順にする
• 挿入: insertion, ランダム箇所の遺伝子を、任意箇所の遺伝子に挿入(遺伝子長は可変）

詳しくは、Reference「2」をご覧ください。

世代交代: generation alternation

世代交代は以下のように分類できます。

※ただし、必ずしも以下のように分類されるわけではなく、世代交代の実装方法によって異なることを念頭に置いてください。

世代交代が離散的であれば(すべての個体が入れ替わっていれば）離散世代モデルとなり、世代交代に連続性があれば（現世代の個体がN%引き継がれていれば）連続世代モデルになると思います。

• 離散世代モデル: Discrete Generation Model

  • 単純GA: Simple GA (SGA)
  • エリートGA: Genetic Algorithm with Elitist Model (EGA)
    • Elitist Recombination (ER) Model
    • Best N (BN) Model, similar to CHC

• 連続世代モデル: Continuous Generation Model

  • 定常状態GA: Steady-State GA (SSGA)

• Island Model

離散世代モデルは、すべての個体が一斉に繁殖を行い、次世代へ世代交代します。そのため、現世代の遺伝子情報はすべて破棄され局所解になりやすい欠点があるが、アルゴリズムが容易という利点があります。

連続世代モデルは、現在の世代の中から一定割合の個体を世代交代するため、局所解になりずらく、最適解に収束しやすい利点があります。一方、一度局所解に入ると、そこから最適解には収束しにくいという欠点があります。

Island Modelは日訳すると島モデル？となり、このモデルではGAの集団が亜集団として複数存在する並列分散GAモデルです。各集団がそれぞれの島で最適解(優秀な個体)を探索しており、それぞれの集団において個体が移動し、各集団(島)においての評価値の差異が小さくなっていきます。
ただ、集団Aから集団Bへの移動は不可逆性をもち、集団への相互移動はできません。

また上記を行う上で、各遺伝子の情報をエンコーディングした形で扱うことが多く

• バイナリエンコーディング(binary encoding): 0/1符号での表現
• 順列エンコーディング(permutation encoding): 順列を示す数字で表現
• 実数値エンコーディング(real encoding): 数値/文字で表現
• 木構造エンコーディング(tree encoding)

といったエンコーディング方法があります。

エンコーディング > 選択&交叉 > デコーディング

といった形で、各遺伝子型を表現型に戻すことも必要になると思います。

• 離散世代モデルの例

東京大学 ソフトコンピューティング演習　第5回

のP6 図8遺伝的アルゴリズムのフローチャートでは、上位50%をエリート選択で世代交代し、下位50%を1点交叉、突然変異させています。

この操作をn世代繰り返すことで指定した評価関数に対しての最適化を求めます。

また、評価時の目的関数は2変数1目的関数といった単目的関数、複数の目的関数について最適化を行う多目的最適化などもあります「3」。

各世代交代モデルの詳細

選択、交叉、突然変異の説明はQiita等で書かれている先人の方々、書籍も沢山あるので、ここでは世代交代モデルの詳細について触れていこおうと思います。

SGA: Simple Genetic Algorithm

Simple Genetic Algorithm (単純GA）は、GAを通常通り解析すると複雑なので、処理を以下のように単純化して解析する手法です「4, 5」。

1. 遺伝子表現は1/0のみ
2. ルーレット選択
3. 一点交叉
4. 突然変異は1箇所の遺伝子座のみ反転させる

上記の選択、交叉、突然変異の種類は適宜最適化問題によって変更することが想定されていると思います。

C++での実装例も示しておきます。

sga.cpp

#include <iostream>
#include <vector>
#include <time.h>
#include <cmath>
#include <random>
#include <stdlib.h>
#include <algorithm>

class Sga{
  public:
    Sga();
    void alternation();
    struct individual{
      std::vector<int> chrom;
      int decimal_input;
      double fitness;
    };
    std::vector<individual> population;
    std::vector<individual> next_pop;
    std::vector<int> parents_num; // roulette_select parents_num of tournament
    double output;
    double global_fitness;

    int bit_len = 8; // 2^8 = 256
    int population_size = 20;
    double mutate_prob = 0.05; // mutate_rate

  private:
    void convert2decimal();
    void evaluate();
    void sort();
    void roulette_select(int individual_num);
    void single_point_crossover();
    void mutate();

    double rand01;
    double denom;
    std::vector<double> prob_p;

};

Sga::Sga(){
  population.resize(population_size);
  next_pop.resize(population_size);
  for (int j=0; j<population_size; j++){
    population[j].chrom.resize(bit_len);
    next_pop[j].chrom.resize(bit_len);
    for(int k=0; k<bit_len; k++){
      population[j].chrom[k] = rand()%2; 
    }
  }
  convert2decimal();
  evaluate();
  sort();
}

void Sga::convert2decimal(){
  for(int j=0; j<population_size; j++){
    population[j].decimal_input = 0.0;
  }
  for(int j=0; j<population_size; j++){
    for(int k=0; k<bit_len; k++){
        population[j].decimal_input += pow(2, k)*population[j].chrom[bit_len-k];
    }
  }
}

// TODO
void Sga::evaluate(){
  for(int j=0; j<population_size; j++){
    population[j].fitness = 1.5/std::sqrt(2*M_PI)*exp(-std::pow(population[j].decimal_input-50,2)/2000)\
    + 2.5/std::sqrt(2*M_PI)*exp(-std::pow(population[j].decimal_input-150,2)/2000);        
  }
}

void Sga::sort(){
  std::sort(std::begin(population), std::end(population),
    [](const individual& a, const individual& b) {
      return a.fitness > b.fitness;
    });
  output = population[0].decimal_input;
  global_fitness = population[0].fitness;
}

void Sga::roulette_select(int individual_num){
  parents_num.resize(individual_num);

  denom = 0.0;
  for(int j=0; j<population_size; j++){
    denom += population[j].fitness;
  }

  prob_p.clear();
  for(int j=0; j<population_size; j++){
    prob_p.push_back(population[j].fitness / denom);
  }
  std::random_device seed_gen;
  std::mt19937 engine(seed_gen());
  std::discrete_distribution<int> dist(prob_p.begin(), prob_p.end());
  for(int i=0; i<parents_num.size(); i++){
    parents_num[i] = dist(engine);    
  }
}

void Sga::single_point_crossover(){
  int point, k;
  int parent_1, parent_2;
  for(int j=0; j<population_size; j+=2){
    point = rand() % bit_len;
    roulette_select(2);
    parent_1 = parents_num[0];
    parent_2 = parents_num[1];   

    for(k=0; k<=point; k++){
      next_pop[j].chrom[k] = population[parent_1].chrom[k];
      next_pop[j+1].chrom[k] = population[parent_2].chrom[k];
    }
    for(; k<bit_len; k++){
      next_pop[j].chrom[k] = population[parent_2].chrom[k];
      next_pop[j+1].chrom[k] = population[parent_1].chrom[k];     
    }
  }
}

void Sga::mutate(){
  for(int j=0; j<population_size; j++){
    for(int k=0; k<bit_len; k++){
      rand01 = ((double)rand() / RAND_MAX);
      if(rand01 < mutate_prob){
        next_pop[j].chrom[k] = 1 - population[j].chrom[k];
      }
    }
  }
}

void Sga::alternation(){
  single_point_crossover();
  mutate();

  // alternation
  for(int j=0; j<population_size; j++){
    for(int k=0; k<bit_len; k++){
      population[j].chrom[k] = next_pop[j].chrom[k];
    }
  }

  convert2decimal();
  evaluate();
  sort();
}


int main(){
  srand((unsigned int)time(NULL));

  Sga sga;
  printf("loop----------\n");
  for(int i=0; i<20; i++){
    sga.alternation();
    printf("Generation: %d, decimal: %f, fitness: %f\n", i, sga.output, sga.global_fitness);
  }
  return 0;
}

class Sgaでは構造体として

• chrom: 2進数染色体情報
• decimal_input: 10進数の値
• fitness: 評価値

を持つメンバを定義しています。
この構造体を持つ動的配列のvectorで集団および次世代の集団をpopulation, next_popとして扱っていきます。
※　この記述方法がプログラム的に正しくない可能性もあるので、適宜変更してくださいね。

privateメンバには、個体および集団で処理を行うメンバ関数等を定義しています。

Sga()のコンストラクタでは、集団のサイズpopulation_sizeで各世代の集団を初期化し、2進数の染色体をランダムで生成しています。

convert2decimal()は評価関数に代入するためのデコーディング（2進数→10進数）をしています。
この部分は、実数値→2進数→10進数のようにエンコーディング、デコーディングを上手く活用して、入力パラメータの範囲を調整する必要がありそうです。

evaluate()では、評価関数より評価値を算出しています。
ここの記述を最適化問題に適した関数に変更する必要があります。

sort()では評価値が昇順になるようにソートしています。
このソートも最小勾配法にするのか、最大値探索をするのか、最適化問題に適した並び替えが必要になると思います。
今回は、評価関数の最大値を探索するので、昇順ソートになっています。

roulette_select()では、ある確率$P_i$により親個体$i$を決定する方法で、確率は

$$P_i={\frac{f_i}{\sum f_i}}$$

で求めることができます。
この確率に従い、親個体をルーレット選択により決定します。

single_point_crossover()では一点交叉を行っています。
point = rand() % bit_len;で交叉点をランダムに決めて、2つの親個体から2つの子個体へ繁殖します。

mutate()では突然変異率のしきい値より乱数が小さくなったときに突然変異が生じるようにしており、対立バイナリに変更する「置換」を使用しています。

最後に、alternation()によりすべての個体を削除し、新しい個体へと世代交代させています（離散世代モデル）。

これを指定世代分繰り返すことで、評価関数に対する最適解を解いています。

実行すると、以下のようになり

terminal

loop----------
Generation: 0, decimal: 142.000000, fitness: 0.974637
Generation: 1, decimal: 142.000000, fitness: 0.974637
Generation: 2, decimal: 134.000000, fitness: 0.895098
Generation: 3, decimal: 142.000000, fitness: 0.974637
Generation: 4, decimal: 148.000000, fitness: 1.000278
Generation: 5, decimal: 140.000000, fitness: 0.959140
Generation: 6, decimal: 142.000000, fitness: 0.974637
Generation: 7, decimal: 142.000000, fitness: 0.974637
Generation: 8, decimal: 142.000000, fitness: 0.974637
Generation: 9, decimal: 142.000000, fitness: 0.974637
Generation: 10, decimal: 160.000000, fitness: 0.950125
Generation: 11, decimal: 152.000000, fitness: 0.998658
Generation: 12, decimal: 152.000000, fitness: 0.998658
Generation: 13, decimal: 152.000000, fitness: 0.998658
Generation: 14, decimal: 150.000000, fitness: 1.001388
Generation: 15, decimal: 150.000000, fitness: 1.001388
Generation: 16, decimal: 152.000000, fitness: 0.998658
Generation: 17, decimal: 152.000000, fitness: 0.998658
Generation: 18, decimal: 150.000000, fitness: 1.001388
Generation: 19, decimal: 152.000000, fitness: 0.998658

最大値が148〜152付近であることが分かります。
より精度を上げるためには、選択、交叉の手法や世代交代モデルを変更することにより最適解に近づけることが可能です。

EGA: Genetic Algorithm with Elitist Model

エリート戦略によるGAで、エリート戦略のモデルにより以下のように分類できます「6」。（エリートモデルの一部です。）

ER: Elitist Recombination Model

ランダムに選択された親個体2個と、そこから作られる子個体2個を「家族」(4個体分)とし、「家族」(4個体分)の中からエリート選択とルーレット選択で2個体を次世代に残していきます。
これを個体集合:Populationの数だけ繰り返すことで世代交代をします。

BN: Best N Model

ERの選択個体数がN個となったモデルです。
ランダムに選択された親個体N個と、そこから作られる子個体N個を「家族」(2N個体分)とし、「家族」(2N個体分)の中からエリート選択とルーレット選択でN個体を次世代に残していきます。
これを個体集合:Populationの数だけ繰り返すことで世代交代をします。

SSGA: Steady-State GA

連続世代モデルで「定常状態GA」とも呼ばれます。
1世代につき1組(2つ個体)の親個体から子個体を生成し、交叉・突然変異を得て、現世代のうち最も適応度の低い個体と入れ替えることで世代交代し最適解を探索します「7」。

Reference

---GA---
「1」Qiita: 遺伝的アルゴリズムについてコードも交えて解説する

「2」slideshare: 遺伝的アルゴリズム♪（Genetic Algorithm）を始めよう！

「3」TECHNO OH: 多目的最適化問題(第一回)

---SGA---
「4」Wikipedia: 遺伝的アルゴリズム
「5」東京女子大学：遺伝的アルゴリズム

---EGA---
「6」Multidisciplinary Design Optimization of Aircraft Wing Planform Based
on Evolutionary Algorithms: p3, Elitist Models

---SSGA---
「7」Evolutionary Computation, Optimization and Learning
Algorithms for Data Science Figure3

疑問点、改善点等あればお気軽にご連絡ください。
また、この記事が良かったと感じたら、"いいね"ボタンよろしくお願いします。

以上。