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

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.