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

Six essential steps for genetic algorithm implementation

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(j-1 ...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 multi-constraints. 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 0-1 knapsack problem. In this paper the problem is 0/1, therefore we worked on bounded 0-1 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

Relations between gene, chromosome and population with four chromosomes, and each chromosome has six values depending inclusion or exclusion of genes

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

Chromosome-1 [ 100110]

[14+0+0+6+9+0=29]

Chromosome-2[011100]

[0+4+5+6+0+0=15]

Chromosome-3 [010100]

[0+4+0+6+0+0=10]

Chromosome-4[011001]

[0+4+5+0+0+19=28]

Four sections of chart showing benefits points of various chromosomes and chromosome-1 has maximum value while chromosome-3 has minimum

FIGURE 12.3 Four sections of chart showing benefits points of various chromosomes and chromosome-1 has maximum value while chromosome-3 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 chromosome-1 and chromosome-4, 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 one-point 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].

Mutation operation where genes are flipped

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,...X6) 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

X4

5

Bottle

X5

6

Glucose

X6

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 (Xh X2,...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,

N-Bits=n,

# Set Maximum Number of Generations

# Stopping Criteria (run) if best value obtained or no improvements in run generations

maxiter=lOO, run=l50, pop-size=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 meta-algorithms 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 complex-valued encoding wind driven optimization for the 0-1 knapsack problem. Applied Intelligence. 46: 684-702.
  • 2. Yang, X.-S. 2017. Nature-Inspired Algorithms and Applied Optimization, Springer. New York. NY.
  • 3. Rezoug, A.. Bader-EI-Den. M. and Boughaci, D. 2018. Guided genetic algorithm for multidimensional knapsack problem. Memetic Computing. 10(1): 29-42.
  • 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): 1-37.
  • 7. Feng, Y.H. and Wang, G.-G. 2018. Binary moth search algorithm for discounted {0,1) knapsack problem. IEEE Access. 6: 10708-10719.
 
Source
< Prev   CONTENTS   Source   Next >