Free cookie consent management tool by TermsFeed Policy Generator

source: stable/HeuristicLab.Tests/HeuristicLab.Problems.QuadraticAssignment-3.3/QAPMoveEvaluatorTest.cs @ 11606

Last change on this file since 11606 was 11170, checked in by ascheibe, 10 years ago

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