CODEWITHSUNDEEP
pythonsimulated-annealing
PuzzleheadedSoup-98
PuzzleheadedSoup-98

Reputation: 1

using simulated annealing to solve 0/1 knapsack problem

I got to know about the 0/1 knapsack problem in a college course and came upon simulated annealing as a part of that course . I tried to implement it in python. It didnt always converge to optimum solution even for just 4 items. I know SA is a heuristic but given my parameters i thought it might converge. Any help would be appreciated.

Heres my code :

import NumPy as np
import random as rd
import matplotlib.pyplot as plt
class simulated_knapsack : 

    def __init__(self,item_dict,alpha=0.9,t_max=100,t_min=1e-5,iters=50):
        self.item_dict = item_dict
        self.alpha = alpha
        self.tmax = t_max
        self.tmin = t_min
        self.iters = iters 
        self.max = 2*max(self.item_dict)

    def main(self) : 

        current = self.__initial()
        current_best = current
        T = self.tmax
        p=[]
        while T > self.tmin : 

            for i in range(self.iters):
                new = self.__generate_new(current)
                delta = self.__fitness(new)-self.__fitness(current)
                if self.__accept(delta,T) : 
                    current = new
                    if self.__fitness(new)>self.__fitness(current_best):
                        current_best = new
            p.append((current_best))
            T *= self.alpha
        plt.scatter([i for i in range(len(p))],[self.__fitness(i) for i in p],s=4)

        plt.show()
        return (p[-1],self.__fitness(p[-1]))
    
    def __fitness(self,individual):
        wt,val = 0,0
        for bit,w in zip(individual,self.item_dict):
            wt += bit*w
            val += bit*self.item_dict[w]
        if wt > self.max : return 0
        else : return val
    
    def __generate_new(self,individual) : 
                r = rd.randint(0,len(individual)-1)
                individual[r]=1-individual[r]
                while self.__fitness(individual)==0 :
                    r = rd.randint(0,len(individual)-1)
                    individual[r]=1-individual[r]
                return individual
    
    def __initial(self):
        p=[rd.choice((0,1)) for i in range(len(self.item_dict))]
        while self.__fitness(p) == 0 : 
            p=[rd.choice((0,1)) for i in range(len(self.item_dict))]
        return p
    
    def __accept(self,delta,T): 
        if delta <0 : return True
        else : return rd.random()<np.exp(-delta/T)
    

simulated_knapsack(item_dict={4:3,5:5,6:5,12:20}).main()

i think my issue might be with how i generate neighbours but im not sure. any Help is greatly appreciated!

Upvotes: 0

Views: 206

Answers (1)

Sauron
Sauron

Reputation: 1353

  • In your __generate_new method randomly select an index r and flip the value at that index. However, you're not creating a new copy of the individual before modifying it, the modifications made to individual will affect the original individual as well.
def __generate_new(self, individual):
    new_individual = individual[:]
    r = rd.randint(0, len(new_individual) - 1)
    new_individual[r] = 1 - new_individual[r]
    while self.__fitness(new_individual) == 0:
        r = rd.randint(0, len(new_individual) - 1)
        new_individual[r] = 1 - new_individual[r]
    return new_individual

Upvotes: 1

Related Questions