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 [ ]: