Changeset 9363 for branches/OaaS/HeuristicLab.Problems.QuadraticAssignment

Timestamp:

04/16/13 13:13:41 (12 years ago)

Author:

spimming

Message:

#1888:

• Merged revisions from trunk

Location:

branches/OaaS

Files:

• . (modified) (2 props)
• HeuristicLab.Problems.QuadraticAssignment (modified) (1 prop)
• HeuristicLab.Problems.QuadraticAssignment/3.3/BoundsCalculators/GilmoreLawlerBoundCalculator.cs (modified) (3 diffs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/HeuristicLab.Problems.QuadraticAssignment-3.3.csproj (modified) (4 diffs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveInsertionLocalImprovement.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveInsertionLocalImprovement.cs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveInversionLocalImprovement.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveInversionLocalImprovement.cs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveSwap2LocalImprovement.cs (modified) (7 diffs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPStochasticScrambleLocalImprovement.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPStochasticScrambleLocalImprovement.cs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/Plugin.cs.frame (modified) (2 diffs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/Properties/AssemblyInfo.cs.frame (modified) (1 diff)
• HeuristicLab.Problems.QuadraticAssignment/3.3/QAPSimilarityCalculator.cs (copied) (copied from trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/QAPSimilarityCalculator.cs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs (modified) (6 diffs)

branches/OaaS

@@ -21 +21 @@
 protoc.exe
 _ReSharper.HeuristicLab 3.3 Tests
+Google.ProtocolBuffers-2.4.1.473.dll
 packages

@@ -21 +21 @@
 protoc.exe
 _ReSharper.HeuristicLab 3.3 Tests
+Google.ProtocolBuffers-2.4.1.473.dll
 packages

branches/OaaS/HeuristicLab.Problems.QuadraticAssignment/3.3/BoundsCalculators/GilmoreLawlerBoundCalculator.cs

@@ -22 +22 @@
 using System;
 using HeuristicLab.Data;
+using HeuristicLab.Encodings.PermutationEncoding;
 using HeuristicLab.Problems.LinearAssignment;
 
@@ -27 +28 @@
   public static class GilmoreLawlerBoundCalculator {
     public static double CalculateLowerBound(DoubleMatrix weights, DoubleMatrix distances) {
+      Permutation tmp;
+      return CalculateLowerBound(weights, distances, out tmp);
+    }
+
+    public static double CalculateLowerBound(DoubleMatrix weights, DoubleMatrix distances, out Permutation solution) {
       int N = weights.Rows;
       DoubleMatrix sortedWeights = SortEachRowExceptDiagonal(weights), sortedDistances = SortEachRowExceptDiagonal(distances);
@@ -40 +46 @@
 
       double result;
-      LinearAssignmentProblemSolver.Solve(costs, out result);
+      solution = new Permutation(PermutationTypes.Absolute, LinearAssignmentProblemSolver.Solve(costs, out result));
       return result;
     }

branches/OaaS/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" />
     <Compile Include="QuadraticAssignmentProblem.cs" />
+    <Compile Include="QAPSimilarityCalculator.cs" />
     <None Include="Plugin.cs.frame" />
     <Compile Include="Plugin.cs" />
@@ -178 +182 @@
       <Private>False</Private>
     </ProjectReference>
+    <ProjectReference Include="..\..\HeuristicLab.Optimization.Operators\3.3\HeuristicLab.Optimization.Operators-3.3.csproj">
+      <Project>{25087811-f74c-4128-bc86-8324271da13e}</Project>
+      <Name>HeuristicLab.Optimization.Operators-3.3</Name>
+      <Private>False</Private>
+    </ProjectReference>
     <ProjectReference Include="..\..\HeuristicLab.Optimization\3.3\HeuristicLab.Optimization-3.3.csproj">
       <Project>{14AB8D24-25BC-400C-A846-4627AA945192}</Project>
@@ -210 +219 @@
   <Import Project="$(MSBuildToolsPath)\Microsoft.CSharp.targets" />
   <PropertyGroup>
-    <PreBuildEvent>set Path=%25Path%25;$(ProjectDir);$(SolutionDir)
+    <PreBuildEvent Condition=" '$(OS)' == 'Windows_NT' ">set Path=%25Path%25;$(ProjectDir);$(SolutionDir)
 set ProjectDir=$(ProjectDir)
 set SolutionDir=$(SolutionDir)
@@ -216 +225 @@
 
 call PreBuildEvent.cmd</PreBuildEvent>
+    <PreBuildEvent Condition=" '$(OS)' != 'Windows_NT' ">
+export ProjectDir=$(ProjectDir)
+export SolutionDir=$(SolutionDir)
+
+$SolutionDir/PreBuildEvent.sh
+</PreBuildEvent>
   </PropertyGroup>
   <PropertyGroup>

branches/OaaS/HeuristicLab.Problems.QuadraticAssignment/3.3/LocalImprovement/QAPExhaustiveSwap2LocalImprovement.cs

@@ -21 +21 @@
 
 using System;
+using System.Threading;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -46 +47 @@
     }
 
+    public ILookupParameter<IntValue> LocalIterationsParameter {
+      get { return (ILookupParameter<IntValue>)Parameters["LocalIterations"]; }
+    }
+
     public IValueLookupParameter<IntValue> MaximumIterationsParameter {
       get { return (IValueLookupParameter<IntValue>)Parameters["MaximumIterations"]; }
@@ -76 +81 @@
     public ILookupParameter<DoubleMatrix> DistancesParameter {
       get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
+    }
+
+    public IValueLookupParameter<BoolValue> UseFastEvaluationParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["UseFastEvaluation"]; }
     }
 
@@ -86 +95 @@
     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."));
@@ -94 +104 @@
       Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix."));
       Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix."));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("UseFastEvaluation", "Enabling this option will use a NxN double matrix to save the last move qualities. The moves of the first iteration will then be evaluated in O(N) while all further moves will be evaluated in O(1).", new BoolValue(true)));
     }
 
@@ -100 +111 @@
     }
 
-    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."));
+      if (!Parameters.ContainsKey("UseFastEvaluation"))
+        Parameters.Add(new ValueLookupParameter<BoolValue>("UseFastEvaluation", "Enabling this option will use a NxN double matrix to save the last move qualities. The moves of the first iteration will then be evaluated in O(N) while all further moves will be evaluated in O(1).", new BoolValue(false)));
+    }
+    #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) {
+            bestQuality = moveQuality;
+            bestMove = move;
+          }
+        }
+        evaluatedSolutions.Value += (int)Math.Ceiling(evaluations);
+        if (bestMove == null) break;
+        Swap2Manipulator.Apply(assignment, bestMove.Index1, bestMove.Index2);
+        quality.Value += bestQuality;
+        localIterations.Value++;
+        cancellation.ThrowIfCancellationRequested();
+      }
+    }
+
+    public static void ImproveFast(Permutation assignment, DoubleMatrix weights, DoubleMatrix distances, DoubleValue quality, IntValue localIterations, IntValue evaluatedSolutions, bool maximization, int maxIterations, CancellationToken cancellation) {
+      Swap2Move bestMove = null;
+      double evaluations = 0.0;
+      var lastQuality = new double[assignment.Length, assignment.Length];
+      for (int i = localIterations.Value; i < maxIterations; i++) {
+        double bestQuality = 0; // we have to make an improvement, so 0 is the baseline
+        var lastMove = bestMove;
+        bestMove = null;
+        foreach (Swap2Move move in ExhaustiveSwap2MoveGenerator.Generate(assignment)) {
+          double moveQuality;
+          if (lastMove == null) {
+            moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, weights, distances);
+            evaluations += 4.0 / assignment.Length;
+          } else {
+            moveQuality = QAPSwap2MoveEvaluator.Apply(assignment, move, lastQuality[move.Index1, move.Index2], weights, distances, lastMove);
+            if (move.Index1 == lastMove.Index1 || move.Index2 == lastMove.Index1 || move.Index1 == lastMove.Index2 || move.Index2 == lastMove.Index2)
+              evaluations += 4.0 / assignment.Length;
+            else evaluations += 2.0 / (assignment.Length * assignment.Length);
+          }
+          lastQuality[move.Index1, move.Index2] = moveQuality;
           if (maximization && moveQuality > bestQuality
             || !maximization && moveQuality < bestQuality) {
@@ -118 +175 @@
         if (bestMove == null) break;
         Swap2Manipulator.Apply(assignment, bestMove.Index1, bestMove.Index2);
-        quality += bestQuality;
+        quality.Value += bestQuality;
+        localIterations.Value++;
+        if (cancellation.IsCancellationRequested) {
+          evaluatedSolutions.Value += (int)Math.Round(evaluations);
+          throw new OperationCanceledException();
+        }
       }
-      return quality;
+      evaluatedSolutions.Value += (int)Math.Round(evaluations);
     }
 
     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;
-
-      double evaluations;
-      QualityParameter.ActualValue.Value = Improve(assignment, quality, weights, distances, maximization, maxIterations, out evaluations);
-      EvaluatedSolutionsParameter.ActualValue.Value += (int)Math.Ceiling(evaluations);
+      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;
+      }
+
+      if (UseFastEvaluationParameter.ActualValue.Value)
+        ImproveFast(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);
+      else Improve(assignment, weights, distances, quality, localIterations, evaluations, maximization, maxIterations, CancellationToken);
+
+      localIterations.Value = 0;
       return base.Apply();
     }

branches/OaaS/HeuristicLab.Problems.QuadraticAssignment/3.3/Plugin.cs.frame

@@ -23 +23 @@
 
 namespace HeuristicLab.Problems.QuadraticAssignment {
-  [Plugin("HeuristicLab.Problems.QuadraticAssignment", "3.3.6.$WCREV$")]
+  [Plugin("HeuristicLab.Problems.QuadraticAssignment", "3.3.7.$WCREV$")]
   [PluginFile("HeuristicLab.Problems.QuadraticAssignment-3.3.dll", PluginFileType.Assembly)]
   [PluginDependency("HeuristicLab.Analysis", "3.3")]
@@ -34 +34 @@
   [PluginDependency("HeuristicLab.Operators", "3.3")]
   [PluginDependency("HeuristicLab.Optimization", "3.3")]
+  [PluginDependency("HeuristicLab.Optimization.Operators", "3.3")]
   [PluginDependency("HeuristicLab.Parameters", "3.3")]
   [PluginDependency("HeuristicLab.Persistence", "3.3")]

branches/OaaS/HeuristicLab.Problems.QuadraticAssignment/3.3/Properties/AssemblyInfo.cs.frame

@@ -55 +55 @@
 // [assembly: AssemblyVersion("1.0.*")]
 [assembly: AssemblyVersion("3.3.0.0")]
-[assembly: AssemblyFileVersion("3.3.6.$WCREV$")]
+[assembly: AssemblyFileVersion("3.3.7.$WCREV$")]

branches/OaaS/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs

@@ -177 +177 @@
       if (!Parameters.ContainsKey("AverageQuality")) {
         Parameters.Add(new OptionalValueParameter<DoubleValue>("AverageQuality", "The expected quality of a random solution."));
-        AverageQuality = new DoubleValue(Weights.Average() * Distances.Average() * Weights.Rows * Weights.Rows);
+        AverageQuality = new DoubleValue(ComputeAverageQuality());
       }
       #endregion
@@ -303 +303 @@
       Operators.Add(new QAPPopulationDiversityAnalyzer());
       Operators.Add(new QAPExhaustiveSwap2LocalImprovement());
+      Operators.Add(new QAPSimilarityCalculator());
       ParameterizeAnalyzers();
       ParameterizeOperators();
@@ -386 +387 @@
         localOpt.WeightsParameter.ActualName = WeightsParameter.Name;
       }
+
+      QAPSimilarityCalculator similarityCalculator = Operators.OfType<QAPSimilarityCalculator>().SingleOrDefault();
+      if (similarityCalculator != null) {
+        similarityCalculator.SolutionVariableName = SolutionCreator.PermutationParameter.ActualName;
+        similarityCalculator.QualityVariableName = Evaluator.QualityParameter.ActualName;
+      }
     }
 
@@ -401 +408 @@
 
     private void UpdateParameterValues() {
-      LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances));
-      AverageQuality = new DoubleValue(Weights.Average() * Distances.Average() * Weights.Rows * Weights.Rows);
+      Permutation lbSolution;
+      // calculate the optimum of a LAP relaxation and use it as lower bound of our QAP
+      LowerBound = new DoubleValue(GilmoreLawlerBoundCalculator.CalculateLowerBound(Weights, Distances, out lbSolution));
+      // evalute the LAP optimal solution as if it was a QAP solution
+      var lbSolutionQuality = QAPEvaluator.Apply(lbSolution, Weights, Distances);
+      // in case both qualities are the same it means that the LAP optimum is also a QAP optimum
+      if (LowerBound.Value.IsAlmost(lbSolutionQuality)) {
+        BestKnownSolution = lbSolution;
+        BestKnownQuality = new DoubleValue(LowerBound.Value);
+      }
+      AverageQuality = new DoubleValue(ComputeAverageQuality());
+    }
+
+    private double ComputeAverageQuality() {
+      double rt = 0, rd = 0, wt = 0, wd = 0;
+      int n = Weights.Rows;
+      for (int i = 0; i < n; i++)
+        for (int j = 0; j < n; j++) {
+          if (i == j) {
+            rd += Distances[i, i];
+            wd += Weights[i, i];
+          } else {
+            rt += Distances[i, j];
+            wt += Weights[i, j];
+          }
+        }
+
+      return rt * wt / (n * (n - 1)) + rd * wd / n;
     }
     #endregion
@@ -412 +445 @@
       Description = data.Description;
       Load(weights, distances);
+      if (data.BestKnownQuality.HasValue) BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
       EvaluateAndLoadAssignment(data.BestKnownAssignment);
       OnReset();
@@ -426 +460 @@
       Description = data.Description;
       Load(weights, distances);
+      if (data.BestKnownQuality.HasValue) BestKnownQuality = new DoubleValue(data.BestKnownQuality.Value);
       EvaluateAndLoadAssignment(data.BestKnownTour);
       OnReset();

@@ -21 +21 @@
 protoc.exe
 _ReSharper.HeuristicLab 3.3 Tests
+Google.ProtocolBuffers-2.4.1.473.dll
 packages