HN 日本語サマリー

← 一覧へ戻る
AI・機械学習

遺伝的アルゴリズムを用いた自己駐車可能な車 (2021)

Self-parking car using genetic algorithm (2021) (trekhleb.dev)

65 pointsby trekhleb5 コメント

要約

この記事では、遺伝的アルゴリズムを用いて車を自己駐車できるように訓練する方法を解説しています。車の「筋肉」(エンジン、ステアリング)、「目」(センサー)、「脳」(ニューラルネットワークまたは線形多項式)を段階的に構築し、遺伝的アルゴリズムを適用して最適な「脳」のパラメータを進化させるプロセスを説明しています。シミュレーターでその進化の様子を確認できます。

全文翻訳

500行のコードで実現する自己駐車カー

[画像: Self-Parking car evolution]

TL;DR

この記事では、遺伝的アルゴリズム を用いて車に自己駐車を学習させます。

まず、ランダムなゲノムを持つ車の第1世代を作成します。これらの車は以下のような動きをします。

[画像: The 1st generation of cars with random genomes]

約40世代目になると、車は自己駐車とは何かを学び始め、駐車スペースに近づくようになります。

[画像: The 40th generation start learning how to park]

より挑戦的な初期条件での別の例です。

[画像: More challenging starting point for self-parking]

はいはい、車は途中で他の車にぶつかったり、駐車スペースに完璧に収まらなかったりしますが、これは彼らにとって世界の創造からまだ40世代目なのですから、寛容になって成長の余地を与えてあげてください :D

タクシー 自己駐車カー進化シミュレーター を起動して、ブラウザで直接進化のプロセスを確認できます。シミュレーターでは以下の機能が利用できます。

このプロジェクトの遺伝的アルゴリズムはTypeScriptで実装されています。完全な遺伝子ソースコードはこの記事で紹介しますが、最終的なコード例は Evolution Simulator リポジトリ で見つけることができます。

私たちは、車のゲノムを進化させるという特定のタスクに遺伝的アルゴリズムを使用します。しかし、この記事ではアルゴリズムの基本に触れるだけで、遺伝的アルゴリズムの完全なガイドではありません。

それでは、さらに詳しく見ていきましょう...

計画

ステップバイステップで、自己駐車カーを作成するという高レベルのタスクを、最適な 180 ビットの組み合わせ(最適な車のゲノム)を見つけるという、単純な低レベルの最適化問題に分解していきます。

以下を行う予定です。

  1. 💪🏻 車に筋肉(エンジン、ステアリングホイール)を与え、駐車スペースに向かって移動できるようにします。
  2. 👀 車に目(センサー)を与え、周囲の障害物を見えるようにします。
  3. 🧠 車に脳を与え、車が見ているもの(センサー経由の障害物)に基づいて筋肉(動き)を制御します。脳は単純に純粋な関数 movements = f(sensors) となります。
  4. 🧬 脳を進化させ、センサー入力に基づいて正しい動きができるようにします。ここで遺伝的アルゴリズムを適用します。世代を重ねるごとに、私たちの脳関数 movements = f(sensors) は、車を駐車スペースに近づける方法を学習します。

車に筋肉を与える

移動するためには、車には「筋肉」が必要です。車に2種類の筋肉を与えましょう。

  1. エンジン筋肉 - 車を ↓ 後退、↑ 前進、または ◎ ニュートラル(ギアニュートラル)させることができます。
  2. ステアリングホイール筋肉 - 車を ← 左折、→ 右折、または移動中に ◎ 直進 させることができます。

これらの2つの筋肉により、車は以下の動きを実行できます。

[画像: Car movements achieved by car muscles]

この場合、筋肉は脳から 100ms(ミリ秒)ごとに送られてくる信号の受信機です。脳からの信号の値に基づいて、筋肉は異なる動作をします。「脳」の部分は後述しますが、現時点では、私たちの脳は各筋肉に -1、0、または +1 の3つの可能な信号しか送信できないとしましょう。

type MuscleSignal = -1 | 0 | 1;

例えば、脳がエンジン筋肉に +1 の値を持つ信号を送信すると、車は前進し始めます。エンジンへの信号 -1 は車を後退させます。同時に、脳がステアリングホイール筋肉に -1 の信号を送信した場合、車は左に曲がりますなど。

脳の信号値が筋肉の動作にどのようにマッピングされるかを以下に示します。

筋肉Signal = -1Signal = 0Signal = +1
エンジン↓ 後退◎ ニュートラル↑ 前進
ステアリングホイール← 左折◎ 直進→ 右折

Evolution Simulator を使用して、手動で車を駐車してみてください。車の筋肉がどのように機能するかを確認できます。WASD キーボードキー(またはタッチスクリーンのジョイスティック)を押すたびに、これらの -1、0、または +1 の信号がエンジンとステアリングホイールの筋肉に送信されます。

車に目を与える

車が筋肉を使って自己駐車する方法を学ぶ前に、周囲を「見る」ことができるようになる必要があります。8つの距離センサーという形で8つの「目」を与えましょう。

  • 各センサーは 0〜4m(メートル)の距離範囲で障害物を検出できます。
  • 各センサーは、100ms ごとに、車に「見えている」障害物に関する最新情報を「脳」に報告します。
  • センサーが障害物を見つけられない場合、値 0 を報告します。逆に、値がゼロではないが小さい場合(例: 0.01m)は、障害物が近いことを意味します。

[画像: Car sensors with distances]

Evolution Simulator を使用して、各センサーの色が障害物までの距離に応じてどのように変化するかを確認してください。

type Sensors = number[];

車に脳を与える

この時点では、車は「見ること」と「動くこと」ができますが、「目」からの信号を「筋肉」の適切な動きに変換する「調整役」がいません。車に「脳」を与える必要があります。

脳の入力

センサーからの入力として、100ms ごとに脳は 8 つの浮動小数点数を受け取ります。それぞれ [0...4] の範囲です。例えば、入力は次のようになります。

const sensors: Sensors = [s0, s1, s2, s3, s4, s5, s6, s7];
// 例: 🧠 ← [0, 0.5, 4, 0.002, 0, 3.76, 0, 1.245]
脳の出力

100ms ごとに、脳は2つの整数を出力する必要があります。

  1. エンジンへの信号としての1つの数値: engineSignal
  2. ステアリングホイールへの信号としての1つの数値: wheelSignal

各数値は MuscleSignal 型で、-1、0、または +1 のいずれかの値を取ります。

脳の数式/関数

上記の脳の入力と出力を考慮すると、脳は単なる関数であると言えます。

const { engineSignal, wheelSignal } = brainToMuscleSignal(
  brainFunction(sensors)
);
// 例: { engineSignal: 0, wheelSignal: -1 } ← 🧠 ← [0, 0.5, 4, 0.002, 0, 3.76, 0, 1.245]

ここで、brainToMuscleSignal() は、生の脳信号(任意の浮動小数点数)を筋肉信号(-1、0、または +1 の数値)に変換する関数です。この変換関数は後で実装します。

主な質問は、brainFunction() がどのような種類の関数であるかということです。

車をより賢く、その動きをより洗練されたものにするために、多層パーセプトロン を採用することもできます。名前は少し怖いかもしれませんが、これは基本的なアーキテクチャを持つ単純なニューラルネットワークです(多くのパラメータ/係数を持つ大きな数式と考えてください)。

私は、homemade-machine-learning、machine-learning-experiments、および nano-neuron プロジェクトで多層パーセプトロンについて詳しく説明しました。あなたは、この単純なネットワークにあなたの書いた数字を認識させる ことさえ挑戦できます。

しかし、ニューラルネットワークという全く新しい概念の導入を避けるために、より単純なアプローチを採用し、複数の変数を持つ2つの線形多項式を使用します(より正確には、各多項式は 8 つのセンサーがあるため、ちょうど 8 つの変数を持つことになります)。これは次のようになります。

engineSignal = brainToMuscleSignal(
  (e0 * s0) + (e1 * s1) + ... + (e7 * s7) + e8 // <- brainFunction
)

wheelSignal = brainToMuscleSignal(
  (w0 * s0) + (w1 * s1) + ... + (w7 * s7) + w8 // <- brainFunction
)

ここで:

  • [s0, s1, ..., s7] - 8 つの変数、つまり 8 つのセンサー値です。これらは動的です。
  • [e0, e1, ..., e8] - エンジン多項式の 9 つの係数です。これらは車が学習する必要があり、静的です。
  • [w0, w1, ..., w8] - ステアリングホイール多項式の 9 つの係数です。これらは車が学習する必要があり、静的です。

より単純な関数を脳に使用することのコストは、車が高度な動きを学習できず、未知の環境への汎化や適応も得意ではないことです。しかし、私たちの特定の駐車場と、遺伝的アルゴリズムの動作を実証するという目的のためには、これで十分でしょう。

汎用的な多項式関数は次のように実装できます。

type Coefficients = number[];

// 係数と変数に基づいて線形多項式の値を計算します。
const linearPolynomial = (coefficients: Coefficients, variables: number[]): number => {
  if (coefficients.length !== (variables.length + 1)) {
    throw new Error('Incompatible number of polynomial coefficients and variables');
  }
  let result = 0;
  coefficients.forEach((coefficient: number, coefficientIndex: number) => {
    if (coefficientIndex < variables.length) {
      result += coefficient * variables[coefficientIndex];
    } else {
      // 最後の係数は乗算なしで加算する必要があります。
      result += coefficient
    }
  });
  return result;
};

この場合、車の脳は2つの多項式で構成され、次のようになります。

const engineSignal: MuscleSignal = brainToMuscleSignal(
  linearPolynomial(engineCoefficients, sensors)
);

const wheelSignal: MuscleSignal = brainToMuscleSignal(
  linearPolynomial(wheelCoefficients, sensors)
);

linearPolynomial() 関数の出力は浮動小数点数です。brainToMuscleSignal() 関数は、広範囲の浮動小数点数を3つの特定の整数に変換する必要があります。これは2つのステップで行います。

  1. 広範囲の浮動小数点数(例: 0.456、3673.45、-280)を (0...1) の範囲の浮動小数点数(例: 0.05、0.86)に変換します。
  2. (0...1) の範囲の浮動小数点数を、-1、0、または +1 の3つの整数値のいずれかに変換します。例えば、0 に近い浮動小数点数は -1 に、0.5 に近い浮動小数点数は 0 に、1 に近い浮動小数点数は 1 に変換されます。

この変換の最初のステップを実行するには、シグモイド関数 を導入する必要があります。これは次の式を実装します。

[画像: Sigmoid formula]

これは、広範囲の浮動小数点数(x軸)を (0...1) の範囲に制限された浮動小数点数(y軸)に変換します。これはまさに私たちが求めているものです。

[画像: Sigmoid graph]

シグモイドグラフでの変換ステップの例を以下に示します。

[画像: Conversion steps on the graph]

上記の2つの変換ステップの実装は次のようになります。

// 指定された数値のシグモイド値を計算します。
const sigmoid = (x: number): number => {
  return 1 / (1 + Math.E ** -x);
};

// シグモイド値 (0...1) を筋肉信号 (-1, 0, +1) に変換します。
// margin パラメータは 0 から 0.5 の間の値です。
// [0 ... (0.5 - margin) ... 0.5 ... (0.5 + margin) ... 1]
const sigmoidToMuscleSignal = (sigmoidValue: number, margin: number = 0.4): MuscleSignal => {
  if (sigmoidValue < (0.5 - margin)) {
    return -1;
  }
  if (sigmoidValue > (0.5 + margin)) {
    return 1;
  }
  return 0;
};

// 生の脳信号を筋肉信号に変換します。
const brainToMuscleSignal = (rawBrainSignal: number): MuscleSignal => {
  const normalizedBrainSignal = sigmoid(rawBrainSignal);
  return sigmoidToMuscleSignal(normalizedBrainSignal);
}

車のゲノム(DNA)

☝🏻 上記の「目」、「筋肉」、「脳」のセクションからの主な結論は次のとおりです。係数 [e0, e1, ..., e8] と [w0, w1, ..., w8] が車の動作を定義します。これらの 18 個の数値が組み合わさって、ユニークな車のゲノム(または車のDNA)を形成します。

10進数形式の車ゲノム

脳係数の [e0, e1, ..., e8] と [w0, w1, ..., w8] を結合して、10進数形式の車のゲノムを形成しましょう。

// 10進数の数値(係数)のリストとしての車ゲノム。
const carGenomeBase10 = [e0, e1, ..., e8, w0, w1, ..., w8];

// 例: carGenomeBase10 = [17.5, 0.059, -46, 25, 156, -0.085, -0.207, -0.546, 0.071, -58, 41, 0.011, 252, -3.5, -0.017, 1.532, -360, 0.157]
バイナリ形式の車ゲノム

さらに一歩進んで(遺伝子のレベルまで)、車のゲノムの10進数値をバイナリ形式(プレーンな 1 と 0)に変換しましょう。

浮動小数点数をバイナリ数に変換するプロセスについては、浮動小数点数のバイナリ表現 の記事で詳しく説明しました。このセクションのコードが不明瞭な場合は、そちらを参照することをお勧めします。

浮動小数点数を 16ビット のバイナリ数に変換する簡単な例を以下に示します(例が分かりにくい場合は、まずこちらを読む ことをお勧めします)。

[画像: Example of floating to binary numbers conversion]

この場合、ゲノムの長さを短縮するために、各浮動小数点係数を非標準の 10ビット バイナリ数(1 ビットの符号、4 ビットのエクスポーネント、5 ビットのフラクション)に変換します。

合計 18 個の係数があり、各係数は 10ビット の数値に変換されます。これは、車のゲノムが 18 * 10 = 180ビット の長さの 0 と 1 の配列になることを意味します。

例えば、上記の10進数形式のゲノムの場合、そのバイナリ表現は次のようになります。

type Gene = 0 | 1;

type Genome = Gene[];

const genome: Genome = [
  // エンジン係数。
  0, 1, 0, 1, 1, 0, 0, 0, 1, 1, // <- 17.5
  0, 0, 0, 1, 0, 1, 1, 1, 0, 0, // <- 0.059
  1, 1, 1, 0, 0, 0, 1, 1, 1, 0, // <- -46
  0, 1, 0, 1, 1, 1, 0, 0, 1, 0, // <- 25
  0, 1, 1, 1, 0, 0, 0, 1, 1, 1, // <- 156
  1, 0, 0, 1, 1, 0, 1, 1, 0, 0, // <- -0.085
  1, 0, 1, 0, 0, 1, 0, 1, 0, 1, // <- -0.207
  1, 0, 1, 1, 0, 0, 0, 0, 1, 1, // <- -0.546
  0, 0, 0, 1, 1, 0, 0, 1, 0, 0, // <- 0.071

  // ホイール係数。
  1, 1, 1, 0, 0, 1, 1, 0, 1, 0, // <- -58
  0, 1, 1, 0, 0, 0, 1, 0, 0, 1, // <- 41
  0, 0, 0, 0, 0, 0, 1, 0, 1, 0, // <- 0.011
  0, 1, 1, 1, 0, 1, 1, 1, 1, 1, // <- 252
  1, 1, 0, 0, 0, 1, 1, 0, 0, 0, // <- -3.5
  1, 0, 0, 0, 1, 0, 0, 1, 0, 0, // <- -0.017
  0, 0, 1, 1, 1, 1, 0, 0, 0, 1, // <- 1.532
  1, 1, 1, 1, 1, 0, 1, 1, 0, 1, // <- -360
  0, 0, 1, 0, 0, 0, 1, 0, 0, 0, // <- 0.157
];

うわー!バイナリゲノムは非常に難解に見えます。しかし、この 180 個のゼロとイチだけが、車の駐車場のでの振る舞いを定義していると想像できますか!まるで誰かのDNAをハッキングして、各遺伝子が正確に何を意味するかを知っているかのようです。素晴らしい!

ちなみに、Evolution Simulator のダッシュボードで、最もパフォーマンスの高い車の正確なゲノム値と係数を確認できます。

[画像: Car genomes and coefficients examples]

以下は、バイナリ形式から浮動小数点数の10進数形式への変換を実行するソースコードです(脳は、ゲノムをデコードし、ゲノムデータに基づいて筋肉信号を生成するためにこれを使用します)。

type Bit = 0 | 1;

type Bits = Bit[];

type PrecisionConfig = {
  signBitsCount: number,
  exponentBitsCount: number,
  fractionBitsCount: number,
  totalBitsCount: number,
};

type PrecisionConfigs = {
  custom: PrecisionConfig,
};

const precisionConfigs: PrecisionConfigs = {
  // より高速な進化の進行のためにカスタムメイドされた10ビット精度。
  custom: {
    signBitsCount: 1,
    exponentBitsCount: 4,
    fractionBitsCount: 5,
    totalBitsCount: 10,
  },
};

// 浮動小数点数のバイナリ表現を10進数の浮動小数点数に変換します。
function bitsToFloat(bits: Bits, precisionConfig: PrecisionConfig): number {
  const { signBitsCount, exponentBitsCount } = precisionConfig;

  // 符号を決定します。
  const sign = (-1) ** bits[0]; // -1^1 = -1, -1^0 = 1

  // エクスポーネント値を計算します。
  const exponentBias = 2 ** (exponentBitsCount - 1) - 1;
  const exponentBits = bits.slice(signBitsCount, signBitsCount + exponentBitsCount);
  const exponentUnbiased = exponentBits.reduce(
    (exponentSoFar: number, currentBit: Bit, bitIndex: number) => {
      const bitPowerOfTwo = 2 ** (exponentBitsCount - bitIndex - 1);
      return exponentSoFar + currentBit * bitPowerOfTwo;
    },
    0,
  );
  const exponent = exponentUnbiased - exponentBias;

  // フラクション値を計算します。
  const fractionBits = bits.slice(signBitsCount + exponentBitsCount);
  const fraction = fractionBits.reduce(
    (fractionSoFar: number, currentBit: Bit, bitIndex: number) => {
      const bitPowerOfTwo = 2 ** -(bitIndex + 1);
      return fractionSoFar + currentBit * bitPowerOfTwo;
    },
    0,
  );

  // すべての部分を組み合わせて最終的な数値を計算します。
  return sign * (2 ** exponent) * (1 + fraction);
}

// 浮動小数点数の8ビットバイナリ表現を10進数の浮動小数点数に変換します。
function bitsToFloat10(bits: Bits): number {
  return bitsToFloat(bits, precisionConfigs.custom);
}
バイナリゲノムを扱う脳関数

以前は、脳関数は engineCoefficients と wheelCoefficients の多項式係数の10進数形式で直接動作していました。しかし、これらの係数は現在、ゲノムのバイナリ形式でエンコードされています。ゲノムから係数を抽出する decodeGenome() 関数を追加し、脳関数を書き直しましょう。

// 車は16個の距離センサーを備えています。
const CAR_SENSORS_NUM = 8;

// 数値パラメータに接続されていない追加の数式係数。
const BIAS_UNITS = 1;

// 各数値パラメータをエンコードするために必要な遺伝子の数。
const GENES_PER_NUMBER = precisionConfigs.custom.totalBitsCount;

// 8つの距離センサーに基づいて、車の動作を定義する2つの数式を提供する必要があります。
// 1. エンジン数式(入力:8つのセンサー、出力:-1(後退)、0(ニュートラル)、+1(前進))
// 2. ホイール数式(入力:8つのセンサー、出力:-1(左)、0(直進)、+1(右))
const ENGINE_FORMULA_GENES_NUM = (CAR_SENSORS_NUM + BIAS_UNITS) * GENES_PER_NUMBER;
const WHEELS_FORMULA_GENES_NUM = (CAR_SENSORS_NUM + BIAS_UNITS) * GENES_PER_NUMBER;

// 車のバイナリゲノムの長さ。
const GENOME_LENGTH = ENGINE_FORMULA_GENES_NUM + WHEELS_FORMULA_GENES_NUM;

type DecodedGenome = {
  engineFormulaCoefficients: Coefficients,
  wheelsFormulaCoefficients: Coefficients,
}

// ゲノムをバイナリ形式から10進数形式に変換します。
const genomeToNumbers = (genome: Genome, genesPerNumber: number): number[] => {
  if (genome.length % genesPerNumber !== 0) {
    throw new Error('Wrong number of genes in the numbers genome');
  }
  const numbers: number[] = [];
  for (let numberIndex = 0; numberIndex < genome.length; numberIndex += genesPerNumber) {
    const number: number = bitsToFloat10(genome.slice(numberIndex, numberIndex + genesPerNumber));
    numbers.push(number);
  }
  return numbers;
};

// ゲノムをバイナリ形式から10進数形式に変換し、
// ゲノムを2つの係数セット(各筋肉に1セット)に分割します。
const decodeGenome = (genome: Genome): DecodedGenome => {
  const engineGenes: Gene[] = genome.slice(0, ENGINE_FORMULA_GENES_NUM);
  const wheelsGenes: Gene[] = genome.slice(
    ENGINE_FORMULA_GENES_NUM,
    ENGINE_FORMULA_GENES_NUM + WHEELS_FORMULA_GENES_NUM,
  );

  const engineFormulaCoefficients: Coefficients = genomeToNumbers(engineGenes, GENES_PER_NUMBER);
  const wheelsFormulaCoefficients: Coefficients = genomeToNumbers(wheelsGenes, GENES_PER_NUMBER);

  return {
    engineFormulaCoefficients,
    wheelsFormulaCoefficients,
  };
};

// エンジン筋肉のための脳関数を更新します。
export const getEngineMuscleSignal = (genome: Genome, sensors: Sensors): MuscleSignal => {
  const {engineFormulaCoefficients: coefficients} = decodeGenome(genome);
  const rawBrainSignal = linearPolynomial(coefficients, sensors);
  return brainToMuscleSignal(rawBrainSignal);
};

// ホイール筋肉のための脳関数を更新します。
export const getWheelsMuscleSignal = (genome: Genome, sensors: Sensors): MuscleSignal => {
  const {wheelsFormulaCoefficients: coefficients} = decodeGenome(genome);
  const rawBrainSignal = linearPolynomial(coefficients, sensors);
  return brainToMuscleSignal(rawBrainSignal);
};

自己運転車の問題設定

☝🏻 ついに、自己駐車カーを作成するという高レベルのタスクを、最適な 180 個の1とゼロの組み合わせ(最適な車のゲノム)を見つけるという、単純な低レベルのタスクに分解しました。シンプルに聞こえませんか?

ナイーブなアプローチ

「適切な」ゲノムを見つけるという問題にナイーブな方法でアプローチし、すべての可能な遺伝子の組み合わせを試すことができます。

  1. [0, ..., 0, 0]、そして...
  2. [0, ..., 0, 1]、そして...
  3. [0, ..., 1, 0]、そして...
  4. [0, ..., 1, 1]、そして...
  5. ...

しかし、少し計算してみましょう。180 ビットで、各ビットが 0 または 1 のいずれかである場合、2^180(または 1.53 * 10^54)の可能な組み合わせがあります。各車が駐車に成功するかどうかを確認するために 15秒 かかるとしましょう。また、一度に 10 台の車でシミュレーションを実行できるとしましょう。その場合、15 * (1.53 * 10^54) / 10 = 2.29 * 10^54 [秒] が必要になります。これは 7.36 * 10^46 [年] です。非常に長い待ち時間です。単なる余談ですが、キリストが生まれた後から経過した時間は 2.021 * 10^3 [年] にすぎません。

遺伝的アプローチ

最適なゲノム値を見つけるには、より高速なアルゴリズムが必要です。ここで遺伝的アルゴリズムが役立ちます。最適なゲノム値を見つけられないかもしれませんが、最適な値を見つけられる可能性があります。そして、さらに重要なのは、それほど長く待つ必要がないことです。Evolution Simulator を使用して、24 [時間] 以内にかなり良いゲノムを見つけることができました。

遺伝的アルゴリズムの基本

遺伝的アルゴリズム(GA)は自然選択のプロセスに触発されており、交差、突然変異、選択 のような生物学的にインスパイアされた演算子に依存して、最適化問題に対して高品質な解を生成するために一般的に使用されます。

車の「適切な」遺伝子の組み合わせを見つけるという問題は、最適化問題のように見えるため、GAがここで役立つ可能性が高いです。

遺伝的アルゴリズムを詳細にすべてカバーするわけではありませんが、大まかには次の基本的なステップを実行する必要があります。

  1. CREATE – 車の最初の世代は何もないところから生まれてくるわけではありません ので、最初にランダムな車のゲノム(バイナリ配列のセット 180 の長さ)のセットを生成します。例えば、~1000 台の車を作成するかもしれません。個体数が多いほど、最適な解を見つける(そしてより速く見つける)可能性が高まります。
  2. SELECT - 次のステップ(交配)のために、現在の世代から最も適した個体を選択する必要があります。各個体の適性は、フィットネス関数に基づいて定義されます。この場合、フィットネス関数は車が目標の駐車スペースにどれだけ近づいたかを示します。車が駐車スペースに近いほど、適性は高くなります。
  3. MATE – 単純に言うと、選択された「♂ 父車」と選択された「♀ 母車」が「交尾」できるようにし、それらのゲノムを ~50/50 の割合で混合して「♂♀ 子車」のゲノムを生成します。アイデアは、子車が親から最良(または最悪)のビットを取ることによって、自己駐車においてより良く(または悪く)なる可能性があるということです。
  4. MUTATE - 交配プロセス中に、一部の遺伝子が突然変異する可能性があります(子ゲノムの 1 と 0 が反転する)。これにより、子ゲノムの多様性が広がり、結果として子車の振る舞いの多様性も広がります。例えば、最初のビットがすべての ~1000 台の車で偶然 0 に設定されたと想像してください。最初のビットが 1 に設定された車を試す唯一の方法は、ランダムな突然変異を介してです。同時に、過度の突然変異は健全なゲノムを台無しにする可能性があります。
  5. 生成世代数が上限(例: 100 世代が経過)に達するか、またはトップパフォーマーの個体が期待されるフィットネス関数の値(例: 最良の車が駐車スペースに 1メートル 未満まで近づいた)に達するまで、「ステップ2」に戻ります。そうでない場合は終了します。

[画像: Genetic algorithm flow]

遺伝的アルゴリズムを使用して車の脳を進化させる

遺伝的アルゴリズムを起動する前に、「CREATE」、「SELECT」、「MATE」、「MUTATE」のステップのための関数を作成しましょう。

CREATEステップの関数

createGeneration() 関数は、ランダムなゲノムの配列(別名、個体群または世代)を作成し、2つのパラメータを受け取ります。

  • generationSize - 世代のサイズを定義します。この世代サイズは、世代から世代へと維持されます。
  • genomeLength - 車の個体群の各個体のゲノム長を定義します。この場合、ゲノムの長さは 180 になります。

各ゲノムの各遺伝子は、0 または 1 のいずれかになる 50/50 の確率があります。

type Generation = Genome[];

type GenerationParams = {
  generationSize: number,
  genomeLength: number,
};

function createGenome(length: number): Genome {
  return new Array(length)
    .fill(null)
    .map(() => (Math.random() < 0.5 ? 0 : 1));
}

function createGeneration(params: GenerationParams): Generation {
  const { generationSize, genomeLength } = params;
  return new Array(generationSize)
    .fill(null)
    .map(() => createGenome(genomeLength));
}
MUTATEステップの関数

mutate() 関数は、mutationProbability 値に基づいて、一部の遺伝子をランダムに突然変異させます。

例えば、mutationProbability = 0.1 の場合、各ゲノムが突然変異する確率は 10% です。長さ 10 のゲノムが [0, 0, 0, 0, 0, 0 ,0 ,0 ,0 ,0] のようになっているとしましょう。突然変異後、1つの遺伝子が突然変異する可能性があり、[0, 0, 0, 1, 0, 0 ,0 ,0 ,0 ,0] のようなゲノムが得られるかもしれません。

// 0から1の間の数値。
type Probability = number;

// @see: https://en.wikipedia.org/wiki/Mutation_(genetic_algorithm)
function mutate(genome: Genome, mutationProbability: Probability): Genome {
  for (let geneIndex = 0; geneIndex < genome.length; geneIndex += 1) {
    const gene: Gene = genome[geneIndex];
    const mutatedGene: Gene = gene === 0 ? 1 : 0;
    genome[geneIndex] = Math.random() < mutationProbability ? mutatedGene : gene;
  }
  return genome;
}
MATEステップの関数

mate() 関数は、father(父)と mother(母)のゲノムを受け取り、2つの子を生成します。実際のシナリオを模倣し、交配中にも突然変異を行います。

子ゲノムの各ビットは、父または母の対応するビットの値に基づいて定義されます。子が父または母のビットを継承する確率は 50/50% です。例えば、ゲノムの長さが 4 であるとしましょう(簡潔にするため)。

父のゲノム: [0, 0, 1, 1]
母のゲノム: [0, 1, 0, 1]
                  ↓  ↓  ↓  ↓
可能な子 #1: [0, 1, 1, 1]
可能な子 #2: [0, 0, 1, 1]

上記の例では、突然変異は考慮されていません。

関数の実装は次のとおりです。

// 一様交差を実行します。各ビットは、同等の確率でどちらかの親から選択されます。
// @see: https://en.wikipedia.org/wiki/Crossover_(genetic_algorithm)
function mate(
  father: Genome,
  mother: Genome,
  mutationProbability: Probability,
): [Genome, Genome] {
  if (father.length !== mother.length) {
    throw new Error('Cannot mate different species');
  }

  const firstChild: Genome = [];
  const secondChild: Genome = [];

  // 子を設けます。
  for (let geneIndex = 0; geneIndex < father.length; geneIndex += 1) {
    firstChild.push(
      Math.random() < 0.5 ? father[geneIndex] : mother[geneIndex]
    );
    secondChild.push(
      Math.random() < 0.5 ? father[geneIndex] : mother[geneIndex]
    );
  }

  return [
    mutate(firstChild, mutationProbability),
    mutate(secondChild, mutationProbability),
  ];
}
SELECTステップの関数

さらなる交配のために最も適した個体を選択するには、各ゲノムの適性を知る方法が必要です。これを行うために、いわゆるフィットネス関数を使用します。

フィットネス関数は常に解決しようとしている特定のタスクに関連しており、汎用的ではありません。この場合、フィットネス関数は車と駐車スペースの間の距離を測定します。車が駐車スペースに近いほど、適性は高くなります。フィットネス関数は後で実装しますが、現時点ではインターフェースを紹介します。

type FitnessFunction = (genome: Genome) => number;

さて、個体群の各個体のフィットネス値があるとしましょう。すべての個体をフィットネス値でソートし、最初の個体が最も強いものとしましょう。この配列から父親と母親をどのように選択すべきでしょうか?フィットネス値が高い個体ほど選択される確率が高くなるように選択を行う必要があります。weightedRandom() 関数がこれを支援します。

// 重みに基づいてランダムなアイテムを選択します。
// 重みが大きいアイテムほど頻繁に選択されます。
const weightedRandom = <T>(items: T[], weights: number[]): { item: T, index: number } => {
  if (items.length !== weights.length) {
    throw new Error('Items and weights must be of the same size');
  }

  // 累積重み配列を準備します。
  // 例:
  // - weights = [1, 4, 3]
  // - cumulativeWeights = [1, 5, 8]
  const cumulativeWeights: number[] = [];
  for (let i = 0; i < weights.length; i += 1) {
    cumulativeWeights[i] = weights[i] + (cumulativeWeights[i - 1] || 0);
  }

  // [0...sum(weights)] の範囲でランダムな数値を取得します。
  // 例:
  // - weights = [1, 4, 3]
  // - maxCumulativeWeight = 8
  // - ランダムな数値の範囲は [0...8] です。
  const maxCumulativeWeight = cumulativeWeights[cumulativeWeights.length - 1];
  const randomNumber = maxCumulativeWeight * Math.random();

  // 重みに基づいてランダムなアイテムを選択します。
  // 重みが大きいアイテムほど頻繁に選択されます。
  for (let i = 0; i < items.length; i += 1) {
    if (cumulativeWeights[i] >= randomNumber) {
      return {
        item: items[i],
        index: i,
      };
    }
  }
  return {
    item: items[items.length - 1],
    index: items.length - 1,
  };
};

この関数の使い方は非常に簡単です。例えば、バナナが大好きで、イチゴよりも頻繁に食べたいとしましょう。その場合、const fruit = weightedRandom(['banana', 'strawberry'], [9, 1]) と呼び出すことができ、≈9 回に 10 回は fruit 変数が banana に等しくなり、≈1 回に 10 回だけ strawberry に等しくなります。

交配プロセス中に最良の個体(チャンピオンと呼びましょう)を失うことを避けるために、longLivingChampionsPercentage(長寿チャンピオンの割合)というパラメータを導入することもできます。例えば、longLivingChampionsPercentage = 10 の場合、前の世代の最良の車の 10% が新しい世代に引き継がれます。これは、長生きして子供や孫さえも見ることができる長寿の個体がいると考えることができます。

実際の select() 関数の実装は次のとおりです。

// 0から100の間の数値。
type Percentage = number;

type SelectionOptions = {
  mutationProbability: Probability,
  longLivingChampionsPercentage: Percentage,
};

// @see: https://en.wikipedia.org/wiki/Selection_(genetic_algorithm)
function select(
  generation: Generation,
  fitness: FitnessFunction,
  options: SelectionOptions,
) {
  const { 
    mutationProbability,
    longLivingChampionsPercentage,
  } = options;

  const newGeneration: Generation = [];

  const oldGeneration = [...generation];
  // 最初の一つ - 最も適した一つ。
  oldGeneration.sort((genomeA: Genome, genomeB: Genome): number => {
    const fitnessA = fitness(genomeA);
    const fitnessB = fitness(genomeB);
    if (fitnessA < fitnessB) {
      return 1;
    }
    if (fitnessA > fitnessB) {
      return -1;
    }
    return 0;
  });

  // 長寿チャンピオンが新しい世代で生き続けることを許可します。
  const longLiversCount = Math.floor(longLivingChampionsPercentage * oldGeneration.length / 100);
  if (longLiversCount) {
    oldGeneration.slice(0, longLiversCount).forEach((longLivingGenome: Genome) => {
      newGeneration.push(longLivingGenome);
    });
  }

  // 各個体のフィットネスに関するデータを取得します。
  const fitnessPerOldGenome: number[] = oldGeneration.map((genome: Genome) => fitness(genome));

  // 次の世代が古い世代と同じサイズになるまで埋めます。
  while (newGeneration.length < generation.length) {
    // 集団からランダムな父親と母親を選択します。
    // 最も適した個体ほど選択される確率が高くなります。
    let father: Genome | null = null;
    let fatherGenomeIndex: number | null = null;
    let mother: Genome | null = null;
    let matherGenomeIndex: number | null = null;

    // 子を生成するために、父親と母親はお互いを必要とします。
    // 2つの異なる個体である必要があります。
    while (!father || !mother || fatherGenomeIndex === matherGenomeIndex) {
      const { 
        item: randomFather,
        index: randomFatherGenomeIndex,
      } = weightedRandom<Genome>(generation, fitnessPerOldGenome);

      const { 
        item: randomMother,
        index: randomMotherGenomeIndex,
      } = weightedRandom<Genome>(generation, fitnessPerOldGenome);

      father = randomFather;
      fatherGenomeIndex = randomFatherGenomeIndex;

      mother = randomMother;
      matherGenomeIndex = randomMotherGenomeIndex;
    }

    // 父親と母親に2人の子を産ませます。
    const [firstChild, secondChild] = mate(father, mother, mutationProbability);

    newGeneration.push(firstChild);

    // 長寿チャンピオンの数によっては、
    // 子供が一人しか入る場所がない可能性があります。残念。
    if (newGeneration.length < generation.length) {
      newGeneration.push(secondChild);
    }
  }

  return newGeneration;
}
フィットネス関数

車のフィットネスは、車と駐車スペースの距離によって定義されます。距離が大きいほど、フィットネスは低くなります。

計算される最終的な距離は、車の 4 つのタイヤと駐車スペースの対応する 4 つの角からの平均距離です。この距離を loss(損失)と呼び、fitness(適性)とは反比例の関係にあります。

[画像: The distance from the car to the parking spot]

車の中心から駐車スペースの中心までの距離を計算するだけでなく、各タイヤと各コーナーの距離を個別に計算することで、車は駐車スペースに対して適切な向きを維持できます。

空間内の2点間の距離は、ピタゴラスの定理 に基づいて次のように計算されます。

type NumVec3 = [number, number, number];

// 空間内の2点間のXZ距離を計算します。
// Y軸方向の垂直距離は考慮されません。
const euclideanDistance = (from: NumVec3, to: NumVec3) => {
  const fromX = from[0];
  const fromZ = from[2];
  const toX = to[0];
  const toZ = to[2];
  return Math.sqrt((fromX - toX) ** 2 + (fromZ - toZ) ** 2);
};

車と駐車スペースの間の距離(loss)は次のように計算されます。

type RectanglePoints = {
  fl: NumVec3, // Front-left
  fr: NumVec3, // Front-right
  bl: NumVec3, // Back-left
  br: NumVec3, // Back-right
};

type GeometricParams = {
  wheelsPosition: RectanglePoints,
  parkingLotCorners: RectanglePoints,
};

const carLoss = (params: GeometricParams): number => {
  const { wheelsPosition, parkingLotCorners } = params;

  const { 
    fl: flWheel, 
    fr: frWheel, 
    br: brWheel, 
    bl: blWheel,
  } = wheelsPosition;

  const { 
    fl: flCorner, 
    fr: frCorner, 
    br: brCorner, 
    bl: blCorner,
  } = parkingLotCorners;

  const flDistance = euclideanDistance(flWheel, flCorner);
  const frDistance = euclideanDistance(frWheel, frCorner);
  const brDistance = euclideanDistance(brWheel, brCorner);
  const blDistance = euclideanDistance(blWheel, blCorner);

  return (flDistance + frDistance + brDistance + blDistance) / 4;
};

fitness は loss に反比例するため、次のように計算します。

const carFitness = (params: GeometricParams): number => {
  const loss = carLoss(params);
  // ゼロ除算を避けるために +1 を追加します。
  return 1 / (loss + 1);
};

Evolution Simulator のダッシュボードで、特定のゲノムと現在の車の位置に対する fitness と loss の値を確認できます。

[画像: Evolution simulator dashboard]

進化の起動

進化関数をまとめましょう。「世界を創造」し、進化ループを起動し、時間を進め、世代を進化させ、車に駐車方法を学ばせます。

各車のフィットネス値を取得するには、仮想3D世界での車の動作シミュレーションを実行する必要があります。Evolution Simulator はまさにそれを実行します。これは、Three.js で作成された 以下のコードをシミュレーターで実行します。

// 進化設定例。
// Evolution Simulator で設定可能。
const GENERATION_SIZE = 1000;
const LONG_LIVING_CHAMPIONS_PERCENTAGE = 6;
const MUTATION_PROBABILITY = 0.04;
const MAX_GENERATIONS_NUM = 40;

// フィットネス関数。
// 車の年次健康診断のようなものです。
const carFitnessFunction = (genome: Genome): number => {
  // Evolution simulator は、各車のフィットネス値を fitnessValues マップに格納して計算します。
  // ここでは、現在の世代の車の事前に計算されたフィットネス値を取得するだけです。
  const genomeKey = genome.join('');
  return fitnessValues[genomeKey];
};

// 最初の車の世代で「世界」を作成します。
let generationIndex = 0;
let generation: Generation = createGeneration({
  generationSize: GENERATION_SIZE,
  genomeLength: GENOME_LENGTH, // <- 180遺伝子
});

// 「時間」を開始します。
while(generationIndex < MAX_GENERATIONS_NUM) {
  // ここでシミュレーションが必要です。フィットネス値を事前に計算するため。

  // 現在の世代の選択、交配、突然変異を行います。
  generation = select(
    generation,
    carFitnessFunction,
    {
      mutationProbability: MUTATION_PROBABILITY,
      longLivingChampionsPercentage: LONG_LIVING_CHAMPIONS_PERCENTAGE,
    },
  );

  // 「時間」を進めます。
  generationIndex += 1;
}

// ここで、最新世代の最も適した個体を確認できます。
const fittestCar = generation[0];

select() 関数を実行した後、generation 配列はフィットネス値で降順にソートされます。したがって、最も適した車は常に配列の最初の車になります。

ランダムなゲノムを持つ第1世代の車は、次のような振る舞いをします。

[画像: The 1st generation of cars with random genomes]

約40世代目になると、車は自己駐車とは何かを学び始め、駐車スペースに近づくようになります。

[画像: The 40th generation start learning how to park]

より挑戦的な初期条件での別の例です。

[画像: More challenging starting point for self-parking]

車は途中で他の車にぶつかったり、駐車スペースに完璧に収まらなかったりしますが、これは彼らにとって世界の創造からまだ40世代目なのですから、車にもっと学習する時間を与えても良いでしょう。

世代から世代へと、loss の値が減少していく(つまり、フィットネス値が上昇していく)のがわかります。P50 Avg Loss は、最も適した車の 50% の平均損失値(車から駐車スペースまでの平均距離)を示します。Min Loss は、各世代で最も適した車の損失値を示します。

[画像: Loss history]

平均して、世代の最も適した車の 50% は駐車スペースに近づくことを学習していることがわかります(35世代で駐車スペースから 5.5m 離れた状態から 3.5m まで)。Min Loss 値の傾向はそれほど明確ではありませんが(1m から 0.5m まで、ノイズ信号あり)、上記の С анимации から、車が基本的な駐車動作を学習したことがわかります。

結論

この記事では、自己駐車カーを作成するという高レベルのタスクを、最適な 180 個の1とゼロの組み合わせ(最適な車のゲノム)を見つけるという、単純な低レベルのタスクに分解しました。

次に、遺伝的アルゴリズムを適用して最適な車のゲノムを見つけました。これにより、ナイーブなアプローチを何年も実行する代わりに、数時間のシミュレーションでかなり良い結果を得ることができました。

タクシー Self-parking Car Evolution Simulator を起動して、ブラウザで直接進化のプロセスを確認できます。シミュレーターでは以下の機会が提供されます。

この記事で示された完全な遺伝子ソースコードは、Evolution Simulator リポジトリ にもあります。もしあなたが、コードの行数を数えて500行未満であることを確認するような人なら(テストを除く)、こちら でコードを確認してください 🥸。

コードとシミュレーターには、まだいくつかの未解決の問題があります。

  • 車の脳は単純化されすぎており、例えばニューラルネットワークではなく線形方程式を使用しています。これにより、車は新しい環境や新しいタイプの駐車場に適応できません。
  • 車が他の車に衝突した場合に車のフィットネス値を減らさないため、車は交通事故を起こすことに対して「罪悪感」を感じません。
  • 進化シミュレーターは安定性が低いです。つまり、同じ車のゲノムが異なるフィットネス値を生成する可能性があり、進化の効率が低下します。
  • また、進化シミュレーターはパフォーマンスの点で非常に重いため、例えば一度に 1000 台の車を訓練できないため、進化の進行が遅くなります。
  • さらに、Evolution Simulator はブラウザタブを開いてアクティブにしておく必要があり、シミュレーションを実行できません。
  • その他 多数 ...

しかし、この記事の目的は、遺伝的アルゴリズムの仕組みを学びながら楽しむことであり、本番対応の自己駐車テスラを構築することではありませんでした。したがって、上記の問題点があっても、この記事を楽しんでいただけたことを願っています。

[画像: Fin]