AI Cho Mọi Người → Áp dụng GA cho hàm số

AI Cho Mọi Người

Áp dụng GA cho hàm số

Hàm sphere

Ở bài trước, chúng ta đã học các dùng GA để tìm giá trị max của một hàm. Bài này sẽ trình bày các vận dụng GA cho việc tìm min cho một hàm số. Cụ thể, chúng ta sẽ tìm giá trị min cho hàm sphere có công thức là \(f(x) = x_1^2 + x_2^2 + x_3^2 + x_4^2 + x_5^2 + x_6^2\), trong đó \(x_i \in R\) và \(x_i \in [-20, 20]\).

Vài điểm chú ý trước khi cài đặt

1) Do các biến \(x_1\) có kiểu số thực, nên số điểm trong không gian tìm kiếm là vô hạn. Gen của chromosome được biểu diễn bằng kiểu floating-point.

2) Hàm \(f(x)\) có 6 biến. Do đó, độ dài của chromosome là 6 (n = 6).

3) Chúng ta cần phân biệt hai nhóm thuật ngữ. Nhóm 1 gồm fitness và accuracy. Nhóm 2 gồm loss, error, và cost. Nhóm 1 thường gắn liền với bài toán tìm max, và nhóm 2 thường đi với bài toán tìm min. Đối với một thuật toán hay một hệ thống, giá trị fitness và accuracy càng lớn càng tốt; và giá trị loss, error, và cost càng nhỏ càng tốt. GA ở bài trước được thế kế để tìm max. Vì thế, khi dùng GA để tìm min, chúng ta cần chú ý chỗ hàm tính fitness.

Từ các điểm thảo luận ở trên, việc áp dụng GA để tìm min cho hàm sphere cần chỉnh sửa code ở những chỗ sau

– Viết lại hàm generate_random_value() để sinh ra số thực trong khoảng [-20, 20].

– Viết lại hàm compute_fitness()

– Chỉnh lại giá trị tham số của GA cho phù hợp

Source code áp dụng GA cho hàm sphere như sau

# aivietnam.ai - sphere
import random

n = 6                 # size of individual (chromosome)
m = 50                # size of population
n_generations = 100    # number of generations

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

def generate_random_value(bound = 20):
    return (random.random()*2 - 1)*bound

def compute_loss(individual):
    return sum(gen*gen for gen in individual)

def compute_fitness(individual):
    loss =  compute_loss(individual)
    fitness = 1 / (loss + 1)
    return fitness

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:
        losses.append(compute_loss(sorted_population[m-1]))
        print("Best loss:", compute_loss(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 chạy như sau

Ước lượng giá nhà (phiên bản đơn giản)

Trong phần này, chúng ta sẽ giải bài toán ước lượng giá nhà dùng GA. Cho trước bộ dữ liệu định giá nhà dựa vào diện tích nhà như sau

Các bạn có thể download file data.csv ở link sau đây

Bộ dữ liệu này có 10 mẫu và có 2 cột. Cột 1 là diện tích, và cột 2 là giá nhà. Biểu diễn dữ liệu này lên đồ thị ta được như sau

Yêu cầu bài toán đặt ra là đựa vào dữ liệu cho trước, hãy dự đoán giá nhà khi diện tích là 800 \(m^2\).

Quan sát đồ thị chúng ta thấy rằng sự phân bố của dữ liệu xấp xỉ với một đoạn thẳng. Do đó, chúng ta giả sử phân bố của dữ liệu có dạng price = a*area + b, trong đó a và b là hai giá trị cần tìm. Với mỗi giá trị cụ thể a và b, chúng ta có thể tính được độ lệch giữa giá thực tế và giá ước lượng. Ví dụ, cho a = 1.4 và b = 2.0, độ lệch được minh họa ở hình sau

Với mỗi giá trị area trong bộ dữ liệu cho trước, chúng ta tính được giá ước lượng dựa vào công thức price = 1.4*area + 2.0. Sau đó, so sánh giữa giá ước lượng và giá trong bộ dữ liệu ta được độ lệch về giá cho từng mẫu.

Hình sau minh họa độ lệch về giá với các giá trị tham số a và b khác nhau

Source code

# aivietnam.ai - estimation of house prices
import random

n = 2                  # size of individual (chromosome)
m = 100                # size of population
n_generations = 2000   # number of generations
losses = []            # để vẽ biểu đồ quá trình tối ưu

# Hàm load data
def load_data():
    # kết nối với file
    file = open('data.csv','r')

    # readlines giúp việc đọc file theo từng dòng , mỗi dòng là 1 chuỗi
    lines = file.readlines()
    
    areas  = []
    prices = []
    for i in range(10): 
        string = lines[i].split(',')
        areas.append(float(string[0]))
        prices.append(float(string[1]))

    # Đóng kết nối với file
    file.close()
    
    return areas, prices

# load data
areas, prices = load_data()

def generate_random_value(bound = 200):
    return (random.random()-0.5)*bound

def compute_loss(individual):
    result = 65534
    
    a = individual[0]
    b = individual[1]    
    estimated_prices = [a*x + b for x in areas]
    
    # all prices should be positive numbers
    num_negetive_prices = sum(p < 0 for p in estimated_prices)
    if num_negetive_prices == 0:        
        losses = [abs(y_est-y_gt) for y_est, y_gt in zip(estimated_prices, prices)]
        result = sum(losses)
    
    return result

def compute_fitness(individual):
    loss = compute_loss(individual)
    fitness = 1 / (loss + 1)
    return fitness

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:
        losses.append(compute_loss(sorted_population[m-1]))
        #print("Best loss:", compute_loss(sorted_population[m-1]), 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)

Hình sau hiển thị giá trị loss qua các generation