Abstract

Many problems in computer science can be solved in polynomial time meaning we can get solutions almost instantly (or at least after a few minutes). However, there is a large set of problems that are NP-Hard and could potentially take a lifetime to solve through thoroughly searching the solution space. To approximate an optimal solution in a reasonable amount of time, we utilise the very versatile genetic algorithm model. In this talk, I will walk through the full process of applying the genetic algorithm to a problem by using the 0-1 knapsack problem as an example. We will see how mimicking survival of the fittest and natural reproduction can help us converge from a population of possible solutions to a single optimal solution.

While I currently still intend to talk a bit about real world implementations of the GA, I’m not sure if I will have the time to fully flesh that section out, so I left it out of my initial abstract draft as I don’t want to promise something that I may not be able to fully deliver.