Answers.Body: <h2>No magical formula</h2>
  <p>As already stated <a href="https://ai.stackexchange.com/a/15901/2444">in this answer</a>, 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 <a href="https://ai.stackexchange.com/a/22854/2444"><em>reward function</em></a> in reinforcement learning, such as <em>fitness misspecification</em> (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 <a href="https://github.com/DEAP/deap/blob/master/examples/gp/symbreg.py" rel="nofollow noreferrer">the fitness functions used to solve symbolic regression</a>). 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.</p>
  <h3>What is a fitness function?</h3>
  <p>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</p>
  <p><span class="math-container">$$
  f : \Gamma \rightarrow \mathbb{R},
  $$</span></p>
  <p>where <span class="math-container">$\Gamma$</span> 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).</p>
  <h3>Different types of optimization problems</h3>
  <p>There are different optimization problems that affect the definition of the fitness function [<a href="http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf" rel="nofollow noreferrer">1</a>], such as</p>
  <ul>
  <li><strong>Unconstrained</strong>: this is the simplest case where the fitness function corresponds to your objective function</li>
  <li><strong>Constrained</strong>: 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)</li>
  <li><strong>Multi-objective</strong>: 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 <strong>Pareto-optimality</strong></li>
  <li><strong>Dynamic</strong> (or noisy), where the fitness of solutions can change over time or depend on some noise component (e.g. Gaussian noise)</li>
  </ul>
  <h3>Encodings and fitness functions</h3>
  <p>In genetic algorithms, a form of evolutionary algorithms, the chromosomes are often assumed to be binary (i.e. <span class="math-container">$\Gamma$</span> is a space of binary arrays), so this can limit the way you can evaluate them.</p>
  <p>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.</p>
  <p>See section 10.3 (p. 180) of [<a href="http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf" rel="nofollow noreferrer">1</a>] for more details.</p>
  <h3>Cheap fitness evaluation</h3>
  <p>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 <strong>cheap</strong> 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.</p>
  <h3>Absolute and relative measures</h3>
  <p>The fitness function can provide an <strong>absolute</strong> or <strong>relative</strong> (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 [<a href="http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf" rel="nofollow noreferrer">1</a>].</p>
  <h3>Fitness sharing</h3>
  <p>There is also the concept of <strong>fitness sharing</strong> (see section 9.6.1 of [<a href="http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf" rel="nofollow noreferrer">1</a>], p. 165) where the fitness of an individual can be adjusted based on the fitness of other individuals</p>
  <h2>Further reading</h2>
  <p>Apart from the [<a href="http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf" rel="nofollow noreferrer">1</a>], which has several chapters on evolutionary computation, you could take a look at <a href="https://bi.snu.ac.kr/SEMINAR/EvolComp/EvolComp_Vol2.pdf" rel="nofollow noreferrer">Evolutionary Computation 2: Advanced Algorithms and Operators</a>. The paper <a href="http://www.nelsonrobotics.org/paper_archive_nelson/nelson-jras-2009.pdf" rel="nofollow noreferrer">Fitness functions in evolutionary robotics: A survey and analysis</a> (2009) also seems useful from the title and abstract (and other parts that I quickly read).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-06T21:38:59.283Z
Answers.LastActivityDate: 2021-01-20T14:04:11.443Z
Answers.LastEditDate: 2021-01-20T14:04:11.443Z
Answers.UserDisplayName: nbro
Answers.Body: <p>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.</p>
  
  <p>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.  </p>
  
  <p>For example, the fitness function can include hard constraints like "Genes x,y, and z must all stay on one side of the surface <span class="math-container">$Ax +By +Cz = k$</span>" 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.  </p>
  
  <p>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.</p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-06T20:56:52.203Z
Answers.Text: 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](https://bi.snu.ac.kr/SEMINAR/EvolComp/EvolComp_Vol2.pdf)". There you have some info that could support some of your claims. You could also talk about multi-objective problems.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-06T23:13:54.660Z
Answers.Text: 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.
Answers.UserDisplayName: S. McGrew
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-14T04:41:16.553Z
Answers.LastActivityDate: 2019-10-14T05:03:17.993Z
Answers.LastEditDate: 2019-10-14T05:03:17.993Z
Answers.UserDisplayName: S. McGrew
Body: <p>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?</p>
  
Tags: <genetic-algorithms><evolutionary-algorithms><fitness-functions><fitness-design>
Title: How to create a good fitness function?
UserDisplayName: Abbas Ali
ThreadText: # How to create a good fitness function?
  
  (Asked by: username_0 on 2018-11-22)
  
  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?
  
  **Tags:** genetic-algorithms, evolutionary-algorithms, fitness-functions, fitness-design
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-12-06. Score: 1
  
  ## No magical formula
  
  As already stated [in this answer](https://ai.stackexchange.com/a/15901/2444), 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*](https://ai.stackexchange.com/a/22854/2444) 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](https://github.com/DEAP/deap/blob/master/examples/gp/symbreg.py)). 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](http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf)], 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](http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf)] 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](http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf)].
  
  ### Fitness sharing
  
  There is also the concept of **fitness sharing** (see section 9.6.1 of [[1](http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf)], p. 165) where the fitness of an individual can be adjusted based on the fitness of other individuals
  
  ## Further reading
  
  Apart from the [[1](http://www.shahed.ac.ir/stabaii/Files/CompIntelligenceBook.pdf)], which has several chapters on evolutionary computation, you could take a look at [Evolutionary Computation 2: Advanced Algorithms and Operators](https://bi.snu.ac.kr/SEMINAR/EvolComp/EvolComp_Vol2.pdf). The paper [Fitness functions in evolutionary robotics: A survey and analysis](http://www.nelsonrobotics.org/paper_archive_nelson/nelson-jras-2009.pdf) (2009) also seems useful from the title and abstract (and other parts that I quickly read).
  
  
  ---
  
  ### Answer by username_2 on 2019-10-14. Score: 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.
  
  > **Comments:**
  > **username_1**: 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](https://bi.snu.ac.kr/SEMINAR/EvolComp/EvolComp_Vol2.pdf)". There you have some info that could support some of your claims. You could also talk about multi-objective problems.  
  > **username_2**: 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.  
  
  ---
  
  