Question

how to write a genetic algorithm for a knapsack problem .

Answer 1

Knapsack problem is a classic combinatorial optimisation problem which aims to achieve maximum benefit without exceeding the maximum knapsack capacity.

Generic Algorithms are aim to find to best solution for a given problem from a large set of possible solutions. GA works by formulation of new solutions from the previous candidate solutions (referred as the chromosome).

Steps to write a GA

1. START

2. Randomly generate and populate a set of chromosomes

3. Calculate the fitness(it is the score that denotes the efficiency of the solution to solve the problem) of all the chromosomes

4. Create a new population from chromosome by selection , crossover and mutation.

• Selection : Selection is based on the fitness factor of the chromosomes.The higher the value the higher is the probability of selection.
• Crossover : It is the process of mixing or combining two chromosomes it by bit with one another. The new chromosome created inherits properties of both the previous chromosomes.
• Mutation. : Mutation is done after crossover to prevent all the solutions of population to fall into the same category.This is done by flipping from 1 to 0 and vice versa.

5. Replace the existing population with new population.

6. Test if the solution is optimal and solves the problem, if not then repeat the procedure.

7. END

This flowchart below will give you the detailed demonstration of the process of solving DP using GA.

The complexity of problem can be reduced by limiting the number of items placed in knapsack or by fixing the size of population and the number of possible generations.

GA reduces the complexity of knapsack problem from exponential to linear which makes it a very highly optimal solution.