source: branches/PerformanceComparison/ProblemInstanceIdentifier/Program.cs @ 15529

using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Threading.Tasks;
using HeuristicLab.PluginInfrastructure;
using HeuristicLab.Problems.Instances;
using HeuristicLab.Problems.Instances.QAPLIB;
using HeuristicLab.Problems.QuadraticAssignment;
using HeuristicLab.Random;

namespace ProblemInstanceIdentifier {
  class Program {
    static void Main(string[] args) {
      //var instances = Get20DifferentClasses();
      var instances = GetSomeRandomInstances(50, 13);

      /*var classes = instances.Select(InstanceDescriptor.FromProblemOnly).GroupBy(x => x.Cls);
      foreach (var cls in classes.OrderBy(x => x.Key)) {
        Console.WriteLine("{0};{1}", cls.Key, cls.Count());
      }*/

      var prExplorer = new PathRelinkingExplorer() {
        LocalOptima = false,
        Paths = 200
      };
      var prOldExplorer = new PathRelinkingOldFeaturedExplorer() {
        LocalOptima = false,
        Paths = 200
      };

      var prLocalExplorer = new PathRelinkingExplorer() {
        LocalOptima = true,
        Paths = 200
      };
      var prOldLocalExplorer = new PathRelinkingOldFeaturedExplorer() {
        LocalOptima = true,
        Paths = 200
      };

      var memPrExplorer = new MemPRExplorer() {
        IncludeLocalSearch = false,
        Seconds = 10
      };

      //var training = GenerateData(instances, prOldExplorer, parallel: true);
      //var standardizer = InstancesStandardizer.CreateAndApply(training);
      //var test = GenerateData(instances, prOldExplorer, parallel: true);
      //standardizer.Apply(test);
      //PrintMatchResult(Compare(training, test));

      //Console.WriteLine("=== Path Relinking Walk ===");
      //ExploreMatching(instances,
      //new[] { 1, 5, 10, 20, 50, 100, 200 }.Select(x => new PathRelinkingExplorer() { LocalOptima = false, Paths = x }).ToArray(),
      //new[] { 1, 5, 10, 20, 50, 100, 200 }.Select(x => new PathRelinkingExplorer() { LocalOptima = false, Paths = x }).ToArray(),
      //parallel: true);
      //Console.WriteLine("=== Random Walk ===");
      //ExploreMatching(instances,
      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray(),
      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new RandomWalkExplorer() { Iterations = x }).ToArray(),
      //parallel: true);
      //Console.WriteLine("=== Adaptive Walk ===");
      //ExploreMatching(instances,
      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new AdaptiveWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
      //new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new AdaptiveWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
      //parallel: true);
      Console.WriteLine("=== Up/Down Walk ===");
      ExploreMatching(instances,
      new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new UpDownWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
      new[] { 300, 1500, 3000, 6000, 15000, 30000, 60000 }.Select(x => new UpDownWalkExplorer() { Iterations = x / 10, SampleSize = 10 }).ToArray(),
      parallel: true);
    }

    private static List<QuadraticAssignmentProblem> GetSomeRandomInstances(int totalInstances, int seed) {
      var sync = new object();
      var provider = new OneSizeInstanceProvider();
      var instances = new List<QuadraticAssignmentProblem>();
      var random = new FastRandom(seed);
      Parallel.ForEach(provider.GetDataDescriptors().Shuffle(random), desc => {
        var qapData = provider.LoadData(desc);
        if (instances.Count >= totalInstances) return;
        var qap = new QuadraticAssignmentProblem();
        qap.Load(qapData);
        lock (sync) {
          if (instances.Count >= totalInstances) return;
          instances.Add(qap);
        }
      });
      return instances;
    }

    private static HashSet<string> selectedInstances = new HashSet<string>() {
      "bur26a", "chr25a", "dre24", "els19", "esc32a", "had20", "kra32", "lipa30a", "lipa30b",
      "nug30", "rou20", "scr20", "sko42", "ste36a", "tai25a", "tai25b", "tho30", "wil50",
      "RAND-S-6x6-36-25-AFFY-00_rand_rand_bl", "RAND-S-6x6-36-25-AFFY-00_rand_rand_ci"
    };
    private static List<QuadraticAssignmentProblem> Get20DifferentClasses() {
      var sync = new object();

      var qapProviders = ApplicationManager.Manager.GetInstances<ProblemInstanceProvider<QAPData>>().ToList();
      var instances = new List<QuadraticAssignmentProblem>();
      foreach (var provider in qapProviders) {
        if (provider is TaillardQAPInstanceProvider) continue;
        Parallel.ForEach(provider.GetDataDescriptors(), desc => {
          if (!selectedInstances.Contains(desc.Name)) return;
          //if (desc.Name == "esc16f") return;
          var qapData = provider.LoadData(desc);
          //if (qapData.Dimension < 15 || qapData.Dimension > 150) return;
          var qap = new QuadraticAssignmentProblem();
          qap.Load(qapData);
          lock (sync) {
            instances.Add(qap);
          }
        });
      }
      return instances;
    }

    private static List<InstanceDescriptor> GenerateData(List<QuadraticAssignmentProblem> instances, InstanceExplorer explorer, bool parallel = false) {
      var sync = new object();
      var data = new List<InstanceDescriptor>();
      Action<QuadraticAssignmentProblem> body = (qap) => {
        var instance = explorer.Explore(qap);
        if (instance == null) return;
        lock (sync) {
          data.Add(instance);
        }
      };
      if (parallel) {
        Parallel.ForEach(instances.Select(x => (QuadraticAssignmentProblem)x.Clone()), body);
      } else {
        foreach (var qap in instances) body(qap);
      }
      return data;
    }

    private static MatchResult Compare(List<InstanceDescriptor> training, List<InstanceDescriptor> test) {
      int exactCount = 0, clsCount = 0, totalCount = 0;
      int exactRank = 0, clsRank = 0;
      foreach (var e in test) {
        var ordered = training.OrderBy(x => x.CalculateSimilarity(e)).ToList();
        var bestMatch = ordered.First();
        if (bestMatch.Cls == e.Cls) clsCount++;
        if (bestMatch.Name == e.Name) exactCount++;
        var r = ordered.FindIndex((id) => id.Name == e.Name);
        if (r < 0) continue;
        totalCount++;
        exactRank += r + 1;
        clsRank += ordered.FindIndex((id) => id.Cls == e.Cls) + 1;
      }

      return new MatchResult() {
        ExactCount = exactCount,
        ClsCount = clsCount,
        TotalCount = totalCount,
        ExactAverageRank = exactRank / (double)totalCount,
        ClsAverageRank = clsRank / (double)totalCount
      };
    }

    private static void PrintMatchResult(MatchResult result) {
      Console.WriteLine("{0}\t{1}\t{2}\t{3:F2}\t{4:F2}",
        result.ExactCount, result.ClsCount, result.TotalCount,
        result.ExactAverageRank, result.ClsAverageRank);
    }

    private static void PrintData(List<InstanceDescriptor> instances) {
      using (var iter = instances.GetEnumerator()) {
        if (!iter.MoveNext()) return;
        Console.WriteLine(string.Join(";", new[] {"Name", "Cls", "Dimension"}
          .Concat(iter.Current != null ? iter.Current.FeatureNames : new [] { "(null)" })));
        do {
          PrintInstanceLine(iter.Current);
        } while (iter.MoveNext());
      }
    }

    private static void PrintInstanceLine(InstanceDescriptor instance) {
      Console.WriteLine(string.Join(";",
        new[] {instance.Name, instance.Cls, instance.Dimension.ToString(CultureInfo.CurrentCulture)}
          .Concat(instance.FeatureValues.Select(x => x.ToString(CultureInfo.CurrentCulture)))));
    }

    private static void ExploreMatching(List<QuadraticAssignmentProblem> instances, InstanceExplorer[] trainingExplorers, InstanceExplorer[] testExporers, bool parallel = false) {
      var sync = new object();

      var knowledgeBase = new Dictionary<InstanceExplorer, Tuple<InstancesStandardizer, List<InstanceDescriptor>>>();
      Action<InstanceExplorer> trainingBody = (kbExplorer) => {
        var trainingData = GenerateData(instances, kbExplorer, parallel);
        var standardizer = InstancesStandardizer.Create(trainingData);
        standardizer.Apply(trainingData);
        lock (sync) {
          knowledgeBase.Add(kbExplorer, Tuple.Create(standardizer, trainingData));
        }
      };
      if (parallel) {
        Parallel.ForEach(trainingExplorers, trainingBody);
      } else {
        foreach (var kbExplorer in trainingExplorers) trainingBody(kbExplorer);
      }

      var experimentBase = new Dictionary<InstanceExplorer, List<InstanceDescriptor>>();
      Action<InstanceExplorer> testBody = (expExplorer) => {
        var testData = GenerateData(instances, expExplorer, parallel);
        lock (sync) {
          experimentBase.Add(expExplorer, testData);
        }
      };
      if (parallel) {
        Parallel.ForEach(testExporers, testBody);
      } else {
        foreach (var expExplorer in testExporers) testBody(expExplorer);
      }

      var data = from kb in knowledgeBase
        from exp in experimentBase
        select new { Training = kb, Test = exp };

      if (parallel) {
        Parallel.ForEach(data, (point) => {
          var normalizedTest = point.Test.Value.Select(x => new InstanceDescriptor(x)).ToList();
          point.Training.Value.Item1.Apply(normalizedTest);
          var result = Compare(point.Training.Value.Item2, normalizedTest);
          lock (sync) {
            Console.WriteLine("{0}\t{1}\t{2}\t{3:F2}\t{4}\t{5:F2}\t{6}",
              point.Training.Key.Effort, point.Test.Key.Effort, result.ExactCount,
              result.ExactAverageRank, result.ClsCount, result.ClsAverageRank, result.TotalCount);
          }
        });
      } else {
        foreach (var point in data) {
          var normalizedTest = point.Test.Value.Select(x => new InstanceDescriptor(x)).ToList();
          point.Training.Value.Item1.Apply(normalizedTest);
          var result = Compare(point.Training.Value.Item2, normalizedTest);
          Console.WriteLine("{0}\t{1}\t{2}\t{3:F2}\t{4}\t{5:F2}\t{6}",
            point.Training.Key.Effort, point.Test.Key.Effort, result.ExactCount,
            result.ExactAverageRank, result.ClsCount, result.ClsAverageRank, result.TotalCount);
        }
      }
    }

    private class MatchResult {
      public int ExactCount { get; set; }
      public int ClsCount { get; set; }
      public int TotalCount { get; set; }
      public double ExactAverageRank { get; set; }
      public double ClsAverageRank { get; set; }
    }
  }
}