Ứng dụng Giải thuật Di truyền (Genetic Algorithm - GA) vào một bài toán cụ thể

Nội dung mô tả chi tiết về Giải thuật Di truyền (Genetic Algorithm - GA), bao gồm quy trình cơ bản và hai ví dụ ứng dụng: Bài toán One-max và Tìm kiếm Chuỗi Ký tự Mục tiêu.

I. Tổng quan về Giải thuật Di truyền (GA)

Trong tự nhiên, sự sống không phát triển một cách ngẫu nhiên. Mối loài sinh vật phải thích nghi để tồn tại, và những đặc điểm giúp chúng sinh tồn sẽ được di truyền qua các thế hệ. Quá trình này được gọi là chọn lọc tự nhiên (natural selection) - theo thuyết tiến hóa do Darwin đề xuất.

Và ý tưởng này từ lâu đã truyền cảm hứng cho các nhà khoa học khi họ đang tìm những giải pháp tối ưu (mô phỏng quá trình tiến hóa) cho thuật toán, tương tự như cách tự nhiên chọn lọc sinh vật mạnh nhất.

Đó chính là ý tưởng đằng sau sự ra đời của Giải thuật di truyền (Genetic Algorithm) - một nhánh của Evolutionary Computation, nơi mà các giải pháp được “sinh ra, lai tạo và đột biến” đề ngày càng tốt hơn qua từng thế hệ.

1. Giải thuật Di truyền

• Là kỹ thuật tìm kiếm ngẫu nhiên mô phỏng quá trình tiến hóa tự nhiên.
• Là một phương pháp tối ưu hóa được lấy từ cảm hứng từ quá trình tiến hóa sinh học.

GA không tìm lời giải theo cách tuyến tính hay phương trình cụ thể. Thay vào đó nó duy trì một quần thể (population), gồm nhiều các cá thể/ giải pháp tiềm năng (candidate solutions), và thông qua các bước chọn lọc (selection), lai tạo (crossover), đột biến (mutation), các cá thể tốt hơn dần xuất hiện theo thời gian.

Sự tương đồng giữa Sinh học và Giải thuật Di truyền (GA)

2. Lý do GA hiệu quả

Các phương pháp tối ưu hóa cổ điển thường cần gradient hoặc hàm mục tiêu, điều mà nhiều bài toán thực tế khó có thể xây dựng.

Trong khi đó, GA không cần thông tin đạo hàm, cũng không cần biết trước cấu trúc hàm. Nó chỉ cần đánh giá độ tốt của mỗi giải pháp và để quần thể “tiến hóa” tự tìm lời giải tối ưu.

3. Một số ứng dụng điển hình

• Tối ưu lộ trình giao hàng (Route planning and logistics).
• Tối ưu tham số mạng nơ-ron (Neural network hyperparameters tuning).
• Phân lịch, phân bổ tài nguyên (Resource allocation).
• Tối ưu hóa chiến thuật game (Game strategy optimization).
• Tối ưu hóa thiết kế kỹ thuật (Engineering design optimization).

4. Các bước cơ bản khi thực hiện Genetic Algorithm

Mục tiêu: Tìm giải pháp tối ưu cho một bài toán.

Quy trình cơ bản:
Minh hoạ quy trình cơ bản của giải thuật di truyền:
- Khởi tạo quần thể ban đầu, đánh giá độ thích nghi bằng hàm f(x), sau đó chọn lọc để hình thành nhóm cha–mẹ.
- Từ nhóm này, ta thực hiện lai ghép (crossover) và đột biến (mutation) để tạo thế hệ con, đồng thời có thể giữ lại một số cá thể ưu tú (elitism).
- Vòng lặp tiếp tục qua nhiều thế hệ cho đến khi thoả điều kiện dừng (đủ số thế hệ, đạt ngưỡng fitness, hoặc không còn cải thiện).

1. Khởi tạo quần thể ban đầu (initialization)

• Trước tiên, chúng ta khởi tạo quần thể ban đầu (Initial Population) gồm nhiều cá thể, mỗi cá thể là một chuỗi nhị phân với các gene có giá trị 0 hoặc 1, như minh họa trong Hình 2.
• Ví dụ, khởi tạo 4 cá thể ban đầu, mỗi cá thể là một hàng gồm nhiều ô, mỗi ô đại diện cho một gene, chứa giá trị nhị phân.

2. Đánh giá độ thích nghi (fitness)
   - Để xác định cá thể nào “tốt hơn”, ta cần một hàm đánh giá độ thích nghi (fitness function).
   - Mỗi cá thể sẽ được chấm điểm dựa trên mức độ phù hợp với bài toán. Trong bài toán One-Max, độ thích nghi fitness sẽ bằng số lượng gene 1 trong chuỗi.

3. Chọn lọc cá thể tốt (Selection)

• Sau khi đã tính toán giá trị fitness cho từng cá thể trong quần thể, bước tiếp theo là chọn lọc ra các cá thể tốt nhất để đưa vào Selection Pool, đây là nhóm các cá thể sẽ tham gia lai ghép và đột biến trong bước tiếp theo.
• Cách chọn lọc diễn ra như sau:
  1. Ngẫu nhiên chọn 2 cá thể từ quần thể hiện tại.
  2. So sánh giá trị fitness của 2 cá thể này.
  3. Giữ lại cá thể có fitness cao hơn.

  Cứ chọn như thế cho tới khi đạt đủ cá thể trong selection pool.

4. Lai ghép (crossover) và Đột biến (mutation)
   - Trong bước này, các cá thể tinh anh trong Selection Pool sẽ được bắt cặp để tạo ra thế hệ con mới. Quá trình lai ghép giúp các cá thể con kế thừa đặc điểm tốt từ cả cha lẫn mẹ.

• Crossover mô phỏng sự trao đổi chéo giữa các nhiễm sắc thể trong sinh học, như minh họa trong Hình trên. Qua đó, một phần gen của cá thể cha được trộn lẫn với gen của cá thể mẹ để tạo nên cá thể con mới.
• Chúng ta sẽ áp dụng cơ chế này nhưng không chỉ dừng lại ở trao đổi tại 1 điểm, ta hoàn toàn có thể tăng số lượng điểm được trao đổi lên nhiều hơn, như hình minh hoạ sau:

• Tuy nhiên, để mô phỏng tự nhiên hơn, tức là gen có thể hoán đổi ở bất kỳ vị trí nào với một xác suất nhất định, chúng ta sử dụng phương pháp Uniform Crossover.

• Cách hoạt động của Uniform Crossover diễn ra như sau:
  1. Xác định trước một tỉ lệ hoán đổi (ví dụ là 0.5).
  2. Với mỗi vị trí trong chuỗi gen: Sinh ra một số ngẫu nhiên trong khoảng [0, 1], và nếu số đó nhỏ hơn hoặc bằng tỉ lệ cho trước (theo ví dụ là 0.5) thì thực hiện hoán đổi gene giữa hai cá thể tại vị trí đó.

5. Lặp lại cho đến khi đạt điều kiện dừng

• Quan sát hình trên, ta thấy cá thể x1 có một số gene bị đột biến (các ô màu đỏ). Vì bài toán đang sử dụng chuỗi nhị phân (chỉ gồm 0 và 1), nên quy tắc đột biến rất đơn giản: nếu gene là 0 thì đổi thành 1; nếu gene là 1 thì đổi thành 0.
• Tác động của đột biến được minh họa rõ hơn trong Hình 12b, x1 ban đầu đang ở vùng cực đại cục bộ (local), tuy là điểm tốt nhưng chưa phải tốt nhất, và nhờ bị đột biến, x1 trở thành x ′ 1 và nằm ở vùng cực đại toàn cục (global), giúp giải thuật tìm ra lời giải tốt hơn. Trong bước này, để mô phỏng việc đột biến, ta thực hiện tương tự như các bước trong Crossover.
• Đầu tiên, chọn trước một ngưỡng, ví dụ mutation rate = 0.05.
• Kế tiếp, tiến hành lấy các giá trị ngẫu nhiên trong khoảng từ [0, 1] cho các vị trí, nếu vị trí nào có giá trị thấp hơn hoặc bằng ngưỡng thì thực hiện đột biến tại vị trí đó.
  Quá trình này được minh họa như hình dưới:

II. Ứng dụng 1: Bài toán One-max

Mục tiêu: Tìm chuỗi nhị phân có nhiều gene 1 nhất.
- Fitness: Số lượng gene 1.
- Selection: Chọn cá thể có fitness cao.
- Crossover: Hoán đổi gene giữa cha mẹ (Uniform crossover).
- Mutation: Lật bit ngẫu nhiên để duy trì đa dạng.

🔗 Mở Code trên Google Colab
Bước 1: Khởi tạo và Cài đặt Tham số

import torch
import torch.nn as nn
import numpy as np
import pandas as pd
import random
import matplotlib.pyplot as plt

# Tham số của giải thuật
POP_SIZE = 10          # Kích thước quần thể
GENE_LENGTH = 10       # Độ dài mỗi cá thể (số gene)
MUTATION_RATE = 0.1    # Xác suất đột biến
N_GENERATIONS = 30     # Số thế hệ tiến hóa

np.random.seed(42)

Bước 2: Khởi tạo Quần thể Ban đầu

def initialize_population(POP_SIZE, GENE_LENGTH):
    """Tạo quần thể ban đầu gồm các cá thể ngẫu nhiên (0/1)."""
    return np.random.randint(0, 2, (POP_SIZE, GENE_LENGTH))

population = initialize_population(POP_SIZE, GENE_LENGTH)
print("Initial Population\n", population)

Bước 3: Đánh giá Độ Thích nghi (Fitness Function)

def fitness(individual):
   """Độ thích nghi = Tổng số lượng bit 1."""
   return np.sum(individual)

Bước 4: Chọn Lọc (Selection)

def selection(population, num_selection):
  """Chọn ra các cá thể có fitness cao nhất."""
  fitness_values = np.array([fitness(ind) for ind in population])
  selected_indices = np.argsort(fitness_values)[-num_selection:]
  return population[selected_indices]

Bước 5: Lai Ghép (Crossover)

def crossover(parent1, parent2):
  """Lai ghép hai cá thể cha mẹ tại điểm cắt ngẫu nhiên."""
  point = np.random.randint(1, GENE_LENGTH - 1)
  child1 = np.concatenate((parent1[:point], parent2[point:]))
  child2 = np.concatenate((parent2[:point], parent1[point:]))
  return child1, child2

Bước 6: Đột Biến (Mutation)

def mutate(individual, MUTATION_RATE):
  """Đảo bit ngẫu nhiên với xác suất MUTATION_RATE."""
  for i in range(len(individual)):
      if np.random.rand() < MUTATION_RATE:
          individual[i] = 1 - individual[i]
  return individual

Bước 7: Vòng Lặp Tiến Hóa (Main Loop)

population = initialize_population(POP_SIZE, GENE_LENGTH)
print("Initial Population\n", population)
num_selection = 5
loss = []
for gen in range(N_GENERATIONS):
  fitness_score = np.array([fitness(ind) for ind in population])
  best_fitness = np.max(fitness_score) # Get the best fitness score
  best_individual = population[np.argmax(fitness_score)]
  print(f"Thế hệ {gen+1:02d}: Tốt nhất = {best_fitness}, Cá thể = {best_individual}")
  loss.append(best_fitness)
  if best_fitness == GENE_LENGTH:
    break

  parents = selection(population, num_selection)

  new_population = []
  while len(new_population) < POP_SIZE:
    p1, p2 = parents[np.random.randint(0, 5)], parents[np.random.randint(0, 5)]
    child1, child2 = crossover(p1, p2)
    child1 = mutate(child1, MUTATION_RATE)
    child2 = mutate(child2, MUTATION_RATE)
    new_population.extend([child1, child2])
  population = np.array(new_population[:POP_SIZE])

Mục tiêu (Fitness Tối đa):
Theo tham số của bài toán, GENE_LENGTH = 10, nghĩa là giá trị fitness tối đa (giải pháp tốt nhất) là 10 (chuỗi [1 1 1 1 1 1 1 1 1 1]).
Tốc độ Hội tụ:
Giải thuật đã tìm ra lời giải tối ưu (Tốt nhất = 10) chỉ sau 7 thế hệ (Thế hệ 07). Đây là một tốc độ hội tụ nhanh, cho thấy sự kết hợp của Chọn lọc, Lai ghép và Đột biến đã hoạt động hiệu quả trong việc khai thác các đặc điểm tốt (bit '1') từ các cá thể ban đầu.
Sự Cải thiện qua các Thế hệ
Sự cải thiện của giá trị fitness tốt nhất qua các thế hệ diễn ra rõ ràng:

• Lai ghép (Crossover): Đóng vai trò chính trong việc kết hợp các đoạn chuỗi có nhiều bit '1' từ các cha mẹ tốt để tạo ra các cá thể con có fitness cao hơn (ví dụ: chuyển từ 7 lên 8, và từ 8 lên 9).

• Đột biến (Mutation): Rất quan trọng, đặc biệt là ở những bước nhảy nhỏ (ví dụ từ 9 lên 10). Đột biến giúp lật các bit '0' còn sót lại thành '1', đẩy cá thể tốt nhất vượt qua ngưỡng local optima để đạt tới global optima.

Bước 8: Trực Quan Hóa Quá Trình Tiến Hóa

plt.plot(loss, marker='o')
plt.title("Tiến trình tối ưu hóa bằng Giải thuật Di truyền (GA)")
plt.xlabel("Thế hệ (Generation)")
plt.ylabel("Giá trị Fitness tốt nhất")
plt.grid(True)
plt.show()

• Quá trình tăng Fitness không diễn ra tuyến tính mà theo các bước nhảy gián đoạn, phản ánh bản chất của Giải thuật Di truyền (GA):

III. Ứng dụng 2: Bài toán Tìm kiếm Chuỗi Ký tự

🔗 Mở Code trên Google Colab

Mô tả bài toán:
Cho trước một chuỗi mong muốn (target string), yêu cầu là tạo 1 chuỗi tương ứng khác sao cho giống với chuỗi mong muốn, biết rằng khởi điểm ban đầu của chuỗi này sẽ là 1 dãy ngẫu nhiên ký tự (random string) có dùng độ dài (same length).
Đối với bài toán này, chúng ta sẽ:
- Coi gene là các ký tự A-Z, 0-9 và các ký tự đặc biệt khác.
- Coi chromosome/individual là một chuỗi được tạo ra bởi các ký tự.

Sơ đồ thuật toán::

Giải thích sơ đồ thuật toán:

- Khởi đầu và thiết lập: Thuật toán bắt đầu bằng việc định nghĩa các tham số: POPULATION_SIZE = 100, tập GENES gồm các ký tự có thể dùng, và TARGET = "I love u! :3". Mục tiêu của Genetic Algorithm là tiến hóa dần các chuỗi ngẫu nhiên để khớp hoàn toàn với TARGET.
- Tạo quần thể ban đầu: Thuật toán khởi tạo 100 chromosomes, mỗi chromosome là một chuỗi ký tự ngẫu nhiên có độ dài bằng TARGET. Đây là thế hệ đầu tiên, nơi mọi lời giải còn ngẫu nhiên và kém chất lượng.
- Đánh giá fitness: Mỗi cá thể được đánh giá bằng fitness function, đo số ký tự khác biệt so với TARGET. Cá thể càng giống mục tiêu thì fitness càng tốt, được xem là “thích nghi” hơn trong quần thể.
- Kiểm tra điều kiện dừng: Nếu có cá thể đạt fitness = 0, nghĩa là chuỗi hoàn toàn khớp với TARGET, thuật toán dừng lại và in kết quả. Nếu không, quá trình tiến hóa tiếp tục.
- Chọn lọc: Quần thể được sắp xếp theo fitness, giữ lại 10% cá thể tốt nhất cho thế hệ sau, và chọn 50% cá thể hàng đầu để làm cha mẹ – chuẩn bị cho bước lai ghép.
- Lai ghép: Các cặp cha mẹ được lai gene-by-gene, mỗi ký tự được chọn từ cha hoặc mẹ theo xác suất. Mục tiêu là kết hợp ưu điểm của cả hai để tạo ra offspring có khả năng “sống sót” tốt hơn.
- Tạo thế hệ con: Mỗi offspring được thêm vào new_generation cho đến khi đủ số lượng. Quá trình lai ghép tiếp tục lặp lại để hình thành đầy đủ quần thể thế hệ mới.
- Cập nhật quần thể: Khi thế hệ mới hoàn thành, new_generation thay thế quần thể cũ. Các cá thể mới thường có fitness trung bình cao hơn, phản ánh quá trình chọn lọc tự nhiên đang diễn ra.
- Lặp lại cho đến khi quá trình hoàn tất: Thuật toán quay lại bước đánh giá fitness và lặp toàn bộ chu trình qua nhiều thế hệ, cho đến khi tìm được cá thể hoàn toàn khớp với TARGET — đánh dấu sự tiến hóa thành công của Genetic Algorithm.

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

POPULATION_SIZE = 100
GENES = '''abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 1234567890, .-;:_!"#%&/()=?@${[]}'''
TARGET = "I love u! :3"
class Individual(object):
    '''
    Class representing individual in population
    '''
    def __init__(self, chromosome):
        self.chromosome = chromosome
        self.fitness = self.cal_fitness()

    @classmethod
    def mutated_genes(self):
        '''
        create random genes for mutation
        '''
        global GENES
        gene = random.choice(GENES)
        return gene

    @classmethod
    def create_gnome(self):
        '''
        create chromosome or string of genes
        '''
        global TARGET
        gnome_len = len(TARGET)
        return [self.mutated_genes() for _ in range(gnome_len)]

Bước 2: Đánh giá độ thích nghi (Fitness)

    def cal_fitness(self):
        fitness = 0
        for gs, gt in zip(self.chromosome, TARGET):
            if gs != gt:
                fitness += 1
        return fitness

Bước 3: Lai ghép (Crossover)

    def mate(self, par2):
        child_chromosome = []
        for gp1, gp2 in zip(self.chromosome, par2.chromosome):
            prob = random.random()
            if prob < 0.45:
                child_chromosome.append(gp1)
            elif prob < 0.90:
                child_chromosome.append(gp2)
            else:
                child_chromosome.append(self.mutated_genes())
        return Individual(child_chromosome)

Bước 4: Vòng lặp tiến hóa (Main Loop)

def main():
    generation = 1
    found = False
    population = [Individual.create_gnome() for _ in range(POPULATION_SIZE)]
    population = [Individual(gnome) for gnome in population]

    while not found:
        population = sorted(population, key=lambda x: x.fitness)
        if population[0].fitness <= 0:
            found = True
            break

        new_generation = []

        # 10% cá thể tốt nhất giữ nguyên
        s = int(0.1*POPULATION_SIZE)
        new_generation.extend(population[:s])

        # 90% còn lại lai ghép
        s = int(0.9*POPULATION_SIZE)
        for _ in range(s):
            parent1 = random.choice(population[:50])
            parent2 = random.choice(population[:50])
            child = parent1.mate(parent2)
            new_generation.append(child)

        population = new_generation

        print("Generation: {}\tString: {}\tFitness: {}".format(
            generation,
            "".join(population[0].chromosome),
            population[0].fitness
        ))
        generation += 1

if __name__ == "__main__":
    main()

Giai đoạn 1: Tìm kiếm Nhanh (Thế hệ 1 - 16)
Cải thiện Fitness: Fitness giảm nhanh từ 11 xuống 1.
- Gen 1 → Gen 4: Fitness giảm từ 11 → 10
- Gen 5 → Gen 10: Fitness giảm từ 9 → 5
- Gen 11 → Gen 16: Fitness giảm từ 4 → 1
Chuỗi Tốt nhất: Cá thể tốt nhất nhanh chóng tìm được cấu trúc gần đúng là "I love u! :3" với Fitness = 1 (tại Gen 16).
Nhận xét: Cơ chế Lai ghép (Uniform Crossover) đã hoạt động rất hiệu quả, kết hợp các ký tự đúng từ nhiều cha mẹ khác nhau để tạo ra cấu trúc chuỗi chính xác.

Giai đoạn 2: Ổn định và Khai thác (Thế hệ 17 - 45)
- Sự trì trệ (Plateau): Fitness của cá thể tốt nhất giữ ở mức 1 trong suốt 29 thế hệ (Gen 17 → Gen 45).
- Ý nghĩa: Các gen tốt nhất đã lan truyền rộng rãi trong quần thể, nhưng Lai ghép không thể tự tìm ra ký tự sai cuối cùng.
- Vấn đề còn lại: Vẫn còn 1 ký tự sai (hoặc thiếu) so với chuỗi mục tiêu, mà thuật toán không thể khắc phục chỉ bằng cách trộn lẫn các cá thể tốt nhất.

Giai đoạn 3: Đột biến Giải quyết (Thế hệ 46)
- Đột phá: Fitness giảm từ 1 xuống 0 tại Gen 46.
- Nhận xét: Sự chuyển đổi từ Fitness = 1 sang Fitness = 0 gần như chắc chắn nhờ cơ chế Đột biến (Mutation) (xác suất prob ≥ 0.90 trong hàm mate). Đột biến đã ngẫu nhiên thay ký tự sai cuối cùng thành ký tự chính xác, giúp thuật toán thoát khỏi cực tiểu cục bộ (local optima) để đạt tới tối ưu toàn cục (global optimum).

TÓM TẮT GIẢI THUẬT DI TRUYỀN (GA)

Giải thuật Di truyền (GA) là kỹ thuật tối ưu hóa ngẫu nhiên mô phỏng quá trình tiến hóa tự nhiên để tìm kiếm lời giải tốt nhất.
GA hoạt động qua các bước lặp lại trên quần thể cá thể:
- Fitness: Đánh giá độ thích nghi của giải pháp.
- Chọn lọc (Selection): Giữ lại các cá thể tốt hơn làm cha mẹ.
- Lai ghép (Crossover): Kết hợp gen của cha mẹ để truyền đặc điểm tốt.
- Đột biến (Mutation): Thay đổi gen ngẫu nhiên, giúp duy trì đa dạng và thoát khỏi tối ưu cục bộ.

GA là công cụ hiệu quả. Lai ghép dùng để khai thác nhanh các đặc điểm tốt; Đột biến dùng để thăm dò và đảm bảo tìm được giải pháp tối ưu toàn cục.

Reference

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