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

Timestamp:

08/04/11 10:04:09 (13 years ago)

Author:

abeham

Message:

#1541, #1603, #1606, #1607

• merged to trunk

Location:

trunk/sources

Files:

• . (modified) (1 prop)
• HeuristicLab.Problems.QuadraticAssignment/3.3/Analyzers/QAPAlleleFrequencyAnalyzer.cs (modified) (2 diffs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/Analyzers/QAPPopulationDiversityAnalyzer.cs (modified) (5 diffs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/Evaluators/QAPSwap2MoveEvaluator.cs (modified) (2 diffs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/HeuristicLab.Problems.QuadraticAssignment-3.3.csproj (modified) (1 diff)
• HeuristicLab.Problems.QuadraticAssignment/3.3/QAPPermutationProximityCalculator.cs (copied) (copied from branches/QAPAlgorithms/HeuristicLab.Problems.QuadraticAssignment/3.3/QAPPermutationProximityCalculator.cs)
• HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.QuadraticAssignment/3.3/Tests/QAPMoveEvaluatorTest.cs (modified) (1 diff)

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/Analyzers/QAPAlleleFrequencyAnalyzer.cs

@@ -20 +20 @@
 #endregion
 
+using System.Collections.Generic;
 using HeuristicLab.Analysis;
 using HeuristicLab.Common;
@@ -56 +57 @@
 
     protected override Allele[] CalculateAlleles(Permutation solution) {
-      Allele[] alleles = new Allele[solution.Length];
+      Allele[] alleles = new Allele[solution.Length * solution.Length];
+      Dictionary<string, int> allelesDict = new Dictionary<string, int>();
       DoubleMatrix weights = WeightsParameter.ActualValue;
       DoubleMatrix distances = DistancesParameter.ActualValue;
-      int source, target;
       double impact;
 
-      for (int i = 0; i < solution.Length; i++) {
-        source = i;
-        target = solution[i];
-        impact = 0;
-        for (int j = 0; j < solution.Length; j++)
-          impact += weights[source, j] * distances[target, solution[j]];
-        alleles[i] = new Allele(source.ToString() + "->" + target.ToString(), impact);
+      for (int x = 0; x < solution.Length; x++) {
+        for (int y = 0; y < solution.Length; y++) {
+          string allele = weights[x, y].ToString() + ">" + distances[solution[x], solution[y]].ToString();
+          int repetition = 1;
+          if (allelesDict.ContainsKey(allele)) repetition += allelesDict[allele];
+          allelesDict[allele] = repetition;
+          impact = weights[x, y] * distances[solution[x], solution[y]];
+          alleles[x * solution.Length + y] = new Allele(allele + "/" + repetition, impact);
+        }
       }
 

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/Analyzers/QAPPopulationDiversityAnalyzer.cs

@@ -23 +23 @@
 using HeuristicLab.Common;
 using HeuristicLab.Core;
+using HeuristicLab.Data;
 using HeuristicLab.Encodings.PermutationEncoding;
+using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
 
@@ -33 +35 @@
   [StorableClass]
   public sealed class QAPPopulationDiversityAnalyzer : PopulationDiversityAnalyzer<Permutation> {
+    public IValueParameter<BoolValue> UsePhenotypeSimilarityParameter {
+      get { return (IValueParameter<BoolValue>)Parameters["UsePhenotypeSimilarity"]; }
+    }
+    public ILookupParameter<DoubleMatrix> WeightsParameter {
+      get { return (ILookupParameter<DoubleMatrix>)Parameters["Weights"]; }
+    }
+    public ILookupParameter<DoubleMatrix> DistancesParameter {
+      get { return (ILookupParameter<DoubleMatrix>)Parameters["Distances"]; }
+    }
+
     [StorableConstructor]
     private QAPPopulationDiversityAnalyzer(bool deserializing) : base(deserializing) { }
     private QAPPopulationDiversityAnalyzer(QAPPopulationDiversityAnalyzer original, Cloner cloner) : base(original, cloner) { }
-    public QAPPopulationDiversityAnalyzer() : base() { }
+    public QAPPopulationDiversityAnalyzer()
+      : base() {
+      Parameters.Add(new ValueParameter<BoolValue>("UsePhenotypeSimilarity", "True if the similarity should be measured a level closer to the phenotype (the number of similar assignments of individual weights to distances). Set to false if the number of equal assignments (facility to location) should be counted.", new BoolValue(false)));
+      Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix."));
+      Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix."));
+    }
 
     public override IDeepCloneable Clone(Cloner cloner) {
@@ -42 +59 @@
     }
 
+    [StorableHook(HookType.AfterDeserialization)]
+    private void AfterDeserialization() {
+      // BackwardsCompatibility3.3
+      #region Backwards compatible code, remove with 3.4
+      if (!Parameters.ContainsKey("UsePhenotypeSimilarity"))
+        Parameters.Add(new ValueParameter<BoolValue>("UsePhenotypeSimilarity", "True if the similarity should be measured a level closer to the phenotype (the number of similar assignments of individual weights to distances). Set to false if the number of equal assignments (facility to location) should be counted.", new BoolValue(false)));
+      if (!Parameters.ContainsKey("Weights"))
+        Parameters.Add(new LookupParameter<DoubleMatrix>("Weights", "The weights matrix."));
+      if (!Parameters.ContainsKey("Distances"))
+        Parameters.Add(new LookupParameter<DoubleMatrix>("Distances", "The distances matrix."));
+      #endregion
+    }
+
     protected override double[,] CalculateSimilarities(Permutation[] solutions) {
+      DoubleMatrix weights = WeightsParameter.ActualValue, distances = DistancesParameter.ActualValue;
+      bool phenotypeSimilarity = UsePhenotypeSimilarityParameter.Value.Value;
       int count = solutions.Length;
       double[,] similarities = new double[count, count];
@@ -49 +81 @@
         similarities[i, i] = 1;
         for (int j = i + 1; j < count; j++) {
-          similarities[i, j] = CalculateSimilarity(solutions[i], solutions[j]);
+          if (phenotypeSimilarity)
+            similarities[i, j] = QAPPermutationProximityCalculator.CalculatePhenotypeSimilarity(solutions[i], solutions[j], weights, distances);
+          else similarities[i, j] = QAPPermutationProximityCalculator.CalculateGenotypeSimilarity(solutions[i], solutions[j]);
           similarities[j, i] = similarities[i, j];
         }
@@ -55 +89 @@
       return similarities;
     }
-
-    private double CalculateSimilarity(Permutation assignment1, Permutation assignment2) {
-      int identicalAssignments = 0;
-      for (int i = 0; i < assignment1.Length; i++) {
-        if (assignment1[i] == assignment2[i])
-          identicalAssignments++;
-      }
-      return ((double)identicalAssignments) / assignment1.Length;
-    }
   }
 }

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/Evaluators/QAPSwap2MoveEvaluator.cs

@@ -49 +49 @@
     }
 
+    /// <summary>
+    /// Calculates the quality of the move <paramref name="move"/> by evaluating the changes.
+    /// The runtime complexity of this method is O(N) with N being the size of the permutation.
+    /// </summary>
+    /// <param name="assignment">The current permutation.</param>
+    /// <param name="move">The move that is to be evaluated if it was applied to the current permutation.</param>
+    /// <param name="weights">The weights matrix.</param>
+    /// <param name="distances">The distances matrix.</param>
+    /// <returns>The relative change in quality if <paramref name="move"/> was applied to <paramref name="assignment"/>.</returns>
     public static double Apply(Permutation assignment, Swap2Move move, DoubleMatrix weights, DoubleMatrix distances) {
       if (move.Index1 == move.Index2) return 0;
@@ -73 +82 @@
     }
 
+    /// <summary>
+    /// Is able to compute the move qualities faster O(1) in some cases if it knows the quality of
+    /// performing the move <paramref name="move"/> previously. In other cases it performs a
+    /// standard move quality calculation with runtime complexity O(N).
+    /// </summary>
+    /// <remarks>
+    /// The number of cases that the calculation can be performed faster grows with N^2
+    /// while the number of cases which require a larger recalculation grows linearly with N.
+    /// Larger problem instances thus benefit from this faster method to a larger degree.
+    /// </remarks>
+    /// <param name="assignment">The current permutation.</param>
+    /// <param name="move">The current move that is to be evaluated.</param>
+    /// <param name="previousQuality">The quality of that move as evaluated for the previous permutation.</param>
+    /// <param name="weights">The weigths matrix.</param>
+    /// <param name="distances">The distances matrix.</param>
+    /// <param name="lastMove">The move that was applied to transform the permutation from the previous to the current one.</param>
+    /// <returns>The relative change in quality if <paramref name="move"/> was applied to <paramref name="assignment"/>.</returns>
+    public static double Apply(Permutation assignment, Swap2Move move, double previousQuality,
+      DoubleMatrix weights, DoubleMatrix distances, Swap2Move lastMove) {
+      bool overlapsLastMove = move.Index1 == lastMove.Index1
+                           || move.Index2 == lastMove.Index1
+                           || move.Index1 == lastMove.Index2
+                           || move.Index2 == lastMove.Index2;
+
+      if (!overlapsLastMove) {
+        int r = lastMove.Index1, u = move.Index1, s = lastMove.Index2, v = move.Index2;
+        int pR = assignment[lastMove.Index1], pU = assignment[move.Index1], pS = assignment[lastMove.Index2], pV = assignment[move.Index2];
+
+        return previousQuality
+          + (weights[r, u] - weights[r, v] + weights[s, v] - weights[s, u])
+            * (distances[pS, pU] - distances[pS, pV] + distances[pR, pV] - distances[pR, pU])
+          + (weights[u, r] - weights[v, r] + weights[v, s] - weights[u, s])
+            * (distances[pU, pS] - distances[pV, pS] + distances[pV, pR] - distances[pU, pR]);
+      } else {
+        return Apply(assignment, move, weights, distances);
+      }
+    }
+
     public override IOperation Apply() {
       Swap2Move move = Swap2MoveParameter.ActualValue;

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

@@ -124 +124 @@
     <Compile Include="Parsers\QAPLIBParser.cs" />
     <Compile Include="QAPAssignment.cs" />
+    <Compile Include="QAPPermutationProximityCalculator.cs" />
     <Compile Include="QuadraticAssignmentProblem.cs" />
     <EmbeddedResource Include="Data\bur26a.dat" />

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/QuadraticAssignmentProblem.cs

@@ -385 +385 @@
         Distances = new DoubleMatrix(parser.Distances);
         Weights = new DoubleMatrix(parser.Weights);
-        Name = "Quadratic Assignment Problem (loaded instance " + instance + ")";
-        Description = "Loaded embedded problem data of instance " + instance + ".";
+        Name = instance;
+        Description = "Loaded embedded QAPLIB problem data of instance " + instance + ".";
         OnReset();
       }

trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/Tests/QAPMoveEvaluatorTest.cs

@@ -60 +60 @@
       for (int i = 0; i < ProblemSize - 1; i++) {
         for (int j = i + 1; j < ProblemSize; j++) {
-          symmetricDistances[i, j] = random.Next(ProblemSize);
+          symmetricDistances[i, j] = random.Next(ProblemSize * 100);
           symmetricDistances[j, i] = symmetricDistances[i, j];
-          symmetricWeights[i, j] = random.Next(ProblemSize);
+          symmetricWeights[i, j] = random.Next(ProblemSize * 100);
           symmetricWeights[j, i] = symmetricWeights[i, j];
-          asymmetricDistances[i, j] = random.Next(ProblemSize);
-          asymmetricDistances[j, i] = random.Next(ProblemSize);
-          asymmetricWeights[i, j] = random.Next(ProblemSize);
-          asymmetricWeights[j, i] = random.Next(ProblemSize);
-          nonZeroDiagonalDistances[i, j] = random.Next(ProblemSize);
-          nonZeroDiagonalDistances[j, i] = random.Next(ProblemSize);
-          nonZeroDiagonalWeights[i, j] = random.Next(ProblemSize);
-          nonZeroDiagonalWeights[j, i] = random.Next(ProblemSize);
+          asymmetricDistances[i, j] = random.Next(ProblemSize * 100);
+          asymmetricDistances[j, i] = random.Next(ProblemSize * 100);
+          asymmetricWeights[i, j] = random.Next(ProblemSize * 100);
+          asymmetricWeights[j, i] = random.Next(ProblemSize * 100);
+          nonZeroDiagonalDistances[i, j] = random.Next(ProblemSize * 100);
+          nonZeroDiagonalDistances[j, i] = random.Next(ProblemSize * 100);
+          nonZeroDiagonalWeights[i, j] = random.Next(ProblemSize * 100);
+          nonZeroDiagonalWeights[j, i] = random.Next(ProblemSize * 100);
         }
-        nonZeroDiagonalDistances[i, i] = random.Next(ProblemSize);
-        nonZeroDiagonalWeights[i, i] = random.Next(ProblemSize);
+        nonZeroDiagonalDistances[i, i] = random.Next(ProblemSize * 100);
+        nonZeroDiagonalWeights[i, i] = random.Next(ProblemSize * 100);
       }
       int index = random.Next(ProblemSize);
       if (nonZeroDiagonalDistances[index, index] == 0)
-        nonZeroDiagonalDistances[index, index] = random.Next(1, ProblemSize);
+        nonZeroDiagonalDistances[index, index] = random.Next(1, ProblemSize * 100);
       index = random.Next(ProblemSize);
       if (nonZeroDiagonalWeights[index, index] == 0)
-        nonZeroDiagonalWeights[index, index] = random.Next(1, ProblemSize);
+        nonZeroDiagonalWeights[index, index] = random.Next(1, ProblemSize * 100);
       assignment = new Permutation(PermutationTypes.Absolute, ProblemSize, random);
+    }
+
+    [TestMethod]
+    public void Swap2MoveEvaluatorFastEvaluationTest() {
+
+      for (int i = 0; i < 500; i++) {
+        Swap2Move lastMove = new Swap2Move(random.Next(ProblemSize), random.Next(ProblemSize));
+        Permutation prevAssignment = (Permutation)assignment.Clone();
+        Swap2Manipulator.Apply(assignment, lastMove.Index1, lastMove.Index2);
+        Permutation nextAssignment = (Permutation)assignment.Clone();
+        Swap2Move currentMove = new Swap2Move(random.Next(ProblemSize), random.Next(ProblemSize));
+        Swap2Manipulator.Apply(nextAssignment, currentMove.Index1, currentMove.Index2);
+
+        double moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, symmetricWeights, symmetricDistances);
+        double moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
+                moveBefore, symmetricWeights, symmetricDistances, lastMove);
+        double before = QAPEvaluator.Apply(assignment, symmetricWeights, symmetricDistances);
+        double after = QAPEvaluator.Apply(nextAssignment, symmetricWeights, symmetricDistances);
+
+        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on symmetric matrices: " + Environment.NewLine
+          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
+
+        moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, asymmetricWeights, asymmetricDistances);
+        moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
+                moveBefore, asymmetricWeights, asymmetricDistances, lastMove);
+        before = QAPEvaluator.Apply(assignment, asymmetricWeights, asymmetricDistances);
+        after = QAPEvaluator.Apply(nextAssignment, asymmetricWeights, asymmetricDistances);
+
+        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on asymmetric matrices: " + Environment.NewLine
+          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
+
+        moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
+        moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
+                moveBefore, nonZeroDiagonalWeights, nonZeroDiagonalDistances, lastMove);
+        before = QAPEvaluator.Apply(assignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
+        after = QAPEvaluator.Apply(nextAssignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
+
+        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on non-zero diagonal matrices: " + Environment.NewLine
+          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
+      }
     }