source: branches/PerformanceComparison/ProblemInstanceIdentifier/InstanceExplorer.cs @ 15031

using System;
using System.Linq;
using HeuristicLab.Algorithms.MemPR.Permutation;
using HeuristicLab.Analysis.FitnessLandscape;
using HeuristicLab.Data;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Problems.QuadraticAssignment;
using HeuristicLab.Random;
using HeuristicLab.SequentialEngine;

namespace ProblemInstanceIdentifier {
  public abstract class InstanceExplorer {

    public abstract string Name { get; }
    public abstract int Effort { get; }
    protected InstanceExplorer() { }

    public abstract InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null);
  }

  public class PathRelinkingExplorer : InstanceExplorer {
    public int Paths { get; set; }
    public bool LocalOptima { get; set; }

    public override string Name { get { return "Path-Relinking Explorer"; } }
    public override int Effort { get { return Paths; } }

    public PathRelinkingExplorer() {
      
    }

    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
      var walk = new QAPDirectedWalk {
        Problem = problem,
        BestImprovement = true,
        Paths = Paths,
        Seed = seed,
        LocalOptima = LocalOptima
      };
      var features = walk.Calculate().ToDictionary(x => x.Name, x => x.Value);

      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
        features.Keys.ToArray(), features.Values.Select(x => ((DoubleValue)x).Value).ToArray());
    }
  }

  public class PathRelinkingOldFeaturedExplorer : InstanceExplorer {
    public int Paths { get; set; }
    public bool LocalOptima { get; set; }

    public override string Name { get { return "Path-Relinking Explorer"; } }
    public override int Effort { get { return Paths; } }

    public PathRelinkingOldFeaturedExplorer() {

    }

    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
      var random = new MersenneTwister();
      var samples = QAPDirectedWalk.CalculateRelinkingPoints(random, problem, Paths, LocalOptima);
      var trajectories = QAPDirectedWalk.Run(random, problem, samples);

      double avgAc1 = 0, avgCorLen = 0, avgIc = 0, avgDbi = 0, avgPic = 0, avgIs = 0, avgDiv = 0,
        avgReg = 0, avgEnt = 0, avgPkIc = 0, avgPkDbi = 0;
      int count = 0;
      foreach (var t in trajectories) {
        var trail = t.Select(x => x.Item2).ToArray();
        if (trail.Length < 4) continue;
        count++;
        double[] acf;
        var len = RuggednessCalculator.CalculateCorrelationLength(trail, out acf);
        avgAc1 += acf[0];
        avgCorLen += len;
        var analysis = new InformationAnalysis(trail, 20, 2);
        avgIc += analysis.InformationContent[0];
        avgDbi += analysis.DensityBasinInformation[0];
        avgPic += analysis.PartialInformationContent[0];
        avgIs += analysis.InformationStability;
        avgDiv += analysis.Diversity;
        avgReg += analysis.Regularity;
        avgEnt += analysis.TotalEntropy[0];
        avgPkIc += analysis.PeakInformationContent.Value;
        avgPkDbi += analysis.PeakDensityBasinInformation.Value;
      }
      avgAc1 /= count;
      avgCorLen /= count;
      avgIc /= count;
      avgDbi /= count;
      avgPic /= count;
      avgIs /= count;
      avgDiv /= count;
      avgReg /= count;
      avgEnt /= count;
      avgPkIc /= count;
      avgPkDbi /= count;

      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
        new[] { "Autocorrelation(1)", "CorrelationLength", "InformationContent", "DensityBasinInformation",
          "PartialInformationContent", "InformationStability", "Diversity", "Regularity", "TotalEntropy",
          "PeakInformationContent", "PeakDensityBasinInformation" },
        new[] { avgAc1, avgCorLen, avgIc, avgDbi,
          avgPic, avgIs, avgDiv, avgReg, avgEnt,
          avgPkIc, avgPkDbi });
    }
  }


  public class RandomWalkExplorer : InstanceExplorer {
    public int Iterations { get; set; }

    public override string Name { get { return "Random-Walk Explorer"; } }
    public override int Effort { get { return Iterations; } }

    public RandomWalkExplorer() {

    }

    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
      var walk = new RandomWalk() {
        SeedParameter = { Value = { Value = seed ?? 0 } },
        SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
        MaximumIterationsParameter = { Value = { Value = Iterations } },
        RepetitionsParameter = { Value = { Value = 1 } }
      };
      walk.Problem = problem;
      walk.Engine = new SequentialEngine();
      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
      var calculator = new RandomWalkCalculator(walk) { Problem = problem };
      var features = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);
      
      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
        features.Keys.ToArray(), features.Values.Select(x => ((DoubleValue)x).Value).ToArray());
    }
  }

  public class AdaptiveWalkExplorer : InstanceExplorer {
    public int Iterations { get; set; }
    public int SampleSize { get; set; }

    public override string Name { get { return "Adaptive-Walk Explorer"; } }
    public override int Effort { get { return Iterations * SampleSize; } }

    public AdaptiveWalkExplorer() {

    }

    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
      var walk = new AdaptiveWalk() {
        SeedParameter = { Value = { Value = seed ?? 0 } },
        SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
        MaximumIterationsParameter = { Value = { Value = Iterations } },
        RepetitionsParameter = { Value = { Value = 1 } },
        SampleSizeParameter = { Value = { Value = SampleSize } }
      };
      walk.Problem = problem;
      walk.Engine = new SequentialEngine();
      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
      var calculator = new AdaptiveWalkCalculator(walk) { Problem = problem };
      var features = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);

      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
        features.Keys.ToArray(), features.Values.Select(x => ((DoubleValue)x).Value).ToArray());
    }
  }

  public class UpDownWalkExplorer : InstanceExplorer {
    public int Iterations { get; set; }
    public int SampleSize { get; set; }

    public override string Name { get { return "Up/Down-Walk Explorer"; } }
    public override int Effort { get { return Iterations * SampleSize; } }

    public UpDownWalkExplorer() {

    }

    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
      var walk = new UpDownWalk() {
        SeedParameter = { Value = { Value = seed ?? 0 } },
        SetSeedRandomlyParameter = { Value = { Value = !seed.HasValue } },
        MaximumIterationsParameter = { Value = { Value = Iterations } },
        RepetitionsParameter = { Value = { Value = 1 } },
        SampleSizeParameter = { Value = { Value = SampleSize } }
      };
      walk.Problem = problem;
      walk.Engine = new SequentialEngine();
      walk.MutatorParameter.Value = walk.MutatorParameter.ValidValues.First(x => x is Swap2Manipulator);
      var calculator = new UpDownWalkCalculator(walk) {  Problem = problem };
      var features = calculator.Calculate().ToDictionary(x => x.Name, x => x.Value);

      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows,
        features.Keys.ToArray(), features.Values.Select(x => ((DoubleValue)x).Value).ToArray());
    }
  }

  public class MemPRExplorer : InstanceExplorer {
    public int Seconds { get; set; }

    public bool IncludeLocalSearch { get; set; }

    public override string Name { get { return "MemPR Explorer"; } }
    public override int Effort { get { return Seconds; } }

    public MemPRExplorer() {

    }

    public override InstanceDescriptor Explore(QuadraticAssignmentProblem problem, int? seed = null) {
      var memPr = new PermutationMemPR();
      memPr.Problem = problem;
      memPr.Prepare(true);
      memPr.MaximumExecutionTime = TimeSpan.FromSeconds(Seconds);
      memPr.SetSeedRandomly = !seed.HasValue;
      memPr.Seed = seed ?? 0;
      memPr.StartSync();
      if (memPr.Context.RelinkedPaths.IsEmpty
        || IncludeLocalSearch && memPr.Context.LocalSearchPaths.IsEmpty) {
        Console.WriteLine("{0} not all paths present!", problem.Name);
        return null;
      };

      var features = PermutationPathAnalysis.GetCharacteristics(memPr.Context.RelinkedPaths.Paths.ToList());
      var result = features.GetValues();
      var resultNames = features.GetNames();
      if (IncludeLocalSearch) {
        features = PermutationPathAnalysis.GetCharacteristics(memPr.Context.LocalSearchPaths.Paths.ToList());
        result = result.Concat(features.GetValues()).ToArray();
        resultNames = resultNames.Concat(features.GetNames()).ToArray();
      }
      return new InstanceDescriptor(problem.Name, InstanceDescriptor.GetClass(problem.Name), problem.Weights.Rows, resultNames, result);
    }
  }
}