Free cookie consent management tool by TermsFeed Policy Generator

Changeset 14662


Ignore:
Timestamp:
02/11/17 00:27:04 (8 years ago)
Author:
abeham
Message:

#2731: Added better performing manipulation methods to Permutation and adapted the manipulators to use them

  • Added unit tests
Location:
trunk/sources
Files:
1 added
8 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Manipulators/InsertionManipulator.cs

    r14185 r14662  
    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       int cutIndex, insertIndex, number;
     52      var cutIndex = random.Next(permutation.Length);
     53      var insertIndex = random.Next(permutation.Length);
    5454
    55       cutIndex = random.Next(original.Length);
    56       insertIndex = random.Next(original.Length);
    57       number = original[cutIndex];
     55      if (cutIndex == insertIndex) return;
    5856
    59       int i = 0;  // index in new permutation
    60       int j = 0;  // index in old permutation
    61       while (i < original.Length) {
    62         if (j == cutIndex) {
    63           j++;
    64         }
    65         if (i == insertIndex) {
    66           permutation[i] = number;
    67           i++;
    68         }
    69         if ((i < original.Length) && (j < original.Length)) {
    70           permutation[i] = original[j];
    71           i++;
    72           j++;
    73         }
    74       }
     57      permutation.Move(cutIndex, cutIndex, insertIndex);
    7558    }
    7659
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Manipulators/InversionManipulator.cs

    r14185 r14662  
    6060
    6161    public static void Apply(Permutation permutation, int breakPoint1, int breakPoint2) {
    62       for (int i = 0; i <= (breakPoint2 - breakPoint1) / 2; i++) {  // invert permutation between breakpoints
    63         int temp = permutation[breakPoint1 + i];
    64         permutation[breakPoint1 + i] = permutation[breakPoint2 - i];
    65         permutation[breakPoint2 - i] = temp;
    66       }
     62      permutation.Reverse(breakPoint1, breakPoint2 - breakPoint1 + 1);
    6763    }
    6864
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Manipulators/ScrambleManipulator.cs

    r14185 r14662  
    2020#endregion
    2121
     22using System.Linq;
    2223using HeuristicLab.Common;
    2324using HeuristicLab.Core;
     
    5758      breakPoint2 = random.Next(breakPoint1 + 1, permutation.Length);
    5859
     60      // TODO: Use Fisher-Yates-Shuffle rather than complicated code below
     61      // scrambledIndices = Enumerable.Range(0, breakPoint2 - breakPoint1 + 1).Shuffle(random).ToArray();
     62      // Also, it would be more memory-efficient to change here and Apply(Permutation, int, int[]) below to interpret scrambleArray as values, not indices
     63      // Don't forget the move generator
     64      // BackwardsCompatibility3.3
     65      #region This whole code should be replaced by above line when going for 3.4
    5966      scrambledIndices = new int[breakPoint2 - breakPoint1 + 1];
    6067      remainingIndices = new int[breakPoint2 - breakPoint1 + 1];
     
    7784        }
    7885      }
     86      #endregion
    7987
    8088      Apply(permutation, breakPoint1, scrambledIndices);
     
    8290
    8391    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]];
    87       }
     92      permutation.Replace(startIndex, scrambleArray.Select(x => permutation[startIndex + x]).ToArray());
    8893    }
    8994
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Manipulators/Swap2Manipulator.cs

    r14185 r14662  
    5858
    5959    public static void Apply(Permutation permutation, int index1, int index2) {
    60       int temp = permutation[index1];
    61       permutation[index1] = permutation[index2];
    62       permutation[index2] = temp;
     60      permutation.Swap(index1, index2);
    6361    }
    6462
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Manipulators/Swap3Manipulator.cs

    r14185 r14662  
    5757    public static void Apply(IRandom random, Permutation permutation) {
    5858      if (permutation.Length < 3) throw new ArgumentException("Swap3Manipulator: The permutation must be at least of size 3.", "permutation");
    59       int index1, index2, index3, temp;
     59      int index1, index2, index3;
    6060
    6161      do {
     
    6565      } while (index1 == index2 || index2 == index3 || index1 == index3);
    6666
    67       // swap positions 1 and 2
    68       temp = permutation[index1];
    69       permutation[index1] = permutation[index2];
    70       permutation[index2] = temp;
    71       // swap positions 2 and 3
    72       temp = permutation[index2];
    73       permutation[index2] = permutation[index3];
    74       permutation[index3] = temp;
     67      permutation.Swap(index1, index2);
     68      permutation.Swap(index2, index3);
    7569    }
    7670
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Manipulators/TranslocationManipulator.cs

    r14185 r14662  
    6565
    6666    public static void Apply(Permutation permutation, int breakPoint1, int breakPoint2, int insertPoint) {
    67       Permutation original = (Permutation)permutation.Clone();
    68 
    69       int i = 0;  // index in new permutation
    70       int j = 0;  // index in old permutation
    71       while (i < original.Length) {
    72         if (i == insertPoint) {  // copy translocated area
    73           for (int k = breakPoint1; k <= breakPoint2; k++) {
    74             permutation[i] = original[k];
    75             i++;
    76           }
    77         }
    78         if (j == breakPoint1) {  // skip area between breakpoints
    79           j = breakPoint2 + 1;
    80         }
    81         if ((i < original.Length) && (j < original.Length)) {
    82           permutation[i] = original[j];
    83           i++;
    84           j++;
    85         }
    86       }
     67      permutation.Move(breakPoint1, breakPoint2, insertPoint);
    8768    }
    8869
  • trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Permutation.cs

    r14185 r14662  
    121121    }
    122122
     123    public virtual void Swap(int i, int j) {
     124      var h = array[i];
     125      array[i] = array[j];
     126      array[j] = h;
     127      OnReset();
     128    }
     129
     130    public virtual void Reverse(int startIndex, int length) {
     131      Array.Reverse(array, startIndex, length);
     132      if (length > 1) OnReset();
     133    }
     134
     135    public virtual void Move(int startIndex, int endIndex, int insertIndex) {
     136      if (insertIndex == startIndex) return;
     137      if (insertIndex > startIndex && insertIndex <= endIndex) {
     138        var start = endIndex + 1;
     139        var end = endIndex + insertIndex - startIndex;
     140        insertIndex = startIndex;
     141        startIndex = start;
     142        endIndex = end;
     143      }
     144      var original = (int[])array.Clone();
     145      Array.Copy(original, startIndex, array, insertIndex, endIndex - startIndex + 1);
     146      if (insertIndex > endIndex)
     147        Array.Copy(original, endIndex + 1, array, startIndex, insertIndex - startIndex);
     148      else Array.Copy(original, insertIndex, array, insertIndex + endIndex - startIndex + 1, startIndex - insertIndex);
     149      OnReset();
     150    }
     151
     152    public virtual void Replace(int startIndex, int[] replacement) {
     153      Array.Copy(replacement, 0, array, startIndex, replacement.Length);
     154      OnReset();
     155    }
     156
    123157    public event EventHandler PermutationTypeChanged;
    124158
  • trunk/sources/HeuristicLab.Tests/HeuristicLab.Tests.csproj

    r14479 r14662  
    532532    <Compile Include="HeuristicLab.Encodings.PermutationEncoding-3.3\TranslocationManipulatorTest.cs" />
    533533    <Compile Include="HeuristicLab.Encodings.PermutationEncoding-3.3\UniformLikeCrossoverTest.cs" />
     534    <Compile Include="HeuristicLab.Encodings.PermutationEncoding-3.3\PermutationManipulationTest.cs" />
    534535    <Compile Include="HeuristicLab.Encodings.RealVectorEncoding-3.3\Auxiliary.cs" />
    535536    <Compile Include="HeuristicLab.Encodings.RealVectorEncoding-3.3\BlendAlphaBetaCrossoverTest.cs" />
Note: See TracChangeset for help on using the changeset viewer.