- Đang bay
- Tới mục tiêu
- Va chạm
- Chuyến bay tốt nhất của thế hệ trước
- Tới mục tiêu
- Va chạm
Sân chơi thuật toán di truyền
Thuật toán di truyền giải một bài toán theo cách tiến hóa định hình sinh vật: thử nhiều câu trả lời ngẫu nhiên, giữ lại những câu tốt hơn, trộn chúng với nhau, thay đổi ngẫu nhiên vài phần nhỏ, rồi lặp lại. Ở đây các câu trả lời là những tên lửa. Mỗi tên lửa chỉ làm theo một danh sách các cú đẩy ngẫu nhiên, ngoài ra không gì khác, và lúc đầu chúng lộn nhào không mục đích. Hãy nhấn Chạy và xem quần thể tiến bộ qua từng thế hệ cho đến khi phần lớn tên lửa lượn vòng qua các bức tường tới mục tiêu, mà không ai chỉ cho chúng phải bay đi đâu. Nhấn Chạy và xem một quần thể tên lửa cố gắng bay tới mục tiêu màu xanh lá. Mỗi tên lửa chỉ làm theo gen của nó, một danh sách các cú đẩy nhỏ, mỗi cú ứng với một thời điểm trong chuyến bay. Sau mỗi chuyến bay, những tên lửa đến gần nhất, và trên hết là những tên lửa đã tới đích, có khả năng cao nhất trở thành cha mẹ của thế hệ tiếp theo; gen của chúng được trộn lẫn và một vài gen bị thay đổi ngẫu nhiên. Nút Thế hệ tiếp theo bỏ qua phần còn lại của chuyến bay. Kéo trên sân để vẽ tường, và nhấp vào một bức tường để xóa nó.
Cách nó hoạt động
- Chọn chướng ngại vật, hoặc kéo trên sân để tự vẽ tường, rồi đặt quần thể, tỉ lệ đột biến và tuổi thọ.
- Nhấn Chạy và xem từng thế hệ bay; nút Thế hệ tiếp theo bỏ qua phần còn lại của chuyến bay.
- Theo dõi tỉ lệ tên lửa tới mục tiêu trên các ô số liệu và biểu đồ, rồi thử các tỉ lệ đột biến và phương pháp chọn lọc khác.
Tên lửa tiến hóa như thế nào
Mỗi tên lửa mang các gen: một cú đẩy nhỏ cho mỗi thời điểm trong chuyến bay. Gen của thế hệ đầu tiên là ngẫu nhiên. Sau chuyến bay, mỗi tên lửa nhận một điểm thích nghi: cao nhất khi tới đích sớm, sau đó càng kết thúc gần mục tiêu thì điểm càng cao, và bị chia cho mười nếu va chạm. Cha mẹ của thế hệ tiếp theo được chọn ngẫu nhiên, nhưng tên lửa thích nghi hơn có nhiều khả năng được chọn hơn. Mỗi con lấy phần đầu bộ gen từ một cha mẹ và phần còn lại từ cha mẹ kia, và một vài gen được thay bằng các cú đẩy ngẫu nhiên: đó là đột biến. Qua các thế hệ, những kế hoạch bay tốt lan rộng và ngày càng được cải thiện.
Các thiết lập thay đổi điều gì
Quần thể lớn hơn khám phá nhiều kế hoạch bay cùng lúc hơn và ít bị mắc kẹt hơn, nhưng mỗi thế hệ mất nhiều thời gian hơn. Tỉ lệ đột biến cân bằng giữa khám phá và giữ lại những gì hiệu quả: không có đột biến, quần thể nhanh chóng cạn ý tưởng mới; đột biến quá nhiều, nó quên các chuyến bay tốt nhanh hơn tốc độ tìm ra chúng. Chọn lọc roulette chọn cha mẹ theo tỉ lệ với độ thích nghi, còn giải đấu chọn tên lửa tốt nhất trong ba tên lửa ngẫu nhiên, cách này ít nhạy cảm hơn với cách độ thích nghi được co giãn. Chọn lọc tinh hoa sao chép nguyên vẹn tên lửa tốt nhất sang thế hệ tiếp theo, nên kết quả tốt nhất không bao giờ kém đi.
Câu hỏi thường gặp
Vì sao các tên lửa bị kẹt sau những bức tường so le?
Độ thích nghi của chúng đo khoảng cách theo đường thẳng tới mục tiêu, nên một tên lửa bay đâm vào bức tường bên dưới mục tiêu được điểm cao hơn một tên lửa bay ra xa để tìm khe hở. Quần thể dồn lại trong ngõ cụt đó, một tối ưu cục bộ. Quần thể lớn hơn, nhiều đột biến hơn hoặc chọn lọc giải đấu giúp nó thoát ra, và một hàm thích nghi đo con đường thực tế vòng qua các bức tường sẽ tránh được cái bẫy này. Chọn được một hàm thích nghi tốt là phần khó nhất khi dùng thuật toán di truyền.
Tiến hóa trong tự nhiên có diễn ra như vậy không?
Về đại thể thì có: biến dị từ đột biến và tái tổ hợp, sự di truyền gen và chọn lọc kẻ thích nghi nhất là những thành phần trong thuyết của Darwin. Tuy nhiên khác biệt rất lớn. Tự nhiên không có mục tiêu và không có công thức thích nghi, chỉ có sự sống sót và sinh sản, và bộ gen thật xây dựng cơ thể thông qua quá trình phát triển chứ không liệt kê các hành động.
Thuật toán di truyền được dùng vào việc gì?
Cho những bài toán có không gian câu trả lời khả dĩ rất lớn và có cách dễ dàng để chấm điểm một ứng viên: tạo hình ăng-ten, cánh và linh kiện ô tô, lập thời khóa biểu, tinh chỉnh tham số của các thuật toán khác, thiết kế mạng nơ-ron, và sáng tạo nghệ thuật cũng như chiến lược chơi game. Ăng-ten tiến hóa của NASA trên các vệ tinh ST5 năm 2006 là một ví dụ nổi tiếng.
Vì sao tên lửa tốt nhất đôi khi bay kém hơn ở thế hệ tiếp theo?
Khi không có chọn lọc tinh hoa, tên lửa tốt nhất không được sao chép: gen của nó chỉ tồn tại khi đã trộn với gen khác và có thể bị đột biến, nên thế hệ tiếp theo có thể đánh mất đúng chuyến bay của nó. Khi bật chọn lọc tinh hoa, tên lửa tốt nhất được giữ nguyên và kết quả tốt nhất không bao giờ kém đi.
Có dữ liệu nào được gửi lên máy chủ không?
Không. Các tên lửa bay và tiến hóa ngay trong trình duyệt của bạn, và những bức tường bạn vẽ được lưu trong bộ nhớ cục bộ của trình duyệt này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa