Solving Knapsack Problem with Genetic Algorithm Approach
CONCEPT OF GENETIC ALGORITHMS
Genetic algorithms (GA) are classical, heuristic search algorithms that conceptually use the approaches that are adopted by living organisms to survive in their environment. The genetic algorithms are Socratic in nature, their performance and output efficiency can vary across multiple executions [1]. In genetic algorithms, solutions are interpreted as optimization problem. The genetic algorithms work on population and coding of parameter sets, which are required for solution. The population is constructed by sequent of numbers called “chromosomes” and a sequence of number that constructs the chromosome is named as “gene”. The assemblage of various chromosomes is called a population. The initial population is generated randomly without any specific pattern. Each chromosome in a population has a fitness value, which is a mathematical expression and determines the probability of survival of
FIGURE 12.1 Six essential steps for genetic algorithm implementation.
each particular chromosome in the next generation. The outlines of GA are shown as in Figure 12.1 [2].
THE KNAPSACK PROBLEM
The knapsack problem (KP) is a specimen of stochastic and combinatorial optimization problem [3] that uses to find the optimum solution among available solutions [4]. Mathematically, it can be formulated by numbering the object l to n and introducing a vector for binary variables Xj(j1 ...n) having the meaning [5]:
In this chapter, we will focus on 0/1 KP, in which ‘n’ items (objects) will be selected for a knapsack having capacity of 28 kg and it is assumed a knapsack has positive integer weight [2].
object/Item 7’ has a positive integer volume ‘Wf and positive integer benefit B,'. In addition, there are ‘Qf copies of item T available, where quantity ‘<2,’ is a positive integer satisfying 1 < £>, <
Let's ‘Xf determines how many copies of item T can be placed into the knapsack. The goal is to:
N
Subject to the constraints ^ W, Xj < W
i=l
andO < Xi < Qi
The KP is bounded and may be either 0 or 1 or multiconstraints. If one or more of the Qi is infinite, the KP is unbounded; otherwise, the KP is bounded [6]. If Qi = 1 for i = 1,2,N, the problem is a 01 knapsack problem. In this paper the problem is 0/1, therefore we worked on bounded 01 KP, we could not have more than one copy of an item in the knapsack.
STEPS INVOLVED IN GENETIC ALGORITHM
Let’s assume, we are going to spend a month in an uncultivated region. Suppose we have knapsack (or carry bag) that has maximum capacity of 28 kg. Here different useful items and each having its own “benefit points” and “weight”. In this problem our objective is to maximizing the beneficial (B;) point, so that a carrying bag has maximum useful items. Detail of each item is given in Table 12.1.
12.3.1 Initialization
Providing the solution of a given bounded knapsack problem using genetic algorithm, first create population, it has individuals and each individual has their own set of chromosomes. In this problem, the genotype structure of chromosomes is “binary” strings. If structure has “1”, it means that item is considered, and if “0”, it means item is not considered or dropped as shown in Figure 12.2.
12.3.2 Fitness Function
To calculate the fitness of all chromosomes, B, points are considered as survival of chromosomes. The overall survival points are shown in the Table 12.2.
TABLE 12.1
Showing Items with Benefit and Weight
S. No. 
Items 
Benefit (Bi) 
Weight (Wi) 
I 
Sleeping bag 
14 
16 
2 
Rope 
4 
6 
3 
Pocket knife 
5 
8 
4 
Torch 
6 
8 
5 
Bottle 
9 
7 
6 
Glucose 
15 
6 
FIGURE 12.2 Relations between gene, chromosome and population with four chromosomes, and each chromosome has six values depending inclusion or exclusion of genes.
Now, it is clear chromosomes have different survival points and the fitness order would be as follows:
12.3.3 Selection
After calculating the fitness of each chromosome, the fittest are selected from the pool, which come together to produce their offspring. Generally, we should reproduce the chromosomes that have more fitness value. Although, it creates convergence of population as less diversity in solutions within few generations. To maintain the diversity between chromosomes, we generally use roulette wheel selection method. In this method, selection is based on the statistical value of individual. The individuals showing higher fitness value on the wheel (Figure 12.3) get more chances to create a new population, while individuals showing poor fitness are rejected. Now
TABLE 12.2
Calculation of Fitness Points of Chromosomes on the Basis of Chromosome Inclusion/Exdusion
Chromosome 
Survival Points 
Chromosome1 [ 100110] 
[14+0+0+6+9+0=29] 
Chromosome2[011100] 
[0+4+5+6+0+0=15] 
Chromosome3 [010100] 
[0+4+0+6+0+0=10] 
Chromosome4[011001] 
[0+4+5+0+0+19=28] 
FIGURE 12.3 Four sections of chart showing benefits points of various chromosomes and chromosome1 has maximum value while chromosome3 has minimum.
consider the problem where population of chromosomes is divided in “m” number of divisions. The plot area engrossed by each chromosome is equivalent to its fitness value. Based on chromosome fitness values as in Table 12.2, fitness of chromosomes can be seen in Figure 12.3.
When the rotation of the wheel starts, the area that comes in front of the fixed point is chosen as the parent and is repeated exactly for the second parent.
12.3.4 Crossover
Now crossover operation is applied on chosen parent chromosomes to generate two new members for the next generation to produce offspring. Let us find the crossover between chromosome1 and chromosome4, which were chosen in previous step on the basis of their fitness value. It is shown in Figure 12.4.
The crossover shown in the Figure 12.4 is most fundamental, and it is knowm as a onepoint crossover. In this, random crossover points are identified and tails of both chromosomes exchanged to produce new' offspring. Now if crossover operation performs on tw'o points, it known as multipoint crossover. Crossover is important to maintain diversity between individuals [7].
FIGURE 12.5 Mutation operation where genes are flipped: l replaced by 0.
12.3.5 Mutation
Change in chromosome structure or randomly alteration in genes is known as “mutation”; therefore, a random swapping of gene on chromosome is done here, which promotes the idea of diversity in the population [6]. Process of mutation is illustrated in the Figure 12.5.
TERMINATION CONDITION
The experiment terminates either the specified number of generations achieved or no improvement seen for ‘x’ iterations. If fitness function attains prespecified value, the experiment winds up then too.
Steps for Knapsack Problem Solving with GA
Genetic algorithm is best known in design; here genotype of chromosomes is represented by binary combination like “10101011”. For the stated problem of optimization in an experiment, an initial population of binary strings is created randomly and quality of each chromosome is determined by the value of fitness function. The fitness value/fitness function is calculated as:
Once population is created, parents are selected from the pool. The crossover operation is applied to create “offspring” and fitness of each chromosome is evaluated. In the next step, mutation operation is performed to maintain more diversity in population and result [4]. This allows GA to analyze more search space, by this it avoid
TABLE 12.3
List of Items with Symbols (X,...X_{6}) in Chromosomes Structure and if Item Included the Gene Value is 1 Otherwise 0
S. No. 
Item 
Symbol 
Values 
1 
Sleeping bag 
X, 
If included in combination it is ‘ 1 
2 
Rope 
X, 
otherwise it is ‘O’ 
3 
Pocket knife 
X, 

4 
Torch 
X_{4} 

5 
Bottle 
X_{5} 

6 
Glucose 
X_{6} 
local optima. For our knapsack problem, we consider the data with n = 6 and W = 28. The chromosomes based on item inclusion or exclusion are represented in Table 12.3.
In our case, the problem consists of population size n = 6 and the solution is focus on of selecting appropriate item (X_{h} X_{2},...Xn) in the knapsack. The chromosome represents the vector X, consist the value “1” if item is included “0” if item is not included. It is shown as:
We have created the population by taking the chromosomes values randomly; a few' combinations of potential solutions may be as follows:
Ten percent (say population size 100) of chromosomes are selected from the population to perform crossover operation for creating offspring and mutation operation to maintain the diversity of population. We select the chromosomes (items) by computing Rj to benefit to weight. The chromosomes (item) having more benefit and low weight for the knapsack are selected. The evaluation process remains continue to N generations, for a first generation is shown in Table 12.4.
This process continues until an optimized solution is obtained or termination criteria is met. GA can be implemented by following steps:
Import numpy # Version 3.8
# Define data
# Define Benefits
p < 0(4,14,5,6,9,15)
#Define Weight W < 0(16,6,8,8,7,6)
#Define Knapsack Capacity (W)
W < 28
TABLE 12.4
Estimation of Benefit (B_{;}) and Weight (W;) Ratio (R;) for First Generation and Same Process will be Continue Till Termination
S. No. 
Item (Chromosome) 
Benefit (Bj) 
Weight (Wi) 
Ri = (Bi/Wi) 
1 
000001 
15 
6 
2.50 
2 
100001 
29 
22 
1.318182 
3 
100100 
23 
24 
0.958333 
4 
110100 
24 
30 
0.80 
5 
001010 
14 
15 
0.933333 
6 
110000 
18 
22 
0.818182 
7 
111111 
53 
51 
1.039216 
8 
001110 
20 
23 
0.869565 
9 
110001 
33 
28 
1.178571 
10 
111000 
23 
30 
0.766667 
# Define Number of Objects (Items) n < length (p)
# Define Fitness Function knapsack < function(x)
f < sum(x * p)
penalty < sum(w) * abs(sum(x * w)  W) f  penalty ga (type="binary",
Fitness=knapsack,
NBits=n,
# Set Maximum Number of Generations
# Stopping Criteria (run) if best value obtained or no improvements in run generations
maxiter=lOO, run=l50, popsize=l00, seed=l01)
x.star< SGA@ solution# Final solution: c(l,1,0,0,0,1) sum(x.star) # Total number of selected items: 3 sum(x.star * p) # Total profit/benefit of selected items: 33 sum(x.star * w) # Total weight of selected items: 30
CONCLUSION
To solve our problem, the solution found by GA within knapsack’s capacity constraint of W = 28 is x* = (1,1,0,0,0,1). It is observed that the optimal solution for selecting items is (1, 2, 6), which is maximum total benefit of/(x*) = 33. As the outcome of this experiment, GAs are metaalgorithms that can apply for obtaining solutions of optimizing problems. Here, we have discussed the application of GA to one instance of constrained optimization: ‘knapsack problem’. In this experiment, it is demonstrated that GA can be applied to yield a higher benefit or total profit.
REFERENCES
 1. Zhou. Y.. Bao, Z.. Luo, Q. and Zhang. S. 2017. A complexvalued encoding wind driven optimization for the 01 knapsack problem. Applied Intelligence. 46: 684702.
 2. Yang, X.S. 2017. NatureInspired Algorithms and Applied Optimization, Springer. New York. NY.
 3. Rezoug, A.. BaderEIDen. M. and Boughaci, D. 2018. Guided genetic algorithm for multidimensional knapsack problem. Memetic Computing. 10(1): 2942.
 4. Yu, X. and Gen, M. 2010. Introduction to Evolutionary Algorithms, Decision Engineering Series, Springer, New York. NY.
 5. Martello, S. and Toth, P. 1990. Knapsack Problems. DEIS University, Bologna, Italy.
 6. Scrucca. L. 2013. GA: A package for genetic algorithms in R. Journal of Statistical Software. 53(4): 137.
 7. Feng, Y.H. and Wang, G.G. 2018. Binary moth search algorithm for discounted {0,1) knapsack problem. IEEE Access. 6: 1070810719.