# How to solve knapsack problem with simulated annealing?

I was going through the course contents of Optimization with Metaheuristics in Python in udemy , where they have solved a quadratic assignment problem using Simulated annealing in python , i was trying to implement the same concept for a knapsack problem I couldnot do it.

import numpy as np
from matplotlib import pyplot as plt
import pandas as pd

Dist = pd.DataFrame([[0,1,2,3,1,2,3,4],[1,0,1,2,2,1,2,3],[2,1,0,1,3,2,1,2],
[3,2,1,0,4,3,2,1],[1,2,3,4,0,1,2,3],[2,1,2,3,1,0,1,2],
[3,2,1,2,2,1,0,1],[4,3,2,1,3,2,1,0]],
columns=["A","B","C","D","E","F","G","H"],
index=["A","B","C","D","E","F","G","H"])

Flow = pd.DataFrame([[0,5,2,4,1,0,0,6],[5,0,3,0,2,2,2,0],[2,3,0,0,0,0,0,5],
[4,0,0,0,5,2,2,10],[1,2,0,5,0,10,0,0],[0,2,0,2,10,0,5,1],
[0,2,0,2,0,5,0,10],[6,0,5,10,0,1,10,0]],
columns=["A","B","C","D","E","F","G","H"],
index=["A","B","C","D","E","F","G","H"])

T0 = 1500
M = 250
N = 20
alpha = 0.9

X0 = ["B","D","A","E","C","F","G","H"]

# Make a dataframe of the initial solution

New_Dist_DF = Dist.reindex(columns=X0, index=X0)
New_Dist_Arr = np.array(New_Dist_DF)

# Make a dataframe of the cost of the initial solution

Objfun1_start = pd.DataFrame(New_Dist_Arr*Flow)
Objfun1_start_Arr = np.array(Objfun1_start)

sum_start = sum(sum(Objfun1_start_Arr))

print(sum_start)

Temp = []
Min_Cost = []

for i in range(M):
for j in range(N):
ran_1 = np.random.randint(0,len(X0))
ran_2 = np.random.randint(0,len(X0))

while ran_1==ran_2:
ran_2 = np.random.randint(0,len(X0))

xt = []
xf = []

# ["B","D","A","E","C","F","G","H"]

A1 = X0[ran_1]
A2 = X0[ran_2]

# Make a new list of the new set of departments

w = 0
for i in X0:
if X0[w]==A1:
xt = np.append(xt,A2)
elif X0[w]==A2:
xt = np.append(xt,A1)
else:
xt=np.append(xt,X0[w])
w = w+1

new_dis_df_init = Dist.reindex(columns=X0, index=X0)
new_dis_init_arr = np.array(new_dis_df_init)

new_dis_df_new = Dist.reindex(columns=xt, index=xt)
new_dis_new_arr = np.array(new_dis_df_new)

# Make a adatframe of the current solution
objfun_init = pd.DataFrame(new_dis_init_arr*Flow)
objfun_init_arr = np.array(objfun_init)

# Make a adatframe of the new solution
objfun_new = pd.DataFrame(new_dis_new_arr*Flow)
objfun_new_arr = np.array(objfun_new)

sum_init = sum(sum(objfun_init_arr))
sum_new = sum(sum(objfun_new_arr))

rand1 = np.random.rand()
form = 1/(np.exp(sum_new-sum_init)/T0)

if sum_new<=sum_init:
X0=xt
elif rand1<=form:
X0=xt
else:
X0=X0

Temp.append(T0)
Min_Cost.append(sum_init)

T0 = alpha*T0

print()
print("Final Solution:",X0)
print("Minimized Cost:",sum_init)

plt.plot(Temp,Min_Cost)
plt.title("Cost vs. Temp.", fontsize=20,fontweight='bold')
plt.xlabel("Temp.", fontsize=18,fontweight='bold')
plt.ylabel("Cost", fontsize=18,fontweight='bold')
plt.xlim(1500,0)

plt.xticks(np.arange(min(Temp),max(Temp),100),fontweight='bold')
plt.yticks(fontweight='bold')
plt.show()


how to use this code for a knapsack problem where v is a list of value of items , w being list of weights and k value be the capacity of knapsack, i have tried the following code

import numpy as np
from matplotlib import pyplot as plt
import pandas as pd
v=[1945,321,2945,4136,1107,1022,1101,2890,962,1060,805,689,1513,3878,13504,1865,667,1833,16553]
w= [4990.0 ,1142.0, 7390.0, 10372.0 ,3114.0, 2744.0, 3102.0, 7280.0, 2624.0, 3020.0, 2310.0, 2078.0, 3926.0, 9656.0, 32708.0, 4830.0, 2034.0, 4766.0, 40006.0]
T0 = 1500
M = 250
N = 20
alpha = 0.9
k=31181
X0=[0,1,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0]

Objfun1_start=0
for i in range(0,19):
Objfun1_start = (X0[i]*v[i])+Objfun1_start
Objfun1_start_Arr = np.array(Objfun1_start)

# Make a dataframe of the cost of the initial solution

sum_start = Objfun1_start_Arr

print(sum_start)

Temp = []
Min_Cost = []

for i in range(M):
for j in range(N):
ran_1 = np.random.randint(0,len(X0))
ran_2 = np.random.randint(0,len(X0))

while ran_1==ran_2:
ran_2 = np.random.randint(0,len(X0))

xt = []
xf = []

A1 = X0[ran_1]
A2 = X0[ran_2]

# Make a new list of the new set of departments

w = 0
for i in X0:
if X0[w]==A1:
xt = np.append(xt,A2)
elif X0[w]==A2:
xt = np.append(xt,A1)
else:
xt=np.append(xt,X0[w])
w = w+1

new_dis_df_init = v
new_dis_init_arr = np.array(new_dis_df_init)

new_dis_df_new = v
new_dis_new_arr = np.array(new_dis_df_new)

# Make a adatframe of the current solution
for i in range(0,19):

objfun_init[i] = (v[i]*X0[i])
objfun_init_arr = np.array(objfun_init)

# Make a adatframe of the new solution
for i in range(0,19):
objfun_new[i] = (v[i]*X0[i])
objfun_new_arr = np.array(objfun_new)

sum_init = (objfun_init_arr)
sum_new = (objfun_new_arr)

rand1 = np.random.rand()
form = 1/(np.exp(sum_new-sum_init)/T0)

if sum_new.any()<=sum_init.any():
X0=xt
elif rand1<=form:
X0=xt
else:
X0=X0

Temp.append(T0)
Min_Cost.append(sum_init)

T0 = alpha*T0

print()
print("Final Solution:",X0)
print("maximum value:",sum_init)

plt.plot(Temp,Min_Cost)
plt.title("value vs. Temp.", fontsize=20,fontweight='bold')
plt.xlabel("value.", fontsize=18,fontweight='bold')
plt.ylabel("Cost", fontsize=18,fontweight='bold')
plt.xlim(1500,0)

plt.xticks(np.arange(min(Temp),max(Temp),100),fontweight='bold')
plt.yticks(fontweight='bold')
plt.show()

• I think it's better to be more explicit in describing what do you mean by you could not do it so that others can help you better. May 14, 2020 at 2:06
• edited my question, thank you @SiongThyeGoh
– 21vs
May 14, 2020 at 6:54