Genetik algoritma kullanarak arabaların evrim sürecini izleme

• Tarayıcıda, rastgele oluşturulmuş iki tekerlekli şekillerin nesiller boyunca daha uzağa giden arabalar olarak seçilip mutasyona uğrama sürecini izleyebileceğiniz bir HTML5 simülasyonu
• BoxCar2D fikrini gevşek biçimde takip ediyor, ancak kod baştan yazılmış ve fizik hesaplamalarında box2d kullanılıyor
• Mutasyon oranı, mutasyon büyüklüğü, zemin koşulları, yerçekimi ve elit klon sayısını ayarlayarak evrim koşullarını değiştirebilirsiniz
• Aynı seed ile aynı pist oluşturulabildiği için sonuçları karşılaştırmak kolay, ancak simülasyonun kendisi tamamen deterministik değil
• Genom, gövde ve tekerleklerin şekil, konum ve yoğunluk bilgilerini içeriyor; daha uzağa gidildikçe arazi daha karmaşık hale geldiğinden yalnızca en yüksek skor kararlılığı garanti etmiyor

---

Arabaların nasıl evrimleştiği

• Program, rastgele iki tekerlekli şekilleri nesilden nesile evrimleştirerek araba gibi ilerleyen bireyler üreten basit bir genetik algoritma simülasyonudur
• Fikri gevşek biçimde BoxCar2D'den almıştır, ancak kod sıfırdan yazılmıştır
• Fizik motoru olarak box2d kullanılır
• seedrandom.js, David Bau tarafından yazılmıştır

Kontroller ve evrim ayarları

• Kaydetme ve geri yükleme özellikleriyle deney durumunu sürdürebilirsiniz
  • Save Population, mevcut popülasyonu yerel olarak kaydeder
  • Restore Saved Population, daha önce kaydedilmiş popülasyonu geri yükler
• Simülasyonun çalışma biçimini de doğrudan değiştirebilirsiniz
  • Suprise, çizimi açıp kapatarak simülasyonu daha hızlı hale getirir
  • New Population, oluşturulmuş pisti korurken tüm araba popülasyonunu yeniden başlatır
  • View top replay, mevcut simülasyonu duraklatır ve en yüksek performanslı arabayı gösterir; tekrar tıklanınca simülasyon devam eder
• Create new world with seed, aynı seed her zaman aynı pisti oluşturduğu için başkalarıyla aynı seed üzerinden yarışmanıza olanak tanır
• Evrim parametreleri, yeni neslin ne kadar büyük değişiklikler geçireceğini belirler
  • Mutation rate, yeni nesil doğarken her bireyin her geninin rastgele bir değere mutasyona uğrama olasılığıdır
  • Mutation size, her genin mutasyona uğrayabileceği aralıktır; değer ne kadar düşükse, ortaya çıkan değer orijinaline o kadar yakın olur
  • Elite clones, doğrudan bir sonraki nesle kopyalanacak en iyi n arabanın sayısını belirler

Grafikte performans değişimi

• Grafik renkleri, nesiller arası performansı farklı ölçütlerle gösterir
  • Kırmızı, her neslin en yüksek skorunu gösterir
  • Yeşil, her nesildeki en iyi 10 arabanın ortalamasını gösterir
  • Mavi, tüm neslin ortalamasını gösterir

Genomun ifade ettiği araba yapısı

• Arabanın genomu, gövdeyi ve tekerlekleri oluşturan çeşitli genlere ayrılır
  • Shape: köşe başına 1 adet, toplam 8 gen
  • Wheel size: tekerlek başına 1 adet, toplam 2 gen
  • Wheel position: tekerlek başına 1 adet, toplam 2 gen
  • Wheel density: tekerlek başına 1 adet, toplam 2 gen; daha koyu tekerlek daha yüksek yoğunluk anlamına gelir
  • Chassis density: 1 gen; daha koyu gövde daha yüksek yoğunluk anlamına gelir

Sınırlar ve kodun paylaşımı

• Simülasyon beklenildiği kadar deterministik değildir; bu yüzden en iyi araba öncekiyle aynı performansı göstermeyebilir
• Arazi, mesafe arttıkça daha karmaşık hale gelir
• Betik yüklenmesini ayrıca denetlemediği için, çalışmada tuhaflık olursa sayfayı yenilemeniz gerekir
• Kod, GitHub repository üzerinde yayımlanmıştır ve katkılara açıktır
• Başlangıçta rednuht.org üzerinde yazılmış, daha sonra GitHub katkıcıları da sürece katılmıştır

[GN⁺]

Hacker News yorumları

• Bunu ilk kez neredeyse 20 yıl önce yapmıştım; hâlâ ara sıra burada karşıma çıkması sevindirici
  Ruffle sayesinde hâlâ tarayıcıda çalışıyor:
  https://peteshadbolt.co.uk/posts/ga/

  • O zamanlar Adobe Flash Player ekibinde çalışıyordum; bu Flash filmini bir test vakası olarak kullandığımızı hatırlıyorum :)
  • Birkaç gün çalıştırıldığında ortaya çıkan örnek sonuçlar var mı? Ya da 20 yılın sonunda bile? ;-)
  • Firefox'ta "Save Local Population" seçeneğine basınca çöküyor gibi görünüyor. Bunun neden olduğuna dair bir tahmininiz var mı?
    Site gerçekten harika. Her paylaşıldığında başından ayrılamıyorum
  • Çarpışma tespitini sadece yüke koymak yerine yapıya ya da yaylara da eklerseniz nasıl sonuçlar çıkar?
  • İnternette zamanı çalan şeyler arasında, orijinali en akılda kalanlardan biri
    Bir arkadaşımla öğle arasında çalıştırıp bırakır, döndüğümüzde kimin kazandığına bakardık

• Görünüşe göre bir tasarım şans eseri başarılı olduktan sonra her nesle hakim oluyor ve sonrasındaki mutasyonlar düzgün çalışan seviyeye bile yaklaşamayan çıkmazlara saplanıyor
  Yüzlerce nesil geçse de ilk 10'un değişmediği oluyor. Bu genetik algoritmaların bir özelliği olabilir. Oldukça iyi bir çözümü hızlıca bulup sonra bir yerel maksimumda takılı kalıyor da olabilir; ya da mutasyon olasılığı ve mutasyon büyüklüğü ayarlarıyla daha fazla oynamak gerekiyordur

  • Genel olarak mutasyon olasılığını çok düşük tutmak daha iyidir; böylece popülasyon zaman içinde yavaş yavaş değişir
    Yüksek mutasyon olasılığı yerel optimuma hızla ulaşır ama oradan çıkmayı zorlaştırır; düşük mutasyon olasılığı çok daha fazla nesil ister ama genelde daha iyi uyuma götürür
  • Sanki yalnızca tek bir elit kopya bireyle çalıştırıyorsunuz
    Genetik sezgisel yöntemlerde tam da bu yüzden çok kötü bir yaklaşımdır
  • Sadece şeklin değil, daha fazla unsurun da değişmesi gerekiyor gibi. Daha güçlü motora sahip yavaş bir araba tümseklere daha az takılabilir
    Ama şu anda güç ve hız değişmiyor; birkaç nesilden sonra yalnızca şekil çok az değişiyor gibi. Aşağı kaydırınca genom açıklaması var: 8 şekil geni, 2 tekerlek boyutu, 2 tekerlek konumu, 2 tekerlek yoğunluğu, 1 gövde yoğunluğu. Sonunda iki tekerlek ve orta düzey bir gövde şekline yakınsıyor, sonrasında da büyük bir ilerleme görünmüyor. Güç ve hızın da mutasyon unsurları arasına eklenmesi ilginç olabilir

• Eğlenceli. Yalnız hız ayarı pek sezgisel değil. "Surprise"a basınca hızlanıyor ve birçok yinelemeyi hızlıca geçebiliyorsunuz
  Mutasyon olasılığı, yani g'nin değişme ihtimali ile mutasyon büyüklüğü Δg, popülasyonun zaman içinde nasıl evrildiğini izlerken kurcalaması keyifli hiperparametreler. Arabaya bir tür süspansiyon kazandıracak bir "compliance" geni olsaydı ilginç olurdu. Benim denemelerimin çoğunda neredeyse hepsi Tron motosikleti benzeri biçimlere evrildi

  • Çok yüksek mutasyon olasılığıyla uzun süre arka planda çalıştırınca epey farklı biçimler de çıktı
    Büyük bir tekerleğe bağlı küçük bir tekerlek gibi bir şekil; zıplaya zıplaya gidip tüm engelleri aşıyor

• Önceki tartışmalar:
  https://news.ycombinator.com/item?id=5942757 (664 puan | Haz 2013 | 169 yorum)
  https://news.ycombinator.com/item?id=10600486 (162 puan | Kas 2015 | 57 yorum)

• Flash'sız boxcar2d
  https://news.ycombinator.com/item?id=2196747

  • Üstelik garip şekilde tüm süspansiyon parametreleri de eksik gibi görünüyor
    Fizik simülasyonu açıkça esnek olmayan çarpışmalar kullanıyor gibi; bu oldukça gerçek dışı ve bu yüzden görünüşte yeterince iyi olan pek çok araba parkuru geçemiyor. Sürtünme katsayısı da çok düşük görünüyor. Yaptığım arabaların çoğu iki bölümlü bir eğimi bile tırmanamadı
  • Meğer boxcar2d, Ruffle içinde kusursuz çalışıyormuş ve Internet Archive Ruffle'ı otomatik olarak yüklüyor :)
    https://web.archive.org/web/20240428203838/http://boxcar2d.c...
  • Demek ki bunu 10 yıldan da uzun süre önce gördüğümü düşünmekte haklıymışım

• Küçük bir hata var. Yaklaşık 280m sonrasında yol kalmıyor ve tüm arabalar sonsuz bir çukura düşüyor

• "Rastgele iki tekerlekli şekilleri, birkaç nesil boyunca arabalara evrimleştirir" deniyor ama benim yaşadığım yerde iki tekerlekli arabalara motosiklet denir
  Yine de simülasyon çok güzel!

  • Bu arabaların gittiği simülasyonda, aracın devrilebileceği bir üçüncü boyut yok ve bir çift tekerlek daha koyacak alan da yok
    Bu yüzden geleneksel dört tekerlekli bir araba gibi, hızı 0 olsa bile devrilmiyor. Sırf bu özelliğiyle bile motosikletten çok dört tekerlekli arabalara daha yakın davrandığını söyleyebiliriz bence

• Çok görsel ve eğlenceli bir görselleştirme, bu yüzden hoşuma gidiyor
  Bunu görünce "Self-parking car evolution" içinde genetik algoritmaları denemeye başlamıştım:
  https://trekhleb.dev/self-parking-car-evolution/

• Cell Lab adlı harika bir Android uygulamasını hatırlattı. Petri kabında yaşayacak çok hücreli ya da tek hücreli organizmalar oluşturabiliyordunuz
  İsterseniz radyasyon seviyesini artırıp mutasyon ve evrimin gerçekleşmesini de sağlayabiliyordunuz

• Böyle şeyleri seviyorsanız https://old.reddit.com/r/WatchMachinesLearn/ adresine uğrayın

  • Konu harika ama çok da aktif bir subreddit gibi görünmüyor. En son gönderi 3 yıl önceymiş :-/