Самопаркующийся авто за 500 строк кода

TLDR

В этой статье мы научим авто самостоятельно парковаться с помощью генетического алгоритма.

Мы создадим первое поколение авто с произвольными геномами, которое будет вести себя примерно так:

Примерно на сороковом поколении авто начнут понимать, что такое авто-парковка, и начнут приближаться к парковочному месту:

Другой пример с более сложной отправной точкой:

Да-да, авто врезаются в другие авто и паркуются не идеально, но это лишь 40 поколение с момента создания их мира, поэтому будьте милостивы и позвольте авто расти :D

Вы можете запустить симулятор, чтобы увидеть процесс эволюции прямо в браузере. Симулятор предоставляет следующие возможности:

• обучать авто с нуля и настраивать генетические параметры
• наблюдать обученные самопаркующиеся авто в действии
• парковаться вручную

Генетический алгоритм для этого проекта реализован на TypeScript. Полный исходный код проекта можно найти в этом репозитории.

Мы будем использовать генетический алгоритм для эволюционирования геномов авто. Однако статья затрагивает только основы алгоритма и не является исчерпывающим руководством по генетическим алгоритмам.

Готовы? Тогда поехали.

План

Шаг за шагом мы перейдем от высокоуровневой задачи создания самопаркующегося авто к простой низкоуровневой задаче поиска оптимальной комбинации 180 битов (поиска оптимального генома авто).

Мы собираемся сделать следующее:

1. 💪🏻 Дать авто мышцы (мускулы) (двигатель, рулевое колесо), чтобы оно могло двигаться к парковочному месту.
2. 👀 Дать авто глаза (сенсоры или датчики), чтобы оно могло видеть препятствия вокруг.
3. 🧠 Дать авто мозг, чтобы оно могло управлять мышцами (движениями) на основе того, что оно видит (препятствия через сенсоры). Мозг будет простой чистой функцией движения = f(сенсоры)
4. 🧬 Эволюционировать мозг, чтобы совершать правильные движения на основе данных сенсоров. Здесь мы будем применять генетический алгоритм. Поколение за поколением наша функция мозга движения = f(сенсоры) будет учиться парковаться.

Даем авто мышцы

Для того, чтобы двигаться, авто нужны "мышцы". Дадим авто 2 типа мышц:

1. Мышцы двигателя — позволяют авто двигаться ↓ назад, ↑ вперед или ◎ продолжать движение (нейтральная передача)
2. Мышцы руля — позволяют авто поворачивать ← влево, → вправо или ◎ двигаться прямо

С этими двумя мышцами авто сможет выполнять следующие движения:

В нашем случае мышцы — это приемники сигналов, поступающих от мозга каждые 100 мс. Мышцы ведут себя по-разному в зависимости от сигнала мозга. Мы поговорим о "мозге" ниже, а сейчас допустим, что мозг может посылать 3 сигнала для каждой мышцы: -1, 0 или +1.

type MuscleSignal = -1 | 0 | 1;

Например, мозг может послать сигнал со значением +1 в мышцу двигателя и авто начнет двигаться вперед. Сигнал -1 в мышцу двигателя двигает авто назад. Если мозг посылает сигнал -1 в мышцу руля, авто поворачивает налево и т.д.

Вот как значения сигнала мозга сопоставляются с действиями мышц в нашем случае:

В случае ручной парковки в симуляторе при нажатии одной из клавиш WASD (или касании сенсорного экрана) в мышцы посылаются сигналы -1, 0 или +1.

Даем авто глаза

Перед тем, как наше авто научится парковаться с помощью мышц, оно должно иметь возможность "видеть" окружение. Дадим ему 8 глаз в форме сенсоров расстояния:

• каждый сенсор обнаруживает препятствие на расстоянии от 0 до 4 м
• каждый сенсор отправляет информацию о видимом препятствии в мозг каждые 100 мс
• если сенсор не видит препятствия, он отправляет в мозг значение 0. Если значение сенсора чуть больше нуля (например, 0.01), значит, препятствие находится очень близко

С помощью симулятора можно увидеть, как меняется цвет каждого сенсора в зависимости от близости препятствия.

type Sensors = number[];

Даем авто мозг

На данный момент наше авто может видеть и двигаться, но отсутствует "координатор", который будет трансформировать сигналы от глаз в соответствующие движения мышц. Нам нужен мозг.

Входные данные мозга

В качестве входных данных от сенсоров каждые 100 мс мозг будет получать 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]

Выходные данные

Каждые 100 мс мозг должен генерировать 2 целых числа:

1. Сигнал для двигателя — engineSignal.
2. Сигнал для руля — wheelSignal.

Каждое число должно иметь тип MuscleSignal и принимать одно из 3 значений: -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.

Однако, вместо нейронных сетей, мы выберем гораздо более простой подход и будем использовать два линейных полинома с несколькими переменными (если быть точнее, то в каждом полиноме будет ровно 8 переменных, по 1 на сенсор), которые будут выглядеть примерно так:

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

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

Где:

• [s0, s1, ..., s7] — 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('Количество коэффициентов и переменных не совпадает');
  }
  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. Например, число, близкое к 0, будет преобразовано в -1, число, близкое к 0.5, будет преобразовано в 0, а число, близкое к 1, будет преобразовано в 1.

Для выполнения первого преобразования нам потребуется сигмоида, реализующая следующую формулу:

Она преобразует любое число с плавающей запятой (ось x) в число в диапазоне (0...1) (ось y). Это именно то, что нам нужно.

Вот как выглядят шаги преобразования на сигмовидном графике:

Возможная реализация двух упомянутых выше преобразований:

// Вычисляет сигмоидное значение для переданного числа
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);
}

Геном авто (ДНК)

Основной вывод предыдущего раздела: коэффициенты [e0, e1, ..., e8] и [w0, w1, ..., w8] определяют поведение авто. Эти 18 чисел вместе формируют уникальный геном авто (его ДНК, если угодно).

Геном авто в десятичной форме

Объединим коэффициенты [e0, e1, ..., e8] и [w0, w1, ..., w8] вместе для формирования генома авто в десятичной форме:

// Геном авто - это список десятичных чисел (коэффициентов)
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]

Геном авто в двоичной форме

Сделаем шаг вперед (на уровень генов) и преобразуем десятичные числа генома авто в двоичный формат (в 1 и 0).

Я подробно описал процесс преобразования чисел с плавающей запятой в двоичные числа в статье "Двоичное представление чисел с плавающей запятой". Взгляните на нее, если возникнут вопросы.

Пример преобразования числа с плавающей запятой в 16-битное двоичное число:

В нашем случае для уменьшения длины генома мы конвертируем каждое число в нестандартное 10-битное число (1 бит знака, 4 бита экспоненты и 5 дробных битов).

Всего у нас 18 коэффициентов, каждый будет конвертирован в 10-битное число. Это означает, что геном авто будет представлять собой массив из 0 и 1 длиной 18 * 10 = 180 бит.

Например, геном в десятичном формате, упомянутый выше, в двоичном формате будет выглядеть так:

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 нулей и единиц определяют поведение авто на парковке! Это все равно, что хакнуть чужую ДНК и точно определить, что делает каждый ген. Потрясающе!

Кстати, точные значения геномов и коэффициентов лучшего авто можно видеть на панели управления симулятора:

Вот исходный код, который выполняет преобразование чисел с плавающей запятой из двоичного в десятичный формат (это понадобится мозгу для декодирования генома и создания мышечных сигналов на основе данных генома):

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,
  },
};

// Преобразует числа с плавающей запятой из бинарного в десятичный формат
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-битное двоичное число с плавающей запятой в десятичное
function bitsToFloat10(bits: Bits): number {
  return bitsToFloat(bits, precisionConfigs.custom);
}

Функция мозга для работы с двоичным геномом

Ранее функция мозга работала с полиномиальными коэффициентами engineCoefficients и wheelCoefficients напрямую. Однако сейчас эти коэффициенты кодируются в бинарную форму генома. Добавим функцию decodeGenome для извлечения коэффициентов из генома и перепишем функции мозга:

// Авто имеет 8 сенсоров расстояния
const CAR_SENSORS_NUM = 8;

// Дополнительный коэффициент, не связанный с сенсорами
const BIAS_UNITS = 1;

// Количество генов для кодирования каждого числового параметра в формулах
const GENES_PER_NUMBER = precisionConfigs.custom.totalBitsCount;

// Нам требуется 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,
}

// Преобразует геном из бинарной формы в десятичную
const genomeToNumbers = (genome: Genome, genesPerNumber: number): number[] => {
  if (genome.length % genesPerNumber !== 0) {
    throw new Error('Неверное количество генов');
  }
  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;
};

// Преобразует геном из бинарной формы в десятичную и
// делит геном на 2 набора коэффициентов (по одному на каждую мышцу)
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. [0, ..., 0, 0]
2. [0, ..., 0, 1]
3. [0, ..., 1, 0]
4. [0, ..., 1, 1]
5. и т.д.

Но обратимся к математике. 180 нулей или единиц дают нам 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 [лет].

Генетический подход

Нам нужен более быстрый алгоритм поиска оптимального значения генома. Здесь в игру вступает генетический алгоритм. Мы можем не найти лучшего значения генома, но существует вероятность нахождения оптимального значения. И, что еще важнее, нам не нужно долго ждать. С помощью симулятора я нашел довольно хороший геном за 24 [часа].

Основы генетического алгоритма

Генетические алгоритмы (ГА), вдохновленные процессом естественного отбора, обычно используются для нахождения высококачественных решений задач оптимизации, полагаясь на биологически обусловленные операторы, такие как скрещивание (crossover), мутация (mutation) и отбор (selection).

Задача нахождения "достаточно хорошей" комбинации генов для каждого авто выглядит как задача оптимизации, поэтому велика вероятность того, что ГА хорошо с ней справится.

Мы не будем рассматривать ГА во всех подробностях, но на высоком уровне нам необходимо выполнить следующие шаги:

1. СОЗДАНИЕ — самое первое поколение авто не может возникнуть из ниоткуда, поэтому мы сгенерируем набор произвольных геномов (набор бинарных массивов длиной 180). Например, мы можем создать ~1000 авто. Чем больше популяция, тем выше шансы быстро найти оптимальное решение (но тем медленнее будет выполняться программа).
2. ОТБОР — необходимо отобрать лучших (наиболее приспособленных — fittest) особей для дальнейшего скрещивания (см. следующий шаг). Приспособленность каждой особи будет определяться функцией приспособленности (fitness function), которая в нашем случае будет показывать, насколько близко авто подобралось к парковочному месту. Чем ближе, тем лучше.
3. СКРЕЩИВАНИЕ — простыми словами, мы позволяем "♂ авто отцам" "скрещиваться" с "♀ авто матерями" для смешения их геномов в пропорции ~50/50 и производства геномов "♂♀ авто детей". Идея в том, что дети могут быть лучше (или хуже) в парковке, получая лучшие (или худшие) биты от родителей.
4. МУТАЦИЯ — в процессе скрещивания некоторые гены могут произвольно мутировать (1 и 0 в геноме потомка могут меняться местами). Это может привести к более широкому разнообразию геномов потомков и, как следствие, к более вариативному поведению авто. Представьте, что первый бит всех ~1000 авто был случайно установлен в 0. Единственный способ попробовать авто с первым битом, установленным в 1 — произвольные мутации. В тоже время частые мутации могут испортить хорошие геномы.
5. Возврат к шагу 2 до тех пор, пока количество поколений не достигнет лимита (например, 100), или пока лучшие особи не достигнут ожидаемого показателя приспособленности (например, лучшее авто приблизится к парковочному месту ближе чем на 1 метр).

Развитие мозга авто с помощью генетического алгоритма

Создадим функции для каждого шага генетического алгоритма.

Функции шага создания

Функция createGeneration будет создавать массив произвольных геномов (популяцию или поколение) и будет принимать 2 параметра:

• generationSize — размер популяции. Он будет сохраняться между поколениями
• genomeLength — длина генома каждой особи. В нашем случае длина генома будет составлять 180

Каждый ген может быть 1 или 0 с вероятностью 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 будет произвольно мутировать некоторые гены на основе значения mutationProbability (вероятность мутации).

Например, mutationProbability = 0.1 означает 10% вероятность, что ген будет мутирован. Допустим, у нас есть геном длиной 10, который выглядит как [0, 0, 0, 0, 0, 0 ,0 ,0 ,0 ,0]. Тогда после мутации есть шанс мутирования одного гена и получения генома, который выглядит как [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 принимает геномы отца и матери и производит 2 потомков. В процессе скрещивания также возможна мутация (как в реальной жизни).

Каждый бит потомка будет определяться на основе значений соответствующих битов генома отца или матери. Вероятность наследования бита отца или матери составляет 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('Невозможно скрестить разные виды');
  }

  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),
  ];
}

Функции шага отбора

Для выбора лучших особей нам нужен способ определения приспособленности каждого генома. Для этого мы будем использовать так называемую функцию приспособленности (фитнес-функцию).

Фитнес-функция всегда связана с конкретной решаемой задачей, она не является универсальной. В нашем случае фитнес-функция будет измерять расстояние между авто и парковочным местом. Чем ближе авто к месту, тем лучше его приспособленность. Мы реализуем фитнес-функцию немного позже, сейчас же представим для нее интерфейс:

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('Разное количество элементов и весов');
  }

  // Готовим массив совокупных весов.
  // Например:
  // - 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 случае — 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;

    // Для производства потомства требуется две разные особи
    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;
    }

    // Получаем потомство
    const [firstChild, secondChild] = mate(father, mother, mutationProbability);

    newGeneration.push(firstChild);

    // В зависимости от числа долгожителей, место
    // может остаться только для одного потомка
    if (newGeneration.length < generation.length) {
      newGeneration.push(secondChild);
    }
  }

  return newGeneration;
}

Функция приспособленности

Приспособленность авто будет определяться расстоянием от авто до парковочного места. Чем больше расстояние, тем ниже приспособленность.

Итоговое расстояние будет вычисляться как среднее расстояние от 4 колес авто к соответствующим 4 углам парковочного места. Это расстояние мы будем называть loss. Оно будет обратно пропорционально fitness.

Вычисление расстояния между каждым колесом и каждым углом отдельно (вместо вычисления расстояния от центра автомобиля до центра парковочного места) позволит автомобилю сохранять правильную ориентацию относительно места.

Расстояние между двумя точками в пространстве будет рассчитываться на основе теоремы Пифагора следующим образом:

type NumVec3 = [number, number, number];

// Вычисляет расстояние XZ между 2 точками в пространстве.
// Вертикальное расстояние 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, // передний левый угол
  fr: NumVec3, // передний правый
  bl: NumVec3, // задний левый
  br: NumVec3, // задний правый
};

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 во избежание деления на 0
  return 1 / (loss + 1);
};

Значения fitness и loss для конкретного генома и текущего положения авто можно увидеть на панели инструментов симулятора:

Запуск эволюции

Объединим функции эволюции. Мы собираемся "создать мир", запустить цикл эволюции, заставить время течь, поколение развиваться, а авто учиться парковаться.

Чтобы получить показатели приспособленности каждого авто, нам нужно запустить симуляцию в виртуальном трехмерном мире. Симулятор эволюции делает именно это — он запускает приведенный ниже код в симуляторе, созданном с помощью Three.js:

// Пример настройки эволюции.
// Настройки устанавливаются в симуляторе
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 => {
  // Симулятор вычисляет и сохраняет показатели приспособленности каждого авто в карте `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 сортируется по значениям приспособленности в порядке убывания. Таким образом, наиболее приспособленное авто всегда будет первым в массиве.

Первое поколение авто с произвольными геномами будет вести себя примерно так:

Примерно на сороковом поколении авто начинают понимать, что такое авто-парковка, и начинают приближаться к парковочному месту:

Другой пример с более сложной отправной точкой:

Авто по пути сталкиваются с другими авто, а также не идеально паркуются, но это всего лишь 40 поколение, так что дайте авто еще немного времени на обучение.

Из поколения в поколение мы видим, как значения loss снижаются (что означает, что значения fitness растут). P50 Avg Loss показывает среднее значение loss (среднее расстояние от авто до места парковки) для 50% наиболее приспособленных авто. Min Loss показывает значение loss самого приспособленного авто в каждом поколении.

Видно, что в среднем 50% самых приспособленных авто поколения учатся приближаться к парковочному месту (от 5,5 м до 3,5 м за 35 поколений). Тенденция значений Min Loss менее очевидна (от 1 м до 0,5 м с некоторым шумом), однако на приведенной выше анимации видно, что авто выучили некоторые основные движения для парковки.

Заключение

В этой статье мы свели задачу высокого уровня по созданию самопаркующегося авто к простой задаче низкого уровня по поиску оптимальной комбинации 180 единиц и нулей (поиск оптимального генома автомобиля).

Затем мы применили генетический алгоритм для нахождения оптимального генома авто. Это позволило нам получить довольно хорошие результаты за несколько часов моделирования (вместо многих лет в случае использования наивного подхода).

Вы можете запустить симулятор, чтобы увидеть процесс эволюции прямо в браузере. Он предоставляет следующие возможности:

• обучать авто с нуля и самостоятельно настраивать генетические параметры
• видеть обученные авто с функцией авто-парковки в действии
• парковать авто вручную

Полный исходный код, показанный в этой статье, можно найти в этом репозитории.

Проблемы и нерешенные задачи:

• мозг авто слишком упрощен и использует линейные уравнения вместо, скажем, нейронных сетей. Это делает авто неспособным адаптироваться к новому окружению или новым типам парковок
• значение приспособленности авто не уменьшается, когда оно врезается в другое авто. Поэтому авто не "чувствует" никакой вины за ДТП
• симулятор эволюции нестабилен. Это означает, что один и тот же геном авто может давать разные значения приспособленности, что делает эволюцию менее эффективной
• симулятор эволюции также очень тяжел с точки зрения производительности, что замедляет процесс эволюции, поскольку мы не можем обучать, скажем, 1000 авто одновременно
• кроме того, для моделирования эволюции симулятору требуется, чтобы вкладка браузера была открыта и активна
• и др.

Однако цель этой статьи заключалась в том, чтобы немного развлечься, изучая, как работает генетический алгоритм, а не в том, чтобы создать готовую к производству беспилотную Tesla. Итак, даже несмотря на упомянутые выше проблемы, я надеюсь, что вы хорошо провели время, читая эту статью.

---