Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
04/02/11 16:34:32 (14 years ago)
Author:
abeham
Message:

#1330

  • fixed a bug in the swap-2 move evaluator regarding asymmetric matrices and matrices with non-zero diagonals
  • fixed a similar bug for evaluating inversion moves
  • enhanced test cases
  • Renamed !QAPSwapMoveEvaluator.cs to !QAPSwap2MoveEvaluator.cs
Location:
branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3
Files:
1 added
1 deleted
3 edited

Legend:

Unmodified
Added
Removed

  • branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/Evaluators/QAPInversionMoveEvaluator.cs

    r5838 r5930  
    5454      int min = Math.Min(move.Index1, move.Index2);
    5555      int max = Math.Max(move.Index1, move.Index2);
     56
    5657      for (int i = min; i <= max; i++) {
     58        int locI = assignment[i];
     59        int newlocI = assignment[max - i + min];
     60
    5761        for (int j = 0; j < assignment.Length; j++) {
    58           moveQuality -= weights[i, j] * distances[assignment[i], assignment[j]];
    59           if (j < min || j > max) {
    60             moveQuality -= weights[j, i] * distances[assignment[j], assignment[i]];
    61             moveQuality += weights[i, j] * distances[assignment[max - i + min], assignment[j]];
    62             moveQuality += weights[j, i] * distances[assignment[j], assignment[max - i + min]];
     62          int locJ = assignment[j];
     63          if (j >= min && j <= max) {
     64            int newlocJ = assignment[max - j + min];
     65            moveQuality += weights[i, j] * (distances[newlocI, newlocJ] - distances[locI, locJ]);
    6366          } else {
    64             moveQuality += weights[i, j] * distances[assignment[max - i + min], assignment[max - j + min]];
     67            moveQuality += weights[i, j] * (distances[newlocI, locJ] - distances[locI, locJ]);
     68            moveQuality += weights[j, i] * (distances[locJ, newlocI] - distances[locJ, locI]);
    6569          }
    6670        }

  • branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/HeuristicLab.Problems.QuadraticAssignment-3.3.csproj

    r5873 r5930  
    139139  <ItemGroup>
    140140    <Compile Include="Analyzers\BestQAPSolutionAnalyzer.cs" />
    141     <Compile Include="Evaluators\QAPSwapMoveEvaluator.cs" />
     141    <Compile Include="Evaluators\QAPSwap2MoveEvaluator.cs" />
    142142    <Compile Include="Evaluators\QAPEvaluator.cs" />
    143143    <Compile Include="Evaluators\QAPInversionMoveEvaluator.cs" />

  • branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/Tests/QAPMoveEvaluatorTest.cs

    r5838 r5930  
    3434  [TestClass()]
    3535  public class QAPSwapMoveEvaluatorTest {
     36    private const int ProblemSize = 10;
     37    private static DoubleMatrix symmetricDistances, symmetricWeights, asymmetricDistances, asymmetricWeights, nonZeroDiagonalWeights, nonZeroDiagonalDistances;
     38    private static Permutation assignment;
     39    private static MersenneTwister random;
    3640
    3741    private TestContext testContextInstance;
    … …  
    4549    }
    4650
    47     #region Additional test attributes
    48     //
    49     //You can use the following additional attributes as you write your tests:
    50     //
    51     //Use ClassInitialize to run code before running the first test in the class
    52     //[ClassInitialize()]
    53     //public static void MyClassInitialize(TestContext testContext)
    54     //{
    55     //}
    56     //
    57     //Use ClassCleanup to run code after all tests in a class have run
    58     //[ClassCleanup()]
    59     //public static void MyClassCleanup()
    60     //{
    61     //}
    62     //
    63     //Use TestInitialize to run code before running each test
    64     //[TestInitialize()]
    65     //public void MyTestInitialize()
    66     //{
    67     //}
    68     //
    69     //Use TestCleanup to run code after each test has run
    70     //[TestCleanup()]
    71     //public void MyTestCleanup()
    72     //{
    73     //}
    74     //
    75     #endregion
     51    [ClassInitialize]
     52    public static void MyClassInitialize(TestContext testContext) {
     53      random = new MersenneTwister();
     54      symmetricDistances = new DoubleMatrix(ProblemSize, ProblemSize);
     55      symmetricWeights = new DoubleMatrix(ProblemSize, ProblemSize);
     56      asymmetricDistances = new DoubleMatrix(ProblemSize, ProblemSize);
     57      asymmetricWeights = new DoubleMatrix(ProblemSize, ProblemSize);
     58      nonZeroDiagonalDistances = new DoubleMatrix(ProblemSize, ProblemSize);
     59      nonZeroDiagonalWeights = new DoubleMatrix(ProblemSize, ProblemSize);
     60      for (int i = 0; i < ProblemSize - 1; i++) {
     61        for (int j = i + 1; j < ProblemSize; j++) {
     62          symmetricDistances[i, j] = random.Next(ProblemSize);
     63          symmetricDistances[j, i] = symmetricDistances[i, j];
     64          symmetricWeights[i, j] = random.Next(ProblemSize);
     65          symmetricWeights[j, i] = symmetricWeights[i, j];
     66          asymmetricDistances[i, j] = random.Next(ProblemSize);
     67          asymmetricDistances[j, i] = random.Next(ProblemSize);
     68          asymmetricWeights[i, j] = random.Next(ProblemSize);
     69          asymmetricWeights[j, i] = random.Next(ProblemSize);
     70          nonZeroDiagonalDistances[i, j] = random.Next(ProblemSize);
     71          nonZeroDiagonalDistances[j, i] = random.Next(ProblemSize);
     72          nonZeroDiagonalWeights[i, j] = random.Next(ProblemSize);
     73          nonZeroDiagonalWeights[j, i] = random.Next(ProblemSize);
     74        }
     75        nonZeroDiagonalDistances[i, i] = random.Next(ProblemSize);
     76        nonZeroDiagonalWeights[i, i] = random.Next(ProblemSize);
     77      }
     78      int index = random.Next(ProblemSize);
     79      if (nonZeroDiagonalDistances[index, index] == 0)
     80        nonZeroDiagonalDistances[index, index] = random.Next(1, ProblemSize);
     81      index = random.Next(ProblemSize);
     82      if (nonZeroDiagonalWeights[index, index] == 0)
     83        nonZeroDiagonalWeights[index, index] = random.Next(1, ProblemSize);
     84      assignment = new Permutation(PermutationTypes.Absolute, ProblemSize, random);
     85    }
    7686
    7787    [TestMethod]
    78     public void SwapMoveEvaluatorTest() {
    79       DoubleMatrix distances = new DoubleMatrix(
    80         new double[,] { { 0, 1, 2, 3 },
    81                         { 1, 0, 3, 4 },
    82                         { 2, 3, 0, 5 },
    83                         { 3, 4, 5, 0 } });
    84       DoubleMatrix weights = new DoubleMatrix(
    85         new double[,] { { 0, 1, 0, 0 },
    86                         { 1, 0, 2, 0 },
    87                         { 0, 2, 0, 1 },
    88                         { 0, 0, 1, 0 } });
    89       Permutation assignment = new Permutation(PermutationTypes.Absolute,
    90         new int[] { 0, 1, 2, 3 });
    91       MersenneTwister random = new MersenneTwister();
     88    public void Swap2MoveEvaluatorTest() {
    9289      for (int i = 0; i < 500; i++) {
    93         int index1 = random.Next(4);
    94         int index2 = random.Next(4);
    95         double before = QAPEvaluator.Apply(assignment, weights, distances);
     90        int index1 = random.Next(ProblemSize);
     91        int index2 = random.Next(ProblemSize);
     92
     93        // SYMMETRIC MATRICES
     94        double before = QAPEvaluator.Apply(assignment, symmetricWeights, symmetricDistances);
    9695        Swap2Manipulator.Apply(assignment, index1, index2);
    97         double after = QAPEvaluator.Apply(assignment, weights, distances);
    98         // evaluate swap back
    99         double move = QAPSwap2MoveEvaluator.Apply(assignment, new Swap2Move(index1, index2, assignment), weights, distances);
    100         Assert.IsTrue(move.IsAlmost(before - after));
     96        double after = QAPEvaluator.Apply(assignment, symmetricWeights, symmetricDistances);
     97        double move = QAPSwap2MoveEvaluator.Apply(assignment, new Swap2Move(index1, index2, assignment), symmetricWeights, symmetricDistances);
     98        Assert.IsTrue(move.IsAlmost(before - after), "Failed on symmetric matrices");
     99
     100        // ASYMMETRIC MATRICES
     101        before = QAPEvaluator.Apply(assignment, asymmetricWeights, asymmetricDistances);
     102        Permutation clone = (Permutation)assignment.Clone();
     103        Swap2Manipulator.Apply(assignment, index1, index2);
     104        after = QAPEvaluator.Apply(assignment, asymmetricWeights, asymmetricDistances);
     105        move = QAPSwap2MoveEvaluator.Apply(clone, new Swap2Move(index1, index2), asymmetricWeights, asymmetricDistances);
     106        Assert.IsTrue(move.IsAlmost(after - before), "Failed on asymmetric matrices");
     107
     108        // NON-ZERO DIAGONAL ASSYMETRIC MATRICES
     109        before = QAPEvaluator.Apply(assignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     110        clone = (Permutation)assignment.Clone();
     111        Swap2Manipulator.Apply(assignment, index1, index2);
     112        after = QAPEvaluator.Apply(assignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     113        move = QAPSwap2MoveEvaluator.Apply(clone, new Swap2Move(index1, index2), nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     114        Assert.IsTrue(move.IsAlmost(after - before), "Failed on non-zero diagonal matrices");
    101115      }
    102116    }
    … …  
    104118    [TestMethod]
    105119    public void InversionMoveEvaluatorTest() {
    106       DoubleMatrix distances = new DoubleMatrix(
    107         new double[,] { { 0, 1, 2, 3 },
    108                         { 1, 0, 3, 4 },
    109                         { 2, 3, 0, 5 },
    110                         { 3, 4, 5, 0 } });
    111       DoubleMatrix weights = new DoubleMatrix(
    112         new double[,] { { 0, 1, 0, 0 },
    113                         { 1, 0, 2, 0 },
    114                         { 0, 2, 0, 1 },
    115                         { 0, 0, 1, 0 } });
    116       Permutation assignment = new Permutation(PermutationTypes.Absolute,
    117         new int[] { 0, 1, 2, 3 });
    118       MersenneTwister random = new MersenneTwister();
    119120      for (int i = 0; i < 500; i++) {
    120         int index1 = random.Next(4);
    121         int index2 = random.Next(4);
    122         double before = QAPEvaluator.Apply(assignment, weights, distances);
    123         // invert
     121        int index1 = random.Next(ProblemSize);
     122        int index2 = random.Next(ProblemSize);
     123        if (index1 > index2) { int h = index1; index1 = index2; index2 = h; }
     124
     125        // SYMMETRIC MATRICES
     126        double before = QAPEvaluator.Apply(assignment, symmetricWeights, symmetricDistances);
    124127        InversionManipulator.Apply(assignment, Math.Min(index1, index2), Math.Max(index1, index2));
    125         double after = QAPEvaluator.Apply(assignment, weights, distances);
    126         // evaluate invert back
    127         double move = QAPInversionMoveEvaluator.Apply(assignment, new InversionMove(index1, index2, assignment), weights, distances);
    128         Assert.IsTrue(move.IsAlmost(before - after));
     128        double after = QAPEvaluator.Apply(assignment, symmetricWeights, symmetricDistances);
     129        double move = QAPInversionMoveEvaluator.Apply(assignment, new InversionMove(index1, index2, assignment), symmetricWeights, symmetricDistances);
     130        Assert.IsTrue(move.IsAlmost(before - after), "Failed on symmetric matrices");
     131
     132        // ASYMMETRIC MATRICES
     133        before = QAPEvaluator.Apply(assignment, asymmetricWeights, asymmetricDistances);
     134        Permutation clone = (Permutation)assignment.Clone();
     135        InversionManipulator.Apply(assignment, index1, index2);
     136        after = QAPEvaluator.Apply(assignment, asymmetricWeights, asymmetricDistances);
     137        move = QAPInversionMoveEvaluator.Apply(clone, new InversionMove(index1, index2), asymmetricWeights, asymmetricDistances);
     138        Assert.IsTrue(move.IsAlmost(after - before), "Failed on asymmetric matrices");
     139
     140        // NON-ZERO DIAGONAL ASYMMETRIC MATRICES
     141        before = QAPEvaluator.Apply(assignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     142        clone = (Permutation)assignment.Clone();
     143        InversionManipulator.Apply(assignment, index1, index2);
     144        after = QAPEvaluator.Apply(assignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     145        move = QAPInversionMoveEvaluator.Apply(clone, new InversionMove(index1, index2), nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     146        Assert.IsTrue(move.IsAlmost(after - before), "Failed on non-zero diagonal matrices");
    129147      }
    130148    }
    … …  
    132150    [TestMethod]
    133151    public void TranslocationMoveEvaluatorTest() {
    134       DoubleMatrix distances = new DoubleMatrix(
    135         new double[,] { { 0, 1, 2, 3 },
    136                         { 1, 0, 3, 4 },
    137                         { 2, 3, 0, 5 },
    138                         { 3, 4, 5, 0 } });
    139       DoubleMatrix weights = new DoubleMatrix(
    140         new double[,] { { 0, 1, 0, 0 },
    141                         { 1, 0, 2, 0 },
    142                         { 0, 2, 0, 1 },
    143                         { 0, 0, 1, 0 } });
    144       Permutation assignment = new Permutation(PermutationTypes.Absolute,
    145         new int[] { 0, 1, 2, 3 });
    146       MersenneTwister random = new MersenneTwister();
    147152      for (int i = 0; i < 500; i++) {
    148153        int index1 = random.Next(assignment.Length - 1);
    … …  
    154159        else
    155160          insertPoint = 0;
    156         double before = QAPEvaluator.Apply(assignment, weights, distances);
    157         // translocate
     161
     162        // SYMMETRIC MATRICES
     163        double before = QAPEvaluator.Apply(assignment, symmetricWeights, symmetricDistances);
    158164        Permutation clone = new Cloner().Clone(assignment);
    159165        TranslocationManipulator.Apply(assignment, index1, index2, insertPoint);
    160         double after = QAPEvaluator.Apply(assignment, weights, distances);
    161         // evaluate translocate move
    162         double move = QAPTranslocationMoveEvaluator.Apply(clone, new TranslocationMove(index1, index2, insertPoint, assignment), weights, distances);
    163         Assert.IsTrue(move.IsAlmost(after - before));
     166        double after = QAPEvaluator.Apply(assignment, symmetricWeights, symmetricDistances);
     167        double move = QAPTranslocationMoveEvaluator.Apply(clone, new TranslocationMove(index1, index2, insertPoint, assignment), symmetricWeights, symmetricDistances);
     168        Assert.IsTrue(move.IsAlmost(after - before), "Failed on symmetric matrices");
     169
     170        // ASYMMETRIC MATRICES
     171        before = QAPEvaluator.Apply(assignment, asymmetricWeights, asymmetricDistances);
     172        clone = new Cloner().Clone(assignment);
     173        TranslocationManipulator.Apply(assignment, index1, index2, insertPoint);
     174        after = QAPEvaluator.Apply(assignment, asymmetricWeights, asymmetricDistances);
     175        move = QAPTranslocationMoveEvaluator.Apply(clone, new TranslocationMove(index1, index2, insertPoint, assignment), asymmetricWeights, asymmetricDistances);
     176        Assert.IsTrue(move.IsAlmost(after - before), "Failed on asymmetric matrices");
     177
     178        // NON-ZERO DIAGONAL ASYMMETRIC MATRICES
     179        before = QAPEvaluator.Apply(assignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     180        clone = new Cloner().Clone(assignment);
     181        TranslocationManipulator.Apply(assignment, index1, index2, insertPoint);
     182        after = QAPEvaluator.Apply(assignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     183        move = QAPTranslocationMoveEvaluator.Apply(clone, new TranslocationMove(index1, index2, insertPoint, assignment), nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     184        Assert.IsTrue(move.IsAlmost(after - before), "Failed on non-zero diagonal matrices");
    164185      }
    165186    }
Note: See TracChangeset for help on using the changeset viewer.