Genetic Algorithm Car Simulator

JavaScript-версию написал с нуля Рафаэль Мацунага. Кроме открытых исходников и одновременного заезда всех машин в его версии есть возможность отключить рендеринг — в этом случае просчитывается только физика, и эволюция идёт в несколько раз быстрее. В отличие от Box Car D2, поведение машинок не полностью детерминировано — одна и та же машинка на одной и той же трассе может показывать слегка разные результаты, поэтому иногда новое поколение показывает худший результат, чем предыдущее. Тем не менее, трасса, генерируемая псевдослучайно на основе строки, которую может задавать пользователь, всегда одна и та же для одной и той же строки, так что возможность соревноваться есть. В Genetic Cars также несколько меньше первоначальное генетическое разнообразие — у всех машин по два колеса. Всего геном автомобиля состоит из 14 генов — гораздо меньше, чем в Box Car 2D. 8 из них регулируют длину каждой вершины «тела», и по 3 на каждое колесо — расположение, размер и вес. Пока я писал эту статью, в фоновом окне Chromium на трассе, сгенерированной на основе строки «habrahabr.ru» успели посоревноваться уже три десятка поколений машинок. Рекордный результат — 178,87 метра.

250
187
125
62
0
 
 

 
 

Create new world with seed:
Mutation rate:
Mutation size:
Floor:
Gravity:
Elite clones:
 
 
 
 
 

Controls

Suprise: Toggles drawing, makes the simulation faster.
New Population: Keeps the generated track and restarts the whole car population.
Create new world with seed: The same seed always creates the same track, so you can agree on a seed with your friends and compete. :)
Mutation rate: The chance that each gene in each individual will mutate to a random value when a new generation is born.
Mutation size: The range each gene can mutate into. Lower numbers mean the gene will have values closer to the original.
Floor: If set to mutable, a new terrain will be generated each round.
Gravity: Enjoy the freedom of driving on the moon, you cheater!
Elite clones: The top n cars that will be copied over to the next generation.
View top replay: Pause the current simulation and show the top performing car. Click a second time to resume simulation.

Graph

Red: Top score in each generation.
Green: Average of the top 10 cars in each generation.
Blue: Average of the entire generation.

But what is it?

The program uses a simple genetic algorithm to evolve random two-wheeled shapes into cars over generations. Loosely based on BoxCar2D, but written from scratch, only using the same physics engine (box2d).
seedrandom.js written by David Bau. (thanks!)

Genome

The genome consists of:
- Shape: (8 genes, 1 per vertex)
- Wheel size: (2 genes, 1 per wheel)
- Wheel position: (2 genes, 1 per wheel)
- Wheel density: (2 genes, 1 per wheel) darker wheels mean denser wheels
- Chassis density: (1 gene) darker body means denser chassis

Blurb

This is not as deterministic as it should be, so your best car may not perform as well as it once did. The terrain gets more complex with distance.
 
 


Программа генерирует устройства с колес и кузовных деталей, цель которых - проехать как можно дольше. Специальный алгоритм оценивает прохождения трассы каждым автомобилем. Следующие машинки генерируются уже с учетом предыдущих удачных, жизнеспособных экземпляров. Они будто эволюционируют - если в первом поколении образцы без колес не могут проехать и метра, то в третьем поколении у них уже будут появляться колеса и совершенствоваться форма, а в десятом поколении образована машина будет способна преодолевать приличные расстояния.
Генетический алгоритм используется для создания автомобиля из библиотеки Box2D. Цвета показывают кроссинговер и мутация для каждой особи популяции. Можно выбирать коэффициент мутации. Часто генерируются жизнеспособные модели.
Эта программа использует генетический алгоритм для разработки двумерного автомобиля, который будет "оптимальным" для конкретной местности. Автомобиль имеет два колеса и две нагрузки. Исходные позиции и радиусы этих четырех объектов могут быть выбраны с помощью алгоритма. Объекты связаны пружинами, длина которых также избирается по алгоритму. Нагрузка никогда не должны касаться земли.
Оптимальность частичного решения (фитнес-функция пригодности) определяется тем, насколько долго оно существует, прежде чем:
Масса коснется земли. Закончится время. В начале, алгоритм даже не знает, что колеса касаются поверхности. Иногда можно увидеть, как появляются и исчезают различные виды - например, "уницикле", особенно на ранних стадиях прогресса алгоритма.
Генетические алгоритмы могут сходиться гораздо быстрее, при выборе фитнес-функции пригодности, численности популяции. Разработчик сделал моделирования более интересным относительно визуализации оптимизации, чем быстрым.


Поделиться статьей

0
631
0
Genetic Algorithm Car Simulator
Рейтинг 9 из 10. Голосов: 2
Ваша оценка:




Комментарии (0)


avatar

Чтобы оставить комментарий войдите или зарегистрируйтесь






Реализация генетических алгоритмов