Tại sao sử dụng giải thuật di truyền?

Khi các mô phỏng máy tính của các thuật toán tiến hóa bắt đầu từ những năm 1950, phần lớn các giải thuật di truyền (còn gọi là "GA" – genetic algorithm) ta biết ngày nay đã được phát triển bởi John Holland, một giáo sư tại đại học Michigan, tác giả của các cuốn sách “Thích nghi trong tự nhiên” (Adaptation in Natural) và “Các hệ thống nhân tạo” (Artificial Systems) – các cuốn sách đi tiên phong trong nghiên cứu GA. Ngày nay, nhiều giải thuật di truyền nữa là một phần của một phạm vi nghiên cứu rộng hơn, thường được gọi là “Tính toán tiến hóa” (Evolutionary Computing).

Để minh họa cho giải thuật di truyền truyền thống, chúng ta sẽ bắt đầu với các con khỉ. À, không liên qua tới tổ tiên tiến hóa của chúng ta nhé. Chúng ta sẽ bắt đầu với một vài con khỉ hư cấu đang gõ lên bàn phím máy tính với mục đích là sẽ đánh máy được một tác phẩm hoàn chỉnh của Shakerspeare.

“Định lý con khỉ vô hạn” được phát biểu như sau: Một con khỉ gõ lên bàn phím một cách ngẫu nhiên cuối cùng sẽ gõ được một tác phẩm hoàn chỉnh của Shakerspeare (với một khoảng thời gian được cho vô cùng). Vấn đề với lý thuyết này là xác suất để con khỉ nói trên gõ được một tác phẩm Shakerspeare hoàn chỉnh là vô cùng thấp đến nỗi nếu con khỉ đó bắt đầu đánh chữ tại thời điểm Big Bang, chúng ta thậm chí còn không có Hamlet ở thời điểm đọc bài viết này.

Hãy xem xét một con khỉ tên là Geogre. Geogre gõ trên một bàn phím đơn giản chỉ có 27 kí tự: 26 kí tự chữ và một kí tự khoảng trống (space). Do đó xác suất để Geogre đánh trúng một kí tự là 1/27.

Chúng ta hãy xem xét cụm từ “to be or not to be that is the question” (chúng ta đã đơn giản nó từ văn bản gốc “To be, or not to be: that is the question” – tạm dịch: tồn tại hay không tồn tại, đó chính là câu hỏi). Cụm từ này dài 39 kí tự (bao gồm kí tự khoảng trống). Nếu Geogre bắt đầu đánh máy, cơ hội để nó gõ đúng kí tự đầu tiên là 1/27. Bởi xác suất để nó gõ đúng kí tự thứ hai cũng là 1/27, nó có 1/ (27 * 27) cơ hội để gõ đúng hai kí tự đầu tiên theo đúng thứ tự. Do đó, xác suất để Geogre gõ đúng được toàn bộ cụm từ là:

(1/27) nhân cho chính nó 39 lần, tức là (1/27)³⁹

Bằng 1 trên

66,555,937,033,867,822,607,895,549,241,096,482,953,017,615,834,735,226,163 cơ hội để gõ đúng cụm từ!

Không cần phải nói, xác suất để gõ trúng cụm từ này, chứ chưa nói đến toàn bộ tác phẩm, là rất khó xảy ra. Ngay cả khi Geogre là một mô phỏng máy tính và có thể gõ một triệu lần trên một giây, để Geogre đạt được 99% xác suất gõ đúng cụm từ, nó phải gõ bàn phím trong 9,719,096,182,010,563,073,125,591,133,903,305,625,605,017 năm ( Lưu ý rằng độ tuổi của vũ trụ được ước tính chỉ là 13,750,000,000 năm).

Việc chỉ ra những con số cực lớn này không phải để làm cho bạn phải đau đầu, nhưng là để chứng minh rằng một giải thuật “bạo lực” (gõ mọi cụm từ ngẫu nhiên có thể) không phải là một chiến lược hợp lý để đến được mục tiêu “to be or not to be that is the question”. Các giải thuật di truyền chỉ ra cho chúng ta thấy vẫn có thể bắt đầu bằng các cụm từ ngẫu nhiên và tìm ra giải pháp thông qua quá trình mô phỏng sự tiến hóa.

Bây giờ, cần lưu ý rằng vấn đề này (đi đến cụm từ “to be or not to be that is the question”) là một điều vô nghĩa. Vì chúng ta biết câu trả lời, tất cả những gì chúng ta cần làm là gõ nó. Đây là một chương trình Processing để giải quyết vấn đề.

string s = "To be or not to be that is the question";

println(s);

Tuy nhiên, điểm muốn nói ở đây là ở chỗ giải quyết một vấn đề với một câu trả lời đã biết trước cho phép chúng ta kiểm tra chương trình ta viết một cách dễ dàng. Một khi chúng ta giải quyết vấn đề thành công, chúng ta có thể cảm thấy tự tin hơn trong việc sử dụng các giải thuật di truyền để làm một vài công việc thực sự hữu ích: giải quyết các vấn đề với các câu trả lời không rõ. Vì vậy, ví dụ đầu tiên này không có mục đích nào khác là để mô tả giải thuật di truyền hoạt động như thế nào. Nếu chúng ta kiểm tra giải thuật di truyền với câu trả lời đã biết trước và nhận được kết quả “to be or not to be”, thì chúng ta đã thành công trong việc viết ra giải thuật di truyền của mình.