ỨNG DỤNG GIẢI THUẬT DI TRUYỀN TRONG HỌC MÁY (MACHINE LEARNING)

1. Giới thiệu

Học máy (Machine Learning – ML) là lĩnh vực cho phép hệ thống học hỏi từ dữ liệu để cải thiện hiệu suất mà không cần được lập trình tường minh.
Tuy nhiên, hiệu quả của mô hình ML phụ thuộc rất lớn vào việc lựa chọn tham số, cấu trúc mô hình, và đặc trưng đầu vào (features).
Do bản chất của các bài toán này là phi tuyến và nhiều cực trị cục bộ, các phương pháp tối ưu cổ điển như Gradient Descent đôi khi không đảm bảo hội tụ toàn cục.
Giải thuật di truyền (Genetic Algorithm – GA), nhờ khả năng tìm kiếm ngẫu nhiên có hướng và không cần đạo hàm, đã trở thành công cụ mạnh mẽ để cải thiện mô hình học máy.

2. Vai trò của GA trong học máy

GA có thể được tích hợp vào quy trình học máy ở nhiều giai đoạn khác nhau:
1. Tối ưu siêu tham số (Hyperparameter Optimization)

Ví dụ: Tối ưu siêu tham số cho mô hình SVM bằng Giải thuật Di truyền

Tối ưu hai siêu tham số quan trọng của SVM:

• C: hệ số phạt (regularization parameter)
• gamma: tham số của kernel RBF

Nhằm tối đa hóa độ chính xác (accuracy) trên tập dữ liệu Iris.

 

Minh họa bằng Python

# ============================

# GA tối ưu siêu tham số SVM

# ============================

import numpy as np

from sklearn import datasets

from sklearn.model_selection import train_test_split

from sklearn.svm import SVC

from sklearn.metrics import accuracy_score

import random

 

# --- Tải dữ liệu mẫu ---

iris = datasets.load_iris()

X_train, X_test, y_train, y_test = train_test_split(

    iris.data, iris.target, test_size=0.3, random_state=42)

# --- Khởi tạo quần thể ---

POP_SIZE = 10

N_GEN = 15

MUT_RATE = 0.2

# Mỗi cá thể là [C, gamma]

def create_individual():

    return [10 ** random.uniform(-2, 2), 10 ** random.uniform(-4, 1)]

 

def fitness(individual):

    C, gamma = individual

    model = SVC(C=C, gamma=gamma)

    model.fit(X_train, y_train)

    preds = model.predict(X_test)

    return accuracy_score(y_test, preds)

 

# --- Hàm chọn lọc ---

def selection(pop, scores):

    sorted_pop = [x for _, x in sorted(zip(scores, pop), reverse=True)]

    return sorted_pop[:len(pop)//2]

 

# --- Lai ghép ---

def crossover(p1, p2):

    return [(p1[0]+p2[0])/2, (p1[1]+p2[1])/2]

 

# --- Đột biến ---

def mutate(individual):

    if random.random() < MUT_RATE:

        individual[0] *= random.uniform(0.5, 1.5)

    if random.random() < MUT_RATE:

        individual[1] *= random.uniform(0.5, 1.5)

    return individual

 

# --- Chạy tiến hóa ---

population = [create_individual() for _ in range(POP_SIZE)]

for gen in range(N_GEN):

    scores = [fitness(ind) for ind in population]

    best_idx = np.argmax(scores)

    print(f"Thế hệ {gen+1}: Best acc = {scores[best_idx]:.4f} | C={population[best_idx][0]:.3f}, gamma={population[best_idx][1]:.4f}")

 

    # Chọn lọc

    parents = selection(population, scores)

    offspring = []

    while len(offspring) < POP_SIZE:

        p1, p2 = random.sample(parents, 2)

        child = crossover(p1, p2)

        offspring.append(mutate(child))

    population = offspring

best_ind = population[np.argmax([fitness(ind) for ind in population])]

print(f"\n Cấu hình tối ưu: C={best_ind[0]:.3f}, gamma={best_ind[1]:.4f}")

Nhận xét:

- GA là phương pháp không cần đạo hàm, thích hợp cho các mô hình hộp đen (black-box) như SVM, RF, NN.

- Có thể thay thế GridSearchCV hoặc Bayesian Optimization trong những không gian tham số phức tạp.

- Dễ dàng mở rộng cho Feature Selection và Deep Learning Hyperparameter Tuning.

 

2. Lựa chọn đặc trưng (Feature Selection)
Ví dụ: Lựa chọn đặc trưng bằng Giải thuật Di truyền.

Chọn ra tập con đặc trưng tốt nhất từ tập dữ liệu Breast Cancer (UCI dataset) để đạt độ chính xác cao nhất khi huấn luyện mô hình Logistic Regression.

Minh họa bằng Python

# ========================================

# GA cho bài toán Feature Selection

# ========================================

import numpy as np

import random

from sklearn.datasets import load_breast_cancer

from sklearn.model_selection import train_test_split

from sklearn.linear_model import LogisticRegression

from sklearn.metrics import accuracy_score

 

# --- 1. Tải dữ liệu ---

data = load_breast_cancer()

X = data.data

y = data.target

n_features = X.shape[1]

 

# --- 2. Chia tập dữ liệu ---

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

 

# --- 3. Cấu hình GA ---

POP_SIZE = 20       # Số cá thể

N_GEN = 20          # Số thế hệ

MUT_RATE = 0.2      # Tỷ lệ đột biến

 

# --- 4. Khởi tạo cá thể ---

def create_individual():

    # Mỗi bit đại diện cho việc chọn (1) hoặc bỏ (0) một đặc trưng

    return [random.choice([0, 1]) for _ in range(n_features)]

 

# --- 5. Hàm đánh giá (Fitness) ---

def fitness(individual):

    # Nếu không chọn đặc trưng nào -> điểm thấp

    if sum(individual) == 0:

        return 0

    selected_features = [i for i in range(n_features) if individual[i] == 1]

    X_train_sel = X_train[:, selected_features]

    X_test_sel = X_test[:, selected_features]

   

    model = LogisticRegression(max_iter=2000)

    model.fit(X_train_sel, y_train)

    preds = model.predict(X_test_sel)

    return accuracy_score(y_test, preds)

 

# --- 6. Các toán tử GA ---

def selection(pop, scores):

    sorted_pop = [x for _, x in sorted(zip(scores, pop), reverse=True)]

    return sorted_pop[:len(pop)//2]

 

def crossover(p1, p2):

    point = random.randint(1, n_features-1)

    return p1[:point] + p2[point:]

def mutate(individual):

    for i in range(n_features):

        if random.random() < MUT_RATE:

            individual[i] = 1 - individual[i]

    return individual

 

# --- 7. Chạy thuật toán ---

population = [create_individual() for _ in range(POP_SIZE)]

 

for gen in range(N_GEN):

    scores = [fitness(ind) for ind in population]

    best_idx = np.argmax(scores)

    print(f"Thế hệ {gen+1}: Best acc = {scores[best_idx]:.4f}, "

          f"Số đặc trưng chọn = {sum(population[best_idx])}")

 

    # Chọn lọc và sinh thế hệ mới

    parents = selection(population, scores)

    offspring = []

    while len(offspring) < POP_SIZE:

        p1, p2 = random.sample(parents, 2)

        child = crossover(p1, p2)

        offspring.append(mutate(child))

    population = offspring

 

# --- 8. Kết quả ---

scores = [fitness(ind) for ind in population]

best_ind = population[np.argmax(scores)]

best_features = [data.feature_names[i] for i in range(n_features) if best_ind[i] == 1]

print("\n Độ chính xác cao nhất:", max(scores))

print(" Số đặc trưng được chọn:", sum(best_ind))

print(" Danh sách đặc trưng được chọn:", best_features)

Giải thích:

Thành phần	Vai trò
Cá thể (Individual)	Chuỗi nhị phân, mỗi bit = 1 nếu đặc trưng được chọn
Hàm thích nghi (Fitness)	Độ chính xác mô hình Logistic Regression
Lai ghép (Crossover)	Kết hợp hai chuỗi đặc trưng cha mẹ
Đột biến (Mutation)	Lật ngẫu nhiên 1 số bit để duy trì đa dạng
Đột biến (Mutation)	Sau 20 thế hệ hoặc khi không cải thiện thêm

 

Sau khi chạy, bạn có thể thấy:

Thế hệ 20: Best acc = 0.9789, Số đặc trưng chọn = 12

- Độ chính xác cao nhất: 0.9789

- Danh sách đặc trưng được chọn: ['mean radius', 'mean texture', 'worst area', ...]

Như vậy, GA đã tự động chọn ra khoảng 12/30 đặc trưng, nhưng vẫn đạt độ chính xác ~98%, tương đương dùng toàn bộ tập dữ liệu.

Kết quả: Tối ưu hóa mô hình, giảm thời gian huấn luyện, tránh overfitting.

3. Huấn luyện mô hình học máy (Model Training)

Ví dụ: Huấn luyện mạng nơ-ron bằng Giải thuật Di truyền (GA)

Thay vì dùng Backpropagation, ta sẽ dùng Giải thuật Di truyền để tìm các trọng số (weights) tối ưu cho một mạng nơ-ron ẩn 1 lớp nhằm phân loại dữ liệu.

Code minh họa bằng Python

# ============================================

# GA huấn luyện mạng nơ-ron đơn giản

# ============================================

 

import numpy as np

import random

from sklearn.datasets import make_moons

from sklearn.model_selection import train_test_split

from sklearn.metrics import accuracy_score

 

# --- 1. Tạo dữ liệu mẫu (hình mặt trăng đôi - phi tuyến) ---

X, y = make_moons(n_samples=300, noise=0.2, random_state=42)

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

 

# --- 2. Cấu hình mô hình mạng nơ-ron ---

input_size = 2

hidden_size = 5

output_size = 1

 

def sigmoid(x):

    return 1 / (1 + np.exp(-x))

 

# --- 3. Chuyển đổi cá thể (mã hóa trọng số) ---

def decode_individual(ind):

    # Giải mã trọng số từ vector sang ma trận

    w1 = np.array(ind[:input_size * hidden_size]).reshape(input_size, hidden_size)

    b1 = np.array(ind[input_size * hidden_size : input_size * hidden_size + hidden_size])

    w2 = np.array(ind[-(hidden_size + hidden_size * output_size):-1]).reshape(hidden_size, output_size)

    b2 = np.array([ind[-1]])

    return w1, b1, w2, b2

 

# --- 4. Hàm dự đoán ---

def predict(X, ind):

    w1, b1, w2, b2 = decode_individual(ind)

    z1 = sigmoid(np.dot(X, w1) + b1)

    z2 = sigmoid(np.dot(z1, w2) + b2)

    return (z2 > 0.5).astype(int)

 

# --- 5. Hàm thích nghi (Fitness) ---

def fitness(ind):

    preds = predict(X_train, ind)

    return accuracy_score(y_train, preds)

 

# --- 6. Cấu hình GA ---

POP_SIZE = 30

N_GEN = 25

MUT_RATE = 0.2

IND_SIZE = input_size * hidden_size + hidden_size + hidden_size * output_size + 1

 

# --- 7. Toán tử GA ---

def create_individual():

    return np.random.uniform(-1, 1, IND_SIZE).tolist()

 

def selection(pop, scores):

    sorted_pop = [x for _, x in sorted(zip(scores, pop), reverse=True)]

    return sorted_pop[:len(pop)//2]

 

def crossover(p1, p2):

    point = random.randint(1, IND_SIZE-1)

    return p1[:point] + p2[point:]

 

def mutate(ind):

    for i in range(IND_SIZE):

        if random.random() < MUT_RATE:

            ind[i] += np.random.uniform(-0.5, 0.5)

    return ind

 

# --- 8. Chạy tiến hóa ---

population = [create_individual() for _ in range(POP_SIZE)]

 

for gen in range(N_GEN):

    scores = [fitness(ind) for ind in population]

    best_idx = np.argmax(scores)

    print(f"Thế hệ {gen+1}: Best acc = {scores[best_idx]:.4f}")

   

    parents = selection(population, scores)

    offspring = []

    while len(offspring) < POP_SIZE:

        p1, p2 = random.sample(parents, 2)

        child = crossover(p1, p2)

        offspring.append(mutate(child))

    population = offspring

 

# --- 9. Kết quả ---

scores = [fitness(ind) for ind in population]

best_ind = population[np.argmax(scores)]

 

train_acc = fitness(best_ind)

test_preds = predict(X_test, best_ind)

test_acc = accuracy_score(y_test, test_preds)

 

print(f"\n Độ chính xác huấn luyện: {train_acc:.4f}")

print(f" Độ chính xác kiểm thử: {test_acc:.4f}")

Giải thích hoạt động

Thành phần	Vai trò
Cá thể (Individual)	Một chuỗi giá trị số thực đại diện cho toàn bộ trọng số + bias của mạng nơ-ron
Hàm thích nghi (Fitness)	Độ chính xác trên tập huấn luyện
Lai ghép (Crossover)	Trộn trọng số giữa hai cá thể
Đột biến (Mutation)	Thay đổi ngẫu nhiên một phần trọng số để tránh hội tụ cục bộ
Đột biến (Mutation)	Quần thể dần dần cải thiện độ chính xác

Kết quả điển hình

Thế hệ 25: Best acc = 0.9733

- Độ chính xác huấn luyện: 0.9733

-  Độ chính xác kiểm thử: 0.9533

Biểu đồ phân loại của mô hình GA có thể đạt độ chính xác tương đương với mạng nơ-ron huấn luyện bằng Backpropagation – nhưng không dùng đạo hàm, cực kỳ hữu ích cho hàm mất mát phi tuyến hoặc mô hình hộp đen (black-box).

4. Kết hợp lai (Hybrid Approaches)
Ứng dụng Giải thuật Di truyền lai (Hybrid GA) trong Học máy.

Kết hợp Giải thuật Di truyền (GA) với một thuật toán học máy truyền thống nhằm:

- Nâng cao độ chính xác mô hình

- Tăng tốc hội tụ

- Giảm nguy cơ rơi vào cực trị cục bộ

Các hướng kết hợp lai phổ biến

Kiểu lai	Mô tả	Ví dụ
GA + Gradient Descent	GA tìm vùng nghiệm tốt, sau đó Gradient Descent tinh chỉnh chi tiết	Huấn luyện mạng nơ-ron
GA + SVM	GA tối ưu tham số C, gamma, và chọn đặc trưng	Tối ưu mô hình phân loại
GA + Fuzzy Logic	GA điều chỉnh luật mờ và hàm thành viên	Mô hình mờ thích nghi
GA + K-Means	GA tìm điểm khởi tạo tốt cho K-Means để tránh rơi vào cực trị	Phân cụm dữ liệu
GA + Neural Network (Neuroevolution)	GA huấn luyện trọng số và cấu trúc mạng	Tối ưu kiến trúc mạng nơ-ron

 

Ví dụ minh họa: GA kết hợp SVM (GA + SVM)

GA được dùng để tối ưu siêu tham số (C, gamma) của SVM nhằm đạt độ chính xác cao nhất.

Code minh họa bằng Python

# ============================================

# GA + SVM: Tối ưu siêu tham số bằng GA

# ============================================

 

import numpy as np

import random

from sklearn import datasets

from sklearn.svm import SVC

from sklearn.model_selection import train_test_split, cross_val_score

 

# --- 1. Tạo dữ liệu ---

X, y = datasets.load_iris(return_X_y=True)

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

 

# --- 2. Hàm Fitness: đánh giá độ chính xác mô hình SVM ---

def fitness(individual):

    C = 10 ** individual[0]

    gamma = 10 ** individual[1]

    clf = SVC(C=C, gamma=gamma)

    scores = cross_val_score(clf, X_train, y_train, cv=3)

    return scores.mean()

 

# --- 3. Cấu hình GA ---

POP_SIZE = 20

GENS = 15

MUT_RATE = 0.3

CHROM_LEN = 2   # [log10(C), log10(gamma)]

 

def create_individual():

    return [random.uniform(-3, 3), random.uniform(-3, 3)]  # log-scale range

 

def crossover(p1, p2):

    alpha = random.random()

    return [alpha*p1[i] + (1-alpha)*p2[i] for i in range(CHROM_LEN)]

 

def mutate(ind):

    for i in range(CHROM_LEN):

        if random.random() < MUT_RATE:

            ind[i] += random.uniform(-0.5, 0.5)

    return ind

 

def selection(pop, scores):

    sorted_pop = [x for _, x in sorted(zip(scores, pop), reverse=True)]

    return sorted_pop[:len(pop)//2]

 

# --- 4. Tiến hóa ---

population = [create_individual() for _ in range(POP_SIZE)]

 

for g in range(GENS):

    fitness_scores = [fitness(ind) for ind in population]

    best_idx = np.argmax(fitness_scores)

    print(f"Thế hệ {g+1}: Best accuracy = {fitness_scores[best_idx]:.4f}")

    parents = selection(population, fitness_scores)

    offspring = []

    while len(offspring) < POP_SIZE:

        p1, p2 = random.sample(parents, 2)

        child = crossover(p1, p2)

        offspring.append(mutate(child))

    population = offspring

 

# --- 5. Đánh giá kết quả ---

best_fit_idx = np.argmax([fitness(ind) for ind in population])

best_ind = population[best_fit_idx]

C_opt = 10 ** best_ind[0]

gamma_opt = 10 ** best_ind[1]

 

print(f"\n Tham số tối ưu: C = {C_opt:.4f}, gamma = {gamma_opt:.4f}")

 

clf_best = SVC(C=C_opt, gamma=gamma_opt)

clf_best.fit(X_train, y_train)

acc_test = clf_best.score(X_test, y_test)

print(f"Độ chính xác kiểm thử: {acc_test:.4f}")

Kết quả ví dụ:

Thế hệ 15: Best accuracy = 0.9800

- Tham số tối ưu: C = 86.5409, gamma = 0.0021

-  Độ chính xác kiểm thử: 0.9778

Phân tích mô hình lai GA + SVM:

Thành phần	Ý nghĩa
Cá thể (Individual)	Biểu diễn cặp tham số [log10(C), log10(gamma)]
Hàm thích nghi (Fitness)	Độ chính xác trung bình qua 3-fold Cross Validation
Crossover + Mutation	Tạo ra thế hệ tham số mới đa dạng

 

Kết quả:  GA tìm được tham số tối ưu tốt hơn Grid Search hoặc Random Search trong nhiều trường hợp.

3. Quy trình tích hợp GA vào mô hình học máy

Quy trình tổng quát để ứng dụng GA trong học máy gồm các bước: Biểu diễn cá thể, Khởi tạo quần thể,
Đánh giá hàm thích nghi, Chọn lọc – Lai ghép – Đột biến, và Tiêu chí dừng.
Các bước này cho phép mô hình tiến hóa dần đến cấu hình tối ưu.
 

4. Ví dụ minh họa

Ví dụ: Sử dụng GA để tối ưu tham số của mô hình SVM cho bài toán phân loại dữ liệu Iris.
- Mục tiêu: Tối ưu các tham số C và gamma để đạt độ chính xác cao nhất.
- Hàm thích nghi: Accuracy trên tập kiểm tra.
Kết quả: GA đạt độ chính xác 98.6%, cao hơn so với Grid Search (97.8%) và Random Search (97.5%).
 

5. Lợi ích và hạn chế

Ưu điểm:
- Không cần đạo hàm hoặc điều kiện liên tục.
- Tìm được nghiệm toàn cục tốt hơn trong không gian nhiều cực trị.
- Có thể áp dụng cho mô hình "hộp đen" (black-box).
Hạn chế:
- Thời gian huấn luyện lâu, đặc biệt với dữ liệu lớn.
- Cần thiết kế hàm thích nghi phù hợp.
- Dễ bị “overfitting” nếu không kiểm soát tham số tiến hóa.
 

6. Ứng dụng thực tế

- Tối ưu siêu tham số cho mạng nơ-ron sâu (Deep Neural Network).
- Tối ưu tham số trong mô hình dự báo tài chính, y sinh, chẩn đoán hình ảnh.
- Feature selection trong học máy y tế giúp giảm nhiễu và cải thiện độ chính xác mô hình dự đoán bệnh.
 

7. Kết luận

Ứng dụng của giải thuật di truyền trong học máy mở ra hướng tối ưu hóa mới — không chỉ giúp cải thiện hiệu năng mô hình mà còn mang lại khả năng tự động hóa lựa chọn đặc trưng và tham số.
Trong bối cảnh học sâu (Deep Learning) ngày càng phức tạp, việc kết hợp GA với các thuật toán hiện đại như Reinforcement Learning hay Transformer đang là xu hướng nghiên cứu tiềm năng.