## 3 Dynamic Time Slots Allocation Based on Genetic Algorithm
### Genetic Algorithm for Beam Hopping  
Genetic algorithm is a stochastic method for solving both constrained and unconstrained optimization problems. In genetic algorithm, the set of feasible solutions is considered as a population. Each individual represents a solution. Through selection, crossover and mutation in the evolution process, genetic algorithm repeatedly modifies a population of individual solutions from generation to generation [23]. To be specific, the evolution usually starts from a population of randomly generated individuals and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population, and modified based on crossover and possibly randomly mutation to obtain a new generation population [37]. Usually, the algorithm can be terminated when either a satisfactory fitness level of the population has been reached, or the maximum number of generations has been produced [23]. Thus, to solve the nonlinear optimization problem of beam hopping under time varying rain attenuation, this paper proposes genetic algorithm. As a global optimization algorithm for BHTP, it mainly includes the chromosome encoding, fitness function, and the design of the genetic operations [23]. (1) Chromosome encoding:  
For BHTP design under time-varying rain attenuation, this paper assumes K beams are in one cluster, and one beam hopping period contains W time slots. Consequently, there will be \(\left(C_{K}^{1}\right)^{W}=K^{W}\) possible solutions, which will be a tragedy for searching space dimensions. As stated above, in this paper, only one beam can be activated at a time slot in each cluster. Thus, inspired by [13], multi-action selection method can be employed to simply make the actions select one beam from K beams for illumination and repeat W times. When using a binary encoding manner, the chromosome for BH method should contain at least \(log_{2}K\) genes for both feasibility and low complexity. (2) Fitness function:  
The fitness function is used to evaluate the goodness of the chromosomes. That is to say, it measures the adaptability of individuals to the living. Individuals are selected according to their fitness value: individuals with higher fitness value are more likely to survive and reproduce the next generation. Generally, for maximization optimization problem fitness function is directly proportional to object function while minimization optimization problem fitness function is inversely proportional to object function [38]. Since the beam hopping object function of this paper is a minimization problem (to meet the user's traffic demand as much as possible with second order manner), the fitness function can be designed as:  
\[Fit(X)=\frac{1}{f(X)}=\frac{1}{\min\sum_{i}^{K}|R_{i}-\hat{R}_{i}|^{2}} \tag{12}\]  
where \(R_{i}=\sum_{j}^{\text{W}}B_{w}\cdot f_{\text{DVB-SZX}}\left(SNR_{ij}\right)\cdot T _{ij}\), as previously stated. Note that, for beam hopping under rain environment, due to time-varying rain attenuation, the SNR of each beam is also time-varying, which can be obtained by bringing Equation (3) into Equation (7). (3) Genetic operations:  
With an initial population of individuals and evaluated through their fitness function, the operators of genetic algorithm begin to generate a new and improve population from the parent generation [38]. Genetic algorithm usually consists of three classical operations: selection, crossover, and mutation. For selection, this paper uses the roulette method, which is the most common selection method, to make the individuals with higher fitness get larger probability of survival. It means that better BHTP solutions are selected as the generation. Moreover, crossover and mutation operators employ single-point exchange and uniform mutation methods respectively [23]. The process chart of proposed method is shown in Figure 3.  
Other parameters include the number of individuals in the initial population, the probability of crossover and mutation.