Giải thích thuật toán di truyền
Tiến hóa đã tạo ra mắt, cánh và bộ não mà không cần nhà thiết kế, chỉ bằng cách giữ lại những gì hiệu quả và biến đổi nó. Thuật toán di truyền mượn ý tưởng đó để giải bài toán trên máy tính. Nó không cần hiểu bài toán, chỉ cần phân biệt được câu trả lời tốt hơn với câu trả lời kém hơn, điều khiến nó trở thành công cụ mạnh mẽ khi không gian câu trả lời khả dĩ quá lớn và quá kỳ lạ để tìm kiếm theo bất kỳ cách nào khác.
Ý tưởng
Trong những năm 1960 và 1970, John Holland tại Đại học Michigan đã biến thuyết của Darwin thành một thuật toán, được ông mô tả trong cuốn sách Adaptation in Natural and Artificial Systems năm 1975. Cùng thời gian đó, Ingo Rechenberg và Hans-Paul Schwefel ở Đức phát triển các chiến lược tiến hóa cho thiết kế kỹ thuật. Công thức chung là: duy trì một quần thể lời giải ứng viên, chấm điểm chúng, để những lời giải tốt hơn sinh sản kèm biến đổi, và lặp lại qua nhiều thế hệ.
Gen và quần thể
Mỗi ứng viên được mô tả bằng một nhiễm sắc thể, tức một danh sách gen. Trong sân chơi, gen của một tên lửa là các cú đẩy của nó, mỗi cú ứng với một thời điểm trong chuyến bay; trong các bài toán khác, gen có thể là các bit của một số, thứ tự các thành phố trên một lộ trình hoặc kích thước các bộ phận trong một thiết kế. Thế hệ đầu tiên là ngẫu nhiên, nghĩa là nó khám phá không gian câu trả lời rất rộng nhưng hầu như không có câu trả lời nào tốt.
Hàm thích nghi
Độ thích nghi là con số duy nhất cho biết một ứng viên tốt đến mức nào, và đó là điều duy nhất thuật toán biết về bài toán. Với các tên lửa, nó thưởng nhiều nhất cho việc tới đích sớm, sau đó là kết thúc gần mục tiêu, và phạt việc va chạm. Một hàm thích nghi được chọn tốt dẫn dắt quá trình tìm kiếm một cách suôn sẻ tới các câu trả lời tốt; một hàm cẩu thả sẽ thưởng sai điều, và thuật toán sẽ khai thác mọi kẽ hở mà nó để lại.
Chọn lọc
Cha mẹ được chọn sao cho các ứng viên thích nghi hơn có nhiều con hơn, nhưng những ứng viên yếu hơn vẫn có cơ hội, vì gen của chúng có thể chứa những mảnh hữu ích. Chọn lọc bánh xe roulette cho mỗi ứng viên một lát trên bánh xe tỉ lệ với độ thích nghi của nó; chọn lọc giải đấu chọn ngẫu nhiên vài ứng viên và lấy ứng viên tốt nhất trong số đó. Chọn lọc mạnh hơn đẩy nhanh tiến bộ nhưng cũng làm quần thể giống nhau hơn, điều có thể khiến quá trình tìm kiếm kết thúc quá sớm.
Lai ghép và đột biến
Lai ghép kết hợp hai cha mẹ: ở đây một con lấy phần đầu bộ gen từ một cha mẹ và phần còn lại từ cha mẹ kia, nhờ đó những pha điều khiển ban đầu của một tên lửa có thể gặp những pha điều khiển về sau của một tên lửa khác. Đột biến thay ngẫu nhiên một vài gen. Lai ghép tổ hợp lại những gì quần thể đã có; đột biến mang tới những gì nó chưa từng có. Định lý sơ đồ (schema theorem) của Holland mô tả cách các khối xây dựng ngắn gồm những gen tốt lan rộng trong quần thể dưới sự kết hợp giữa chọn lọc và tái tổ hợp này.
Chọn lọc tinh hoa, khám phá và khai thác
Sao chép nguyên vẹn vài ứng viên tốt nhất sang thế hệ tiếp theo, tức chọn lọc tinh hoa, bảo đảm rằng câu trả lời tốt nhất không bao giờ bị mất. Mọi thuật toán di truyền đều phải cân bằng giữa khám phá, tức thử những vùng mới của không gian tìm kiếm, và khai thác, tức tinh chỉnh những gì đã tốt. Quá ít biến dị thì quần thể hội tụ về một câu trả lời tầm thường; quá nhiều thì nó không bao giờ ổn định. Kích thước quần thể, tỉ lệ đột biến và áp lực chọn lọc là những núm vặn điều chỉnh sự cân bằng đó.
Tối ưu cục bộ
Thuật toán di truyền chỉ đi theo độ thích nghi, nên nó có thể bị đánh lừa. Khi con đường tới câu trả lời tốt nhất ban đầu đi qua những câu trả lời kém hơn, quần thể leo lên ngọn đồi gần nhất và ở lại đó: một tối ưu cục bộ. Sau những bức tường so le trong sân chơi, các tên lửa va chạm bên dưới mục tiêu được điểm cao hơn những tên lửa rẽ ra xa để tìm khe hở, nên quần thể dồn cục vào bức tường. Các cách khắc phục gồm quần thể lớn hơn, tỉ lệ đột biến cao hơn, giữ cho quần thể đa dạng, và trên hết là một hàm thích nghi tốt hơn.
Tự khám phá
Hãy mở sân chơi thuật toán di truyền để cho tên lửa tiến hóa vòng qua một bức tường, một khe hở, các cột, những bức tường so le hoặc những bức tường do chính bạn vẽ. Thay đổi quần thể, tỉ lệ đột biến, tuổi thọ và phương pháp chọn lọc, bật và tắt chọn lọc tinh hoa, rồi theo dõi trên biểu đồ xem tỉ lệ tên lửa tới mục tiêu tăng nhanh đến mức nào, hoặc vì sao nó không tăng.
Câu hỏi thường gặp
Thuật toán di truyền có phải là một dạng trí tuệ nhân tạo không?
Nó thuộc lĩnh vực rộng hơn của AI và học máy, với vai trò là một phương pháp tìm kiếm và tối ưu hóa. Nó không học từ các ví dụ như mạng nơ-ron; nó cải thiện các lời giải ứng viên bằng thử nghiệm và chọn lọc. Hai phương pháp này thường được kết hợp, chẳng hạn bằng cách tiến hóa cấu trúc hoặc trọng số của mạng nơ-ron, một cách tiếp cận gọi là tiến hóa thần kinh (neuroevolution).
Thuật toán di truyền có luôn tìm được câu trả lời tốt nhất không?
Không. Nó là một phương pháp heuristic: thường tìm được câu trả lời tốt cho những bài toán khó, nhưng không bảo đảm tìm ra câu trả lời tốt nhất và không chứng minh được câu trả lời của nó gần tốt nhất đến mức nào. Với những bài toán mà một phương pháp chính xác đủ nhanh, phương pháp đó tốt hơn.
Thuật toán di truyền khác chiến lược tiến hóa ở điểm nào?
Cả hai đều là thuật toán tiến hóa. Thuật toán di truyền cổ điển chú trọng lai ghép trên các nhiễm sắc thể dạng chuỗi; chiến lược tiến hóa chủ yếu làm việc với đột biến trên số thực và thường tự điều chỉnh độ lớn đột biến của mình trong quá trình chạy. Các phương pháp hiện đại kết hợp ý tưởng từ cả hai.
Vì sao lúc đầu các tên lửa vụng về đến vậy?
Gen đầu tiên của chúng là những cú đẩy hoàn toàn ngẫu nhiên, nên tính trung bình chúng triệt tiêu lẫn nhau và tên lửa trôi dạt. Chỉ sau khi chọn lọc đã giữ lại những tên lửa hiếm hoi tình cờ đẩy gần đúng hướng, và lai ghép đã kết hợp những đoạn tốt của chúng, các chuyến bay phối hợp nhịp nhàng mới xuất hiện.
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.
Mở sân chơi thuật toán di truyền