Answers.Body: <p>How can you assess the quality of any solution without a measure of quality, which, in the context of genetic algorithms, is <em>known as</em> fitness function? The term <em>fitness function</em> is due to the well-known phrase &quot;<strong>Survival of the Fittest</strong>&quot;, which is often used to describe the Darwinian theory of natural selection (which genetic algorithms are based on). However, note that the fitness function can take any form, such as</p>
  <ul>
  <li><em>How well this solution performs in a game?</em> (in this case, solutions could, for example, be policies to play a game), or</li>
  <li><em>How close this solution is to a minimum/maximum of some function <span class="math-container">$f$</span> (more precisely, if you want to find the maximum of the function <span class="math-container">$f(x) = x^2$</span>, then individuals are scalars in <span class="math-container">$\hat{x} \in \mathbb{R}$</span>, and the fitness could be determined by <span class="math-container">$f'(\hat{x})$</span> or by how big <span class="math-container">$f(\hat{x})$</span> with respect to other individuals); check how I did it <a href="https://github.com/nbro/function_max_with_ga/blob/master/main.py" rel="nofollow noreferrer">here</a>)?</em></li>
  </ul>
  <p>The definition of the fitness function depends on what problem you want to solve and which solutions you want to find.</p>
  <p>So, you need some kind of fitness function in genetic algorithms to perform selection in a reasonable way, so that to maintain the &quot;best solutions&quot; in the population. More precisely, while selecting the new individuals for the new generation (i.e. iteration), if you don't use a fitness (which you can also call <em>performance</em>, if you like) function to understand which individuals deserve to live or die, how do you know that the new solutions are better than the previous ones? You cannot know this without a fitness/performance function, so you cannot also logically decide which individuals to kill before the next generation. Mutations alone just change the solutions, i.e. they are used to explore the space of solutions.</p>
  <p>Genetic algorithms are always composed of</p>
  <ul>
  <li>a population of solutions/individuals/chromosomes (i.e. usually at least <span class="math-container">$2$</span> solutions)</li>
  <li>operations to randomly (or stochastically) change existing solutions to create new ones (typically mutations and crossovers)</li>
  <li>a selection process that selects the new solutions/individuals for the next generation (or to be combined and mutated)</li>
  <li>a fitness function to help you decide which solutions need to be selected (or even combined and mutated)</li>
  </ul>
  <p>For more info about genetic algorithms or, more generally, evolutionary algorithms, take a look at chapter 8 and 9 of the book <a href="https://papers.harvie.cz/unsorted/computational-intelligence-an-introduction.pdf#page=160" rel="nofollow noreferrer">Computational Intelligence: An Introduction</a> by Andries P. Engelbrecht.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-25T10:16:02.807Z
Answers.LastActivityDate: 2020-10-25T11:08:36.417Z
Answers.LastEditDate: 2020-10-25T11:08:36.417Z
Answers.UserDisplayName: nbro
Answers.Body: <p>You do not always need an <em>explictly coded</em> fitness function to perform genetic algorithm searches. The more general need is for a selection process that favours individuals that perform better at the core tasks in an environment (i.e. that are &quot;more fit&quot;). One way of assessing performance is to award a numerical score, but other approaches are possible, including:</p>
  <ul>
  <li><p><a href="https://en.wikipedia.org/wiki/Tournament_selection" rel="nofollow noreferrer">Tournament selection</a> where two or more individuals compete in a game, and the winner is selected.</p>
  </li>
  <li><p>Opportunity-based selection, where agents in a shared environment - typically with limited resources and chances to compete - may reproduce as one of the available actions, provided they meet some criteria such as having collected enough of some resource. I was not able to find a canonical name for this form of selection, but it is commonly implemented in artificial life projects.</p>
  </li>
  </ul>
  <p>A key distinction between <a href="https://en.wikipedia.org/wiki/Artificial_life" rel="nofollow noreferrer">A-life</a> projects and GA optimisation projects is that in A-life projects there is no goal behaviour or target performance. Typically A-life projects are simulations with an open ended result and the developer runs a genetic algorithm to &quot;see what happens&quot; as opposed to &quot;make the best game-player&quot;. If your project is like this then you are most likely looking for the second option here.</p>
  <p>To discover more details about this kind of approach, you could try searching &quot;artifical life genetic algorithms&quot; as there are quite a few projects of this type published online, some of which use NEAT.</p>
  <p>Technically, you could view either of the methods listed above as ways of <em>sampling</em> comparisons between individuals against an unknown fitness function. Whether or not a true fitness function could apply is then partly a matter of philosophy. More importantly for you as the developer, is that you do not have to <em>write</em> one. Instead you can approximately measure fitness using various methods of individual selection.</p>
  <blockquote>
  <p>So far I've implemented most of the basics in amethyst (a parallel game engine written in rust), but I'm worried that the learning will happen very slowly. Should I approach this problem differently?</p>
  </blockquote>
  <p>It is difficult to say whether you should approach the problem differently. However, the biggest bottlenecks against successful GA approaches are:</p>
  <ul>
  <li><p>Time/CPU resources needed to assess agents.</p>
  </li>
  <li><p>Size of search space for genomes.</p>
  </li>
  </ul>
  <p>Both of these can become real blockers for ambitious a-life projects. It is common to heavily simplify agents and environments in attempts address these issues.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-21T21:32:18.763Z
Answers.Text: So, can we say that in these cases there is not a fitness function, or that we don't need to define it *explicitly*?
Answers.UserDisplayName: desertnaut
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-21T21:34:43.973Z
Answers.Text: @desertnaut Yes. You could *potentially* twist the definition of a fitness function to match those selection methods and claim that there is one. However, I think it is simpler to say that there is not one. Instead there is some threshold to being selected, such as beating an opponent in a game or meeting a prospective mate whilst having enough resources. You do still need to define the event or threshold that makes the selection.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-22T07:31:10.050Z
Answers.Text: Thanks, approach two is what I was talking about.
  My primary problem was also that I couldn't find a canonical name for this and therefore I can't really do any research on this topic. Do you know of any resources where I could learn some more?
Answers.UserDisplayName: LU15.W1R7H
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-22T08:02:34.247Z
Answers.Text: @LU15.W1R7H I would suggest searching for "artificial life genetic algorithms"
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-22T11:33:01.073Z
Answers.Text: As it is, the answer seems a few far from the main point of the question. I think it will improve a lot, and be a very useful answer, if it starts by the "artificial life genetic algorithms" reference and resumes the main points of the state of art applicable to this question.
Answers.UserDisplayName: pasaba por aqui
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-22T16:27:56.087Z
Answers.Text: @pasabaporaqui You're correct that your title would have been more fitting. But the whole problem with this question was, that I wasn't sure how to call the problem. As Neil said, there is no canonical name for what I'm trying to accomplish.
Answers.UserDisplayName: LU15.W1R7H
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-25T10:07:02.773Z
Answers.Text: I think this answer is highly misleading or even wrong. How can you measure the quality of solutions without a measure of quality, which, in the context of genetic algorithms, is known as _fitness function_ (which can take any form, really)? If you look at the pseudocode of the tournament selection they even write "choose the best individual". How can you choose the best solution without a fitness function? See my comment under [the post](https://ai.stackexchange.com/questions/24204/is-it-possible-to-perform-neuroevolution-without-a-fitness-function#comment38165_24204) for other details.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-25T10:26:33.597Z
Answers.Text: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/115489/discussion-between-neil-slater-and-nbro).
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-25T13:07:55.037Z
Answers.Text: @nbro: I've re-worded the answer to try and make it more disctinct between "a fitness function exists always in theory" (I don't believe it always does in a useful sense, but that is not part of this answer which tries to give OP some practical solutions) and "you have to write a fitness function in order to develop genetic algorithms" (which is demonstrably not true). More details of my thinking and link to teaching example referencing A-life saying much the same thing are in the chat
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-25T13:11:53.173Z
Answers.Text: @NeilSlater Right, you may not necessarily need to "code" it (procedurally), but let's say that it somehow needs to exist and you somehow need to use it for selection. I think now that your answer is not so misleading with respect to the existence of or need for a fitness function, but I would like to note that tournament selection actually requires a fitness, so I wouldn't give it as an example of a way of assessing the quality/performance that doesn't require a fitness. Tournament selection is, as the name says, a selection procedure, defined as a function of fitness [continued]
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-25T13:17:59.243Z
Answers.Text: [continued] as the pseudocode suggests (i.e. you choose the _best_, i.e. according to the fitness, individual with probability $p$, then the second-best individual with some other probability, and so on)
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-25T13:18:57.687Z
Answers.Text: @nbro:  The wikipedia pseudocode gives a very generic view of tournament selecton. Tournament selection needs an internal ranking between the opponents who are randomly selected from the whole population. It can be extremely minimal, e.g. "winner = 1, loser =0" for a two-player game. That is not the same as the fitness function over the population (which might be analogous to the ELO score). Again, importantly, the OP would not need to code such a function, they can just pick the winner of each game directly in a selection process, oblivious to any "scoring"
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-25T13:21:11.897Z
Answers.Text: @NeilSlater Well, yes, you need a way of ordering the solutions according to their "quality", and that way of evaluating the quality is typically called _fitness function_ in genetic algorithms. The way you calculate fitness, of course, depends on different factors, including how you represent the solutions (i.e. genotypes) and your goal (i.e. what you are trying to optimize).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-25T14:02:38.167Z
Answers.Text: @nbro: Another link that differentiates A-life by calling out that when a fitness function applies: https://en.wikipedia.org/wiki/Artificial_life quote: "Evolutionary algorithms are a practical application of the weak alife principle applied to optimization problems. Many optimization algorithms have been crafted which borrow from or closely mirror alife techniques. The primary difference lies in explicitly defining the fitness of an agent by its ability to solve a problem"
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-10-21T21:29:30.410Z
Answers.LastActivityDate: 2020-10-25T14:01:18.667Z
Answers.LastEditDate: 2020-10-25T14:01:18.667Z
Answers.UserDisplayName: Neil Slater
Body: <p>My question is about <strong>neuroevolution</strong> (genetic algorithm + neural network): I want to create <strong>artificial life</strong> by evolving agents. But instead of relying on a fitness function, I would like to have the agents reproduce with some mutation applied to the genes of their offspring and have some agents die through natural selection. Achieve evolution in this manner is my goal.</p>
  <p>Is this feasible? And has there been some prior work on this? Also, is it somehow possible to incorporate <strong>NEAT</strong> into this scheme?</p>
  <p>So far, I've implemented most of the basics in amethyst (a parallel game engine written in Rust), but I'm worried that the learning will happen very slowly. Should I approach this problem differently?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-10-25T10:04:00.750Z
Comments.Text: How can you assess the quality of any solution without a measure of quality, which, in the context of genetic algorithms, is _known as_ fitness function (but can take any form, really)? You need some kind of fitness function in genetic algorithms. Mutations alone just change the solutions, but how do you know that the new solutions are better than the previous ones? You cannot know this without a fitness/performance function, so you cannot also logically decide which individuals to kill before the next generation.
Comments.UserDisplayName: nbro
Tags: <neural-networks><genetic-algorithms><neuroevolution><fitness-functions><artificial-life>
Title: Is it possible to perform neuroevolution without a fitness function?
UserDisplayName: LU15.W1R7H
ThreadText: # Is it possible to perform neuroevolution without a fitness function?
  
  (Asked by: username_0 on 2020-10-21)
  
  My question is about **neuroevolution** (genetic algorithm + neural network): I want to create **artificial life** by evolving agents. But instead of relying on a fitness function, I would like to have the agents reproduce with some mutation applied to the genes of their offspring and have some agents die through natural selection. Achieve evolution in this manner is my goal.
  
  Is this feasible? And has there been some prior work on this? Also, is it somehow possible to incorporate **NEAT** into this scheme?
  
  So far, I've implemented most of the basics in amethyst (a parallel game engine written in Rust), but I'm worried that the learning will happen very slowly. Should I approach this problem differently?
  
  **Tags:** neural-networks, genetic-algorithms, neuroevolution, fitness-functions, artificial-life
  
  > **Comments:**
  > **username_1**: How can you assess the quality of any solution without a measure of quality, which, in the context of genetic algorithms, is _known as_ fitness function (but can take any form, really)? You need some kind of fitness function in genetic algorithms. Mutations alone just change the solutions, but how do you know that the new solutions are better than the previous ones? You cannot know this without a fitness/performance function, so you cannot also logically decide which individuals to kill before the next generation.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-10-21. Score: 3 | Accepted answer
  
  You do not always need an *explictly coded* fitness function to perform genetic algorithm searches. The more general need is for a selection process that favours individuals that perform better at the core tasks in an environment (i.e. that are "more fit"). One way of assessing performance is to award a numerical score, but other approaches are possible, including:
  
  * [Tournament selection](https://en.wikipedia.org/wiki/Tournament_selection) where two or more individuals compete in a game, and the winner is selected.
  * Opportunity-based selection, where agents in a shared environment - typically with limited resources and chances to compete - may reproduce as one of the available actions, provided they meet some criteria such as having collected enough of some resource. I was not able to find a canonical name for this form of selection, but it is commonly implemented in artificial life projects.
  
  A key distinction between [A-life](https://en.wikipedia.org/wiki/Artificial_life) projects and GA optimisation projects is that in A-life projects there is no goal behaviour or target performance. Typically A-life projects are simulations with an open ended result and the developer runs a genetic algorithm to "see what happens" as opposed to "make the best game-player". If your project is like this then you are most likely looking for the second option here.
  
  To discover more details about this kind of approach, you could try searching "artifical life genetic algorithms" as there are quite a few projects of this type published online, some of which use NEAT.
  
  Technically, you could view either of the methods listed above as ways of *sampling* comparisons between individuals against an unknown fitness function. Whether or not a true fitness function could apply is then partly a matter of philosophy. More importantly for you as the developer, is that you do not have to *write* one. Instead you can approximately measure fitness using various methods of individual selection.
  
  > So far I've implemented most of the basics in amethyst (a parallel game engine written in rust), but I'm worried that the learning will happen very slowly. Should I approach this problem differently?
  
  It is difficult to say whether you should approach the problem differently. However, the biggest bottlenecks against successful GA approaches are:
  
  * Time/CPU resources needed to assess agents.
  * Size of search space for genomes.
  
  Both of these can become real blockers for ambitious a-life projects. It is common to heavily simplify agents and environments in attempts address these issues.
  
  > **Comments:**
  > **username_3**: So, can we say that in these cases there is not a fitness function, or that we don't need to define it *explicitly*?  
  > **username_2**: @username_3 Yes. You could *potentially* twist the definition of a fitness function to match those selection methods and claim that there is one. However, I think it is simpler to say that there is not one. Instead there is some threshold to being selected, such as beating an opponent in a game or meeting a prospective mate whilst having enough resources. You do still need to define the event or threshold that makes the selection.  
  > **username_0**: Thanks, approach two is what I was talking about. My primary problem was also that I couldn't find a canonical name for this and therefore I can't really do any research on this topic. Do you know of any resources where I could learn some more?  
  > **username_2**: @username_0 I would suggest searching for "artificial life genetic algorithms"  
  > **username_4**: As it is, the answer seems a few far from the main point of the question. I think it will improve a lot, and be a very useful answer, if it starts by the "artificial life genetic algorithms" reference and resumes the main points of the state of art applicable to this question.  
  > **username_0**: @username_4 You're correct that your title would have been more fitting. But the whole problem with this question was, that I wasn't sure how to call the problem. As username_2 said, there is no canonical name for what I'm trying to accomplish.  
  > **username_1**: I think this answer is highly misleading or even wrong. How can you measure the quality of solutions without a measure of quality, which, in the context of genetic algorithms, is known as _fitness function_ (which can take any form, really)? If you look at the pseudocode of the tournament selection they even write "choose the best individual". How can you choose the best solution without a fitness function? See my comment under [the post](https://ai.stackexchange.com/questions/24204/is-it-possible-to-perform-neuroevolution-without-a-fitness-function#comment38165_24204) for other details.  
  > **username_2**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/115489/discussion-between-username_2-and-username_1).  
  > **username_2**: @username_1: I've re-worded the answer to try and make it more disctinct between "a fitness function exists always in theory" (I don't believe it always does in a useful sense, but that is not part of this answer which tries to give OP some practical solutions) and "you have to write a fitness function in order to develop genetic algorithms" (which is demonstrably not true). More details of my thinking and link to teaching example referencing A-life saying much the same thing are in the chat  
  > **username_1**: @username_2 Right, you may not necessarily need to "code" it (procedurally), but let's say that it somehow needs to exist and you somehow need to use it for selection. I think now that your answer is not so misleading with respect to the existence of or need for a fitness function, but I would like to note that tournament selection actually requires a fitness, so I wouldn't give it as an example of a way of assessing the quality/performance that doesn't require a fitness. Tournament selection is, as the name says, a selection procedure, defined as a function of fitness [continued]  
  > **username_1**: [continued] as the pseudocode suggests (i.e. you choose the _best_, i.e. according to the fitness, individual with probability $p$, then the second-best individual with some other probability, and so on)  
  > **username_2**: @username_1:  The wikipedia pseudocode gives a very generic view of tournament selecton. Tournament selection needs an internal ranking between the opponents who are randomly selected from the whole population. It can be extremely minimal, e.g. "winner = 1, loser =0" for a two-player game. That is not the same as the fitness function over the population (which might be analogous to the ELO score). Again, importantly, the OP would not need to code such a function, they can just pick the winner of each game directly in a selection process, oblivious to any "scoring"  
  > **username_1**: @username_2 Well, yes, you need a way of ordering the solutions according to their "quality", and that way of evaluating the quality is typically called _fitness function_ in genetic algorithms. The way you calculate fitness, of course, depends on different factors, including how you represent the solutions (i.e. genotypes) and your goal (i.e. what you are trying to optimize).  
  > **username_2**: @username_1: Another link that differentiates A-life by calling out that when a fitness function applies: https://en.wikipedia.org/wiki/Artificial_life quote: "Evolutionary algorithms are a practical application of the weak alife principle applied to optimization problems. Many optimization algorithms have been crafted which borrow from or closely mirror alife techniques. The primary difference lies in explicitly defining the fitness of an agent by its ability to solve a problem"  
  
  ---
  
  ### Answer by username_1 on 2020-10-25. Score: 1
  
  How can you assess the quality of any solution without a measure of quality, which, in the context of genetic algorithms, is *known as* fitness function? The term *fitness function* is due to the well-known phrase "**Survival of the Fittest**", which is often used to describe the Darwinian theory of natural selection (which genetic algorithms are based on). However, note that the fitness function can take any form, such as
  
  * *How well this solution performs in a game?* (in this case, solutions could, for example, be policies to play a game), or
  * *How close this solution is to a minimum/maximum of some function $f$ (more precisely, if you want to find the maximum of the function $f(x) = x^2$, then individuals are scalars in $\hat{x} \in \mathbb{R}$, and the fitness could be determined by $f'(\hat{x})$ or by how big $f(\hat{x})$ with respect to other individuals); check how I did it [here](https://github.com/username_1/function_max_with_ga/blob/master/main.py))?*
  
  The definition of the fitness function depends on what problem you want to solve and which solutions you want to find.
  
  So, you need some kind of fitness function in genetic algorithms to perform selection in a reasonable way, so that to maintain the "best solutions" in the population. More precisely, while selecting the new individuals for the new generation (i.e. iteration), if you don't use a fitness (which you can also call *performance*, if you like) function to understand which individuals deserve to live or die, how do you know that the new solutions are better than the previous ones? You cannot know this without a fitness/performance function, so you cannot also logically decide which individuals to kill before the next generation. Mutations alone just change the solutions, i.e. they are used to explore the space of solutions.
  
  Genetic algorithms are always composed of
  
  * a population of solutions/individuals/chromosomes (i.e. usually at least $2$ solutions)
  * operations to randomly (or stochastically) change existing solutions to create new ones (typically mutations and crossovers)
  * a selection process that selects the new solutions/individuals for the next generation (or to be combined and mutated)
  * a fitness function to help you decide which solutions need to be selected (or even combined and mutated)
  
  For more info about genetic algorithms or, more generally, evolutionary algorithms, take a look at chapter 8 and 9 of the book [Computational Intelligence: An Introduction](https://papers.harvie.cz/unsorted/computational-intelligence-an-introduction.pdf#page=160) by Andries P. Engelbrecht.
  
  
  ---
  
  