Tuesday, December 30, 2014

By means of natural selection

I like Tournament selection in evolutionary algorithms. There are a lot of different selection schemes, each of which can perform better for the particular cases. However, the Tournament selection is easy to implement, flexible, and gives some chances to not very fit solutions to take part in the competition. And this selection can be easily adjusted to both minimization and maximization problems. Somewhat arguable feature is independence on the fitness values and their signs, but so far for me this is more an advantage rather than a weakness.
The necessity to cope with both minimization and maximization problems within one package/class library sometimes can be annoying, that is why, many implementations stick to only minimization problems. Leaving it to people, who use the package, to transform the fitness values, the way they find appropriate. There are many ways to make this kind of transform, but no ultimate one. However with selection methods that do not depend on the sign and the value (like Truncation or Tournament selections) this problem simply does not exist. That is why there are also a lot of packages that use these variants of selection.

So, how to handle both minimization and maximization problems? Here is the outline how I usually do this (other variants are surely possible):
1. Create a class to compare two fitness values ([FitnessComparator]) with a boolean field (say, [MinimizeFitness]) that indicates if the problem at hand is minimization or maximization.
2. Implement methods [IsWorse] and/or [IsBetter] that accept two fitness values and return boolean variable indicating if the first argument is respectively worse or better than the second one.
3. In the implementation of the Tournament selection just use these methods to define the winner in the tournament.
I prefer making the class static, so that I can just set the [MinimizeFitness] value during the initialization step, depending on what kind of problem is considered. After that I can be sure that fitness comparison works properly and I don't need to set it again elsewhere. I also believe that one more advantage of the usage of the comparator class is that it makes the code easier to read, as it operates with notions "better/worse" rather than plain comparison of vlaues, which can be confusing. Of course, there will be small reduction of the processing speed, but it is usually negligible, because other operations of the evolutionary algorithm are computationally more demanding.
The simplified implementation can look like this (C#):
public class FitnessComparator
{
///
/// Indicates whether minimization of maximization problem is considered.
///
public static bool MinimizeFitness { get; set; }
 
///
/// Compares two given fitnesses.
///
/// 1st fitness value.
/// 2nd fitness value.
/// [True] if 1st fitness value is worse than the 2nd one and [False] otherwise.
public static bool IsWorse(float f1, float f2) { return MinimizeFitness ? f1 > f2 : f1 < f2;}
 
///
/// Compares two given fitnesses.
///
/// 1st fitness.
/// 2nd fitness value.
/// [True] if 1st fitness value is better than the 2nd one and [False] otherwise.
public static bool IsBetter(float f1, float f2) { return MinimizeFitness ? f1 < f2 : f1 > f2; }
}

======================================
P.S. Originally posted here.

No comments:

Post a Comment