Free cookie consent management tool by TermsFeed Policy Generator

source: branches/QAP/HeuristicLab.Problems.QuadraticAssignment/3.3/Tests/QAPMoveEvaluatorTest.cs @ 5801

Last change on this file since 5801 was 5801, checked in by abeham, 14 years ago

#1330

  • Added QAP evaluator for translocation moves
File size: 6.5 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
37    private TestContext testContextInstance;
38    /// <summary>
39    ///Gets or sets the test context which provides
40    ///information about and functionality for the current test run.
41    ///</summary>
42    public TestContext TestContext {
43      get { return testContextInstance; }
44      set { testContextInstance = value; }
45    }
46
47    #region Additional test attributes
48    //
49    //You can use the following additional attributes as you write your tests:
50    //
51    //Use ClassInitialize to run code before running the first test in the class
52    //[ClassInitialize()]
53    //public static void MyClassInitialize(TestContext testContext)
54    //{
55    //}
56    //
57    //Use ClassCleanup to run code after all tests in a class have run
58    //[ClassCleanup()]
59    //public static void MyClassCleanup()
60    //{
61    //}
62    //
63    //Use TestInitialize to run code before running each test
64    //[TestInitialize()]
65    //public void MyTestInitialize()
66    //{
67    //}
68    //
69    //Use TestCleanup to run code after each test has run
70    //[TestCleanup()]
71    //public void MyTestCleanup()
72    //{
73    //}
74    //
75    #endregion
76
77    [TestMethod]
78    public void SwapMoveEvaluatorTest() {
79      DoubleMatrix distances = new DoubleMatrix(
80        new double[,] { { 0, 1, 2, 3 },
81                        { 1, 0, 3, 4 },
82                        { 2, 3, 0, 5 },
83                        { 3, 4, 5, 0 } });
84      DoubleMatrix weights = new DoubleMatrix(
85        new double[,] { { 0, 1, 0, 0 },
86                        { 1, 0, 2, 0 },
87                        { 0, 2, 0, 1 },
88                        { 0, 0, 1, 0 } });
89      Permutation assignment = new Permutation(PermutationTypes.Absolute,
90        new int[] { 0, 1, 2, 3 });
91      MersenneTwister random = new MersenneTwister();
92      for (int i = 0; i < 500; i++) {
93        int index1 = random.Next(4);
94        int index2 = random.Next(4);
95        double before = QAPEvaluator.Apply(assignment, weights, distances);
96        Swap2Manipulator.Apply(assignment, index1, index2);
97        double after = QAPEvaluator.Apply(assignment, weights, distances);
98        // evaluate swap back
99        double move = QAPSwapMoveEvaluator.Apply(assignment, new SwapMove(index1, index2, assignment), weights, distances);
100        Assert.IsTrue(move.IsAlmost(before - after));
101      }
102    }
103
104    [TestMethod]
105    public void InversionMoveEvaluatorTest() {
106      DoubleMatrix distances = new DoubleMatrix(
107        new double[,] { { 0, 1, 2, 3 },
108                        { 1, 0, 3, 4 },
109                        { 2, 3, 0, 5 },
110                        { 3, 4, 5, 0 } });
111      DoubleMatrix weights = new DoubleMatrix(
112        new double[,] { { 0, 1, 0, 0 },
113                        { 1, 0, 2, 0 },
114                        { 0, 2, 0, 1 },
115                        { 0, 0, 1, 0 } });
116      Permutation assignment = new Permutation(PermutationTypes.Absolute,
117        new int[] { 0, 1, 2, 3 });
118      MersenneTwister random = new MersenneTwister();
119      for (int i = 0; i < 500; i++) {
120        int index1 = random.Next(4);
121        int index2 = random.Next(4);
122        double before = QAPEvaluator.Apply(assignment, weights, distances);
123        // invert
124        InversionManipulator.Apply(assignment, Math.Min(index1, index2), Math.Max(index1, index2));
125        double after = QAPEvaluator.Apply(assignment, weights, distances);
126        // evaluate invert back
127        double move = QAPInversionMoveEvaluator.Apply(assignment, new InversionMove(index1, index2, assignment), weights, distances);
128        Assert.IsTrue(move.IsAlmost(before - after));
129      }
130    }
131
132    [TestMethod]
133    public void TranslocationMoveEvaluatorTest() {
134      DoubleMatrix distances = new DoubleMatrix(
135        new double[,] { { 0, 1, 2, 3 },
136                        { 1, 0, 3, 4 },
137                        { 2, 3, 0, 5 },
138                        { 3, 4, 5, 0 } });
139      DoubleMatrix weights = new DoubleMatrix(
140        new double[,] { { 0, 1, 0, 0 },
141                        { 1, 0, 2, 0 },
142                        { 0, 2, 0, 1 },
143                        { 0, 0, 1, 0 } });
144      Permutation assignment = new Permutation(PermutationTypes.Absolute,
145        new int[] { 0, 1, 2, 3 });
146      MersenneTwister random = new MersenneTwister();
147      for (int i = 0; i < 500; i++) {
148        int index1 = random.Next(assignment.Length - 1);
149        int index2 = random.Next(index1 + 1, assignment.Length);
150        int insertPointLimit = assignment.Length - index2 + index1 - 1;  // get insertion point in remaining part
151        int insertPoint;
152        if (insertPointLimit > 0)
153          insertPoint = random.Next(insertPointLimit);
154        else
155          insertPoint = 0;
156        double before = QAPEvaluator.Apply(assignment, weights, distances);
157        // translocate
158        Permutation clone = new Cloner().Clone(assignment);
159        TranslocationManipulator.Apply(assignment, index1, index2, insertPoint);
160        double after = QAPEvaluator.Apply(assignment, weights, distances);
161        // evaluate translocate move
162        double move = QAPTranslocationMoveEvaluator.Apply(clone, new TranslocationMove(index1, index2, insertPoint, assignment), weights, distances);
163        Assert.IsTrue(move.IsAlmost(after - before));
164      }
165    }
166
167  }
168}
Note: See TracBrowser for help on using the repository browser.