Sự tiến hóa của code [P5]

Giải thuật di truyền, Phần II: Chọn lọc

Đây là nơi mà chúng ta áp dụng nguyên tắc chọn lọc của Darwin. Chúng ta cần đánh giá quần thể và chọn ra những thành viên thích hợp để làm cá thể cha mẹ cho thế hệ kế tiếp. Tiến trình chọn lọc có thể được chia thành hai bước:

1) Đánh giá mức độ thích ứng

Để giải thuật di truyền hoạt động đúng chức năng, chúng ta sẽ cần phải thiết kế một hàm gọi là “Hàm số fitness” (hàm số tính mức độ thích ứng). Hàm này sẽ đưa ra một điểm số để mô tả mức độ thích ứng của một thành viên trong quần thể. Điều này, dĩ nhiên, hoàn toàn không giống với những gì xảy ra trong thế giới thật. Các sinh vật trong thế giới thật không được cho điểm số, chúng đơn giản là sống sót hoặc không. Nhưng trong trường hợp của giải thuật di truyền truyền thống, nơi mà chúng ta đang cố gắng phát triển một giải pháp tối ưu cho một vấn đề, chúng ta cần phải có một đánh giá định lượng cho mọi giải pháp khả dĩ.

Chúng ta hãy kiểm tra trong ví dụ gần nhất, con khỉ gõ bàn phím. Một lần nữa, hãy đơn giản hóa ngữ cảnh và phát biểu rằng ta đang cố gắng phát triển từ “cat”. Chúng ta có 3 thành viên trong quần thể: hut, car và box. Rõ ràng từ car là thích ứng nhất, bởi nó chứa tới hai kí tự đúng, hut chỉ có một kí tự đúng, còn box thì không có kí tự đúng nào. Do đó, hàm fitness của chúng ta là:

fitness = số lượng kí tự đúng

Chúng ta sẽ muốn xét tới những ví dụ khác có hàm fitness phức tạp hơn, nhưng ví dụ trên là một xuất phát điểm tốt để bắt đầu.

2) Tạo một bể giao phối (a mating pool)

Sau khi mức độ thích ứng đã được tính toán cho tất cả các thành viên trong quần thể, chúng ta bây giờ có thể chọn ra những thành viên nào phù hợp nhất để làm cha mẹ và đặt chúng vào một bể giao phối (a mating pool). Chúng ta có thể thực hiện một vài cách tiếp cận khác nhau ở đây. Ví dụ, chúng ta có thể triển khai một phương pháp gọi là phương pháp elitist (phương pháp tinh hoa) và nói, “Tìm 2 thành viên có điểm số thích ứng cao nhất, tất cả con cái sẽ được tạo ra bởi 2 thành viên này”. Đây có lẽ là một trong những phương pháp dễ nhất để thực hiện; tuy nhiên, nó lại tác động lớn tới nguyên tắc của sự đa dạng. Nếu 2 thành viên của một quần thể (gồm 1000 cá thể chẳng hạn) là những thành viên duy nhất được lựa chọn để sinh sản, thế hệ kế tiếp sẽ có ít sự đa dạng và sẽ kiềm hãm quá trình tiến hóa. Chúng ta có thể thay vào đó tạo ra một bể giao phối cho một số lượng lớn các thành viên – ví dụ, top 50% của quần thể, 500 trong số 1000 thành viên. Điều này cũng dễ để lập trình, nhưng nó sẽ không tạo ra những kết quả tối ưu. Trong trường hợp này, cơ hội được chọn để tham gia sinh sản của những phần tử có điểm số cao nhất sẽ cũng chỉ bằng với các phần tử có điểm số trung bình. Và tại sao phần tử thứ 500 lại được chọn để tham gia sinh sản, trong khi phần tử thứ 501 lại không được?

Một giải pháp tốt hơn cho bể giao phối là sử dụng phương pháp xác suất, hay chúng ta còn gọi là “vòng quay may mắn” (hay “vòng quay roulette”). Để minh họa cho phương pháp này, hãy xem xét một ví dụ đơn giản nơi mà chúng ta có 5 phần tử, mỗi phần tử tương ứng với một điểm số fitness.

Điều đầu tiên chúng ta muốn là chuẩn hóa tất cả các điểm số này. Hãy cộng tất cả các điểm số lại.

Tổng fitness = 3 + 4 + 0.5 + 1.5 + 1 = 10

Chia mỗi điểm số cho tổng fitness, ta sẽ có fitness chuẩn.

Và bây giờ là lúc chơi vòng quay may mắn.

Xoay vòng quay và bạn sẽ thấy rằng phần tử B có cơ hội cao nhất để được chọn, theo sau bởi A, sau đó D, sau đó E và cuối cùng là C. Phương pháp lựa chọn dựa trên xác suất của giá trị fitness là một cách tiếp cận rất tốt. Thứ nhất, nó đảm bảo rằng những phần tử có điểm số cao nhất sẽ có nhiều cơ hội nhất để được chọn. Thứ hai, nó không loại bỏ hoàn toàn bất cứ một cá thể nào từ quần thể. Không giống như phương pháp elitist, thậm chí phần tử với điểm số thấp nhất (trong trường hợp này là C) vẫn có cơ hội truyền lại gen của nó cho thế hệ tiếp theo. Hoàn toàn có khả năng rằng một phần tử có điểm số thấp nhất nhưng lại chứa những mã gen thực sự quan trọng và do đó phần tử đó không nên bị loại trừ một cách hoàn toàn khỏi quần thể. Ví dụ, trong trường hợp của “to be or not to be”, chúng ta có các phần tử sau.

A: to be or not to go
B: to be or not to pi
C: xxxxxxxxxxxxxxxxbe

Như bạn có thể thấy, phần tử A và B rõ ràng là thích ứng nhất và sẽ có điểm số cao nhất. Nhưng cả hai phần tử này đều không chứa những kí tự chính xác sau cùng của cụm từ. Phần tử C, mặc dù có điểm số rất thấp, nhưng lại chứa dữ liệu di truyền cho từ cuối của cụm từ. Và do vậy trong khi chúng ta muốn A và B sẽ được chọn để tạo ra phần đông cá thể con của thế hệ kế tiếp, ta vẫn muốn C có cơ hội nhỏ để tham gia vào tiến trình sinh sản này.