# Scan Matching by Cross-Correlation and Differential Evolution
## 3 Background
### Differential Evolution  
Differential evolution (DE) is a successful stochastic evolutionary optimization method for continuous parameter optimization [55; 56]. It is an evolutionary optimization process based on the concept of scaled vector differentials. The DE represents a continuous alternative to the widespread genetic algorithms that work with a discrete encoding of the candidate solutions. Both algorithms are nature-inspired problem-solving strategies that evolve a population of candidate solutions. On the other hand, they use different solution encodings (real-valued vs. discrete one), apply different operations to evolve the population and as a result implement different search strategies. Figure 3: Degree of alignment approaches: (**a**) Area comparison (**b**) Boundary line comparison. The DE algorithm has a history of successful applications in many industrial and engineering domains. It was designed as a generic global optimization metaheuristic but with practical engineering applications in mind [56]. It was used, among others, to predict the ground state structures of hydrogenated amorphous silicon (Si-H) clusters in material science, to streamline non-imaging optical design in optics and lightning development, to achieve 3D image registration in healthcare imaging, to design transversal digital filters in electronics and in particular signal processing, to fuse sensor data in robotics, to optimize industrial compressor supply systems, to realize system identification for decision making and in general in the area of robotics and expert systems [56]. The algorithm has also been applied in electrical engineering and electromagnetics. For example, it was used to optimize design of antennas for low signal-to-noise ratio conditions, to improve power allocation for the interleave-division multiple-access channel access method, to optimize antenna locations in a wireless network for maximum space coverage and to optimize source pulses and detection template in ultra-wideband radio systems. In the area of electromagnetics, the DE has been used to solve electromagnetic inverse scattering problems, the frequency assignment problem with real-world constraints and multiple objectives and to model large devices with distributed dipoles [56]. The wide variety of industrial applications shows that the DE is a metaheuristic optimization algorithm popular among practitioners. In this article, it is used as an optimization method for the registration of two 2-dimensional laser range scans. From an optimization point of view, the DE evolves a group (population) of real-valued vectors by an iterative application of the differential mutation and crossover operations [55]. So-called trial vectors are in every iteration of the algorithm created from the current population by the differential mutation and recombined with corresponding target vectors by the crossover operator. The novel solutions the trial vectors represent are evaluated in the context of the problem and the trial vectors compete with the target vectors for survival in the population. The DE procedure starts with a randomly constructed population of \(N\) real-valued vectors. In the course of the evolution, new trial vectors are created as scaled perturbations of existing population vectors. The algorithm creates trial vectors as scaled differences of a minimum of two distinct population vectors added to a third one. If a trial vector represents a better solution than the corresponding target vector, it takes its place in the population. DE's most important control parameters are scaling factor and mutation probability [55]. The scaling factor, \(F\in[0,\infty]\), affects the rate at which the population evolves and the crossover probability, \(C\in[0,1]\), regulates the ratio of elements (vector values) that are transferred to the trial vector from the target vector. Population size, \(N\) and the choice of particular differential operators are important parameters of the top-level optimization process, too.