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()