# An Application of Simulated Annealing in Compensation of Nonlinearity of Scanners
## 2 Materials and Methods
The algorithm then reconstructs the driving signal (that approximates a triangular signal) using a combination of a positive right ramp with a negative left ramp. The first (growing) ramp is generated using the optimization algorithm, and the next (decreasing) ramp is obtained by mirroring the left ramp with respect to the \(y\)-axis. The initial normalized value of all tiny slopes is 1. This means that the initial signal to drive the scanners was a triangular signal. The optimization algorithm alters the slopes of the short ramps and hence the shape of the driving signal iteratively in such a way that the FFT spectrum of the photodetected signal became narrower and the peak of the main component in the spectrum taller. There are two main loops in the optimization algorithm as explained in Algorithm 1: A local search loop (LSL) alters the slope of each short ramp randomly in the range of +0.01 to +0.3 with steps of 0.01; A global search loop (GSL) alters the slope of each short ramp randomly in the range of +1 to +3 with a step of 0.01. As explained in [35; 36], the use of the global search in the optimization algorithm is necessary to find an optimum around which the global optimum can be found through the local search loop. The algorithm continues until a certain number of iterations is reached or until the rate of improvement becomes too slow (\(<\)1%). In the optimization algorithm, attention is paid to: (1) the range of the perturbation of the slopes in the local and global search loops and (2) the appropriate length of the signal that FFT is applied to. In this study, the algorithm stopped after 10,000 iterations, however, in most cases it has converged after around 4000 iterations. For 10,000 iterations, the algorithm took about 5 s using a quad core 3 GHz PC with 16 GB RAM. Figure 2: The experimental setup of the compensation/optimization system. Metal plate with hexagonal holes in front of the scanning probe head (outlined with red broken line). In general, if a computing task is well-suited to single instruction multiple data (SIMD) parallelization then it will be well-suited to computation on a GPU. The data-parallel computations with high arithmetic intensity exist in our algorithm were able to attain maximum performance from a GPU. This was because the volume of very fast arithmetic instruction can 'hide' the relatively slow memory accesses. We are in the process of implementing the code in a GPU (XFX-AMD Radeon RX 580 GTS, Advanced Micro Devices, Austin, TX, USA) following the method described in [37]. Based on the initial preview, for 100,000 iterations, the algorithm takes about 400 ms.  
```
Start: Initialization Send an initial slope vector (1) to reconstruct a triangular signal Record the peak of FFT (PFFT) as BestMax Record the slope vector as BestShape Loop (local search loop (LSL)): Perturb slopes in the interval [0.1 0.3] If PFFT \(>\) BestMax BestMax = PFFT Update BestShape Endif Loop (global search loop (GSL) Perturb slopes in the interval [1 3] If PFFT \(>\) BestMax BestMax = PFFT Update BestShape Endif Endloop (LSL) End
```  
**Algorithm 1**