1. Sơ lược về thuật toán tối ưu

1.1 Khái niệm về thuật toán tối ưu

Thuật toán tối ưu bao gồm các phương pháp tính toán nhằm tìm ra lời giải tốt nhất, trong tập các lời giải có thể xảy ra, theo tiêu chí hoặc hàm mục tiêu được xác định từ trước.

Ví dụ: tìm giá trị nhỏ nhất, lớn nhất của hàm số, tìm đường ngắn nhất đến mục tiêu, tối ưu chi phí, lợi nhuận.

Hàm mục tiêu (objective/fitness function) là hàm cho biết mức độ hiệu quả của một lời giải.

Mục tiêu của của thuật toán tối ưu là tối đa hóa hoặc tối thiểu hóa hàm mục tiêu (objective/fitness function).

Ví dụ:
- Tối đa hóa: lợi nhuận, hiệu suất, độ chính xác,…
- Tối thiểu hóa: chi phí, thời gian, sai số,…

Một bài toán tối ưu gồm 3 thành phần:
- Không gian tìm kiếm (search space): tập các lời giải có thể
- Hàm mục tiêu (objective): quy định mức độ tốt của lời giải
- Ràng buộc (constraints): điều kiện mà lời giải phải thỏa

1.2 Một số ví dụ về thuật toán tối ưu

  • Tối ưu dựa trên đạo hàm: Gradient Descent, Newton's Method
  • Tối ưu dựa trên đồ thị: Dijkstra (tìm đường đi ngắn nhất)
  • Tối ưu học tăng cường (Reinforcement Learning): tối ưu hành động của agent
  • Tối ưu mô hình deep learning: tìm bộ tham số giảm Loss thấp nhất

1.3 Thách thức với thuật toán tối ưu

Trong thực tế, có nhiều thách thức đối với thuật toán tối ưu khiến cho các bài toán rất khó giải, vì:

  • Chỉ có dữ liệu đầu vào - đầu ra: Không biết trước cấu trúc không gian bên trong
  • Không gian tìm kiếm quá lớn: tốn nhiều tài nguyên, dễ bị mắc vào cực trị cục bộ
  • Hàm mục tiêu phức tạp: nhiều đỉnh cục bộ (local optimum), không có đạo hàm, nhiều biến
  • Thiếu thuật toán hiệu quả
  • Yêu cầu thời gian tính toán cao

1.4 Thuật toán tối ưu hộp đen (Black-box optimization)

image.png

Trong nhiều trường hợp thực tế, ta chỉ biết đầu vào - đầu ra, mà không biết công thức hay đạo hàm của hàm tối ưu, không tính được đạo hàm hay không biết rằng phương pháp hiện tại có phù hợp với vấn đề cần giải quyết hay không.

Ví dụ:

  • Tối ưu kiến trúc mạng Neural Network: không có công thức chính xác mô tả kiến trúc → Chỉ số accuracy chỉ có sau khi huấn luyện (train) & test
  • Tối ưu tham số trong mô phỏng vật lý: chỉ biết đầu vào và kết quả mô phỏng

→ Cần những thuật toán chỉ dựa trên việc đánh giá lời giải. Một trong số đó, có thuật toán tối ưu hộp đen (Black-box optimization).

Thuật toán tối ưu hộp đen là tối ưu dựa trên việc đánh giá đầu vào/đầu ra mà không cần tìm hiểu hệ thống hoạt động bên trong.

Giải pháp phổ biến: Thuật toán tiến hóa (Evolutionary Algorithms).

2. Giải thuật tiến hóa

2.1 Khái niệm & Tư tưởng chính

Giải thuật tiến hóa (Evolutionary Algorithms - EA) là nhóm thuật toán tối ưu lấy cảm hứng từ quá trình tiến hóa sinh học như chọn lọc tự nhiên, sinh sản, đột biến.

Đây là nhóm thuật toán mô phỏng cơ chế tiến hóa tự nhiên với ý tưởng cốt lõi là: "Chọn lọc tự nhiên + biến đổi di truyền", trong đó cá thể tốt hơn có cơ hội sinh tồn và truyền lại những đặc tính tốt cho thế hệ sau.

Trong EA, Một lời giải được xem như một cá thể (individual) trong quần thể, trải qua các thế hệ để cải thiện fitness (Fitness là giá trị định lượng, dùng để đánh giá chất lượng của cá thể (lời giải) trong quần thể. Fitness càng cao, cá thể càng tốt và ngược lại).

Thuật toán tiến hóa cũng giúp duy trì tính đa dạng, khắc phục vấn đề kẹt với đỉnh cục bộ (local optimum) như thuật toán tối ưu.

2.2 Quy trình phổ quát của Giải thuật tiến hóa

image 1.png

Chi tiết tiến trình:

  1. Khởi tạo quần thể: Tạo tập cá thể ban đầu
  2. Đánh giá fitness: Đo độ tốt từng cá thể
  3. Chọn lọc: Chọn cá thể tốt (fitness cao) để làm cá thể bố mẹ
  4. Tạo biến thể (variation)
  5. Hình thành thế hệ mới: Từ offspring hoặc/và cá thể cũ
  6. Lặp lại đến khi dừng: Tối đa số thế hệ hoặc đạt ngưỡng tốt nhất

2.3 Phân loại giải thuật tiến hóa

Một số nhánh chính của giải thuật tiến hóa:

  • Genetic Algorithms: mã hóa nhị phân (0-1)
  • Evolution Strategy: biến thực nhiều chiều
  • Genetic Programming: cấu trúc cây (program)
  • Differential Evolution, Particle Swarm Optimization

3. Giải thuật di truyền

3.1 Từ tìm kiếm ngẫu nhiên tới giải thuật di truyền

Trong các bài toán tối ưu phức tạp, việc tìm kiếm lời giải tối ưu bằng phương pháp duyệt toàn bộ (brute force) là gần như bất khả thi khi không gian tìm kiếm quá lớn. Một cách tiếp cận đơn giản hơn là tìm kiếm ngẫu nhiên – ta tạo ra nhiều lời giải ngẫu nhiên, đánh giá chúng, rồi chọn lời giải tốt nhất. Tuy nhiên, phương pháp này thường kém hiệu quả vì không tận dụng được thông tin từ các lời giải đã có để sinh ra lời giải mới tốt hơn.

Đây chính là lý do giải thuật di truyền (Genetic Algorithm – GA) ra đời. Lấy cảm hứng từ quá trình tiến hóa sinh học của Darwin, GA mô phỏng cách mà các cá thể trong tự nhiên tiến hóa qua nhiều thế hệ để thích nghi tốt hơn với môi trường.

Ý tưởng cốt lõi là:

  • Mỗi cá thể đại diện cho một lời giải tiềm năng.
  • Các cá thể "tốt" hơn (tức có độ thích nghi cao) có xác suất được chọn cao hơn để "sinh con".
  • Qua các thao tác lai ghép và đột biến, thế hệ mới được tạo ra với hi vọng chứa nhiều lời giải tốt hơn.

Cứ như vậy, qua nhiều thế hệ, quần thể dần tiến hóa về phía lời giải tối ưu.

3.2 Quy trình tổng quát của giải thuật di truyền

b5825756-8de5-4a0c-81ef-0b4dd7255d9a.png

  1. Khởi tạo quần thể (Initialization): Tạo ra một tập hợp các cá thể ngẫu nhiên (mỗi cá thể là một lời giải có thể).
  2. Đánh giá độ thích nghi (Evaluation): Tính giá trị hàm mục tiêu cho từng cá thể.
  3. Chọn lọc (Selection): Chọn ra những cá thể có độ thích nghi cao để tái sinh.
  4. Lai ghép (Crossover): Kết hợp hai cá thể "cha mẹ" để tạo ra "con" mới.
  5. Đột biến (Mutation): Thay đổi ngẫu nhiên một vài gene để duy trì tính đa dạng.
  6. Thay thế và lặp lại: Tạo thế hệ mới và lặp lại quá trình cho đến khi đạt điều kiện dừng (ví dụ: đạt số thế hệ nhất định hoặc độ thích nghi không còn cải thiện).

4. Các bước của giải thuật di truyền

4.1 Khởi tạo (Initialization)

image 2.png

Ở bước đầu tiên, ta tạo ngẫu nhiên một quần thể ban đầu gồm nhiều cá thể.

Mỗi cá thể thường được biểu diễn dưới dạng chuỗi nhị phân, vector số thực hoặc hoán vị, tùy vào đặc thù bài toán.

Ví dụ:
- Với bài toán tối ưu hàm, mỗi gene có thể là một biến số.
- Với bài toán xếp lịch, mỗi gene có thể đại diện cho một nhiệm vụ hay vị trí.

Kích thước quần thể ảnh hưởng trực tiếp đến hiệu quả:
- Quần thể nhỏ → tốc độ nhanh nhưng dễ kẹt tại cực trị cục bộ.
- Quần thể lớn → tốn thời gian nhưng tăng khả năng tìm được nghiệm tối ưu.

4.2 Đánh giá (Evaluation)

image 3.png

Sau khi khởi tạo, ta tính giá trị độ thích nghi (fitness) cho từng cá thể bằng hàm đánh giá – thường là hàm mục tiêu của bài toán.

Ví dụ:

  • Nếu bài toán cần tối đa hóa lợi nhuận, độ thích nghi có thể chính là giá trị lợi nhuận.
  • Nếu cần tối thiểu hóa chi phí, ta có thể định nghĩa fitness = 1 / chi phí.

Độ thích nghi càng cao → cá thể càng "tốt" → xác suất được chọn càng lớn trong bước chọn lọc.

4.3 Chọn lọc (Selection)

Mục tiêu của chọn lọc là giữ lại những cá thể tốt nhất và tăng cơ hội sinh sản cho chúng.

Một số phương pháp chọn lọc phổ biến:

  • Roulette Wheel Selection (vòng quay may mắn): Xác suất chọn tỉ lệ thuận với độ thích nghi.
  • Tournament Selection: Chọn ngẫu nhiên một nhóm cá thể, cá thể tốt nhất trong nhóm thắng.
  • Rank Selection: Xếp hạng cá thể rồi chọn theo thứ bậc để tránh chênh lệch quá lớn giữa các fitness.

Cơ chế này đảm bảo rằng "gene tốt" có cơ hội được di truyền sang thế hệ sau, giúp quần thể dần tiến hóa.

4.4 Lai ghép (Crossover / Recombination)

Lai ghép là bước kết hợp thông tin di truyền của hai "cha mẹ" để tạo ra "con" mới.

Ví dụ, với chuỗi nhị phân:

  • Cha: 110|011

  • Mẹ: 001|101

    → Con: 110|101

Các kiểu lai ghép thông dụng:

  • One-point crossover: Cắt tại 1 vị trí ngẫu nhiên.
  • Two-point crossover: Cắt tại 2 vị trí.
  • Uniform crossover: Mỗi gene được chọn từ cha hoặc mẹ với xác suất 50%.

Xác suất lai ghép thường được ký hiệu là $P_c$, và thường nằm trong khoảng 0.6 – 0.9.

4.5 Đột biến (Mutation)

Đột biến mô phỏng sự thay đổi ngẫu nhiên trong gene, giúp duy trì tính đa dạng của quần thể và tránh bị kẹt ở cực trị cục bộ.

Ví dụ:

  • Chuỗi trước đột biến: 101011
  • Sau đột biến (lật một bit): 101111

Tỷ lệ đột biến $P_m$ thường nhỏ (khoảng 0.001 – 0.05).

  • Nếu đột biến quá ít → quần thể có thể "thoái hóa";
  • nếu quá nhiều → mất ổn định và phá vỡ cấu trúc tốt.

5. Ví dụ áp dụng giải thuật di truyền

5.1 One-Max Problem

Bài toán

  • Bài toán: Cho chuỗi nhị phân độ dài $n$, hãy tìm chuỗi chứa nhiều bit 1 nhất.
  • Không gian tìm kiếm: $(0,1)^n$ (kích thước $2^n$, tăng theo hàm mũ).
  • Fitness: $F(\mathbf{b}) = \sum_{i=1}^{n} b_i$, càng lớn càng tốt.
  • Mã hoá: trực tiếp bằng chuỗi bit (bitstring).

Ví dụ minh họa: một vòng lặp (n = 8)

Để hiểu rõ cách GA hoạt động, chúng ta sẽ theo dõi chi tiết một vòng lặp hoàn chỉnh với $n=8$ và quần thể $P=4$.

Bước 1: Khởi tạo quần thể

Tạo ngẫu nhiên 4 cá thể (chuỗi bit độ dài 8) và tính fitness của từng cá thể:

Cá thể Bitstring Fitness
A 0 0 1 1 0 1 0 1 4
B 1 1 0 0 1 0 0 1 4
C 1 1 1 0 0 1 0 0 4
D 1 0 1 1 1 0 1 0 5

Cá thể D có fitness cao nhất (5 bit 1), trong khi A, B, C đều có 4 bit 1.

Bước 2: Chọn lọc (Tournament k=2)

Thực hiện chọn lọc bằng phương pháp Tournament với k=2 để chọn ra 2 cá thể cha mẹ:

  • Lần chọn thứ nhất: Chọn ngẫu nhiên 2 cá thể {D, A}
  • So sánh fitness: D (fitness = 5) > A (fitness = 4)

  • Cá thể D thắng, được chọn làm cha

  • Lần chọn thứ hai: Chọn ngẫu nhiên 2 cá thể {C, B}

  • So sánh fitness: C (fitness = 4) = B (fitness = 4)
  • Chọn ngẫu nhiên, giả sử cá thể C thắng, được chọn làm mẹ

Kết quả: Hai cá thể cha mẹ được chọn là D và C.

Bước 3: Lai ghép (1-point crossover)

Thực hiện lai ghép 1 điểm với điểm cắt được chọn ngẫu nhiên sau vị trí thứ 3:

Cha D:  [1 0 1] | [1 1 0 1 0]
Mẹ C:   [1 1 1] | [0 0 1 0 0]
        -------   -----------
        Giữ      Hoán đổi

Sau khi trao đổi phần đuôi (sau dấu |), ta được 2 cá thể con:

  • Con 1: 1 0 1 0 0 1 0 0 (lấy đầu từ D, đuôi từ C) → fitness = 3
  • Con 2: 1 1 1 1 1 0 1 0 (lấy đầu từ C, đuôi từ D) → fitness = 6

Con 2 có fitness tốt hơn cả hai bố mẹ (6 > 5), cho thấy lai ghép đã tạo ra cá thể tốt hơn.

Bước 4: Đột biến

Với xác suất đột biến $p_m \approx 1\%$ (tức khoảng 1/100 bit bị đột biến), giả sử:

  • Con 1 không bị đột biến (giữ nguyên: 1 0 1 0 0 1 0 0)
  • Con 2 bị đột biến tại bit cuối cùng:
  • Trước đột biến: 1 1 1 1 1 0 1 0
  • Sau đột biến: 1 1 1 1 1 0 1 1 (lật bit từ 0 → 1)
  • Fitness tăng từ 6 lên 7

Bước 5: Elitism và hình thành thế hệ mới

Áp dụng Elitism (giữ lại các cá thể tốt nhất):
- Giữ lại cá thể D (fitness = 5) từ thế hệ cũ
- Thêm vào Con 2 sau đột biến (fitness = 7)
- Có thể thêm Con 1 (fitness = 3) hoặc các cá thể khác để đủ kích thước quần thể

Kết quả sau một vòng lặp:
- Fitness tốt nhất tăng từ 5 lên 7 (cải thiện 40%)
- Quần thể đang tiến hóa đúng hướng, tiến gần hơn đến nghiệm tối ưu (chuỗi toàn bit 1)

Lặp lại quá trình

Quá trình này được lặp lại qua nhiều thế hệ. Sau vài thế hệ, thuật toán thường tìm được chuỗi toàn bit 1 (fitness = $n$), tức nghiệm tối ưu toàn cục.

Các siêu tham số khuyến nghị

  • Kích thước quần thể: 30–100 (tùy $n$).
  • Tỉ lệ lai ghép ($p_c$): 0.7–0.95.
  • Tỉ lệ đột biến ($p_m$): $\approx 1/n$ trên từng bit (hoặc 1–2% cho toàn cá thể).
  • Elitism: 1–2 cá thể.
  • Dừng: đạt fitness $= n$ hoặc hết số thế hệ.

Code (Python) — best/avg/worst

1. Import các thư viện cần thiết

import random
import statistics
import matplotlib.pyplot as plt

2. Biểu diễn bài toán One-max và hàm fitness

# One-Max GA (bitstring)
def onemax_fitness(bits):
    return sum(bits)

3. Chọn lọc (selection)

def tournament_select(pop, fits, k=3):
    cand = random.sample(range(len(pop)), k)
    cand.sort(key=lambda i: fits[i], reverse=True)
    return pop[cand[0]]

4. Lai giống (crossover)

def one_point_crossover(p1, p2):
    if len(p1) < 2:
        return p1[:], p2[:]
    cut = random.randint(1, len(p1)-1)
    return p1[:cut] + p2[cut:], p2[:cut] + p1[cut:]

5. Đột biến (mutation)

def bitflip_mutation(bits, pm=0.01):
    return [(b ^ 1) if random.random() < pm else b for b in bits]

6. Thuật toán hoàn chỉnh và visualization

def ga_onemax(n=60, pop_size=60, pc=0.9, pm=None,
              elite_size=2, max_gen=400, seed=42, verbose=True):
    random.seed(seed)
    if pm is None:
        pm = 1.0 / n  # quy tắc cho one-max

    # Khởi tạo
    pop = [[random.randint(0,1) for _ in range(n)] for _ in range(pop_size)]
    best = None; best_fit = float("-inf")
    hist_best, hist_avg, hist_worst = [], [], []

    for gen in range(max_gen):
        fits = [onemax_fitness(ind) for ind in pop]
        b = max(fits); w = min(fits); a = statistics.mean(fits)
        hist_best.append(b); hist_avg.append(a); hist_worst.append(w)

        # Cập nhật best toàn cục
        bi = max(range(pop_size), key=lambda i: fits[i])
        if fits[bi] > best_fit:
            best_fit = fits[bi]; best = pop[bi][:]

        # In tiến độ
        if verbose and (gen % 20 == 0 or b == n):
            print(f"Gen {gen:03d}: best={b}, avg={a:.2f}, worst={w}")

        # Dừng sớm nếu tối ưu
        if b == n:
            break

        # Elitism
        elite_idx = sorted(range(pop_size), key=lambda i: fits[i], reverse=True)[:elite_size]
        new_pop = [pop[i][:] for i in elite_idx]

        # Sinh thế hệ mới
        while len(new_pop) < pop_size:
            p1 = tournament_select(pop, fits, k=3)
            p2 = tournament_select(pop, fits, k=3)
            c1, c2 = p1[:], p2[:]
            if random.random() < pc:
                c1, c2 = one_point_crossover(p1, p2)
            c1 = bitflip_mutation(c1, pm)
            c2 = bitflip_mutation(c2, pm)
            new_pop.extend([c1, c2])

        pop = new_pop[:pop_size]

    # Vẽ đồ thị
    plt.figure(figsize=(7,4.2))
    plt.plot(hist_best, label="Best")
    plt.plot(hist_avg, label="Average")
    plt.plot(hist_worst, label="Worst")
    plt.xlabel("Generation")
    plt.ylabel("Fitness")
    plt.title(f"One-Max (n={n}, pop={pop_size})")
    plt.legend(); plt.grid(True, alpha=0.3)
    plt.tight_layout()
    plt.show()

    return best, best_fit, (hist_best, hist_avg, hist_worst)

7. Chạy thử

if __name__ == "__main__":
    best, best_fit, _ = ga_onemax(n=80, pop_size=60, pc=0.9, elite_size=2, max_gen=400)
    print("Best fitness:", best_fit)
    print("Best individual (first 64 bits):", "".join(map(str, best[:64])), "...")

Output:

Gen 000: best=50, avg=40.43, worst=31
Gen 020: best=73, avg=69.22, worst=66
Gen 033: best=80, avg=77.02, worst=73

Best fitness: 80
Best individual (first 64 bits): 1111111111111111111111111111111111111111111111111111111111111111 ...

Giải thích kết quả:

Kết quả cho thấy thuật toán GA hoạt động rất hiệu quả trên bài toán One-Max:

  • Thế hệ 0: Fitness tốt nhất chỉ đạt 50/80 bit (62.5%), fitness trung bình là 40.43, cho thấy quần thể ban đầu còn khá xa nghiệm tối ưu.
  • Thế hệ 20: Fitness tốt nhất đã tăng lên 73/80 (91.25%), và đặc biệt fitness trung bình cũng đã cải thiện lên 69.22. Điều này chứng tỏ cả quần thể đang tiến hóa tốt, không chỉ một vài cá thể.
  • Thế hệ 33: Thuật toán đã tìm ra nghiệm tối ưu toàn cục với fitness = 80 (chuỗi toàn bit 1). Khoảng cách giữa best và worst chỉ còn 7 bit, cho thấy toàn bộ quần thể đã hội tụ về vùng nghiệm tốt.

Thuật toán chỉ cần 33 thế hệ để đạt nghiệm tối ưu cho bài toán với $n=80$, trong khi không gian tìm kiếm có tới $2^{80}$ khả năng. Đây là minh chứng rõ ràng cho hiệu quả của cơ chế chọn lọc, lai ghép và đột biến trong GA.

image 4.png

Đồ thị cho thấy quá trình hội tụ nhanh của thuật toán. Đường "Best" tăng mạnh trong 30 thế hệ đầu, đường "Average" cũng theo sát, chứng tỏ cả quần thể đang cải thiện đồng đều. Khoảng cách giữa best và worst giảm dần theo thời gian, phản ánh sự đồng nhất hóa của quần thể khi tiến gần đến nghiệm tối ưu.

5.2 Tối ưu hồi quy tuyến tính bằng GA

(tìm tham số $(a,b)$ sao cho $y \approx a x + b$ với MSE nhỏ nhất)

Mặc dù hồi quy tuyến tính có nghiệm đóng (Ordinary Least Squares - OLS), ví dụ này minh hoạ cách dùng GA cho biến thực (real-coded GA) — hữu ích khi mô hình phức tạp/phi tuyến/không đạo hàm.

Bài toán

Cho tập dữ liệu $\{(x_i, y_i)\}_{i=1}^n$, tối thiểu hoá:

$$ \text{MSE}(a,b) = \frac{1}{N}\sum_{i=1}^N \big(y_i - (a x_i + b)\big)^2 $$

Đặt fitness để tối đa hoá:

$$ \text{fitness}(a,b) = -\text{MSE}(a,b) $$

Mã hoá & toán tử GA cho biến thực

Thuật toán di truyền với mã hóa thực (Real-coded GA)

  • Cá thể (Individual):
  • Biểu diễn: vector thực $\mathbf{x} = [x_1, x_2, ..., x_n] \in [a, b]^n$
  • Với $x_i$: giá trị gen thứ $i$, $n$: số chiều (số biến)

  • $[a, b]$: miền giá trị của mỗi gen

  • Chọn lọc (Selection):

  • Phương pháp: Tournament selection
  • Quy trình: chọn ngẫu nhiên $k$ cá thể (thường $k=2$ hoặc $3$), cá thể có fitness tốt nhất được chọn làm bố/mẹ

  • Tương tự như bài toán One-Max

  • Lai ghép (Crossover - Real-coded):

  • Phương pháp: Blend/Arithmetic Crossover

$$\mathbf{x}_{\text{con}} = \alpha \cdot \mathbf{x}_{\text{bố}} + (1-\alpha)\cdot \mathbf{x}_{\text{mẹ}}$$

  • Với:
    • $\mathbf{x}_{\text{bố}}, \mathbf{x}_{\text{mẹ}}$: hai vector bố mẹ được chọn
    • $\alpha \sim U(0.3, 0.7)$: hệ số trộn, lấy mẫu từ phân phối đều trong $[0.3, 0.7]$
    • $\mathbf{x}_{\text{con}}$: vector con được tạo ra (kế thừa đặc trưng của cả bố và mẹ)

  • Áp dụng từng thành phần: $x_{\text{con},i} = \alpha \cdot x_{\text{bố},i} + (1-\alpha)\cdot x_{\text{mẹ},i}$

  • Đột biến (Mutation - Gaussian):

$$x'_i = x_i + \mathcal{N}(0, \sigma^2)$$

  • Với:

    • $x_i$: giá trị gen thứ $i$ trước đột biến
    • $\mathcal{N}(0, \sigma^2)$: nhiễu Gaussian có trung bình $0$, phương sai $\sigma^2$
    • pm (probability of mutation): xác suất đột biến mỗi gen (thường $\text{pm} = 1/n$)
    • Mỗi gen có xác suất pm để bị cộng thêm nhiễu

  • Ràng buộc biên (Boundary constraint - Tuỳ chọn):

$$x'_i = \begin{cases} L & \text{nếu } x'_i < L \\ U & \text{nếu } x'_i > U \\ x'_i & \text{nếu } L \leq x'_i \leq U \end{cases}$$

  • Với $[L, U]$: giới hạn cho phép của không gian tìm kiếm
  • Clamp: đưa giá trị vượt biên về biên gần nhất sau đột biến
  • Đảm bảo tất cả cá thể luôn nằm trong miền khả thi

Ghi chú:
- Giá trị $\sigma$ (độ lệch chuẩn) thường giảm dần theo thế hệ để tinh chỉnh tìm kiếm
- Tham số $\alpha$ có thể cố định hoặc lấy mẫu mới mỗi lần lai ghép

Code (Python) — OLS & đồ thị

1. Import thư viện

import random
import math
import statistics
import numpy as np
import matplotlib.pyplot as plt

2. Sinh dữ liệu tuyến tính giả lập: y = a_true*x + b_true + noise

def make_linear_data(n=120, a_true=3.2, b_true=5.0, noise_std=2.0, seed=0):
    rng = random.Random(seed)
    xs = [rng.uniform(-5, 5) for _ in range(n)]
    ys = [a_true*x + b_true + rng.gauss(0, noise_std) for x in xs]
    return np.array(xs, dtype=float), np.array(ys, dtype=float)

3. Tính toán MSE & Fitness

def mse_ab(a, b, xs, ys):
    pred = a*xs + b
    return float(np.mean((ys - pred)**2))

def fitness_ab(ind, xs, ys):
    a, b = ind
    return -mse_ab(a, b, xs, ys)  # tối đa hoá fitness

4. Chọn lọc bằng phương pháp Tournament

def tournament_select_real(pop, fits, k=3):
    cand = random.sample(range(len(pop)), k)
    cand.sort(key=lambda i: fits[i], reverse=True)
    return pop[cand[0]][:]  # copy

5. Lai ghép dạng Uniform

def blend_crossover(p1, p2, alpha=None):
    if alpha is None:
        alpha = random.uniform(0.3, 0.7)
    c1 = [alpha*p1[i] + (1-alpha)*p2[i] for i in range(len(p1))]
    c2 = [alpha*p2[i] + (1-alpha)*p1[i] for i in range(len(p1))]
    return c1, c2

6. Đột biến theo phân phối Gaussian

def gaussian_mutation(ind, pm=0.5, sigma=0.1, bounds=None):
    new = ind[:]
    for i in range(len(new)):
        if random.random() < pm:
            new[i] += random.gauss(0, sigma)
        if bounds is not None:
            lo, hi = bounds[i]
            new[i] = max(lo, min(hi, new[i]))
    return new

7. Triển khai GA với bài toán hồi quy tuyến tính

def ga_linear_regression(xs, ys,
                         pop_size=50, pc=0.9, pm=0.4,
                         sigma=0.15, elite_size=2, max_gen=300,
                         init_range=(-10, 10), bounds=None, seed=1,
                         verbose=True):
    random.seed(seed)

    # Khởi tạo quần thể trong init_range
    pop = [[random.uniform(*init_range), random.uniform(*init_range)]
           for _ in range(pop_size)]

    best = None; best_fit = float("-inf")
    hist_best, hist_avg, hist_worst = [], [], []

    for gen in range(max_gen):
        fits = [fitness_ab(ind, xs, ys) for ind in pop]
        b = max(fits); w = min(fits); a = statistics.mean(fits)
        hist_best.append(b); hist_avg.append(a); hist_worst.append(w)

        # cập nhật best
        bi = max(range(pop_size), key=lambda i: fits[i])
        if fits[bi] > best_fit:
            best_fit = fits[bi]; best = pop[bi][:]

        if verbose and gen % 20 == 0:
            print(f"Gen {gen:03d}: best fitness={b:.4f}  (MSE={-b:.4f})")

        # Elitism
        elite_idx = sorted(range(pop_size), key=lambda i: fits[i], reverse=True)[:elite_size]
        new_pop = [pop[i][:] for i in elite_idx]

        # Sinh thế hệ mới
        while len(new_pop) < pop_size:
            p1 = tournament_select_real(pop, fits, k=3)
            p2 = tournament_select_real(pop, fits, k=3)
            c1, c2 = p1[:], p2[:]
            if random.random() < pc:
                c1, c2 = blend_crossover(p1, p2, alpha=None)
            c1 = gaussian_mutation(c1, pm=pm, sigma=sigma, bounds=bounds)
            c2 = gaussian_mutation(c2, pm=pm, sigma=sigma, bounds=bounds)
            new_pop.extend([c1, c2])

        pop = new_pop[:pop_size]

    a_hat, b_hat = best
    mse_min = -best_fit
    return (a_hat, b_hat), mse_min, (hist_best, hist_avg, hist_worst)

8. Vẽ lịch sử fitness

def plot_fitness_history(hist_best, hist_avg, hist_worst):
    plt.figure(figsize=(7,4.2))
    plt.plot(hist_best, label="Best (=-MSE)")
    plt.plot(hist_avg, label="Average")
    plt.plot(hist_worst, label="Worst")
    plt.xlabel("Generation"); plt.ylabel("Fitness")
    plt.title("GA for Linear Regression (maximize -MSE)")
    plt.legend(); plt.grid(True, alpha=0.3)
    plt.tight_layout(); plt.show()

9. Baseline OLS (nghiệm đóng)

def ols_ab(xs, ys):
    X = np.vstack([xs, np.ones_like(xs)]).T  # [x, 1]
    a_hat, b_hat = np.linalg.lstsq(X, ys, rcond=None)[0]
    mse_hat = float(np.mean((ys - (a_hat*xs + b_hat))**2))
    return (a_hat, b_hat), mse_hat

10. Demo

# Tạo dữ liệu
xs, ys = make_linear_data(n=200, a_true=3.2, b_true=5.0, noise_std=2.0, seed=0)

# GA
(a_ga, b_ga), mse_ga, (hist_best, hist_avg, hist_worst) = ga_linear_regression(
    xs, ys,
    pop_size=60, pc=0.9, pm=0.45, sigma=0.12,
    elite_size=2, max_gen=350, init_range=(-10, 10),
    bounds=None, seed=2, verbose=True
)
print(f"[GA]   a ≈ {a_ga:.3f}, b ≈ {b_ga:.3f}, MSE ≈ {mse_ga:.3f}")

# OLS baseline
(a_ls, b_ls), mse_ls = ols_ab(xs, ys)
print(f"[OLS]  a ≈ {a_ls:.3f}, b ≈ {b_ls:.3f}, MSE ≈ {mse_ls:.3f}")

# Vẽ đồ thị fitness
plot_fitness_history(hist_best, hist_avg, hist_worst)

11. Minh hoạ so sánh giữa GA và baseline (nghiệm đóng)

xs_plot = np.linspace(xs.min(), xs.max(), 200)
y_ga = a_ga*xs_plot + b_ga
y_ls = a_ls*xs_plot + b_ls

plt.figure(figsize=(7,4.2))
plt.scatter(xs, ys, s=12, alpha=0.5, label="Data")
plt.plot(xs_plot, y_ga, label="GA fit", linewidth=2)
plt.plot(xs_plot, y_ls, label="OLS fit", linestyle="--", linewidth=2)
plt.xlabel("x"); plt.ylabel("y")
plt.title("Linear Regression by GA vs OLS")
plt.legend(); plt.grid(True, alpha=0.3)
plt.tight_layout(); plt.show()

Output:

Gen 000: best fitness=-15.2242  (MSE=15.2242)
Gen 020: best fitness=-4.2586  (MSE=4.2586)
Gen 040: best fitness=-4.2586  (MSE=4.2586)
...
Gen 320: best fitness=-4.2586  (MSE=4.2586)
Gen 340: best fitness=-4.2586  (MSE=4.2586)

[GA]   a ≈ 3.112, b ≈ 5.045, MSE ≈ 4.259
[OLS]  a ≈ 3.112, b ≈ 5.045, MSE ≈ 4.259

Giải thích kết quả:

Kết quả cho thấy GA hoạt động rất hiệu quả và có khả năng tìm ra nghiệm gần đúng với phương pháp OLS (nghiệm đóng):

  • Thế hệ 0: MSE ban đầu là 15.22, cho thấy quần thể khởi tạo ngẫu nhiên còn rất xa nghiệm tối ưu.
  • Thế hệ 20: MSE đã giảm xuống còn 4.26, cải thiện đáng kể qua chỉ 20 thế hệ. Điều này chứng tỏ cơ chế chọn lọc và lai ghép đang hoạt động hiệu quả.
  • Từ thế hệ 20-340: MSE ổn định ở mức 4.26, cho thấy thuật toán đã hội tụ về nghiệm tối ưu.

So sánh giữa GA và OLS:
- Tham số $a$: GA tìm được 3.112, OLS cho 3.112 (trùng khớp hoàn toàn)
- Tham số $b$: GA tìm được 5.045, OLS cho 5.045 (trùng khớp hoàn toàn)
- MSE: Cả hai phương pháp đều cho MSE = 4.259

Kết quả này chứng minh rằng GA có thể tìm ra nghiệm chính xác như phương pháp giải tích (OLS), mặc dù GA không sử dụng đạo hàm hay công thức toán học. Điều này đặc biệt hữu ích cho các bài toán phức tạp hơn mà không có nghiệm đóng hoặc không thể tính đạo hàm.

image 5.png

Đồ thị fitness cho thấy quá trình hội tụ nhanh chóng. Đường "Best" giảm mạnh trong 20 thế hệ đầu tiên (từ -15.22 lên -4.26), sau đó ổn định. Đường "Average" và "Worst" cũng theo xu hướng tương tự, chứng tỏ cả quần thể đang tiến hóa đồng đều về vùng nghiệm tối ưu.

image 6.png

Biểu đồ so sánh cho thấy đường hồi quy của GA (đường liền) và OLS (đường gạch) gần như trùng khớp hoàn toàn, khẳng định độ chính xác của GA trong bài toán này. Cả hai đường đều fit tốt với dữ liệu phân tán, phản ánh đúng xu hướng tuyến tính của tập dữ liệu.

Mở rộng

  • Ràng buộc/Phạt (Penalty): nếu $(a,b)$ cần nằm trong một miền xác định, có thể clamp hoặc thêm penalty vào MSE khi vi phạm.
  • Regularization: có thể dùng $\text{MSE} + \lambda(a^2+b^2)$ (ridge-like) ⇒ thay mse_ab.
  • Toán tử lai ghép khác: BLX-α, SBX (simulated binary crossover) cho biến thực.
  • Đa mục tiêu (Multi-objective): cân bằng MSE nhỏ & $|a|,|b|$ nhỏ → NSGA-II (gợi mở).

5.3 Một số lưu ý khi giải các bài toán GA

  • Mã hoá đúng bản chất bài toán.
  • Fitness phản ánh đúng mục tiêu. (nhất quán tối đa hoá/tối thiểu hoá)
  • Đa dạng quần thể đủ tốt. (đặt pm không quá thấp; tournament không quá "hung hãn")
  • Elitism nhỏ để giữ thành quả, không quá lớn để vẫn đa dạng.
  • Theo dõi best/avg/worst và dừng sớm khi không cải thiện.
  • Seed cố định để tái lập kết quả khi viết báo cáo.

6. Ứng dụng và hạn chế của giải thuật di truyền

6.1 Hạn chế và giải pháp

Mặc dù hữu dụng và thú vị, thuật toán di truyền không phải "thuốc tiên" cho mọi vấn đề. Dưới đây là các hạn chế phổ biến của GA trong thực tế:

  • Chi phí tính toán cao: GA cần thực hiện rất nhiều vòng lặp thế hệ, với nhiều cá thể (lời giải) trong mỗi thế hệ. Điều này đồng nghĩa phải đánh giá hàm mục tiêu hàng trăm, hàng ngàn lần. Nếu mỗi lần đánh giá đã chậm (ví dụ phải chạy mô phỏng phức tạp), tổng thời gian chạy GA sẽ cực kỳ lớn.

  • Nguy cơ hội tụ sớm (mắc kẹt cực trị địa phương): Một vấn đề nổi tiếng của GA là dễ hội tụ sớm vào một nhóm giải pháp chưa tối ưu. Khi một số cá thể ban đầu tỏ ra vượt trội, quần thể có xu hướng đồng nhất hóa quanh cá thể đó (do các cá thể yếu bị đào thải hết). Kết quả là đa dạng di truyền giảm mạnh và thuật toán mắc kẹt trong một vùng lời giải cụ thể, không tìm được lời giải tốt hơn ở nơi khác. GA có thể kết thúc với nghiệm cục bộ thay vì nghiệm toàn cục tốt nhất.

Từ đó, ta có kết luận thuật toán di truyền (GA) là một công cụ mạnh mẽ để giải quyết các bài toán tối ưu phức tạp, nhưng không phải lúc nào cũng là lựa chọn tốt nhất. GA phát huy tác dụng khi bài toán không có công thức giải rõ ràng, không thể dùng đạo hàm hay phương pháp tuyến tính, và không yêu cầu đáp số tuyệt đối chính xác.

Giải pháp:

  • Dùng mô hình thay thế (surrogate): Huấn luyện một mô hình nhanh (ví dụ Random Forest/GP) để ước lượng fitness, chỉ gửi một phần nhỏ phương án đi mô phỏng thật.
  • Ghi nhớ kết quả (memoization): Nếu một phương án (hoặc rất gần) đã mô phỏng rồi, tận dụng lại kết quả, tránh chạy lại.
  • Dừng sớm & giữ đa dạng: Dừng khi không cải thiện đáng kể; tránh hội tụ sớm để khỏi phí mô phỏng.

6.2 Ứng dụng thực tế

  • Logistics (tối ưu tuyến giao hàng): GA sắp thứ tự các điểm giao cho từng xe để giảm tổng quãng đường/chi phí và đúng hẹn.
  • Lập lịch (thi, ca máy, dây chuyền): GA phân công người/máy theo ràng buộc để rút ngắn makespan và giảm xung đột lịch.
  • Thiết kế kỹ thuật (cầu, cánh quạt, ăng-ten): GA "tiến hoá" hình dạng/thông số để tối ưu độ bền, khối lượng, băng thông khi mô phỏng đắt.

Kết luận: "Giải thuật di truyền không chỉ là một công cụ tối ưu — mà là cách chúng ta học hỏi từ tự nhiên để giải quyết những bài toán phức tạp nhất của con người."