石取りゲームで遺伝的アルゴリズムの実験その4

著者：北本敦

公開日：2021/04/07

最終更新日：2021/04/22

カテゴリー：技術情報

北本です。

今回は、遺伝的アルゴリズムの肝要となる「遺伝的操作」を行うGetNextGeneration関数の実装を紹介していきたいと思います。

void GetNextGeneration(GENERATION_DATA currentGeneration, GENERATION_DATA* nextGeneration)
は、引数currentGenerationを元に次世代を生成して引数nextGenerationに渡す関数となっています。

手法

今回の実験では、以下のような遺伝的操作を行い次世代の100個体を生成します。

①まず、現世代(引数currentGenerationで渡されたデータ)の勝数上位10個体を選択、すなわちそのまま残します。

②残り90個体については、以下のルールに従って抽選を2回行って2個体を選出して交叉させる操作を90回行って生成します。

下記A～Hの抽選方法があり、その中から一つを選択する。A～Hの各方法が選ばれる確率は括弧内の値の通りである。

A. 勝数 1～10位の個体からランダムで選出 (40%)
B. 勝数11～20位の個体からランダムで選出 (20%)
C. 勝数21～30位の個体からランダムで選出 (15%)
D. 勝数31～40位の個体からランダムで選出 (10%)
E. 勝数41～50位の個体からランダムで選出 ( 8%)
F. 勝数51～60位の個体からランダムで選出 ( 4%)
G. 勝数61～70位の個体からランダムで選出 ( 2%)
H. 勝数71～80位の個体からランダムで選出 ( 1%)

そして、選ばれた方法に従って抽選を行い個体を選出する。

交叉対象に同じ2個体が選出された場合は抽選やり直しとしますが、同じ組み合わせの交叉が複数回行われることは許容することとします。

交叉は一様交叉で行います。
各遺伝子について、親の2個体のパラメータのいずれかを各1/2の確率で選択して子に継承します。

③100個体が生成されたら、全個体の遺伝子(21×100=2100箇所)の内、0～6箇所を値をランダムに書き換えます(突然変異)。

実装

コードは以下の通りです。

void GetNextGeneration(GENERATION_DATA currentGeneration, GENERATION_DATA* nextGeneration)
{
  // 勝数降順にソート
  std::sort(std::begin(currentGeneration.data), std::end(currentGeneration.data),
    [](const INDIVIDUAL_DATA lh, const INDIVIDUAL_DATA rh) { return lh.numberOfWins > rh.numberOfWins; }
  );

  // 勝数上位10個体を選択(そのまま残す)
  memcpy(nextGeneration->data->genes, currentGeneration.data, sizeof(INDIVIDUAL_DATA) * 10);

  // 残り90個体を交叉によって生成
  for (int i = 10; i < NUMBER_OF_INDIVIDUALS; i++)
  {
    int ind1, ind2;
    ind1 = ChooseIndividualNumber();
    do
    {
      ind2 = ChooseIndividualNumber();
    } while (ind1 == ind2);
    memcpy(nextGeneration->data[i].genes, GetCrossed(currentGeneration.data[ind1].genes, currentGeneration.data[ind2].genes), sizeof(BYTE) * NUMBER_OF_STONES);
  }

  // 全個体の遺伝子の内、0～6箇所を突然変異させる
  int mutationNum = rand() % 7;
  for (int i = 0; i < mutationNum; i++)
  {
    Mutate(nextGeneration);
  }

  // 勝数データの初期化
  for (int i = 0; i < NUMBER_OF_INDIVIDUALS; i++)
  {
    nextGeneration->data[i].numberOfWins = -1;
  }
}

上記コードの中で使われている関数については以下の通りです。

ChooseIndividualNumber
交叉対象を抽選し個体の勝数順位(ゼロオーダー)を返します。
GetCrossed
引数で渡した親2個体の遺伝情報を交叉して生成した子の遺伝情報を返します。
Mutate
全個体の遺伝子の中から一箇所をランダムで選んで値を書き換えます。

これらの内容は後掲します。
それ以外の定数などに関しては前々回の記事を参照してください。

ChooseIndividualNumber

static int ChooseIndividualNumber()
{
  int r = rand() % 100;
  if (r < 40) // A.勝数 1～10位の個体からランダムで選出 (40%)
  {
    return rand() % 10;
  }
  else if (r < 60) // B.勝数11～20位の個体からランダムで選出 (20%)
  {
    return rand() % 10 + 10;
  }
  else if (r < 75) // C.勝数21～30位の個体からランダムで選出 (15%)
  {
    return rand() % 10 + 20;
  }
  else if (r < 85) // D.勝数31～40位の個体からランダムで選出 (10%)
  {
    return rand() % 10 + 30;
  }
  else if (r < 93) // E.勝数41～50位の個体からランダムで選出 ( 8%)
  {
    return rand() % 10 + 40;
  }
  else if (r < 97) // F.勝数51～60位の個体からランダムで選出 ( 4%)
  {
    return rand() % 10 + 50;
  }
  else if (r < 99) // G.勝数61～70位の個体からランダムで選出 ( 2%)
  {
    return rand() % 10 + 60;
  }
  else // H.勝数71～80位の個体からランダムで選出 ( 1%)
  {
    return rand() % 10 + 70;
  }
}

GetCrossed

static BYTE* GetCrossed(BYTE* genes1, BYTE* genes2)
{
  BYTE crossed[NUMBER_OF_STONES];
  for (int i = 0; i < NUMBER_OF_STONES; i++)
  {
    crossed[i] = (rand() % 2) ? genes1[i] : genes2[i];
  }
  return crossed;
}

Mutate

static void Mutate(GENERATION_DATA* generationData)
{
  int indvIndex = rand() % NUMBER_OF_INDIVIDUALS;
  int geneIndex = rand() % NUMBER_OF_STONES;

  int value;
  if (NUMBER_OF_STONES - geneIndex == 1) // 残り石数が1個の場合
    value = 1;
  else if (NUMBER_OF_STONES - geneIndex == 2) // 残り石数が2個の場合
    value = rand() % 2 + 1;
  else
    value = rand() % 3 + 1;

  generationData->data[indvIndex].genes[geneIndex] = value;
}

今回の実験での遺伝的操作の方法については、細かい値設定や抽選の仕方を特になんらかの根拠に基づいて決定しているわけではなく、勝数上位の個体の形質が多く次世代に継承されかつ勝数下位の個体の形質が淘汰されすぎないというのを目標に感覚的に設定したにすぎません。このあたりをうまく調整するのが遺伝的アルゴリズムにおける腕の見せ所となってくるのでしょう。

次回は実際にプログラムを実行した結果を見てみることにします。

石取りゲームで遺伝的アルゴリズムの実験 その4

手法

実装

石取りゲームで遺伝的アルゴリズムの実験その4