В этой статье мы научим авто самостоятельно парковаться с помощью генетического алгоритма.
Мы создадим первое поколение авто с произвольными геномами, которое будет вести себя примерно так:
Примерно на сороковом поколении авто начнут понимать, что такое авто-парковка, и начнут приближаться к парковочному месту:
Другой пример с более сложной отправной точкой:
Да-да, авто врезаются в другие авто и паркуются не идеально, но это лишь 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]
. Входные данные могут выглядеть так:
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 целых числа:
engineSignal
.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 этапа:
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 => {
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
единиц и нулей (поиске "достаточно хорошего" генома авто). Звучит просто, не так ли?
Наивный подход поиска "достаточно хорошего" генома заключается в переборе всех комбинаций генов:
[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
авто. Чем больше популяция, тем выше шансы быстро найти оптимальное решение (но тем медленнее будет выполняться программа).~50/50
и производства геномов "♂♀ авто детей". Идея в том, что дети могут быть лучше (или хуже) в парковке, получая лучшие (или худшие) биты от родителей.1
и 0
в геноме потомка могут меняться местами). Это может привести к более широкому разнообразию геномов потомков и, как следствие, к более вариативному поведению авто. Представьте, что первый бит всех ~1000
авто был случайно установлен в 0
. Единственный способ попробовать авто с первым битом, установленным в 1
— произвольные мутации. В тоже время частые мутации могут испортить хорошие геномы.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
единиц и нулей (поиск оптимального генома автомобиля).
Затем мы применили генетический алгоритм для нахождения оптимального генома авто. Это позволило нам получить довольно хорошие результаты за несколько часов моделирования (вместо многих лет в случае использования наивного подхода).
Вы можете запустить симулятор, чтобы увидеть процесс эволюции прямо в браузере. Он предоставляет следующие возможности:
Полный исходный код, показанный в этой статье, можно найти в этом репозитории.
Проблемы и нерешенные задачи:
Однако цель этой статьи заключалась в том, чтобы немного развлечься, изучая, как работает генетический алгоритм, а не в том, чтобы создать готовую к производству беспилотную Tesla. Итак, даже несмотря на упомянутые выше проблемы, я надеюсь, что вы хорошо провели время, читая эту статью.
Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩