8
$\begingroup$

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?

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Maybe you should provide references to papers that describe specific examples (just for reliability), but, after the first reading, this answer seems reasonable. I suggest that you take a look at the book "Evolutionary Computation 2: Advanced Algorithms and Operators". There you have some info that could support some of your claims. You could also talk about multi-objective problems. $\endgroup$
    – nbro
    Dec 6 '20 at 20:56
  • $\begingroup$ To be perfectly frank, I have not looked at a paper about evolutionary computation in a LONG time. My answer was based entirely on about 30 years' experience creating and using genetic algorithms. I would be willing to try to answer a question about multi-objective problems if it were asked separately, but one of the first things I learned in a Calculus of Variations class many, many years ago was that it is in general not possible to simultaneously maximize multiple independent functions. The route to success is to find reasonable ways to couple or constrain the objective functions. $\endgroup$
    – S. McGrew
    Dec 6 '20 at 23:13
1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.