Cơ bản về Giải thuật di truyền

1. Giải thuật di truyền là gì?

Trên thực tế, trong nhiều bài toán tối ưu, ta không biết rõ công thức hay cách tính đạo hàm của hàm mục tiêu, chỉ biết đầu vào và đầu ra. Khi đó, giải thuật di truyền (Genetic Algorithm) xuất hiện như một cách tiếp cận đầy cảm hứng từ tự nhiên. Thuật toán này mô phỏng quá trình chọn lọc tự nhiên, lai ghép và đột biến, cho phép các lời giải “tiến hoá” qua nhiều thế hệ để tìm ra nghiệm tốt nhất. Một ý tưởng đơn giản nhưng mạnh mẽ, đưa tinh thần của tự nhiên vào thế giới tính toán.

2. Sơ lược về giải thuật di truyền

2.1. Motivation

Về mặt ý tưởng, các nhà khoa học lấy cảm hứng từ quá trình chọn lọc tự nhiên và áp dụng quá trình đó vào bài toán tối ưu trong máy tính.

Về mặt kỹ thuật, giải thuật di truyền ra đời từ nhu cầu tìm nghiệm tối ưu trong những bài toán phức tạp, không thể giải bằng các phương pháp giải tích hay đạo hàm, cụ thể:
- Hàm mục tiêu không khả vi (non-differentiable),
- Không có mô hình toán học rõ ràng, hoặc
- Các phương pháp như Gradient Descent dễ bị “kẹt” ở các cực trị cục bộ.

2.2 History

(Mục này đọc thêm cho vui, bạn có thể skip)
Vào năm 1950, ý tưởng đầu tiên về việc mô phỏng tiến hóa trong máy tính đã được nêu bởi Alan Turing trong bài Computing Machinery and Intelligence, gợi ý rằng máy có thể “học” thông qua quá trình đột biến và chọn lọc. Nhưng mãi đến năm 1975, John Holland tại Đại học Michigan mới được xem là người đặt nền móng chính thức cho Giải thuật Di truyền, với cuốn sách kinh điển “Adaptation in Natural and Artificial Systems”. Qua đó, ông giới thiệu các khái niệm:
- Biểu diễn bằng nhiễm sắc thể (chromosome encoding)

• Chọn lọc, lai ghép, đột biến

• Cơ chế tiến hóa qua thế hệ

3. Chi tiết về giải thuật di truyền

3.1. Một vài thuật ngữ quan trọng

• Encoding: mã hóa đối tượng cần tìm để tối ưu thành dạng dữ liệu mà máy tính hiểu được
• Population: tập hợp các đối tượng là ứng cử viên để tìm lời giải tối ưu
• Fitness function (Objective function): hàm mục tiêu mà ta muốn tối ưu nó
• Các "toán tử" di truyền: giúp quần thể tiến gần hơn tới nghiệm tối ưu
  • Chọn lọc (Selection)
  • Lai ghép (Crossover)
  • Đột biến (Mutation)

3.2. Cách hoạt động

Giải thuật di truyền là một vòng lặp mô phỏng tiến hoá: ta giữ nhiều lời giải (cá thể) cùng tiến hóa qua các thế hệ bằng cách chọn lọc, lai ghép và đột biến. Mục tiêu là ngày càng sinh ra những cá thể “khỏe hơn”, tức có giá trị hàm mục tiêu tốt hơn.

Cụ thể các bước như sau:
Bước 1: Mã hoá (Encoding)

Trước hết, ta phải biểu diễn mỗi lời giải dưới dạng mà máy tính xử lý được.
- Có thể mã nhị phân (chuỗi 0/1), chuỗi số thực,...
- Lưu ý rằng cách mã hoá phải phụ thuộc vào bài toán.

Bước 2: Khởi tạo quần thể (Initialize population)

Tạo ngẫu nhiên $N$ cá thể ban đầu (ví dụ $N \in [50; 200]$).
Mục đích: phủ được nhiều vùng khác nhau của không gian nghiệm để khám phá.

Bước 3: Đánh giá (Fitness evaluation)

Với mỗi cá thể, tính chỉ số fitness để đo độ “tốt” của chính nó (có thể là giá trị hàm cần tối ưu hoặc số nghịch đảo nếu là bài toán minimization). Tất cả các phép chọn, lai, đột biến đều dựa trên giá trị này.

Bước 4: Lựa chọn (Selection)

Chọn cá thể làm cha mẹ (parents) theo xác suất tỷ lệ với fitness hoặc theo tranh đấu:
- Roulette wheel (fitness-proportionate): chọn theo xác suất tương ứng với fitness.

• Tranh đấu(Tournament): rút $k$ (thường là 2) cá thể ngẫu nhiên, chọn tốt nhất.

Mục tiêu: ưu tiên cá thể tốt nhưng vẫn giữ đa dạng.

Bước 5: Lai ghép (Crossover)

Ghép hai (hoặc nhiều) bố mẹ để tạo cá thể con (offspring), kết hợp “gene” của bố mẹ, tương tự như Lựa chọn, ta có nhiều Lai ghép khác nhau:

• 1-point crossover: chia chuỗi tại 1 điểm, hoán đổi phần sau.

• n-point crossover: chia nhiều điểm.

• Uniform crossover: với mỗi gene, chọn từ bố hoặc mẹ theo xác suất.

• Multi-parent: dùng >2 bố mẹ để phối trộn.

Thông thường, tỉ lệ crossover được đặt khá cao, khoảng 0.95.

Bước 6: Đột biến (Mutation)
Sau khi đã tạo ra cá thể con thành công, ta thay đổi một vài gene của con cái với xác suất nhỏ (ví dụ ≤ 0.01–0.05).

Ý nghĩa: mục đích của đột biến là để có thể thêm các gene mới mà các cá thể cha mẹ nói riêng, hoặc cả quần thể nói chung, chưa có, nhằm cải thiện sự đa dạng, tránh kẹt ở cực trị cục bộ.

Lưu ý:
- số lượng cá thể con ở thế hệ mới sẽ được duy trì bằng với thế hệ trước,

Bước 7: Elitism

Elitism, hay dịch là "chủ nghĩa tinh hoa", là một bước rất thú vị và vô cùng quan trọng trong giải thuật di truyền của chúng ta. Cơ chế này hoạt động bằng cách giữ một vài cá thể có fitness cao nhất ở thế hệ trước và tuyển thẳng vào thế hệ sau mà không cần phải đấu tranh sinh tồn gì cả.

Điều này giúp cho các thế hệ sau, về mặt tổng thể, luôn có các gene tốt hơn các thế hệ trước, bảo đảm được sự hội tụ của thuận toán.
Bước 8: Dừng thuật toán (Stopping criteria)

Dừng khi một trong các điều kiện thỏa:
- khi đạt số thế hệ tối đa, hoặc

• chỉ số fitness không cải thiện trong N thế hệ, hoặc

• đạt ngưỡng fitness mong muốn.

Tóm lại, giải thuật di truyền bắt đầu từ việc mã hoá và khởi tạo quần thể ban đầu (B1&2), sau đó lặp lại liên tục các bước đánh giá → chọn lọc → lai ghép → đột biến → (giữ cá thể tinh hoa) (B3-7) để tạo ra thế hệ mới, cho đến khi đạt số thế hệ tối đa hoặc hội tụ theo tiêu chí dừng (B8).

4. Ứng dụng của Giải thuật Di truyền

Một ứng dụng rất hay của giải thuật di truyền mà mình tìm được là AutoML (Automated Machine Learning), nơi mà toàn bộ quá trình xây dựng mô hình ML được tự động hóa, từ data preprocessing đến chọn mô hình và tinh chỉnh tham số. Bản chất của vấn đề là có vô số cách kết hợp các bước này, và việc thử tất cả là bất khả thi. Đây chính là lúc giải thuật di truyền phát huy sức mạnh.

Vậy, Genetic Algorithm trong AutoML hoạt động như thế nào?
Tương tự như đã giới thiệu ở trên, nó bao gồm các bước cơ bản:

Mã hóa

Mỗi cá thể trong quần thể chính là một pipeline học máy hoàn chỉnh bao gồm chuỗi các bước như chuẩn hóa dữ liệu, chọn đặc trưng, chọn mô hình (ví dụ Random Forest, SVM, XGBoost) và bộ siêu tham số (hyperparameters) tương ứng. Chuỗi này được mã hoá giống như một “nhiễm sắc thể”.

# Mỗi pipeline (cá thể) "cơ bản" gồm: scaler, feature selector, model + hyperparameter
import random

scalers = ["none", "standard", "minmax"]
selectors = ["none", "pca", "selectkbest"]
models = [
    {"name": "svm", "C": [0.1, 1, 10]},
    {"name": "random_forest", "n_estimators": [50, 100, 200]},
    {"name": "xgboost", "max_depth": [3, 5, 7]},
]

def random_pipeline():
    model = random.choice(models)
    return {
        "scaler": random.choice(scalers),
        "selector": random.choice(selectors),
        "model": model["name"],
        "param": random.choice(list(model.values())[1])  # chọn ngẫu nhiên 1 hyperparameter
    }

Khởi tạo quần thể

Thuật toán sẽ random nhiều pipeline khác nhau, mỗi pipeline là một ứng viên giải pháp.

# Ta khởi tạo quần thể với 10 pipelines được random 
def initialize_population(size=10):
    return [random_pipeline() for _ in range(size)]

population = initialize_population(10)
print("Initial population:")
for p in population:
    print(p)

Đánh giá

Mỗi pipeline được huấn luyện và kiểm tra trên tập dữ liệu validation. Chỉ số fitness ở đây thường là độ chính xác, F1-score hoặc MSE tùy theo bài toán.

# Giả lập hàm fitness: giá trị ngẫu nhiên 0–1, trong thực tế, bạn sẽ huấn luyện mô hình, dự đoán tập test và đánh giá trên 1 metric nói trên nhé!

def evaluate_fitness(pipeline):
    return random.uniform(0, 1)

def evaluate_population(population):
    return [(p, evaluate_fitness(p)) for p in population]

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

Những pipeline có hiệu suất tốt hơn sẽ được “chọn làm bố mẹ”. Các phần trong cấu trúc pipeline (ví dụ mô hình hoặc bước xử lý dữ liệu) được “lai ghép” để tạo pipeline con, giúp kết hợp các đặc điểm tốt từ cha mẹ.

def select_parents(evaluated_pop, num_parents=4):
    # Chọn ra num_parents pipeline tốt nhất
    evaluated_pop.sort(key=lambda x: x[1], reverse=True)
    return [p[0] for p in evaluated_pop[:num_parents]]

def crossover(parent1, parent2):
    # Lai ghép bằng cách hoán đổi 1–2 gene
    child = parent1.copy()
    for key in child.keys():
        if random.random() < 0.95:
            child[key] = parent2[key]
    return child

Đột biến:

Một số pipeline con sẽ được thay đổi ngẫu nhiên ở vài điểm (chẳng hạn thay thuật toán từ Random Forest sang XGBoost, hoặc thay đổi tham số học). Điều này giúp duy trì sự đa dạng và khám phá những hướng tối ưu mới.

def mutate(pipeline, mutation_rate=0.05):
    if random.random() < mutation_rate:
        pipeline["scaler"] = random.choice(scalers)
    if random.random() < mutation_rate:
        pipeline["selector"] = random.choice(selectors)
    if random.random() < mutation_rate:
        model = random.choice(models)
        pipeline["model"] = model["name"]
        pipeline["param"] = random.choice(list(model.values())[1])
    return pipeline

Lặp qua nhiều thế hệ:

Quá trình đánh giá → chọn lọc → lai ghép → đột biến được lặp lại qua nhiều thế hệ, cho đến khi tìm được pipeline đạt hiệu suất mong muốn hoặc đạt giới hạn số vòng lặp.

def evolve(num_generations=5, population_size=10):
    population = initialize_population(population_size)
    for gen in range(num_generations):
        print(f"\n--- Generation {gen+1} ---")
        evaluated = evaluate_population(population)
        parents = select_parents(evaluated)

        # Tạo thế hệ mới
        next_gen = []
        while len(next_gen) < population_size:
            p1, p2 = random.sample(parents, 2)
            child = crossover(p1, p2)
            child = mutate(child)
            next_gen.append(child)

        population = next_gen

    # Kết quả cuối cùng
    best = max(evaluate_population(population), key=lambda x: x[1])
    print("\nBest pipeline found:", best)
    return best

best_pipeline = evolve()

=> Nhờ cơ chế “tiến hóa” này, AutoML có thể tự động tìm ra cấu trúc pipeline tối ưu, tiết kiệm thời gian và công sức so với việc tinh chỉnh thủ công.

5. Kết luận

Giải thuật di truyền là một ví dụ tuyệt vời cho thấy cách con người học hỏi từ tự nhiên để giải quyết các bài toán phức tạp. Nhờ cơ chế chọn lọc, lai ghép và đột biến, thuật toán này có thể tìm ra lời giải tối ưu ngay cả khi ta không biết rõ công thức hay quy luật bên trong.

Cảm ơn bạn đã dành thời gian để đọc. Hy vọng bài viết giúp bạn hiểu rõ hơn về giải thuật di truyền và có thêm cảm hứng để nghiên cứu sâu hơn các thuật toán tiến hoá.