Genetic Algorithm – Bí Quyết Tối Ưu Dựa Trên Quy Luật Tiến Hóa Tự Nhiên

Nhóm: CONQ024
Học viên: Lê Hồ Anh Duy
Lớp: AI Việt Nam – AIO 2025
Ngày: 22/10/2025

1. Evolutionary Algorithms (EA)

Thuật toán tiến hóa (Evolutionary Algorithms – EA) là một nhóm các phương pháp tính toán mô phỏng cơ chế tiến hóa sinh học trong tự nhiên, đặc biệt là chọn lọc tự nhiên (natural selection) và di truyền học (genetics). Mục tiêu của các thuật toán này là tìm ra lời giải tối ưu hoặc gần tối ưu cho các bài toán phức tạp, nơi mà phương pháp truyền thống (ví dụ như đạo hàm, giải tích hay gradient descent) không thể áp dụng hiệu quả.

Khác với những thuật toán xác định (deterministic algorithms), EA dựa trên tính ngẫu nhiên có kiểm soát (stochastic process), kết hợp với cơ chế chọn lọc và thích nghi. Quá trình tiến hóa được mô phỏng thông qua nhiều thế hệ (generations), trong đó các lời giải (gọi là cá thể – individuals) không ngừng được đánh giá, chọn lọc, lai ghép và đột biến, nhằm tạo ra thế hệ mới tốt hơn.

2. Genetic Algorithms (GA)

2.1 Khái niệm

• Genetic Algorithm (GA) — hay Thuật toán di truyền — là một nhánh đặc biệt của các thuật toán tiến hóa (Evolutionary Algorithms – EA).
• GA mô phỏng cơ chế di truyền sinh học và chọn lọc tự nhiên, trong đó các cá thể “tốt hơn” có nhiều khả năng được duy trì và sinh sản, tạo nên thế hệ mới vượt trội hơn.
• Khác với các phương pháp tối ưu truyền thống dựa trên đạo hàm (như gradient descent), GA không cần biết dạng toán học của hàm mục tiêu.
  Thay vào đó, nó chỉ cần một hàm đánh giá (fitness function) để đo “độ tốt” của mỗi lời giải, giúp GA đặc biệt phù hợp cho các bài toán phi tuyến, không khả vi, hoặc có không gian tìm kiếm phức tạp.

2.2 Các thành phần chính

3. Vấn đề mục tiêu tối ưu hóa

GA được dùng để giải các bài toán tối ưu hóa (Optimization Problems), có thể được mô tả như sau:

• Tối đa hóa:
  $$ v^* = \arg\max_{v \in \Omega} g(v) $$
• Hoặc tối thiểu hóa:
  $$ v^* = \arg\min_{v \in \Omega} g(v) $$

Trong đó
$\Omega$: là không gian tìm kiếm
$g(v)$: là hàm fitness.
Với bài toán tối thiểu hóa thường chuyển đổi thành fitness tăng dần, ví dụ:

$$\text{fitness}(v) = \frac{1}{1 + f(v)}$$
$f(v)$: là hàm cần tối thiểu hóa.

4. Chu trình hoạt động (GA workflow)

4.1 Tổng quan

Quá trình hoạt động của một thuật toán di truyền (Genetic Algorithm – GA) được tổ chức như một vòng lặp tiến hóa, trong đó quần thể các lời giải (population) liên tục được đánh giá, chọn lọc, lai ghép và đột biến để tạo ra thế hệ mới ngày càng tốt hơn.
Mục tiêu là tìm ra cá thể có giá trị fitness cao nhất (hoặc thấp nhất) — tức là nghiệm tối ưu cho bài toán đang xét.

4.2 Cụ thể từng giai đoạn của GA

Bước 1: Khởi tạo quần thể (Population Initialization)
Khởi tạo một tập hợp ngẫu nhiên các cá thể, mỗi cá thể đại diện cho một lời giải khả thi của bài toán.

• Kích thước quần thể thường là N, ví dụ 50–200 cá thể tùy độ phức tạp của bài toán.
• Mỗi cá thể được biểu diễn dưới dạng chuỗi gen (chromosome) – có thể là:
• Chuỗi nhị phân (binary): 010101…
• Vector số nguyên hoặc vector thực, tùy bài toán.

Mục đích: tạo ra sự đa dạng ban đầu để khám phá toàn bộ không gian tìm kiếm.

import random
import numpy as np

# ====== HÀM CƠ BẢN ======

# Sinh 1 gene ngẫu nhiên (0 hoặc 1)
def generate_random_value():
    return random.randint(0, 1)

# Tạo 1 cá thể (một chuỗi bit)
def create_individual(size):
    return [generate_random_value() for _ in range(size)]

Bước 2: Đánh giá độ thích nghi (Fitness Evaluation)
Mỗi cá thể được đánh giá bằng hàm fitness (fitness function), thể hiện mức độ phù hợp của lời giải.

• Với bài toán tối đa hóa, cá thể có fitness càng cao càng tốt.
• Với bài toán tối thiểu hóa, fitness có thể được quy đổi ngược lại, ví dụ:

$$\text{fitness}(x) = \frac{1}{1 + f(x)}$$

Giá trị fitness quyết định khả năng được chọn của cá thể trong bước tiếp theo.

Ví dụ:
Nếu đang tìm hàm có giá trị nhỏ nhất, thì cá thể nào cho giá trị f(x) thấp nhất sẽ có fitness cao nhất.

# Hàm fitness cơ bản: tổng số bit 1 (càng nhiều 1 → càng tốt)
def compute_fitness(individual):
    return sum(individual)

# Hàm trap fitness: nếu không toàn 1 thì bị trừ điểm mạnh
def trap_fitness(individual, block_size=5):
    score = 0
    for start in range(0, len(individual), block_size):
        block = individual[start:start + block_size]
        ones = sum(block)
        if ones == block_size:
            # toàn 1 → tốt nhất
            score += block_size            
        else:
            # ngược lại → “rơi bẫy”
            score += block_size - 1 - ones 
    return score

Bước 3: Chọn lọc (Selection / Reproduction)
Chọn ra các cá thể tốt nhất từ quần thể hiện tại để tham gia “sinh sản” — tạo ra thế hệ con.

Các phương pháp chọn lọc phổ biến:
- Roulette Wheel Selection: xác suất chọn tỉ lệ thuận với fitness.
- Tournament Selection: chọn ngẫu nhiên vài cá thể rồi lấy cá thể tốt nhất.
- Rank Selection: sắp xếp cá thể theo thứ hạng fitness rồi chọn theo xác suất giảm dần.

Quá trình này đảm bảo rằng các lời giải tốt có cơ hội phát huy ảnh hưởng, trong khi các lời giải yếu dần bị loại bỏ.

Tương tự trong tự nhiên: cá thể khỏe mạnh hơn có khả năng sinh sản và truyền gen cho thế hệ sau cao hơn.

# Chọn lọc theo tỉ lệ (Roulette Wheel Selection)
def proportional_select(population, fitness_scores):
    total_fitness = sum(fitness_scores)
    if total_fitness == 0:
        return random.choice(population)
    threshold = random.uniform(0, total_fitness)
    cumulative = 0.0
    for ind, fit in zip(population, fitness_scores):
        cumulative += fit
        if cumulative >= threshold:
            return ind
    return population[-1]

Bước 4: Lai ghép (Crossover / Recombination)
Hai hoặc nhiều cá thể cha mẹ được chọn để kết hợp gen tạo ra thế hệ con (offspring).

Crossover giúp tái tổ hợp thông tin di truyền, kết hợp các đặc điểm tốt từ cha mẹ để tạo lời giải mới có tiềm năng tốt hơn.

Một số dạng lai ghép:
- One-point crossover: chọn 1 điểm cắt và trao đổi phần sau giữa 2 cá thể.
- Two-point / n-point crossover: có nhiều điểm cắt hơn.
- Uniform crossover: mỗi gen được chọn ngẫu nhiên từ cha hoặc mẹ.

Ví dụ:
Cha: 101100
Mẹ: 010011
One-point crossover tại vị trí 3 → Con: 101011

# Hàm uniform crossover (Lai ghép đồng nhất: mỗi gene có xác suất rate để hoán đổi giữa 2 cha mẹ)
def uniform_crossover(ind1, ind2, rate):
    c1, c2 = ind1.copy(), ind2.copy()
    for i in range(len(ind1)):
        if random.random() <= rate:
            c1[i], c2[i] = c2[i], c1[i]
    return c1, c2

Bước 5: Đột biến (Mutation)
Một số gen trong cá thể con có thể thay đổi ngẫu nhiên giá trị với xác suất nhỏ (mutation rate, thường 0.01–0.1).

Đột biến giúp:
- Tăng đa dạng di truyền,
- Tránh hội tụ sớm vào nghiệm cục bộ,
- Khám phá các vùng mới trong không gian tìm kiếm.

Tuy nhiên, tỉ lệ đột biến quá cao có thể phá hỏng cấu trúc gen tốt, nên cần được cân bằng hợp lý.

Đột biến không phải sai sót, mà là cách để khám phá những hướng mới trong tìm kiếm.

# Đột biến: lật bit (0 ↔ 1) với xác suất rate
def bitflip_mutation(individual, rate):
    return [1 - bit if random.random() <= rate else bit for bit in individual]

Bước 6: Hình thành thế hệ mới (New Population)
Sau khi crossover và mutation, một quần thể mới được tạo ra.

Có thể áp dụng elitism để giữ lại cá thể tốt nhất từ thế hệ cũ, đảm bảo không mất nghiệm tối ưu.

Thế hệ mới thay thế thế hệ cũ và bắt đầu lại từ bước đánh giá fitness.

# Sinh cá thể mới bằng chọn lọc + lai + đột biến
while len(new_pop) < POP_SIZE:
    p1 = proportional_select(population, fitness_scores)
    p2 = proportional_select(population, fitness_scores)
    c1, c2 = uniform_crossover(p1, p2, CROSS_RATE)
    c1 = bitflip_mutation(c1, MUT_RATE)
    c2 = bitflip_mutation(c2, MUT_RATE)
    new_pop += [c1, c2]

# Cập nhật quần thể cho thế hệ tiếp theo
population = new_pop[:POP_SIZE]

Bước 7: Kiểm tra điều kiện dừng (Convergence Test / Termination)
Thuật toán dừng khi thỏa một trong các điều kiện sau:
- Đạt số vòng lặp tối đa (max generations),
- Fitness không cải thiện đáng kể sau nhiều thế hệ,
- Hoặc đạt ngưỡng mong muốn (ví dụ fitness > 0.99).

Khi đó, cá thể tốt nhất hiện có được xem là nghiệm tối ưu của bài toán.

Tóm tắt: GA tiến hóa một quần thể các lời giải bằng tổ hợp các toán tử selection → crossover → mutation, lặp đến khi đạt điều kiện dừng.

5. So sánh One-Max và Sphere (fittness)

Cả One-Max và Sphere Function đều chứng minh rằng:
Genetic Algorithm có khả năng tự học và tiến hóa mà không cần thông tin đạo hàm hay cấu trúc cụ thể của hàm mục tiêu.
Qua quá trình chọn lọc, lai ghép và đột biến, GA có thể tìm được lời giải tốt dần theo thời gian, bất kể không gian tìm kiếm là rời rạc hay liên tục.
Chính đặc tính này khiến GA trở thành một trong những thuật toán tối ưu hóa mạnh mẽ và linh hoạt nhất trong AI và Khoa học Máy tính.

6. Từ Random Search → Genetic Algorithm (lộ trình tiến hóa tư duy)

6.1 Tư duy tiến hóa của thuật toán tìm kiếm

Trước khi có Genetic Algorithm (GA), người ta thường giải các bài toán tối ưu bằng Random Search — tức là thử ngẫu nhiên nhiều lời giải, chọn ra lời giải có kết quả tốt nhất, rồi dừng lại. Tuy nhiên, phương pháp này rất tốn tài nguyên và thiếu tính học hỏi, vì:
- Mỗi lần thử là độc lập.
- Không có sự kế thừa giữa các thế hệ lời giải.
- Không tận dụng được kinh nghiệm của các lần tìm kiếm trước.

Chính vì vậy, các nhà nghiên cứu đã phát triển một chuỗi cải tiến theo hướng “mô phỏng tiến hóa” — từng bước đưa yếu tố “thông minh” vào quá trình tìm kiếm.
Khi kết hợp đủ các yếu tố, ta có được Genetic Algorithm hoàn chỉnh.

6.2 Các giai đoạn tiến hóa logic

7. Exploration và Exploitation:

• Exploration (Khám phá):
  Khai thác vùng chưa biết trong không gian — thực hiện bằng mutation.
  Là chìa khóa để thoát khỏi "nút thắt" tối ưu cục bộ mà tiến tới tối ưu toàn cục.

• Exploitation (Khai thác):
  Cải thiện lời giải tốt hiện có — thực hiện bằng selection & crossover.
  Cân bằng giữa hai yếu tố này là chìa khóa để GA vừa tìm nhanh vừa tránh kẹt local optima.

Có thể cân bằng giữa Exploration và Exploitation là chìa khóa giúp GA vừa hiệu quả, vừa tránh bị kẹt local optima.

8. So sánh giữa Genetic Algorithm (GA) và các phương pháp tối ưu truyền thống

8.1. Bảng so sánh

8.2. Minh họa: Gradient Descent vs. Genetic Algorithm

Gradient Descent

• Xuất phát từ một điểm duy nhất trong không gian tìm kiếm.
• Di chuyển theo hướng đạo hàm âm của hàm mục tiêu để giảm giá trị.
• Nếu hàm có nhiều cực trị cục bộ → dễ kẹt tại local minimum.
• Nhanh và chính xác khi hàm lồi, trơn (smooth).

Genetic Algorithm

• Không cần đạo hàm — chỉ cần biết lời giải nào tốt hơn.
• Làm việc với cả quần thể lời giải, khám phá nhiều vùng khác nhau cùng lúc.
• Crossover và mutation giúp vượt qua vùng cực trị cục bộ, hướng tới global optimum.
• Dù tốc độ hội tụ chậm hơn, nhưng kết quả ổn định và mạnh mẽ hơn trong bài toán phi tuyến.

8.3. Kết hợp giữa GA và các phương pháp truyền thống

Trong thực tế, nhiều hệ thống hiện đại kết hợp GA với các thuật toán cổ điển để tận dụng ưu điểm của cả hai:

Hybrid GA–Gradient Descent

• GA dùng để tìm điểm khởi tạo tốt,
• Sau đó Gradient Descent tinh chỉnh nghiệm chính xác hơn.

GA + Simulated Annealing / PSO

• GA dùng để khám phá toàn cục,
• Sau đó các thuật toán khác tối ưu cục bộ nhanh hơn.

→ Sự kết hợp này tạo ra mô hình metaheuristic lai (Hybrid Metaheuristics) — xu hướng hiện đại trong tối ưu hóa AI.

Có thể kết luận rằng sự khác biệt căn bản giữa GA và phương pháp tối ưu truyền thống nằm ở tư duy tiếp cận:

9. Công thức tổng quát & mô hình toán học

• Mục tiêu tối ưu:
  $$v^* = \arg\max_{v\in\Omega} g(v)\quad\text{hoặc}\quad v^* = \arg\min_{v\in\Omega} g(v)$$

• Cấu trúc tiến hóa một thế hệ:
  $$P^{(t+1)} = M\big(C\big(S(P^{(t)})\big)\big)$$
  Trong đó:

• $P^{(t)}$: quần thể ở thế hệ (t).
• $S(\cdot)$: selection.
• $C(\cdot)$: crossover.

• $M(\cdot)$: mutation.

• Quy đổi cho bài toán tối thiểu hóa:
  $$\text{fitness}(v)=\dfrac{1}{1+f(v)}$$
  Để fitness tăng khi f giảm.

10. Tổng kết

10.1 Ưu điểm của Genetic Algorithm (GA)

Genetic Algorithm (GA) là một trong những phương pháp tối ưu hóa mạnh mẽ và linh hoạt nhất hiện nay, với các ưu điểm nổi bật:

• Không phụ thuộc vào công thức toán học cụ thể, chỉ cần có tiêu chí đánh giá (fitness function).
• Làm việc tốt với dữ liệu phức tạp, phi tuyến hoặc rời rạc, kể cả các bài toán không khả vi.
• Khả năng tìm kiếm toàn cục (global search), tránh kẹt tại cực trị cục bộ.
• Dễ mở rộng và kết hợp với các lĩnh vực khác như AI, Machine Learning, Robotics, AutoML,...
• Tự nhiên hỗ trợ song song hóa (parallelization) — tận dụng tốt sức mạnh tính toán đa lõi.
• Tính thích nghi cao, mô phỏng đúng bản chất “tiến hóa tự nhiên” – học từ sai lầm và cải thiện qua thế hệ.

10.2 Hạn chế và thách thức của GA

Mặc dù mạnh mẽ, Genetic Algorithm vẫn tồn tại những hạn chế cần cân nhắc:

• Tốc độ hội tụ chậm, cần nhiều thế hệ để đạt kết quả tốt.
• Độ ngẫu nhiên cao → kết quả có thể thay đổi giữa các lần chạy.
• Cần tinh chỉnh tham số (population size, crossover rate, mutation rate) cẩn thận để tránh mất cân bằng giữa exploration và exploitation.
• Không đảm bảo nghiệm tối ưu tuyệt đối, chỉ đảm bảo lời giải “tốt” hoặc “gần tối ưu”.
• Khó áp dụng cho bài toán yêu cầu thời gian thực hoặc độ chính xác tuyệt đối.

10.3 Kết luận

Genetic Algorithm là minh chứng cho sức mạnh của tiến hóa tự nhiên khi được mô phỏng trong khoa học máy tính.
Nó biến quá trình “tìm kiếm ngẫu nhiên” thành một quá trình có tổ chức, có chọn lọc và có trí tuệ, giúp máy tính dần học cách tìm ra lời giải tốt nhất — tương tự như cách loài sinh vật thích nghi để tồn tại.

11. Tài liệu tham khảo

- AIO2025