Genetic Algorithm – Thuật toán di truyền

Đầu thế kỷ 19, một lý thuyết được nêu ra bởi nhà khoa học Darwin: “Loài người có họ hàng với loài vượn” đã làm chấn động nền tảng khoa học. Trong đó, ý tưởng chủ đạo là sự tiến hóa của các muôn loài dựa trên sự chọn lọc tự nhiên. Lấy cảm hứng từ lý thuyết này, các nhà khoa học máy tính đã phát triển một thuật toán phỏng theo ý tưởng này nhằm giải quyết các bài toán tìm kiếm tối ưu có không gian cực lớn mà phương pháp vét cạn đơn thuần không giải quyết nổi.

Giả thuyết Những Con Khỉ và Shakespeare

Giả thuyết này được tạo ra bởi Nick Hoggard nói rằng khở đầu từ 100 con khỉ, số lượng khỉ sẽ gấp đôi sau vài ngày. Nếu một con khỉ, giả sử rằng mỗi giây gõ được 1 ký tự, và mỗi trang giấy là 2000 ký tự. Xác xuất chọn lựa để gõ 1 phím trên bàn phím của một con khỉ là như nhau. Với một giả thiết như vậy, thì sẽ mất khoảng 2,737,850 tỷ tỷ tỷ tỷ năm để có thể tạo ra một văn bản giống hệt với toàn bộ công trình văn học của Shakespeare.

Chúng ta không đi sâu vào giả thuyết này. Chỉ xét đơn cử một ví dụ: Giả sử rằng ta sinh ngẫu nhiên các chuỗi ký tự cùng độ dài với chuỗi “to be or not to be”, 18 ký tự kể cả khoảng trắng. Và giả sử các lựa chọn sinh ngẫu nhiên chỉ gồm 27 lựa chọn bao gồm các ký tự từ a đến z và một khoảng trắng. Như vậy số lượng các chuỗi ngẫu nhiên có thể sinh ra là 27^18 (lũy thừa) = 58,149,737,003,040,059,690,390,169. Rõ ràng đối với một số lượng các trường hợp như vậy, vét cạn là phương pháp hoàn toàn không khả thi.

Thuật toán di truyền đã được giới thiệu để giải quyết các bài toán tối ưu tìm kiếm trong không gian cực lớn như đã nếu ở trên.

Thuật toán Di truyền (Genetic algorithm)

Tư tưởng thuật toán này dựa trên ý tưởng về lai tạo và biến dị để tạo ra cá thể tốt hơn như sau:
Giả sử rằng khởi điểm ta có một quần thể các các thể. Các cá thể có thể “lai tạo”(crossover) với nhau và “biến dị”(mutate) để tạo ra cá thể mới. Các cá thể mới tốt hơn và dần thay thế những cá thể cũ. Như vậy sau một số thế hệ tiến hóa, chúng ta sẽ dần tạo ra cá thể tối ưu.

Ở đây sẽ có một số câu hỏi đặt ra, đó là:

  • Thế nào là tối ưu?

    Đó là trạng thái mục tiêu mà ta cần đạt được. Nghĩa là, ta cần sinh ra một cá thể có trạng thái ứng với trạng thái mục tiêu. Ví dụ như sinh ra một chuỗi có nội dung là “to be or not to be”.

  • Thế nào là cá thể tốt hơn cá thể khác?

    Đó là sự đánh giá độ mạnh yếu (fitness) được định nghĩa dựa trên khoảng cách từ một cá thể đến cá thể mục tiêu. Khoảng cách càng gần thì cá thể càng tốt.

  • Thế nào là sự lai tạo?

    Mỗi cá thể được mã hóa thành một chuỗi các gene gọi là chromosome. Trong máy tính, chromosome thường được mô tả là một chuỗi bit (mỗi gene là một bit) hoặc một chuỗi các ký tự (mỗi gene là một ký tự). Sự lai tạo được thực hiện bằng cách lựa chọn hai cá thể trong quần thể để lai tạo. Để mô tả chọn lọc tự nhiên, cũng như để hướng tới việc cá thể sau tốt hơn cá thể trước, việc chọn lựa sẽ ưu tiên chọn các cá thể mạnh hơn hay nói cách khác, các cá thể mạnh hơn có nhiều cơ hội được lựa chọn để lai tạo hơn. Sự lai tạo giữa hai cá thể thực chất là việc ghép phần đầu chromosome của cá thể này với phần đuôi chromosome của cá thể kia.

  • Làm sao để mã hóa thành các chromosome?

    Tùy vào từng bài toán sẽ có những cách mã hóa khác nhau. Đây cũng chính là mấu chốt của vấn đề, nếu ta có thể mã hóa bài toán thành dạng chromosome, bài toán có thể giải quyết bằng thuật giải di truyền.

  • Biến dị là gì?

    Việc lai tạo đơn giản là các sự kết hợp giữa 2 chromosome cũ với nhau đến một lúc nào đó sẽ bị bão hòa và không thể tạo ra phần tử mới nữa. Lúc này đòi hỏi phải có một phẩn tử hoàn toàn mới để cung cấp sự đa dạng cho quần thể. Sự biến dị sẽ tạo nên cá thể mới so với quần thể, đảm bảo tính đa dạng cho quần thể. Sự biến dị không phải lúc nào cũng xảy ra mà chỉ xảy ra ở một tỷ lệ nhất định.

Bài toán sinh chuỗi “to be or not to be”.

  • Trạng thái mục tiêu chính là chuỗi “to be or not to be”.
  • Các trạng thái là các chuỗi được sinh ngẫu nhiên có cùng độ dài. Mỗi chuỗi này biểu diễn cho một chromosome bao gồm các gene nối tiếp nhau, mỗi gene là một ký tự. Sự lai tạo có thể được hình dung như sau:

    Nếu việc lai tạo được thực hiện ở chính giữa chuỗi, ta có cá thể mới sinh ra bằng cách lấy nửa đầu chuỗi 1 ghép với nửa sau chuỗi 2 để có: “ABCEDD”.
  • Sự biến dị thực chất chỉ là việc thay đổi một số gene trong chuỗi được sinh ra. Ví dụ ký tự đầu của chromosome “ABCEDD” bị biến dị thành “ABCEFD”.
  • Fitness của một trạng thái có thể được định nghĩa là số lượng các ký tự giống với trạng thái mục tiêu

Thuật toán

  • Khởi tạo quần thể ngẫu nhiên
  • Lặp:

    • Tính fitness cho mỗi cá thể so với mục tiêu
    • Lựa chọn ngẫu nhiên 2 cá thể theo quy luật chọn lọc tự nhiên. Ở đây, sau khi update fitness cho từng cá thể, ta tạo ra một mating pool để lấy 2 phần tử sao ngẫu nhiên từ pool này cho cá thể mạnh hơn có cơ hội được chọn lựa cao hơn.
      Ví dụ:
      Có 5 cá thể A,B,C,D,E lần lượt có fitness như sau: 1, 3, 2, 0, 4.
      Như vậy mating pool như sau: A, B, B, B, C, C, E, E, E, E.
      Rõ ràng nếu ta lấy ngẫu nhiên 1 phần tử trong pool này, tỷ lệ chọn ra E sẽ là cao nhất.
    • Thực hiện lai ghép để tạo ra cá thể mới
    • Thay thế cá thể cũ bằng cá thể mới tạo ra
    • Nếu cá thể mới giống với mục tiêu hoặc giống ở mức chấp nhận được thì dừng. Ở đây, rất có thể chúng ta không tìm được kết quả tối ưu hoặc sẽ rất lâu mới tìm thấy trạng thái này, như vậy ta có quyền dừng ở trạng thái chấp nhận được để tiết kiệm thời gian.

Thiết kế thuật toán:


Như vậy, ta cần định nghĩa thêm một class DNA để đại diện cho một cá thể trong quần thể:

Các bạn có thể tham khảo toàn bộ code ở đây

No Comments

Post A Comment