-
Tuần 1 - Ngày 10 tháng 7 năm 2019
- Giới thiệu về khóa học
- Hướng dẫn viết chương trình Python trên web
- Hướng dẫn sử dụng PyCharm
- Tổng quan về Python
- Kỹ năng sử dụng Google search
- Viết tài liệu kỹ thuật dùng Markdown
- Hàm xây dựng sẵn trong Python – math và random
- Cài đặt các công thức toán cơ bản
- Xây dựng hàm trong python
- Điều kiện if-else
- Những lỗi thường gặp trong Python
- Reading assignment
-
Tuần 2 - Ngày 17 tháng 7 năm 2019
-
Tuần 3 - Ngày 24 tháng 7 năm 2019
-
Tuần 4 - Ngày 31 tháng 7 năm 2019
-
Tuần 5 - Ngày 7 tháng 8 năm 2019
-
Advanced Python
-
Tuần 6 - Ngày 14 tháng 8 năm 2019
-
Tuần 7 - Ngày 28 tháng 8 năm 2019
-
Tuần 8
-
Tuần 9
Á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
Kết quả model tiên đoán giá nhà sau khi tối ưu tham số dung GA