Solution caching to avoid costly re-evaluations

[abeham]

I implemented the u574 TSP instance in form of a programmable problem and a simple caching dictionary and hit counter in the Evaluate method.

Using a GA with the following settings:

• Crossover: OrderCrossover2
• Elites: 1
• MaximumGenerations: 1000
• MutationProbability: 5 %
• Mutator: InversionManipulator
• PopulationSize: 500
• Selector: TournamentSelector (Group Size: 4)
• ReevaluateElites: False

Out of the 499,500 evaluated solutions 286,503 or about 57% were cache hits. This is of course heavily dependent on the algorithm instance as well as on the problem instance. With an OSGA instance cache hits were slightly below 4%, but in applications where evaluations are really costly even 4% are a substantial amount. Still, having dictionaries with millions of entries is not really efficient. But I think it would be doable to forget about solutions, have a fixed-size cache of reasonable size and still achieve a large parts of the hits as the most recent solutions are probably most likely to achieve a hit than very old ones.

Caches could be implemented on the level of the algorithm or on the level of the problem. However a few remarks:

• The cache would need to be reset between runs
• We will need EqualityComparers

This is probably mostly an issue in discrete combinatorial optimization (binary vectors, integer vectors, permutations, linear linkage arrays) and simulation-based optimization using these encodings.

[abeham]

The following would be a cache implementation with reprioritization on hits based on a high performance priority queue (​github) that is also used in Sim#:

public class DeterministicEvaluationCache<TSolution, TComparer> where TSolution : IItem where TComparer : EqualityComparer<TSolution>, new() {
  private int maxBufferSize;
  private FastPriorityQueue<DeterministicEvaluationCacheNode<TSolution>> buffer;
  private Dictionary<TSolution, DeterministicEvaluationCacheNode<TSolution>> cache;
  private int cacheHits;
  private long sequence;
  public int Hits { get { return cacheHits; } }
  
  public DeterministicEvaluationCache(int maxBufferSize) {
    this.maxBufferSize = maxBufferSize;
    buffer = new  FastPriorityQueue<DeterministicEvaluationCacheNode<TSolution>>(maxBufferSize);
    cache = new Dictionary<TSolution, DeterministicEvaluationCacheNode<TSolution>>(maxBufferSize, new TComparer());
    cacheHits = 0;
    sequence = 0;
  }
  
  public void Reset() {
    buffer.Clear();
    cache.Clear();
    cacheHits = 0;
    sequence = 0;
  }
  
  public bool TryGetValue(TSolution solution, out double quality) {
    DeterministicEvaluationCacheNode<TSolution> node;
    if (cache.TryGetValue(solution, out node)) {
      quality = node.Quality;
      buffer.UpdatePriority(node, ++sequence);
      cacheHits++;
      return true;
    }
    quality = double.NaN;
    return false;
  }
  
  public void Add(TSolution solution, double quality) {
    if (buffer.Count == maxBufferSize) {
      var old = buffer.Dequeue();
      cache.Remove(old.Solution);
    }
    var node = new DeterministicEvaluationCacheNode<TSolution>(solution, quality);
    buffer.Enqueue(node, ++sequence);
    cache[solution] = node;
  }
  
  public double GetOrAdd(TSolution solution, Func<double> qualityFunc) {
    double quality;
    if (!TryGetValue(solution, out quality)) {
      quality = qualityFunc();
      Add(solution, quality);
    }
    return quality;
  }
}

public class DeterministicEvaluationCacheNode<TSolution> : FastPriorityQueueNode {
  public TSolution Solution { get; private set; }
  public double Quality { get; private set; }
  
  public DeterministicEvaluationCacheNode(TSolution solution, double quality) {
    Solution = solution;
    Quality = quality;
  }
}

[gkronber]

My thoughts on this...

Yes, caching might be useful in some cases (very expensive fitness functions). But you also need to consider the overhead for calculation of hash codes and equality checks for every individual. Caching also introduces complexity (probably into specific evaluators).

I believe the root problem is that so many duplicate solutions candidates are visited by the algorithm. This means that the algorithm is inefficient overall. We should 'think big' to improve overall algorithm efficiency instead of investing resources into performance tuning.