 |
Genetic Algorithm (GA) is an intelligent optimization algorithm, mainly used to solve optimization problems. The steps of GA can be concluded as follows:
The process begins with a set of the individual called population. An individual consists of a set of character which is gene. In TSP, an individual represented by a sequence of number means the order that UAV visits each city, a gene means a city number. A fitness function determines how fit an individual is, it will give a fitness score for every individual, a sequence with a shorter tour length means higher fitness score. And then the selection phase will select several individual for the reproduction, individuals which have higher fitness score will have a higher probability to be selected. After selection, and crossover phase with process crossover for each pair of parents, which means exchange genes based on crossover points between two sequences be selected in the previous step. Those parents and offspring formed a new generation. In certain offspring, a mutation occurs, some positions of gene changes randomly, in TSP mean gene swapping at two positions. This process will repeat until the set of iteration is reached.
The Simulated Annealing Algorithm is a general probabilistic algorithm for finding the optimal solution in a large search space [19]. It is a stochastic optimality-seeking algorithm based on the Monte- Carlo iterative solution strategy. Simulated annealing algorithm is one of the effective methods to solve TSP problems. The steps of SA are:
Start with an initial solution 𝑠_0 which is calculated by A* and an initial temperature 𝑡_0.
Choose a temperature reduction function:
Given a new solution 𝑠_1 , which is a neighbor of 𝑠_0 , calculate the difference in cost between 𝑠_0 and 𝑠_1.
If 𝑠_1 is better than 𝑠_0, then accept 𝑠_1. If 𝑠_0 is better, than generate a random number 𝑟 from 0 and 1. Then we calculate the probability of accepting 𝑠_1 by 𝑝=𝑒^(−|𝑠_0−𝑠_1 |/𝑡_0 )
If 𝑟 < 𝑝 , then accept 𝑠_1. If not, go back to Step 3.
Output the best optimal solution.
|
IEEE/ICACT20230128 Slide.09
[Big Slide]
[YouTube]