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.
≈ 6 min read
Fitness function. encyclopegia.org, snapshot enwiki-001371946428. /a/fitness-function
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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. It is an important component of evolutionary algorithms (EA), such as genetic programming, evolution strategies or genetic algorithms.
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.
Similar quality functions are also used in other metaheuristics, such as ant colony optimization or particle swarm optimization. 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.
Two main classes of fitness functions exist: one where the fitness function does not change, as in optimizing a fixed function or testing with a fixed set of test cases; and one where the fitness function is mutable, as in niche differentiation or co-evolving the set of test cases. Another way of looking at fitness functions is in terms of a fitness landscape, which shows the fitness for each possible chromosome.
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, such as tournament selection or Pareto optimization.
Computational efficiency
The fitness function should not only closely align with the designer's goal, but also be computationally efficient. Execution speed is crucial, as a typical evolutionary algorithm must be iterated many times in order to produce a usable result for a non-trivial problem.
Fitness approximation may be appropriate, especially in the following cases: Fitness computation time of a single solution is extremely high Precise model for fitness computation is missing The fitness function is uncertain or noisy. Alternatively or also in addition to the fitness approximation, the fitness calculations can also be distributed to a parallel computer in order to reduce the execution times.
Depending on the population model of the EA used, both the EA itself and the fitness calculations of all offspring of one generation can be executed in parallel. When optimizing with the weighted sum, the single values of the O objectives are first normalized so that they can be compared.
This can be done with the help of costs or by specifying target values and determining the current value as the degree of fulfillment. 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.
Each objective o_i is assigned a weight w_i in the form of a percentage value so that the overall raw fitness f_{raw} can be calculated as a weighted sum: f_{raw} = \sum_{i=1}^O{o_i \cdot w_i} \quad \mathsf{with} \quad \sum_{i=1}^O{w_i} = 1 A violation of R restrictions r_j can be included in the fitness determined in this way in the form of penalty functions. For this purpose, a function pf_j(r_j) can be defined for each restriction which returns a value between 0 and 1 depending on the degree of violation, with the result being 1 if there is no violation.
The previously determined raw fitness is multiplied by the penalty function(s) and the result is then the final fitness f_{final} : f_{final}= f_{raw} \cdot \prod_{j=1}^R{pf_j(r_j)} = \sum_{i=1}^O{(o_i \cdot w_i)} \cdot \prod_{j=1}^R{pf_j(r_j)} This approach is simple and has the advantage of being able to combine any number of objectives and restrictions. The disadvantage is that different objectives can compensate each other and that the weights have to be defined before the optimization.
This means that the compromise lines must be defined before optimization, which is why optimization with the weighted sum is also referred to as the a priori method. In addition, certain solutions may not be obtained, see the section on the comparison of both types of optimization.
The cyber shack of Adaptive Fuzzy Fitness Granulation (AFFG) That is designed to accelerate the convergence rate of EAs. Fitness functions in evolutionary robotics: A survey and analysis (AFFG) (PDF), A review of fitness functions used in evolutionary robotics. Ford, Neal; Richards, Mark, Sadalage, Pramod; Dehghani, Zhamak.
(2021) Software Architecture: The Hard Parts O'Reilly Media, Inc. .
Text derived from https://en.wikipedia.org/w/index.php?oldid=1371946428 under CC BY-SA 4.0; modifications have been made.