AI Cho Mọi Người

AI Cho Mọi Người

Genetic algorithm (GA)

 

 

Giải thuật di truyền (GA) là giải thuật tìm kiếm dựa vào ngẫu nhiên và phù hợp cho các bài toán NP-hard. GA hiện được dùng rộng rãi trong rất nhiều lĩnh vực để tối ưu giá trị cho bộ tham số của một hệ thống hay một phương pháp.

Ở bài này, chúng ta sẽ học GA, gắn với việc giải quyết bài toán one-max. GA dùng các thuật ngữ bên di truyền học để mô tả các thành phần và hành vi. Bài trước chúng ta dùng vector với chiều dài n để mô tả một thể hiện (hay trạng thái) cụ thể. GA dùng thuật ngữ chromosome (cá thể) để chỉ một thể hiện cho không gian lời giải. Mỗi vị trí trong chromosome được gọi là gen, và mỗi chromosome có n gen. Hình sau minh họa population, chromosome và gen.

GA bao gồm 3 bước chính là selection (chọn lọc), crossover (lai ghép) và mutation (đột biến) được mô tả ở hình vẽ sau

trong đó
– Selection: chọn lọc những cá thể có fitness (hay score) tốt để lai ghép và đột biến
– Crossover: Trao đổi gen giữa hai cá thể
– Mutation: đột biến gen của một cá thể

Ngoài ra còn có bước population initialization (khởi tạo quần thể) nhằm tạo ngẫu nhiên quần thể ban đầu. Bước evaluation có mục đích để tính giá trị fitness cho các cá thể. Tương tự như random search, GA không quan tâm đến cách thức tính fitness cho một cá thể, mà chỉ cần biết thông tin input và output. Ba bước chính của GA sẽ được lặp đi lặp lại cho đến khi nào điều kiện dừng được thỏa mãn. Điều kiện dừng có thể là số lần lặp (generation), tính bão hòa của giá trị max_fitness, hay sự hội tự của quần thể (các cá thế có fitness gần giống nhau).

Sau đây chúng ta sẽ đi vào chi tiết từng bước và minh họa bằng bài toán one-max.

Population initialization

Ở bước này, dựa vào thông tin số cá thể m và số gen của một cá thể n, quần thể gồm m cá thể được khởi tạo với các giá trị ngẫu nhiên. Hình sau minh họa giá trị khởi tạo một quần thể với m = 10n = 6.

Source code cho bước này như sau

Evaluation

Ở bước này, GA sử dụng một hàm được cung cấp sẵn để tính fitness cho từng cá thể. Với bài one-max, hàm cung cấp sẵn chính là hàm secret(), nhận input là một cá thể và output là giá trị fitness của cá thể đó. GA không biết nội dung bên trong của hàm secret() mà chỉ biết chuẩn input và giá trị output. Minh họa bước tính fitness cho quần thể ở hình sau

Selection

Dựa vào giá trị fitness của mỗi cá thể, bước selection sẽ chọn ra một tập hợp các cá thể có fitness tốt nhất. Nguyên tắc chọn là cá thể nào có fitness càng cao thì khả năng cá thể đó sẽ được chọn càng nhiều lần. Có nhiều phương pháp selection trong GA, và ở bài này chúng ta sẽ áp dụng phương pháp binary selection. Binary selection hoạt động như sau: lấy ngẫu nhiên hai cá thể trong quần thể, cá thể nào có fitness tốt hơn thì được chọn.

Nói cách khác, giả sử các cá thể trong quần thể được đánh giá trị index (từ 0 đến 9 cho 10 cá thể). Để chọn ra được một cá thể tốt, chúng ta sẽ sinh ra hai số ngẫu nhiên \(i_1\) và \(i_2\) nằm trong đoạn [0, 9]. Sau đó, lấy hai cá thể vị trí index \(i_1\) và \(i_2\), cá thể nào có fitness cao hơn sẽ được chọn.

Binary selection có thể cài bằng với hai bước: 1) sắp xếp các cá thể theo thứ tự tăng dần với tiêu chí fitness; 2) Sinh ra hai số ngẫu nhiên \(i_1, i_2 \in [0,m-1]\), rồi chọn cá thể có giá trị index lớn hơn. Hình sau minh họa binary selection.

Ví dụ minh họa trên muốn chọn ra hai cá thể tự quần thể hiện tại. Ban đầu, quần thể được sắp xếp theo tứ tự tăng đần của fitness. Sau đó, hai cặp số ngẫu nhiên được sinh ra. Cặp số đầu tiên là (9, 4), nghĩa là giữa hai cá thể ở vị trí index 9 và 4, chọn cá thể tốt hơn. Do quần thể đã được sắp xếp, vị trí index lớn hơn sẽ được chọn. Cuối cùng, cá thể có index 9 được chọn. Tương tự cho cặp số ngẫu nhiên thứ 2 (5, 2), cá thể vị trí index 5 được chọn.

Trong trường hợp chúng ta muốn lựa chọn những cá thể tốt từ quần thể hiện tại để tạo ra một quần thể mới, m cặp số ngẫu nhiên sẽ được sinh ra nhằm chọn ra được m cá thể cho quần thể mới. Hình sau mình họa quá trình tạo quần thể mới.

Chúng ta thấy được rằng ở quần thể mới, những cá thể tốt nhất ở quần thể cũ được giữ lại và những cá thể có fitness nhỏ được loại bỏ. Điều này có ý nghĩa rằng qua quá trình tiến hóa, chúng ta mong muốn những cá thể tốt với nhiều gen tốt sẽ được giữ lại và lan tỏa ra quần thể.

Source code cho bước này như sau

Crossover

Crossover nhắm lai ghép giữa hai cá thế. Cụ thể, hai cá thể có thể trao đổi gen với nhau. Trong bài này, chúng ta sẽ dùng binary crossover để thực hiện việc lai tạo giữa hai cá thể. Binary crossover hoạt động như sau: cho trước xác suất thực hiện crossover cho một gen là \(R_{cr} = 0.9\), sinh ra một boolean vector \(v_{cr}\) có độ dài n, trong đó mỗi phần tử chứa giá trị True hoặc False. Giá trị True cho một vị trí index nghĩa là thực hiện việc trao đổi gen ở vị trí đó giữa hai cá thể. Ví dụ cho \(R_{cr} = 0.9\) nghĩa là việc trao đổi gen cho một vị trí giữa hai cá thể là 90% khả năng. Hình sau minh họa việc trao đổi gen cho trước vector \(v_{cr}\).

Source code cho bước này như sau

Mutation

Mutation nhằm đột biến gen cho một cá thể. Gen cần đột biến sẽ nhận một giá trị ngẫn nhiên nằm trong miền giá trị. Tương tự crossover, mutation cũng cần một boolean vector \(v_{mt}\) để xác định những gen nào cần đột biến. Vector \(v_{mt}\) được sinh ra một cách ngẫu nhiên theo một khả năng mutation \(R_{mt}\) cho trước. Hình sau minh họa việc đột biến cho một cá thể dựa vào vector \(v_{mt}\) cho trước.

Source code cho bước này như sau

GA thường gây hơi khó hiểu cho những bạn mới học lần đầu, vì nó là dạng thuật toán dựa vào quần thể và tiến hóa dần dần. Vì thế chúng ta không nhìn thấy ngay lý do và cách thức GA đạt được kết quả tốt. Nếu các bạn cũng cảm thấy như vậy thì cũng bình thường. Áp dụng GA vào giải khoảng 3 hay 4 bài toán khác nhau, các bạn sẽ hiểu rõ hơn về GA.

Source code cho bài toán one-max dùng GA

# aivietnam.ai - one-max
# Chương trình cài đặt với mục đích dễ hiểu
# Nhiều chỗ có thể cải tiến về mặt computation và memory
import random

n = 20                # size of individual (chromosome)
m = 10                # size of population
n_generations = 40    # number of generations

# để vẽ biểu đồ quá trình tối ưu
fitnesses = []

def generate_random_value():
    return random.randint(0, 1)

def compute_fitness(individual):
    return sum(gen for gen in individual)

def create_individual():
    return [generate_random_value() for _ in range(n)]

def crossover(individual1, individual2, crossover_rate = 0.9):
    individual1_new = individual1.copy()
    individual2_new = individual2.copy()
    
    for i in range(n):
        if random.random() < crossover_rate:
            individual1_new[i] = individual2[i]
            individual2_new[i] = individual1[i]            
    
    return individual1_new, individual2_new

def mutate(individual, mutation_rate = 0.05):
    individual_m = individual.copy()
    
    for i in range(n):
        if random.random() < mutation_rate:
            individual_m[i] = generate_random_value()
        
    return individual_m

def selection(sorted_old_population):    
    index1 = random.randint(0, m-1)    
    while True:
        index2 = random.randint(0, m-1)    
        if (index2 != index1):
            break
            
    individual_s = sorted_old_population[index1]
    if index2 > index1:
        individual_s = sorted_old_population[index2]
    
    return individual_s 

def create_new_population(old_population, elitism=2, gen=1):
    sorted_population = sorted(old_population, key=compute_fitness)
        
    if gen%1 == 0:
        fitnesses.append(compute_fitness(sorted_population[m-1]))
        print("BEST:", compute_fitness(sorted_population[m-1]))      
    
    new_population = []
    while len(new_population) < m-elitism:
        # selection
        individual_s1 = selection(sorted_population)
        individual_s2 = selection(sorted_population) # duplication
        
        # crossover
        individual_c1, individual_c2 = crossover(individual_s1, individual_s2)
        
        # mutation
        individual_m1 = mutate(individual_c1)
        individual_m2 = mutate(individual_c2)
        
        new_population.append(individual_m1)
        new_population.append(individual_m2)            
    
    for ind in sorted_population[m-elitism:]:
        new_population.append(ind.copy())
    
    return new_population

population = [create_individual() for _ in range(m)]
for i in range(n_generations):
    population = create_new_population(population, 2, i)

 

Kết quả cho một lần thử

Chúng ta thấy rằng GA tiến hóa lời giải và  tìm ra giá trị tối ưu ở generation thứ 27 với giá trị max-fitness là 20.