# Query Optimization in Distributed Database Based on Improved Artificial Bee Colony Algorithm
## 2 Proposed Method
### Genetic Operators  
In this paper, the three operators of selection, crossover, and mutation in the genetic algorithm [36] are introduced to overcome the problem that the traditional artificial bee colony algorithm has a slow convergence speed and easily falls into local optimization. The chromosome in the genetic algorithm consists of \"genes\", in which the chromosome and the food source in the artificial bee colony algorithm are consistent, both representing a feasible solution, i.e., a query execution plan. The genes represent the sites where the data shardings are located in the query; the value of the genes represents the location of the sites where the data are located; and the length of the chromosome represents the length of the data shardings involved in the from statement in the query. Selection operator: this operation is based on the selection rate to determine the individuals to be subjected to crossover and mutation operations. In this method, the parameters will be initialized at the beginning of the algorithm, where \(P_{select}\) is the selection rate. In the leader bee and follower bee search phase, for the food source \(X_{i}\) currently being searched, a uniformly distributed random number \(r\) is generated in [0, 1], and the crossover and mutation operations are performed on the food source \(X_{i}\) if \(P_{select}\) is greater than \(r\). Crossover operator: the crossover operation is the key to improving the global search capability of the overall algorithmic model, which can improve the diversity of the solution set to avoid falling into local optimal solutions. This operation randomly selects multiple crossover points in the two chromosomes, and crossover interchanges the two chromosomes according to the gene values corresponding to the selected positions in order to generate two new chromosomes. Shown in Figure 3 is the two-point crossover operation, and the number of specific selections of crossover positions is obtained from Equation (8):  
\[N_{cross}=P_{cross}\cdot Len(X) \tag{8}\]  
where \(N_{cross}\) is the number of crossover points in the crossover operation, \(P_{cross}\) is the crossover rate, and \(Len(X)\) is the length of the chromosome, i.e., the food source. Mutation operator: this operation changes the values of multiple random genes in a chromosome to produce a new chromosome. Shown in Figure 4 is a two-point mutation operation, with the number of crossover points obtained from Equation (9):  
\[N_{mutation}=P_{mutation}\cdot Len(X) \tag{9}\]  
where \(N_{mutation}\) is the number of variant points in the mutation operation, \(P_{mutation}\) is the mutation rate, and \(Len(X)\) is the length of the chromosome. The mutation operation is shown in Equation (10):  
\[X_{id}{}^{\prime}=Random(L_{d}-X_{id}). \tag{10}\]  
In the equation, \(d\) is the mutation point position selected for the food source \(X_{i}\), \(X_{id}\) is the value of the corresponding mutation point, \(X_{id}\) is the value of this point after the mutation operation, and \(Random(L_{d}-X_{id})\) denotes that a data site with this data sharding that is not equal to \(X_{id}\) is randomly selected in the row where the \(d\)-th data sharding is located in the search domain matrix. Figure 4: Two-point mutation operator example. Figure 3: Two-point cross-operator example. Similarly, the selection rate, crossover rate, and mutation rate of the genetic operator corresponding to each food source dynamically change with the iterative process of the overall population, as shown in Table 2:  
In the table, \(P_{select}\), \(P_{crossover}\), and \(P_{mutation}\) are the selection, crossover, and mutation rates set at initialization, respectively, and \(\eta\) is the dynamic perturbation factor of the current food source. Example: D1, D2, D3, D4, D5, and D6 are the data shardings that need to be accessed in the query. Assume that these six shardings are distributed in nine sites as S1, S2, S3, S4, S5, S6, S7, S8, and S9.