# An Improved Adaptive Genetic Algorithm for Two-Dimensional Rectangular Packing Problem
## 3 Improved Adaptive Genetic Algorithm
### Adaptive Crossover Operator and Mutation Operator
\(f^{\prime}\) is the fitness value of the larger individuals that are ready to implement crossover; \(f_{\max}\) is the maximum fitness value of the current population; \(f_{avg}\) is the average fitness value of the current population. The \(\lambda\) is an adjustable weight parameter with the range of \(0<\lambda<1\), and \(\lambda=0.6\) in the experiment. \((1-e^{-ct})/(1+e^{-ct})\) in Formula (2) has a value range of 0-1 when \(t\) is greater than or equal to 0, which ensures that \(P_{c}(t)\) changes between \(P_{c2}\) and \(P_{c1}\). It also helps to solve the problem for AGA [29] that is greatly affected by the contemporary optimal fitness, representing the fitness function range with appropriately adjusting \(P_{c1}\) and \(P_{c2}\). It is beneficial to combine with AGA [26]. The \(t\) is recorded after each iteration to determine the change of \(P_{c}(t)\). If \(t\) becomes larger, it shows that the optimal fitness of the population evolution has not changed, and the crossover probability needs to be increased to promote the change of the optimal fitness. If \(t=0\), it reveals that the optimal fitness of the population evolution has increased, and the crossover probability \(P_{c}(t)\) will drop to \(P_{c2}\) for increasing more possible solutions. Then, combining Formula (3) to increase the difference of crossover operation for different individuals. Combining Formula (2) and Formula (3), it works together to find a better solution from the global perspective of population evolution and the local perspective of individual fitness. In addition, because it can increase the crossover probability from the perspective of the population evolution process, it is also helpful to overcome the problem that evolution is likely to stagnate when \(f_{avg}\) is close to \(f_{\max}\). The effect of the adaptive mutation probability change in the latter part is similar to this. When carrying out crossover, the packing sequence gene string adopts the partial matching crossover (PMX), and the rotating state gene string adopts the two-point crossover method. An example of the crossover process is shown in Figure 4. The procedure of the hybrid adaptive crossover algorithm is described in Algorithm 2. ```
\(\text{HACA}(t,P,PS)\):
1 Initialize the parameter \(P_{c1},P_{c2},c,\lambda\)
2 Copy population \(P^{\prime}\) from the population \(P\) with \(PS\) individuals
3 Compute \(P_{c}(t)\) with formula (2)
4 Compute \(f_{\max},f_{avg}\) for \(P\)
5 fori in range(0, \(PS,2\)):
6 Randomly select two different parents \(E_{1},E_{2}\) from \(P\)
7 Compute greater fitness \(f^{\prime}\) from \(E_{1},E_{2}\)
8 Compute \(P_{c}(f^{\prime})\) with formula (3) and \(P_{c}\) with formula (4)
9 Generate a random number \(r\) between [0, 1] with rand() function
10 if\(r<P_{c}\):
11 Generate different random numbers \(r_{1},r_{2}\) within \([1,n]\) and \(r_{3},r_{4}\) within \([n+1,2n]\)
12 Get two crossed children using the same method of Figure 4
13 Put two crossed children with Heuristic Packing Procedure
14 Update \(P^{\prime}[i],P^{\prime}[i+1]\) using two crossed children
15 Add \(P^{\prime}\) to \(P\), Sort them in decreasing order of fitness
16 Delete \(PS\) individuals with small fitness and get crossed population \(P\)
17 return crossed population \(P\)
```  
**Algorithm 2** Hybrid adaptive crossover algorithm  
Figure 4: Partial matching crossover (PMX) and two-point crossover (\(n=8,r_{1}=4,r_{2}=6\), \(r_{3}=11,r_{4}=14\)). The adaptive description of mutation probability is as follows:  
\[P_{m}(t)=P_{m2}+(P_{m1}-P_{m2})\frac{1-e^{-ct}}{1+e^{-ct}},t\geq 0 \tag{5}\]  
\[P_{m}(f)=\left\{ \begin{array}{ll}P_{m1}-\frac{(P_{m1}-P_{m2})(f-f_{avg})}{f_{ max}-f_{avg}}&,f\geq f_{avg}\\ P_{m1}&,f<f_{avg}\end{array} \right. \tag{6}\]  
\[P_{m}=\lambda P_{m}(t)+(1-\lambda)P_{m}(f) \tag{7}\]  
where \(P_{m1}\) and \(P_{m2}\) are the upper bound and lower bound of \(P_{m}\). In the experiment, these two mutation probability parameters recommended are 0.1 and 0.5 respectively [36]; i.e., \(P_{m1}=0.5\) and \(P_{m2}=0.1\).