Genetic Algorithms (Thuật toán Di truyền – GA)

Phần 1: Dẫn nhập và Nguyên lý Cốt lõi của Thuật toán Di truyền

1.1. Định nghĩa và Nguồn gốc: Từ Thuyết Tiến hóa đến Tối ưu hóa Tính toán

Thuật toán Di truyền (Genetic Algorithm – GA) là một lớp siêu thuật toán (meta-heuristic) tìm kiếm và tối ưu hóa, lấy cảm hứng trực tiếp từ quá trình tiến hóa và chọn lọc tự nhiên của sinh vật. Được phát triển chủ yếu bởi John Holland vào những năm 1970 thông qua công trình "Adaptation in Natural and Artificial Systems", và mở rộng bởi David E. Goldberg, GA mô phỏng các nguyên lý Darwin về sự sống còn của cá thể thích nghi nhất.

GA thuộc nhóm Evolutionary Algorithms (EA) – mô phỏng các cơ chế chọn lọc, lai ghép, và đột biến. Quá trình tiến hóa trong tự nhiên được xem như một thuật toán tìm kiếm song song, trong đó bài toán tương đương với môi trường sinh tồn, lời giải tương đương với nhiễm sắc thể, và fitness function đại diện cho mức độ thích nghi của cá thể. Nhờ trừu tượng hóa sinh học sang tính toán, GA được ứng dụng trong kỹ thuật, tài chính, AI và khoa học dữ liệu.

1.2. Các Thành phần Cơ bản

Population (Quần thể) là tập hợp các lời giải tiềm năng mà thuật toán đang xem xét đồng thời. GA tìm kiếm song song trên nhiều điểm trong không gian lời giải, điều này giúp tránh bị mắc kẹt tại các điểm tối ưu cục bộ.

Individual (Cá thể) đại diện cho một lời giải cụ thể trong quần thể. Mỗi cá thể mang thông tin về một cấu hình có thể của bài toán đang giải quyết.

Chromosome & Gene là cách mã hóa lời giải. Chromosome (nhiễm sắc thể) có thể được biểu diễn bằng chuỗi nhị phân, vector số thực, hoặc cấu trúc cây phức tạp hơn trong Genetic Programming. Mỗi gene là một đơn vị thông tin nhỏ trong chromosome.

Phenotype & Genotype là hai dạng biểu diễn khác nhau của cùng một lời giải. Genotype là dạng mã hóa mà các toán tử GA thao tác trực tiếp, trong khi phenotype là biểu hiện thực tế của lời giải trong bối cảnh bài toán. Chúng ta cần giải mã từ genotype sang phenotype trước khi tính fitness.

Fitness Function là hàm đánh giá độ tốt của mỗi lời giải. Đây là thành phần duy nhất liên kết thuật toán với bài toán cụ thể, và nó quyết định khả năng sinh sản của từng cá thể trong quần thể.

1.3. Chu trình Tiến hóa

Thuật toán Di truyền hoạt động theo một chu trình lặp đi lặp lại qua nhiều thế hệ. Mỗi chu trình bao gồm các bước sau:

Khởi tạo (Initialization) là bước đầu tiên, trong đó chúng ta sinh ngẫu nhiên một quần thể ban đầu. Việc khởi tạo ngẫu nhiên đảm bảo rằng không gian tìm kiếm được khám phá một cách đa dạng ngay từ đầu.

Đánh giá (Evaluation) là quá trình tính toán điểm fitness cho từng cá thể trong quần thể. Bước này cho phép chúng ta so sánh các lời giải với nhau và xác định cá thể nào tốt hơn.

Chọn lọc (Selection) là cơ chế chọn ra các cá thể cha mẹ để tạo thế hệ tiếp theo. Các cá thể có fitness cao hơn sẽ có xác suất được chọn cao hơn, mô phỏng nguyên tắc "survival of the fittest" trong tự nhiên.

Lai ghép (Crossover) kết hợp thông tin di truyền từ hai cá thể cha mẹ để tạo ra cá thể con. Quá trình này cho phép các đặc điểm tốt từ các lời giải khác nhau được kết hợp lại với nhau.

Đột biến (Mutation) thay đổi ngẫu nhiên một số gene trong nhiễm sắc thể. Đây là cơ chế quan trọng để duy trì đa dạng di truyền trong quần thể và tránh hội tụ sớm.

Thay thế (Replacement) là bước mà quần thể con thay thế quần thể cha, tạo thành thế hệ mới. Có nhiều chiến lược thay thế khác nhau, từ thay thế hoàn toàn đến giữ lại một số cá thể tốt nhất từ thế hệ cũ (elitism).

Điều kiện dừng (Termination) xác định khi nào thuật toán sẽ kết thúc. Thông thường chúng ta dừng khi đạt số thế hệ tối đa, hoặc khi fitness không còn cải thiện đáng kể qua nhiều thế hệ.

Bảng 1. So sánh các phương pháp chọn lọc

Phương pháp Mô tả Áp lực chọn lọc Chi phí tính toán Ảnh hưởng đa dạng
Roulette Wheel Xác suất chọn ∝ fitness Thấp–TB Thấp Dễ bị siêu cá thể chi phối
Tournament Chọn nhóm ngẫu nhiên, lấy cá thể tốt nhất TB–Cao TB Giữ đa dạng tốt
Rank Selection Chọn theo thứ hạng thay vì giá trị tuyệt đối TB Cao Duy trì ổn định, ít trôi hội tụ

2. Cơ sở lý thuyết

2.1. Khả năng Tìm kiếm Toàn cục

GA có khả năng tránh mắc kẹt tại các điểm tối ưu cục bộ nhờ vào việc cân bằng giữa exploration (khám phá) và exploitation (khai thác). Đột biến đóng vai trò chính trong exploration, giúp thuật toán khám phá các vùng mới trong không gian tìm kiếm. Trong khi đó, chọn lọc và lai ghép thực hiện exploitation, tập trung vào việc khai thác và cải thiện các lời giải tốt đã tìm được. Sự cân bằng này được điều chỉnh thông qua các tham số như tỉ lệ đột biến và tỉ lệ lai ghép.

2.2. Tính Linh hoạt

Một trong những ưu điểm lớn nhất của GA là tính linh hoạt. GA không yêu cầu đạo hàm, tính liên tục, hay convexity của hàm mục tiêu. Điều duy nhất cần thiết là một hàm đánh giá (fitness function) có khả năng so sánh chất lượng của các lời giải. Điều này cho phép GA áp dụng cho các bài toán mà các phương pháp tối ưu truyền thống không thể giải quyết hiệu quả.

2.3. Tính Bền vững

GA hoạt động ổn định trong môi trường nhiễu vì quyết định dựa trên đánh giá của cả quần thể chứ không chỉ một cá thể đơn lẻ. Nếu một vài cá thể bị đánh giá sai do nhiễu, các cá thể khác vẫn có thể dẫn dắt quần thể về hướng đúng. Tính chất này làm cho GA phù hợp với các bài toán thực tế, nơi mà dữ liệu đầu vào thường có sai số.

2.4. Song song hóa

Các cá thể trong quần thể được đánh giá độc lập với nhau, do đó quá trình tính toán fitness có thể được song song hóa một cách tự nhiên. Điều này cho phép GA tận dụng kiến trúc đa lõi, GPU, hoặc các cụm máy tính hiệu năng cao để tăng tốc đáng kể, đặc biệt khi hàm fitness có chi phí tính toán lớn.

3. Công thức & Lý giải

3.1. Các công thức cơ bản

Xác suất chọn cá thể i trong phương pháp Roulette Wheel Selection được tính theo công thức:

$$ P_i = \frac{f_i}{\sum_j f_j} $$
Trong đó $P_i$ là xác suất cá thể thứ i được chọn, $f_i$ là giá trị fitness của cá thể i, và $\sum_j f_j$ là tổng fitness của toàn bộ quần thể. Công thức này đảm bảo rằng cá thể có fitness cao hơn sẽ chiếm tỷ trọng lớn hơn trên "bánh xe roulette", giống như việc một người có nhiều vé số hơn sẽ có xác suất trúng thưởng cao hơn.*

Công thức này đảm bảo rằng cá thể có fitness cao hơn sẽ có xác suất được chọn cao hơn, tỉ lệ thuận với giá trị fitness của nó so với tổng fitness của toàn quần thể.

Lai ghép một điểm tạo ra hai cá thể con từ hai cha mẹ theo công thức:

$$ O_1 = [P_1(1:k),\, P_2(k+1:n)], \quad O_2 = [P_2(1:k),\, P_1(k+1:n)] $$

Ở đây $k$ là điểm cắt được chọn ngẫu nhiên trong khoảng từ 1 đến $n-1$, $P_1$ và $P_2$ là hai nhiễm sắc thể cha mẹ, còn $O_1$ và $O_2$ là hai nhiễm sắc thể con. Ký hiệu $P_1(1:k)$ nghĩa là lấy các gene từ vị trí 1 đến vị trí k của cha mẹ thứ nhất. Cơ chế này giống như việc ghép nửa đầu của một sợi dây DNA với nửa sau của sợi dây DNA khác, tạo ra hai con lai mang đặc điểm từ cả hai bên cha mẹ.*

Đột biến nhị phân thay đổi giá trị của mỗi gene theo quy tắc:

$$ g'_j = \begin{cases} 1 - g_j, & \text{nếu } rand() < p_m \\ g_j, & \text{ngược lại} \end{cases} $$
Trong đó $g_j$ là giá trị gene thứ j ban đầu (0 hoặc 1), $g'_j$ là giá trị sau khi đột biến, $p_m$ là tỉ lệ đột biến (thường từ 0.01 đến 0.1), và $rand()$ là một số ngẫu nhiên từ 0 đến 1. Nếu số ngẫu nhiên nhỏ hơn $p_m$, gene sẽ bị đảo bit (0 thành 1 hoặc ngược lại theo công thức $1 - g_j$). Đây giống như việc một nucleotide trong DNA bị thay đổi ngẫu nhiên do bức xạ hoặc lỗi sao chép.

Với xác suất p_m (mutation rate), mỗi bit sẽ bị đảo ngược giá trị (0 thành 1 hoặc 1 thành 0). Với xác suất còn lại, bit giữ nguyên giá trị.

Chuyển bài toán minimize thành maximize có thể thực hiện bằng một trong hai cách:

$$ F(C_i) = \frac{1}{1 + f(x)} \quad \text{hoặc} \quad F(C_i) = -f(x) $$
Trong đó $f(x)$ là hàm mục tiêu cần minimize (giá trị càng nhỏ càng tốt), còn $F(C_i)$ là hàm fitness cần maximize (giá trị càng lớn càng tốt). Công thức đầu tiên luôn cho giá trị dương và tránh chia cho 0 bằng cách cộng thêm 1 vào mẫu số - khi $f(x)$ nhỏ thì $F(C_i)$ lớn. Công thức thứ hai đơn giản hơn nhưng tạo ra giá trị âm - khi $f(x)$ nhỏ (tốt) thì $-f(x)$ sẽ lớn (cũng tốt trong nghĩa maximize). Ví dụ: nếu bài toán là tìm đường đi ngắn nhất (minimize khoảng cách), ta có thể dùng fitness là $F = \frac{1}{1 + \text{khoảng cách}}$.*

Cách thứ nhất luôn cho giá trị dương và tránh chia cho 0, trong khi cách thứ hai đơn giản hơn nhưng có thể tạo ra giá trị âm.

Định lý Schema (Holland) mô tả sự phát triển của các schema (mẫu) trong quần thể:

$$ E[m(H, t+1)] \geq \frac{m(H, t) \cdot f(H)}{a_t} \cdot (1 - p) $$

với xác suất phá vỡ schema:

$$ p = \frac{\delta(H)}{l-1}p_c + o(H)p_m $$
Trong đó $m(H,t)$ là số lượng cá thể chứa schema H tại thế hệ t, $E[m(H,t+1)]$ là kỳ vọng số lượng ở thế hệ tiếp theo, $f(H)$ là fitness trung bình của các cá thể chứa schema H, $a_t$ là fitness trung bình của toàn quần thể, $p$ là xác suất schema bị phá vỡ, $\delta(H)$ là khoảng cách giữa gene đầu và cuối của schema (định nghĩa chiều dài), $l$ là tổng chiều dài nhiễm sắc thể, $o(H)$ là số vị trí cố định trong schema (order), $p_c$ và $p_m$ lần lượt là tỉ lệ lai ghép và đột biến. Định lý này giải thích tại sao các schema ngắn (δ nhỏ), có order thấp (o nhỏ) và fitness cao sẽ tăng số lượng theo cấp số nhân qua các thế hệ - chúng ít bị phá vỡ bởi crossover và mutation hơn. Đây là nền tảng lý thuyết giải thích tại sao GA hoạt động hiệu quả: nó không chỉ tìm kiếm các cá thể tốt mà còn tìm kiếm các "khối xây dựng" (building blocks) tốt để lắp ghép thành lời giải tối ưu.

Định lý này giải thích tại sao các schema ngắn, ít bị ảnh hưởng bởi crossover và mutation, có fitness cao sẽ tăng số lượng theo cấp số nhân qua các thế hệ.

3.2. Code mẫu – Python (bài toán One-Max)

Lưu đồ thuật toán GA
Lưu đồ thuật toán Genetic Algorithm (GA) mô tả các bước khởi tạo, chọn lọc, lai ghép, đột biến và điều kiện dừng.

Chúng ta sẽ triển khai thuật toán Di truyền để giải quyết bài toán One-Max, một bài toán đơn giản nhưng minh họa rõ ràng các khái niệm cốt lõi. Bài toán là tìm một chuỗi nhị phân có độ dài n sao cho tổng các bit bằng 1 là lớn nhất.

import random

# Thiết lập các tham số cho thuật toán
POP_SIZE     = 20    # Kích thước quần thể - số lượng cá thể trong mỗi thế hệ
GENES        = 10    # Độ dài nhiễm sắc thể - số lượng gene (bit) trong mỗi cá thể
CROSS_RATE   = 0.8   # Tỉ lệ lai ghép - xác suất hai cha mẹ sẽ lai ghép
MUTATE_RATE  = 0.05  # Tỉ lệ đột biến - xác suất mỗi bit sẽ bị thay đổi
GENERATIONS  = 30    # Số thế hệ tiến hóa - số lần lặp của thuật toán

Các tham số này cần được điều chỉnh cẩn thận. POP_SIZE lớn hơn giúp khám phá rộng hơn nhưng tốn nhiều tài nguyên. CROSS_RATE cao khuyến khích khai thác các lời giải tốt, trong khi MUTATE_RATE cao giúp duy trì đa dạng.

def create_individual():
    # Tạo một cá thể mới với các gene được khởi tạo ngẫu nhiên
    # Mỗi gene là một bit có giá trị 0 hoặc 1
    return [random.randint(0,1) for _ in range(GENES)]

Hàm khởi tạo này tạo ra một chuỗi nhị phân ngẫu nhiên. Ở thế hệ đầu tiên, chúng ta không có thông tin gì về lời giải tốt, nên việc khởi tạo ngẫu nhiên đảm bảo phủ đều không gian tìm kiếm.

def fitness(ind):
    # Đánh giá độ thích nghi của cá thể
    # Trong bài toán One-Max, fitness đơn giản là tổng số bit 1
    return sum(ind)

Hàm fitness này đếm số lượng bit 1 trong chuỗi. Một cá thể có nhiều bit 1 hơn sẽ có fitness cao hơn và được coi là lời giải tốt hơn. Đây là trái tim của thuật toán - hàm này định nghĩa "tốt" nghĩa là gì trong bối cảnh bài toán.

def select(pop):
    # Chọn lọc theo phương pháp Roulette Wheel
    # Cá thể có fitness cao hơn có xác suất được chọn cao hơn

    # Tính tổng fitness của toàn bộ quần thể
    total = sum(fitness(i) for i in pop)

    # Chọn một điểm ngẫu nhiên trên "bánh xe"
    pick  = random.uniform(0, total)

    # Quay bánh xe và tìm cá thể tương ứng
    current = 0
    for i in pop:
        current += fitness(i)
        if current > pick:
            return i

Phương pháp Roulette Wheel Selection hoạt động như việc quay một bánh xe may rủi, trong đó mỗi cá thể được phân bổ một "khu vực" trên bánh xe tỉ lệ với fitness của nó. Chúng ta chọn một điểm ngẫu nhiên và xem nó rơi vào khu vực của cá thể nào. Điều này đảm bảo cá thể tốt hơn có nhiều cơ hội được chọn, nhưng cá thể yếu hơn vẫn có khả năng, giúp duy trì đa dạng di truyền.

def crossover(p1, p2):
    # Lai ghép hai cha mẹ để tạo con
    # Chỉ thực hiện lai ghép với xác suất CROSS_RATE
    if random.random() < CROSS_RATE:
        # Chọn ngẫu nhiên một điểm cắt
        k = random.randint(1, GENES-1)
        # Tạo con bằng cách lấy phần đầu từ p1 và phần sau từ p2
        return p1[:k] + p2[k:]
    # Nếu không lai ghép, trả về cha thứ nhất nguyên vẹn
    return p1

Lai ghép một điểm cắt chuỗi cha mẹ thành hai phần tại một vị trí ngẫu nhiên, sau đó ghép phần đầu của cha thứ nhất với phần sau của cha thứ hai. Việc chỉ thực hiện lai ghép với xác suất CROSS_RATE cho phép một số cá thể tốt được truyền nguyên vẹn sang thế hệ sau, đây là một dạng đơn giản của elitism.

def mutate(ind):
    # Đột biến: thay đổi ngẫu nhiên một số gene
    # Mỗi gene có xác suất MUTATE_RATE bị đảo giá trị
    for j in range(GENES):
        if random.random() < MUTATE_RATE:
            ind[j] = 1 - ind[j]  # Đảo bit: 0 thành 1, 1 thành 0
    return ind

Đột biến là cơ chế quan trọng giúp thuật toán thoát khỏi các điểm tối ưu cục bộ. Mỗi bit có một xác suất nhỏ bị đảo ngược, tạo ra các biến thể mới mà lai ghép đơn thuần không thể tạo ra. Tỉ lệ đột biến thường được đặt thấp để không phá hủy quá nhiều thông tin tốt đã tích lũy.

# Khởi tạo quần thể ban đầu với các cá thể ngẫu nhiên
population = [create_individual() for _ in range(POP_SIZE)]

# Vòng lặp tiến hóa qua các thế hệ
for gen in range(GENERATIONS):
    new_pop = []

    # Tạo quần thể mới bằng cách lặp lại: chọn lọc, lai ghép, đột biến
    for _ in range(POP_SIZE):
        # Chọn hai cha mẹ từ quần thể hiện tại
        p1 = select(population)
        p2 = select(population)

        # Tạo con bằng cách lai ghép và đột biến
        child = mutate(crossover(p1, p2))
        new_pop.append(child)

    # Thay thế quần thể cũ bằng quần thể mới
    population = new_pop

    # Tìm và in ra cá thể tốt nhất trong thế hệ này
    best = max(population, key=fitness)
    print(f"Gen {gen+1}: best = {best}, fitness = {fitness(best)}")

print("Kết quả cuối cùng:", best, "với fitness =", fitness(best))

Vòng lặp chính thực hiện quá trình tiến hóa. Ở mỗi thế hệ, chúng ta tạo một quần thể hoàn toàn mới bằng cách lặp lại chu trình chọn lọc, lai ghép và đột biến. Quần thể mới này thay thế hoàn toàn quần thể cũ. Chúng ta theo dõi cá thể tốt nhất qua các thế hệ để quan sát sự tiến bộ của thuật toán. Trong bài toán One-Max, bạn sẽ thấy số lượng bit 1 tăng dần và cuối cùng hội tụ về giá trị tối đa là 10.

Link code mẫu

4. Kết luận

Thuật toán Di truyền (GA) là công cụ tối ưu hóa mạnh mẽ, linh hoạt và bền vững, đặc biệt hiệu quả trong các bài toán không khả vi, phức tạp, đa mục tiêu.

Điểm mạnh của GA bao gồm khả năng tìm kiếm toàn cục nhờ vào cơ chế duy trì đa dạng trong quần thể. GA không phụ thuộc vào cấu trúc toán học của bài toán, chỉ cần một hàm đánh giá. Hơn nữa, GA có khả năng song song hóa tự nhiên, cho phép tận dụng các kiến trúc tính toán hiện đại.

Thách thức khi sử dụng GA bao gồm khả năng hội tụ sớm vào các điểm tối ưu cục bộ nếu đa dạng di truyền không được duy trì tốt. GA cần tinh chỉnh tham số cẩn thận để đạt hiệu suất tốt, và điều này thường phụ thuộc vào bài toán cụ thể. Chi phí tính toán có thể cao do cần đánh giá nhiều cá thể qua nhiều thế hệ.

Hướng phát triển của GA trong tương lai bao gồm Hybrid GA, nơi GA được kết hợp với các kỹ thuật tìm kiếm cục bộ, mạng nơ-ron, hoặc logic mờ để tăng hiệu quả. Parallel GA tận dụng GPU và các hệ thống song song để xử lý các quần thể lớn. Adaptive GA tự động điều chỉnh các tham số như tỉ lệ lai ghép và đột biến dựa trên tiến trình của thuật toán.

Tóm lại, GA không chỉ là công cụ tối ưu hóa mà còn là nền tảng cho các hệ thống thông minh lai, mở ra hướng nghiên cứu sâu hơn trong Evolutionary Computation.

Tài liệu tham khảo

  1. Wikipedia: Genetic Algorithm
  2. Viblo.vn – Thuật toán di truyền
  3. Scribd – Luận văn Giải thuật di truyền và ứng dụng vào bài toán lập thời khóa biểu
  4. ResearchGate – Critical Evaluation of Genetic Algorithms
  5. PMC – Genetic Algorithm for Traveling Salesman Problem
  6. Taylor & Francis – Simulation-based Optimization of a Production System Topology
  7. ResearchGate – Qualities, Challenges and Future of Genetic Algorithms