1. Giới thiệu

Trong lĩnh vực tối ưu hóa và học máy, việc tìm kiếm giải pháp tối ưu cho các bài toán phức tạp luôn là một thách thức lớn. Giải thuật di truyền (Genetic Algorithm) là một trong những phương pháp mạnh mẽ được phát triển dựa trên nguyên lý tiến hóa tự nhiên, giúp giải quyết các vấn đề tối ưu hóa mà các phương pháp truyền thống khó có thể tiếp cận. Bằng cách mô phỏng quá trình chọn lọc tự nhiên, lai ghép và đột biến, giải thuật di truyền không chỉ tìm kiếm giải pháp tối ưu mà còn duy trì sự đa dạng trong quần thể giải pháp, giúp tránh tình trạng mắc kẹt ở các cực trị cục bộ.

2. Cơ sở lý thuyết

2.1. Khái niệm

Giải thuật di truyền mô phỏng quá trình tiến hóa tự nhiên để tìm kiếm giải pháp tối ưu. Các cá thể trong quần thể được đánh giá qua độ thích nghi (fitness) và các cá thể mạnh nhất sẽ được lựa chọn để tạo ra thế hệ mới. Quá trình này diễn ra qua ba bước chính: Khởi tạo quần thể, Đánh giá độ thích nghi, và Áp dụng các thuật toán di truyền (chọn lọc, lai ghép, đột biến). Trong đó:

• Selection (Chọn lọc): Quá trình chọn lọc xác định cá thể nào trong quần thể sẽ được chọn để sinh sản. Các cá thể tốt hơn (có fitness cao hơn) sẽ có nhiều cơ hội được chọn. Các phương pháp chọn lọc phổ biến bao gồm chọn lọc theo tỷ lệ (Roulette Wheel Selection) và chọn lọc theo giải đấu (Tournament Selection).

• Crossover (Lai ghép): Lai ghép là quá trình kết hợp thông tin từ hai cá thể cha mẹ để tạo ra một hoặc nhiều cá thể con. Mục tiêu của lai ghép là kết hợp những đặc điểm tốt của các cá thể cha mẹ để tạo ra các cá thể con có khả năng tối ưu hóa cao hơn. Tỷ lệ lai ghép cao cho phép quần thể nhanh chóng truyền tải thông tin tốt từ các cá thể tốt. Các phương pháp lai ghép thường gặp là lai ghép một điểm (One-point Crossover), lai ghép hai điểm (Two-point Crossover), và lai ghép đồng nhất (Uniform Crossover). Trong đó, tại công thức cho phép lai ghép một điểm, $P_1$ và $P_2$ là các cá thể cha mẹ, $C_1$ và $C_2$ là các cá thể con, và $k$ là điểm cắt:

• Mutation (Đột biến): Đột biến là quá trình thay đổi ngẫu nhiên một hoặc nhiều gen trong cá thể con sau khi lai ghép. Đột biến giúp duy trì sự đa dạng di truyền trong quần thể và giúp thuật toán tránh bị mắc kẹt trong cực trị địa phương. Tỷ lệ đột biến thường rất nhỏ để tránh làm biến dạng quá mức các cá thể tốt trong quần thể. Trong đó, tại công thức đột biến, $P$ là cá thể ban đầu, $\delta$ là vector đột biến ngẫu nhiên, và $\oplus$ là phép toán XOR:

Quá trình tiến hóa qua các thế hệ sẽ tiếp tục cho đến khi thỏa mãn một trong các điều kiện dừng sau:

• Đạt số thế hệ tối đa.
• Đạt giá trị fitness đủ cao (giải pháp tối ưu).
• Không có sự cải thiện về fitness qua nhiều thế hệ.

2.2. Ý tưởng

Giải thuật di truyền hoạt động dựa trên việc mô phỏng quá trình tiến hóa tự nhiên để tìm kiếm giải pháp tối ưu. Một quần thể sinh vật bắt đầu với nhiều cá thể khác nhau, mỗi cá thể có bộ gen riêng. Cá thể nào thích nghi tốt hơn với môi trường thì có khả năng sống sót cao hơn. Các cá thể buộc phải tiến hóa liên tục qua từng thế hệ để thích nghi với môi trường và tồn tại. Giải thuật di truyền là một tìm kiếm ngẫu nhiên (stochastic search) trong không gian giải pháp, nơi các cá thể trong quần thể sẽ thay đổi qua các thế hệ để tìm ra giải pháp tốt nhất.

3. Thực hiện thuật toán

3.1. Mô tả bài toán

Mục đích: Tìm tổ hợp máy hoạt động tối ưu trong một ca sản xuất sao cho đảm bảo các ràng buộc về công suất, máy xung đột và máy cần bảo trì.

Yêu cầu bài toán: Có NUM_MACHINES máy trong hệ thống. Mỗi máy có công suất tiêu thụ riêng POWER[i]. Mỗi máy có thể ở 2 trạng thái: 1: máy được bật hoạt động; 0: máy tắt. Cần thỏa mãn các ràng buộc sau:

• Giới hạn công suất tổng

• Xung đột máy móc

  • Một số cặp máy không thể cùng bật trong ca đó (ví dụ: dùng chung nguồn, hoặc khu vực chồng chéo).

  • Nếu (i, j) là một cặp xung đột → STATE[i] và STATE[j] không được đồng thời bằng 1.

• Máy bảo trì: Các máy nằm trong danh sách MAINTENANCE phải luôn tắt (STATE[i] = 0).

Ta bắt đầu định nghĩa tham số bài toán trước khi thực hiện thuật toán di truyền

import numpy as np
import random

# --- Cấu hình bài toán ---
NUM_MACHINES = 40
POWER = np.random.randint(10, 30, size=NUM_MACHINES)
POWER_LIMIT = 250

# 15 cặp xung đột (cho phép máy xuất hiện ở nhiều cặp)
conflict_indices = np.random.choice(range(NUM_MACHINES), size=30, replace=True).reshape(15, 2).tolist()
CONFLICT_PAIRS = [tuple(pair) for pair in conflict_indices]

# 8 máy đang bảo trì
MAINTENANCE = set(np.random.choice(range(NUM_MACHINES), size=8, replace=False))

# --- Tham số Giải Thuật Di Truyền (GA) ---
POP_SIZE = 100          # kích thước quần thể
ELITE_SIZE = 1          # số cá thể tinh hoa được giữ nguyên
CROSSOVER_PROB = 0.9    # xác suất lai ghép
MUTATION_PROB = 5.0 / NUM_MACHINES  # xác suất đột biến
GENERATIONS = 400       # số thế hệ tiến hóa

3.2. Các bước thực hiện

3.2.1. Biểu diễn và khởi tạo quần thể

Mỗi cá thể (individual) là chuỗi nhị phân độ dài NUM_MACHINES (1=bật, 0=tắt).

Khởi tạo POP_SIZE cá thể ngẫu nhiên để tạo quần thể (population) ban đầu.

def random_individual(n):
    """Tạo một cá thể ngẫu nhiên với n gene nhị phân"""
    return np.random.randint(0, 2, size=n, dtype=np.int8)

# Khởi tạo quần thể
POP_SIZE = 100
pop = [random_individual(NUM_MACHINES) for _ in range(POP_SIZE)]

# Ví dụ một cá thể với NUM_MACHINES = 40
ind = random_individual(NUM_MACHINES)
print(ind)
# Output: [1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 1 1 0 0 1 1 1 1]

3.2.2. Đánh giá độ thích nghi

Trong các bài toán thực tế, không phải mọi cá thể sinh ra đều thỏa mãn ràng buộc. Giải thuật di truyền cần cơ chế để đảm bảo việc đánh giá fitness hợp lý. Có hai hướng xử lý phổ biến:

• Penalty (Phạt): Giữ nguyên cá thể vi phạm, nhưng giảm giá trị fitness theo mức độ vi phạm. Điều này giúp thám hiểm xung quanh các nghiệm vi phạm, tránh kẹt ở điểm cục trị cục bộ. Ví dụ, nếu cá thể vượt công suất 20 đơn vị và hệ số phạt λ = 0.1, tức trừ 2 điểm fitness.

• Repair (Sửa nghiệm): Trước khi đánh giá fitness, sửa cá thể để khớp với các ràng buộc.

  • Tắt máy bảo trì: Với các máy trong MAINTENANCE, luôn đặt bit = 0.

  • Giải quyết xung đột: Với mỗi cặp trong CONFLICT_PAIRS, nếu cả hai đều bật, ta tắt ngẫu nhiên một máy trong cặp.

  • Giới hạn công suất: Nếu tổng công suất vượt POWER_LIMIT, ta tắt các máy đang bật theo thứ tự công suất giảm dần và tiếp tục cho đến khi tổng công suất nằm trong giới hạn.

def fitness_and_repaired(ind):
    """
    Repair cá thể và tính fitness.
    Returns: (fitness_score, repaired_individual)
    """
    ind = ind.copy()

    # Repair 1: Tắt các máy bảo trì
    for i in MAINTENANCE:
        ind[i] = 0

    # Repair 2: Giải quyết xung đột
    for a, b in CONFLICT_PAIRS:
        if ind[a] == 1 and ind[b] == 1:
            if random.random() < 0.5:
                ind[a] = 0
            else:
                ind[b] = 0

    # Repair 3: Giới hạn công suất
    total = (ind * POWER).sum()
    if total > POWER_LIMIT:
        active = np.where(ind == 1)[0]
        # Tắt máy theo thứ tự công suất giảm dần
        for idx in sorted(active, key=lambda i: POWER[i], reverse=True):
            ind[idx] = 0
            total -= POWER[idx]
            if total <= POWER_LIMIT:
                break

    # Tính fitness = số máy đang hoạt động
    fitness = int(ind.sum())
    return fitness, ind

3.2.3. Chọn lọc

Chọn ra những cá thể tốt để làm cha mẹ sinh ra thế hệ mới. Để đảm bảo đơn giản, hiệu quả, ta áp dụng kỹ thuật Tournament Selection (k = 3):

• Mỗi lần chọn, ta ngẫu nhiên lấy 3 cá thể từ quần thể hiện tại.
• So sánh fitness của 3 cá thể này.
• Giữ lại cá thể có fitness cao nhất.
• Lặp lại cho đến khi đủ số lượng cá thể cần thiết cho thế hệ mới.

def tournament_selection(pop, fitnesses, k=3):
    """
    Chọn cá thể tốt nhất từ k cá thể ngẫu nhiên.

    Args:
        pop: Quần thể hiện tại
        fitnesses: Mảng fitness tương ứng
        k: Kích thước tournament (mặc định 3)

    Returns:
        Bản copy của cá thể được chọn
    """
    selected = random.sample(range(len(pop)), k)
    best = selected[0]
    for idx in selected[1:]:
        if fitnesses[idx] > fitnesses[best]:
            best = idx
    return pop[best].copy()

3.2.4. Lai ghép

Kết hợp thông tin di truyền từ hai cá thể cha mẹ để tạo ra thế hệ con tiềm năng hơn. Ta áp dụng kỹ thuật Single-point Crossover:

• Chọn ngẫu nhiên một điểm cắt (crossover point) trên chuỗi gene.
• Hoán đổi phần sau điểm cắt giữa 2 cha mẹ.
• Tạo ra 2 cá thể con mới.

Minh họa

Parent 1: [1 1 1 1 | 0 0 0 0]
Parent 2: [0 0 0 0 | 1 1 1 1]
                   ↑ điểm cắt

Child 1:  [1 1 1 1 | 1 1 1 1]
Child 2:  [0 0 0 0 | 0 0 0 0]

def single_point_crossover(a, b):
    """
    Lai ghép một điểm giữa hai cá thể cha mẹ.

    Args:
        a, b: Hai cá thể cha mẹ

    Returns:
        (child1, child2): Hai cá thể con
    """
    cp = random.randrange(1, len(a))  # Điểm cắt từ 1 đến len-1
    child1 = np.concatenate([a[:cp], b[cp:]])
    child2 = np.concatenate([b[:cp], a[cp:]])
    return child1, child2

3.2.5. Đột biến

Đột biến thay đổi ngẫu nhiên một phần nhỏ gene trong cá thể để tạo đa dạng di truyền, giúp quần thể thoát khỏi điểm cực trị cục bộ.

Minh họa

Before: [1 0 1 1 0 1 0 0]
         ↑     ↑       ↑ (đột biến)
After:  [0 0 1 0 0 1 0 1]

def mutate(ind, mut_prob):
    """
    Đột biến bit-flip với xác suất mut_prob.

    Args:
        ind: Cá thể cần đột biến
        mut_prob: Xác suất đột biến mỗi gene

    Returns:
        Cá thể sau khi đột biến
    """
    for i in range(len(ind)):
        if random.random() < mut_prob:
            ind[i] = 1 - ind[i]  # Flip bit
    return ind

Đến đây, ta đã hoàn thành việc tạo ra cá thể con mới. Nếu kích thước quần thể vẫn chưa đủ để tạo thành một thế hệ hoàn chỉnh, ta cần lặp lại các bước trên sao cho thỏa yêu cầu bài toán. Phần thực nghiệm các bước tiến hóa minh họa bên dưới.

def run_ga(seed=None):
    """
    Chạy Genetic Algorithm cho bài toán phân công máy.

    Args:
        seed: Random seed để tái tạo kết quả

    Returns:
        Dictionary chứa kết quả và lịch sử tiến hóa
    """
    if seed is not None:
        random.seed(seed)
        np.random.seed(seed)

    # Khởi tạo quần thể
    pop = [random_individual(NUM_MACHINES) for _ in range(POP_SIZE)]

    best_history = []
    mean_history = []

    for gen in range(GENERATIONS):
        # Đánh giá quần thể (repair + fitness)
        repaired_pop = []
        fitnesses = []
        for ind in pop:
            fit, rep = fitness_and_repaired(ind)
            fitnesses.append(fit)
            repaired_pop.append(rep)
        fitnesses = np.array(fitnesses)

        # Lưu thống kê
        best_fit = fitnesses.max()
        mean_fit = fitnesses.mean()
        best_history.append(best_fit)
        mean_history.append(mean_fit)

        # Tìm best solution
        best_idx = np.argmax(fitnesses)
        best_solution = repaired_pop[best_idx]

        # Tạo quần thể mới
        sorted_idx = np.argsort(-fitnesses)
        new_pop = []

        # Elitism: Giữ elite tốt nhất
        for i in range(ELITE_SIZE):
            new_pop.append(repaired_pop[int(sorted_idx[i])].copy())

        # Sinh phần còn lại
        while len(new_pop) < POP_SIZE:
            # Selection
            p1 = tournament_selection(pop, fitnesses, k=3)
            p2 = tournament_selection(pop, fitnesses, k=3)

            # Crossover
            if random.random() < CROSSOVER_PROB:
                c1, c2 = single_point_crossover(p1, p2)
            else:
                c1, c2 = p1.copy(), p2.copy()

            # Mutation
            new_pop.append(mutate(c1, MUTATION_PROB))
            if len(new_pop) < POP_SIZE:
                new_pop.append(mutate(c2, MUTATION_PROB))

        pop = new_pop  # Cập nhật quần thể

    # Trả về kết quả
    return {
        'best_fit': best_fit,
        'best_solution': best_solution,
        'power_used': int((best_solution * POWER).sum()),
        'best_history': best_history,
        'mean_history': mean_history
    }

3.3. Kết quả đạt được

• Độ thích nghi tốt nhất (Best Fitness)

  • Giá trị độ thích nghi tốt nhất mà thuật toán đạt được là 16.0 máy.
  • Kết quả tối ưu này được tìm thấy rất sớm, vào khoảng thế hệ thứ 10, và được duy trì ổn định trong suốt 390 thế hệ còn lại mà không có sự thay đổi.

• Độ thích nghi trung bình (Mean Fitness)

  • Độ thích nghi trung bình của quần thể tăng mạnh từ khoảng 12.5 lên đến xấp xỉ 14.5 trong 20-30 thế hệ đầu tiên.
  • Sau đó, giá trị này dao động ổn định quanh mức 14.2 đến 14.6 cho đến thế hệ cuối cùng.

• Khoảng cách Best-Mean

  • Khoảng cách giữa Best Fitness và Mean Fitness: ~1.5-1.8 máy
  • Khoảng cách này cho biết mức độ đa dạng di truyền còn lại trong quần thể.

3.4. Hạn chế và hướng phát triển

3.4.1. Hạn chế

• Hội tụ sớm (Premature Convergence): Việc đường "Best Fitness" đạt đến giá trị cực đại và không thay đổi trong một khoảng thời gian dài (từ thế hệ 10 đến 400) là một dấu hiệu của sự hội tụ sớm. Có khả năng thuật toán đã bị mắc kẹt tại một điểm cực trị cục bộ.

• Thiếu đa dạng di truyền: Khoảng cách tương đối lớn và không được thu hẹp giữa "Best Fitness" (16.0) và "Mean Fitness" (14.4) cho thấy sự đa dạng trong quần thể có thể đã giảm sút.

3.4.2. Hướng phát triển

• Khởi tạo lại một phần quần thể (Partial Re-initialization): Trong kết quả hiện tại, độ thích nghi tốt nhất (Best Fitness) đạt mức tối đa 16.Giá trị 0 ngay ở thế hệ thứ 10 và không thay đổi trong suốt 390 thế hệ tiếp theo. Điều này cho thấy thuật toán đã hội tụ sớm và không còn tạo ra các nghiệm mới tốt hơn. Việc thay thế ngẫu nhiên một phần quần thể yếu nhất giúp tăng đa dạng di truyền, tránh quần thể bị mắc kẹt tại cực trị cục bộ và giữ lại các cá thể tốt nhất, đảm bảo không mất đi lời giải tốt hiện tại.

• Tỷ lệ đột biến thích ứng (Adaptive Mutation Rate): Quan sát biểu đồ fitness cho thấy sau khi đạt đỉnh ở thế hệ thứ 10, các thế hệ sau không còn cải thiện. Đây là dấu hiệu của việc quần thể bị thiếu biến dị — tức là mutation rate cố định không đủ mạnh để tạo ra khác biệt. Tỷ lệ đột biến thích ứng cho phép thuật toán tự điều chỉnh khả năng tìm kiếm nghiệm mới (exploration) và cải thiện nghiệm hiện có (exploitation):

  • Khi đa dạng thấp, cần tăng tỷ lệ đột biến để sinh ra nhiều biến thể mới, giúp quần thể thoát khỏi cực trị cục bộ.
  • Khi đa dạng cao, nên giảm tỷ lệ đột biến để duy trì sự ổn định và khai thác vùng nghiệm tốt hiện tại.