3
$\begingroup$

I've just started studying genetic algorithms and I'm not able to understand why a genetic algorithm can improve if, at each learning, the 'world' that the population encounters change. For example, in this demo (http://math.hws.edu/eck/js/genetic-algorithm/GA.html), it's pretty clear to me that the eating statistics will improve every year if bunches of grass grow exactly in the same place, but instead they always grow in different positions and I can't figure out how it can be useful to evaluate (through the fitness function) the obtained eating stats given that the next environment will be different.

$\endgroup$
1
$\begingroup$

There are a couple of ways of dealing with this. Very often, the approach is just to design your representation and operators in a way to account for the fact that the world changes. The idea is to give the algorithm something that can be used to learn general behaviors or solutions rather than specific ones.

Take an example of learning to steer a race car around a track. You want to represent the state of the world and have the GA learn to select an appropriate action. You might choose to represent the state of the world as a vector of $[x, y, v, a]$, where $(x, y)$ is your location on the track, $v$ is your current velocity vector, and $a$ is an acceleration to apply. The fitness function could return how "good" it was to apply that acceleration. If you do this, your algorithm can probably learn to navigate this track, but a different track will be hopeless, as the locations aren't corresponding to the same turn locations on the new track.

However, what if you encode the world as $[s, v, a]$, where instead of an $(x, y)$ pair representing your current position, you have $s$ as a vector of sensor readings? Is there a wall coming up in front of you or is the track starting to bank? Now, your algorithm can learn to be more general. It doesn't need to be the exact track it learned on, because what it's learning is not to brake at a specific point, but to brake when it detects a wall coming up.

I didn't do a lot of digging into the example you linked, but if you run it for a few years, you can see evidence of this. You see agents that appear to have learned to move in lines horizontally or vertically until they encounter a green square, and then they'll stick around and eat in the patches around that square. That behavior is general, because every environment it encounters has lots of blank space with clusters of green. It's not learning "go to square $(20, 30)$". It's learning to move in a pattern until it finds green and then move around that location.

You can do this in a lot of cases where the specific environment can change, but the objective is the same. There are problems where the actual fitness function changes over time, however. For those problems, there are specific techniques to deal with dynamic fitness functions. Generally, this involves doing something to maintain diversity so that your whole population isn't getting stuck on whatever the current "best" looks like. That's a bit more advanced topic though, and I think your question was really more about the former type of problems.

$\endgroup$
5
  • $\begingroup$ You say "The fitness function could return how "good" it was to apply that acceleration", but, from your example, it's not fully clear how you can know how good it is to apply a certain acceleration. Maybe you can clarify that you can retrieve this information from e.g. the output of that action, such as if the car hits the wall or something? Maybe that's what you mean? In that case, wouldn't this just be equivalent to your second example, where the fitness depends on the observations? So, I think that's not what you mean. $\endgroup$
    – nbro
    Dec 8 '20 at 15:06
  • $\begingroup$ Or maybe are you saying that you have a dataset of arrays $(x, y, v, a)$ for each possible position, $v$, and $a$ for a single track, and you are already given somehow the ground-truth fitness? Is that your assumption? As I said before, I don't think you would need this anyway. You would just need a way to quantify how a certain acceleration (action) is good with respect to an arbitrary $x$ and $y$ (i.e. your example of the fitness function that computes the fitness based on the observations), i.e. I don't fully understand your first example, ie why a fitness based on $x$ and $y$ is not good? $\endgroup$
    – nbro
    Dec 8 '20 at 15:06
  • $\begingroup$ I mean, I don't specifically understand this "but a different track will be hopeless, as the locations aren't corresponding to the same turn locations on the new track.". Why would that be the case, if the fitness is given as a function of $x$, $y$ and $a$? Apart from these things, your answer seems good to me. $\endgroup$
    – nbro
    Dec 8 '20 at 15:11
  • $\begingroup$ If you encode the (x,y) position as part of your state, then the algorithm is going to learn a specific track. If (8, 12) is the beginning of a long straight stretch, then hammering the accelerator is good. If there's a wall at (8,14) on a different track, you're going to crash, because all you've learned is to accelerate straight ahead from that location. That's why you need to use sensor data instead of absolute positions. $\endgroup$
    – deong
    Dec 9 '20 at 15:18
  • $\begingroup$ I understand that. What I don't understand is: why is it different to encode $(x, y)$ rather than the sensors' readings? Aren't $(x, y)$ also supposed to be sensors' readings? Maybe by sensors' readings you mean not only the location but also if the car has crashed and similar info? So, I guess that, to clarify this answer, you're essentially saying that the position alone is insufficient to act well on the environment and you need some kind of information about the obstacles around the car and the "state" of the car (i.e. has it crashed or not). Is this what you mean? $\endgroup$
    – nbro
    Dec 9 '20 at 17:01

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.