Giải thuật di truyền (Genetic Algorithms)

Giải thuật di truyền (Genetic Algorithm - GA) là một phương pháp tối ưu hóa dựa trên quá trình chọn lọc tự nhiên trong sinh học. GA mô phỏng quá trình tiến hóa để tìm kiếm lời giải tốt nhất cho một bài toán.

Các bước chính trong giải thuật di truyền:

• Chọn lọc tự nhiên – Giữ lại cá thể tốt nhất.
• Lai ghép (crossover) – Kết hợp hai cá thể để tạo thế hệ mới.
• Đột biến (mutation) – Thay đổi nhỏ để tạo sự đa dạng.
• Đánh giá (fitness function) – Xác định độ tốt của cá thể.

Ứng dụng của giải thuật di truyền là tối ưu hóa tham số mạng nơ ron, giải bài toán tổ hợp (người giao hàng, lập lịch, đóng gói), sinh học tính toán (mô phỏng tiến hóa, dự đoán chuổi gen), tối ưu hóa công nghiệp (thiết kế vật liệu, tự động hóa).

Ví dụ cho một bài toán sau: một công ty giao hàng có 5 điểm giao hàng và được đánh số từ 0 đến 4. Người giao hàng phải đi qua tất cả các điểm đúng một lần rồi quay về điểm xuất phát, sao cho tổng quãng đường ngắn nhất.

Dưới đây là bảng khoảng cách giữa các điểm giao hàng

Một lộ trình hợp lệ là một hoán vị của các điểm giao hàng. Ví dụ: [0, 2, 1, 3, 4, 0].

Điểm xuất phát là 0, đi qua các điểm 2 à 1 à 3 à 4 à 0. Để đánh giá một lời giải tốt hay không dựa vào hàm đánh giá (Fitness Function). Trong bài toán này, hàm đánh giá là tổng quãng đường của một lộ trình. Giá trị hàm này càng nhỏ càng tốt. 

Các bước thực hiện thuật toán di truyền:

1. Khởi tạo quần thể

          Tạo một tập hợp N cá thể (N lời giải ngẫu nhiên)

          Ví dụ:

[0, 1, 2, 3, 4, 0]

[0, 3, 1, 4, 2, 0]

[0, 2, 4, 3, 1, 0]

[0, 4, 3, 1, 2, 0]

[0, 1, 3, 2, 4, 0]

2. Đánh giá độ thích nghi (Fitness Function)

Tính tổng quãng đường của từng cá thể trong quần thể. 

Ví dụ tính khoảng cách cho cá thể [0, 1, 2, 3, 4, 0]:

          10+35+30+15+25=115 km

Cá thể nào có tổng quãng đường nhỏ nhơn sẽ có fitness tốt hơn.

3. Chọn lọc (Selection)

Chọn những cá thể tốt nhất để lai ghép. Ví dụ chọn 2 cá thể có quãng đường ngắn nhất để làm cha mẹ. Ví dụ: [0, 2, 1, 3, 4, 0] (95 km) [0, 1, 4, 3, 2, 0] (100 km). 

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

• Roulette Wheel Selection (Tỷ lệ chọn dựa trên fitness).
• Tournament Selection (Chọn nhóm nhỏ, lấy cá thể mạnh nhất).
• Rank-Based Selection (Sắp xếp theo fitness và chọn xác suất).

4. Lai ghép (Crossover)

Lai ghép hai cá thể cha mẹ để tạo ra thế hệ con mới. Một số phương pháp lai ghép:

• One-Point Crossover (Cắt tại một vị trí ngẫu nhiên).
• Two-Point Crossover (Cắt tại hai điểm).
• Uniform Crossover (Ngẫu nhiên lấy gen từ cha hoặc mẹ).
• Order Crossover (OX) (bảo toàn thứ tự các thành phố). 

Trong bài toán này cần bảo toàn thứ tự các thành phố nên sử dụng Order Crossover. 

Giả sử đây là cá thể cha mẹ:

Cha 1: [0, 2, 1, 3, 4, 0]

Cha 2: [0, 1, 4, 3, 2, 0]

Hoán vị vị trí 1 và 3, ta có thế hệ con thừa hưởng đặc điểm cha mẹ nhưng có hoán vị.

Con 1: [0, 1, 2, 3, 4, 0]

Con 2: [0, 2, 4, 3, 1, 0]

5. Đột biến (Mutation)

Ngẫu nhiên thay đổi một số gen để duy trì tính đa dạng di truyền. Xác suất đột biến thường nhỏ (0.01 - 0.1). Ví dụ đồi với một cá thể được biểu diễn nhị phân. Trước đột biến là 11001, sau đột biến là 10001.

Đối với bài toán người vận chuyển, cá thể con [0, 2, 4, 3, 1, 0] sáu khi đột biến hoán vị vị trí ở 2 và 4 là [0, 2, 1, 3, 4, 0]. 

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

Tiếp tục chạy nhiều thế hệ cho đến khi:

• Đạt giá trị tối ưu (fitness đủ cao).
• Không còn cải thiện qua nhiều thế hệ.
• Số vòng lặp đạt giới hạn.

Đối với bài toán của chúng ta, điều kiện dừng là khi hoàn thành 100 thế hệ hoặc không còn cải thiện được kết quả.

Quảng đường tối ưu là: [0, 1, 3, 4, 2, 0] với tổng quãng đường: 85 km

Cài đặt Python cho bài toán:

import random

# Bảng khoảng cách giữa các điểm

distances = [

    [0, 10, 15, 20, 25],

    [10, 0, 35, 25, 30],

    [15, 35, 0, 30, 20],

    [20, 25, 30, 0, 15],

    [25, 30, 20, 15, 0]

]

# Hàm tính tổng quãng đường

def fitness(route):

    return sum(distances[route[i]][route[i+1]] for i in range(len(route)-1))

# Khởi tạo quần thể ngẫu nhiên

def create_population(size):

    population = []

    for _ in range(size):

        route = [0] + random.sample(range(1, 5), 4) + [0]

        population.append(route)

    return population

# Chọn lọc (Tournament Selection)

def selection(population):

    return sorted(population, key=fitness)[:2]

# Lai ghép (Order Crossover)

def crossover(parent1, parent2):

    cut = random.randint(1, 3)

    child1 = parent1[:cut] + [x for x in parent2 if x not in parent1[:cut]] + [0]

    child2 = parent2[:cut] + [x for x in parent1 if x not in parent2[:cut]] + [0]

    return child1, child2

# Đột biến (Swap Mutation)

def mutate(route):

    i, j = random.sample(range(1, 5), 2)

    route[i], route[j] = route[j], route[i]

    return route

# Thuật toán di truyền

def genetic_algorithm(generations=200, population_size=10):

    population = create_population(population_size)

    for _ in range(generations):

        selected = selection(population)

        offspring = []

        for i in range(0, len(selected), 2):

            child1, child2 = crossover(selected[0], selected[1])

            offspring.append(mutate(child1))

            offspring.append(mutate(child2))

        population = selected + offspring

    best_route = min(population, key=fitness)

    return best_route, fitness(best_route)

# Chạy thuật toán

best_path, min_distance = genetic_algorithm()

print(f"Lộ trình tối ưu: {best_path}, Tổng quãng đường: {min_distance} km")