GeneticAlgorithm - Shortest Path

Project made for the Genetic Algorithms class

The problem

Find the shortest path between between two positions in a map/matrix, following these movement conditions:

• An individual may only move one position at a time (diagonals included);

• Visiting a position already visited before is allowed.

The algorithm

The algorithm is made out of 4 steps:

• Create initial population;

• Fitness function;

• Crossover;

• Mutation;

Fitness function

Given a threshold, only select individuals which path length is less or equal than the given threshold.

Crossover

Given intersection points of two individuals, create a new one combining the segments of the parents at random.

Image credits: https://stackoverflow.com/questions/12687963/genetic-algorithms-crossover-and-mutation-operators-for-paths

Mutation

The mutation is made by selecting part of the individual's path and creating a new one, with a new random length, increasing variability.

Explaining video (PT-BR)

https://drive.google.com/file/d/1oM82fZIgWDyuzrUFMGKBfOJk3v6g30qv/view?usp=sharing