AI Cho Mọi Người

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.

========================================