Modified Genetic Algorithm to solve the Zero-One Knapsack Problem
This article is the third part of my previous article: Genetic Algorithms to solve the Zero-One Knapsack Problem. Please read that article before proceeding with this article to better understand the concept. The second article in the series talks about the Implementation of the traditional Genetic Algorithm for the Zero-One Knapsack Problem, check that article here.
For this article, we are going to talk about a Modified Genetic Algorithm that is inspired by the two variations of Genetic Algorithms each with a different approach compared to the traditional one. This Modified Genetic Algorithm has been published here by Mojtaba Montazeri, Rasoul Kiani, and Seyed Saleh Rastkhadiv.
Now without any further delay let's get started …
Restart-Base Genetic Algorithm -
In a nutshell, this implementation is identical to the traditional approach with the only difference that during the convergence point (i.e. the point when the Algorithm fails to improve the quality of the winner genome), this version of the Genetic Algorithm introduces a new random population when the threshold value is not achieved with the winner from the previous generation continued in the new cycle.
Island Genetic Algorithm -
This algorithm is a parallel version of the traditional Genetic Algorithm with “k” separate generations performing “k” separate Genetic Algorithms. However, the major highlight of this approach is that they share the best answers together. The main advantage other than the speed that this version offers is the stochasticity during the Crossover and Mutation operations.
Another way of thinking about this is that we run “k” parallel crossover and mutation operations during the traditional genetic algorithm. This gives us more variety during the evolution stages of the algorithm.
Now let us move to the main highlight of this article i.e. …..
Modified Genetic Algorithm -
The paper proposed the Modified Genetic Algorithm as a hybrid of the two previously mentioned versions. The proposed solution aims to run ‘M’ parallel Genetic Algorithms, each with ‘subM’ size of population for ‘subCycle’ number of iterations to get the local optimums for the ‘subM’ set.
Each of these subroutines returns a chromosome ‘C’ corresponding to the local optimum for these various partitions. These chromosomes are then finally used as a superior population for an outer genetic Algorithm to generate a superior chromosome, which is considered the final result. Since the ‘subM’ value is small, a local optimum for it can be achieved quickly.
To better understand the approach lets try to understand this with the below image -
The graph above has multiple local minima which pose a threat to the traditional approach. To solve this, we first divide the x-axis of the graph (i.e. the search space” into “M” subsets each with “subM” population size. Next, we run “M” Parallel Genetic Algorithms over each subset. This gives us the local minima for each of the “M” sub-set. We then use these “M” winners as our population and run an Outer Genetic Algorithm over this “Superior Population” to find the global minima.
The main objective of this paper is to overcome the two primary limitations of the Genetic Algorithm which are -
- High Time Complexity
- Inability to escape local optimums
The proposed algorithm fixes these issues by implementing the following -
- Running Parallel Threads to reduce time complexity.
- Each thread works over a sub-set of the search space, which helps avoid convergence at local optimums.
Now let us compare the Modified version with the Traditional Algorithm by comparing their respective Psuedo Codes -
Conclusion: After evaluating the proposed algorithm over a set of test cases and with some intuition we are able to conclude that the proposed algorithm does outperform the traditional approach in terms of both accuracy and time complexity.
You can find Python Implementations for each of the above-mentioned variations of Genetic Algorithms at Restart-Base Genetic Algorithm, Island Genetic Algorithm, and Modified Genetic Algorithm. If you found this article helpful, please follow me on Medium and GitHub and star the Project Repository.
Do check out other parts of this article series -
