I. Thuật toán tiến hóa (Evolutionary Algorithms)

1. Sơ lược về thuyết tiến hóa

Như ta đã biết, sự sống trên Trái Đất đã tiến hóa qua hàng triệu năm, và quá trình này là điều bắt buộc để các sinh vật sống có thể thích nghi để tồn tại và thích nghi trong môi trường sống của chúng. Một ví dụ điển hình là hươu cao cổ. Chúng đã phát triển cổ dài qua từng thế hệ để vươn tới những chiếc lá cao hơn để có được nguồn thức ăn của mình, nơi các loài động vật khác không thể với tới. Điều này được thúc đẩy bởi chọn lọc tự nhiên, nơi những đặc điểm mới được sinh ra và trở nên phổ biến hơn vì những cá thể mang chúng có khả năng sống sót cao hơn.

Nói một cách đơn giản hơn, các sinh vật mang những đặc điểm phù hợp với môi trường xung quanh sẽ có cơ hội sống sót và truyền lại cho con cái của chúng những đặc trưng hữu ích ấy. Cứ như vậy, với những thay đổi nhỏ được cộng lại theo thời gian sẽ giúp cho thế hệ con cái đối phó với các điều kiện môi trường khắc nghiệt nhất.

2. Liên hệ từ thuyết tiến hóa đến thuật toán tiến hóa

Ý tưởng về thuyết tiến hóa đã trở thành nguồn cảm hứng mạnh mẽ cho các nhà khoa học máy tính, khi vào những năm 1960 đã xuất hiện ra câu hỏi: "Sẽ ra sao nếu chúng ta có thể mô phỏng quy luật tự nhiên này bên trong máy tính?" Thay vì thiết kế 1 giải pháp, chúng ta có thể khiến chúng phải tiến hóa?

Đó cũng chính là linh hồn của Thuật toán tiến hóa (Evolutionary Algorithms - EA), và đặc biệt là nhánh nghiên cứu nổi tiếng nhất của nó: Giải thuật di truyền (Genetic Algorithm - GA).

Lấy cảm hứng từ quá trình tiến hóa tự nhiên, Thuật toán Tiến hóa (EA) hoạt động bằng cách liên tục sàng lọc một nhóm giải pháp để chọn ra những phương án tốt nhất. Các phương án này sau đó được áp dụng những thay đổi nhỏ (biến dị) và được đánh giá lại để xem liệu chúng có mang lại sự cải thiện hay không. Bằng cách lặp đi lặp lại chu trình "chọn lọc - cải tiến" này qua nhiều thế hệ, EA có khả năng hội tụ về các giải pháp xuất sắc cho những vấn đề phức tạp trong nhiều lĩnh vực.

II. Giải thuật di truyền (Genetic Algorithm)

1. Từ thuật toán tiến hóa (EA) đến giải thuật di truyền (GA)

• Trong họ hàng các thuật toán tiến hóa, mỗi nhánh đều lấy cảm hứng từ một khía cạnh khác nhau của tiến hóa tự nhiên. Evolution Strategies (ES) - Chiến lược tiến hóa được lấy cảm hứng từ quá trình thích nghi liên tục của sinh vật với môi trường; hay Differential Evolution (DE) – Tiến hóa vi sai sử dụng ý tưởng tạo đột biến dựa trên chênh lệch giữa các cá thể trong quần thể. Nhưng nổi bật và phổ biến nhất chính là Giải thuật Di truyền (Genetic Algorithm - GA), với ý tưởng mạnh mẽ từ di truyền học và chọn lọc tự nhiên. Trong bài viết này, chúng ta sẽ đào sâu về Giải thuật di truyền - nhánh nghiên cứu phổ biến của EA và được ứng dụng rộng rãi đa lĩnh vực.

• Mục tiêu của Genetic Algorithm: tìm kiếm lời giải tối ưu hoặc gần tối ưu cho những bài toán phức tạp, phi tuyến, không có công thức đạo hàm rõ ràng, nơi mà các phương pháp cổ điển (như Gradient Descent) không thể áp dụng hiệu quả. Trong khi Gradient Descent dựa trên việc di chuyển dần theo hướng giảm dốc của hàm mất mát (loss function) để tìm cực tiểu, Genetic Algorithm mô phỏng sự tiến hóa tự nhiên để tìm lời giải tối ưu mà không cần thông tin về đạo hàm hay cấu trúc toán học của bài toán.

2. Các thành phần chính của Genetic Algorithm

Dưới đây là bảng các thành phần chính của Genetic Algorithm và sự tương quan giữa chúng với các khái niệm sinh học của thuyết tiến hóa:

2.1. Tập hợp các lời giải (Population)

Quần thể (Population) là nơi chứa đựng các lời giải ứng viên (candidate solutions). Quần thể là một tập hợp các nhiễm sắc thể (chromosome), còn được gọi là các cá thể (individual).
Mục tiêu của thuật toán là giải quyết vấn đề bằng cách bắt chước các cơ chế tiến hóa thông qua nhiều cá thể cùng tồn tại và hợp tác giải quyết vấn đề. Quần thể đại diện cho các lời giải khả thi khác nhau cho bài toán tối ưu.
Quần thể ban đầu thường được khởi tạo. Ví dụ, trong bài toán One-Max, quần thể ban đầu bao gồm nhiều cá thể, mỗi cá thể là một chuỗi nhị phân được sinh ngẫu nhiên

2.2. Mã hóa cá thể (Encoding)

Trong GA, mỗi lời giải cần được biểu diễn dưới dạng nhiễm sắc thể (chromosome).
- Mã hóa (Encoding) là quá trình các biến (phenotype) của bài toán thực tế được chuyển thành nhiễm sắc thể (genotype)
- Một cá thể là một lời giải ứng viên. Nhiễm sắc thể được xem là một danh sách các bit, trong đó mỗi bit đại diện cho một gen (gene), mã hóa một phần của lời giải.
Ví dụ: Trong bài toán One-Max, mỗi cá thể là một chuỗi nhị phân (gồm các số 0 và 1), và mỗi gen là một bit 0 hoặc 1. Các kiểu gen (genotypes) phổ biến có thể là chuỗi nhị phân, hoặc vector giá trị thực (real-valued vectors).

2.3. Hàm thích nghi (Fitness Function)

Hàm thích nghi (Fitness Function) là thước đo độ "tốt" (goodness) của mỗi lời giải ứng viên (cá thể)
- Độ thích nghi (Fitness) đo lường mức độ hiệu quả của cá thể đó trong việc giải quyết bài toán. Giá trị fitness càng cao, lời giải càng tốt.
- Độ thích nghi có thể được đo bằng các thuật ngữ toán học, mô phỏng máy tính, hoặc thậm chí là đánh giá của con người
- Mục tiêu chính của Giải thuật Di truyền là tối đa hóa giá trị của hàm fitness $f(x)$.
Ví dụ: Trong bài toán One-Max, hàm fitness $f(x)$ được tính bằng tổng số bit 1
$$f(x) = \sum_{i=0}^{n} x_i$$

2.4. Toán tử chọn lọc (Selection Operator)

Toán tử chọn lọc (Selection Operator) là cơ chế thực hiện nguyên tắc "Sự sống sót của cá thể thích nghi nhất" (Survival of the fittest).
- Mục đích: chọn ra các cá thể có độ thích nghi cao từ quần thể để làm cha mẹ (parents) cho thế hệ tiếp theo.
- Cơ chế phổ biến:
Roulette Wheel Selection (Chọn lọc Vòng quay Xổ số): Xác suất chọn một nhiễm sắc thể tỷ lệ thuận với độ thích nghi (fitness) của nó.
Tournament Selection (Chọn lọc Đấu loại): Kết hợp khái niệm tỷ lệ độ thích nghi với chọn lọc ngẫu nhiên. Cơ chế này thường hoạt động bằng cách chọn ngẫu nhiên các cá thể, so sánh giá trị fitness của chúng, và giữ lại cá thể có fitness cao hơn.
- Elitism (Cá thể ưu tú): Một chiến lược quan trọng là giữ lại nguyên vẹn một số cá thể tốt nhất (cá thể ưu tú) để chúng trực tiếp chuyển sang thế hệ tiếp theo

2.5. Toán tử lai ghép (Crossover Operator)

Toán tử lai ghép (Crossover Operator), hay tái tổ hợp (Recombination), mô phỏng sự kế thừa gen (genetic inheritance).
• Mục đích: Kết hợp các gen của hai cá thể cha mẹ để tạo ra cá thể con mới, qua đó trao đổi vật liệu di truyền để khám phá các lời giải mới. Quá trình này mô phỏng sự trao đổi chéo giữa các nhiễm sắc thể.
• Cơ chế: Trao đổi các phân đoạn gen thuộc về các cá thể cha mẹ.
• Các loại Crossover: Bao gồm 1-point crossover, n-point crossover (ví dụ 2-point, 3-point), và Uniform Crossover.
• Uniform Crossover (Lai ghép đồng nhất): Là phương pháp trao đổi vật liệu di truyền bằng cách quyết định ngẫu nhiên cho mỗi gen xem có nên hoán đổi nó hay không, dựa trên một tỉ lệ hoán đổi (p_{cross})

2.6. Toán tử đột biến (Mutation Operator)

Toán tử đột biến (Mutation Operator) thực hiện sự biến đổi gen (self-variation), thường được áp dụng sau bước lai ghép.
• Mục đích cốt lõi: Đột biến đưa vào các thay đổi ngẫu nhiên nhỏ để duy trì tính đa dạng trong quần thể.
• Xác suất: Phần trăm áp dụng đột biến phải rất nhỏ, được gọi là tỉ lệ đột biến (p_{muta}).
• Vai trò cứu cánh: Đột biến là cực kỳ quan trọng vì nó giúp thuật toán có khả năng thoát khỏi các điểm cực trị cục bộ (local optima) và tiếp tục khám phá không gian tìm kiếm.
• Cơ chế (nhị phân): Thay đổi ngẫu nhiên giá trị của một gen thành một giá trị khác. Ví dụ trong bài toán nhị phân, gen 0 sẽ đổi thành 1, và ngược lại.

3. Quy trình hoạt động của Genetic Algorithm

Toàn bộ hoạt động của GA vận hành như một chu trình tiến hóa có định hướng, được chia thành các vòng lặp rời rạc gọi là thế hệ. Mỗi thế hệ là một nỗ lực nhằm cải thiện chất lượng giải pháp tổng thể của quần thể. Để làm được điều này, thuật toán sẽ áp dụng một chuỗi các toán tử di truyền (genetic operators) lên quần thể hiện tại để sản sinh ra một quần thể kế cận. Các bước tạo nên một thế hệ hoàn chỉnh bao gồm:

Bước 1: Khởi tạo (Initialization):
Tạo ra quần thể ban đầu gồm nhiều cá thể (individuals), mỗi cá thể biểu diễn một lời giải tiềm năng cho bài toán. Quần thể khởi đầu $P_0$ được tạo ra bằng cách sinh ngẫu nhiên 1 số lượng N cá thể, với mỗi cá thể được biểu diễn thành chuôi gen. Tùy thuộc vào bài toán mà chuỗi gen sẽ khác nhau (ví dụ như trong bài One-Max Problem sẽ là chuỗi nhị phân).

Bước 2: Đánh giá fitness quần thể (Fitness Evaluation):
Đánh giá mức độ thích nghi (fitness) của từng cá thể để xác định chất lượng nghiệm bằng cách áp dụnghàm thích nghi (Fitness Function) cho mỗi cá thể. Giá trị fitness sẽ đánh giá mức độ tốt của từng cá thể trong bài toán.

Bước 3: Giữ các cá thể ưu tú (Elitism):
Đảm bảo các cá thể tốt nhất không bị mất đi trong quá trình tiến hóa. Những cá thể có fitness cao nhất sẽ được chuyển trực tiếp vào quần thể tiếp theo, giúp quá trình hội tụ nhanh và ổn định hơn.

Bước 4: Chọn lọc bố mẹ (Selection):
Chọn các cá thể “bố mẹ” để tạo ra thế hệ con (offspring) bằng cách áp dụng các toán tử chọn lọc (Selection Operator)

Bước 5: Lai ghép (Crossover):
Tạo ra các cá thể con mới bằng cách kết hợp gen của hai bố mẹ bằng cách áp dụng các toán tử lai ghép (Crossover Operator).

Bước 6: Đột biến (Mutation):
Giới thiệu đa dạng di truyền để tránh hội tụ cục bộ bằng cách áp dụng toán tử đột biến (Mutation Operator) để thay đổi ngẫu nhiên một (hoặc vài) gen trong chuỗi.

Bước 7: Cập nhật quần thể mới (Population Update):
Tạo ra quần thể mới $P_{t+1}$ gồm các cá thể ưu tú giữ lại và cá thể con từ quá trình lai ghép và đột biến.

Bước 8: Điều kiện dừng (Termination Condition):
Kiểm tra xem có nên dừng vòng lặp tiến hóa hay không. Một vài điều kiện dừng thường gặp:
- Đạt đến số thế hệ tối đa.
- Không cải thiện thêm về fitness sau nhiều vòng.
- Đạt được nghiệm mong muốn.

4. One-Max Problem – bài toán minh họa kinh điển cho cơ chế hoạt động của giải thuật di truyền

Ta sẽ giải bài toán One-Max bằng Giải thuật di truyền, với các bước triển khai bằng Python như sau:

Bước 1: Cài đặt các thư viện cần thiết và các cấu hình thực nghiệm

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

RANDOM_STATE = 42

def set_random_seed(seed=RANDOM_STATE):
    random.seed(seed)
    np.random.seed(seed)

set_random_seed()

CHROM_SIZE = 10             # Độ dài cá thể
pop_size = 5                # Kích thước quần thể
generations = 21            # Số thế hệ
elitism = 2                 # Số cá thể ưu tú được chọn
crossover_rate = 0.9        # Tỉ lệ lai ghép
mutation_rate = 0.1         # Tỉ lệ đột biến

Bước 2: Khởi tạo cá thể, với mỗi cá thể là chuỗi nhị phân có độ dài là CHROM_SIZE = 10

def generate_random_value():
    """Tạo gen ngẫu nhiên"""
    random_value = random.randint(0, 1)
    return random_value

def create_individual(size):
    """Tạo một cá thể ngẫu nhiên"""
    random_lst = [generate_random_value() for _ in range(size)]
    return random_lst

Bước 3: Hàm thích nghi (Fitness Function)
Hàm fitness $f(x)$ được tính bằng tổng số bit 1
$$f(x) = \sum_{i=0}^{n} x_i$$

def compute_fitness(individual):
    """Tính tổng các gen ở trong 1 cá thể (tổng các bit)"""
    fitness = sum(individual)
    return fitness

Bước 4: Giữ các cá thể ưu tú (Elitism)
Trong ví dụ này, ta sẽ dùng cơ chế Tournament Selection để chọn ra các cá thể ưu tú nhất

def tournament_select(population, fitness_scores, tournament_size=2):
    """Chọn ra k cá thể ngẫu nhiên từ quần thể và trả về cá thể có giá trị fitness cao nhất"""
    k = min(tournament_size, len(population))
    candidate_indices = random.sample(range(len(population)), k = k)
    best_idx = max(candidate_indices, key=lambda idx:           fitness_scores[idx])

    return population[best_idx]

Bước 5: Toán tử lai ghép (Crossover)
Hàm này duyệt qua từng gen của bố mẹ, mỗi gen sẽ có tỉ lệ đổi gen là rate. Với cấu hình crossover_rate = 0.9, mỗi gen sẽ có 90% cơ hội được hoán đổi, từ đó tạo ra các cá thể con từ những sự kết hợp ngẫu nhiên

def uniform_crossover(individual1, individual2, rate):
    child1, child2 = individual1.copy(),  individual2.copy()
    for i in range(len(individual1)):
      if random.random() <= rate:
        child1[i], child2[i] = individual2[i],  individual1[i]

    return child1, child2

Bước 6: Toán tử đột biến (Mutation)
Hàm này sẽ duyệt qua từng bit của 1 cá thể, sử dụng cơ chế lật bit từ 0 thành 1 và ngược lại với xác suất mutation_rate = 0.1

def bitflip_mutation(individual, rate):
    mutated = []
    for bit in individual:
      if random.random() <= rate:
        mutated.append(1 - bit)
      else:
        mutated.append(bit)
    return mutated

Bước 7: Vòng lặp tiến hóa

def select_parent(population, fitness_scores, method):
    """
    - Chọn một cá thể cha/mẹ từ quần thể (population) 
    dựa trên phương pháp (method) "tournament" hoặc "proportional".
    - Trong bài toán này ta chỉ quan tâm đến phương pháp "tournament"
    """
    if method == "tournament":
        return tournament_select(population, fitness_scores)
    if method == "proportional":
        return proportional_select(population, fitness_scores)

def evaluate_population(population, fitness_fn):
    """
    Đánh giá toàn bộ quần thể:
    1. Sắp xếp các cá thể theo fitness giảm dần (tốt nhất -> tệ nhất).
    2. Trả về quần thể đã sắp xếp và danh sách điểm fitness tương ứng.
    """
    ordered = sorted(population, key=fitness_fn, reverse=True)
    fitness_scores = [fitness_fn(individual) for individual in ordered]
    return ordered, fitness_scores

def collect_elites(population, elite_count):
    """
    Trích xuất 'elite_count' cá thể tốt nhất từ quần thể (đã được sắp xếp).
    """
    if elite_count <= 0:
        return []
    return population[:elite_count]

def create_offspring(
    population, fitness_scores, selection_method,
    crossover_rate, mutation_rate,
):
    """
    Tạo ra một cặp cá thể con (children) mới:
    1. Chọn 2 cha mẹ (parent1, parent2) bằng phương pháp 'selection_method'.
    2. Lai ghép (crossover) 2 cha mẹ để tạo ra 2 con (child1, child2).
    3. Đột biến (mutation) 2 con.
    4. Trả về 2 con đã đột biến.
    """
    parent1 = select_parent(population, fitness_scores, selection_method)
    parent2 = select_parent(population, fitness_scores, selection_method)
    child1, child2 = uniform_crossover(parent1, parent2, crossover_rate)
    return (
        bitflip_mutation(child1, mutation_rate),
        bitflip_mutation(child2, mutation_rate),
    )

def evolve_ga(chrom_size, pop_size, crossover_rate, mutation_rate,
              selection_method="tournament", fitness_fn=compute_fitness,
              seed=RANDOM_STATE
):
    """
    Thực thi vòng lặp Giải thuật Di truyền (GA) chính.
    """
    set_random_seed(seed)

    # Khởi tạo quần thể
    population = [create_individual(chrom_size) for _ in range(pop_size)]
    fitness_history = []

    for _ in range(generations):
        # Đánh giá quần thể hiện tại, sắp xếp quần thể và lấy điểm fitness
        population, fitness_scores = evaluate_population(population, fitness_fn)

        # Ghi lại điểm fitness của cá thể tốt nhất thế hệ này
        fitness_history.append(fitness_scores[0])

        # Giữ các cá thể ưu tú (Elitism)
        new_population = collect_elites(population, elitism)
        while len(new_population) < pop_size:
            # Tạo các cá thể con mới
            children = create_offspring(population, fitness_scores, selection_method, crossover_rate, mutation_rate)

            # Thêm các con vào quần thể mới
            for child in children:
                new_population.append(child)
                if len(new_population) == pop_size:
                    break

        # Quần thể mới (new_population) trở thành quần thể (population) cho vòng lặp tiếp theo
        population = new_population

    # Sau khi kết thúc tất cả các thế hệ, đánh giá quần thể cuối cùng
    best_population, _ = evaluate_population(population, fitness_fn)

    # Trả về cá thể tốt nhất (best_population[0]) và lịch sử fitness
    return best_population[0], fitness_history

III. Kết luận

Giải thuật Di truyền (Genetic Algorithm – GA) mô phỏng quá trình tiến hóa tự nhiên để giải quyết các bài toán tối ưu. Bằng cơ chế chọn lọc, lai ghép và đột biến, GA có khả năng tìm kiếm nghiệm tốt trong không gian lớn mà không cần thông tin đạo hàm hay cấu trúc toán học của bài toán.

Thực nghiệm với bài toán One-Max cho thấy GA có thể hội tụ nhanh về nghiệm tối ưu, nhờ sự kết hợp giữa khai thác nghiệm tốt hiện có và duy trì đa dạng di truyền. Dù không luôn đảm bảo tìm được nghiệm tối ưu tuyệt đối, GA thường cho kết quả xấp xỉ tối ưu trong thời gian hợp lý.

Với ưu điểm về tính linh hoạt và khả năng thích nghi, Giải thuật Di truyền được ứng dụng rộng rãi trong các lĩnh vực như tối ưu kỹ thuật, tài chính, trí tuệ nhân tạo và điều khiển tự động.

IV. Reference

[1] Các hình ảnh và code được tham khảo từ slide và bài tập của tài liệu AIO2025, Module 05