# Hybrid Approach with Improved Genetic Algorithm and Simulated Annealing for Thesis Sampling
## The Proposed Algorithm
### Selection, Crossover and Mutation  
The selection operator chooses some good individuals from the current population and transfers them to the next generation [18]. Methods used as the selection operator can be classified into two categories: proportional and elitist. The former category employs the probability of selection proportional to the fitness value of each individual. These methods allow maintaining a genetic diversity within the population of candidate solutions throughout the generations, which prevents GA from falling into local optima. However, these methods increase the time of convergence [19]. This paper uses the roulette wheel method making individuals with high-fitting values get a higher probability of survival. The basic idea under this method is that the probability of each individual being selected is proportional to its fitness value. The proportional selection method has enormous randomness and thus might be trapped in local extrema. The integration of simulated annealing factor into the genetic algorithm leads to avoid slow convergence rate and local extrema problem.  
The crossover operator newly produces some better individual patterns [20], which is the main element of the search process in optimization. The encoding type used in GA is the major criteria for  
Figure 3: Initialization and encoding.  
selecting the crossover. The global convergence and search space must be considered for selecting the crossover operators. the effect of crossover operators in GA is dependent on the application, as well as encoding [21]. Here, the two-point arithmetic crossover is used.  
\[\omega_{1}(t) =(\omega_{11},\omega_{21},...,\omega_{n1}) \tag{4}\] \[\omega_{2}(t) =(\omega_{12},\omega_{22},...,\omega_{n2}) \tag{5}\]  
where \(\omega_{1}(t)\) and \(\omega_{2}(t)\) are two chromosomes at time \(t\). Let two random numbers generated at time \(t\) be \(i(1\leq i\leq n)\) and \(j(0<j<1)\). Then, the two-point arithmetic crossover at the \(i\)-th locus of the above two chromosomes, respectively, as \(\omega_{1}^{{}^{\prime}}(t)\) and \(\omega_{2}^{{}^{\prime}}(t)\), is defined as follows:  
\[\omega_{i1}^{{}^{\prime}} =j*\omega_{i2}+(1-j)*\omega_{i1} \tag{6}\] \[\omega_{i2}^{{}^{\prime}} =j*\omega_{i1}+(1-j)*\omega_{i2} \tag{7}\]  
The following descendants are propagated:  
\[\omega_{1}(t+1) =(\omega_{11},\omega_{21},...,\omega_{i1}^{{}^{\prime}},..., \omega_{n1}) \tag{8}\] \[\omega_{2}(t+1) =(\omega_{12},\omega_{22},...,\omega_{i2}^{{}^{\prime}},..., \omega_{n2}) \tag{9}\]  
where, \(i\) is the locus involved in the crossover operation on the chromosome. \(n\) is the length of the chromosomes, that is, the number of genes. In this paper, it is the number of selected theses.  
The mutation operator is employed to avoid establishing a uniform population unable to evolve [22]. According to [23], the NP-complete problems are intractable, i.e., they can be solved theoretically, but in practice, they take too long for their solutions to be useful.  
Once a new generation is created after the crossover operation, the genetic process is performed iteratively until an optimal result is found. We have used the traditional genetic algorithm to solve the thesis sampling problem. More than 30,000 iterations were carried out, which took nearly 3.5 h, and the sampling effect was not ideal. By analyzing the traditional genetic algorithm, we found that the whole algorithm was time consuming. Since the mutation operator is directionless, we believe that some modifications could be made to the mutation operator based on the traditional genetic algorithm to speed up the convergence of the algorithm. Thus, an improved mutation strategy is introduced as Algorithm 1.  
Figure 4, provided below, is for easier understanding of the proposed mutation operation.  
Figure 4: Schematic diagram of the improved mutation operation.