## 3 Existing Pathfinding Techniques
### Metaheuristic Approach Algorithms
#### 3.3.1 Genetic Algorithm (GA)  
This is a very popular Algorithm belonging to the metaheuristic category of Algorithms based on the concept of natural selection. Introduced first in 1960 by [PERSON], the Algorithm has numerous applications in the fields of climatology for monitoring changes in global temperatures, neural networks, robotics, natural language processing, etc. In the world of video games, this Algorithm is used for finding the route with least cost. The search space for this Algorithm is termed as population [75]. In this population, there are several elements called chromosomes. From this population, the Algorithm generates randomly a set of chromosomes or a suitable set of solutions called the initial solution. Every element of this initial solution is inspected by a function that decides which acceptable set of chromosomes will remain until the end. This function is termed as the fitness function. The larger the value of this function, the greater the chances of survival of the move towards the next generation [76]. Figure 10 shows the six different steps involved in the Algorithm.  
1. **Initial Population:** The Algorithm begins with a set of individuals called a Population. Each individual is a solution to the problem you want to solve. An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution). In a genetic Algorithm, the set of genes of an individual is represented using a string, in terms of an alphabet. Usually, binary values are used (string of 1 s and 0 s). We say that we encode the genes in a chromosome. The distinction between a gene, chromosome and population is represented in Figure 11[77].  
Figure 10: Process flow of genetic Algorithm.  
2. **Fitness Function:** The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.
3. **Selection:** The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation. Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.
4. **Crossover:** Crossover is the most significant phase in a genetic Algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes. Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached. The new offspring are added to the population as shown in Figure 12[78].
5. **Mutation:** In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped. Mutation occurs to maintain diversity within the population and prevent premature convergence. The Algorithm terminates if the population has converged (does not produce offspring which are significantly different from the previous generation). Then, it is said that the genetic Algorithm has provided a set of solutions to our problem as shown in Figure 13[79].  
Figure 11: Distinction between population, chromosome, and gene.