3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – nbro Oct 25 '20 at 10:04
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So, can we say that in these cases there is not a fitness function, or that we don't need to define it explicitly? $\endgroup$ – desertnaut Oct 21 '20 at 21:32
  • 2
    $\begingroup$ @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. $\endgroup$ – Neil Slater Oct 21 '20 at 21:34
  • $\begingroup$ 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? $\endgroup$ – LU15.W1R7H Oct 22 '20 at 7:31
  • 2
    $\begingroup$ @LU15.W1R7H I would suggest searching for "artificial life genetic algorithms" $\endgroup$ – Neil Slater Oct 22 '20 at 8:02
  • $\begingroup$ 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. $\endgroup$ – pasaba por aqui Oct 22 '20 at 11:33
1
$\begingroup$

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.

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