# Research on Joint Resource Allocation for Multibeam Satellite Based on Metaheuristic Algorithms
## 3 Constraint Handling Method  
### Unused Bandwidth Allocation  
The metaheuristic algorithm contains operators with randomness, which cause some individuals not to satisfy the constraints and become invalid solutions. Solutions to deal with invalid solutions often include discarding, repairing, penalizing, and transferring; the UBA described below uses the repair method.  
As depicted in Figure 2, the unused bandwidth allocation (UBA) method [20] is utilized primarily to address the bandwidth constraint of invalid solutions. When using UBA, all beams are encoded and optimized, such that all neighboring beam pairs have bandwidth overlap constraints.  
We assume a sequence of adjacent beams with \(N_{b}\) beams; a corresponding individual in the algorithm is \(X=[XP,XB]\), where \(XP\) and \(XB\) denote the power vector and the bandwidth vector, respectively. The bandwidth constraint can be handled as follows:  
1. With a probability of 0.5, the starting beam is selected as 1 or \(N_{b}\). The beam pair is expressed as follows: \[(beam_{a},beam_{b}),b=a+1,a\in\{1,2,\cdots,N_{b}-1\},\] (12) \[(beam_{a},beam_{b}),b=a-1,a\in\{N_{b},N_{b}-1,\cdots,2\}.\] (13)2. For each pair of beams \((beam_{a},beam_{b})\), if \(xb_{a}+xb_{b}>1\) is satisfied, the operation \(xb_{b}=1-xb_{a}\) is performed in order to ensure that constraint \(\mathcal{C}_{4}\) is satisfied; however, some bandwidth may be unused.  
Using a column of four adjacent beams as an example, Figure 3 illustrates the underlying principle of this step. As bandwidth overlap is eliminated, unused bandwidth is gradually generated and expanded. Consequently, the bandwidth of some beams is altered; this phenomenon has a detrimental effect on the search direction of the algorithm. It is possible that when the beam's bandwidth is increased to improve the objective function, a smaller value is obtained after this step (and vice versa), causing the algorithm to search in the opposite direction.  
Figure 3: Elimination of overlapping bandwidth and the emergence of unused bandwidth.  
Figure 2: Principles of coding methods and algorithm evolution (UBA).  
3. The beams are ordered from largest to smallest based on the demand. The serial number sequence is denoted as \(SortD\). \[b_{unused}=\left\{\begin{array}{c}1-xb_{i}-\max(xb_{L},xb_{R})\\ 1-xb_{i}-xb_{A}\end{array}\right.,\] (14) \[xb^{\prime}{}_{i}=xb_{i}+b_{unused},i\in SortD,\] (15) where \(xb_{L}\) and \(xb_{R}\) denote the bandwidths of the adjacent beams when beam \(i\) has two adjacent beams, whereas \(xb_{A}\) is the bandwidth of the adjacent beam when beam \(i\) has only one adjacent beam. As shown in Figure 2, for population evaluation, the bandwidth vector must be transformed into a bandwidth allocation vector: \[bw_{i}=xb^{\prime}{}_{i}\times B_{tot},i\in\{1,2,\cdots,N_{b}\}.\] (16)  
The UBA method has two issues: First, in step 2, it needs to repair the positions of a significant number of particles in the algorithm population while only ensuring that this portion of particles satisfies the constraint rather than having performed a valid search. These particles do useless work with greater probability, in addition to increasing the computational complexity. Second, the low-bandwidth flexibility of each beam affects the algorithm's ability to search the solution space, reducing its global optimization capability.