- Es una simulación en HTML5 que permite ver en el navegador cómo formas aleatorias de dos ruedas son seleccionadas y mutadas a lo largo de generaciones para convertirse en autos que llegan cada vez más lejos
- Sigue de forma flexible la idea de BoxCar2D, pero el código fue reescrito desde cero y usa box2d para los cálculos físicos
- Se pueden ajustar la tasa de mutación, el tamaño de mutación, las condiciones del suelo, la gravedad y la cantidad de clones élite para cambiar las condiciones de la evolución
- Se puede generar la misma pista con la misma seed, lo que facilita comparar resultados, pero la simulación en sí no es completamente determinista
- El genoma contiene la forma, posición y densidad del chasis y las ruedas, y como el terreno se vuelve más complejo mientras más lejos se avanza, solo el récord máximo no garantiza estabilidad
Cómo evolucionan los autos
- El programa es una simulación simple de algoritmo genético que hace evolucionar por generaciones formas aleatorias de dos ruedas para producir individuos que se desplazan como autos
- Toma la idea de forma flexible de BoxCar2D, pero el código fue escrito desde cero
- Usa box2d como motor de física
- seedrandom.js fue escrito por David Bau
Controles y configuración de la evolución
- Con las funciones de guardado y restauración se puede continuar el estado del experimento
- Save Population guarda localmente la población actual
- Restore Saved Population restaura una población guardada anteriormente
- También se puede cambiar directamente la forma en que avanza la simulación
- Suprise alterna el dibujo para hacer la simulación más rápida
- New Population reinicia toda la población de autos manteniendo la pista generada
- View top replay pausa la simulación actual y muestra el auto con mejor rendimiento; al hacer clic otra vez, la simulación se reanuda
- Create new world with seed permite competir con otras personas usando la misma seed, ya que la misma seed siempre genera la misma pista
- Los parámetros evolutivos determinan qué tanto cambia cada nueva generación
- Mutation rate es la probabilidad de que cada gen de cada individuo mute a un valor aleatorio cuando nace una nueva generación
- Mutation size es el rango dentro del cual puede mutar cada gen; cuanto más bajo es el valor, más cerca queda del valor original
- Elite clones define cuántos de los mejores autos se copiarán tal cual a la siguiente generación
Cambios de rendimiento vistos en la gráfica
- Los colores de la gráfica muestran el rendimiento de cada generación con distintos criterios
- Rojo representa la puntuación más alta de cada generación
- Verde representa el promedio de los 10 mejores autos de cada generación
- Azul representa el promedio de toda la generación
Estructura del auto representada por el genoma
- El genoma del auto se divide en varios genes que componen el chasis y las ruedas
- Shape: 1 por vértice, 8 genes en total
- Wheel size: 1 por rueda, 2 genes en total
- Wheel position: 1 por rueda, 2 genes en total
- Wheel density: 1 por rueda, 2 genes en total; las ruedas más oscuras significan mayor densidad
- Chassis density: 1 gen; un chasis más oscuro significa mayor densidad
Limitaciones y publicación del código
- La simulación no es tan determinista como se esperaría, por lo que el mejor auto puede no rendir igual que antes
- El terreno se vuelve más complejo mientras más distancia se recorre
- Como no se maneja por separado la verificación de carga de scripts, si algo funciona raro hay que recargar la página
- El código está publicado en el GitHub repository y acepta contribuciones
- Originalmente fue creado en rednuht.org y después participaron colaboradores de GitHub
1 comentarios
Opiniones en Hacker News
Hice esto por primera vez hace casi 20 años, y me alegra ver que todavía aparece por aquí de vez en cuando.
Gracias a Ruffle, aún se ejecuta en el navegador:
https://peteshadbolt.co.uk/posts/ga/
El sitio está buenísimo. Cada vez que aparece, termino quedándome demasiado tiempo
Lo dejábamos corriendo con un amigo durante la hora del almuerzo y al volver veíamos quién había ganado
Siempre parece que un diseño tiene éxito de pura suerte y luego domina en cada generación, mientras que las mutaciones posteriores caen en un callejón sin salida donde ni siquiera se acercan a funcionar bien.
Incluso después de cientos de generaciones, el top 10 no cambia. Tal vez sea una característica de los algoritmos genéticos: encontrar rápido una solución bastante buena y luego quedarse atrapado en un máximo local. O quizá haga falta ajustar más la probabilidad y el tamaño de las mutaciones
Una probabilidad de mutación alta llega rápido a un óptimo local, pero cuesta salir de ahí; una probabilidad baja requiere muchísimas más generaciones, pero normalmente lleva a una mejor adaptación
En heurísticas genéticas, eso es una muy mala práctica precisamente por ese fenómeno
Pero ahora la potencia y la velocidad no cambian, y después de algunas generaciones parece que solo cambia muy poco la forma. Bajando más, veo la descripción del genoma: 8 genes para la forma, 2 para el tamaño de las ruedas, 2 para la posición de las ruedas, 2 para la densidad de las ruedas y 1 para la densidad de la carrocería. Al final converge en dos ruedas y una carrocería mediana, y después no parece haber grandes avances. Sería interesante incluir también potencia y velocidad como factores de variación
Es divertido. Aunque el control de velocidad no es muy intuitivo. Si presionas "Surprise", se acelera y puedes pasar rápidamente por varias iteraciones.
La probabilidad de mutación, es decir, la posibilidad de que cambie g, y el tamaño de la mutación Δg son hiperparámetros buenos para ajustar mientras ves cómo evoluciona la población con el tiempo. Sería interesante que hubiera un gen de "compliance" para que al auto le aparezca algún tipo de suspensión. En la mayoría de las corridas que probé, casi todos evolucionaron hacia algo parecido a una moto de Tron
Una tenía una rueda grande con una rueda pequeña pegada, y va rebotando mientras supera todos los obstáculos
Discusiones anteriores:
https://news.ycombinator.com/item?id=5942757 (664 points | Jun 2013 | 169 comments)
https://news.ycombinator.com/item?id=10600486 (162 points | Nov 2015 | 57 comments)
Es boxcar2d sin Flash.
https://news.ycombinator.com/item?id=2196747
La simulación física claramente parece usar colisiones inelásticas, lo cual es bastante poco realista, y por eso muchos autos que visualmente se ven suficientemente bien no logran completar el recorrido. El coeficiente de fricción también parece muy bajo. La mayoría de los autos que hice ni siquiera pudieron subir una pendiente de dos tramos
https://web.archive.org/web/20240428203838/http://boxcar2d.c...
Hay un pequeño bug. Después de unos 280 m ya no hay camino, así que todos los autos caen en un pozo infinito
Dice “evolucionar formas aleatorias de dos ruedas hasta convertirlas en autos a lo largo de varias generaciones”, pero donde vivo a un auto de dos ruedas le decimos motocicleta.
¡Aun así, la simulación está muy buena!
Por eso, aunque su velocidad sea 0, no se caen, como un auto tradicional de cuatro ruedas. Creo que solo por esa propiedad su comportamiento se parece más al de un auto de cuatro ruedas que al de una motocicleta
Me gusta porque es una visualización muy visual y entretenida.
Esto me llevó a experimentar con algoritmos genéticos en "Self-parking car evolution":
https://trekhleb.dev/self-parking-car-evolution/
Me recuerda a una excelente app de Android llamada Cell Lab. Podías crear organismos multicelulares o unicelulares para que vivieran en una placa de Petri.
Si querías, también podías subir el nivel de radiación para provocar mutaciones y evolución
Si te gustan estas cosas, pásate por https://old.reddit.com/r/WatchMachinesLearn/