Changeset 6507

Timestamp:

07/04/11 23:15:21 (13 years ago)

Author:

abeham

Message:

#1494

• Made ULX crossover sealed
• PermutationEqualityComparer
  • Now derives from EqualityComparer<Permutation>
  • Fixed the GetHashCode function to return the same hash value when the objects are equal according to the equals function
  • Created a unit test to test this comparer

Location:

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3

Files:

• Crossovers/UniformLikeCrossover.cs (modified) (1 diff)
• PermutationEqualityComparer.cs (modified) (3 diffs)
• Tests/HeuristicLab.Encodings.PermutationEncoding-3.3.Tests.csproj (modified) (1 diff)
• Tests/PermutationEqualityComparerTest.cs (added)

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Crossovers/UniformLikeCrossover.cs

@@ -29 +29 @@
   [Item("UniformLikeCrossover", "The ULX crossover tries to maintain the position in the permutation. It randomly chooses from left to right one of its parents' alleles at each position. Missing entries are then filled randomly later. It is described in Tate, D. M. and Smith, A. E. 1995. A genetic approach to the quadratic assignment problem. Computers & Operations Research, vol. 22, pp. 73-83.")]
   [StorableClass]
-  public class UniformLikeCrossover : PermutationCrossover {
+  public sealed class UniformLikeCrossover : PermutationCrossover {
     [StorableConstructor]
     protected UniformLikeCrossover(bool deserializing) : base(deserializing) { }

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/PermutationEqualityComparer.cs

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
+using System.Linq;
+using System.Text;
 using HeuristicLab.PluginInfrastructure;
 
 namespace HeuristicLab.Encodings.PermutationEncoding {
   [NonDiscoverableType]
-  public class PermutationEqualityComparer : IEqualityComparer<Permutation> {
-    public bool Equals(Permutation x, Permutation y) {
+  public class PermutationEqualityComparer : EqualityComparer<Permutation> {
+    public override bool Equals(Permutation x, Permutation y) {
       if (x.PermutationType != y.PermutationType) return false;
       if (x.Length != y.Length) return false;
@@ -43 +45 @@
 
     private bool EqualsAbsolute(Permutation x, Permutation y) {
-      for (int i = 0; i < x.Length; i++)
-        if (x[i] != y[i]) return false;
-      return true;
+      return x.SequenceEqual(y);
     }
 
@@ -66 +66 @@
     }
 
-    public int GetHashCode(Permutation obj) {
+    public override int GetHashCode(Permutation obj) {
       if (obj == null) return 0;
-      return obj.GetHashCode();
+      return GenerateHashString(obj).GetHashCode();
+    }
+
+    private string GenerateHashString(Permutation p) {
+      StringBuilder sb = new StringBuilder();
+      if (p.PermutationType == PermutationTypes.Absolute) {
+        for (int i = 0; i < p.Length; i++)
+          sb.Append(p[i].ToString() + ";");
+      } else {
+        int i = 0;
+        while (p[i] != 0) i++; // always start at element 0
+        if (p.PermutationType == PermutationTypes.RelativeDirected) {
+          for (int j = 0; j < p.Length; j++)
+            sb.Append(p.GetCircular(i + j).ToString() + ";");
+        } else {
+          bool goLeft = p.GetCircular(i - 1) < p.GetCircular(i + 1); // go in direction of the lowest edge so that the total inversion and its original return the same hash code
+          for (int j = 0; j < p.Length; j++) {
+            if (goLeft) sb.Append(p.GetCircular(i - j).ToString() + ";");
+            else sb.Append(p.GetCircular(i + j).ToString() + ";");
+          }
+        }
+      }
+      return sb.ToString();
     }
   }

trunk/sources/HeuristicLab.Encodings.PermutationEncoding/3.3/Tests/HeuristicLab.Encodings.PermutationEncoding-3.3.Tests.csproj

@@ -112 +112 @@
     <Compile Include="OrderCrossoverTest.cs" />
     <Compile Include="PartiallyMatchedCrossoverTest.cs" />
+    <Compile Include="PermutationEqualityComparerTest.cs" />
     <Compile Include="PositionBasedCrossoverTest.cs" />
     <Compile Include="Properties\AssemblyInfo.cs" />