How to design a fitness function for a Genetic Algorithm that moves a car to a point through a city?

Question

I am trying to design a genetic algorithm with neural networks to move a car through a city generated in Unity to a randomised target destination. I have designed it and the code works but the agent only learns to avoid obstacles and not move to the specified target destination.

Currently my fitness function is: ((1 / (1 + totalDistanceTravelled)) + (1 / (1 + distanceToTarget)) + (1 / (1 + numberOfCollisions)) + sensors.Average())

How can I modify this to meet the desired outcome?

If more is required let me know.

Answer 1

Let's take a closer look at your fitness function in a perhaps more readable way (though I figure the parenthesis are there to help with that too):

(
  (
    1 / (1 + totalDistanceTravelled)
  ) + 
  (
    1 / (1 + distanceToTarget)
  ) + 
  (
     1 / (1 + numberOfCollisions)
  ) + 
  sensors.Average()
)

Looks like you are equally weighing distance traveled, distance to target, and number of collisions. Not sure what the sensors.Average() is (not familiar with unity), but I will figure that it's probably not the issue.

Let's assume the number of collisions is much less than the distance traveled or distance to the target. Say we have 10 collisions, we have traveled 100 units and we have 100 units left to travel.

The first two are 0.0099, the second one is 0.09. If we figure higher is better, then it would definitely give priority to avoiding stuff, at least until you are super close to the target or you have had a lot of collisions.

A better option would be to use the number of collisions as a coefficient. Something like:

(
  (
    (
      1 / (1 + totalDistanceTravelled)
    ) + 
    (
      1 / (1 + distanceToTarget)
    )
  ) * 
  (
     1 / (1 + numberOfCollisions)
  ) + 
  sensors.Average()
)

In this case, we equally consider the distances, then we multiply that by the factor of the collisions

Answer 2

Designing a good fitness function is not a trivial task, and, in fact, it is usually the central task for creating a successful genetic algorithm. You have not provided much detail, but I will try to provide some useful analysis.

One requirement of a good fitness function is that it must provide a smooth path to where you want to go from at least some of the starting points in gene-space. That is, if you start at a random point in gene-space, can you mostly, incrementally migrate to better and better places in gene-space using the fitness function as a guide.

Looking at your fitness function, my inclination is that the easiest solution to find is simply not moving much. Let's break the fitness function down into its components:

• 1/(1 + distance-travelled)
• 1/(1 + distance-to-target)
• 1/(1 + number-collisions)
• sensor-average - not sure what this is?

Let's suppose distance-to-target is 10. The first three components are 1 + 1/10 + 1. If you move one-step closer to the target without colliding with anything, the first three components are 1/2 + 1/9 + 1 which is less than before. That is obviously not the feedback you want to be giving for making a correct move.

For this task, I think you want distance-to-target to dominate the fitness, i.e. if you get closer to the target, regardless of the other factors, fitness should increase.

I don't have an ideal fitness function off the top of my head, but I will give it some thought.

Assuming equivalent distance-to-taret's, distance-travelled should be the next most important factor. Assuming two results get to 5 for distance-to-target, the one that travelled less distance should score higher.

number-collision needs to be relative to the distance-travelled, otherwise, you can minimize number-collisions by not traveling.

The idea is that you need to work through the details of the fitness function and make sure that it is always providing the correct feedback. This is not as easy as it sounds since most fitness functions have several variables.

If there is a pernicious solution that finds a local maximum in the fitness function without actually solving the problem, the algorithm will probably find it.