# The Path Planning of Mobile Robots Based on an Improved Genetic Algorithm
## 3 Improved Genetic Algorithm
### Improved Selection Strategy  
The traditional selection method in genetic algorithms is roulette wheel selection, where the selection probability is associated with the individual's fitness. When a few exceptional individuals dominate the population, they may be selected frequently during the selection process, causing the next generation to be quickly dominated by these individuals. As a result, the population becomes homogeneous, losing competitiveness and exploration ability, potentially falling into a local optimum. The selection probability can be expressed as  
\[\mathrm{P_{i}}=\frac{\mathrm{f_{i}}}{\sum\limits_{j=i}^{n}\mathrm{f_{j}}} \tag{3}\]where \(P_{i}\) is the selection probability of the i-th individual in the roulette wheel selection method, \(f_{i}\) is the fitness value of the i-th individual in the population, and n is the population size, where \(\mathrm{j}=1,2,\ldots,\ n\).  
To address this issue, an improved tournament selection method is proposed. This method reduces the absolute dominance of exceptional individuals by using multiple rounds of group competitions, introducing more randomness and competitive layers. As a result, individuals with lower fitness values may also be selected, effectively preserving population diversity and avoiding convergence to a local optimum. The specific steps are as follows:  
Step 1: Set the population size to n (where n is a multiple of 32).  
Step 2: Randomly divide the population into G groups, where \(\mathrm{G}=\frac{n}{32}\). Each group undergoes a layered competition, including preliminary rounds, semifinals, and finals. The competition selects the four individuals with the highest fitness in each group. In each round of the tournament, a total of 4G individuals are selected.  
Step 3: Repeat Step 2 for eight rounds of the tournament. In the end, a total of n individuals are selected.  
The improved tournament selection is shown in Algorithm 2.  
```
1:Input: Population P (size N); Fitness values F (length N)
2:Output: selected_pop
3:Initialize parameters
4: Group size \(\mathrm{G}\leftarrow\) 32; Groups per tournament \(\mathrm{K}\leftarrow\) 4; Winners per group \(\mathrm{W}\gets\) 4;
5: selected_pop \(\leftarrow\) 0;
6: \(\mathrm{T}\leftarrow\mathrm{N}/(\mathrm{K}\times\mathrm{W})\);
7:for t = 1 : T
8: I \(\leftarrow\) randperm(NP);
9: Split I into K groups \(\mathrm{G}_{1}\),..,\(\mathrm{G}_{\mathrm{C}}\)K (each size G);
10:for i = 1: K
11: \(\mathrm{S}_{1}\leftarrow\) []; \(\mathrm{S}_{2}\leftarrow\) []; \(\mathrm{W}_{\mathrm{i}}\leftarrow\) [];
12:for j: 2G_K
13: (\(\mathrm{ind}_{1}\), \(\mathrm{ind}_{2}\)) \(\leftarrow\) (\(\mathrm{G}_{\mathrm{i}}\)[j], \(\mathrm{G}_{\mathrm{j}}\)[j + 1]);
14: \(\mathrm{S}_{1}\leftarrow\mathrm{S}_{1}\cup[\mathrm{F}[\mathrm{ind}_{1}]]> \mathrm{F}[\mathrm{ind}_{2}]\)? \(\mathrm{ind}_{1}:\mathrm{ind}_{2}\)];
15:end
16:for j: 2: length(S\({}_{1}\))
17: \(\mathrm{S}_{2}\leftarrow\mathrm{S}_{2}\cup[\mathrm{F}[\mathrm{ind}_{1}]> \mathrm{F}[\mathrm{ind}_{2}]\)? \(\mathrm{ind}_{1}:\mathrm{ind}_{2}\)];
18:end
19:for j: 2: length(S\({}_{2}\))
20: (\(\mathrm{ind}_{1}\), \(\mathrm{ind}_{2}\)) \(\leftarrow\) (\(\mathrm{S}_{2}\)[j], \(\mathrm{S}_{2}\)[j + 1]);
21: \(\mathrm{W}_{\mathrm{j}}\leftarrow\mathrm{W}_{\mathrm{j}}\cup[\mathrm{F}[ \mathrm{ind}_{1}]>\mathrm{F}[\mathrm{ind}_{2}]\)? \(\mathrm{ind}_{1}:\mathrm{ind}_{2}\)];
22:end
23: selected_pop \(\leftarrow\)selected_pop \(\cup\) W_i;
24:end
25:end
```  
**Algorithm 2** Improved Tournament Selection