Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HivePerformance/sources/HeuristicLab.Tests/HeuristicLab.Problems.QuadraticAssignment-3.3/QAPMoveEvaluatorTest.cs @ 9596

Last change on this file since 9596 was 9539, checked in by ascheibe, 12 years ago

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