source: branches/2457_ExpertSystem/WalkExporter/RandomWalk.cs @ 18007

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2018 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using HeuristicLab.Analysis.FitnessLandscape;
using HeuristicLab.Core;
using HeuristicLab.Encodings.PermutationEncoding;
using HeuristicLab.Problems.Instances;
using HeuristicLab.Problems.Instances.QAPLIB;
using HeuristicLab.Random;
using ProtoBuf;

namespace WalkExporter {
  class RandomWalk {
    public static (Knowledgebase training, Knowledgebase test) GetKnowledgeBases(Experiment experiment, int length) {
      var training = new Knowledgebase() { Problems = new List<ProblemInstanceDescriptor>() };
      var test = new Knowledgebase() { Problems = new List<ProblemInstanceDescriptor>() };
      foreach (var trial in experiment.Trials) {
        foreach (var desc in AnalyzeEachWalk(trial, length)) {
          if (training.Problems.Count == test.Problems.Count)
            training.Problems.Add(desc);
          else test.Problems.Add(desc);
        }
      }
      return (training, test);
    }

    private static IEnumerable<ProblemInstanceDescriptor> AnalyzeEachWalk(Exploration trial, int length) {
      var instance = trial.Problem;
      var dim = trial.Dimension;
      foreach (var walk in trial.Walks) {
        var trail = walk.QualityTrail.Take(length).ToArray();
        var clen = RuggednessCalculator.CalculateCorrelationLength(trail, out double[] acf);
        var ia = new InformationAnalysis(trail);
        var desc = new ProblemInstanceDescriptor() {
          Name = instance,
          Class = Util.GetGeneratorClass(instance),
          Dimension = dim,
          DescriptionEffort = length * 4.0 / dim,
        };
        desc.Features = new List<KeyValue>();
        desc.Features.Add(new KeyValue { Key = "AC1", ContinuousValue = acf[1] });
        desc.Features.Add(new KeyValue { Key = "CorrelationLength", DiscreteValue = clen });
        foreach (var f in ia.GetFeatures()) {
          if (f.Item2 is double d) desc.Features.Add(new KeyValue { Key = f.Item1, ContinuousValue = d });
          else if (f.Item2 is int i) desc.Features.Add(new KeyValue { Key = f.Item1, DiscreteValue = i });
        }
        yield return desc;
      }
    }

    public static Experiment PerformExperiment() {
      var experiment = new Experiment() { Algorithm = "RandomWalk", Trials = new List<Exploration>() };
      foreach (var dimension in new[] { 20, 30, 40 }) {
        var provider = new OneSizeInstanceProvider(dimension);
        foreach (var desc in provider.GetDataDescriptors()) {
          var qapData = provider.LoadData(desc);
          var exploration = new Exploration() { Problem = qapData.Name, Dimension = qapData.Dimension, Walks = new List<Walk>() };
          for (var r = 0; r < 2; r++) {
            var walk = RandomWalk.Run(new MersenneTwister((uint)(r + 13)), qapData).Take((int)Math.Pow(2, 18)).ToList();
            exploration.Walks.Add(new Walk() { QualityTrail = walk });
          }
          experiment.Trials.Add(exploration);
        }
      }
      return experiment;
    }

    public static IEnumerable<double> Run(IRandom random, QAPData qap) {
      var sol = new Permutation(PermutationTypes.Absolute, qap.Dimension, random);
      var fit = Util.Evaluate(sol, qap);
      yield return fit;
      while (true) {
        var z1 = random.Next(qap.Dimension);
        var z2 = (z1 + random.Next(1, qap.Dimension)) % qap.Dimension;
        var move = Util.EvaluateSwap2Diff(sol, z1, z2, qap);
        fit += move;
        yield return fit;
        sol.Swap(z1, z2);
      }
    }

    ///////////////////////////////////////////////////////////////////////////////////
    ///                             CONFINED RANDOM WALK                            ///
    ///////////////////////////////////////////////////////////////////////////////////

    
    public static void ConfinedRandomWalkAnalysis(QAPData qapData) {
      Exploration exploration = null;
      if (File.Exists($"confinedrandwalk_{qapData.Name}.buf")) {
        using (var file = File.OpenRead($"confinedrandwalk_{qapData.Name}.buf")) {
          exploration = Serializer.Deserialize<Exploration>(file);
        }
      } else {
        exploration = PerformCondinedRandomwWalkExploration(qapData, 100);
        using (var file = File.Create($"confinedrandwalk_{qapData.Name}.buf")) {
          Serializer.Serialize(file, exploration);
        }
      }

      using (var writer = File.CreateText($"confinedrandwalk_{qapData.Name}.csv")) {
        var headers = new[] { "Run", "Algorithm Name", "Problem Name", "Dimension", "Ld(Iterations)", "Iterations", "Effort",
          "AC1", "CorrelationLength", "InformationContent", "DensityBasinInformation", "PartialInformationContent",
          "InformationStability", "Diversity", "Regularity", "TotalEntropy", "SymmetricInformationContent",
          "SymmetricDensityBasinInformation", "SymmetricTotalEntropy", "PeakInformationContent", "PeakDensityBasinInformation",
          "PeakTotalEntropy", "PeakSymmetricInformationContent", "PeakSymmetricDensityBasinInformation", "PeakSymmetricTotalEntropy" };
        var order = headers.Select((v, i) => new { Index = i, Header = v }).ToDictionary(x => x.Header, x => x.Index);
        writer.WriteLine(string.Format(string.Join(";", Enumerable.Range(0, headers.Length).Select(x => "{" + x + "}")), headers));
        foreach (var exp in Enumerable.Range(7, 18 - 6)) {
          var length = (int)Math.Pow(2, exp);
          var run = 0;
          foreach (var desc in AnalyzeEachWalk(exploration, length)) {
            var features = string.Join(";", desc.Features.OrderBy(x => order[x.Key]).Select(x => x.GetNumericValue().ToString()));
            writer.WriteLine(string.Format("R{0};Confined Random Walk;{5};{6};{1};{2};{3};{4}", run, exp, length, length * 4.0 / qapData.Dimension, features, qapData.Name, qapData.Dimension));
            run++;
          }
        }
      }
    }

    private static Exploration PerformCondinedRandomwWalkExploration(QAPData qapData, int repetitions) {
      var exploration = new Exploration() { Problem = qapData.Name, Dimension = qapData.Dimension, Walks = new List<Walk>() };
      for (var r = 0; r < repetitions; r++) {
        var walk = RunConfined(new MersenneTwister((uint)r), qapData, qapData.Dimension / 5).Take((int)Math.Pow(2, 18)).ToList();
        exploration.Walks.Add(new Walk() { QualityTrail = walk });
      }
      return exploration;
    }

    public static IEnumerable<double> RunConfined(IRandom random, QAPData qap, int distance) {
      var sol = new Permutation(PermutationTypes.Absolute, qap.Dimension, random);
      var anchor = (Permutation)sol.Clone();
      var fit = Util.Evaluate(sol, qap);
      var dist = 0;
      yield return fit;

      while (true) {
        var (j, k, deltaDist) = MoveConfined(random, sol, anchor, dist, distance);
        dist += deltaDist;
        var move = Util.EvaluateSwap2Diff(sol, j, k, qap);
        fit += move;
        yield return fit;
        sol.Swap(j, k);
      }
    }

    private static (int j, int k, int deltaDist) MoveConfined(IRandom random, Permutation current, Permutation anchor, int dist, int maxDist) {
      var evalSolPerMove = 4.0 / current.Length;
      var orderJ = Enumerable.Range(0, current.Length).Shuffle(random);
      var orderK = Enumerable.Range(0, current.Length).Shuffle(random);
      foreach (var j in orderJ) {
        if (dist == maxDist && current[j] == anchor[j]) continue;
        foreach (var k in orderK) {
          if (j == k) continue;
          var distChange = 0;
          if (current[j] != anchor[j] && current[k] == anchor[j]) distChange--;
          if (current[k] != anchor[k] && current[j] == anchor[k]) distChange--;
          if (current[j] == anchor[j]) distChange++;
          if (current[k] == anchor[k]) distChange++;
          if (dist + distChange > maxDist) continue;

          return (j, k, distChange);
        }
      }
      return (-1, -1, 0);
    }
  }
}