An Unity Project that shows the using of genetic algorithms for finding paths of mazes
Chromosomes are made up of blocks of genes constructed by nucleotides (A, G, C, T). Genes determine certain features of the organism such as hair color, or the shape of the ears. The different configurations that can have for example (brown, blond, black hair) are known as alleles and their position in the DNA chain is called locus.
The collection of chromosomes within a cell contains all the information necessary to reproduce that organism. This collection of chromosomes is known as the genome of the organism. The state of the alleles in a particular genome is known as the genotype of that organism. These are the instructions that can be applied to the real organism itself, which are called phenotype.
- Genome: just one Chromosome (the route)
- Chromosomes: has chromosomesLenght amount of genes with the instructions (i.e 11|10|10|01|01|00, Lenght = 6)
- Gene: is the particular instruction (i.e 10 = 2) (In this project geneLenght always is equals to 2)
- Nucleotide: 0 or 1
1001101001110000010111010100101111010010111001...
the alleles in this project represent the directions
00 => 0 = North
01 => 1 = East
10 => 2 = South
11 => 3 = West
Create the initial population randomly.
Loop until solution is found
-
Test each chromosome to see how good it is at solving the problem and assign fitness score acordingly.
-
Select two members from the current population. The selection method depends on the selected method.
-
Dependent on the crossover rate, crossover the genes from each chosen chromosome at a randomly chosen point.
-
Step trhough the chosen chromosome's bits (Nucleotides) and flip dependent on the mutation rate.
-
Repeat steps 2,3 and 4 until a new population of population size has been created
End Loop
The algorithm is executed until the loop reaches the amount of epochs or a solution is found.
-
allowRepahtMove : bool
When true, it allows the algorithm to repeat positions when creating/searchin path, walk by positions that it previously walked
-
showFittestByEpoch : bool
When true, algorithm will show the fittest genome(route) by each generation, the path will has magenta color. also shows the all time fittest in yellow color.
-
totalEpochs : int
The maximun number of times/cycles that algorithm will be executed or will try to find a solution
-
populationSize : int
The amount of genomes by each iteration (epoch)
-
reproductionMode : enum
-
parentsByEpoch
The two selected parents creates all the new population (this was just for test purposes, not recomended)
-
parentsByChild
For every child (in this project we create two childs per parents) we select new parents (could be the same, depends on the parent selection method)
-
-
parentSelectionMethod : enum
-
Random
Parents are random genomes picked from the population
-
Roulette Wheel
Parents are selected with RouletteWheelSelection method (algorithm extracted from the book) from the population
-
FittestAndRandom
One parent is the fittest genome of the generation and the other is selected randomly from the population
-
FittestAndRouletteWheel
One parent is the fittest genome of generation and the other is selected using RouletteWheelSelection method from the population
-
RandomOfSurvivors
Parents are selected randomly from the survivors population (the amount of survivors depends by epoch on de survivorsRate variable)
-
RouletteWheelOfSurvivors
Parents are selected with RouletteWheelSelection method from the survivors population
-
Fittest2OfPop
Parents are the two fittest genomes (was only for test purposes, not recomended)
-
-
survivorsRange : float
The percentage of the population that survive and are able to be selected as parents (only used when is selected a parent selection mode that involve survivors population)
-
crossoverRate : float
The probability that babies results from the parent crossover
-
mutationRate : float
The proability that a nucleotide (bit) mutates, resulting in new allele (or a gene mutates)
-
chromosomesLenght : int
The amount of genes per chromosome
-
The algorithm sometimes never found a solution, It happens when it reach a point very close to the maze exit point and then, a significant number of generations pass without finding the solution. The new population begin to be less fittest and degenerates with time (The complete species dies/extinct)
-
ParentByGeneration is a bad method to use, always use ParentsByChild method. Genomes degenerate fast and there is not heritage between generation.
-
The best results always of reproduction mode were RandomOfSurvivors and Random (still don't know why 😄). The survivors range at 0.3 (fittest 30% of the population), and with a population at Range [150 - 500]. Greater the populations is, greater probability of finding a solution.
-
Chromosomes lenght at 30 or 35 are good values. Greater chromosomes lenght is, greater probability of finding a solution.