-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathknapsack_ga_binary.py
executable file
·160 lines (109 loc) · 4.36 KB
/
knapsack_ga_binary.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
# 0 - 1 Knapsack
import random
import statistics
def check_fitness(population, values, weights, n_items, max_weight):
fitness = []
for j,chromosome in enumerate(population):
while True:
cur_weight = 0
cur_value = 0
for i in range(0,n_items):
if chromosome & pow(2,i) != 0:
cur_weight += weights[n_items - i - 1]
cur_value += values[n_items - i - 1]
if cur_weight <= max_weight:
fitness.append(cur_value)
break
else:
remove = ~pow(2,random.randint(1,n_items))
chromosome &= remove
population[j] = chromosome
return fitness
def generate_population(population_size, n_items):
population = []
for i in range(0,population_size):
population.append(random.randint(0,pow(2,n_items) - 1))
return population
def select_parents(population,fitness):
target_fitness = random.randint(0,sum(fitness))
temp_sum = 0
parent1 = []
fitness1 = 0
selected = ([],[])
for i in range(0,len(population)):
temp_sum += fitness[i]
if temp_sum >= target_fitness:
parent1 = population.pop(i)
fitness1 = fitness.pop(i)
break
temp_sum = 0
target_fitness = random.randint(0,sum(fitness))
for i in range(0,len(population)):
temp_sum += fitness[i]
if temp_sum >= target_fitness:
parent2 = population[i]
population.append(parent1)
fitness.append(fitness1)
selected = (parent1,parent2)
break
return selected
def crossover(parent1,parent2,n_items):
pivot = random.randint(0,n_items-1)
max_value = pow(2,n_items) - 1
mask1 = (max_value >> pivot) << pivot
mask2 = max_value - mask1
child = (parent1 & mask1) + (parent2 & mask2)
return child
def mutate(chromosome,n_items,mutation_resillence):
for i in range(0,n_items - 1):
mutation_cofficient = random.randint(1,mutation_resillence)
if mutation_cofficient == 1:
chromosome ^= pow(2,i)
return chromosome
def get_elite(population,fitness):
elite = 0
for i,cur_fitness in enumerate(fitness):
if cur_fitness > fitness[elite]:
elite = i
return population[elite]
def generate_next_generation(population, fitness, n_items, mutation_resillence):
population_size = len(fitness)
new_population = [ get_elite(population,fitness) ]
while(len(new_population) < population_size):
(parent1, parent2) = select_parents(population,fitness)
new_population.append(mutate(crossover(parent1,parent2,n_items),n_items,mutation_resillence))
return new_population
def is_converged(fitness, convergence_acceptance):
mode_fitness = max(set(fitness),key=fitness.count)
if float(fitness.count(mode_fitness)) / float(len(fitness)) >= convergence_acceptance:
return True
return False
def binary_to_array(number,n_items):
array = [int(x) for x in format(number,"0{}b".format(n_items))]
return array
def solve_knapsack(values, weights, max_weight, population_size, mutation_resillence, generations, acceptance):
generation = 0
population = generate_population(population_size, len(values))
fitness = check_fitness(population, values, weights, len(values), max_weight)
while(not is_converged(fitness,acceptance) and generation < generations):
generation += 1
population = generate_next_generation(population, fitness, len(values), mutation_resillence)
fitness = check_fitness(population, values, weights, len(values), max_weight)
return (generation,get_elite(population,fitness))
def run():
values = [100,60,40,5,50]
weights = [90,50,30,10,20]
population_size = 100
max_weight = 100
(generations,solution) = solve_knapsack(values,weights,max_weight,population_size,100,100,0.6)
solution_arr = binary_to_array(solution,len(values))
cur_val = 0
cur_weight = 0
for i,x in enumerate(solution_arr):
if x == 1:
cur_val += values[i]
cur_weight += weights[i]
print("Solution found in {} generations".format(generations))
print("Selection is: ", solution_arr)
print("Total values is: ", cur_val)
print("Total weight is: ", cur_weight)