Mathematical optimization describes the task of finding solutions to a given problem that satisfy it in the best way possible (according to some measure). An easy method taught in school is the maximization or minimization of a given differentiable function \(f\) of \(x\) by setting the first derivative of \(f\) equal to \(0\) and then solving for \(x\). Unfortunately, relevant problems are usually a lot harder to solve. For example, many NP-complete decision problems can be phrased as important optimization problems.
One way of approaching such hard problems is to only look for a sufficiently good (and not necessarily optimal) solution. Algorithms that guide the search process to such solutions are called heuristics and are commonly applied. For classical problems, such as the Traveling Salesman Problem, heuristics are based on years of experience and research in that area. However, if one is faced with a different problem, these heuristics may not apply, and one has to start from scratch.
In order to not come up with a new optimization algorithm for each problem, general-purpose solvers exist, which try to solve a wide range of optimization problems. This is done by only making very general assumptions about the problem, for example, that the quality of a solution can be determined efficiently, and then using them for the optimization process. Oftentimes, such solvers use randomness to make decision about where to search next. The resulting algorithms are commonly referred to as randomized search heuristics (RSHs).
One important class of RSHs are evolutionary algorithms (EAs), which draw inspiration from the concept of natural evolution. EAs are algorithms that maintain and evolve a multiset of potential solutions (the population). In each iteration, new solutions are randomly generated from the population by means of various operations, such as mutation or recombination. Afterward, a certain subset of best solutions is selected for the next iteration. This simple concept has proven powerful, and EAs are applied to real-world problems often with great success.
