Fitness function
A fitness function is a particular type of objective or cost function that is used to summarize, as a single figure of merit, how close a given candidate solution is to achieving the set aims.
An EA is a metaheuristic that reproduces the basic principles of biological evolution as a computer algorithm in order to solve challenging optimization or planning tasks, at least approximately.
For this purpose, many candidate solutions are generated, which are evaluated using a fitness function in order to guide the evolutionary development towards the desired goal.
In the field of EAs, each candidate solution, also called an individual, is commonly represented as a string of numbers (referred to as a chromosome).
After each round of testing or simulation the idea is to delete the n worst individuals, and to breed n new ones from the best solutions.
Each individual must therefore to be assigned a quality number indicating how close it has come to the overall specification, and this is generated by applying the fitness function to the test or simulation results obtained from that candidate solution.
In the following, it is assumed that the fitness is determined based on an evaluation that remains unchanged during an optimization run.
A fitness function does not necessarily have to be able to calculate an absolute value, as it is sometimes sufficient to compare candidates in order to select the better one.
A relative indication of fitness (candidate a is better than b) is sufficient in some cases,[5] such as tournament selection or Pareto optimization.
The quality of the evaluation and calculation of a fitness function is fundamental to the success of an EA optimisation.
When setting up a fitness function, one must always be aware that it is about more than just describing the desired target state.
Rather, the evolutionary search on the way to the optimum should also be supported as much as possible (see also section on auxiliary objectives), if and insofar as this is not already done by the fitness function alone.
Definition of the fitness function is not straightforward in many cases and often is performed iteratively if the fittest solutions produced by an EA is not what is desired.
Interactive genetic algorithms address this difficulty by outsourcing evaluation to external agents which are normally humans.
The fitness function should not only correlate closely with the designer's goal, but it also should be computationally efficient.
Speed of execution is very important, as a typical evolutionary algorithm must be iterated many times in order to produce a usable result for a non-trivial problem.
[9][10][11] Practical applications usually aim at optimizing multiple and at least partially conflicting objectives.
Costs or degrees of fulfillment can then be compared with each other and, if required, can also be mapped to a uniform fitness scale.
Without loss of generality, fitness is assumed to represent a value to be maximized.
This approach is simple and has the advantage of being able to combine any number of objectives and restrictions.
[12] In addition, certain solutions may not be obtained, see the section on the comparison of both types of optimization.
The elements of the set form the Pareto front (green line).
From this set, a human decision maker must subsequently select the desired compromise solution.
[14] It was recognized early on that EAs with their simultaneously considered solution set are well suited to finding solutions in one run that cover the Pareto front sufficiently well.
[14][15] They are therefore well suited as a-posteriori methods for multi-objective optimization, in which the final decision is made by a human decision maker after optimization and determination of the Pareto front.
The advantage of Pareto optimization is that, in contrast to the weighted sum, it provides all alternatives that are equivalent in terms of the objectives as an overall solution.
However, in the case of repeated optimization of variations of one and the same task, the desired lines of compromise are usually known and the effort to determine the entire Pareto front is no longer justified.
The optimization goals include not only a general fast processing of all orders but also the compliance with a latest completion time.
The second goal is not achieved by the exemplary initial schedule, as shown in the adjacent figure.
As long as only the latest completion time is evaluated, however, the fitness of the mutated schedule remains unchanged, even though it represents a relevant step towards the objective of a timely completion of the order.
