-
Notifications
You must be signed in to change notification settings - Fork 0
/
knapsack.py
131 lines (115 loc) · 4.7 KB
/
knapsack.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
import numpy as np
import random as rd
from random import randint
def cal_fitness(weight, value, population, threshold):
fitness = np.empty(population.shape[0])
for i in range(population.shape[0]):
S1 = np.sum(population[i] * value)
S2 = np.sum(population[i] * weight)
if S2 <= threshold:
fitness[i] = S1
else :
fitness[i] = 0
return fitness.astype(int)
def weighted_random_choice(choices):
max = sum(choices)
pick = rd.uniform(0, max)
current = 0
for i,value in enumerate(choices):
current =current+value
if current > pick:
return i
def selection(fitness, num_parents, population):
fitness = list(fitness)
parents = np.empty((num_parents, population.shape[1]))
for i in range(num_parents):
index=weighted_random_choice(fitness)
parents[i,:] = population[index, :]
return parents
def crossover(parents, num_offsprings):
offsprings = np.empty((num_offsprings, parents.shape[1]))
crossover_point = int(parents.shape[1]/2)
crossover_rate = 0.9
i=0
while (parents.shape[0] < num_offsprings):
parent1_index = i%parents.shape[0]
parent2_index = (i+1)%parents.shape[0]
x = rd.random()
if x > crossover_rate:
continue
parent1_index = i%parents.shape[0]
parent2_index = (i+1)%parents.shape[0]
offsprings[i,0:crossover_point] = parents[parent1_index,0:crossover_point]
offsprings[i,crossover_point:] = parents[parent2_index,crossover_point:]
i=+1
return offsprings
def mutation(offsprings):
mutants = np.empty((offsprings.shape))
mutation_rate = 0.2
for i in range(mutants.shape[0]):
random_value = rd.random()
mutants[i,:] = offsprings[i,:]
if random_value > mutation_rate:
continue
int_random_value = randint(0,offsprings.shape[1]-1)
if mutants[i,int_random_value] == 0 :
mutants[i,int_random_value] = 1
else :
mutants[i,int_random_value] = 0
return mutants
def elitism(mutants, population, fitness, weight, value, threshold):
elitis = np.empty((mutants.shape))
elitis = mutants
parents_max_loc = np.where(fitness == np.max(fitness))[0]
parents_max_loc_real = parents_max_loc[0]
fitness_mutants = cal_fitness(weight, value, mutants, threshold)
mutants_min_loc = np.where(fitness_mutants == np.min(fitness_mutants))
mutants_min_loc_real = mutants_min_loc[0]
elitis[mutants_min_loc_real] = population[parents_max_loc_real]
return elitis
def optimize(weight, value, population, pop_size, num_generations, threshold):
parameters, fitness_history = [], []
num_parents = int(pop_size[0])
num_offsprings = pop_size[0]
for i in range(num_generations-1):
fitness = cal_fitness(weight, value, population, threshold)
fitness_history.append(fitness)
parents = selection(fitness, num_parents, population)
offsprings = crossover(parents, num_offsprings)
mutants = mutation(offsprings)
population = elitism(mutants, population, fitness, weight, value, threshold)
fitness_last_gen = cal_fitness(weight, value, population, threshold)
max_fitness = np.where(fitness_last_gen == np.max(fitness_last_gen))
parameters.append(population[max_fitness[0][0],:])
return parameters, fitness_history
def kalkulasi(number_of_item, nama_makanan, value_makanan, harga_makanan, uang) :
numpy_nama_makanan = np.array([i for i in nama_makanan.split(',')])
numpy_value_makanan = np.array([int(i) for i in value_makanan.split(',')])
numpy_harga_makanan = np.array([int(i) for i in harga_makanan.split(',')])
item_number = np.arange(1, int(number_of_item) + 1)
weight = numpy_harga_makanan
value = numpy_value_makanan
knapsack_threshold = int(uang)
solutions_per_pop = 10
pop_size = (solutions_per_pop, item_number.shape[0])
initial_population = np.random.randint(2, size = pop_size)
initial_population = initial_population.astype(int)
num_generations = 50
parameters, fitness_history = optimize(weight, value, initial_population, pop_size, num_generations, knapsack_threshold)
selected_items = item_number * parameters
hasil_nama_makanan = []
kalori = 0
uang_yang_dibutuhkan = 0
for i in selected_items[0] :
if (i!=0) :
hasil_nama_makanan.append(numpy_nama_makanan[int(i)-1])
kalori = kalori + numpy_value_makanan[int(i)-1]
uang_yang_dibutuhkan = uang_yang_dibutuhkan + numpy_harga_makanan[int(i)-1]
hasil_string = ""
for i in hasil_nama_makanan :
hasil_string = hasil_string + i + ","
total = []
total.append(hasil_string)
total.append(kalori)
total.append(uang_yang_dibutuhkan)
return total