สังเกตกระบวนการวิวัฒนาการของรถยนต์ด้วยอัลกอริทึมพันธุกรรม

• เป็นซิมูเลชัน HTML5 ที่ให้ดูในเบราว์เซอร์ได้ว่า รูปทรงสองล้อที่สร้างแบบสุ่ม ถูกคัดเลือกและกลายพันธุ์ข้ามรุ่นจนเป็นรถที่วิ่งได้ไกลขึ้นอย่างไร
• อิงไอเดียของ BoxCar2D แบบหลวม ๆ แต่เขียนโค้ดใหม่ และใช้ box2d สำหรับการคำนวณฟิสิกส์
• ปรับเงื่อนไขการวิวัฒนาการได้ด้วยการตั้งค่าอัตราการกลายพันธุ์ ขนาดการกลายพันธุ์ สภาพพื้น แรงโน้มถ่วง และจำนวน โคลนชั้นยอด
• สามารถสร้างแทร็กเดียวกันด้วย seed เดียวกัน จึงเปรียบเทียบผลลัพธ์ได้ง่าย แต่ตัวซิมูเลชันเองไม่ได้เป็นแบบ กำหนดแน่นอน อย่างสมบูรณ์
• จีโนมเก็บรูปทรง ตำแหน่ง และความหนาแน่นของตัวถังกับล้อ และยิ่งวิ่งไปไกล ภูมิประเทศก็ยิ่งซับซ้อน ทำให้ยากที่จะรับประกันความเสถียรจากสถิติสูงสุดเพียงอย่างเดียว

---

รถยนต์วิวัฒนาการอย่างไร

• โปรแกรมนี้เป็นซิมูเลชันอัลกอริทึมพันธุกรรมแบบง่าย ที่วิวัฒนาการ รูปทรงสองล้อแบบสุ่ม ไปทีละรุ่น เพื่อสร้างสิ่งมีลักษณะเหมือนรถยนต์ที่วิ่งได้
• ได้แรงบันดาลใจแบบหลวม ๆ จาก BoxCar2D แต่โค้ดเขียนขึ้นตั้งแต่ต้น
• ใช้ box2d เป็นเอนจินฟิสิกส์
• seedrandom.js เขียนโดย David Bau

การควบคุมและการตั้งค่าวิวัฒนาการ

• ฟีเจอร์บันทึกและกู้คืนช่วยให้ทำการทดลองต่อจากสถานะเดิมได้
  • Save Population บันทึกประชากรปัจจุบันไว้ในเครื่อง
  • Restore Saved Population กู้คืนประชากรที่เคยบันทึกไว้ก่อนหน้า
• สามารถเปลี่ยนวิธีดำเนินซิมูเลชันได้เองด้วย
  • Suprise สลับการวาดภาพเพื่อทำให้ซิมูเลชันเร็วขึ้น
  • New Population เริ่มประชากรรถยนต์ทั้งหมดใหม่ โดยคงแทร็กที่สร้างไว้เดิม
  • View top replay หยุดซิมูเลชันปัจจุบันชั่วคราวและแสดงรถที่ทำผลงานดีที่สุด เมื่อคลิกอีกครั้งจะกลับมาดำเนินซิมูเลชันต่อ
• Create new world with seed ทำให้ seed เดียวกันสร้างแทร็กเดียวกันเสมอ จึงสามารถแข่งขันกับคนอื่นด้วย seed เดียวกันได้
• พารามิเตอร์วิวัฒนาการกำหนดว่ารุ่นใหม่จะเปลี่ยนแปลงมากเพียงใด
  • Mutation rate คือความน่าจะเป็นที่ยีนแต่ละตัวของแต่ละสิ่งมีชีวิตจะกลายพันธุ์เป็นค่าสุ่มเมื่อรุ่นใหม่เกิดขึ้น
  • Mutation size คือช่วงที่ยีนแต่ละตัวสามารถกลายพันธุ์ได้ โดยค่าต่ำกว่าจะได้ค่าที่ใกล้กับค่าเดิมมากกว่า
  • Elite clones กำหนดจำนวนรถอันดับบนสุด n คันที่จะถูกคัดลอกไปยังรุ่นถัดไปโดยตรง

การเปลี่ยนแปลงประสิทธิภาพที่เห็นจากกราฟ

• สีของกราฟแสดงประสิทธิภาพในแต่ละรุ่นตามเกณฑ์ที่ต่างกัน
  • สีแดง แสดงคะแนนสูงสุดของแต่ละรุ่น
  • สีเขียว แสดงค่าเฉลี่ยของรถ 10 อันดับแรกในแต่ละรุ่น
  • สีน้ำเงิน แสดงค่าเฉลี่ยของทั้งรุ่น

โครงสร้างรถยนต์ที่จีโนมแทนค่า

• จีโนม ของรถยนต์แบ่งเป็นยีนหลายตัวที่ประกอบเป็นตัวถังและล้อ
  • Shape: ยีน 1 ตัวต่อจุดยอด รวม 8 ยีน
  • Wheel size: ยีน 1 ตัวต่อล้อ รวม 2 ยีน
  • Wheel position: ยีน 1 ตัวต่อล้อ รวม 2 ยีน
  • Wheel density: ยีน 1 ตัวต่อล้อ รวม 2 ยีน โดยล้อที่สีเข้มกว่าหมายถึงความหนาแน่นสูงกว่า
  • Chassis density: ยีน 1 ตัว โดยตัวถังที่สีเข้มกว่าหมายถึงความหนาแน่นสูงกว่า

ข้อจำกัดและการเปิดเผยโค้ด

• ซิมูเลชันไม่ได้เป็นแบบ กำหนดแน่นอน เท่าที่คาดไว้ ทำให้รถที่ดีที่สุดอาจทำผลงานได้ไม่เท่าเดิม
• ภูมิประเทศ จะซับซ้อนขึ้นเมื่อระยะทางไกลขึ้น
• ไม่มีการจัดการตรวจสอบการโหลดสคริปต์แยกต่างหาก ดังนั้นหากการทำงานผิดปกติควรรีเฟรชหน้า
• โค้ดเผยแพร่ไว้ที่ GitHub repository และยินดีรับการมีส่วนร่วม
• เดิมเขียนขึ้นที่ rednuht.org และภายหลังมีผู้ร่วมพัฒนาจาก GitHub เข้ามามีส่วนร่วม

[GN⁺]

ความคิดเห็นจาก Hacker News

• ผมสร้างสิ่งนี้ครั้งแรกเมื่อเกือบ 20 ปีก่อน ดีใจที่เห็นว่ามันยังถูกเอามาโพสต์ที่นี่เป็นครั้งคราว
  ต้องขอบคุณ Ruffle ที่ทำให้ยังรันในเบราว์เซอร์ได้:
  https://peteshadbolt.co.uk/posts/ga/

  • ตอนนั้นผมทำงานอยู่ในทีม Adobe Flash Player และจำได้ว่าเคยใช้ Flash movie นี้เป็น test case :)
  • มีตัวอย่างผลลัพธ์หลังปล่อยให้รันหลายวันไหมครับ? หรือแม้แต่ 20 ปีก็ได้? ;-)
  • ใน Firefox ดูเหมือนว่าพอกดตัวเลือก "Save Local Population" แล้วจะ crash พอจะเดาได้ไหมว่าเพราะอะไร?
    เว็บเจ๋งมากครับ ทุกครั้งที่มันถูกโพสต์ ผมก็เผลอใช้เวลากับมันนานเกินไป
  • ถ้าเพิ่มการตรวจจับการชนให้กับ โครงสร้างหรือสปริง ด้วย แทนที่จะดูเฉพาะที่น้ำหนัก จะได้ผลลัพธ์แบบไหนนะ?
  • ในบรรดาสิ่งที่ดูดเวลาบนอินเทอร์เน็ต ตัวต้นฉบับถือว่าเป็นหนึ่งในสิ่งที่ผมจำได้มากที่สุด
    ผมกับเพื่อนเคยเปิดทิ้งไว้ตอนพักกลางวัน แล้วกลับมาดูว่าใครชนะ

• ดูเหมือนว่ามักจะมีดีไซน์หนึ่งที่โชคดีประสบความสำเร็จ แล้ว ครอบงำในแต่ละรุ่น จากนั้น mutation รุ่นถัด ๆ ไปก็ไปติดทางตันที่แทบไม่ได้ใกล้เคียงกับระดับที่ใช้งานได้เลย
  แบบว่าผ่านไปหลายร้อยรุ่นแล้ว 10 อันดับแรกก็ยังไม่เปลี่ยน นี่อาจเป็นลักษณะของ genetic algorithm ก็ได้ อาจเป็นรูปแบบที่หา solution ที่ค่อนข้างดีได้เร็ว แล้วไปติดอยู่ที่ local maximum หรือไม่ก็อาจต้องปรับค่าความน่าจะเป็นของ mutation และขนาดของ mutation เพิ่มเติม

  • โดยทั่วไปแล้ว ควรรักษา ความน่าจะเป็นของ mutation ให้ต่ำมาก เพื่อให้ประชากรค่อย ๆ เปลี่ยนไปตามเวลา
    ความน่าจะเป็นของ mutation ที่สูงจะไปถึง local optimum ได้เร็ว แต่หลุดออกมายาก ส่วนความน่าจะเป็นของ mutation ที่ต่ำต้องใช้รุ่นมากกว่ามาก แต่โดยปกติจะนำไปสู่การปรับตัวที่ดีกว่า
  • ฟังดูเหมือนรันโดยมีแค่ สำเนา elite ตัวเดียว
    ใน genetic heuristics นั่นเป็นวิธีที่แย่มากเพราะปรากฏการณ์แบบนี้พอดี
  • นอกจากรูปร่างแล้ว น่าจะต้องมีองค์ประกอบอื่น ๆ ที่เปลี่ยนได้มากกว่านี้ รถที่ช้ากว่าแต่มีแรงขับมากกว่าอาจจะไม่ตกหลุมง่ายนัก
    แต่ตอนนี้แรงขับและความเร็วไม่เปลี่ยน และหลังผ่านไปไม่กี่รุ่นดูเหมือนจะมีแค่รูปร่างที่เปลี่ยนเล็กน้อยมาก เลื่อนลงไปดูถึงเจอคำอธิบายจีโนม: ยีนรูปร่าง 8 ตัว, ขนาดล้อ 2 ตัว, ตำแหน่งล้อ 2 ตัว, ความหนาแน่นล้อ 2 ตัว, ความหนาแน่นตัวถัง 1 ตัว สุดท้ายมันลู่เข้าหาล้อสองล้อกับรูปทรงตัวถังระดับกลาง ๆ และหลังจากนั้นดูไม่ค่อยมีความคืบหน้ามากนัก ถ้าใส่ แรงขับและความเร็ว เป็นองค์ประกอบที่กลายพันธุ์ได้ด้วย น่าจะน่าสนใจ

• สนุกดีครับ แต่ การปรับความเร็ว ไม่ได้ตรงไปตรงมานัก ถ้ากด "Surprise" จะเร็วขึ้น ทำให้ผ่านการวนซ้ำหลายรอบได้ไว
  ความน่าจะเป็นของ mutation หรือโอกาสที่ g จะเปลี่ยน และขนาดของ mutation Δg เป็น hyperparameter ที่น่าลองปรับระหว่างดูประชากรวิวัฒน์ไปตามเวลา ถ้ามียีน "compliance" เพื่อให้รถเกิดระบบกันสะเทือนบางอย่างก็น่าจะน่าสนใจ ในการรันส่วนใหญ่ที่ผมลอง แทบทั้งหมดวิวัฒน์ไปเป็นรูปทรงคล้ายมอเตอร์ไซค์ Tron

  • ผมปล่อยให้รันเบื้องหลังอยู่นานด้วยความน่าจะเป็นของ mutation ที่สูงมาก แล้วก็ได้รูปทรงที่ต่างออกไปพอสมควร
    เป็นรูปแบบที่มี ล้อใหญ่กับล้อเล็ก ติดอยู่ เด้ง ๆ แล้วข้ามสิ่งกีดขวางทั้งหมดไปได้

• กระทู้เก่า ๆ ครับ:
  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)

• นี่คือ boxcar2d แบบไม่มี Flash
  https://news.ycombinator.com/item?id=2196747

  • แถมแปลกตรงที่ดูเหมือนว่า พารามิเตอร์ของช่วงล่าง หายไปทั้งหมด
    ฟิสิกส์ซิมูเลชันดูเหมือนจะใช้การชนแบบไม่ยืดหยุ่นอย่างชัดเจน ซึ่งค่อนข้างไม่สมจริง และทำให้รถหลายคันที่ดูภายนอกดีพอสมควรไม่สามารถผ่านสนามได้ ค่าสัมประสิทธิ์แรงเสียดทานก็ดูต่ำมาก รถส่วนใหญ่ที่ผมสร้างขึ้นยังขึ้นทางลาดสองช่วงไม่ได้เลย
  • ปรากฏว่า boxcar2d ทำงานได้สมบูรณ์บน Ruffle และ Internet Archive ก็โหลด Ruffle ให้อัตโนมัติ :)
    https://web.archive.org/web/20240428203838/http://boxcar2d.c...
  • ผมนึกว่าเคยเห็นอะไรแบบนี้เมื่อกว่า 10 ปีก่อน ที่แท้ก็ใช่จริง ๆ

• มีบั๊กเล็ก ๆ อยู่ หลังจากประมาณ 280m ไปแล้วไม่มีถนน ทำให้รถทุกคันตกลงไปในหลุมที่ไม่มีที่สิ้นสุด

• เขียนไว้ว่า “วิวัฒนาการรูปแบบสุ่มสองล้อให้เป็นรถตลอดหลายรุ่น” แต่แถวบ้านผมเรียก รถสองล้อ ว่ามอเตอร์ไซค์นะ
  แต่ซิมูเลชันก็เจ๋งมากครับ!

  • ในซิมูเลชันที่รถเหล่านี้วิ่ง ไม่มี มิติที่สาม ที่ยานพาหนะจะล้มคว่ำได้ และก็ไม่มีพื้นที่ให้ใส่ล้ออีกคู่
    ดังนั้นถึงความเร็วจะเป็น 0 มันก็ไม่ล้ม เหมือนรถสี่ล้อแบบดั้งเดิม ผมคิดว่าแค่คุณสมบัตินี้อย่างเดียวก็ถือว่าพฤติกรรมของมันใกล้กับรถสี่ล้อมากกว่ามอเตอร์ไซค์แล้ว

• ผมชอบ เพราะเป็น visualization ที่เป็นภาพชัดเจนและสนุกมาก
  หลังดูสิ่งนี้ ผมก็ไปทดลองกับ genetic algorithm ใน "Self-parking car evolution":
  https://trekhleb.dev/self-parking-car-evolution/

• ทำให้นึกถึงแอป Android ชั้นดีชื่อ Cell Lab ที่ให้สร้าง สิ่งมีชีวิตหลายเซลล์หรือเซลล์เดียว เพื่อให้อยู่ในจานเพาะเชื้อได้
  ถ้าต้องการ ก็เพิ่มระดับรังสีเพื่อให้เกิด mutation และวิวัฒนาการได้

• ถ้าชอบอะไรแบบนี้ แวะมาที่ https://old.reddit.com/r/WatchMachinesLearn/ ได้ครับ

  • หัวข้อน่าสนใจดี แต่ดูเหมือนไม่ใช่ subreddit ที่คึกคักเท่าไร โพสต์ล่าสุดเมื่อ 3 ปีก่อน :-/