Thuật toán di truyền

9.1 Giới thiệu về thuật toán di truyền.

Thuật toán di truyền (GA) là phương pháp tối ưu hóa và tìm kiếm, được lấy cảm hứng từ quá trình chọn lọc tự nhiên, mô phỏng các quy trình tiến hóa sinh học.

Thuật toán di truyền được áp dụng để giải quyết các bài toán phức tạp, nơi mà các phương pháp truyền thống có thể không hiệu quả. Những thuật toán này sử dụng các cơ chế chọn lọc, lai (crossover) và đột biến để tiến hóa các giải pháp.

Nguyên tắc hoạt động:

1. Khởi tạo:

Tạo một quần thể ban đầu của các giải pháp khả thi (nhiễm sắc thể). Mỗi giải pháp được mã hóa dưới dạng chuỗi (chuỗi bit, chuỗi ký tự hoặc các cấu trúc khác).

2. Hàm thích nghi (fitness function):

Đánh giá chất lượng của từng giải pháp trong quần thể.

3. Đánh giá:

Mỗi giải pháp (cá nhân) được đánh giá bằng hàm thích nghi (fitness function), hàm này xác định mức độ giải quyết bài toán của giải pháp.

4. Chọn lọc:

Các giải pháp tốt hơn có cơ hội được chọn để tái tạo. Các phương pháp thường được sử dụng bao gồm chọn lọc bánh xe roulette (roulette wheel selection), chọn lọc đấu trường (tournament selection) và chọn lọc xếp hạng (rank selection).

5. Lai (crossover):

Những giải pháp được chọn (bố mẹ) được kết hợp để tạo ra các giải pháp mới (con cái). Crossover có thể là một điểm, hai điểm hoặc nhiều điểm.

6. Đột biến:

Các thay đổi ngẫu nhiên trong những giải pháp mới (đột biến) được áp dụng để giới thiệu sự đa dạng. Điều này giúp thuật toán tránh khỏi các cực trị cục bộ.

7. Thay thế:

Quần thể mới thay thế quần thể cũ, và quá trình lặp lại cho đến khi điều kiện dừng được thực hiện (ví dụ, đạt được một số lượng thế hệ nhất định hoặc đạt được sự thích nghi nhất định).

Ưu điểm và nhược điểm

Ưu điểm:

• Phạm vi ứng dụng rộng: Có thể áp dụng để giải quyết các bài toán khác nhau, bao gồm cả những bài toán mà các phương pháp phân tích không hoạt động.
• Tối ưu hóa toàn cầu: Có khả năng tìm thấy cực trị toàn cầu trong không gian đa chiều và phức tạp.
• Lin hoạt: Có thể sử dụng với bất kỳ hàm thích nghi nào.

Nhược điểm:

• Chi phí tính toán cao: Yêu cầu nhiều tài nguyên tính toán, đặc biệt cho các quần thể lớn và bài toán phức tạp.
• Khó khăn trong việc điều chỉnh tham số: Chọn các tham số (kích thước quần thể, tỷ lệ đột biến và crossover) có thể khó và ảnh hưởng mạnh đến hiệu suất.
• Không có đảm bảo tìm được giải pháp tối ưu: Không có đảm bảo rằng giải pháp tìm được sẽ là cực trị toàn cầu.

Thực tế, thuật toán di truyền là một phương pháp heuristics hiệu quả cao. Nó không đảm bảo sẽ tìm ra giải pháp tốt nhất, ngay cả khi có truy cập đến tất cả dữ liệu. Nhưng cho các tình huống phức tạp và lượng dữ liệu khổng lồ, nó rất nhanh chóng đưa ra giải pháp gần với lý tưởng.

9.2 Ví dụ ứng dụng

Hãy xem xét một ví dụ sử dụng thuật toán di truyền để tối ưu hóa một hàm.

import random

# Tham số của thuật toán di truyền
POPULATION_SIZE = 100
GENERATIONS = 1000
MUTATION_RATE = 0.01
TOURNAMENT_SIZE = 5
            
# Định nghĩa hàm thích nghi
def fitness_function(x):
    return -x**2 + 10*x
            
# Khởi tạo quần thể
def initialize_population(size):
    return [random.uniform(-10, 10) for _ in range(size)]
            
# Chọn lọc (đấu trường)
def tournament_selection(population):
    tournament = random.sample(population, TOURNAMENT_SIZE)
    return max(tournament, key=fitness_function)
            
# Lai (crossover) một điểm
def crossover(parent1, parent2):
    alpha = random.random()
    return alpha * parent1 + (1 - alpha) * parent2
            
# Đột biến
def mutate(individual):
    if random.random() < MUTATION_RATE:
        return individual + random.gauss(0, 1)
    return individual
            
# Vòng lặp chính của thuật toán di truyền
population = initialize_population(POPULATION_SIZE)
            
for generation in range(GENERATIONS):
    new_population = []
    for _ in range(POPULATION_SIZE):
        parent1 = tournament_selection(population)
        parent2 = tournament_selection(population)
        offspring = crossover(parent1, parent2)
        offspring = mutate(offspring)
        new_population.append(offspring)
    population = new_population
            
# Xuất giải pháp tốt nhất
best_individual = max(population, key=fitness_function)
print("Giải pháp tốt nhất:", best_individual)
print("Giá trị của hàm:", fitness_function(best_individual))
            
        

Ưu điểm và nhược điểm

9.3 Tối ưu hóa hàm đa chiều

Bài toán:

Tìm giá trị nhỏ nhất của một hàm đa chiều.

Giải pháp:

Lấy mẫu từ trước đó

import numpy as np

def fitness_function(x):
    return np.sum(x ** 2)
            
def create_individual(dim):
    return np.random.uniform(-10, 10, dim)
            
def create_population(pop_size, dim):
    return np.array([create_individual(dim) for _ in range(pop_size)])
            
def select_individuals(population, fitness, num_parents):
    parents = np.empty((num_parents, population.shape[1]))
    for parent_num in range(num_parents):
        min_fitness_idx = np.where(fitness == np.min(fitness))
        min_fitness_idx = min_fitness_idx[0][0]
        parents[parent_num, :] = population[min_fitness_idx, :]
        fitness[min_fitness_idx] = float('inf')
    return parents
            
def crossover(parents, offspring_size):
    offspring = np.empty(offspring_size)
    crossover_point = np.uint8(offspring_size[1] / 2)
    for k in range(offspring_size[0]):
        parent1_idx = k % parents.shape[0]
        parent2_idx = (k + 1) % parents.shape[0]
        offspring[k, 0:crossover_point] = parents[parent1_idx, 0:crossover_point]
        offspring[k, crossover_point:] = parents[parent2_idx, crossover_point:]
    return offspring
            
def mutate(offspring, mutation_rate):
    for idx in range(offspring.shape[0]):
        if np.random.rand() < mutation_rate:
            random_value = np.random.uniform(-1.0, 1.0, 1)
            offspring[idx, 4] = offspring[idx, 4] + random_value
    return offspring
            
def genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations):
    population = create_population(pop_size, dim)
    for generation in range(num_generations):
        fitness = np.array([fitness_function(ind) for ind in population])
        parents = select_individuals(population, fitness, num_parents)
        offspring_crossover = crossover(parents, (pop_size - parents.shape[0], dim))
        offspring_mutation = mutate(offspring_crossover, mutation_rate)
        population[0:parents.shape[0], :] = parents
        population[parents.shape[0]:, :] = offspring_mutation
    best_solution = population[np.argmin(fitness)]
    return best_solution
# Ví dụ sử dụng:
dim = 10
pop_size = 100
num_parents = 20
mutation_rate = 0.01
num_generations = 1000
best_solution = genetic_algorithm(dim, pop_size, num_parents, mutation_rate, num_generations)
print(f"Giải pháp tốt nhất: {best_solution}")