Fitness function
Encyclopedia
A fitness function is a particular type of objective function that is used to summarise, as a single figure of merit
, how close a given design solution is to achieving the set aims.
In particular, in the fields of genetic programming
and genetic algorithm
s, each design solution is 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 design solutions, and to breed
'n' new ones from the best design solutions. Each design solution, therefore, needs to be awarded a figure of merit, to indicate how close it came to meeting the overall specification, and this is generated by applying the fitness function to the test, or simulation, results obtained from that solution.
The reason that genetic algorithms are not a lazy way of performing design work is precisely because of the effort involved in designing a workable fitness function. Even though it is no longer the human designer, but the computer, that comes up with the final design, it is the human designer who has to design the fitness function. If this is designed wrongly, the algorithm will either converge on an inappropriate solution, or will have difficulty converging at all.
Moreover, the fitness function must not only correlate closely with the designer's goal, it must also be computed quickly. Speed of execution is very important, as a typical genetic 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:
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.
Definition of the fitness function is not straightforward in many cases and often is performed iteratively if the fittest solutions produced by GA are not what is desired. In some cases, it is very hard or impossible to come up even with a guess of what fitness function definition might be. Interactive genetic algorithms address this difficulty by outsourcing evaluation to external agents (normally humans).
Figure of merit
A figure of merit is a quantity used to characterize the performance of a device, system or method, relative to its alternatives. In engineering, figures of merit are often defined for particular materials or devices in order to determine their relative utility for an application...
, how close a given design solution is to achieving the set aims.
In particular, in the fields of genetic programming
Genetic programming
In artificial intelligence, genetic programming is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. It is a specialization of genetic algorithms where each individual is a computer program...
and genetic algorithm
Genetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s, each design solution is represented as a string of numbers (referred to as a chromosome
Chromosome (genetic algorithm)
In genetic algorithms, a chromosome is a set of parameters which define a proposed solution to the problem that the genetic algorithm is trying to solve...
). After each round of testing, or simulation, the idea is to delete the 'n' worst design solutions, and to breed
Crossover (genetic algorithm)
In genetic algorithms, crossover is a genetic operator used to vary the programming of a chromosome or chromosomes from one generation to the next. It is analogous to reproduction and biological crossover, upon which genetic algorithms are based...
'n' new ones from the best design solutions. Each design solution, therefore, needs to be awarded a figure of merit, to indicate how close it came to meeting the overall specification, and this is generated by applying the fitness function to the test, or simulation, results obtained from that solution.
The reason that genetic algorithms are not a lazy way of performing design work is precisely because of the effort involved in designing a workable fitness function. Even though it is no longer the human designer, but the computer, that comes up with the final design, it is the human designer who has to design the fitness function. If this is designed wrongly, the algorithm will either converge on an inappropriate solution, or will have difficulty converging at all.
Moreover, the fitness function must not only correlate closely with the designer's goal, it must also be computed quickly. Speed of execution is very important, as a typical genetic algorithm must be iterated many times in order to produce a usable result for a non-trivial problem.
Fitness approximation
Fitness approximation
In function optimization, fitness approximation is a method for decreasing the number of fitness function evaluations to reach a target solution...
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.
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
Niche differentiation
The term niche differentiation , as it applies to the field of ecology, refers to the process by which natural selection drives competing species into different patterns of resource use or different niches...
or co-evolving
Co-evolution
In biology, coevolution is "the change of a biological object triggered by the change of a related object." Coevolution can occur at many biological levels: it can be as microscopic as correlated mutations between amino acids in a protein, or as macroscopic as covarying traits between different...
the set of test cases.
Another way of looking at fitness functions is in terms of a fitness landscape
Fitness landscape
In evolutionary biology, fitness landscapes or adaptive landscapes are used to visualize the relationship between genotypes and reproductive success. It is assumed that every genotype has a well-defined replication rate . This fitness is the "height" of the landscape...
, which shows the fitness for each possible chromosome.
Definition of the fitness function is not straightforward in many cases and often is performed iteratively if the fittest solutions produced by GA are not what is desired. In some cases, it is very hard or impossible to come up even with a guess of what fitness function definition might be. Interactive genetic algorithms address this difficulty by outsourcing evaluation to external agents (normally humans).