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

Timestamp:

02/22/12 22:43:09 (13 years ago)

Author:

abeham

Message:

#1614

• added instances of Cordeau et al. as given by L. Moccia
• added operators for tabu search

Location:

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3

Files:

• Evaluators/GQAPNMoveEvaluator.cs (modified) (3 diffs)
• HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj (modified) (1 diff)
• Moves/GQAPNMoveGenerator.cs (modified) (1 diff)
• Moves/NMove.cs (modified) (4 diffs)
• Moves/NMoveAbsoluteAttribute.cs (added)
• Moves/NMoveMaker.cs (modified) (2 diffs)
• Moves/NMoveTabuChecker.cs (added)
• Moves/NMoveTabuMaker.cs (added)
• Moves/StochasticNMoveMultiMoveGenerator.cs (modified) (1 diff)
• Moves/StochasticNMoveSingleMoveGenerator.cs (modified) (1 diff)

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

@@ -20 +20 @@
 #endregion
 
-using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -32 +31 @@
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
-  [Item("GQAPNMoveEvaluator", "Evaluates an n-move.")]
+  [Item("N-Move Evaluator", "Evaluates an N-Move.")]
   [StorableClass]
   public class GQAPNMoveEvaluator : SingleSuccessorOperator, IGQAPNMoveEvaluator, IAssignmentAwareGQAPOperator,
@@ -159 +158 @@
       var slack = (DoubleArray)capacities.Clone();
       var oldSlack = (DoubleArray)slack.Clone();
-      Dictionary<int, int> moving = new Dictionary<int, int>();
-      for (int i = 0; i < moves; i++) moving.Add(move.Equipments[i], move.Locations[i]);
-
-      for (int i = 0; i < moves; i++) {
-        int equip = move.Equipments[i];
-        int newLoc = move.Locations[i];
+      bool first = true;
+      foreach (var kvp in move.NewAssignments) {
+        int equip = kvp.Key;
+        int newLoc = kvp.Value;
         moveInstallationQuality -= installationCosts[equip, assignment[equip]];
         moveInstallationQuality += installationCosts[equip, newLoc];
         for (int j = 0; j < assignment.Length; j++) {
-          if (!moving.ContainsKey(j)) {
+          if (!move.NewAssignments.ContainsKey(j)) {
             moveFlowDistanceQuality += weights[equip, j] * distances[newLoc, assignment[j]];
             moveFlowDistanceQuality -= weights[equip, j] * distances[assignment[equip], assignment[j]];
             moveFlowDistanceQuality += weights[j, equip] * distances[assignment[j], newLoc];
             moveFlowDistanceQuality -= weights[j, equip] * distances[assignment[j], assignment[equip]];
-            if (i == 0) { // only once for each untouched equipment deduct the demand from the capacity
+            if (first) { // only once for each untouched equipment deduct the demand from the capacity
               slack[assignment[j]] -= demands[j];
               oldSlack[assignment[j]] -= demands[j];
             }
           } else {
-            moveFlowDistanceQuality += weights[equip, j] * distances[newLoc, moving[j]];
+            moveFlowDistanceQuality += weights[equip, j] * distances[newLoc, move.NewAssignments[j]];
             moveFlowDistanceQuality -= weights[equip, j] * distances[assignment[equip], assignment[j]];
           }
         }
+        first = false;
         slack[newLoc] -= demands[equip];
         oldSlack[assignment[equip]] -= demands[equip];

branches/GeneralizedQAP/HeuristicLab.Problems.GeneralizedQuadraticAssignment/3.3/HeuristicLab.Problems.GeneralizedQuadraticAssignment-3.3.csproj

@@ -134 +134 @@
     <Compile Include="Moves\GQAPMoveGenerator.cs" />
     <Compile Include="Moves\GQAPNMoveGenerator.cs" />
+    <Compile Include="Moves\NMoveAbsoluteAttribute.cs" />
     <Compile Include="Moves\NMoveMaker.cs" />
+    <Compile Include="Moves\NMoveTabuChecker.cs" />
+    <Compile Include="Moves\NMoveTabuMaker.cs" />
     <Compile Include="Moves\StochasticNMoveMultiMoveGenerator.cs" />
     <Compile Include="Moves\StochasticNMoveSingleMoveGenerator.cs" />

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

@@ -30 +30 @@
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
-  [Item("GQAPNMoveGenerator", "Base class for move operators that generate n-move moves.")]
+  [Item("N-Move Generator", "Base class for move operators that generate N-Move moves.")]
   [StorableClass]
   public abstract class GQAPNMoveGenerator : GQAPMoveGenerator, IGQAPNMoveOperator {

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

@@ -21 +21 @@
 
 using System;
+using System.Collections.Generic;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -27 +28 @@
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
-  [Item("n-move", "An n-move describes moving n equipments to n locations.")]
+  [Item("N-Move", "An N-Move describes the relocation of n equipments to n different locations.")]
   [StorableClass]
   public class NMove : Item {
     [Storable]
-    public int[] Equipments { get; private set; }
-    [Storable]
-    public int[] Locations { get; private set; }
+    public Dictionary<int, int> NewAssignments { get; private set; }
     [Storable]
     public IntegerVector OriginalVector { get; private set; }
 
-    public int N { get { return Equipments.Length; } }
+    public int N { get { return NewAssignments.Count; } }
 
     [StorableConstructor]
@@ -43 +42 @@
     protected NMove(NMove original, Cloner cloner)
       : base(original, cloner) {
-      Equipments = (int[])original.Equipments.Clone();
-      Locations = (int[])original.Locations.Clone();
+      NewAssignments = new Dictionary<int, int>(original.NewAssignments);
       if (original.OriginalVector != null)
         OriginalVector = cloner.Clone(original.OriginalVector);
@@ -55 +53 @@
       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.");
-      Equipments = equipments;
-      Locations = locations;
+      NewAssignments = new Dictionary<int, int>();
+      for (int i = 0; i < equipments.Length; i++)
+        NewAssignments[equipments[i]] = locations[i];
       OriginalVector = originalVector;
     }

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

@@ -30 +30 @@
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
-  [Item("NMoveMaker", "Performs an n-move.")]
+  [Item("N-Move Maker", "Performs an N-Move.")]
   [StorableClass]
   public class NMoveMaker : SingleSuccessorOperator, IAssignmentAwareGQAPOperator, IQualityAwareGQAPOperator, IMoveQualityAwareGQAPOperator, IGQAPNMoveOperator, IMoveMaker {
@@ -97 +97 @@
 
     public static void Apply(IntegerVector vector, NMove move) {
-      for (int i = 0; i < move.N; i++) {
-        vector[move.Equipments[i]] = move.Locations[i];
-      }
+      foreach (var kvp in move.NewAssignments)
+        vector[kvp.Key] = kvp.Value;
     }
 

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

@@ -30 +30 @@
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
-  [Item("Stochastic n-move MultiMoveGenerator", "Randomly samples a number of n-moves.")]
+  [Item("Stochastic N-Move MultiMoveGenerator", "Randomly samples a number of N-Moves.")]
   [StorableClass]
   public class StochasticNMoveMultiMoveGenerator : GQAPNMoveGenerator, ICapacitiesAwareGQAPOperator, IStochasticOperator, IMultiMoveGenerator {

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

@@ -30 +30 @@
 
 namespace HeuristicLab.Problems.GeneralizedQuadraticAssignment {
-  [Item("Stochastic n-move SingleMoveGenerator", "Randomly samples a single n-move.")]
+  [Item("Stochastic N-Move SingleMoveGenerator", "Randomly samples a single N-Move.")]
   [StorableClass]
   public class StochasticNMoveSingleMoveGenerator : GQAPNMoveGenerator, ICapacitiesAwareGQAPOperator, IStochasticOperator, ISingleMoveGenerator {