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

Giải thuật di truyền, phần I: tạo ra một quần thể

Trong ngữ cảnh con khỉ gõ bàn phím, chúng ta sẽ tạo ra một quần thể của các cụm từ. (Lưu ý rằng chúng ta đang sử dụng thuật ngữ “cụm từ” khá lỏng lẻo, có nghĩa là một chuỗi các ký tự). Điều này đặt ra câu hỏi: Làm thế nào để chúng ta tạo ra quần thể này? Đây chính là nơi để áp dụng nguyên tắc về sự đa dạng của Darwin. Nói một cách đơn giản, chúng ta đang cố gắng phát triển cụm từ “cat” và chúng ta có một quần thể có 3 cụm từ.

hug
rid
won

Chắc chắn, có sự khác biệt trong ba cụm từ ở trên, nhưng dù bạn có trộn lẫn hay kết hợp các cụm từ đó theo cách nào đi nữa thì bạn cũng không bao giờ có được con mèo (cat). Không có đủ sự đa dạng quần thể ở đây để phát triển được một giải pháp tối ưu. Tuy nhiên, nếu chúng ta có hàng ngàn cụm từ, tất cả đều được tạo ra ngẫu nhiên, rất có thể có một thành viên trong quần thể có chữ cái bắt đầu bằng c, một thành viên khác có chữ cái thứ hai là a, và một thành viên khác có chữ cái t ở vị trí thứ ba. Một quần thể lớn chắc chắn sẽ cung cấp cho chúng ta nhiều sự đa dạng để tạo ra một cụm từ mong muốn (và trong phần hai của giải thuật, chúng ta sẽ có cơ hội khác để đưa ra nhiều biến thể hơn trong trường hợp quần thể ban đầu không có đủ). Vì vậy, chúng ta có thể mô tả cụ thể hơn bước một như sau:

Tạo ra một quần thể các phần tử, trong đó các phần tử được tạo ngẫu nhiên.

Điều này lại dẫn tới một câu hỏi quan trọng. Bản thân phần tử là gì? Khi đi tới các ví dụ trong chương này, chúng ta sẽ thấy một vài ngữ cảnh khác nhau; chúng ta có thể có một quần thể của hình ảnh (images) hoặc một quần thể của phương tiện giao thông (vehicles). Cái cốt lõi, và là cái mới cho chúng ta ở chương này, là mỗi thành viên trong một quần thể có một “DNA” ảo, một tập hợp các thuộc tính (ta có thể gọi các thuộc tính này là gen) mô tả hình dạng và hành vi của một phần tử. Ví dụ, trong trường hợp con khỉ đánh máy, DNA chỉ đơn giản là một chuỗi ký tự.

Trong lĩnh vực di truyền học, có một sự khác biệt quan trọng giữa khái niệm kiểu gen (genotype) và kiểu hình (phenotype). Mã di truyền - trong trường hợp của chúng ta - là dữ liệu số (chuỗi kí tự) - là một phần tử kiểu gen. Đây là những gì được chuyển từ thế hệ này sang thế hệ khác. Còn phần tử kiểu hình là biểu hiện của dữ liệu số đó. Sự phân biệt này là chìa khóa trong việc bạn sử dụng giải thuật di truyền như thế nào trong công việc của mình. Các đối tượng trong thế giới của bạn là gì? Làm thế nào để bạn thiết kế kiểu gen cho các đối tượng (cấu trúc dữ liệu để lưu trữ thuộc tính của mỗi đối tượng) cũng như kiểu hình (bạn đang sử dụng các biến này để diễn tả điều gì). Chúng ta đã từng làm điều này trong lập trình đồ họa. Ví dụ đơn giản nhất có lẽ là màu sắc.

Như chúng ta thấy, kiểu gen là dữ liệu số. Mỗi màu là một biến chứa một số nguyên và chúng ta chọn để biểu hiện số nguyên đó như là một màu. Nhưng việc chúng ta chọn biểu hiện dữ liệu như thế nào là tùy ý. Theo một cách tiếp cận khác, chúng ta có thể sử dụng số nguyên để mô tả chiều dài của một đường thẳng hoặc trọng lượng của một lực.

Cái hay của ví dụ con khỉ gõ bàn phím của chúng ta là không có sự khác biệt giữa kiểu gen và kiểu hình. Bản thân dữ liệu DNA là một chuỗi các ký tự và biểu hiện của dữ liệu đó cũng là một chuỗi ký tự.

Vậy là, chúng ta cuối cùng cũng đã kết thúc bước đầu tiên với một mô tả yêu cầu cụ thể hơn cho bước này:

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