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

Giải thuật di truyền, phần III: Sinh sản

Sau khi đã có được chiến lược cho việc lựa chọn các cá thể cha mẹ, chúng ta bây giờ cần tìm cách chỉ ra phải thực hiện sự sinh sản này như thế nào để tạo ra một quần thể của thế hệ tiếp theo. Hãy nhớ rằng theo nguyên lý di truyền của Darwin – con cái phải thừa hưởng thuộc tính từ cha mẹ của chúng. Một lần nữa, có nhiều kĩ thuật để chúng ta giải quyết vấn đề này. Ví dụ, một phương pháp khả dĩ (và dễ lập trình) là sử dụng sinh sản vô tính, nghĩa là chúng ta chọn một cá thể cha mẹ và tạo một cá thể con cái với thuộc tính giống hệt cá thể cha mẹ của nó. Tuy nhiên, cách tiếp cận tiêu chuẩn của giải thuật lập trình, là chọn 2 cá thể cha mẹ và tạo ra một cá thể con cái theo các bước sau.

1) Trao đổi chéo (crossover)

Trao đổi chéo liên quan đến việc tạo ra một cá thể con cái từ mã di truyền của cá thể cha và cá thể mẹ. Trong trường hợp con khỉ gõ bàn phím, hãy giả sử chúng ta chọn 2 cụm từ từ bể giao phối.

Parent A: FORK
Parent B: PLAY

Bây giờ thì hoàn toàn phụ thuộc vào chúng ta trong việc tạo ra cụm từ con cái từ hai cá thể cha mẹ này. Có lẽ cách hiển nhiên nhất (hãy gọi cách này là phương pháp 50/50) sẽ là lấy 2 kí tự đầu từ A và 2 kí tự sau từ B, chúng ta sẽ có cụm từ con là FOAY:

Một biến thể khác của kĩ thuật này là chọn một điểm giữa ngẫu nhiên. Nói cách khác, chúng ta không chọn một cách chính xác 50% mã từ một cá thể cha mẹ. Chúng ta có thể đôi khi tạo ra được cụm từ con cái FLAY, hoặc đôi khi là FORY. Cách này thì tốt hơn cách tiếp cận 50/50, bởi chúng ta có khả năng tạo ra nhiều sự đa dạng hơn cho thế hệ kế tiếp.

Một khả năng nữa là chọn một cách ngẫu nhiên một một cá thể cha mẹ cho mỗi kí tự trong chuỗi cá thể con cái. Bạn có thể nghĩ tới cách này như việc tung đồng xu 4 lần: sấp từ cá thể cha mẹ A, ngửa từ cá thể cha mẹ B. Ở đây chúng ta có thể có được nhiều kết quả khác nhau như: PLRY, FLRK, FLRY, FORY …

Chiến lược này về cơ bản sẽ tạo ra các kết quả tương đồng với phương pháp điểm giữa ngẫu nhiên; tuy nhiên, nếu trình tự của thông tin di truyền có đóng vai trò trong biểu hiện kiểu hình, bạn có thể thích lựa chọn giải pháp này hơn thay vì lựa chọn giải pháp kia.

2) Đột biến (mutation)

Sau khi DNA của một cá thể con được tạo ra thông qua trao đổi chéo, chúng ta cần áp dụng một tiến trình cuối cùng trước khi thêm cá thể con vào quần thể thế hệ kế tiếp – đột biến. Đột biến là một bước tùy chọn, trong một vài trường hợp nó thực sự không cần thiết. Tuy nhiên, nó tồn tại trong thuật toán bởi vì nó được đề cập trong nguyên tắc đa dạng sinh học của Darwin. Chúng ta khởi tạo ngẫu nhiên một quần thể ban đầu, và đã đảm bảo rằng chúng ta đã bắt đầu với một quần thể đa dạng các phần tử. Tuy nhiên, ta chỉ đảm bảo được mức độ đa dạng này cho thế hệ đầu tiên, và đột biến sẽ cho phép ta tạo thêm sự đa dạng thông qua bản thân tiến trình tiến hóa.

Đột biến được mô tả theo tỉ lệ. Một thuật toán di truyền nhất định có thể có tỷ lệ đột biến 5% hoặc 1% hoặc 0.1%... Giả sử chúng ta vừa hoàn thành việc trao đổi chéo và tạo ra một cá thể con là FORY. Nếu chúng ta có tỷ lệ đột biến là 1%, điều này có nghĩa là đối với mỗi kí tự trong cụm từ được tạo ra từ trao đổi chéo, nó có 1% khả năng đột biến. Một kí tự đột biến nghĩa là gì? Trong trường hợp này, chúng ta quy định đột biến nghĩa là chọn ra một kí tự mới ngẫu nhiên. Xác suất 1% là khá thấp, và nhìn chung đột biến sẽ không xảy ra cho một chuỗi có 4 kí tự (96% sẽ không có đột biến). Tuy nhiên, khi nó xảy ra, kí tự đột biến sẽ được thay thế bằng một kí tự ngẫu nhiên khác (hình 9.6)

Như chúng ta sẽ thấy trong một số ví dụ, tỷ lệ đột biến có thể ảnh hưởng lớn tới hành vi hệ thống. Một cách chắc chắn, tỷ lệ đột biến rất cao (ví dụ 80%) sẽ kéo lùi quá trình tiến hóa. Nếu phần lớn gen của cá thể con được tạo ra một cách ngẫu nhiên, thì chúng ta không thể đảm bảo rằng các gen “thích ứng” hơn sẽ xuất hiện với tần suất lớn hơn cho mỗi thế hệ tiếp theo.

Quá trình chọn lọc (chọn ra hai cá thể cha và mẹ) và sinh sản (trao đổi chéo và đột biến) được lặp đi lặp lại N lần cho đến khi chúng ta có một quần thể mới của N phần tử. Ở thời điểm này, quần thể mới của các cá thể con sẽ trở thành quần thể hiện tại và chúng ta sẽ lặp lại quá trình để đánh giá mức độ thích ứng và thực hiện việc chọn lọc và sinh sản một lần nữa.

Bây giờ chúng ta đã hoàn thành mô tả chi tiết tất cả các bước của giải thuật di truyền, đây là lúc để đọc chương trình Processing. Bởi vì các bước giải thuật đã được nói đến khá dài, chúng ta hãy tóm tắt lại tổng quan của giải thuật một lần nữa. Sau đó, chúng ta sẽ làm việc với chương trình tương ứng với từng bước.

THIẾT LẬP

Bước 1: Khởi tạo. Tạo ra một quần thể của N phần tử, mỗi phần tử có DNA được tạo ngẫu nhiên.

VÒNG LẶP

Bước 2: Chọn lọc. Đánh giá mức độ thích ứng của mỗi phần tử trong quần thể và xây một bể giao phối.

Bước 3: Sinh sản. Lặp lại N lần:

1. Chọn 2 cá thể cha mẹ với xác suất được chọn dựa trên mức độ thích ứng tương ứng.
2. Trao đổi chéo – tạo một cá thể con bằng cách kết hợp DNA của hai cá thể cha mẹ
3. Đột biến – tạo đột biến DNA cho cá thể con dựa trên xác suất
4. Thêm cá thể con vào quần thể mới

Bước 4: thay thế quần thể cũ bằng quần thể mới và quay lại bước 2.