Xuyên không tôi tham gia Tam pháp thuật bằng Genetic Algorithms

1. Giả định về bối cảnh

Giả sử bạn được xuyên không và trở thành một pháp sư như Harry Potter và các phép thần chú bạn được học sẽ có thể kết hợp với nhau để ra một thần chú mạnh hơn. Tất nhiên sau khi sử dụng phép thuật bạn sẽ tốn mana và tối đa thần chú được dùng là 6.

Chúng ta sẽ dựa trên cấu trúc phát triển như sau:

(Nguồn: AI Vietnam)

Và bạn có kí ức đã được học kiến thức về Genetic Algorithms ở tiền kiếp, mục tiêu của bạn là tìm ra 6 phép thuật cơ bản để gây ra sát thương thần chú lớn nhất khi gặp đối thủ, chúng ta giả định rằng tất cả 6 đơn vị Mana của bạn đều phải được sử dụng một cách hoàn hảo để đạt hiệu quả tối đa.

2. Thần chú Genetic Algorithm

Để bắt đầu niệm chú, chúng ta hãy quy đổi qua cấu trúc của Genetic Algorithm và nhờ Nagini 3 để mô phỏng:

Giá trị Gen:

• 1 : Phép thuật có thể gây sát thương ở vị trí này. Phép thuật này kết hợp hoàn hảo với các phép thuật “1” khác và góp phần gây sát thương.

• 0: Phép thuật không có tác dụng gây sát thương. Phép thuật không kết hợp được, làm lãng phí mana

2.1 Khởi tạo quần thể ban đầu

Với n = 6 và m =6, chúng ta tạo ra một chuỗi thần chú gồm 6 câu mà mỗi câu 6 gene được sinh ra ngẫu nhiên với giá trị nhị nguyên. Ví dụ minh họa của sát thương thần chú:

2.2 Thần chú tiến hóa

1. Fitness Evaluation:

Trong bài toán này, hàm đánh giá sức manh của thần chú là tổng các câu có sát thương trong chuỗi các câu thần chú, như công thức sau:

$$fitness(v) = \sum_{v} v_i $$

Trong đó $v$ là số thần chú có gây ra sát thương.

Như trong bối cảnh chúng ta ở phép thuật, ví dụ các chuỗi pháp chú như ở bảng dưới

Với công thức fitness đánh gia sát thương của bùa chú, chúng ta sẽ xét từng thần chú như sau:

• Thần chú 1: [0, 0, 0, 0, 0, 0] ⇒ fitness = 0 + 0 + 0 + 0 + 0 + 0 = 0

• Thần chú 2: [0, 1, 0, 0, 0, 0] ⇒ fitness = 0 + 1 + 0 + 0 + 0 + 0 = 1

• Thần chú 3: [1, 1, 1, 0, 0, 0] ⇒ fitness = 1 + 1 + 1 + 0 + 0 + 0 = 3

• Thần chú 4: [0, 1, 1, 1, 0, 1] ⇒ fitness = 0 + 1 + 1 + 1 + 0 + 1 = 4

• Thần chú 5: [1, 0, 1, 1, 1, 1] ⇒ fitness = 1 + 0 + 1 + 1 + 1 + 1 = 5

• Thần chú 6: [1, 1, 0, 1, 1, 1] ⇒ fitness = 1 + 1 + 0 + 1 + 1 + 1 = 5

2. Selection
Đây sẽ là bước chọn lọc giữ lại các combo lệnh chú có sát thương cao để sử dụng trong cuộc đấu. Việc chọn lọc sẽ được thực hiện dựa trên giá trị fitness như đề cập ở trên.

Chúng ta sẽ so sánh thần chú 5 với các thần chí còn lại

Trong ví dụ này, số lượng câu thần chú gây sát thương cao elitism =2, do đó, hai thần chú được giữ lại nguyên vẹn, gồm:

• Thần chú 5: [1, 0, 1, 1, 1, 1] ⇒ finess = 1 + 0 + 1 + 1 + 1 + 1 = 5

• Thần chú 6: [1, 1, 0, 1, 1, 1] ⇒ finess = 1 + 1 + 0 + 1 + 1 + 1 = 5

Sau đó, ta tiếp tục chọn ngẫu nhiên các cặp cá thể để so sánh. Nhìn vào danh sách, Thần chú 5 (Fitness = 5) và Thần chú 6 (Fitness = 5) rõ ràng là những ứng cử viên sáng giá nhất. Chúng là những công thức phép thuật mạnh nhất bạn đang có, chỉ còn thiếu một chút nữa là đạt đến sự hoàn hảo.

Chúng ta sẽ chọn 2 cá thể này làm "cha mẹ" để lai ghép.

• Cha: [1, 0, 1, 1, 1, 1] (TC5)

• Mẹ: [1, 1, 0, 1, 1, 1] (TC6)

3. Crossover

Với xác suất 0.9, mỗi gene của thần chú mới sinh ra sẽ được hoán đổi với gene tương ứng của cha/mẹ. Do tất cả giá trị ngẫu nhiên đều nhỏ hơn 0.9, toàn bộ gene giữa hai cá thể cha mẹ được hoán đổi. Tuy nhiên, trong trường hợp đặc biệt này, khi tất cả các gene bị hoán đổi, quá trình lai ghép chỉ dẫn đến việc hoán đổi vị trí của hai câu thần chú.

Kết quả là, hai cá thể con mới không tạo ra bất kỳ cải tiến nào về Fitness (sát thương) so với thế hệ cha mẹ, cả hai đều có sát thương là 5.

Chính vì thế, chúng ta sẽ giảm tỉ lệ lai ghép $p_{cross}$ xuống 0.6 chúng ta sẽ có thần chú mới như sau:

• Tạo Con 1 (Chủ yếu từ Cha, Hoán đổi lấy từ Mẹ)

1. Selection: Đây sẽ là bước chọn lọc giữ lại các combo lệnh chú có sát thương cao để sử dụng trong cuộc đấu. Việc chọn lọc sẽ được thực hiện dựa trên giá trị fitness.

Trong ví dụ này, số lượng câu thần chú gây sát thương cao elitism =2, do đó, hai thần chú được giữ lại nguyên vẹn, gồm:

• Thần chú 5: [1, 0, 1, 1, 1, 1] ⇒ finess = 1 + 0 + 1 + 1 + 1 + 1 = 5

• Thần chú 6: [1, 1, 0, 1, 1, 1] ⇒ finess = 1 + 1 + 0 + 1 + 1 + 1 = 5

Sau đó, ta tiếp tục chọn ngẫu nhiên các cặp cá thể để so sánh. Nhìn vào danh sách, Thần chú 5 (Fitness = 5) và Thần chú 6 (Fitness = 5) rõ ràng là những ứng cử viên sáng giá nhất. Chúng là những công thức phép thuật mạnh nhất bạn đang có, chỉ còn thiếu một chút nữa là đạt đến sự hoàn hảo.

Chúng ta sẽ chọn 2 cá thể này làm "cha mẹ" để lai ghép.

• Cha: [1, 0, 1, 1, 1, 1] (TC5)

• Mẹ: [1, 1, 0, 1, 1, 1] (TC6)

Với xác suất 0.9, mỗi gene của thần chú mới sinh ra sẽ được hoán đổi với gene tương ứng của cha/mẹ. Do tất cả giá trị ngẫu nhiên đều nhỏ hơn 0.9, toàn bộ gene giữa hai cá thể cha mẹ được hoán đổi. Tuy nhiên, trong trường hợp đặc biệt này, khi tất cả các gene bị hoán đổi, quá trình lai ghép chỉ dẫn đến việc hoán đổi vị trí của hai câu thần chú.

Kết quả là, hai cá thể con mới không tạo ra bất kỳ cải tiến nào về Fitness (sát thương) so với thế hệ cha mẹ, cả hai đều có sát thương là 5.

Chính vì thế, chúng ta sẽ giảm tỉ lệ lai ghép $p_{cross}$ xuống 0.6 chúng ta sẽ có thần chú mới như sau:

• Tạo Con 1 (Chủ yếu từ Cha, Hoán đổi lấy từ Mẹ)

Thần chú Con 1: [1, 0, 0, 1, 1, 1]
Fitness (Sát thương) Con 1 : $1 + 0 + 0 + 1 + 1 + 1 = \mathbf{4}$

• Tạo Con 2 (Chủ yếu từ Mẹ, Hoán đổi lấy từ Cha)

Thần chú Con 2: [1, 1, 1, 1, 1, 1]

Fitness (Sát thương) Con 2: 1 + 1 + 1 + 1 + 1 + 1 = 6

Với $P_{swap} = 0.6$, quá trình lai ghép đã thành công trong việc tạo ra giải pháp tối ưu:

Thần chú Con 2: [1, 1, 1, 1, 1, 1] có Fitness = 6.
Việc lai ghép đồng phục (Uniform Crossover) với tỷ lệ hoán đổi không quá cao đã giúp kết hợp các gen mạnh từ cả hai cha mẹ (đặc biệt là khắc phục gene 0 ở vị trí 2 của Cha và gene 0 ở vị trí 3 của Mẹ) để tạo ra tổ hợp hoàn hảo.

Chúc mừng, bạn đã làm một pháp sư tìm ra công thức đại diện đi tham gia Giải đấu Tam Pháp thuật với bí kíp Genetic Algorithm.

Nhưng khoan đã, một pháp sư cẩn trọng không bao giờ bỏ qua bước cuối cùng trong quá trình này. Chúng ta cần đảm bảo thần chú mới này ổn định và sẵn sàng cho thực chiến.

4. Mutation

Trong quá trình khám phá các câu chú thuật, chúng ta sẽ tìm ra các thần chú đột biến. Mục đích của đột biến là để đưa vào những yếu tố ngẫu nhiên mới, giúp chúng ta thoát khỏi các điểm tối ưu cục bộ (local optima). Biết đâu, một sự thay đổi ngẫu nhiên nhỏ lại mở ra một tiềm năng sát thương còn lớn hơn nữa.

Chúng ta đã thiết lập tỉ lệ đột biến $p_{muta} = 0.05$. Điều này có nghĩa là mỗi "gene" (mỗi phần của câu thần chú) trong các cá thể con mới có 5% khả năng bị đảo ngược (từ 1 thành 0, hoặc 0 thành 1).

Hãy xem xét hai thần chú con chúng ta vừa tạo ra:
- Con 1: [1, 0, 0, 1, 1, 1] (Fitness 4)
- Con 2: [1, 1, 1, 1, 1, 1] (Fitness 6)

Nagini 3 sẽ mô phỏng việc "roll" ngẫu nhiên cho từng gene. Chúng ta sẽ đặc biệt chú ý đến Thần chú Con 2, vì nó là giải pháp hoàn hảo của chúng ta.

Niệm chú Đột biến lên Thần chú Con 2: [1, 1, 1, 1, 1, 1]

• Gene 1: $p_{mut\_gen1}$= 0.31 ( > 0.05 -> Không đột biến)
• Gene 2: $p_{mut\_gen2}$ = 0.82 ( > 0.05 -> Không đột biến)
• Gene 3: $p_{mut\_gen3}$= 0.11 ( > 0.05 -> Không đột biến)
• Gene 4: $p_{mut\_gen4}$ = 0.94 ( > 0.05 -> Không đột biến)
• Gene 5: $p_{mut\_gen5}$ = 0.55 ( > 0.05 -> Không đột biến)
• Gene 6: $p_{mut\_gen6}$ = 0.28 ( > 0.05 -> Không đột biến)

Kết quả: Thật may mắn! Không có thần chú nào bị đột biến. Thần chú hoàn hảo của chúng ta vẫn được giữ nguyên.

5. Điều kiện dừng

Đạt mục tiêu (Goal Achieved): Bạn đang tìm kiếm một thần chú sử dụng hoàn hảo 6 mana, nghĩa là một chuỗi `[1, 1, 1, 1, 1, 1] với Fitness = 6.

Kết luận

Đây là góc nhìn của tác giả ví dụ cho thuật toán bằng các liên tưởng để tránh sự lặp lại kiến thức và có góc nhìn khác về thuật toán này. Vậy nên trường hợp sai sót hay khó hiểu thì không thể tránh khỏi, người đọc có thể đóng góp cho tác giả để hoàn thiện hơn trong tương lai.

Những đầu mục mà bài viết áp dụng

• Xác Định Mục Tiêu: Bạn đã xác định chính xác mục tiêu: tìm ra một chuỗi 6 phép thuật (một "cá thể") đạt được sát thương tối đa (Fitness = 6), tương đương với việc sử dụng hoàn hảo 6 đơn vị mana.

• Mô Phỏng Tiến Hóa: Bạn đã áp dụng thành công các bước cốt lõi của Giải thuật Di truyền—từ Khởi tạo quần thể, Đánh giá sức mạnh (Fitness), Lựa chọn tinh hoa (Elitism), cho đến Lai ghép và Đột biến.

• Ra Quyết Định Mấu Chốt: Thành công lớn nhất của bạn nằm ở bước Lai ghép (Crossover). Bạn đã nhạy bén phát hiện ra rằng tỉ lệ lai ghép $p_{cross} = 0.9$ ban đầu không mang lại hiệu quả. Bằng cách điều chỉnh $p_{cross}$ xuống 0.6, bạn đã tạo điều kiện lý tưởng để kết hợp những gen tốt nhất (1) từ cả "Cha" (TC5) và "Mẹ" (TC6), khắc phục hoàn hảo các điểm yếu (0) của cả hai.