Giải thuật di truyền (Genetic Algorithms): Từ Tiến hóa Darwin đến Tối ưu hóa AI

1. Giới thiệu về giải thuật di truyền

Trong bài viết này chúng ta sẽ cùng nhau tìm hiểu về Genetic Algorithms(GAs). Đây là một kỹ thuật tìm kiếm và tối ưu được sử dụng trong Evolutionary Algorithms (EA đây có thể hiểu là đây là thuật toán tối ưu),

GA được phát triển dựa trên ý tưởng của việc chọn lọc các cá thể trong tự liên và lai tạo ra các cá thể mới với các chỉ số có thể cao hơn các cặp lai tạo(cha mẹ) để có thể thích ứng trong điều kiện khắc nghiệt.

Hình 1: Ý tưởng cơ bản về Genetic Algorithm(GA) [1]

Từ ảnh trên các bạn có thể thấy các cá thể sẽ được chọn lọc ngẫu nhiên và lại tạo ra các cá thể mới và tiếp tục vòng lặp như vậy liên tục cho đến khi đạt được các chi số phù hợp với môi trường sống hiện tại.

2. Các thành phần của giải thuật di truyền

Để hiểu cách GA hoạt động, chúng ta cần phân tích các thành phần cấu tạo nên nó. Mỗi thành phần đều có một vai trò tương ứng trong quá trình tiến hóa sinh học.

2.1. Các khái niệm nền tảng

Hình 2: Hình ảnh về Gen, Chromosome, Population trong GA [1]

• Gen (Gene): Đây là đơn vị cơ bản nhất, đại diện cho một tham số duy nhất của giải pháp. Ví dụ, trong một chuỗi nhị phân, mỗi bit (0 hoặc 1) là một gen.

• Nhiễm sắc thể (Chromosome) hay Cá thể (Individual): Là một chuỗi các gen, đại diện cho một giải pháp ứng cử viên hoàn chỉnh cho bài toán. Ví dụ, một chuỗi bit 10110 có thể là một nhiễm sắc thể.

• Quần thể (Population): Là một tập hợp các nhiễm sắc thể, đại diện cho một nhóm các giải pháp khả thi đa dạng cùng tồn tại trong một thế hệ duy nhất.

Mối quan hệ này có thể được hình dung một cách trực quan: một Quần thể bao gồm nhiều Nhiễm sắc thể, và mỗi Nhiễm sắc thể được tạo thành từ các Gen.

2.2. Chu kỳ tiến hóa

Hình 3: Pipeline cơ bản về Genetic Algorithm(GA) [1]

Toàn bộ quá trình hoạt động của GA là một chu kỳ lặp đi lặp lại, gọi là các thế hệ. Mỗi thế hệ bao gồm các bước sau:

1. Khởi tạo (Initialization): Khởi tạo quần thể với n cá thể

2. Đánh giá (Evaluation): Tính toán độ thích nghi của mỗi cá thể trong quần thể.

3. Lựa chọn (Selection): Chọn ra các cá thể "cha mẹ" từ quần thể hiện tại dựa trên độ thích nghi của chúng.

4. Lai ghép (Crossover): Tạo ra các cá thể "con" (offspring) bằng cách kết hợp vật chất di truyền của các cặp cha mẹ đã chọn.

5. Đột biến (Mutation): Thay đổi ngẫu nhiên một vài gen trong các cá thể con để tạo ra sự đa dạng.

6. Thay thế (Replacement): Quần thể mới được tạo ra sẽ thay thế quần thể cũ, và chu kỳ bắt đầu lại.

Quá trình này tiếp tục cho đến khi một điều kiện dừng được thỏa mãn, chẳng hạn như đạt đến một số thế hệ nhất định hoặc tìm thấy một giải pháp đủ tốt.

2.3. Toán tử di truyền (Genetic Operators)

Ở dưới đây là một số toán tử phổ biến trong giải thuật di truyền. Những toán tử này đóng vai trò quan trọng trong thuật toán.

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

• Định nghĩa: Hàm thích nghi (Fitness Function) là một hàm do người dùng định nghĩa để đánh giá mức độ "tốt" của một giải pháp ứng cử viên (một nhiễm sắc thể).

• Vai trò: Đây là kim chỉ nam duy nhất cho quá trình tìm kiếm của thuật toán. GA sử dụng các điểm số này để hướng quần thể tiến dần đến các giải pháp ngày càng tốt hơn qua từng thế hệ.

Hình 4: Fitness Function của bài toán One-max [1]

2.3.2. Lựa chọn - Chọn lọc cha mẹ (Selection)

• Mục đích: Quyết định những cá thể được phép sinh sản để tạo ra thế hệ tiếp theo. Những cá thể có độ thích nghi cao hơn sẽ có xác suất được chọn cao hơn.

Hình 5: Quá trình Selection trong GA [1]

• Các phương pháp phổ biến:

  • Roulette Wheel Selection: Trong phương pháp này, mỗi cá thể được gán một "phần" trên một bánh xe roulette ảo, với kích thước của phần đó tỷ lệ thuận với điểm thích nghi của nó. Bánh xe được quay, và cá thể nào mà con trỏ chỉ vào sẽ được chọn.

  • Tournament Selection: Một nhóm nhỏ các cá thể được chọn ngẫu nhiên từ quần thể để tham gia một "giải đấu". Cá thể có độ thích nghi cao nhất trong nhóm này sẽ chiến thắng và được chọn làm cha mẹ.

2.3.3. Lai ghép - Tạo ra thế hệ con (Crossover)

• Mục đích: Crossover mô phỏng quá trình sinh sản hữu tính. Nó lấy hai nhiễm sắc thể "cha mẹ" và kết hợp vật chất di truyền của chúng để tạo ra một hoặc nhiều nhiễm sắc thể "con".

Hình 6: Minh hoạ về One-point Crossover trong GA [1]

• Các kiểu lai ghép phổ biến:

  • One-Point Crossover: Một điểm ngẫu nhiên được chọn trên cả hai nhiễm sắc thể cha mẹ. Tất cả các gen nằm sau điểm đó sẽ được hoán đổi cho nhau.

  • N-Point Crossover: Nhiều điểm lai ghép được chọn, và các đoạn gen giữa các điểm này được hoán đổi.

  • Uniform Crossover: Đối với mỗi vị trí gen, một "đồng xu" được tung để quyết định xem gen của cha hay mẹ sẽ được truyền cho con.

2.3.4. Đột biến (Mutation)

• Mục đích: Mutation là một toán tử quan trọng giúp đưa các thay đổi ngẫu nhiên vào các nhiễm sắc thể riêng lẻ. Nó hoạt động bằng cách lật ngẫu nhiên giá trị của một gen với một xác suất rất nhỏ.

Hình 7: Minh hoạ về Mutation trong GA [1]

• Vai trò: Vai trò chính của đột biến là duy trì sự đa dạng di truyền trong quần thể. Chống lại sự hội tụ sớm và là cách để thuật toán thoát khỏi các điểm tối ưu cục bộ, cho phép nó tiếp tục khám phá các vùng mới của không gian tìm kiếm.

3. Thực hành triển khai: Giải quyết bài toán One-Max bằng Python

Để hiểu rõ cơ chế hoạt động của GA, chúng ta sẽ bắt đầu với một bài toán kinh điển và đơn giản: bài toán One-Max. Mục tiêu là tìm ra một chuỗi nhị phân có độ dài $N$ sao cho tổng các bit của nó là lớn nhất.

Hướng dẫn lập trình từng bước

Dưới đây là một bản triển khai hoàn chỉnh bằng Python, dựa trên các ví dụ trong tài liệu tham khảo[1].

1. Thiết lập và Khởi tạo

Đầu tiên, chúng ta định nghĩa các tham số cho thuật toán và viết các hàm để tạo ra một cá thể ngẫu nhiên và quần thể ban đầu.

import random

# --- Tham số của GA ---
CHROMOSOME_LENGTH = 50  # Độ dài của mỗi nhiễm sắc thể
POPULATION_SIZE = 100   # Kích thước của quần thể
MUTATION_RATE = 0.01    # Tỷ lệ đột biến
CROSSOVER_RATE = 0.9    # Tỷ lệ lai ghép
GENERATIONS = 100       # Số thế hệ

# --- Hàm khởi tạo ---
def create_individual():
    """Tạo một cá thể (nhiễm sắc thể) ngẫu nhiên."""
    return [random.randint(0, 1) for _ in range(CHROMOSOME_LENGTH)]

def create_initial_population():
    """Tạo quần thể ban đầu."""
    return [create_individual() for _ in range(POPULATION_SIZE)]

• create_individual(): Hàm này tạo ra một chuỗi nhị phân ngẫu nhiên có độ dài CHROMOSOME_LENGTH, đại diện cho một giải pháp.

• create_initial_population(): Hàm này gọi create_individual() nhiều lần để tạo ra một quần thể ban đầu gồm POPULATION_SIZE cá thể.

2. Hàm Thích nghi

Hàm thích nghi cho bài toán One-Max rất đơn giản: nó chỉ cần tính tổng các bit trong nhiễm sắc thể.

def compute_fitness(individual):
    """Tính toán độ thích nghi của một cá thể (tổng các bit 1)."""
    return sum(individual)

3. Toán tử Lựa chọn

Chúng ta sẽ triển khai phương pháp lựa chọn giải đấu vì tính mạnh mẽ và hiệu quả của nó.

def tournament_selection(population, fitnesses, k=3):
    """
    Thực hiện lựa chọn giải đấu.
    Chọn k cá thể ngẫu nhiên và trả về cá thể tốt nhất.
    """
    # Chọn k chỉ số ngẫu nhiên từ quần thể
    selection_ix = [random.randint(0, len(population) - 1) for _ in range(k)]

    # Tìm cá thể có độ thích nghi cao nhất trong số các cá thể được chọn
    best_ix = -1
    best_fitness = -1
    for ix in selection_ix:
        if fitnesses[ix] > best_fitness:
            best_fitness = fitnesses[ix]
            best_ix = ix

    return population[best_ix]

Hàm này chọn ra k cá thể ngẫu nhiên và trả về cá thể có điểm thích nghi cao nhất trong nhóm đó.

4. Toán tử Lai ghép

Chúng ta sẽ sử dụng lai ghép đồng nhất, một phương pháp hiệu quả để tạo ra sự đa dạng.

def uniform_crossover(parent1, parent2):
    """Thực hiện lai ghép đồng nhất."""
    child1, child2 = parent1.copy(), parent2.copy()
    if random.random() < CROSSOVER_RATE:
        for i in range(CHROMOSOME_LENGTH):
            # Tung đồng xu cho mỗi gen
            if random.random() < 0.5:
                child1[i], child2[i] = child2[i], child1[i]
    return child1, child2

Hàm này duyệt qua từng gen của cha mẹ. Với mỗi gen, nó có $50\%$ cơ hội hoán đổi gen đó giữa hai cá thể con, tạo ra sự kết hợp mới mẻ.

5. Toán tử Đột biến

Toán tử đột biến sẽ lật từng bit với một xác suất rất nhỏ.

def mutate(individual):
    """Thực hiện đột biến trên một cá thể."""
    for i in range(CHROMOSOME_LENGTH):
        if random.random() < MUTATION_RATE:
            # Lật bit (0 -> 1, 1 -> 0)
            individual[i] = 1 - individual[i]
    return individual

Đột biến là rất quan trọng để ngăn thuật toán bị mắc kẹt và để khám phá những giải pháp mới.

6. Vòng lặp Tiến hóa Chính

Cuối cùng, chúng ta kết hợp tất cả các thành phần lại trong một vòng lặp chính để mô phỏng quá trình tiến hóa.

def genetic_algorithm():
    """Hàm chính để chạy Giải thuật Di truyền."""
    population = create_initial_population()
    best_fitness_history = []

    for generation in range(GENERATIONS):
        # 1. Đánh giá quần thể hiện tại
        fitnesses = [compute_fitness(ind) for ind in population]

        # Theo dõi cá thể tốt nhất
        best_ind_index = fitnesses.index(max(fitnesses))
        best_fitness = fitnesses[best_ind_index]
        best_fitness_history.append(best_fitness)

        print(f"Thế hệ {generation}: Độ thích nghi tốt nhất = {best_fitness}/{CHROMOSOME_LENGTH}")

        # Điều kiện dừng: nếu đã tìm thấy giải pháp tối ưu
        if best_fitness == CHROMOSOME_LENGTH:
            print("Đã tìm thấy giải pháp tối ưu!")
            break

        # 2. Tạo thế hệ mới
        new_population = []
        while len(new_population) < POPULATION_SIZE:
            # 3. Lựa chọn cha mẹ
            parent1 = tournament_selection(population, fitnesses)
            parent2 = tournament_selection(population, fitnesses)

            # 4. Lai ghép
            child1, child2 = uniform_crossover(parent1, parent2)

            # 5. Đột biến
            mutated_child1 = mutate(child1)
            mutated_child2 = mutate(child2)

            new_population.extend([mutated_child1, mutated_child2])

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

    return best_fitness_history

# Chạy thuật toán
fitness_history = genetic_algorithm()

Trực quan hóa quá trình tiến hóa: Phân tích kết quả

Khi chạy đoạn mã trên, bạn sẽ thấy kết quả tương tự như sau:

Thế hệ 0: Độ thích nghi tốt nhất = 35/50
...
Thế hệ 5: Độ thích nghi tốt nhất = 42/50
...
Thế hệ 10: Độ thích nghi tốt nhất = 48/50
...
Thế hệ 13: Độ thích nghi tốt nhất = 50/50
Đã tìm thấy giải pháp tối ưu!

Chúng ta có thể vẽ biểu đồ lịch sử độ thích nghi để thấy rõ sự cải thiện qua các thế hệ, tương tự như biểu đồ trong.

import matplotlib.pyplot as plt

plt.plot(fitness_history)
plt.title("Sự tiến hóa của độ thích nghi qua các thế hệ")
plt.xlabel("Thế hệ")
plt.ylabel("Độ thích nghi tốt nhất")
plt.grid(True)
plt.show()

Biểu đồ sẽ cho thấy một đường cong đi lên, thể hiện rằng quần thể đang dần "học" và hội tụ về giải pháp tối ưu. Đây là một minh chứng trực quan và mạnh mẽ cho sức mạnh của quá trình tiến hóa mô phỏng.

Hình 8: Kết quả của GA trong One-max problem [1]

4. Ứng dụng của Genetic Algorithm trong những lĩnh vực khác

4.1. Từ chuỗi bit đến tham số mô hình

Sức mạnh thực sự của Giải thuật Di truyền nằm ở tính linh hoạt của nó. Mặc dù ví dụ One-Max sử dụng chuỗi bit, nhiễm sắc thể có thể đại diện cho bất cứ thứ gì, từ trọng số của một mạng nơ-ron đến các tham số của một mô hình hồi quy.
Bí quyết nằm ở sự biểu diễn (representation). Vòng lặp cốt lõi của GA (lựa chọn, lai ghép, đột biến) không quan tâm đến ý nghĩa của các gen. Miễn là chúng ta có thể:

1. Mã hóa (Encode) một giải pháp thành một nhiễm sắc thể.

2. Viết một hàm thích nghi (Fitness Function) để đánh giá chất lượng của giải pháp đó.

Chúng ta có thể áp dụng GA cho gần như mọi bài toán tối ưu hóa. Điều này biến GA từ một thuật toán giải quyết bài toán chuỗi bit thành một metaheuristic tối ưu hóa đa năng.

4.2. Ví dụ thực tế: Huấn luyện một mô hình Hồi quy Tuyến tính

• Bài toán: Tìm các giá trị tối ưu cho $a$ và $b$ trong phương trình $price = a \times area + b$ để giảm thiểu sai số dự đoán trên một tập dữ liệu cho trước.

• Triển khai bằng GA:

  1. Nhiễm sắc thể: Mỗi cá thể sẽ là một nhiễm sắc thể có hai gen, đại diện cho cặp giá trị $[a, b]$. Các gen này sẽ là số thực (floating-point).

  2. Hàm thích nghi: Độ thích nghi sẽ là nghịch đảo của sai số của mô hình, ví dụ như Sai số Tuyệt đối Trung bình (Mean Absolute Error - MAE). Sai số càng thấp, độ thích nghi càng cao. Chúng ta có thể sử dụng hàm compute_loss từ 1 làm cơ sở: $fitness = 1 / (loss + \epsilon)$, trong đó $\epsilon$ là một số rất nhỏ để tránh chia cho không.

  3. Các toán tử: Các toán tử di truyền (khởi tạo, lai ghép, đột biến) sẽ được điều chỉnh để làm việc với số thực thay vì bit. Ví dụ, đột biến có thể là cộng một giá trị ngẫu nhiên nhỏ (từ phân phối Gaussian) vào một gen.

Bằng cách này, GA có thể tìm kiếm trong không gian tham số liên tục để tìm ra các hệ số $a$ và $b$ tối ưu mà không cần sử dụng các phương pháp dựa trên giải tích như Gradient Descent.

5. Kết luận

Tính linh hoạt của GA đã mở ra một loạt các ứng dụng ấn tượng trong nhiều lĩnh vực khác nhau, như được liệt kê trong:

• Tối ưu hóa tổ hợp: Giải quyết các bài toán NP-khó như Bài toán Người du lịch (Traveling Salesman Problem - TSP) và Bài toán Cái túi (Knapsack Problem).

• Kỹ thuật và Thiết kế: Tự động thiết kế các cấu trúc phức tạp như ăng-ten cho NASA, kết cấu cầu, và mạch điện tử.

• Trí tuệ Nhân tạo và Game: Huấn luyện các tác nhân (agents) trong game, tạo ra nội dung game theo thủ tục (procedural content generation), và tìm kiếm kiến trúc mạng nơ-ron tối ưu (Neural Architecture Search).

• Nghệ thuật sáng tạo: Các ứng dụng độc đáo như nghệ thuật tiến hóa (Evolutionary Art) và sáng tác nhạc jazz tự động (GenJam), nơi máy tính và con người hợp tác để tạo ra các tác phẩm nghệ thuật.

Refernces

[1] Ảnh được lấy từ tài liệu khóa học AIO Module 05 Tuần 03