Understanding the problem
Creating a good fitness function is about understanding the domain of the problem.
In this scenario, you will have simulations of the candidates going from the origin to the exit. The simulation will have a given time limit, that when reached the simulation is halted.
This means that the simulation for a given candidates ends either when it reaches the exit, or when the time is up.
And we have two measurements to work with: Distance (the of the candidate to the exit at the end of the simulation) and Time (the total elapsed time of the simulation).
We need to consider the values for these variables in both exit conditions:
- The the time is up:
Distance > 0, Time = TimeLimit
- The exit is Reached:
Distance = 0, Time ∈ [0, TimeLimit)
So, Distance ∈ [0, ∞), and Time ∈ [0, TimeLimit]. Note that I'm assuming that the candidate can go backwards beyond the origin.
We observe that when the exit is reached, Fitness will be a function of Time, and we want its worst value to be at Time = TimeLimit from where Distance should dominate the function. This implies that there will be a notable Fitness value for Distance = 0 and Time = TimeLimit.
I'll call this notable value K. So, K = Fitness(Distance: 0, Time: TimeLimit).
Note: you can use K = 1.
Modelling the fitness function with partial knowledge
I'll be using only information about the intervals of the variables and the fact that we want to minimize both Time and Distance to try to come up with a fitness function.
This will result into perfectly valid and functional fitness functions for genetic algorithms (with some tweaking here and there). However, if you want to see how to use the knowledge of the problem to create an ideal fitness function, skip to the next title.
Since we want to minimize the variables, the Fitness function would have to turn a lower value of these variables into a higher result.
We have two approaches to do that:
Invert the fitness afterwards:
In this approach, we will work an inverse fitness function starting by assigning the lower possible value to the best results.
So, we start by mapping Time ∈ [0, TimeLimit] into [0, K]. Meaning that Fitness'(Distance: 0, Time:0) = 0 and Fitness(Distance: 0, Time:TimeLimit) = K. That can be easily done with a linear function:
Fitness'(Time) = Time * K/TimeLimit
Then, we introduce Distance:
Fitness'(Distance, Time) = Distance + Time * K/TimeLimit
Finally, we invert the function. We can use the multiplicative inverse...
Fitness(Distance, Time) = 1 / (Distance + Time * K/TimeLimit)
... but, be wary that that may lead to a division by zero at the perfect score. Fortunately we know that Time = 0 should not happen. Anyway, we will fix any possible divide by zero by adding 1:
Fitness(Distance, Time) = 1 / (1 + Distance + Time * K/TimeLimit)
Alternatively, we can just flip the sign:
Fitness(Distance, Time) = - Distance - Time * K/TimeLimit
Yet, this will lead to negative numbers. If you are using the And the proportionate selection algorithm, know that it can't work with negative numbers... you may have to normalize the values by adding a value to all them to make them positive (you can use the absolute value of the worst result):
Fitness(Distance, Time) = a - Distance - Time * K/TimeLimit
Where a is constant for the compared population.
Note: this problem leads itself very well to this approach because we need to invert both variables.
Invert the variable beforehand:
In this case we will work as if we were creating fitness functions for each variable... inverting them as needed... and the combining them into a single fitness function.
For Time we start with:
Fitness'(Time) = Time
Again, we can invert this with the multiplicative inverse (leading to possible division by zero) or by flipping signs (leading to possible negative values).
We do the same thing with Distance:
Fitness'(Distance) = Distance
The next question: should add or multiply these functions? There is a clear advantage of adding: it makes it easier to add weights to the variables in the form of constant factors to the appropriate terms.
This leads us to four possible fitness functions:
Fitness(Distance, Time) = b/(1 + Time) + c/(1 + Distance)
Fitness(Distance, Time) = d/((1 + Time) * (1 + Distance))
Fitness(Distance, Time) = e -Time + -Distance
Fitness(Distance, Time) = f -((1 + Time) * (1 + Distance))
Where b, c and d, e and f are constants for the compared population.
Notes:
- Above, in the second alternative presented, we are adding one to the individual variables instead of adding to the denominator. This is because of a simple reason... if you add to the denominator, for the situations where
Distance = 0 you would be multiplying Time by 0, negating the impact of Time in the result of the function, which results in having the same value for all cases where Distance = 0.
- The final alternative is trickier! Not only you have to worry that when one of the variables is zero it negates the other, but also you have to worry that if you inverted both variables by changing their sing... when you multiply them, the result is now growing! Therefore, we have to tweak that.
Comparison of the fitness functions
We have come up with a total of six possible fitness functions:
1. Fitness(Distance, Time) = 1 / (1 + Distance + Time * K/TimeLimit)
2. Fitness(Distance, Time) = a - Distance - Time * K/TimeLimit
3. Fitness(Distance, Time) = b/(1 + Time) + c/(1 + Distance)
4. Fitness(Distance, Time) = d/((1 + Time) * (1 + Distance))
5. Fitness(Distance, Time) = e -Time + -Distance
6. Fitness(Distance, Time) = f -((1 + Time) * (1 + Distance))
Where a, b, c and d, e and f are constants for the compared population.
To pick one, let’s see how this functions behave...
The mapped values correspond to Time in the interval [0, 10] on the left of the graph, and Distance in the interval [0, 10] in the right of the graph.
In the graph all the functions has been normalized to give a score in the interval [0, 120]. This interval was chosen because the option 6 gives a value of -120 at Time = 10 & Distance = 10 which is the last value mapped.
We observe that all the methods present a discontinuous slope at the notable value, except for option 5, which is just a linear function. We also observe that the methods that use flipping sign result in linear segments (as expected), while the other results in hyperbolic segments. In addition, all the options are decreasing functions.
We can't really discard any of these methods, although we could prefer the option that result in curved functions because they don't require to normalize to eliminate negative numbers.
Modelling the fitness function with knowledge of the problem
While any of the fitness function presented above would work for a genetic algorithm, if you need a good representation of their comparative behavior... only the method 5 is good enough. However, even method 5 suffers from negative values.
Therefore, to find a good representation of their comparative and absolute behavior, we go back to the problem.
What we have been trying to do is extrapolate what would have happened in the simulation if we have let it run until the candidate reaches the exit.
For the Time < TimeLimit we know how much time the candidate took to reach the exit, for the other cases we extrapolate using Speed = Distance / Time:
ExpectedTime = |Exit - Origin| * |Candidate - Origin| / Time
Where Exit, Origin and Candidate are vectors. |Exit - Candidate| would be the distance from the candidate to the exit (Distance)
Now, we could score the candidate using Time when Distance = 0 and using ExpectedTime when it isn't.
Yes, you can do that, you can use conditionals in your code.
Yet, we can do that in one function without conditional or tricks... what we need to compute is the expected extra time that the candidate needed to reach the goal...
ExpectedExtraTime = Distance * |Candidate - Origin| / Time
In addition, add to it the elapsed time:
Fitness' = Time + Distance * |Candidate - Origin| / Time
We still need to invert this; we can confidently do it by using the multiplicative inverse:
Fitness = 1 / (Time + Distance * |Candidate - Origin| / Time)
=>
Fitness = 1 / (Time^2/Time + Distance * |Candidate - Origin| / Time)
=>
Fitness = Time / (Time^2 + Distance * |Candidate - Origin|)
This fitness function will only cause division by zero when both Time and Distance are 0. Shouldn't happen. Anyway, we will fix any possible divide by zero by adding 1.
Either here:
Fitness = Time / (1 + Time^2 + Distance * |Candidate - Origin|)
Alternatively, here:
Fitness = 1 / (1 + Time + Distance * |Candidate - Origin| / (1 + Time))
Fitness = 1 / ((1 + Time)^2/(1 + Time) + Distance * |Candidate - Origin| / (1 + Time))
Fitness = (1 + Time) / ((1 + Time)^2 + Distance * |Candidate - Origin|)
Note: in these graphs I assume |Candidate - Origin| = 1.
Personally, I prefer this final option. The reason is that the prior has a change in curvature... that makes the final option better to compare differences of candidates (you can argue the improvement of “A” over “B” is greater than the improvement of “C” over “D”, by comparing the inverses of the differences of their scores)... not that you need that to implement a genetic algorithm.
Both are continuous, decreasing, and will give you a positive scores for any situation.
Addendum: experimenting with this I found another option to prevent division by zero instead of adding 1. That option is to use exponentiation. In particular a fitness function of the form:
Fitness = (v^Time) / ((v^Time)^2 + Distance * |Candidate - Origin|)
Where v is a constant greater than 1, will result in a similar curve to those presented here. The slop will be evidently discontinous for v ≈ 1, from v ≈ 1.1 onwards there is no noticable jump in the slope. Higher values of v will make the function decrease faster. We wary of floating point errors.
