How to write your first Genetic Algorithm — Knapsack Problem

Image of a man evolving from a monkey — Image by vectorpouch on Freepik

So you learned about Genetic Algorithm, but wondering how to start implementing it to solve problems? Or maybe you want to refresh your understanding?

This article will help you write your first genetic algorithm that will serve as a base for solving real-world problems.

Note: We’ll use Python 3 for better readability.

What is Genetic Algorithm?

Genetic Algorithm is a subset of Evolutionary Algorithms. It is inspired by the process of natural selection and uses biological operators like selection, crossover, mutation, etc. to find solutions. You can check this article on Wikipedia for more information.

What is Knapsack Problem?

Imagine you have a bunch of different items that you have to sell at the market, each item has a price and weight associated with it. You have a trailer with limited weight capacity. Now you want to know what items you have to put in your trailer so that your profit will be maximized while keeping the total weight of items equal to/under the trailer’s weight capacity.

Knowing the items and total profit is what we try to solve in the knapsack problem, and for this article, we’ll use the following items and capacity.