# Energy-Efficient Internet of Drones Path-Planning Study Using Meta-Heuristic Algorithms
## 3 Meta-Heuristic Algorithms for Energy-Efficient IoD Path-Planning Description
### Meta-Heuristic Algorithms
#### 3.4.1 Genetic Algorithm (GA)  
GA [37] is one of the evolutionary algorithms utilized to solve NP-hard optimization problems that cannot be solved by deterministic methods in polynomial time. The notion of natural selection is used by the GA and applied to a population of potential solutions to the respective problem. The operation of the GA is shown in Figure 1.  
First, the initial population is randomly generated and then evaluated by the fitness function. The selection strategy is utilized to select the parents and produce new children through crossover and mutation. Each parent in UAV path planning represents a complete path from the start point to the end point.  
The selection method is used to determine which individuals are more likely to generate the best offspring. In this method, the most suitable individuals win the competition of reproduction, while the least fit are excluded, which improves overall fitness.  
In this part, we briefly explain the process of GA to generate a new solution, including selection, crossover, and mutation.
* Selection techniques: There are several selection techniques. The rank selection method always chooses individuals with the best fitness. If \(n\) individuals make up the population, the applied selection is carried out by ranking the solution based on its fitness. The selection method will select the \(k\) best individuals. For each individual, the probability of being selected is proportional to the corresponding fitness. The tournament selection technique is another selection method that uses proportional selection on pairs of individuals, then chooses from among these pairs the individual with the highest fitness score with a probability \(\mathbf{P}\in[0.5,1]\). This process is repeated \(\mathbf{n}\) times to obtain the \(\mathbf{n}\) individuals of populations that will serve as parents. The uniform selection method selects individuals uniformly and without reliance on the fitness value. Each individual has \(\mathbf{1}/\mathbf{N}\) probability of being selected, where \(\mathbf{N}\) is the total number of individuals in the population.
* Crossover mechanism: When two chromosomes have been selected, a crossover is made. A crossover is a mechanism used to generate new children from two individuals. The new individuals (children) inherit certain features from their parents. The genes are selected from two parents and then children are generated. The crossover probability represents the frequency with which the crossovers are applied. If there is no crossover, i.e., probability of crossover is 0%, then children are an exact copy of the parents. If there is crossover, the children are partially similar to their parents.  
ents. However, if the probability is set to 100%, then all the children are generated by crossover.
* Mutation strategies: Mutations are performed on a small proportion of randomly selected individuals. This process generates a new population. The process is repeated many times to imitate the principle of evolution, which only takes its meaning over a large number of generations. The process can be stopped after an arbitrary number of generations or when a solution has a sufficiently satisfactory score. In mutation strategy, one gene can be substituted in another chromosome randomly. A mutation rate is generally chosen between 0.001 and 0.01. It is necessary to choose a relatively low value to avoid random search and keep the principle of selection and evolution. The mutation serves to avoid premature convergence of the algorithm. For example, during an optimum search, the mutation serves to avoid convergence towards local optima.