Mengamati Proses Evolusi Mobil dengan Algoritma Genetika

• Ini adalah simulasi HTML5 di browser yang memperlihatkan bagaimana bentuk roda dua yang dibuat secara acak dipilih dan dimutasi dari generasi ke generasi menjadi mobil yang melaju lebih jauh
• Mengikuti ide BoxCar2D secara longgar, tetapi kodenya ditulis ulang dari awal dan menggunakan box2d untuk perhitungan fisika
• Kondisi evolusi dapat diubah dengan menyesuaikan tingkat mutasi, besar mutasi, kondisi lantai, gravitasi, dan jumlah elite clone
• Track yang sama dapat dibuat dengan seed yang sama sehingga mudah membandingkan hasil, tetapi simulasi itu sendiri tidak sepenuhnya deterministik
• Genom memuat bentuk, posisi, dan densitas bodi mobil serta roda, dan semakin jauh jarak tempuhnya, medannya makin kompleks sehingga sulit menjamin kestabilan hanya dari rekor tertinggi semata

---

Bagaimana mobil berevolusi

• Program ini adalah simulasi algoritma genetika sederhana yang mengembangkan bentuk roda dua acak dari generasi ke generasi untuk menghasilkan individu yang dapat melaju seperti mobil
• Idenya terinspirasi secara longgar dari BoxCar2D, tetapi kodenya ditulis dari nol
• Mesin fisika yang digunakan adalah box2d
• seedrandom.js dibuat oleh David Bau

Kontrol dan pengaturan evolusi

• Dengan fitur simpan dan pulihkan, status eksperimen bisa dilanjutkan
  • Save Population menyimpan populasi saat ini secara lokal
  • Restore Saved Population memulihkan populasi yang sebelumnya disimpan
• Cara simulasi berjalan juga bisa diubah langsung
  • Suprise mengaktifkan/nonaktifkan rendering agar simulasi berjalan lebih cepat
  • New Population memulai ulang seluruh populasi mobil sambil mempertahankan track yang sudah dibuat
  • View top replay menjeda simulasi saat ini dan menampilkan mobil dengan performa terbaik, lalu melanjutkan simulasi saat diklik lagi
• Create new world with seed memungkinkan track yang sama selalu dibuat dari seed yang sama, sehingga bisa bersaing dengan orang lain menggunakan seed yang sama
• Parameter evolusi menentukan seberapa besar perubahan pada generasi baru
  • Mutation rate adalah probabilitas setiap gen pada tiap individu berubah menjadi nilai acak saat generasi baru lahir
  • Mutation size adalah rentang perubahan setiap gen; semakin kecil nilainya, semakin dekat hasil mutasinya dengan nilai asli
  • Elite clones menentukan jumlah n mobil teratas yang akan disalin apa adanya ke generasi berikutnya

Perubahan performa yang terlihat di grafik

• Warna grafik menunjukkan performa tiap generasi berdasarkan kriteria yang berbeda
  • Merah menunjukkan skor tertinggi di setiap generasi
  • Hijau menunjukkan rata-rata 10 mobil terbaik di setiap generasi
  • Biru menunjukkan rata-rata seluruh generasi

Struktur mobil yang direpresentasikan oleh genom

• Genom mobil dibagi menjadi beberapa gen yang membentuk bodi dan roda
  • Shape: 1 gen per titik sudut, total 8 gen
  • Wheel size: 1 gen per roda, total 2 gen
  • Wheel position: 1 gen per roda, total 2 gen
  • Wheel density: 1 gen per roda, total 2 gen; roda yang lebih gelap berarti densitas lebih tinggi
  • Chassis density: 1 gen; bodi yang lebih gelap berarti densitas lebih tinggi

Keterbatasan dan kode yang dibuka

• Simulasi ini tidak sedeterministik yang diharapkan, sehingga mobil terbaik mungkin tidak menampilkan performa yang sama seperti sebelumnya
• Medan menjadi semakin kompleks seiring jarak yang ditempuh makin jauh
• Karena tidak ada penanganan terpisah untuk memastikan pemuatan skrip, jika perilakunya aneh maka halaman perlu dimuat ulang
• Kodenya dibuka di GitHub repository dan menerima kontribusi
• Awalnya dibuat di rednuht.org, lalu dilanjutkan oleh para kontributor di GitHub

[GN⁺]

Komentar Hacker News

• Saya pertama kali membuat ini hampir 20 tahun lalu, dan senang melihatnya masih sesekali muncul di sini
  Berkat Ruffle, ini masih berjalan di browser:
  https://peteshadbolt.co.uk/posts/ga/

  • Saat itu saya bekerja di tim Adobe Flash Player, dan saya ingat menggunakan film Flash ini sebagai test case :)
  • Ada contoh hasil setelah dijalankan selama beberapa hari? Atau bahkan selama 20 tahun? ;-)
  • Di Firefox, sepertinya crash saat menekan opsi "Save Local Population". Ada dugaan kenapa bisa begitu?
    Situsnya benar-benar keren. Setiap kali muncul, saya jadi terlalu lama terpaku padanya
  • Apa yang akan terjadi jika deteksi tabrakan ditambahkan juga ke struktur atau pegas, alih-alih hanya pada beban?
  • Di antara hal-hal di internet yang menyita waktu, versi aslinya termasuk yang paling saya ingat
    Saya dan teman biasa membiarkannya berjalan selama jam makan siang lalu kembali untuk melihat siapa yang menang

• Sepertinya selalu ada satu desain yang berhasil karena beruntung lalu mendominasi tiap generasi, dan mutasi setelahnya terjebak di jalan buntu yang bahkan tidak mendekati tingkat berfungsi dengan baik
  Misalnya 10 teratas tidak berubah bahkan setelah ratusan generasi. Mungkin memang karakteristik algoritma genetika. Bisa jadi caranya adalah cepat menemukan solusi yang cukup baik lalu terjebak di maksimum lokal, atau mungkin perlu lebih banyak mengutak-atik pengaturan probabilitas mutasi dan ukuran mutasi

  • Secara umum, lebih baik menjaga probabilitas mutasi sangat rendah agar populasi berubah perlahan seiring waktu
    Probabilitas mutasi yang tinggi cepat mencapai optimum lokal tetapi sulit keluar darinya, sementara probabilitas mutasi rendah membutuhkan jauh lebih banyak generasi tetapi biasanya menghasilkan adaptasi yang lebih baik
  • Kedengarannya seperti menjalankannya hanya dengan satu individu kloning elite
    Dalam heuristik genetika, itu cara yang sangat buruk justru karena fenomena seperti itu
  • Sepertinya lebih banyak faktor selain bentuk juga perlu berubah. Mobil lambat dengan tenaga lebih kuat mungkin tidak terlalu mudah terjebak di lekukan
    Namun saat ini tenaga dan kecepatan tidak berubah, dan setelah beberapa generasi sepertinya hanya bentuknya yang berubah sangat sedikit. Saya gulir ke bawah dan ada penjelasan genomnya: 8 gen bentuk, 2 ukuran roda, 2 posisi roda, 2 kepadatan roda, dan 1 kepadatan bodi. Pada akhirnya tampaknya konvergen ke dua roda dan bentuk bodi sedang, lalu setelah itu tidak banyak kemajuan besar. Akan menarik jika tenaga dan kecepatan juga dimasukkan sebagai elemen yang bermutasi

• Menarik. Namun pengaturan kecepatan tidak terlalu intuitif. Jika menekan "Surprise", kecepatannya meningkat sehingga bisa melewati banyak iterasi dengan cepat
  Probabilitas mutasi, yaitu kemungkinan g berubah, dan ukuran mutasi Δg adalah hiperparameter yang bagus untuk diutak-atik sambil melihat populasi berevolusi seiring waktu. Akan menarik jika ada gen "compliance" agar mobil memiliki semacam suspensi. Dalam sebagian besar run yang saya coba, hampir semuanya berevolusi menjadi bentuk seperti sepeda Tron

  • Saya menjalankannya lama di background dengan probabilitas mutasi sangat tinggi, dan muncul beberapa bentuk yang cukup berbeda
    Bentuknya roda besar dengan roda kecil menempel, dan ia memantul-mantul melewati semua rintangan

• Ini diskusi lama:
  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)

• Ini boxcar2d tanpa Flash
  https://news.ycombinator.com/item?id=2196747

  • Selain itu, anehnya semua parameter suspensi tampaknya hilang
    Simulasi fisikanya tampaknya jelas memakai tumbukan tidak elastis, yang cukup tidak realistis, sehingga banyak mobil yang di permukaan tampak cukup bagus tidak mampu melewati lintasan. Koefisien geseknya juga terlihat sangat rendah. Sebagian besar mobil yang saya buat bahkan tidak bisa mendaki tanjakan dua segmen
  • Ternyata boxcar2d bekerja sempurna di Ruffle, dan Internet Archive otomatis memuat Ruffle :)
    https://web.archive.org/web/20240428203838/http://boxcar2d.c...
  • Saya merasa pernah melihat hal seperti ini lebih dari 10 tahun lalu, dan ternyata benar

• Ada bug kecil. Setelah sekitar 280m, tidak ada jalan, jadi semua mobil jatuh ke lubang tanpa akhir

• Tertulis “mengembangkan bentuk dua roda acak menjadi mobil selama beberapa generasi”, tetapi di tempat saya tinggal, mobil dua roda disebut sepeda motor
  Meski begitu, simulasinya sangat keren!

  • Dalam simulasi tempat mobil-mobil ini berjalan, tidak ada dimensi ketiga yang memungkinkan kendaraan terguling, dan tidak ada ruang untuk menaruh sepasang roda lagi
    Jadi seperti mobil roda empat tradisional, kendaraan ini tidak jatuh meski kecepatannya 0. Menurut saya sifat itu saja sudah membuat perilakunya lebih mirip mobil roda empat daripada sepeda motor

• Saya menyukainya karena ini visualisasi yang sangat visual dan menyenangkan
  Setelah melihat ini, saya jadi bereksperimen dengan algoritma genetika di "Self-parking car evolution":
  https://trekhleb.dev/self-parking-car-evolution/

• Ini mengingatkan saya pada aplikasi Android hebat bernama Cell Lab. Di sana kita bisa membuat organisme multisel atau unisel untuk hidup di cawan petri
  Jika mau, kita juga bisa menaikkan tingkat radiasi agar terjadi mutasi dan evolusi

• Jika Anda menyukai hal seperti ini, silakan mampir ke https://old.reddit.com/r/WatchMachinesLearn/

  • Topiknya keren, tetapi tampaknya bukan subreddit yang terlalu aktif. Postingan terbarunya 3 tahun lalu :-/