Implementing LAHC in HeuristicLab

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

using HeuristicLab.Analysis;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Problems.Instances;
using HeuristicLab.Problems.Instances.TSPLIB;
using HeuristicLab.Problems.TravelingSalesman;
using HeuristicLab.Optimization;

public class LAHCScript : HeuristicLab.Scripting.CSharpScriptBase {
  public override void Main() {
    var random = new HeuristicLab.Random.MersenneTwister();
    var tsplib = new TSPLIBTSPInstanceProvider();
    var instance = tsplib.GetDataDescriptors()
      .Single(x => x.Name == "berlin52");
    var tsp = tsplib.LoadData(instance);
    var dm = new DistanceMatrix(tsp.GetDistanceMatrix());
    
    Permutation best = null, current = null, candidate = null;
    var candidateFitness = double.MaxValue;
    var bestFitness = double.MaxValue;
    var currentFitness = double.MaxValue;

    IsBetter isBetter = (first, second, orEqual) => (first < second)
      || (orEqual && first == second);
    
    InitializeFitness init = () => {
      candidate = new Permutation(
        PermutationTypes.RelativeUndirected, tsp.Dimension, random);
      current = candidate;
      best = candidate;
      candidateFitness = TourLength(candidate, dm);
      currentFitness = candidateFitness;
      bestFitness = candidateFitness;
      return candidateFitness;
    };
    
    NextFitness next = () => {
      candidate = new Permutation(
        PermutationTypes.RelativeUndirected, current);
      var move = StochasticInversionSingleMoveGenerator
                   .Apply(candidate, random);
      candidateFitness = currentFitness + TSPInversionMovePathEvaluator
                   .EvaluateByDistanceMatrix(candidate, move, dm);
      // important to perform the move after the delta calculation
      InversionManipulator.Apply(candidate, move.Index1, move.Index2);
      return candidateFitness;
    };
    
    Accept accept = () => {
      current = candidate;
      currentFitness = candidateFitness;
      if (isBetter(candidateFitness, bestFitness, orEqual: false)) {
        best = candidate;
        bestFitness = candidateFitness;
      }
    };
    
    var run = LAHC(init, next, accept, isBetter, 5000);
    run.Parameters.Add("Problem Name",
      new StringValue(instance.Name));
    run.Parameters.Add("Problem Type",
      new StringValue(typeof(TravelingSalesmanProblem).Name));
    run.Parameters.Add("Maximization", new BoolValue(false));
    if (tsp.BestKnownQuality.HasValue)
      run.Parameters.Add("BestKnownQuality",
        new DoubleValue(tsp.BestKnownQuality.Value));
    var solution = new PathTSPTour(new DoubleMatrix(tsp.Coordinates),
                                 best, new DoubleValue(bestFitness));
    run.Results.Add("Best Solution", solution);
    HeuristicLab.MainForm.MainFormManager.MainForm.ShowContent(run);
  }
  
  private static double TourLength(Permutation perm, DistanceMatrix dm) {
    var length = dm[perm.Last(), perm.First()];
    for (var i = 1; i < perm.Length; i++) {
      length += dm[perm[i - 1], perm[i]];
    }
    return length;
  }
  
  public delegate double InitializeFitness();
  public delegate double NextFitness();
  public delegate void Accept();
  public delegate bool IsBetter(double first, double second, bool orEqual);
  
  
  public static Run LAHC(InitializeFitness init, NextFitness next,
      Accept accept, IsBetter isBetter, int listSize,
      int minTries = 100000) {
    var sw = Stopwatch.StartNew();
    
    var cgraph_fe = new IndexedDataTable<double>("Convergence Graph FE");
    var cgraph_wc = new IndexedDataTable<double>("Convergence Graph Time");
    var crow_fe = new IndexedDataRow<double>("First-hit");
    var crow_wc = new IndexedDataRow<double>("First-hit");
    
    cgraph_fe.Rows.Add(crow_fe);
    cgraph_fe.VisualProperties.XAxisLogScale = true;
    cgraph_wc.Rows.Add(crow_wc);
    cgraph_wc.VisualProperties.XAxisLogScale = true;
    
    var bestFit = init();
    
    var globalIter = 0;
    var memory = new double[listSize];
    for (var v = 0; v < listSize; v++) {
      memory[v] = bestFit;
    }
    
    Tuple<int, double> last = null;
    foreach (var s in
        LAHC(next, accept, isBetter, bestFit, memory, minTries)) {
      if (isBetter(s.Item2, bestFit, orEqual: false)) {
        bestFit = s.Item2;
        crow_fe.Values.Add(
          Tuple.Create((double)globalIter + s.Item1, s.Item2));
        crow_wc.Values.Add(
          Tuple.Create(sw.ElapsedTicks / (double)Stopwatch.Frequency,
           s.Item2));
      }
      last = s;
    }
    globalIter += last.Item1;
      
    sw.Stop();
    crow_fe.Values.Add(Tuple.Create((double)globalIter, bestFit));
    crow_wc.Values.Add(
      Tuple.Create(sw.ElapsedTicks / (double)Stopwatch.Frequency,
        bestFit));
    
    var run = new Run() { Name = "LAHC-" + listSize };
    run.Parameters.Add("Algorithm Name", new StringValue("LAHC"));
    run.Parameters.Add("ListSize", new IntValue(listSize));
    run.Parameters.Add("MinTries", new IntValue(minTries));
    run.Parameters.Add("Algorithm Type", new StringValue("LAHC"));
    run.Results.Add("ExecutionTime", new TimeSpanValue(
      TimeSpan.FromSeconds(sw.ElapsedTicks
        / (double)Stopwatch.Frequency)));
    run.Results.Add("EvaluatedSolutions", new IntValue(globalIter));
    run.Results.Add("BestQuality", new DoubleValue(bestFit));
    run.Results.Add("QualityPerEvaluations", cgraph_fe);
    run.Results.Add("QualityPerClock", cgraph_wc);
    
    return run;
  }
  
  private static IEnumerable<Tuple<int, double>> LAHC(
      NextFitness nextFitness, Accept doAccept,
      IsBetter isBetter, double fit, double[] memory,
      int minTries) {
    var bestFit = fit;
    var tries = 0;
    var lastSuccess = 0;
    var l = memory.Length;
    
    while (tries < minTries || (tries - lastSuccess) < tries * 0.02) {
      var nextFit = nextFitness();
      var v = tries % l;
      tries++;
      var prevFit = memory[v];
      
      var accept = isBetter(nextFit, fit, orEqual: true)
                || isBetter(nextFit, prevFit, orEqual: true);
      
      if (accept && isBetter(nextFit, fit, orEqual: false))
        lastSuccess = tries;
      
      if (accept) {
        if (isBetter(nextFit, bestFit, orEqual: false)) {
          bestFit = nextFit;
          yield return Tuple.Create(tries, bestFit);
        }
        
        fit = nextFit;
        doAccept();
      }
      if (isBetter(fit, prevFit, orEqual: false)) 
        memory[v] = fit;
    }
    yield return Tuple.Create(tries, bestFit);
  }
}