Quan sát quá trình tiến hóa của ô tô bằng thuật toán di truyền

• Chương trình mô phỏng sự tiến hóa của ô tô bằng thuật toán di truyền

  • Mục tiêu là dùng thuật toán di truyền để cho các hình dạng 2 bánh ngẫu nhiên tiến hóa thành ô tô qua nhiều thế hệ
  • Dựa trên BoxCar2D nhưng được viết lại từ đầu, chỉ sử dụng cùng một engine vật lý (box2d)
  • Sử dụng thư viện seedrandom.js của David Bau

• Điều khiển và thiết lập

  • Có tính năng Save/Restore Population để lưu và khôi phục quần thể hiện tại trên máy cục bộ
  • Có thể bật/tắt vẽ bằng công tắc Surprise để tăng tốc độ mô phỏng
  • New Population chỉ khởi động lại quần thể ô tô, vẫn giữ nguyên đường đua
  • Cùng một seed sẽ luôn tạo ra cùng một đường đua, nên có thể thi đấu với bạn bè
  • Mutation rate là xác suất mỗi gene của từng cá thể bị đột biến thành giá trị ngẫu nhiên khi thế hệ mới được sinh ra
  • Mutation size là phạm vi mỗi gene có thể đột biến; số càng nhỏ thì càng gần với giá trị gốc
  • Elite clones là n chiếc xe đứng đầu sẽ được sao chép sang thế hệ tiếp theo
  • View top replay sẽ tạm dừng mô phỏng hiện tại và hiển thị chiếc xe có hiệu năng tốt nhất

• Biểu đồ

  • Màu đỏ: điểm cao nhất của mỗi thế hệ
  • Màu xanh lá: trung bình của 10 chiếc xe tốt nhất mỗi thế hệ
  • Màu xanh dương: trung bình của toàn bộ thế hệ

• Cấu trúc genome

  • Hình dạng (1 gene cho mỗi đỉnh, tổng cộng 8 gene)
  • Kích thước bánh xe (1 gene cho mỗi bánh, tổng cộng 2 gene)
  • Vị trí bánh xe (1 gene cho mỗi bánh, tổng cộng 2 gene)
  • Mật độ bánh xe (1 gene cho mỗi bánh, tổng cộng 2 gene) - càng tối thì mật độ càng cao
  • Mật độ khung gầm (1 gene) - càng tối thì mật độ càng cao

• Thông tin bổ sung

  • Mô phỏng không mang tính tất định, nên chiếc xe tốt nhất có thể không luôn cho hiệu năng ổn định
  • Độ phức tạp của địa hình tăng dần theo khoảng cách
  • Giờ đây mã nguồn đã có trên GitHub và sẵn sàng cho đóng góp từ cộng đồng

[GN⁺]

Ý kiến trên Hacker News

Tóm tắt như sau:

• Dự án này được tạo ra từ 20 năm trước, và nhờ Ruffle nên vẫn có thể chạy trong trình duyệt
• Do đặc tính của thuật toán di truyền, khi một thiết kế tốt xuất hiện ở một thời điểm nào đó, nó có xu hướng tiếp tục chiếm ưu thế ở các thế hệ sau. Có lẽ cần thử điều chỉnh thiết lập tỷ lệ đột biến và mức độ đột biến
• Có một lỗi nhỏ là sau mốc 280m thì không còn đường nữa, khiến các xe rơi xuống một hố sâu vô tận
• Có thể nhấn nút "Surprise" để đi nhanh qua nhiều thế hệ. Việc điều chỉnh tỷ lệ đột biến và mức độ đột biến rồi quan sát quá trình tiến hóa theo thời gian khá thú vị
• Sẽ rất thú vị nếu xe có một gene về "compliance" để có thể mô phỏng hệ thống treo. Trong phần lớn các lần chạy, thiết kế có xu hướng hội tụ về hình dạng giống xe Tron
• Địa hình không thay đổi ngay cả khi thế hệ thay đổi
• Nó cũng đã được giới thiệu nhiều lần trong các cuộc thảo luận HN trước đây (boxcar2d tương tự, nhưng được triển khai không cần Flash)
• Gợi lại ký ức ngày nhỏ từng dành hàng giờ chơi Boxcar 2D
• Tò mò liệu điều tương tự có khả thi trong môi trường mô phỏng dựa trên vật lý 3D hay không. Cũng thú vị khi nghĩ đến việc thuật toán di truyền có thể được dùng để khám phá các hình dạng khí động học mới cho drone và các phương tiện tương tự trong mô phỏng hay không