Free cookie consent management tool by TermsFeed Policy Generator

source: branches/ScopedAlgorithms/HeuristicLab.Tests/HeuristicLab.Problems.QuadraticAssignment-3.3/QAPMoveEvaluatorTest.cs @ 15557

Last change on this file since 15557 was 13408, checked in by mkommend, 9 years ago

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