🧬 Giải thuật Di truyền (Genetic Algorithm): Tối ưu hóa mô phỏng Tiến hóa

I. Giới thiệu về Giải thuật Di truyền (GA)

Giải thuật Di truyền (Genetic Algorithm - GA) là một phương pháp tìm kiếm và tối ưu hóa dựa trên quần thể, thuộc nhóm các Giải thuật Tiến hóa (Evolutionary Algorithms - EAs). GA lấy cảm hứng từ quá trình tiến hóa tự nhiên và chọn lọc tự nhiên của sinh vật

Nguyên lý cốt lõi
- Giống như các loài sinh vật liên tục tiến hóa để thích nghi với môi trường, GA duy trì một quần thể các nghiệm ứng viên (cá thể), đánh giá độ thích nghi (fitness), và cải thiện chúng qua các thế hệ (generations).
- Mục tiêu là tìm ra cá thể có độ thích nghi cao nhất – nghiệm tối ưu cho bài toán.

Ưu điểm nổi bật
GA là phương pháp không cần gradient (Gradient-free), phù hợp cho các bài toán tối ưu phức tạp mà Gradient Descent (GD) gặp khó khăn, ví dụ khi:
- Hàm mục tiêu không khả vi hoặc nhiễu.
- Hàm mục tiêu chỉ có thể đánh giá như “hộp đen” thông qua mô phỏng hoặc thử nghiệm.
- Không gian tìm kiếm có nhiều cực trị cục bộ (local optima) khiến GD dễ bị mắc kẹt.

GA có khả năng vượt qua các “thung lũng cục bộ” nhờ duy trì sự đa dạng quần thể và đột biến.

II. Các Thành phần Cơ bản của GA

GA hoạt động theo chu trình lặp lại qua các thế hệ.

1. Cá thể (Individual) và Quần thể (Population)

• Cá thể (Individual) / Nhiễm sắc thể (Chromosome): Là một nghiệm ứng viên, biểu diễn bằng chuỗi nhị phân hoặc vector số thực.
• Trong bài toán One-Max, cá thể là chuỗi nhị phân, mỗi bit là một gene.

• Trong bài toán Hồi quy tuyến tính, cá thể là vector số thực $\theta=[w; b]$.

• Quần thể (Population): Tập hợp các cá thể trong một thế hệ.

• Khởi tạo (Initialization): Tạo quần thể ban đầu (thường ngẫu nhiên).

2. Đánh giá Độ thích nghi (Fitness Evaluation)

• Độ thích nghi (Fitness): Đo lường chất lượng của cá thể, mục tiêu là tối đa hóa giá trị fitness.
• Hàm thích nghi (Fitness Function) – $f(x)$: Hàm tính độ thích nghi cho mỗi cá thể.

Ví dụ:
- Trong One-Max, $fitness(v)$ = tổng số bit 1 trong chuỗi $v$.
- Trong Hồi quy tuyến tính, $fitness = \frac{1}{\text{MSE} + \epsilon}$ với $\epsilon$ nhỏ để tránh chia 0.

3. Các Toán tử Di truyền (Genetic Operators)

Các toán tử này thúc đẩy sự tiến hóa giữa các thế hệ:

a. Chọn lọc (Selection)

Chọn cá thể tốt nhất để làm cha mẹ – mô phỏng “survival of the fittest”.
- Tournament Selection: Chọn ngẫu nhiên $k$ cá thể ($k=2$), giữ lại cá thể có fitness cao hơn.
- Proportional Selection (Roulette-Wheel): Xác suất chọn tỉ lệ thuận với fitness.

• Đây là phương pháp chọn lọc theo thể thức đấu loại (Tournament Selection), trong đó:Chọn ngẫu nhiên $k$ cá thể (trong ví dụ này $k=2$) từ quần thể hiện tại.
• Cá thể có Fitness cao nhất trong nhóm được chọn sẽ là người chiến thắng và được đưa vào Selection Pool (Nhóm chọn lọc).
• Quá trình này lặp lại cho đến khi có đủ số lượng cá thể cần thiết trong - Selection Pool để tham gia vào bước Lai ghép (Crossover) và Đột biến (Mutation)1818.

Mục tiêu là chọn ra những cá thể "tinh anh" (Elite) để đảm bảo các đặc điểm tốt được truyền lại cho thế hệ sau.

b. Lai ghép (Crossover)

Kết hợp gene của hai cá thể cha mẹ để tạo ra con mới.
- Uniform Crossover: Tại mỗi gene, chọn gene từ cha hoặc mẹ dựa trên xác suất $p_{cross}=0.5$.

Quan sát hình 6, cách hoạt động của Uniform Crossover diễn ra như sau:

1. Xác định trước một tỉ lệ hoán đổi (ví dụ là 0.5).
2. Với mỗi vị trí trong chuỗi gen: Sinh ra một số ngẫu nhiên trong khoảng [0, 1], và nếu số đó
   nhỏ hơn hoặc bằng tỉ lệ cho trước (theo ví dụ là 0.5) thì thực hiện hoán đổi gene giữa hai cá thể tại vị trí đó.

c. Đột biến (Mutation)

Thay đổi ngẫu nhiên gene với xác suất nhỏ $p_{muta}$ để duy trì đa dạng.

• Bit-flip Mutation: Lật bit (0 ↔ 1) trong bài toán nhị phân.
• Gaussian Mutation: Thêm nhiễu Gaussian $\mathcal{N}(0,\sigma^2)$ trong bài toán số thực.

d. Cá thể Ưu tú (Elitism)

Giữ lại các cá thể tốt nhất từ thế hệ hiện tại để đảm bảo nghiệm tốt không bị mất đi.

4. Điều kiện Dừng (Termination Criteria)

GA dừng khi thỏa mãn một trong các điều kiện sau:
- Đạt số thế hệ tối đa (Max Generations).
- Đạt ngưỡng fitness mong muốn.
- Hội tụ: chất lượng không cải thiện sau nhiều thế hệ.

III. Ứng dụng GA trong Tối ưu hóa: Ví dụ Bài toán One-Max

Tìm chuỗi nhị phân có độ dài $n$ chứa nhiều số 1 nhất.

A. Cấu hình Tham số (Ví dụ)

B. Minh họa quá trình Tiến hóa (Gen 0 → Gen 1)

1. Khởi tạo và Đánh giá

Quần thể ban đầu (Gen 0):

2. Chọn lọc và Lai ghép

• Elitism: Giữ lại 2 cá thể tốt nhất (Fitness = 4).
• Elite 1: [0, 1, 1, 1, 1]
• Elite 2: [1, 1, 0, 1, 1]
• Chọn cặp cha mẹ (ví dụ):
• Parent 1: [1, 1, 0, 1, 1]
• Parent 2: [0, 0, 0, 1, 0]
• Uniform Crossover ($p_{cross}=0.9$)
• Con 1 (trước đột biến): [0, 0, 0, 1, 0]
• Con 2 (trước đột biến): [1, 1, 0, 1, 1]

3. Đột biến (Mutation)

• Áp dụng $p_{muta}=0.05$, không gene nào thay đổi.
• Con 1 (sau đột biến): [0, 0, 0, 1, 0]
• Con 2 (sau đột biến): [1, 1, 0, 1, 1]

4. Quần thể Thế hệ Mới (Gen 1)

• [0, 1, 1, 1, 1] (Elite)
• [1, 1, 0, 1, 1] (Elite)
• [0, 0, 0, 1, 0] (Con 1)
• [1, 1, 0, 1, 1] (Con 2)
• [0, 0, 0, 1, 0] (Thêm)

Quá trình lặp lại qua các thế hệ cho đến khi đạt điều kiện dừng.

C. Kết quả Tiến hóa

Sau 5 thế hệ, cá thể tốt nhất đạt được:
[1, 1, 1, 1, 1] với fitness = 5.

IV. Mở rộng Ứng dụng GA trong Học máy (Machine Learning)

GA có thể áp dụng vào nhiều bài toán tối ưu trong học máy, nơi hàm mục tiêu phức tạp và không khả vi:

Lưu ý:
Trong các bài toán tối ưu hóa số thực (như hồi quy tuyến tính hoặc tinh chỉnh siêu tham số), sử dụng Gaussian Mutation thay cho Bit-flip và áp dụng Uniform Crossover trên các tham số thực.

Tóm tắt

Giải thuật Di truyền (Genetic Algorithm - GA) là phương pháp tìm kiếm và tối ưu hóa mô phỏng theo quá trình tiến hóa tự nhiên.
- Nguyên lý: Dựa trên chọn lọc tự nhiên, lai ghép (crossover) và đột biến (mutation) để tạo ra thế hệ cá thể tốt hơn.
- Cơ chế hoạt động:
1. Khởi tạo quần thể ngẫu nhiên
2. Đánh giá độ thích nghi (fitness)
3. Chọn lọc các cá thể tốt
4. Lai ghép và đột biến để tạo thế hệ mới
5. Lặp lại đến khi đạt tiêu chí dừng

Mục tiêu: Tìm ra “cá thể có độ thích nghi cao nhất”, tương ứng với nghiệm tối ưu cho bài toán.

Refernces

[1] Ảnh được lấy từ tài liệu khóa học AIO Module 05 Tuần 03