-
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 Travelling Salesman và Knapsack 0/1
Bạn Hoàng Trường Phước chia sẻ code áp dụng GA cho bài toàn Travelling Salesman và Knapsack 0/1. Các bạn có thể download source code ở link sau
https://www.dropbox.com/s/k6uneilhblkq4uq/salesman_travelling.zip?dl=0
https://www.dropbox.com/s/ohuadh1l5u8ukpr/knapsack.zip?dl=0
Travelling Salesman
Phát biểu bài toán như sau: Có 5 thành phố được đánh số từ 1 đến 5, được nối với nhau như hình vẽ. Một người muốn đi từ một thành phố, qua tất cả các thành phố khác và trở về thành phố ban đầu với chi phí nhỏ nhất. Hãy thiết lập tuyến đường cho người này.
Dữ liệu mô tả các thành phố và chi phí giữa chúng là một mảng 2 chiều; dòng và cột đầu tiên là tên các thành phố. Các giá trị còn lại biểu diễn chi phí đi lại của hai thành phố tương ứng. Với những thành phố không nối trực tiếp với nhau, ta cho chi phí là một số lớn.
import random n = 5 # so luong thanh pho m = 100 # so luong ca the trong quan the n_generations = 100 # so vong doi losses = [] # de ve bieu de losses # load data def load_data(): map = [] file = open('data_route.txt', 'r') lines = file.readlines() # bo header for i in range(1, len(lines)): strings = lines[i].split(',') # bo cot dau tien prices = [int(s.strip()) for s in strings[1:]] map.append(prices) file.close() return map map = load_data() print('load_data') print(map) # tao individual def create_individual(): # list cac thanh pho return [random.randint(1,n) for _ in range(n)] # tinh loss def compute_loss(individual): i = 0 price = 0 while i < n-1: a = individual[i] - 1 b = individual[i+1] - 1 price += map[a][b] i += 1 # cong voi quang duong tp cuoi ve tp dau start = individual[0] - 1 finish = individual[n-1] - 1 price += map[finish][start] # Kiem tra xem individual co chua het thanh pho khong s = set(individual) price += ((n-len(s)) * 1000) return price # tinh fitness def compute_fitness(individual): loss = compute_loss(individual) return 1 / (1 + loss) # chon loc def selection(sorted_population): index1 = random.randint(0, m-1) while True: index2 = random.randint(0, m-1) if index2 != index1: break individual = sorted_population[index1] if index2 > index1: individual = sorted_population[index2] return individual # lai ghep: 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 # dot bien def mutate(individual, mutation_rate = 0.05): individual_m = individual.copy() for i in range(n): if random.random() < mutation_rate: individual_m[i] = random.randint(1,n) return individual_m # tao quan the moi def create_new_population(soted_old_population): # luu vao losses losses.append(compute_loss(sorted_old_population[-1])) # in cac gia tri tot nhat qua tung doi # print(losses[-1]) new_population = [] while len(new_population) < m-2: # chon loc individual1 = selection(sorted_old_population) individual2 = selection(sorted_old_population) # lai ghep individual_c1, individual_c2 = crossover(individual1, individual2) # dot bien individual_m1 = mutate(individual_c1) individual_m2 = mutate(individual_c2) # cho vao quan the moi new_population.append(individual_m1) new_population.append(individual_m2) # cho 2 con dep nhat cua quan the cu vao quan the moi new_population.append(sorted_old_population[-1]) new_population.append(sorted_old_population[-2]) return new_population # tao quan the ban dau population = [create_individual() for _ in range(m)] for _ in range(n_generations): sorted_old_population = sorted(population, key = compute_fitness) population = create_new_population(sorted_old_population) # hien thi tuyen duong ngan nhat route_min = sorted_old_population[-1] route_min.append(sorted_old_population[-1][0]) print('duong di ngan nhat: ', route_min, 'chi phi: ', losses[-1])
Kết quả một lần chạy mẫu
Knapsack 0/1
Đây là bài toán thú vị và rất phù hợp với GA. Phát biểu bài toán như sau: có n = 12
vật có giá trị và cân nặng cho trước. Hãy để n
vật này vào một cái túi có sức chứa tối đa max_weight = 70 kg
sao cho giá trị trong chiếc túi là lớn nhất.
(Bài toán không nhất thiết cố định độ n và max_weight. Tuy nhiên, việc mở rộng 2 tham số trên rất đơn giản.)
import random n = 12 # so luong vat m = 1000 # so luong ca the trong quan the n_generations = 1000 # so doi fitnesses = [] # de ve do thi fitnesses max_weight = 70 # khối lượng tối đa cái túi có thể đựng được # cho truoc du lieu weights = [1, 2, 5, 7, 10, 12, 15, 23, 32, 33, 35, 37] # can nang cac vat prices = [1, 3, 6, 7, 12, 15, 25, 32, 44, 45, 47, 50] # gia tri cua cac vat tuong ung # tao gia tri gen ngau nhien def generate_random_value(): return random.randint(0, 1) # tinh fitness def compute_fitness(individual): fitness = sum(c*x for c, x in zip(individual, prices)) # kiem tra xem individual co vuot qua khoi luong khong if compute_weight(individual) > max_weight: # penalty fitness /= 1000 return fitness # tinh can nang def compute_weight(individual): sum_weight = sum(c*x for c, x in zip(individual, weights)) return sum_weight # tao nhiem sac the def create_individual(): return [generate_random_value() for _ in range(n)] # lua chon def selection(sorted_population): index1 = random.randint(0, m-1) while True: index2 = random.randint(0, m-1) if index2 != index1: break individual = sorted_population[index1] if index1 < index2: individual = sorted_population[index2] return individual # lai ghep def crossover(individual1, individual2, crossover_rate = 0.9): individual_c1 = individual1.copy() individual_c2 = individual2.copy() # point crossover if random.random() < crossover_rate: index = random.randint(1, n - 2) for i in range(index): individual_c1[i] = individual2[i] individual_c2[i] = individual1[i] return individual_c1, individual_c2 # dot bien def mutate(individual, mutation_rate = 0.05): individual_new = individual.copy() if random.random() < mutation_rate: index = random.randint(0, n-1) individual_new[index] = generate_random_value() return individual_new # tao quan the moi def create_new_population(old_popuation): sorted_old_popuation = sorted(old_popuation, key = compute_fitness) fitnesses.append(compute_fitness(sorted_old_popuation[-1])) #print('fitness', fitnesses[-1]) new_population = [] while len(new_population) < m - 2: # chon loc individual1 = selection(sorted_old_popuation) individual2 = selection(sorted_old_popuation) # lai ghep individual_c1, individual_c2 = crossover(individual1, individual2) # dot bien individual_m1 = mutate(individual_c1) individual_m2 = mutate(individual_c2) # cho vao quan the moi new_population.append(individual_m1) new_population.append(individual_m2) new_population.append(sorted_old_popuation[-1]) new_population.append(sorted_old_popuation[-2]) return new_population # tao quan the ban dau population = [create_individual() for _ in range(m)] for _ in range(n_generations): population = create_new_population(population) sorted_population = sorted(population, key = compute_fitness) print('cach cho do vao: ', sorted_population[-1]) print('khoi luong: ', compute_weight(sorted_population[-1])) print('gia tri: ', compute_fitness(sorted_population[-1]))
Bài đóng góp từ bạn Hoàng Trường Phước
AIVIETNAM cám ơn sự đóng góp của bạn.
========================================