Outline

Origin [5 Minutes]

• Speaker introduction;
• Talk Introduction;
• Origin and Inspiration behind GA;

Theory [10 Minutes]

• Algorithm Structure;
• Initial Population;
• Solution(Chromosome, Genes);
• Fitness Function;
• Crossover;
• Mutation;
• Termination;

Hands-on [15 Minutes]

• Live code a Genetic Algorithm to make car travel to the finish line without crashing;
• Play with mutation(errors) to see how it change the solution.
• When to use GA;
• Advantages and Limitations of GA;

Ending [10 Minutes]

• Closing Note;
• key Takeaway;
• Q/A

Summary

Origin

Genetics has been the root behind the life today, it all started with a single cell making an error when dividing themselves. It was discovered by Charles Darwin & Alfred Russel Wallace in their book "On the Origin of Species", which highlighted 2 important points:

1. Survival of the fittest
2. Mutation.

This later inspired John Henry Holland to create Genetic Algorithms and write about it in his book "Adaptation in Natural and Artificial Systems"

Theory

In computer science, Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems. To understand this better we will start with an example by creating a tiny world of cars(solution), and along the way discuss the definitions.

• Decide the size of the population: N = 10
• To live, cars have to solve the problem of crossing a road without touching the borders.
• Decide the characteristics(genes) of a single individual(Chromosome).

{
  "id": "0-n",
  "length": "Length of car",
  "width": "Width of car",
  "height": "Height of car",
  "step-size": "Speed",
  "angle": "Angle at which car is driven",
  "step-taken": "Steps taken before termination; set after solution is implemented",
  "fitness": "will be between 0-1; set after the solution is implemented"
}

• Create 10 cars with a 10 random chromosomes.

{
  "id": "0",
  "length": "60",
  "width": "40",
  "height": "50",
  "step-size": "10",
  "angle": "30",
  "step-taken": "0",
  "fitness": "-1"
}
...

• Make these cars cross the road.
• Find the fitness of cars, which is how far a car was able to travel from the start.

"""
 Both angel and step-taken can be used for fitness, but angle won't be a good
 criteria cause it is only applicable if there are no other cars on the road.
 However, but for our case we will use it.
"""
def calculateFitness(carN):
    fitness = angleNearZero(carN.angle)

• Crossover top 5 cars to create 10 new cars.
• Mutate some of the chromosomes.
• Make these cars cross the road again
• Repeat above steps until all the cars can cross the road.

Genetic_Algo ()

    initialize_population ()
        for(Population size)
            {
                gene1: value,
                gene2: value
            }

   while (Termination) do
      Solve the problem
      Fitness()

      parents selection()
      crossover()
            {
                gene1: value of parent 1,
                gene2: value of parent 2
            }

      mutation()
   return best

Hands-on

Here I will live code the above example from scratch, it will most likely be in Jupiter notebook with graphics to help the audience understand better.

Key Takeaways

Writing basic Genetic Algorithm

This talk will give enough information and methods to the audience that they will be able to program their simple Genetic Algorithm, plus they will also be able to research the topic further with little or no help.

Mutation is actually an error

Without mutation(error) life is just Permutation and Combination problem, its this error which open infinite possibilities.