In [53]:
import random
In [54]:
# list of items (value/volume pairs)
list_of_items = [(1, 4), (12, 4), (23, 1), (24, 12), (3, 4), (12, 3), (13, 12), (1, 3), (2, 4), (7, 12), (6, 8),
                 (9, 15), (4, 11), (2, 5), (11, 9)]

#first population
population_1 = []

for i in range(1000):
    c = []
    y = 0
    while y<50:
        item = random.choice(list_of_items)
        if item not in c:
            c.append(item)
            for x in c:
                y += x[1]
 
    y = 0
    for x in c:
        y += x[1]
    if y > 50:
        c.pop()
        
    population_1.append(c)
In [55]:
#making a list of values
values = []
for i in population_1:
    val_sum = 0
    for a in i:
        val_sum += a[0]
    values.append(val_sum) 

#combining list of values with population    
population_1_with_values = list(zip(values, population_1))
In [56]:
#sorting population1_with_values
sorted_population_1_with_values = sorted(population_1_with_values, reverse=True)
In [57]:
def evolution (previous_generation, list2):
    
    list1 = []
    for i in range (400):
        list1.append(previous_generation[i])
    
    gametes = []
    for k in range(2):
        
        for i in list1:
            gamete = []
            random.shuffle(i[1])
            gamete.extend(i[1][:3])
    
            if random.randint(0,2) == 1:
                gene = random.choice(list2)
                if gene not in gamete:
                    gamete.append(gene)
            volum = 0
            for i in gamete:
                volum += i[1]
            if volum <= 50:
                gametes.append(gamete)
        
    random.shuffle(gametes)
    for i in list1:
        gamete = []
        random.shuffle(i[1])
        gamete.extend(i[1][:3])
    
        if random.randint(0,2) == 1:
            
            gene = random.choice(list2)
            if gene not in gamete:
                 gamete.append(gene)
        volum = 0
        for i in gamete:
            volum += i[1]
        if volum <= 50:
            gametes.append(gamete)
        
    random.shuffle(gametes)
    
    offsprings = []
    for i in range(len(gametes)-1):
        offspring = []
        offspring = list(set(gametes[i] + gametes[i+1]))
        val = 0
        for i in offspring:
            val += i[1]
        if val <= 50:
            offsprings.append(offspring)        
            
    list_of_offsprings_values = []
    for i in offsprings:
        values_value = 0
        for j in i:
            values_value += j[0]
        list_of_offsprings_values.append(values_value)
    
    
    offsprings_with_values = list(zip(list_of_offsprings_values, offsprings))
    sorted_offsprings_with_values = sorted(offsprings_with_values, reverse=True)  
    return sorted_offsprings_with_values
In [58]:
generation_1 = evolution(sorted_population_1_with_values, list_of_items)
In [59]:
generation_1[0]
Out[59]:
(94, [(9, 15), (11, 9), (23, 1), (12, 4), (24, 12), (3, 4), (12, 3)])
In [60]:
generation_2 = evolution(generation_1, list_of_items)
generation_2[0]
Out[60]:
(98, [(13, 12), (11, 9), (24, 12), (12, 4), (23, 1), (3, 4), (12, 3)])
In [61]:
generation_3 = evolution(generation_2, list_of_items)
generation_3[0]
Out[61]:
(101, [(13, 12), (6, 8), (11, 9), (24, 12), (12, 4), (23, 1), (12, 3)])
In [ ]: