The following theoretical principles apply to all or almost all EAs.
No free lunch theorem The
no free lunch theorem of optimization states that all optimization strategies are equally effective when the set of all optimization problems is considered. Under the same condition, no evolutionary algorithm is fundamentally better than another. This can only be the case if the set of all problems is restricted. This is exactly what is inevitably done in practice. Therefore, to improve an EA, it must exploit problem knowledge in some form (e.g. by choosing a certain mutation strength or a
problem-adapted coding). Thus, if two EAs are compared, this constraint is implied. In addition, an EA can use problem specific knowledge by, for example, not randomly generating the entire start population, but creating some individuals through
heuristics or other procedures. Another possibility to tailor an EA to a given problem domain is to involve suitable heuristics,
local search procedures or other problem-related procedures in the process of generating the offspring. This form of extension of an EA is also known as a
memetic algorithm. Both extensions play a major role in practical applications, as they can speed up the search process and make it more robust.
Convergence For EAs in which, in addition to the offspring, at least the best individual of the parent generation is used to form the subsequent generation (so-called elitist EAs), there is a general proof of
convergence under the condition that an
optimum exists.
Without loss of generality, a maximum search is assumed for the proof: From the property of elitist offspring acceptance and the existence of the optimum it follows that per generation k an improvement of the fitness F of the respective best individual x' will occur with a probability P > 0. Thus: :F(x'_1) \leq F(x'_2) \leq F(x'_3) \leq \cdots \leq F(x'_k) \leq \cdots I.e., the fitness values represent a
monotonically non-decreasing
sequence, which is
bounded due to the existence of the optimum. From this follows the convergence of the sequence against the optimum. Since the proof makes no statement about the speed of convergence, it is of little help in practical applications of EAs. But it does justify the recommendation to use elitist EAs. However, when using the usual
panmictic population model, elitist EAs tend to
converge prematurely more than non-elitist ones. In a panmictic population model, mate selection (see step 4 of the
generic definition) is such that every individual in the entire population is eligible as a mate. In
non-panmictic populations, selection is suitably restricted, so that the dispersal speed of better individuals is reduced compared to panmictic ones. Thus, the general risk of premature convergence of elitist EAs can be significantly reduced by suitable population models that restrict mate selection.
Virtual alphabets With the theory of virtual alphabets,
David E. Goldberg showed in 1990 that by using a representation with real numbers, an EA that uses classical
recombination operators (e.g. uniform or n-point crossover) cannot reach certain areas of the search space, in contrast to a coding with binary numbers. This results in the recommendation for EAs with real representation to use arithmetic operators for recombination (e.g. arithmetic mean or intermediate recombination). With suitable operators, real-valued representations are more effective than binary ones, contrary to earlier opinion. ==Comparison to other concepts==