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

TLDR

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

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

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

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

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

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

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

Генетический алгоритм для этого проекта реализован на 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. Итак, даже несмотря на упомянутые выше проблемы, я надеюсь, что вы хорошо провели время, читая эту статью.

---

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩