Genetic algorithm used for path-finding
The project employs a genetic algorithm to discover a path from a starting point to a goal, both identified by black spots.
A genetic algorithm is a computational technique inspired by the process of natural selection and evolution. It's often used to solve optimization and search problems. In this case optimizing for the correct set of movement that will lead to the goal. Another example could be to find a sequence of characters as seen in this precursor to this project: demo link.
The candidate solutions, represented by colored circles, begin by moving somewhat randomly. In each generation, a fitness function evaluates their performance, rewarding progress towards the goal while penalizing deviations or collisions with obstacles.
Each candidate solution is represented by a sequence of movements, described as two-dimensional vectors. One point crossover is used to combine candidate solutions.
The mutation rate determines how frequently these movements will undergo changes, crucially introducing a randomizing factor.
The top candidate solutions from the population are chosen through Tournament or Rank selection methods.
Initially, the candidate solutions move somewhat randomly, with a tendency towards upward movement. This deliberate choice accelerates the demonstration, showcasing the improvement of candidate solutions more rapidly.
Typically, after 12-15 generations, a stable solution is commonly reached. At this point, several candidate solutions successfully navigate around obstacles and reach the goal.
The project is developed as a Blazor WebAssembly application, with visualization rendered on an HTML5 canvas. A demonstration of the project can be accessed here.