This project aims to solve the famous 0-1 Knapsack Problem using various versions of Genetic Algorithm. The various approaches for this are inspired from this paper.
You can find the complete concept and implementations explained in detail at the following blog posts -
- Standard Genetic Algorithm to solve the Zero-One Knapsack Problem
- Standard Genetic Algorithm to solve the Zero-One Knapsack Problem: Implementation
- Modified Genetic Algorithm to solve the Zero-One Knapsack Problem
- Modified Genetic Algorithm to solve the Zero-One Knapsack Problem: Implementation
- Introduction
- Index
- Genetic Algorithm
- Methodology
- Installation
- Usage
- Files in the repository
- Bibliography
Problem: The zero-one knapsack problem belongs to the category of combinatorial optimization problems. Combinatorial optimization problems typically involve the selection of an optimal solution from a finite set of solutions. An exhaustive search for these problems is usually not feasible as it may be computationally expensive. The problem's primary objective is filling a knapsack (or a backpack) of fixed size with the most profitable items from a set of items. Each item has an associated weight, and thus, selecting a specific item consumes its associated weight from the knapsack's fixed capacity. This type of problem is analogous to a resource allocation task where one may include or exclude a non-divisible job in a budget-bound or time-bound queue.
Proposed Approach: Genetic Algorithms belongs to the class of Evolutionary Algorithms. General Algorithm is a population-based metaheuristic optimization Algorithm, governed by natural-selection. In the Algorithm, a population is initialized with a set of candidate solutions. Each candidate is distinguished by a specific set of properties called the genotype or the chromosome. An objective function calculates the fitness for each individual. The individuals with the highest fitness are selected from the current generation and are crossed to form new individuals. These individuals may then undergo mutation to form a new generation. This cycle is repeated until a satisfactory solution is obtained, or the maximum number of generations is exhausted.
The primary two limitations of the Genetic Algorithms are
-
its inability to escape local optimums (Local optimums refer to the points in the search space that the Algorithm mistakes for the best results preventing the Algorithm from converging to the best global results).
-
high time complexity due to large search space and sequential nature of Genetic Operations.
Restart-base Genetic Algorithm is an improvised version of the standard genetic algorithm which randomly generates a new generation and restarts the algorithm when it fails to find better results.
Island Genetic Algorithm is a parallelized version of a genetic algorithm and includes running k-genetic algorithms in parallel.
The paper proposes a hybrid version of the Restart-base and Island genetic algorithms in order to overcome the limitations. The algorithm runs m-number of genetic algorithms in parallel over specified search spaces. The winners of each sub-genetic algorithms are added to a “Superior Population”. An outer genetic algorithm is then deployed over the “Superior Population” to obtain the overall winner.
Fig: Visualizing the Modified Genetic Algorithm
Step 1: Initialization -
The chromosomes or the genotype of the individuals in the initial population are typically generated at random. In some cases, these chromosomes may also result from a seed value, where the solution of the problem is likely to be found in a particular region of the search space.
Step 2: Selection -
First, the fitness score of each individual is calculated by an objective function, which is decided based on the respective problem. This fitness score is an indication of how suitable the respective solution is for the problem. During each successive generation a portion of the current population with relatively higher fitness scores is allowed to move to the next stage.
Various schemes may be used in the selection stage, such as tournament selection, rank-based selection, roulette wheel selection, elitism selection, etc.
Fig: Selection
Step 3: Crossover -
Crossover involves the reproduction of a new generation from the selected individuals. It is a genetic operation used to combine the genetic information of two parents in order to generate new offspring.
Fig: Crossover
Step 4: Mutation -
Mutation is the genetic operation used to maintain genetic diversity after the crossover stages. It is analogous to biological mutation and alters the chromosomes of the children using one or more schemes such as bit-flip mutation, swap mutation, scramble mutation, etc.
In simple terms, mutation may be defined as a small random tweak in the chromosomes, to get a new
solution.
Fig: Mutation
Step 5: Termination -
The cycle of selection, crossover and mutation is repeated until one of the following conditions is met –
- A solution is found that satisfies the threshold condition.
- The maximum number of iterations/cycles have been exhausted.
- The high ranking solutions’ fitness scores have become stagnant and show no or little improvement.
- Allocated computation/time resources have been exhausted.
Fig: Termination
The genome of an individual in any generation can be represented as an array of binary bits, as shown below. The length of the genome is equal to the total number of items.
Fig: Representation: Genome of an Individual
The initial population is stochastically generated and represented as a matrix, with each row as an individual genotype sequence.
Fig: Representation: Population
The crossover operation is applied over selected individuals using one of the schemes mentioned previously. This results in a completely new population. This Children Population is then mutated to increase the diversity in the population.
Fig: Crossover and Mutation over the Selected Population
The Mutated Children are then merged with the individuals from the selected population.
Fig: Merging
This new population is twice the original size, so it is sorted in descending order based on the fitness score for each of the individuals, and the lower 50% of the population is discarded.
Fig: Sorting and Resizing the Population
pip3 install -r requirements.txt
or
pip install -r requirements.txt- Use existing knapsack json files from
valuesdirectory or generate a file with random values or create a custom file. - Change fname in the respective code.
- Select the parameters such as
cycle,selection_percentage,k_parallel,restart_rate, etc.
python3 standard_genetic_algorithm.pypython3 restart_base_genetic_algorithm.pypython3 island_genetic_algorithm.pypython3 modified_genetic_algorithm.pyThe files in the repository are :
This directory contains the images for the icons and other media for the README File.
Contains the code for an exhaustive search to find the best solution for Knapsack Problem.
The description file containing details about the repository. The file that you looking at right now.
This file contains the respective packages needed to be installed.
The __init__.py file is to make Python treat directories containing the file as packages.
This file contains the Knapsack class for creating random weight-value vectors and writing it to json files.
This file contains the Restart-Base implementation of Genetic Algorithm.
This file contains the Island implementation of Genetic Algorithm.
This file contains the Traditional implementation of Genetic Algorithm.
This file contains the implementation of Genetic Algorithm as proposed in the above mentioned paper.
This directory contains the json files containing the sample values created and used as test cases for Knapsack Problem.
- M. Montazeri, R. Kiani and S. S. Rastkhadiv, "A new approach to the Restart Genetic Algorithm to solve zero-one knapsack problem," 2017 IEEE 4th International Conference on Knowledge-Based Engineering and Innovation (KBEI), Tehran, 2017, pp. 0050-0053, doi: 10.1109/KBEI.2017.8324863.
- Playlist by YarpizProjects, you can check it out here.
