Free cookie consent management tool by TermsFeed Policy Generator

source: branches/histogram/HeuristicLab.Problems.QuadraticAssignment/3.3/Tests/QAPMoveEvaluatorTest.cs @ 6194

Last change on this file since 6194 was 5933, checked in by abeham, 13 years ago

#1330

  • Merged QAP from branch into trunk
  • Merged MDS from branch into trunk
  • Merged Swap2 moves from branch into trunk
File size: 10.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2011 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using HeuristicLab.Common;
24using HeuristicLab.Data;
25using HeuristicLab.Encodings.PermutationEncoding;
26using HeuristicLab.Random;
27using Microsoft.VisualStudio.TestTools.UnitTesting;
28
29namespace HeuristicLab.Problems.QuadraticAssignment.Tests_33 {
30
31  /// <summary>
32  ///This is a test class for the QAP move evaluators
33  ///</summary>
34  [TestClass()]
35  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;
40
41    private TestContext testContextInstance;
42    /// <summary>
43    ///Gets or sets the test context which provides
44    ///information about and functionality for the current test run.
45    ///</summary>
46    public TestContext TestContext {
47      get { return testContextInstance; }
48      set { testContextInstance = value; }
49    }
50
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    }
86
87    [TestMethod]
88    public void Swap2MoveEvaluatorTest() {
89      for (int i = 0; i < 500; i++) {
90        int index1 = random.Next(ProblemSize);
91        int index2 = random.Next(ProblemSize);
92
93        // SYMMETRIC MATRICES
94        double before = QAPEvaluator.Apply(assignment, symmetricWeights, symmetricDistances);
95        Swap2Manipulator.Apply(assignment, index1, index2);
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");
115      }
116    }
117
118    [TestMethod]
119    public void InversionMoveEvaluatorTest() {
120      for (int i = 0; i < 500; i++) {
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);
127        InversionManipulator.Apply(assignment, Math.Min(index1, index2), Math.Max(index1, index2));
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");
147      }
148    }
149
150    [TestMethod]
151    public void TranslocationMoveEvaluatorTest() {
152      for (int i = 0; i < 500; i++) {
153        int index1 = random.Next(assignment.Length - 1);
154        int index2 = random.Next(index1 + 1, assignment.Length);
155        int insertPointLimit = assignment.Length - index2 + index1 - 1;  // get insertion point in remaining part
156        int insertPoint;
157        if (insertPointLimit > 0)
158          insertPoint = random.Next(insertPointLimit);
159        else
160          insertPoint = 0;
161
162        // SYMMETRIC MATRICES
163        double before = QAPEvaluator.Apply(assignment, symmetricWeights, symmetricDistances);
164        Permutation clone = new Cloner().Clone(assignment);
165        TranslocationManipulator.Apply(assignment, index1, index2, insertPoint);
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");
185      }
186    }
187
188  }
189}
Note: See TracBrowser for help on using the repository browser.