Changeset 8338 for trunk/sources/HeuristicLab.Problems.QuadraticAssignment

Timestamp:

07/27/12 01:22:49 (12 years ago)

Author:

abeham

Message:

#1904: Added additional local improvement operators

Location:

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3

Files:

• HeuristicLab.Problems.QuadraticAssignment-3.3.csproj (modified) (1 diff)
• LocalImprovement/QAPExhaustiveInsertionLocalImprovement.cs (added)
• LocalImprovement/QAPExhaustiveInversionLocalImprovement.cs (added)
• LocalImprovement/QAPExhaustiveSwap2LocalImprovement.cs (modified) (5 diffs)
• LocalImprovement/QAPStochasticScrambleLocalImprovement.cs (added)

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/HeuristicLab.Problems.QuadraticAssignment-3.3.csproj

@@ -125 +125 @@
     <Compile Include="Interfaces\IQAPEvaluator.cs" />
     <Compile Include="Interfaces\IQAPMoveEvaluator.cs" />
+    <Compile Include="LocalImprovement\QAPExhaustiveInsertionLocalImprovement.cs" />
+    <Compile Include="LocalImprovement\QAPStochasticScrambleLocalImprovement.cs" />
     <Compile Include="LocalImprovement\QAPExhaustiveSwap2LocalImprovement.cs" />
+    <Compile Include="LocalImprovement\QAPExhaustiveInversionLocalImprovement.cs" />
     <Compile Include="QAPAssignment.cs" />
     <Compile Include="QAPPermutationProximityCalculator.cs" />

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveSwap2LocalImprovement.cs

@@ -21 +21 @@
 
 using System;
+using System.Threading;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -44 +45 @@
       get { return problem; }
       set { problem = (QuadraticAssignmentProblem)value; }
+    }
+
+    public ILookupParameter<IntValue> LocalIterationsParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["LocalIterations"]; }
     }
 
@@ -86 +91 @@
     public QAPExhaustiveSwap2LocalImprovement()
       : base() {
-      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum amount of iterations that should be performed (note that this operator will abort earlier when a local optimum is reached.", new IntValue(10000)));
+      Parameters.Add(new LookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed."));
+      Parameters.Add(new ValueLookupParameter<IntValue>("MaximumIterations", "The maximum amount of iterations that should be performed (note that this operator will abort earlier when a local optimum is reached).", new IntValue(10000)));
       Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The amount of evaluated solutions (here a move is counted only as 4/n evaluated solutions with n being the length of the permutation)."));
       Parameters.Add(new LookupParameter<ResultCollection>("Results", "The collection where to store results."));
@@ -100 +106 @@
     }
 
-    public static double Improve(Permutation assignment, double quality, DoubleMatrix weights, DoubleMatrix distances, bool maximization, int maxIterations, out double evaluatedSolutions) {
-      evaluatedSolutions = 0.0;
+    // BackwardsCompatibility3.3
+    #region Backwards compatible code, remove with 3.4
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      if (!Parameters.ContainsKey("LocalIterations"))
+        Parameters.Add(new LookupParameter<IntValue>("LocalIterations", "The number of iterations that have already been performed."));
+    }
+    #endregion
+
+    public static void Improve(Permutation assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation) {
       double evalSolPerMove = 4.0 / assignment.Length;
 
-      for (int i = 0; i < maxIterations; i++) {
+      for (int i = localIterations.Value; i < maxIterations; i++) {
         Swap2Move bestMove = null;
         double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
+        double evaluations = 0.0;
         foreach (Swap2Move move in ExhaustiveSwap2MoveGenerator.Generate(assignment)) {
           double moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, weights, distances);
-          evaluatedSolutions += evalSolPerMove;
+          evaluations += evalSolPerMove;
           if (maximization && moveQuality > bestQuality
             || !maximization && moveQuality < bestQuality) {
@@ -116 +131 @@
           }
         }
+        evaluatedSolutions.Value += (int)Math.Ceiling(evaluations);
         if (bestMove == null) break;
         Swap2Manipulator.Apply(assignment, bestMove.Index1, bestMove.Index2);
-        quality += bestQuality;
+        quality.Value += bestQuality;
+        localIterations.Value++;
+        cancellation.ThrowIfCancellationRequested();
       }
-      return quality;
     }
 
     public override IOperation Apply() {
-      int maxIterations = MaximumIterationsParameter.ActualValue.Value;
-      Permutation assignment = AssignmentParameter.ActualValue;
-      bool maximization = MaximizationParameter.ActualValue.Value;
-      DoubleMatrix weights = WeightsParameter.ActualValue;
-      DoubleMatrix distances = DistancesParameter.ActualValue;
-      double quality = QualityParameter.ActualValue.Value;
+      var maxIterations = MaximumIterationsParameter.ActualValue.Value;
+      var assignment = AssignmentParameter.ActualValue;
+      var maximization = MaximizationParameter.ActualValue.Value;
+      var weights = WeightsParameter.ActualValue;
+      var distances = DistancesParameter.ActualValue;
+      var quality = QualityParameter.ActualValue;
+      var localIterations = LocalIterationsParameter.ActualValue;
+      var evaluations = EvaluatedSolutionsParameter.ActualValue;
+      if (localIterations == null) {
+        localIterations = new IntValue(0);
+        LocalIterationsParameter.ActualValue = localIterations;
+      }
 
-      double evaluations;
-      QualityParameter.ActualValue.Value = Improve(assignment, quality, weights, distances, maximization, maxIterations, out evaluations);
-      EvaluatedSolutionsParameter.ActualValue.Value += (int)Math.Ceiling(evaluations);
+      Improve(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);
       return base.Apply();
     }