Genetic Algorithm: Part 3 — Knapsack Problem

Previously, we discussed about Genetic Algorithm(GA) and its working and also saw its simple implementation.

This time we will solve a classical problem using GA. The problem we will be solving is Knapsack Problem.

Problem Statement

A thief enters a shop carrying knapsack(bag) which can carry 35 kgs of weight. The shop has 10 items, each with a specific weight and price. Now, the thief’s dilemma is to make such a selection of items that it maximizes the value(i.e. total price) without exceeding the knapsack weight. We have to help the thief to make the selection.

Solution

We will be using GA to solve this problem. We will follow the same flowchart as we discussed in my first article.

So, here we go….

We begin with randomly initializing the list of items.

Output:

The list is as follows: 
Item No.   Weight   Value 
1          3         266  
2          13         442  
3          10         671  
4          9         526  
5          7         388  
6          1         245  
7          8         210  
8          8         145  
9          2         126  
10         9         322

Now we declare the initial population. In this problem the idea of chromosome encoding is to have a chromosome consisting as many genes as there are total number of items such that each gene index corresponds to item index in the list. Each gene has a value 1 or 0 which tells whether the corresponding item is present or not.

Output:

Population size = (8, 10) 
Initial population:  
[[0 1 0 1 1 0 0 1 1 1]  
[1 1 1 1 0 1 1 1 0 0]  
[0 1 0 0 0 0 1 1 0 1]  
[0 0 1 0 1 1 0 0 0 0]  
[0 0 1 1 0 0 0 0 0 1]  
[0 1 0 1 1 0 1 0 0 0]  
[1 1 1 0 0 0 1 0 1 0]  
[0 0 0 0 1 1 1 0 0 0]]

The fitness function that we will be using for this problem is as follows:

where,

n = chromosome length

c_i = ith gene

v_i = ith value

w_i = ith weight

kw = knapsack weight

Now we select the fittest individuals so that they can undergo crossover.

For crossover we will be using one-point crossover(refer to my previous articles). We will be setting crossover rate to a high value to ensure more number of fittest individuals undergo crossover.

In Mutation, which chromosome will undergo mutation is being done randomly. For creating mutants we will be using bit-flip technique i.e. if the selected gene which is going to undergo mutation is 1 then change it to 0 and vice-versa.

As all the necessary functions have been defined so now we will call them in the order of the flow chart to find the required parameters and make all the necessary initializations.

The corresponding items of the parameters in the item_number array will be the ones that the thief will take.

Output:

Last generation:  
[[1 0 1 1 0 1 0 0 1 1]  
[1 0 1 1 0 1 0 0 1 1]  
[1 0 1 1 0 1 0 0 1 1]  
[1 0 1 1 0 1 0 0 1 1]  
[1 0 1 1 0 1 0 0 1 1]  
[1 0 1 1 0 1 0 0 1 1]  
[1 0 1 1 0 1 0 0 1 1]  
[1 0 1 1 0 0 0 0 1 1]]  
Fitness of the last generation:  
[2156 2156 2156 2156 2156 2156 2156 1911]  
The optimized parameters for the given inputs are:  
[array([1, 0, 1, 1, 0, 1, 0, 0, 1, 1])]  
Selected items that will maximize the knapsack without breaking it: 
1  
3  
4  
6  
9  
10

Now we will visualize how the fitness changes with every generation.

Output:

Thank you for reading this. Stay tuned for more Machine Learning stuff.….. :)