Changeset 14690 for branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs

Timestamp:

02/20/17 20:41:33 (7 years ago)

Author:

abeham

Message:

#2457: working on identification of problem instances

File:

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

branches/PerformanceComparison/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs

@@ -32 +32 @@
 using System.Collections.Generic;
 using System.Linq;
+using System.Threading;
 
 namespace HeuristicLab.Analysis.FitnessLandscape {
@@ -50 +51 @@
     }
 
+    public IFixedValueParameter<BoolValue> LocalOptimaParameter {
+      get { return (IFixedValueParameter<BoolValue>)Parameters["LocalOptima"]; }
+    }
+
     public int Paths {
       get { return PathsParameter.Value.Value; }
@@ -63 +68 @@
       get { return SeedParameter.Value != null ? SeedParameter.Value.Value : (int?)null; }
       set { SeedParameter.Value = value.HasValue ? new IntValue(value.Value) : null; }
+    }
+
+    public bool LocalOptima {
+      get { return LocalOptimaParameter.Value.Value; }
+      set { LocalOptimaParameter.Value.Value = value; }
     }
 
@@ -74 +84 @@
       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)));
     }
 
@@ -90 +101 @@
 
       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);
-        permutations.Add(perm);
+        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);
+        }
+        if (HammingSimilarityCalculator.CalculateSimilarity(permutations.Last(), perm) < 0.75)
+          permutations.Add(perm);
       }
 
@@ -151 +171 @@
 
       for (var p = 0; p < f2.Count; p++) {
+        if (f2[p].Count <= 2) continue;
         var bump = 0;
         var flat = 0;
@@ -266 +287 @@
     }
 
+    // Center-of-Mass
     private static double ComBelowZero(IEnumerable<Tuple<Permutation, double>> path) {
       var area = 0.0;