Index: branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/GQAP/GQAPDirectedWalk.cs
===================================================================
--- branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/QAP/QAPDirectedWalk.cs	(revision 15702)
+++ branches/1614_GeneralizedQAP/HeuristicLab.Analysis.FitnessLandscape/3.3/ProblemCharacteristicAnalysis/GQAP/GQAPDirectedWalk.cs	(revision 15713)
@@ -20,22 +20,21 @@
 #endregion
 
+using System;
+using System.Collections.Generic;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Data;
-using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Encodings.IntegerVectorEncoding;
 using HeuristicLab.Optimization;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
-using HeuristicLab.Problems.QuadraticAssignment;
+using HeuristicLab.Problems.GeneralizedQuadraticAssignment;
 using HeuristicLab.Random;
-using System;
-using System.Collections.Generic;
-using System.Linq;
-using System.Threading;
 
 namespace HeuristicLab.Analysis.FitnessLandscape {
-  [Item("Directed Walk (QAP-specific)", "")]
+  [Item("Directed Walk (GQAP-specific)", "")]
   [StorableClass]
-  public class QAPDirectedWalk : CharacteristicCalculator {
+  public class GQAPDirectedWalk : CharacteristicCalculator {
     
     public IFixedValueParameter<IntValue> PathsParameter {
@@ -76,8 +75,8 @@
 
     [StorableConstructor]
-    private QAPDirectedWalk(bool deserializing) : base(deserializing) { }
-    private QAPDirectedWalk(QAPDirectedWalk original, Cloner cloner) : base(original, cloner) { }
-    public QAPDirectedWalk() {
-      characteristics.AddRange(new[] { "Swap2.Sharpness", "Swap2.Bumpiness", "Swap2.Flatness" }
+    private GQAPDirectedWalk(bool deserializing) : base(deserializing) { }
+    private GQAPDirectedWalk(GQAPDirectedWalk original, Cloner cloner) : base(original, cloner) { }
+    public GQAPDirectedWalk() {
+      characteristics.AddRange(new[] { "1Shift.Sharpness", "1Shift.Bumpiness", "1Shift.Flatness" }
         .Select(x => new StringValue(x)).ToList());
       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)));
@@ -88,53 +87,52 @@
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new QAPDirectedWalk(this, cloner);
+      return new GQAPDirectedWalk(this, cloner);
     }
 
     public override bool CanCalculate() {
-      return Problem is QuadraticAssignmentProblem;
+      return Problem is GQAP;
     }
 
     public override IEnumerable<IResult> Calculate() {
       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);
+      var gqap = (GQAP)Problem;
+      List<IntegerVector> assignments = CalculateRelinkingPoints(random, gqap, Paths, LocalOptima);
+
+      var trajectories = Run(random, (GQAP)Problem, assignments, BestImprovement).ToList();
+      var result = IntegerVectorPathAnalysis.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 perm = new Permutation(PermutationTypes.Absolute, qap.Weights.Rows, random);
+        if (chara == "1Shift.Sharpness") yield return new Result("1Shift.Sharpness", new DoubleValue(result.Sharpness));
+        if (chara == "1Shift.Bumpiness") yield return new Result("1Shift.Bumpiness", new DoubleValue(result.Bumpiness));
+        if (chara == "1Shift.Flatness") yield return new Result("1Shift.Flatness", new DoubleValue(result.Flatness));
+      }
+    }
+
+    public static List<IntegerVector> CalculateRelinkingPoints(IRandom random, GQAP gqap, int pathCount, bool localOptima) {
+      var assign = new IntegerVector(gqap.ProblemInstance.Demands.Length, random, 0, gqap.ProblemInstance.Capacities.Length);
       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);
+        var eval = gqap.ProblemInstance.Evaluate(assign);
+        var fit = gqap.ProblemInstance.ToSingleObjective(eval);
+        OneOptLocalSearch.Apply(random, assign, ref fit, ref eval, gqap.ProblemInstance, out var evals);
+      }
+      var points = new List<IntegerVector> { assign };
+      while (points.Count < pathCount + 1) {
+        assign = (IntegerVector)points.Last().Clone();
+        RelocateEquipmentManipluator.Apply(random, assign, gqap.ProblemInstance.Capacities.Length, 0);
         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 eval = gqap.ProblemInstance.Evaluate(assign);
+          var fit = gqap.ProblemInstance.ToSingleObjective(eval);
+          OneOptLocalSearch.Apply(random, assign, ref fit, ref eval, gqap.ProblemInstance, out var evals);
         }
-        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) {
-      var iter = permutations.GetEnumerator();
+        if (HammingSimilarityCalculator.CalculateSimilarity(points.Last(), assign) < 0.75)
+          points.Add(assign);
+      }
+
+      return points;
+    }
+
+    public static IEnumerable<List<Tuple<IntegerVector, double>>> Run(IRandom random, GQAP gqap, IEnumerable<IntegerVector> points, bool bestImprovement = true) {
+      var iter = points.GetEnumerator();
       if (!iter.MoveNext()) yield break;
-
-      var min = qap.LowerBound.Value;
-      var max = qap.AverageQuality.Value;
 
       var start = iter.Current;
@@ -142,92 +140,96 @@
         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 walk = (bestImprovement ? BestDirectedWalk(gqap, start, end) : FirstDirectedWalk(random, gqap, start, end)).ToList();
+        yield return walk.ToList();
         start = end;
       } // end paths
     }
 
-    private static IEnumerable<Tuple<Permutation, double>> BestDirectedWalk(QuadraticAssignmentProblem qap, Permutation start, Permutation end) {
-      var N = qap.Weights.Rows;
+    private static IEnumerable<Tuple<IntegerVector, double>> BestDirectedWalk(GQAP gqap, IntegerVector start, IntegerVector end) {
+      var N = gqap.ProblemInstance.Demands.Length;
       var sol = start;
-      var fitness = QAPEvaluator.Apply(sol, qap.Weights, qap.Distances);
+      var evaluation = gqap.ProblemInstance.Evaluate(start);
+      var fitness = gqap.ProblemInstance.ToSingleObjective(evaluation);
       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 reassignments = Enumerable.Range(0, N).Select(x => {
+        if (start[x] == end[x]) return null;
+        var r = new int[N];
+        r[x] = end[x] + 1;
+        return r;
+      }).ToArray();
+      var indices = Enumerable.Range(0, N).Select(x => start[x] == end[x] ? null : new List<int>(1) { x }).ToArray();
+
+      for (var step = 0; step < N; step++) {
         var bestFitness = double.MaxValue;
+        Evaluation bestEvaluation = null;
         var bestIndex = -1;
-        sol = (Permutation)sol.Clone();
+        sol = (IntegerVector)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);
+
+          var oneMove = new NMove(reassignments[index], indices[index]);
+          var eval = GQAPNMoveEvaluator.Evaluate(oneMove, sol, evaluation, gqap.ProblemInstance);
+          var fit = gqap.ProblemInstance.ToSingleObjective(eval);
           if (fit < bestFitness) { // QAP is minimization
             bestFitness = fit;
+            bestEvaluation = eval;
             bestIndex = index;
           }
         }
         if (bestIndex >= 0) {
-          var prev = sol[bestIndex];
-          Swap2Manipulator.Apply(sol, bestIndex, invSol[end[bestIndex]]);
-          fitness += bestFitness;
+          sol[bestIndex] = end[bestIndex];
+          fitness = bestFitness;
+          evaluation = bestEvaluation;
           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;
+    private static IEnumerable<Tuple<IntegerVector, double>> FirstDirectedWalk(IRandom random, GQAP gqap, IntegerVector start, IntegerVector end) {
+      var N = gqap.ProblemInstance.Demands.Length;
       var sol = start;
-      var fitness = QAPEvaluator.Apply(sol, qap.Weights, qap.Distances);
+      var evaluation = gqap.ProblemInstance.Evaluate(start);
+      var fitness = gqap.ProblemInstance.ToSingleObjective(evaluation);
       yield return Tuple.Create(sol, fitness);
 
-      var invSol = GetInverse(sol);
+      var reassignments = Enumerable.Range(0, N).Select(x => {
+        if (start[x] == end[x]) return null;
+        var r = new int[N];
+        r[x] = end[x] + 1;
+        return r;
+      }).ToArray();
+      var indices = Enumerable.Range(0, N).Select(x => start[x] == end[x] ? null : new List<int>(1) { x }).ToArray();
+
       // 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++) {
+
+      for (var step = 0; step < N; step++) {
         var bestFitness = double.MaxValue;
+        Evaluation bestEvaluation = null;
         var bestIndex = -1;
-        sol = (Permutation)sol.Clone();
+        sol = (IntegerVector)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
+
+          var oneMove = new NMove(reassignments[index], indices[index]);
+          var eval = GQAPNMoveEvaluator.Evaluate(oneMove, sol, evaluation, gqap.ProblemInstance);
+          var fit = gqap.ProblemInstance.ToSingleObjective(eval);
+
+          if (fit < bestFitness) { // GQAP is minimization
             bestFitness = fit;
+            bestEvaluation = evaluation;
             bestIndex = index;
-            if (bestFitness < 0) break;
+            if (fit < fitness) break;
           }
         }
         if (bestIndex >= 0) {
-          var prev = sol[bestIndex];
-          Swap2Manipulator.Apply(sol, bestIndex, invSol[end[bestIndex]]);
-          fitness += bestFitness;
+          sol[bestIndex] = end[bestIndex];
+          fitness = bestFitness;
+          evaluation = bestEvaluation;
           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;
-    }
-
-    // permutation must be strictly different in every position
-    private static void BiasedShuffle(Permutation p, IRandom random) {
-      for (var i = p.Length - 1; i > 0; i--) {
-        // Swap element "i" with a random earlier element (excluding itself)
-        var swapIndex = random.Next(i);
-        var h = p[swapIndex];
-        p[swapIndex] = p[i];
-        p[i] = h;
       }
     }
