How to create a good fitness function?

Question

In genetic algorithms, a function called "fitness" (or "evaluation") function is used to determine the "fitness" of the chromosomes. Creating a good fitness function is one of the challenging tasks in genetic algorithms. How would you create a good fitness function?

Answer 1

In my experience, the fitness function is a way to define the goal of a genetic algorithm. It provides a way to compare how "good" two solutions are, for example, for mate selection and for deleting "bad" solutions from the population.

The fitness function can also be a way to incorporate constraints, prior knowledge you may have about the shape of the fitness landscape, or the way your crossover/recombination operators will work in that fitness landscape.

For example, the fitness function can include hard constraints like "Genes x,y, and z must all stay on one side of the surface $Ax +By +Cz = k$" by assigning the fitness value at zero if the gene values are on the wrong side of the surface. However, it's often better in a case like that soften the boundary by assigning a fitness penalty that is zero at the surface and grows larger as the gene values move farther from the surface on the wrong side of the surface.

Different fitness functions can be used for mate selection vs deleting "bad" trial solutions. For example, "mating fitness" between two potential parents A and B can be a function of how different the two parents are. By providing a mating advantage to pairs that are significantly different, the population can be forced to remain fairly diverse and thus explore a larger region of solution space, or to avoid converging to local (sub-optimum) fitness maxima. Meanwhile, the usual kind of fitness will cull the low-fitness individuals from the population and drive evolution toward high fitness.

What is often much more important is the set of variables ("genes") used to represent a trial solution, how the genes are arranged in the "chromosome", and the ways genes from two parents can be combined to form a new trial solution. Since you didn't ask about those things I won't go into detail in this answer, but if you ask in a separate question I will provide a detailed answer.

Answer 2

No magical formula

As already stated in this answer, the definition of the fitness function depends on the problem, given that it essentially determines the solutions that you are looking for, and it raises similar issues to the ones you would encounter while defining a reward function in reinforcement learning, such as fitness misspecification (in fact, the concepts of a reward function and fitness functions are similar, although, in some cases, a fitness function is more similar to a cost function in supervised learning problems: as an example, take a look at the fitness functions used to solve symbolic regression). The design of a fitness function is an engineering problem, in the sense that you need to think about the solutions you are looking for, and what represents a good and bad solution. So, I cannot give you the magical formula to define the fitness function for all problems, but I can give you some info that can be useful to guide the design of a fitness function.

What is a fitness function?

Let's start with the definition. A fitness function is a function that maps the chromosome representation into a scalar value (a real number) that quantifies the quality of the chromosome (i.e. solution), so it's a function of the form

$$ f : \Gamma \rightarrow \mathbb{R}, $$

where $\Gamma$ is the space of chromosomes (where a chromosome is a numerical encoding of a solution for your problem that is suitable for evaluation and modification).

Different types of optimization problems

There are different optimization problems that affect the definition of the fitness function [1], such as

• Unconstrained: this is the simplest case where the fitness function corresponds to your objective function
• Constrained: in this case, your fitness function could be composed of two terms: the original objective and a penalty term (that penalizes solutions that do not satisfy the constraints)
• Multi-objective: where you have multiple fitness functions (one for each objective) and the final fitness function is a combination of these multiple fitness functions; in this context, you will often encounter terms like Pareto-optimality
• Dynamic (or noisy), where the fitness of solutions can change over time or depend on some noise component (e.g. Gaussian noise)

Encodings and fitness functions

In genetic algorithms, a form of evolutionary algorithms, the chromosomes are often assumed to be binary (i.e. $\Gamma$ is a space of binary arrays), so this can limit the way you can evaluate them.

In other evolutionary approaches, the solutions may be encoded differently and represent something different than just a collection of numbers. In particular, in genetic programming, the solutions are programs, so the fitness should correspond to something that the program you are looking for is supposed to accomplish. For example, if you are looking for an analytical expression (e.g. a polynomial) that minimises the squared error with another expression, then the fitness would be e.g. the squared error.

See section 10.3 (p. 180) of [1] for more details.

Cheap fitness evaluation

One of the most desirable properties that you should look for while designing a fitness function is how cheap it is to evaluate the fitness of an individual. Ideally, the fitness evaluation should be quite cheap in order for the evolutionary algorithm to be feasible and practically useful. If it takes 1 year to perform an evaluation of an individual, then you don't get anything done. Alternatively, you can approximate the fitness of an individual, if the computation of the exact fitness is too expensive.

Absolute and relative measures

The fitness function can provide an absolute or relative (to other chromosomes in the population or other competing populations) measure of the quality of a chromosome (or solution). Relative fitness functions are used in co-evolutionary algorithms and are suited for situations where an absolute measure of the quality of a solution is not possible [1].

Fitness sharing

There is also the concept of fitness sharing (see section 9.6.1 of [1], p. 165) where the fitness of an individual can be adjusted based on the fitness of other individuals

Further reading

Apart from the [1], which has several chapters on evolutionary computation, you could take a look at Evolutionary Computation 2: Advanced Algorithms and Operators. The paper Fitness functions in evolutionary robotics: A survey and analysis (2009) also seems useful from the title and abstract (and other parts that I quickly read).