Changeset 6648


Ignore:
Timestamp:
08/09/11 18:46:09 (11 years ago)
Author:
abeham
Message:

#1617

  • added scramble moves
  • added a scramble move evaluator for the QAP
  • added a unit test for the move evaluator
Location:
trunk/sources
Files:
7 added
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/HeuristicLab.Encodings.PermutationEncoding-3.3.csproj

    r6342 r6648  
    120120    <Compile Include="Crossovers\UniformLikeCrossover.cs" />
    121121    <Compile Include="HeuristicLabEncodingsPermutationEncodingPlugin.cs" />
     122    <Compile Include="Interfaces\IPermutationScrambleMoveOperator.cs" />
    122123    <Compile Include="Interfaces\IPermutationMultiNeighborhoodShakingOperator.cs" />
    123124    <Compile Include="Interfaces\IPermutationSwap2MoveOperator.cs" />
     
    139140    <Compile Include="Moves\Edge.cs" />
    140141    <Compile Include="Moves\PermutationMoveAttribute.cs" />
     142    <Compile Include="Moves\Scramble\StochasticScrambleMultiMoveGenerator.cs" />
     143    <Compile Include="Moves\Scramble\ScrambleMove.cs" />
     144    <Compile Include="Moves\Scramble\ScrambleMoveGenerator.cs" />
     145    <Compile Include="Moves\Scramble\ScrambleMoveMaker.cs" />
    141146    <Compile Include="Moves\StandardEdgeEqualityComparer.cs" />
    142147    <Compile Include="Moves\Swap2\ExhaustiveSwap2MoveGenerator.cs" />
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Manipulators/ScrambleManipulator.cs

    r5445 r6648  
    5050    /// <param name="permutation">The permutation to manipulate.</param>
    5151    public static void Apply(IRandom random, Permutation permutation) {
    52       Permutation original = (Permutation)permutation.Clone();
    53 
    5452      int breakPoint1, breakPoint2;
    5553      int[] scrambledIndices, remainingIndices, temp;
    5654      int selectedIndex, index;
    5755
    58       breakPoint1 = random.Next(original.Length - 1);
    59       breakPoint2 = random.Next(breakPoint1 + 1, original.Length);
     56      breakPoint1 = random.Next(permutation.Length - 1);
     57      breakPoint2 = random.Next(breakPoint1 + 1, permutation.Length);
    6058
    6159      scrambledIndices = new int[breakPoint2 - breakPoint1 + 1];
     
    8078      }
    8179
    82       for (int i = 0; i <= (breakPoint2 - breakPoint1); i++) {  // scramble permutation between breakpoints
    83         permutation[breakPoint1 + i] = original[breakPoint1 + scrambledIndices[i]];
     80      Apply(permutation, breakPoint1, scrambledIndices);
     81    }
     82
     83    public static void Apply(Permutation permutation, int startIndex, int[] scrambleArray) {
     84      Permutation original = (Permutation)permutation.Clone();
     85      for (int i = 0; i < scrambleArray.Length; i++) {  // scramble permutation between breakpoints
     86        permutation[startIndex + i] = original[startIndex + scrambleArray[i]];
    8487      }
    8588    }
  • trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/HeuristicLab.Problems.QuadraticAssignment-3.3.csproj

    r6628 r6648  
    111111    <Compile Include="Analyzers\QAPAlleleFrequencyAnalyzer.cs" />
    112112    <Compile Include="Analyzers\QAPPopulationDiversityAnalyzer.cs" />
     113    <Compile Include="Evaluators\QAPScrambleMoveEvaluator.cs" />
    113114    <Compile Include="Evaluators\QAPSwap2MoveEvaluator.cs" />
    114115    <Compile Include="Evaluators\QAPEvaluator.cs" />
  • trunk/sources/HeuristicLab.Problems.QuadraticAssignment/3.3/Tests/QAPMoveEvaluatorTest.cs

    r6628 r6648  
    226226    }
    227227
     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        Permutation clone = new Cloner().Clone(assignment);
     236        ScrambleManipulator.Apply(assignment, scramble.StartIndex, scramble.ScrambledIndices);
     237        double after = QAPEvaluator.Apply(assignment, symmetricWeights, symmetricDistances);
     238        double move = QAPScrambleMoveEvaluator.Apply(clone, scramble, symmetricWeights, symmetricDistances);
     239        Assert.IsTrue(move.IsAlmost(after - before), "Failed on symmetric matrices");
     240
     241        // ASYMMETRIC MATRICES
     242        before = QAPEvaluator.Apply(assignment, asymmetricWeights, asymmetricDistances);
     243        clone = new Cloner().Clone(assignment);
     244        ScrambleManipulator.Apply(assignment, scramble.StartIndex, scramble.ScrambledIndices);
     245        after = QAPEvaluator.Apply(assignment, asymmetricWeights, asymmetricDistances);
     246        move = QAPScrambleMoveEvaluator.Apply(clone, scramble, asymmetricWeights, asymmetricDistances);
     247        Assert.IsTrue(move.IsAlmost(after - before), "Failed on asymmetric matrices");
     248
     249        // NON-ZERO DIAGONAL ASYMMETRIC MATRICES
     250        before = QAPEvaluator.Apply(assignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     251        clone = new Cloner().Clone(assignment);
     252        ScrambleManipulator.Apply(assignment, scramble.StartIndex, scramble.ScrambledIndices);
     253        after = QAPEvaluator.Apply(assignment, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     254        move = QAPScrambleMoveEvaluator.Apply(clone, scramble, nonZeroDiagonalWeights, nonZeroDiagonalDistances);
     255        Assert.IsTrue(move.IsAlmost(after - before), "Failed on non-zero diagonal matrices");
     256      }
     257    }
     258
    228259  }
    229260}
Note: See TracChangeset for help on using the changeset viewer.