Changeset 16096 for branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs

Timestamp:

08/29/18 18:16:05 (6 years ago)

Author:

abeham

Message:

#2457:

• Changed calculation of correlation length (using limit introduced Hordijk 1996)
• Changed RuggednessCalculator (no more a HL item)
• Added additional, information-analysis-based features for directed walks
• Added generic DirectedWalk algorithm (as described in thesis)
• Made OneSizeInstanceProvider parametrizable
• Adapted program for analyzing problem instance reidentification

File:

• branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs (modified) (7 diffs)

branches/2457_ExpertSystem/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs

@@ -20 +20 @@
 #endregion
 
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Threading;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -29 +33 @@
 using HeuristicLab.Problems.QuadraticAssignment;
 using HeuristicLab.Random;
-using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Threading;
 
 namespace HeuristicLab.Analysis.FitnessLandscape {
@@ -38 +38 @@
   [StorableClass]
   public class QAPDirectedWalk : CharacteristicCalculator {
+
+    public enum WalkType { RandomRandom, RandomGlobal, RandomLocal, LocalLocal, LocalGlobal, LocalInverse }
+
+    private const string NBHOOD_STR = "Swap2";
     
     public IFixedValueParameter<IntValue> PathsParameter {
@@ -51 +55 @@
     }
 
-    public IFixedValueParameter<BoolValue> LocalOptimaParameter {
-      get { return (IFixedValueParameter<BoolValue>)Parameters["LocalOptima"]; }
+    public IFixedValueParameter<EnumValue<WalkType>> TypeParameter {
+      get { return (IFixedValueParameter<EnumValue<WalkType>>)Parameters["Type"]; }
     }
 
@@ -70 +74 @@
     }
 
-    public bool LocalOptima {
-      get { return LocalOptimaParameter.Value.Value; }
-      set { LocalOptimaParameter.Value.Value = value; }
+    public WalkType Type {
+      get { return TypeParameter.Value.Value; }
+      set { TypeParameter.Value.Value = value;}
     }
 
@@ -79 +83 @@
     private QAPDirectedWalk(QAPDirectedWalk original, Cloner cloner) : base(original, cloner) { }
     public QAPDirectedWalk() {
-      characteristics.AddRange(new[] { "Swap2.Sharpness", "Swap2.Bumpiness", "Swap2.Flatness" }
-        .Select(x => new StringValue(x)).ToList());
+      characteristics.AddRange(CurveAnalysisResult.AllFeatures.Select(x => new StringValue(x.ToString())));
+      characteristics.AddRange(new[] { "AutoCorrelation1", "CorrelationLength", "InformationContent",
+        "DensityBasinInformation", "PartialInformationContent", "InformationStability",
+        "Diversity", "Regularity", "TotalEntropy", "PeakInformationContent",
+        "PeakDensityBasinInformation" }.Select(x => new StringValue(x)));
+
       Parameters.Add(new FixedValueParameter<IntValue>("Paths", "The number of paths to explore (a path is a set of solutions that connect two randomly chosen solutions).", new IntValue(50)));
       Parameters.Add(new FixedValueParameter<BoolValue>("BestImprovement", "Whether the best of all alternatives should be chosen for each step in the path or just the first improving (least degrading) move should be made.", new BoolValue(true)));
       Parameters.Add(new OptionalValueParameter<IntValue>("Seed", "The seed for the random number generator."));
-      Parameters.Add(new FixedValueParameter<BoolValue>("LocalOptima", "Whether to perform walks between local optima.", new BoolValue(false)));
+      Parameters.Add(new FixedValueParameter<EnumValue<WalkType>>("Type", "Type of directed walk to perfom.", new EnumValue<WalkType>(WalkType.RandomRandom)));
     }
 
@@ -95 +103 @@
     }
 
+    private double _evaluatedSolutions;
+
     public override IEnumerable<IResult> Calculate() {
+      _evaluatedSolutions = 0;
+      var permutations = CalculateRelinkingPoints();
+
+      var trajectories = Run(permutations).ToList();
+      var result = PermutationPathAnalysis.GetCharacteristics(trajectories);
+
+      #region Calculate Information Analysis Features
+      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;
+      var isResults = new Dictionary<string, double>() {
+        { "AutoCorrelation1", avgAc1 },
+        { "CorrelationLength", avgCorLen },
+        { "InformationContent", avgIc },
+        { "DensityBasinInformation", avgDbi },
+        { "PartialInformationContent", avgPic },
+        { "InformationStability", avgIS },
+        { "Diversity", avgDiv },
+        { "Regularity", avgReg },
+        { "TotalEntropy", avgEnt },
+        { "PeakInformationContent", avgPkIc },
+        { "PeakDensityBasinInformation", avgPkDbi }
+      };
+      #endregion
+
+      foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) {
+        if (Enum.TryParse<CurveAnalysisFeature>(chara, out var caf))
+          yield return new Result(Type.ToString() + "-DW." + NBHOOD_STR + "." + chara, new DoubleValue(result.GetValue(caf)));
+        else yield return new Result(Type.ToString() + "-DW." + NBHOOD_STR + "." + chara, new DoubleValue(isResults[chara]));
+      }
+      yield return new Result("EvaluatedSolutions", new IntValue((int)Math.Round(_evaluatedSolutions)));
+    }
+
+    private IEnumerable<Permutation> CalculateRelinkingPoints() {
       IRandom random = Seed.HasValue ? new MersenneTwister((uint)Seed.Value) : new MersenneTwister();
       var qap = (QuadraticAssignmentProblem)Problem;
-      List<Permutation> permutations = CalculateRelinkingPoints(random, qap, Paths, LocalOptima);
-
-      var trajectories = Run(random, (QuadraticAssignmentProblem)Problem, permutations, BestImprovement).ToList();
-      var result = PermutationPathAnalysis.GetCharacteristics(trajectories);
-
-      foreach (var chara in characteristics.CheckedItems.Select(x => x.Value.Value)) {
-        if (chara == "Swap2.Sharpness") yield return new Result("Swap2.Sharpness", new DoubleValue(result.Sharpness));
-        if (chara == "Swap2.Bumpiness") yield return new Result("Swap2.Bumpiness", new DoubleValue(result.Bumpiness));
-        if (chara == "Swap2.Flatness") yield return new Result("Swap2.Flatness", new DoubleValue(result.Flatness));
-      }
-    }
-
-    public static List<Permutation> CalculateRelinkingPoints(IRandom random, QuadraticAssignmentProblem qap, int pathCount, bool localOptima) {
+      var pathCount = Paths;
+
       var perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);
-      if (localOptima) {
-        var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
-        QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
-      }
-      var permutations = new List<Permutation> { perm };
-      while (permutations.Count < pathCount + 1) {
-        perm = (Permutation)permutations.Last().Clone();
-        BiasedShuffle(perm, random);
-        if (localOptima) {
+      var startLocal = Type == WalkType.LocalGlobal || Type == WalkType.LocalLocal;
+      var targetLocal = Type == WalkType.LocalLocal || Type == WalkType.RandomLocal;
+      var targetGlobal = Type == WalkType.LocalGlobal || Type == WalkType.RandomGlobal;
+      var inverseWalk = Type == WalkType.LocalInverse;
+
+      if (Type == WalkType.LocalInverse) pathCount--; // inverse walks equal one walk per solution
+      for (var i = 0; i <= pathCount; i++) {
+        var start = i % 2 == 0;
+        var target = i % 2 == 1;
+        if (inverseWalk || start && startLocal) {
+          perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);
           var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
-          QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), new IntValue(0), qap.Maximization.Value, int.MaxValue, CancellationToken.None);
+          _evaluatedSolutions++;
+          var evalSol = new IntValue(0);
+          QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), evalSol, qap.Maximization.Value, int.MaxValue, CancellationToken.None);
+          _evaluatedSolutions += evalSol.Value;
+        } else if (target && (targetLocal || targetGlobal)) {
+          if (targetGlobal) {
+            perm = qap.BestKnownSolutions.SampleRandom(random);
+          } else {
+            perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);
+            var fit = new DoubleValue(QAPEvaluator.Apply(perm, qap.Weights, qap.Distances));
+            _evaluatedSolutions++;
+            var evalSol = new IntValue(0);
+            QAPExhaustiveSwap2LocalImprovement.ImproveFast(perm, qap.Weights, qap.Distances, fit, new IntValue(0), evalSol, qap.Maximization.Value, int.MaxValue, CancellationToken.None);
+            _evaluatedSolutions += evalSol.Value;
+          }
+        } else { // random
+          BiasedShuffle(perm, random);
         }
-        if (HammingSimilarityCalculator.CalculateSimilarity(permutations.Last(), perm) < 0.75)
-          permutations.Add(perm);
-      }
-
-      return permutations;
-    }
-
-    public static IEnumerable<List<Tuple<Permutation, double>>> Run(IRandom random, QuadraticAssignmentProblem qap, IEnumerable<Permutation> permutations, bool bestImprovement = true) {
+        yield return (Permutation)perm.Clone();
+      }
+    }
+
+    private IEnumerable<List<Tuple<Permutation, double>>> Run(IEnumerable<Permutation> permutations) {
+      if (Type == WalkType.LocalInverse) return RunInverse(permutations);
+      return RunRegular(permutations);
+    }
+
+    private IEnumerable<List<Tuple<Permutation, double>>> RunInverse(IEnumerable<Permutation> permutations) {
+      var qap = (QuadraticAssignmentProblem)Problem;
+      var min = qap.LowerBound.Value;
+      var max = qap.AverageQuality.Value;
+      var bestImprovement = BestImprovement;
+
+      foreach (var start in permutations) {
+        var startFitness = QAPEvaluator.Apply(start, qap.Weights, qap.Distances);
+        _evaluatedSolutions++;
+
+        // inverse walks are applied to all solutions
+        Func<Tuple<Permutation, double>, IEnumerable<Tuple<Permutation, double>>> inverseNeighborFunc = (p) => RestrictedInverseNeighborhood(qap, p.Item1, p.Item2, start);
+        var walk = DirectedWalk<Permutation>.WalkRestricted(qap.Maximization.Value, inverseNeighborFunc, start, startFitness, !bestImprovement);
+        yield return walk.Select(x => Tuple.Create(x.Item1, (x.Item2 - min) / (max - min))).ToList();
+      } // end paths
+    }
+
+    private IEnumerable<List<Tuple<Permutation, double>>> RunRegular(IEnumerable<Permutation> permutations) {
       var iter = permutations.GetEnumerator();
       if (!iter.MoveNext()) yield break;
-
+      var bestImprovement = BestImprovement;
+
+      var qap = (QuadraticAssignmentProblem)Problem;
       var min = qap.LowerBound.Value;
       var max = qap.AverageQuality.Value;
 
       var start = iter.Current;
+      
       while (iter.MoveNext()) {
+        var startFitness = QAPEvaluator.Apply(start, qap.Weights, qap.Distances);
+        _evaluatedSolutions++;
         var end = iter.Current;
 
-        var walk = (bestImprovement ? BestDirectedWalk(qap, start, end) : FirstDirectedWalk(random, qap, start, end)).ToList();
-        yield return walk.Select(x => Tuple.Create(x.Item1, (x.Item2 - min) / (max - min))).ToList();
+        var invSol = new int[start.Length];
+        Func<Tuple<Permutation, double>, IEnumerable<Tuple<Permutation, double>>> regularNeighborFunc = (p) => RestrictedNeighborhood(qap, p.Item1, p.Item2, end, invSol);
+        var walk = DirectedWalk<Permutation>.WalkRestricted(qap.Maximization.Value, regularNeighborFunc, start, startFitness, !bestImprovement);
+
+        var trail = new List<Tuple<Permutation, double>>();
+        foreach (var step in walk) {
+          for (var i = 0; i < invSol.Length; i++)
+            invSol[step.Item1[i]] = i;
+          trail.Add(Tuple.Create(step.Item1, (step.Item2 - min) / (max - min)));
+        }
+        yield return trail;
+
         start = end;
       } // end paths
     }
 
-    private static IEnumerable<Tuple<Permutation, double>> BestDirectedWalk(QuadraticAssignmentProblem qap, Permutation start, Permutation end) {
-      var N = qap.Weights.Rows;
-      var sol = start;
-      var fitness = QAPEvaluator.Apply(sol, qap.Weights, qap.Distances);
-      yield return Tuple.Create(sol, fitness);
-
-      var invSol = GetInverse(sol);
-      // we require at most N-1 steps to move from one permutation to another
-      for (var step = 0; step < N - 1; step++) {
-        var bestFitness = double.MaxValue;
-        var bestIndex = -1;
-        sol = (Permutation)sol.Clone();
-        for (var index = 0; index < N; index++) {
-          if (sol[index] == end[index]) continue;
-          var fit = QAPSwap2MoveEvaluator.Apply(sol, new Swap2Move(index, invSol[end[index]]), qap.Weights, qap.Distances);
-          if (fit < bestFitness) { // QAP is minimization
-            bestFitness = fit;
-            bestIndex = index;
-          }
+    private IEnumerable<Tuple<Permutation, double>> RestrictedInverseNeighborhood(QuadraticAssignmentProblem qap, Permutation current, double currentFit, Permutation start) {
+      var evalSolPerMove = 4.0 / current.Length;
+      var N = current.Length;
+      for (var index = 0; index < N; index++) {
+        if (current[index] != start[index]) continue;
+        for (var k = 0; k < N; k++) {
+          if (k == index) continue;
+          var fit = QAPSwap2MoveEvaluator.Apply(current, new Swap2Move(index, k), qap.Weights, qap.Distances);
+          _evaluatedSolutions += evalSolPerMove;
+          current.Swap(index, k);
+          yield return Tuple.Create(current, currentFit + fit);
+          current.Swap(index, k); // reverse
         }
-        if (bestIndex >= 0) {
-          var prev = sol[bestIndex];
-          Swap2Manipulator.Apply(sol, bestIndex, invSol[end[bestIndex]]);
-          fitness += bestFitness;
-          yield return Tuple.Create(sol, fitness);
-          invSol[prev] = invSol[end[bestIndex]];
-          invSol[sol[bestIndex]] = bestIndex;
-        } else break;
-      }
-    }
-
-    private static IEnumerable<Tuple<Permutation, double>> FirstDirectedWalk(IRandom random, QuadraticAssignmentProblem qap, Permutation start, Permutation end) {
-      var N = qap.Weights.Rows;
-      var sol = start;
-      var fitness = QAPEvaluator.Apply(sol, qap.Weights, qap.Distances);
-      yield return Tuple.Create(sol, fitness);
-
-      var invSol = GetInverse(sol);
-      // randomize the order in which improvements are tried
-      var order = Enumerable.Range(0, N).Shuffle(random).ToArray();
-      // we require at most N-1 steps to move from one permutation to another
-      for (var step = 0; step < N - 1; step++) {
-        var bestFitness = double.MaxValue;
-        var bestIndex = -1;
-        sol = (Permutation)sol.Clone();
-        for (var i = 0; i < N; i++) {
-          var index = order[i];
-          if (sol[index] == end[index]) continue;
-          var fit = QAPSwap2MoveEvaluator.Apply(sol, new Swap2Move(index, invSol[end[index]]), qap.Weights, qap.Distances);
-          if (fit < bestFitness) { // QAP is minimization
-            bestFitness = fit;
-            bestIndex = index;
-            if (bestFitness < 0) break;
-          }
-        }
-        if (bestIndex >= 0) {
-          var prev = sol[bestIndex];
-          Swap2Manipulator.Apply(sol, bestIndex, invSol[end[bestIndex]]);
-          fitness += bestFitness;
-          yield return Tuple.Create(sol, fitness);
-          invSol[prev] = invSol[end[bestIndex]];
-          invSol[sol[bestIndex]] = bestIndex;
-        } else break;
-      }
-    }
-
-    private static int[] GetInverse(Permutation p) {
-      var inv = new int[p.Length];
-      for (var i = 0; i < p.Length; i++) {
-        inv[p[i]] = i;
-      }
-      return inv;
+      }
+    }
+
+    private IEnumerable<Tuple<Permutation, double>> RestrictedNeighborhood(QuadraticAssignmentProblem qap, Permutation current, double currentFit, Permutation target, int[] inverse) {
+      var evalSolPerMove = 4.0 / current.Length;
+      for (var index = 0; index < current.Length; index++) {
+        if (current[index] == target[index]) continue;
+        var k = inverse[target[index]];
+        var fit = QAPSwap2MoveEvaluator.Apply(current, new Swap2Move(index, k), qap.Weights, qap.Distances);
+        _evaluatedSolutions += evalSolPerMove;
+        current.Swap(index, k);
+        yield return Tuple.Create(current, currentFit + fit);
+        current.Swap(index, k); // reverse
+      }
     }