Is it possible to perform neuroevolution without a fitness function?

Question

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?

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. — nbro, Oct 25 '20 at 10:04

Neil Slater · Accepted Answer · 2020-10-25T14:01:18.667

3

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

edited Oct 25 '20 at 14:01

answered Oct 21 '20 at 21:29

Neil Slater

28,678
3
38
60

1

So, can we say that in these cases there is not a fitness function, or that we don't need to define it *explicitly*? – desertnaut Oct 21 '20 at 21:32
2

@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. – Neil Slater Oct 21 '20 at 21:34
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? – LU15.W1R7H Oct 22 '20 at 07:31
2

@LU15.W1R7H I would suggest searching for "artificial life genetic algorithms" – Neil Slater Oct 22 '20 at 08:02
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. – pasaba por aqui Oct 22 '20 at 11:33
@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. – LU15.W1R7H Oct 22 '20 at 16:27
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. – nbro Oct 25 '20 at 10:07
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/115489/discussion-between-neil-slater-and-nbro). – Neil Slater Oct 25 '20 at 10:26
@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 – Neil Slater Oct 25 '20 at 13:07
@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] – nbro Oct 25 '20 at 13:11
[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) – nbro Oct 25 '20 at 13:17
@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" – Neil Slater Oct 25 '20 at 13:18
@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). – nbro Oct 25 '20 at 13:21
@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" – Neil Slater Oct 25 '20 at 14:02

nbro · Answer 2 · 2020-10-25T11:08:36.417

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

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 by Andries P. Engelbrecht.

Is it possible to perform neuroevolution without a fitness function?

2 Answers2