Genetic Algorithms for Beginners

Genetic algorithms are part of the family of optimization algorithms. They operate on the theory of evolution, more particularly, genetic evolution. Each solution is a chromosome that's made up of genes, and is evaluated to determine how well it performs. This repeats until a good solution is found.

Evolution suggests that the living organisms that we see today did not suddenly exist that way, but evolved through millions of years of subtle changes, with each generation adapting to its environment. See this article for more: https://rhurbans.com/intelligence-through-evolution/.

Genetic algorithms are optimization algorithms. They are used to evaluate massive search spaces for good solutions fast. See this article for more about optimization algorithms: https://rhurbans.com/optimization-finding-the-best-solutions/. Let's dive into how genetic algorithms (GAs) work next.

When we use a GA, it is paramount to do the encoding step correctly. It requires careful design of the representation of possible states. In this case we want to figure out which items to include in the knapsack to maximize the total value and not exceed the weight limit.

Binary encoding represents a gene in terms of 0 or 1, so a chromosome is represented by a string of binary bits. For the knapsack problem, 0 = exclude the item, and 1 = include the item. We can then sum the included items' values to find how well that chromosome performs.

When the search space is small, it's fairly easy for us to figure out a good solution. But what if there were 26 possible items to add to the knapsack? It becomes much more difficult for a human to solve it by hand. Here's where GAs are useful.

A genetic algorithm evaluates the performance of each chromosome and uses mixing to make new solutions that hopefully perform better - like human reproduction. Mixing chromosomes can happen in different ways. A simple approach is to take half and half.

Genetic algorithms also use the concept of mutation. Like in nature, a random gene might be changed after reproduction between two parent chromosomes. This entire process runs for many cycles, called generations, until a good solution is found.

GAs can perform significantly faster than other methods. But remember, they're not guaranteed to find the BEST solution. I'll be elaborating on genetic algorithms with more visual explanations in upcoming articles. Follow @RishalHurbans for updates.

Thank you for reading. If you're keen to learn at your leisure, see Grokking AI Algorithms with Manning Publications: http://bit.ly/gaia-book. Or join my mailing list for infrequent knowledge drops: https://rhurbans.com/subscribe.