# Hybrid Approach with Improved Genetic Algorithm and Simulated Annealing for Thesis Sampling
## 2 Background
### Simulated Annealing  
Simulated annealing (SA) is a learning method that simulates the physical quenching process in thermodynamics. Its starting point is based on the similarity between the annealing process of solid materials in physics and general combinatorial optimization [11]. It is a greedy algorithm, but its search process introduces random factors. When iterating to update the feasible solution, a solution worse than the current solution is accepted with a certain probability, so it is possible to get the optimal global solution by jumping out of the local optimal solution [12]. In [13; 14; 15], the simulated annealing algorithm was improved or combined with other algorithms to achieve a better performance in experiments.  
Figure 2 is an example. Assuming that the initial solution is the left blue point \(A\), the simulated annealing algorithm will quickly search for the optimal local solution \(B\), but after searching for the optimal local solution, it does not end there, but will move to the left with a certain probability. Maybe after a few of these non-locally optimal moves, the global optimum \(D\) is reached, and the local minimum jumps out.  
Figure 2: Simulated annealing algorithm.  
According to the principle of thermodynamics, when the temperature is \(T\), the probability of the temperature drop with the energy difference of \(dE\) is \(p(dE)\), which is expressed as:  
\[p(dE)=\exp(\frac{dE}{kT}), \tag{1}\]  
where \(k\) is the Boltzmann constant; the value is \(1.3806488\times 10^{-23}\), and \(dE<0\). Therefore \(dE/kT<0\), so the value range of the \(p(dE)\) function is (0,1). In fact, the more intuitive meaning of this formula is: the higher the temperature, the greater the probability that the energy difference is \(p(dE)\), and the lower the temperature, the lower the probability of temperature drop.  
In practical problems, the calculation of \"certain probability\" here refers to the annealing process of metal smelting. Assuming that the currently feasible solution is \(x\) and the iteratively-updated solution is \(x_{new}\), then the corresponding \"energy difference\" is defined as:  
\[\Delta f=f(x_{new})-f(x), \tag{2}\]  
and its corresponding \"certain probability\" is:  
\[p(\Delta f)=\left\{\begin{aligned} & 1,& if& \Delta f>0\\ &\exp(\frac{\Delta f}{kT}),& if& \Delta f\leq 0\end{aligned}\right. \tag{3}\]  
Here, let \(k=1\). The simulated annealing algorithm can be described as below,  
1. Initialization: initial temperature \(T\) (sufficiently large), original best solution \(x\) obtained after GA applied; solution obtained from the previous iteration \(x_{new}\).
2. Calculate the increment \(\Delta f=f(x_{new})-f(x)\), where \(f(x)\) is the optimization target. Here, it is the function that minimizes the mean absolute error \(\epsilon\) calculated according to the sampling rules after the sampling result is obtained by decoding the solution. We use the result of one minus \(\epsilon\) to represent the fitness function value; see Section 3.4.
3. If \(\Delta f>0\), \(x_{new}\) is accepted as the new current solution, otherwise \(x_{new}\) is accepted as the new current solution with the probability \(\exp(\frac{\Delta f}{kT})\).
4. If the termination condition is satisfied, the current solution is output as the optimal solution to terminate the program. Otherwise, wait for a new \(x_{new}\) to go to Step 2.