Free cookie consent management tool by TermsFeed Policy Generator

source: branches/2521_ProblemRefactoring/HeuristicLab.Tests/HeuristicLab.Problems.QuadraticAssignment-3.3/QAPMoveEvaluatorTest.cs

Last change on this file was 17321, checked in by abeham, 5 years ago

#2521: fixed compile errors in Tests
File size: 15.5 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 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 System.Threading;
24using HeuristicLab.Common;
25using HeuristicLab.Data;
26using HeuristicLab.Encodings.PermutationEncoding;
27using HeuristicLab.Random;
28using Microsoft.VisualStudio.TestTools.UnitTesting;
29
30namespace HeuristicLab.Problems.QuadraticAssignment.Tests {
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
39    private static QuadraticAssignmentProblem symmetricProblem, asymmetricProblem, nonZeroDiagonalProblem;
40    private static Permutation assignment;
41    private static MersenneTwister random;
42
43    private TestContext testContextInstance;
44    /// <summary>
45    ///Gets or sets the test context which provides
46    ///information about and functionality for the current test run.
47    ///</summary>
48    public TestContext TestContext {
49      get { return testContextInstance; }
50      set { testContextInstance = value; }
51    }
52
53    [ClassInitialize]
54    public static void MyClassInitialize(TestContext testContext) {
55      random = new MersenneTwister();
56      symmetricDistances = new DoubleMatrix(ProblemSize, ProblemSize);
57      symmetricWeights = new DoubleMatrix(ProblemSize, ProblemSize);
58      asymmetricDistances = new DoubleMatrix(ProblemSize, ProblemSize);
59      asymmetricWeights = new DoubleMatrix(ProblemSize, ProblemSize);
60      nonZeroDiagonalDistances = new DoubleMatrix(ProblemSize, ProblemSize);
61      nonZeroDiagonalWeights = new DoubleMatrix(ProblemSize, ProblemSize);
62      for (int i = 0; i < ProblemSize - 1; i++) {
63        for (int j = i + 1; j < ProblemSize; j++) {
64          symmetricDistances[i, j] = random.Next(ProblemSize * 100);
65          symmetricDistances[j, i] = symmetricDistances[i, j];
66          symmetricWeights[i, j] = random.Next(ProblemSize * 100);
67          symmetricWeights[j, i] = symmetricWeights[i, j];
68          asymmetricDistances[i, j] = random.Next(ProblemSize * 100);
69          asymmetricDistances[j, i] = random.Next(ProblemSize * 100);
70          asymmetricWeights[i, j] = random.Next(ProblemSize * 100);
71          asymmetricWeights[j, i] = random.Next(ProblemSize * 100);
72          nonZeroDiagonalDistances[i, j] = random.Next(ProblemSize * 100);
73          nonZeroDiagonalDistances[j, i] = random.Next(ProblemSize * 100);
74          nonZeroDiagonalWeights[i, j] = random.Next(ProblemSize * 100);
75          nonZeroDiagonalWeights[j, i] = random.Next(ProblemSize * 100);
76        }
77        nonZeroDiagonalDistances[i, i] = random.Next(ProblemSize * 100);
78        nonZeroDiagonalWeights[i, i] = random.Next(ProblemSize * 100);
79      }
80      int index = random.Next(ProblemSize);
81      if (nonZeroDiagonalDistances[index, index] == 0)
82        nonZeroDiagonalDistances[index, index] = random.Next(1, ProblemSize * 100);
83      index = random.Next(ProblemSize);
84      if (nonZeroDiagonalWeights[index, index] == 0)
85        nonZeroDiagonalWeights[index, index] = random.Next(1, ProblemSize * 100);
86      assignment = new Permutation(PermutationTypes.Absolute, ProblemSize, random);
87
88      symmetricProblem = new QuadraticAssignmentProblem();
89      symmetricProblem.Distances = symmetricDistances;
90      symmetricProblem.Weights = symmetricWeights;
91
92      asymmetricProblem = new QuadraticAssignmentProblem();
93      asymmetricProblem.Distances = asymmetricDistances;
94      asymmetricProblem.Weights = asymmetricWeights;
95
96      nonZeroDiagonalProblem = new QuadraticAssignmentProblem();
97      nonZeroDiagonalProblem.Distances = nonZeroDiagonalDistances;
98      nonZeroDiagonalProblem.Weights = nonZeroDiagonalWeights;
99    }
100
101    [TestMethod]
102    [TestCategory("Problems.Assignment")]
103    [TestProperty("Time", "short")]
104    public void Swap2MoveEvaluatorFastEvaluationTest() {
105      for (int i = 0; i < 500; i++) {
106        Swap2Move lastMove = new Swap2Move(random.Next(ProblemSize), random.Next(ProblemSize));
107        Permutation prevAssignment = (Permutation)assignment.Clone();
108        Swap2Manipulator.Apply(assignment, lastMove.Index1, lastMove.Index2);
109        Permutation nextAssignment = (Permutation)assignment.Clone();
110        Swap2Move currentMove = new Swap2Move(random.Next(ProblemSize), random.Next(ProblemSize));
111        Swap2Manipulator.Apply(nextAssignment, currentMove.Index1, currentMove.Index2);
112
113        double moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, symmetricWeights, symmetricDistances);
114        double moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
115                moveBefore, symmetricWeights, symmetricDistances, lastMove);
116        double before = symmetricProblem.Evaluate(assignment, CancellationToken.None);
117        double after = symmetricProblem.Evaluate(nextAssignment, CancellationToken.None);
118
119        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on symmetric matrices: " + Environment.NewLine
120          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
121
122        moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, asymmetricWeights, asymmetricDistances);
123        moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
124                moveBefore, asymmetricWeights, asymmetricDistances, lastMove);
125        before = asymmetricProblem.Evaluate(assignment, CancellationToken.None);
126        after = asymmetricProblem.Evaluate(nextAssignment, CancellationToken.None);
127
128        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on asymmetric matrices: " + Environment.NewLine
129          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
130
131        moveBefore = QAPSwap2MoveEvaluator.Apply(prevAssignment, currentMove, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
132        moveAfter = QAPSwap2MoveEvaluator.Apply(assignment, currentMove,
133                moveBefore, nonZeroDiagonalWeights, nonZeroDiagonalDistances, lastMove);
134        before = nonZeroDiagonalProblem.Evaluate(assignment, CancellationToken.None);
135        after = nonZeroDiagonalProblem.Evaluate(nextAssignment, CancellationToken.None);
136
137        Assert.IsTrue(moveAfter.IsAlmost(after - before), "Failed on non-zero diagonal matrices: " + Environment.NewLine
138          + "Quality changed from " + before + " to " + after + " (" + (after - before).ToString() + "), but move quality change was " + moveAfter + ".");
139      }
140    }
141
142    [TestMethod]
143    [TestCategory("Problems.Assignment")]
144    [TestProperty("Time", "short")]
145    public void Swap2MoveEvaluatorTest() {
146
147      for (int i = 0; i < 500; i++) {
148        int index1 = random.Next(ProblemSize);
149        int index2 = random.Next(ProblemSize);
150
151        // SYMMETRIC MATRICES
152        double before = symmetricProblem.Evaluate(assignment, CancellationToken.None);
153        Swap2Manipulator.Apply(assignment, index1, index2);
154        double after = symmetricProblem.Evaluate(assignment, CancellationToken.None);
155        double move = QAPSwap2MoveEvaluator.Apply(assignment, new Swap2Move(index1, index2, assignment), symmetricWeights, symmetricDistances);
156        Assert.IsTrue(move.IsAlmost(before - after), "Failed on symmetric matrices");
157
158        // ASYMMETRIC MATRICES
159        before = asymmetricProblem.Evaluate(assignment, CancellationToken.None);
160        Permutation clone = (Permutation)assignment.Clone();
161        Swap2Manipulator.Apply(assignment, index1, index2);
162        after = asymmetricProblem.Evaluate(assignment, CancellationToken.None);
163        move = QAPSwap2MoveEvaluator.Apply(clone, new Swap2Move(index1, index2), asymmetricWeights, asymmetricDistances);
164        Assert.IsTrue(move.IsAlmost(after - before), "Failed on asymmetric matrices");
165
166        // NON-ZERO DIAGONAL ASSYMETRIC MATRICES
167        before = nonZeroDiagonalProblem.Evaluate(assignment, CancellationToken.None);
168        clone = (Permutation)assignment.Clone();
169        Swap2Manipulator.Apply(assignment, index1, index2);
170        after = nonZeroDiagonalProblem.Evaluate(assignment, CancellationToken.None);
171        move = QAPSwap2MoveEvaluator.Apply(clone, new Swap2Move(index1, index2), nonZeroDiagonalWeights, nonZeroDiagonalDistances);
172        Assert.IsTrue(move.IsAlmost(after - before), "Failed on non-zero diagonal matrices");
173      }
174    }
175
176    [TestMethod]
177    [TestCategory("Problems.Assignment")]
178    [TestProperty("Time", "short")]
179    public void InversionMoveEvaluatorTest() {
180      for (int i = 0; i < 500; i++) {
181        int index1 = random.Next(ProblemSize);
182        int index2 = random.Next(ProblemSize);
183        if (index1 > index2) { int h = index1; index1 = index2; index2 = h; }
184
185        // SYMMETRIC MATRICES
186        double before = symmetricProblem.Evaluate(assignment, CancellationToken.None);
187        InversionManipulator.Apply(assignment, Math.Min(index1, index2), Math.Max(index1, index2));
188        double after = symmetricProblem.Evaluate(assignment, CancellationToken.None);
189        double move = QAPInversionMoveEvaluator.Apply(assignment, new InversionMove(index1, index2, assignment), symmetricWeights, symmetricDistances);
190        Assert.IsTrue(move.IsAlmost(before - after), "Failed on symmetric matrices");
191
192        // ASYMMETRIC MATRICES
193        before = asymmetricProblem.Evaluate(assignment, CancellationToken.None);
194        Permutation clone = (Permutation)assignment.Clone();
195        InversionManipulator.Apply(assignment, index1, index2);
196        after = asymmetricProblem.Evaluate(assignment, CancellationToken.None);
197        move = QAPInversionMoveEvaluator.Apply(clone, new InversionMove(index1, index2), asymmetricWeights, asymmetricDistances);
198        Assert.IsTrue(move.IsAlmost(after - before), "Failed on asymmetric matrices");
199
200        // NON-ZERO DIAGONAL ASYMMETRIC MATRICES
201        before = nonZeroDiagonalProblem.Evaluate(assignment, CancellationToken.None);
202        clone = (Permutation)assignment.Clone();
203        InversionManipulator.Apply(assignment, index1, index2);
204        after = nonZeroDiagonalProblem.Evaluate(assignment, CancellationToken.None);
205        move = QAPInversionMoveEvaluator.Apply(clone, new InversionMove(index1, index2), nonZeroDiagonalWeights, nonZeroDiagonalDistances);
206        Assert.IsTrue(move.IsAlmost(after - before), "Failed on non-zero diagonal matrices");
207      }
208    }
209
210    [TestMethod]
211    [TestCategory("Problems.Assignment")]
212    [TestProperty("Time", "short")]
213    public void TranslocationMoveEvaluatorTest() {
214      for (int i = 0; i < 500; i++) {
215        int index1 = random.Next(assignment.Length - 1);
216        int index2 = random.Next(index1 + 1, assignment.Length);
217        int insertPointLimit = assignment.Length - index2 + index1 - 1;  // get insertion point in remaining part
218        int insertPoint;
219        if (insertPointLimit > 0)
220          insertPoint = random.Next(insertPointLimit);
221        else
222          insertPoint = 0;
223
224        // SYMMETRIC MATRICES
225        double before = symmetricProblem.Evaluate(assignment, CancellationToken.None);
226        Permutation clone = new Cloner().Clone(assignment);
227        TranslocationManipulator.Apply(assignment, index1, index2, insertPoint);
228        double after = symmetricProblem.Evaluate(assignment, CancellationToken.None);
229        double move = QAPTranslocationMoveEvaluator.Apply(clone, new TranslocationMove(index1, index2, insertPoint, assignment), symmetricWeights, symmetricDistances);
230        Assert.IsTrue(move.IsAlmost(after - before), "Failed on symmetric matrices");
231
232        // ASYMMETRIC MATRICES
233        before = asymmetricProblem.Evaluate(assignment, CancellationToken.None);
234        clone = new Cloner().Clone(assignment);
235        TranslocationManipulator.Apply(assignment, index1, index2, insertPoint);
236        after = asymmetricProblem.Evaluate(assignment, CancellationToken.None);
237        move = QAPTranslocationMoveEvaluator.Apply(clone, new TranslocationMove(index1, index2, insertPoint, assignment), asymmetricWeights, asymmetricDistances);
238        Assert.IsTrue(move.IsAlmost(after - before), "Failed on asymmetric matrices");
239
240        // NON-ZERO DIAGONAL ASYMMETRIC MATRICES
241        before = nonZeroDiagonalProblem.Evaluate(assignment, CancellationToken.None);
242        clone = new Cloner().Clone(assignment);
243        TranslocationManipulator.Apply(assignment, index1, index2, insertPoint);
244        after = nonZeroDiagonalProblem.Evaluate(assignment, CancellationToken.None);
245        move = QAPTranslocationMoveEvaluator.Apply(clone, new TranslocationMove(index1, index2, insertPoint, assignment), nonZeroDiagonalWeights, nonZeroDiagonalDistances);
246        Assert.IsTrue(move.IsAlmost(after - before), "Failed on non-zero diagonal matrices");
247      }
248    }
249
250    [TestMethod]
251    [TestCategory("Problems.Assignment")]
252    [TestProperty("Time", "short")]
253    public void ScrambleMoveEvaluatorTest() {
254      for (int i = 0; i < 500; i++) {
255        ScrambleMove scramble = StochasticScrambleMultiMoveGenerator.GenerateRandomMove(assignment, random);
256
257        // SYMMETRIC MATRICES
258        double before = symmetricProblem.Evaluate(assignment, CancellationToken.None);
259        double move = QAPScrambleMoveEvaluator.Apply(assignment, scramble, symmetricWeights, symmetricDistances);
260        ScrambleManipulator.Apply(assignment, scramble.StartIndex, scramble.ScrambledIndices);
261        double after = symmetricProblem.Evaluate(assignment, CancellationToken.None);
262        Assert.IsTrue(move.IsAlmost(after - before), "Failed on symmetric matrices");
263
264        // ASYMMETRIC MATRICES
265        before = asymmetricProblem.Evaluate(assignment, CancellationToken.None);
266        move = QAPScrambleMoveEvaluator.Apply(assignment, scramble, asymmetricWeights, asymmetricDistances);
267        ScrambleManipulator.Apply(assignment, scramble.StartIndex, scramble.ScrambledIndices);
268        after = asymmetricProblem.Evaluate(assignment, CancellationToken.None);
269        Assert.IsTrue(move.IsAlmost(after - before), "Failed on asymmetric matrices");
270
271        // NON-ZERO DIAGONAL ASYMMETRIC MATRICES
272        before = nonZeroDiagonalProblem.Evaluate(assignment, CancellationToken.None);
273        move = QAPScrambleMoveEvaluator.Apply(assignment, scramble, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
274        ScrambleManipulator.Apply(assignment, scramble.StartIndex, scramble.ScrambledIndices);
275        after = nonZeroDiagonalProblem.Evaluate(assignment, CancellationToken.None);
276        Assert.IsTrue(move.IsAlmost(after - before), "Failed on non-zero diagonal matrices");
277      }
278    }
279
280  }
281}
Note: See TracBrowser for help on using the repository browser.