How to solve knapsack problem with simulated annealing?

Question

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

Answer 1

Simulated annealing is just a (meta)heuristic strategy to help local search to better escape local optima. Local search for combinatorial optimization is conceptually simple: move from a solution to another one by changing some (generally a few) decisions, and then evaluate if this new solution is better or not than the previous one. For an introduction to this algorithmic technique, have a look to https://dl.acm.org/doi/book/10.5555/549160.

Consequently, first you have to implement a local search approach for the knapsack problem. What are the decisions of the problem to solve? To decide if an item is taken in the bag or not. What is a possible representation of a solution of the problem? The list of items stored in the bag. In a first attempt, the moves can basically be: take an item outside the bag and put it inside (insertion), take an item inside the bag and put it outside (deletion), take an item inside the bag and replace it with an item outside (exchange).

For each move, you have to implement a method to evaluate the impact of the move on the quality of the solution: does the new solution, obtained after the move, satisfy the constraints (here the sum of the weights of items in the bag must be lower than the knapsack bound)? does the new solution have a better objective value (here the sum of the prices of the items in the bag has to be maximized)? The evaluation can be done in constant time, that is, very fast, thanks to an incremental computation (store and update the sum of weights and the sum of prices for the items in the bag).

To go further, you can add a simulated annealing strategy, as described in the code given to solve the quadratic assignment problem, to help the local search to escape local optima. The idea is to accept with a certain probability (that becomes lower and lower along the resolution time is running) some moves which deteriorate the quality of the incumbent solution. On our side, we always prefer first to enrich/enlarge the moves (for example, exchanges K items inside the bag with K' items outside) instead of implementing such "meta" strategies that require to tune several parameters.