Changeset 15511 for branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment

Timestamp:

12/11/17 23:06:32 (7 years ago)

Author:

abeham

Message:

#1614: Improved performance by switching from Dictionary to Array

Location:

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3

Files:

• Evaluation/GQAPNMoveEvaluator.cs (modified) (3 diffs)
• Moves/NMove.cs (modified) (3 diffs)
• Moves/NMoveAbsoluteAttribute.cs (modified) (3 diffs)
• Moves/NMoveMaker.cs (modified) (1 diff)
• Moves/NMoveTabuChecker.cs (modified) (1 diff)
• Moves/StochasticNMoveSingleMoveGenerator.cs (modified) (3 diffs)
• Operators/LocalImprovers/ApproximateLocalSearch.cs (modified) (1 diff)

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Evaluation/GQAPNMoveEvaluator.cs

@@ -90 +90 @@
       var slack = evaluation.Slack.ToArray();
 
-      foreach (var kvp in move.NewAssignments) {
-        int equip = kvp.Key;
-        int newLoc = kvp.Value;
+      foreach (var equip in move.Indices) {
+        int newLoc = move.Reassignments[equip] - 1; // locations are given 1-based
         int oldLoc = assignment[equip];
         var equipDemand = problemInstance.Demands[equip];
@@ -98 +97 @@
         installationCosts += problemInstance.InstallationCosts[equip, newLoc];
         for (int j = 0; j < assignment.Length; j++) {
-          if (!move.NewAssignments.ContainsKey(j)) {
+          var reassignedLoc = move.Reassignments[j] - 1; // 0 indicates that this equipment is not reassigned
+          if (reassignedLoc < 0) {
             flowCosts += problemInstance.Weights[equip, j] * problemInstance.Distances[newLoc, assignment[j]];
             flowCosts -= problemInstance.Weights[equip, j] * problemInstance.Distances[oldLoc, assignment[j]];
@@ -104 +104 @@
             flowCosts -= problemInstance.Weights[j, equip] * problemInstance.Distances[assignment[j], oldLoc];
           } else {
-            flowCosts += problemInstance.Weights[equip, j] * problemInstance.Distances[newLoc, move.NewAssignments[j]];
+            flowCosts += problemInstance.Weights[equip, j] * problemInstance.Distances[newLoc, reassignedLoc];
             flowCosts -= problemInstance.Weights[equip, j] * problemInstance.Distances[oldLoc, assignment[j]];
           }

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/NMove.cs

@@ -20 +20 @@
 #endregion
 
-using System;
 using System.Collections.Generic;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
-using HeuristicLab.Encodings.IntegerVectorEncoding;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
@@ -32 +31 @@
   public class NMove : Item {
     [Storable]
-    public Dictionary<int, int> NewAssignments { get; private set; }
+    private int[] reassignments;
+    /// <summary>
+    /// Contains for each equipment the newly assigned location.
+    /// </summary>
+    /// <remarks>
+    /// Locations are 1-based. A 0 indicates that this equipment is not reassigned.
+    /// </remarks>
+    public IReadOnlyList<int> Reassignments {
+      get { return reassignments; }
+    }
     [Storable]
-    public IntegerVector OriginalVector { get; private set; }
+    private List<int> indices;
+    /// <summary>
+    /// Which indices (=equipments) are reassigned.
+    /// </summary>
+    /// <remarks>
+    /// Equipments are 0-based.
+    /// </remarks>
+    public IReadOnlyList<int> Indices {
+      get { return indices; }
+    }
 
-    public int N { get { return NewAssignments.Count; } }
+    public int N { get { return Indices.Count; } }
 
     [StorableConstructor]
@@ -42 +59 @@
     protected NMove(NMove original, Cloner cloner)
       : base(original, cloner) {
-      NewAssignments = new Dictionary<int, int>(original.NewAssignments);
-      if (original.OriginalVector != null)
-        OriginalVector = cloner.Clone(original.OriginalVector);
+      reassignments = original.reassignments.ToArray();
+      indices = original.indices.ToList();
     }
-    public NMove() : this(new int[0], new int[0], null) { }
-    public NMove(int[] equipments, int[] locations) : this(equipments, locations, null) { }
-    public NMove(int[] equipments, int[] locations, IntegerVector originalVector)
+    public NMove(int[] reassignments, List<int> indices)
       : base() {
-      if (equipments == null) throw new ArgumentNullException("equipments", "NMove: Equipments must not be null.");
-      if (locations == null) throw new ArgumentNullException("locations", "NMove: Locations must not be null.");
-      if (equipments.Length != locations.Length) throw new ArgumentException("NMove: Length of equipments and locations is not identical.");
-      NewAssignments = new Dictionary<int, int>();
-      for (int i = 0; i < equipments.Length; i++)
-        NewAssignments[equipments[i]] = locations[i];
-      OriginalVector = originalVector;
+      this.reassignments = reassignments;
+      this.indices = indices;
     }
 

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/NMoveAbsoluteAttribute.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Collections.Generic;
 using HeuristicLab.Common;
@@ -32 +33 @@
 
     [Storable]
-    public Dictionary<int, int> OldAssignments { get; private set; }
+    public List<Tuple<int, int>> OldAssignments { get; private set; }
     [Storable]
     public double MoveQuality { get; private set; }
@@ -41 +42 @@
     public NMoveAbsoluteTabuAttribute(NMove move, IntegerVector assignment, double moveQuality)
       : base() {
-      OldAssignments = new Dictionary<int, int>();
-      foreach (var kvp in move.NewAssignments)
-        OldAssignments.Add(kvp.Key, assignment[kvp.Key]);
+      OldAssignments = new List<Tuple<int, int>>(move.N);
+      foreach (var equip in move.Indices)
+        OldAssignments.Add(Tuple.Create(equip, assignment[equip]));
       MoveQuality = moveQuality;
     }

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/NMoveMaker.cs

@@ -71 +71 @@
 
     public static void Apply(IntegerVector vector, NMove move) {
-      foreach (var kvp in move.NewAssignments)
-        vector[kvp.Key] = kvp.Value;
+      for (var i = 0; i < move.N; i++) {
+        var equip = move.Indices[i];
+        vector[equip] = move.Reassignments[equip] - 1; // location is given 1-based in reassignments
+      }
     }
 

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/NMoveTabuChecker.cs

@@ -111 +111 @@
           isTabu = true;
           foreach (var kvp in attribute.OldAssignments) {
-            if (move.NewAssignments.ContainsKey(kvp.Key)) {
-              if (move.NewAssignments[kvp.Key] != kvp.Value) {
-                isTabu = false;
-                break;
-              }
+            var assignedLoc = move.Reassignments[kvp.Item1] - 1; // location is given 1-based
+            if (assignedLoc >= 0 && assignedLoc != kvp.Item2) {
+              isTabu = false;
+              break;
             }
           }

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Moves/StochasticNMoveSingleMoveGenerator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using System.Collections.Generic;
+using System.Linq;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -28 +30 @@
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.Random;
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
@@ -55 +58 @@
 
     public static NMove GenerateExactlyN(IRandom random, IntegerVector assignment, int n, DoubleArray capacities) {
-      int[] equipments = new int[n], locations = new int[n];
-      HashSet<int> chosenEquipments = new HashSet<int>();
-      for (int i = 0; i < n; i++) {
+      if (capacities.Length <= 1) throw new ArgumentException("There must be at least two locations.");
+      var dim = assignment.Length;
+      var reassignment = new int[dim];
+      var equipments = Enumerable.Range(0, dim).SampleRandomWithoutRepetition(random, n, dim).ToList();
+      for (var i = 0; i < n; i++) {
+        var equip = equipments[i];
         do {
-          equipments[i] = random.Next(assignment.Length);
-        } while (chosenEquipments.Contains(equipments[i]));
-        chosenEquipments.Add(equipments[i]);
-        do {
-          locations[i] = random.Next(capacities.Length);
-        } while (locations[i] == assignment[equipments[i]]);
+          reassignment[equip] = random.Next(capacities.Length) + 1;
+        } while (reassignment[equip] == assignment[equip] + 1);
       }
-      return new NMove(equipments, locations);
+      return new NMove(reassignment, equipments);
     }
 

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/Operators/LocalImprovers/ApproximateLocalSearch.cs

@@ -126 +126 @@
           
           var moveEval = GQAPNMoveEvaluator.Evaluate(move, assignment, evaluation, problemInstance);
-          evaluations += move.NewAssignments.Count * deltaEvaluationFactor;
+          evaluations += move.Indices.Count * deltaEvaluationFactor;
           double moveQuality = problemInstance.ToSingleObjective(moveEval);