In this project, the knapscak problem is solved by genetic algorithm. The solving is compared on CPU and GPU.
Used the ILGPU library to run through the GPU.
Steps
Step 1
- Creating items with weight and amount values.
- Creating chromosomes from items.
- Calculating fitness values of chromosomes.
Step 2
- Calculating probabilities from fitness values.
- Calculating cumulative totals of probabilities.
Step 3
- Selection of parents with using cumulative totals
- Crossing genes of the parents
Parents
Crossover Type 1
Crossover Type 2
Note: In the GPU calculation, only type 1 crossover was used.
Step 4
- Mutation of 30-50% of the total chromosomes
- Alteraion a random number of genes
Step 5
- Ranking by amount value
- Removal of excess chromosomes
Step 6
- Go to Step 2 and repeat as many times as the number iteration