Modified Genetic Algorithm to solve the Zero-One Knapsack Problem: Implementation
This article is the fourth and final part of my article series on Genetic Algorithms to solve the Zero-One Knapsack Problem.
The First article introduces us to Genetic Algorithms in general and how they are applicable to the Zero-One Knapsack Problem.
The Second article then takes us through the implementation of Traditional Genetic Algorithms for this problem.
The Third article talks about the new approaches to this problem using a Modified Version of a Genetic Algorithm inspired by two other variations i.e. Restart-Base Genetic Algorithm and Island Genetic Algorithm.
Please read these articles before proceeding, to better understand the concept.
Summary of how the modified genetic algorithm works: 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.
For this article, we are going to focus on implementing the Restart-Base, Island, and Modified versions of the Genetic Algorithm. Before moving forward, if you are not comfortable with Python and Numpy, I recommend the following Youtube playlist and video -
You can find the explanation for the Utility functions i.e. “get_genome_sequence”, “get_genome_value” and “fitness_func” in part II of the article series. You can find the article here.
So without further ado, let’s start with the code ….
Restart-Base Genetic Algorithm Class -
This class consists of the following member variables which are initialized using the “super().__dict__.update(kwargs)” statement -
- Cycle: Maximum number of Generations to iterate.
- Genome Size: The size of the genotype i.e. the number of items in the knapsack.
- Population Size: The number of individuals in each generation.
- Crossover Scheme: The type of Crossover operation to be performed.
- Mutation Scheme: The type of Mutation operation to be performed.
- Fitness Function: Function that is used to evaluate the quality of an individual.
- Seed Range: Genome value range i.e. The minimum decimal value of an individual and the maximum decimal value of an individual.
- Encoding Function: Function that is used to encode the genome sequence to the genome value.
- Decoding Function: Function that is used to decode the genome value to the genome sequence.
Driver Method -
The “driver” method is like the main function of our class. This is where the methods for the stages of the Genetic Algorithm are called. For each cycle, a new population is initialized, then we run a “survival” while loop which performs “selection”, “crossover”, and “mutation” until there is only a single survivor left.
Within the “survival” loop, we have the restart-base condition, i.e. -
- We generate a random float value between 0 and 1, check this against a set threshold restart rate which is 0.995 by default; Or
- We check if the winner genome of this population satisfies a threshold value.
Note: The threshold condition could be calculated based on either the weight vector or the value vector. We will better understand this below when we look at the function call.
If any of the above criteria evaluates as true, we augment the population with a randomly generated population and continue the survival loop. When this survival loop end, we save the winner genome in a separate list.
This survival loop is repeated for a couple of generations and each winner genome is added to the list. We then return the genome with the highest fitness score and the Genetic Algorithm Cycle ends.
Main Run -
Here we load the values from the JSON file into the knapsack object and we initialize the Restart-Base Genetic Algorithm object. We then call the driver method and print the winner genome.
Note: On-Line 24, we use the Knapsack Objects Weights as the threshold vector and 75% of the Knapsack Capacity as the threshold value. This means that if our winner genome for any cycle iteration does not fill at least 75% of the Knapsack, then we continue the survival loop after adding more members to the population.
Output -
Capacity: 4098Number of Items: 15Weights: [29, 75, 118, 215, 311, 330, 334, 368, 431, 536, 697, 935, 1059, 1170, 1366]Values: [71, 155, 217, 324, 431, 493, 499, 543, 609, 752, 936, 1189, 1349, 1479, 1693]100%|███████████████████████████████| 5/5 [00:01<00:00, 4.21it/s]Sequence: [1 1 1 1 0 1 1 1 1 1 1 1 0 0 0]Genome Value: 31736Profit: 5788Capacity Used: 4068
Island Genetic Algorithm Class -
The class consists of the same member variables as the Restart-Base Genetic Algorithm which is initialized using the “super().__dict__.update(kwargs)” statement.
Note: We are using “ThreadPoolExecutor” and NOT “ProcessPoolExecutor” because the former run each of your workers in separate threads within the main process while the latter runs each of your workers in their own separate child processes.
This impacts our program in the sense, that if we use different child processes for the program, we are unable to share object variables between the child processes and it leads to a pickling error exception.
Crossover-Mutation Member -
This function acts as a combined function of the crossover and mutation step. This is done for simplifying the threading process. The combiner function acts as a serial pipeline of functions that each thread needs to execute.
Driver Method -
The “driver” method is the main function of our class. This is where the methods for the stages of the Genetic Algorithm are called. For each cycle, a new population is initialized, then we run a “survival” while loop which performs “selection”, “crossover_mutation”, and population union until there is only a single survivor left. Let’s explore the threading of “crossover_mutation” stepwise -
- Step 1: We create a ThreadPoolExecutor Object.
- Step 2: Next we create a list of threads, where each thread is supplied a pipeline method and its input parameter.
- Step 3: Then, we run the “as_completed” method over the list of threads, this is a blocking operation and yields threads as and when they are completed.
- Step 4: Each thread when completed returns its result using the “result” method, which is then added to a list.
The population union operation is basically a union operation over the population generated by the parallel threads of “crossover_mutation”.
Main Run -
Here we load the values from the JSON file into the knapsack object and we initialize the Island Genetic Algorithm object. We then call the driver method and print the winner genome.
Note: On-Line 24, the first parameter corresponds to the “selection_rate” i.e. the percentage of the population that moves forward from one survival loop iteration. The second parameter corresponds to the number of threads to be created, i.e. the number of “crossover_mutation” operations to be performed in parallel. The higher the number, the more variety in the evolution can be expected. But this comes with a minor overhead caused due to the increase in population.
Output -
Capacity: 4098Number of Items: 15Weights: [29, 75, 118, 215, 311, 330, 334, 368, 431, 536, 697, 935, 1059, 1170, 1366]Values: [71, 155, 217, 324, 431, 493, 499, 543, 609, 752, 936, 1189, 1349, 1479, 1693]100%|███████████████████████████████| 20/20 [00:00<00:00, 27.56it/s]Sequence: [1 1 1 1 0 1 1 1 1 1 1 1 0 0 0]Genome Value: 31736Profit: 5788Capacity Used: 4068
Modified Genetic Algorithm Class -
Before moving forward with the code, let’s have a look at the Psuedo-Code for this algorithm.
Now let us go ahead with the code -
This class consists of the following member variables which are initialized using the “self.__dict__.update(kwargs)” statement -
- Cycle: Maximum number of Generations to iterate.
- M Parallel: The number of Parallel Thread to be executed i.e. the number of Divisions of Search Space.
- Genome Size: The size of the genotype i.e. the number of items in the knapsack.
- Inner Genetic Algorithm Data: The data member values using to initialize the Sub-Genetic Algorithm same as that for Restart-Base, Island, and Traditional Genetic Algorithms.
We run a loop to initialize the Genetic Algorithm objects while specifying the range of their respective search spaces.
Generate Super Population Method -
This method is an iterator. It returns the superior population by running each of the sub-population threads each running an independent Genetic Algorithm over their respective search space divisions. This is implemented in a similar manner to that of the Island Genetic Algorithm Driver method.
Driver Method -
The “driver” method is the main function of our class. This is where the methods for the stages of the Genetic Algorithm are called. For each cycle, a new population is initialized, then we run a “survival” while loop which performs “selection”, “crossover” and“mutation” until there is only a single survivor left. This is an exact implementation of the Restart-Base Genetic Algorithm with the only difference that instead of running the “init_population” method, we use a fresh superior population generated as explained before by using the “generate_superior_population” method.
Main Run -
Here we load the values from the JSON file into the knapsack object and we initialize the Modified Genetic Algorithm object with the Outer Genetic Algorithm data and the Inner Genetic Algorithm data. We then call the driver method and print the winner genome.
Output -
Capacity: 4098Number of Items: 15Weights: [29, 75, 118, 215, 311, 330, 334, 368, 431, 536, 697, 935, 1059, 1170, 1366]Values: [71, 155, 217, 324, 431, 493, 499, 543, 609, 752, 936, 1189, 1349, 1479, 1693]100%|███████████████████████████████| 5/5 [00:01<00:00, 5.17it/s]Sequence: [1 1 1 1 0 1 1 1 1 1 1 1 0 0 0]Genome Value: 31736Profit: 5788Capacity Used: 4068
You can find the complete python implementation here. 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 -
