Мы создадим первое поколение авто с произвольными геномами, которое будет вести себя примерно так:
Примерно на сороковом поколении авто начнут понимать, что такое авто-парковка, и начнут приближаться к парковочному месту:
Другой пример с более сложной отправной точкой:
Да-да, авто врезаются в другие авто и паркуются не идеально, но это лишь 40 поколение с момента создания их мира, поэтому будьте милостивы и позвольте авто расти :D
Вы можете запустить симулятор, чтобы увидеть процесс эволюции прямо в браузере. Симулятор предоставляет следующие возможности:
Генетический алгоритм для этого проекта реализован на TypeScript. Полный исходный код проекта можно найти в этом репозитории.
Мы будем использовать генетический алгоритм для эволюционирования геномов авто. Однако статья затрагивает только основы алгоритма и не является исчерпывающим руководством по генетическим алгоритмам.
Готовы? Тогда поехали.
План
Шаг за шагом мы перейдем от высокоуровневой задачи создания самопаркующегося авто к простой низкоуровневой задаче поиска оптимальной комбинации 180 битов (поиска оптимального генома авто).
Мы собираемся сделать следующее:
Дать авто мышцы (мускулы) (двигатель, рулевое колесо), чтобы оно могло двигаться к парковочному месту.
Дать авто глаза (сенсоры или датчики), чтобы оно могло видеть препятствия вокруг.
Дать авто мозг, чтобы оно могло управлять мышцами (движениями) на основе того, что оно видит (препятствия через сенсоры). Мозг будет простой чистой функцией движения = f(сенсоры)
Эволюционировать мозг, чтобы совершать правильные движения на основе данных сенсоров. Здесь мы будем применять генетический алгоритм. Поколение за поколением наша функция мозгадвижения = f(сенсоры) будет учиться парковаться.
Даем авто мышцы
Для того, чтобы двигаться, авто нужны "мышцы". Дадим авто 2 типа мышц:
Мышцы двигателя — позволяют авто двигаться ↓ назад, ↑ вперед или ◎ продолжать движение (нейтральная передача)
Мышцы руля — позволяют авто поворачивать ← влево, → вправо или ◎ двигаться прямо
С этими двумя мышцами авто сможет выполнять следующие движения:
В нашем случае мышцы — это приемники сигналов, поступающих от мозга каждые 100 мс. Мышцы ведут себя по-разному в зависимости от сигнала мозга. Мы поговорим о "мозге" ниже, а сейчас допустим, что мозг может посылать 3 сигнала для каждой мышцы: -1, 0 или +1.
type MuscleSignal = -1 | 0 | 1;
Например, мозг может послать сигнал со значением +1 в мышцу двигателя и авто начнет двигаться вперед. Сигнал -1 в мышцу двигателя двигает авто назад. Если мозг посылает сигнал -1 в мышцу руля, авто поворачивает налево и т.д.
Вот как значения сигнала мозга сопоставляются с действиями мышц в нашем случае:
Мышца
-1
0
1
Двигатель
↓ Назад
◎ Нейтраль
↑ Вперед
Руль
← Налево
◎ Прямо
→ Направо
В случае ручной парковки в симуляторе при нажатии одной из клавиш WASD (или касании сенсорного экрана) в мышцы посылаются сигналы -1, 0 или +1.
Даем авто глаза
Перед тем, как наше авто научится парковаться с помощью мышц, оно должно иметь возможность "видеть" окружение. Дадим ему 8 глаз в форме сенсоров расстояния:
каждый сенсор обнаруживает препятствие на расстоянии от 0 до 4 м
каждый сенсор отправляет информацию о видимом препятствии в мозг каждые 100 мс
если сенсор не видит препятствия, он отправляет в мозг значение 0. Если значение сенсора чуть больше нуля (например, 0.01), значит, препятствие находится очень близко
С помощью симулятора можно увидеть, как меняется цвет каждого сенсора в зависимости от близости препятствия.
type Sensors = number[];
Даем авто мозг
На данный момент наше авто может видеть и двигаться, но отсутствует "координатор", который будет трансформировать сигналы от глаз в соответствующие движения мышц. Нам нужен мозг.
Входные данные мозга
В качестве входных данных от сенсоров каждые 100 мсмозг будет получать 8 чисел с плавающей запятой, каждое в диапазоне [0...4]. Входные данные могут выглядеть так:
Где brainToMuscleSignal — это функция, конвертирующая сырые сигналы мозга (числа с плавающей запятой) в сигналы мышц (числа -1, 0 или +1), которые мышцы способны понять. Мы реализуем эту функцию преобразования позже.
Сейчас главный вопрос — что представляет собой brainFunction?
Чтобы сделать автомобиль умнее, а его движения более сложными, можно использовать многослойный перцептрон. Название немного пугающее, но это просто нейронная сеть с базовой архитектурой (думайте об этом как о формуле с большим количеством параметров/коэффициентов).
Однако, вместо нейронных сетей, мы выберем гораздо более простой подход и будем использовать два линейных полинома с несколькими переменными (если быть точнее, то в каждом полиноме будет ровно 8 переменных, по 1 на сенсор), которые будут выглядеть примерно так:
[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)) {
thrownewError('Количество коэффициентов и переменных не совпадает');
}
let result = 0;
coefficients.forEach((coefficient: number, coefficientIndex: number) => {
if (coefficientIndex < variables.length) {
result += coefficient * variables[coefficientIndex];
} else {
// Последний коэффициент добавляется без умножения
result += coefficient
}
});
return result;
};
В этом случае мозг авто будет состоять из 2 полиномов и будет выглядеть так:
Результатом функции linearPolynomial является число с плавающей запятой. Функция brainToMuscleSignal должна конвертировать широкий диапазон чисел с плавающей запятой в 3 целых числа. Она будет это делать в 2 этапа:
Преобразование любого числа с плавающей запятой (например, 0.456, 3673.45 или -280) в число с плавающей запятой в диапазоне (0...1) (например, 0.05 или 0.86).
Преобразование числа с плавающей запятой в диапазоне (0...1) в целые числа -1, 0 или +1. Например, число, близкое к 0, будет преобразовано в -1, число, близкое к 0.5, будет преобразовано в 0, а число, близкое к 1, будет преобразовано в 1.
Для выполнения первого преобразования нам потребуется сигмоида, реализующая следующую формулу:
Она преобразует любое число с плавающей запятой (ось x) в число в диапазоне (0...1) (ось y). Это именно то, что нам нужно.
Вот как выглядят шаги преобразования на сигмовидном графике:
Возможная реализация двух упомянутых выше преобразований:
// Вычисляет сигмоидное значение для переданного числаconst sigmoid = (x: number): number => {
return1 / (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)) {
return1;
}
return0;
};
// Преобразует сигнал мозга в сигнал мышц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] вместе для формирования генома авто в десятичной форме:
Пример преобразования числа с плавающей запятой в 16-битное двоичное число:
В нашем случае для уменьшения длины генома мы конвертируем каждое число в нестандартное 10-битное число (1 бит знака, 4 бита экспоненты и 5 дробных битов).
Всего у нас 18 коэффициентов, каждый будет конвертирован в 10-битное число. Это означает, что геном авто будет представлять собой массив из 0 и 1 длиной 18 * 10 = 180 бит.
Например, геном в десятичном формате, упомянутый выше, в двоичном формате будет выглядеть так:
О боже! Бинарный геном выглядит так загадочно. Но эти 180 нулей и единиц определяют поведение авто на парковке! Это все равно, что хакнуть чужую ДНК и точно определить, что делает каждый ген. Потрясающе!
Кстати, точные значения геномов и коэффициентов лучшего авто можно видеть на панели управления симулятора:
Вот исходный код, который выполняет преобразование чисел с плавающей запятой из двоичного в десятичный формат (это понадобится мозгу для декодирования генома и создания мышечных сигналов на основе данных генома):
Ранее функция мозга работала с полиномиальными коэффициентами 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) {
thrownewError('Неверное количество генов');
}
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,
};
};
// Обновляет функцию мозга для мышцы двигателяexportconst getEngineMuscleSignal = (genome: Genome, sensors: Sensors): MuscleSignal => {
const { engineFormulaCoefficients: coefficients } = decodeGenome(genome);
const rawBrainSignal = linearPolynomial(coefficients, sensors);
return brainToMuscleSignal(rawBrainSignal);
};
// Обновляет функцию мозга для мышцы руляexportconst getWheelsMuscleSignal = (genome: Genome, sensors: Sensors): MuscleSignal => {
const { wheelsFormulaCoefficients: coefficients } = decodeGenome(genome);
const rawBrainSignal = linearPolynomial(coefficients, sensors);
return brainToMuscleSignal(rawBrainSignal);
};
Постановка проблемы самопаркующегося автомобиля
Итак, мы свели высокоуровневую задачу самопаркующегося авто к простой задаче оптимизации, заключающейся в поиске оптимальной комбинации 180 единиц и нулей (поиске "достаточно хорошего" генома авто). Звучит просто, не так ли?
Наивный подход
Наивный подход поиска "достаточно хорошего" генома заключается в переборе всех комбинаций генов:
[0, ..., 0, 0]
[0, ..., 0, 1]
[0, ..., 1, 0]
[0, ..., 1, 1]
и т.д.
Но обратимся к математике. 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).
Задача нахождения "достаточно хорошей" комбинации генов для каждого авто выглядит как задача оптимизации, поэтому велика вероятность того, что ГА хорошо с ней справится.
Мы не будем рассматривать ГА во всех подробностях, но на высоком уровне нам необходимо выполнить следующие шаги:
СОЗДАНИЕ — самое первое поколение авто не может возникнуть из ниоткуда, поэтому мы сгенерируем набор произвольных геномов (набор бинарных массивов длиной 180). Например, мы можем создать ~1000 авто. Чем больше популяция, тем выше шансы быстро найти оптимальное решение (но тем медленнее будет выполняться программа).
ОТБОР — необходимо отобрать лучших (наиболее приспособленных — fittest) особей для дальнейшего скрещивания (см. следующий шаг). Приспособленность каждой особи будет определяться функцией приспособленности (fitness function), которая в нашем случае будет показывать, насколько близко авто подобралось к парковочному месту. Чем ближе, тем лучше.
СКРЕЩИВАНИЕ — простыми словами, мы позволяем " авто отцам" "скрещиваться" с " авто матерями" для смешения их геномов в пропорции ~50/50 и производства геномов " авто детей". Идея в том, что дети могут быть лучше (или хуже) в парковке, получая лучшие (или худшие) биты от родителей.
МУТАЦИЯ — в процессе скрещивания некоторые гены могут произвольно мутировать (1 и 0 в геноме потомка могут меняться местами). Это может привести к более широкому разнообразию геномов потомков и, как следствие, к более вариативному поведению авто. Представьте, что первый бит всех ~1000 авто был случайно установлен в 0. Единственный способ попробовать авто с первым битом, установленным в 1 — произвольные мутации. В тоже время частые мутации могут испортить хорошие геномы.
Возврат к шагу 2 до тех пор, пока количество поколений не достигнет лимита (например, 100), или пока лучшие особи не достигнут ожидаемого показателя приспособленности (например, лучшее авто приблизится к парковочному месту ближе чем на 1 метр).
Развитие мозга авто с помощью генетического алгоритма
Создадим функции для каждого шага генетического алгоритма.
Функции шага создания
Функция createGeneration будет создавать массив произвольных геномов (популяцию или поколение) и будет принимать 2 параметра:
generationSize — размер популяции. Он будет сохраняться между поколениями
genomeLength — длина генома каждой особи. В нашем случае длина генома будет составлять 180
Каждый ген может быть 1 или 0 с вероятностью 50/50.
Функция 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)functionmutate(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 (для простоты):
Для выбора лучших особей нам нужен способ определения приспособленности каждого генома. Для этого мы будем использовать так называемую функцию приспособленности (фитнес-функцию).
Фитнес-функция всегда связана с конкретной решаемой задачей, она не является универсальной. В нашем случае фитнес-функция будет измерять расстояние между авто и парковочным местом. Чем ближе авто к месту, тем лучше его приспособленность. Мы реализуем фитнес-функцию немного позже, сейчас же представим для нее интерфейс:
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]
constmaxCumulativeWeight = cumulativeWeights[cumulativeWeights.length-1];
constrandomNumber = maxCumulativeWeight * Math.random();
// Извлекаем произвольный элемент на основе его веса.
// Элементы с большим весом извлекаются чаще
for (leti = 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)functionselect(
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) {
return1;
}
if (fitnessA > fitnessB) {
return-1;
}
return0;
});
// Долгожители переходят в новое поколение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];
returnMath.sqrt((fromX - toX) ** 2 + (fromZ - toZ) ** 2);
};
Расстояние (loss) между автомобилем и парковочным местом будет рассчитываться так:
Поскольку fitness должна быть обратно пропорциональна loss, она рассчитывается следующим образом:
const carFitness = (params: GeometricParams): number => {
const loss = carLoss(params);
// Добавляем 1 во избежание деления на 0return1 / (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. Итак, даже несмотря на упомянутые выше проблемы, я надеюсь, что вы хорошо провели время, читая эту статью.