Changeset 8322 for branches/ScatterSearch (trunk integration)

Timestamp:

07/25/12 10:14:58 (12 years ago)

Author:

jkarder

Message:

#1331:

• applied some of the changes suggested by ascheibe in comment:32:ticket:1331
• minor code improvements

Location:

branches/ScatterSearch (trunk integration)

Files:

• HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPoolUpdateMethod.cs (modified) (3 diffs)
• HeuristicLab.Optimization.Operators/3.3/SingleObjectiveSolutionSimilarityCalculator.cs (modified) (2 diffs)
• HeuristicLab.Optimization.Operators/3.3/SolutionSimilarityCalculator.cs (modified) (2 diffs)
• HeuristicLab.Optimization/3.3/Interfaces/ISingleObjectiveSolutionSimilarityCalculator.cs (modified) (1 diff)
• HeuristicLab.Optimization/3.3/Interfaces/ISolutionSimilarityCalculator.cs (modified) (2 diffs)
• HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.TestFunctions/3.3/Improvers/SingleObjectiveTestFunctionImprovementOperator.cs (modified) (1 diff)
• HeuristicLab.Problems.TestFunctions/3.3/PathRelinkers/SingleObjectiveTestFunctionPathRelinker.cs (modified) (1 diff)
• HeuristicLab.Problems.TestFunctions/3.3/SingleObjectiveTestFunctionProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.TravelingSalesman/3.3/PathRelinkers/TSPMultipleGuidesPathRelinker.cs (modified) (1 diff)
• HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs (modified) (1 diff)
• HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs (modified) (1 diff)
• HeuristicLab.Problems.VehicleRouting/3.3/VehicleRoutingProblem.cs (modified) (1 diff)

branches/ScatterSearch (trunk integration)/HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPoolUpdateMethod.cs

@@ -21 +21 @@
 
 using System;
-using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -129 +128 @@
       if (orderedOffspring.Any(hasBetterQuality)) {
         // produce the set union
-        var union = orderedParents.Union(orderedOffspring.Where(hasBetterQuality), new SolutionEqualityComparer<IScope>(SimilarityCalculator.CalculateSolutionSimilarity));
+        var union = orderedParents.Union(orderedOffspring.Where(hasBetterQuality), SimilarityCalculator);
         if (union.Count() > orderedParents.Count()) {
           var orderedUnion = Maximization.Value ? union.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value) :
@@ -140 +139 @@
       return base.Apply();
     }
-
-    // derive SingleObjectiveSolutionSimilarityCalculator from EqualityComparer
-    // delete this ...
-    public class SolutionEqualityComparer<T> : EqualityComparer<T> {
-      private readonly Func<T, T, double> similarityCalculator;
-
-      public SolutionEqualityComparer(Func<T, T, double> similarityCalculator) {
-        this.similarityCalculator = similarityCalculator;
-      }
-
-      public override bool Equals(T x, T y) {
-        if (object.ReferenceEquals(x, y)) return true;
-        if (x == null || y == null) return false;
-        return similarityCalculator(x, y) == 1.0;
-      }
-
-      public override int GetHashCode(T obj) {
-        return 0; // return the same hash code for each object, otherwise Equals will not be called
-      }
-    }
   }
 }

branches/ScatterSearch (trunk integration)/HeuristicLab.Optimization.Operators/3.3/SingleObjectiveSolutionSimilarityCalculator.cs

@@ -34 +34 @@
     #region Properties
     [Storable]
+    public string SolutionVariableName { get; set; }
+    [Storable]
     public string QualityVariableName { get; set; }
-    [Storable]
-    public string SolutionVariableName { get; set; }
     #endregion
 
@@ -43 +43 @@
     protected SingleObjectiveSolutionSimilarityCalculator(SingleObjectiveSolutionSimilarityCalculator original, Cloner cloner)
       : base(original, cloner) {
-      if (original.QualityVariableName != null)
-        this.QualityVariableName = (string)original.QualityVariableName.Clone();
+      this.SolutionVariableName = original.SolutionVariableName;
+      this.QualityVariableName = original.QualityVariableName;
     }
     protected SingleObjectiveSolutionSimilarityCalculator() : base() { }
 
     public override int GetHashCode(IScope scope) {
-      var quality = ((DoubleValue)scope.Variables[QualityVariableName].Value).Value;
-      return quality.ToString().GetHashCode();
+      return ((DoubleValue)scope.Variables[QualityVariableName].Value).Value.GetHashCode();
     }
   }

branches/ScatterSearch (trunk integration)/HeuristicLab.Optimization.Operators/3.3/SolutionSimilarityCalculator.cs

@@ -21 +21 @@
 
 using System;
-using System.Collections.Generic;
 using System.Linq;
 using HeuristicLab.Common;
@@ -33 +32 @@
   [Item("SimilarityCalculator", "A base class for items that perform similarity calculation between two solutions.")]
   [StorableClass]
-  public abstract class SolutionSimilarityCalculator : Item, ISolutionSimilarityCalculator, IEqualityComparer<IScope> {
+  public abstract class SolutionSimilarityCalculator : Item, ISolutionSimilarityCalculator {
     [StorableConstructor]
     protected SolutionSimilarityCalculator(bool deserializing) : base(deserializing) { }

branches/ScatterSearch (trunk integration)/HeuristicLab.Optimization/3.3/Interfaces/ISingleObjectiveSolutionSimilarityCalculator.cs

@@ -25 +25 @@
   /// </summary>
   public interface ISingleObjectiveSolutionSimilarityCalculator : ISolutionSimilarityCalculator {
+    string SolutionVariableName { get; set; }
     string QualityVariableName { get; set; }
-    string SolutionVariableName { get; set; }
   }
 }

branches/ScatterSearch (trunk integration)/HeuristicLab.Optimization/3.3/Interfaces/ISolutionSimilarityCalculator.cs

@@ -20 +20 @@
 #endregion
 
+using System.Collections.Generic;
 using HeuristicLab.Core;
 
@@ -26 +27 @@
   /// An interface which represents an operator for similarity calculation.
   /// </summary>
-  public interface ISolutionSimilarityCalculator : IItem {
+  public interface ISolutionSimilarityCalculator : IItem, IEqualityComparer<IScope> {
     /// <summary>
     /// Calculates the similarity of two solutions.

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.Knapsack/3.3/KnapsackProblem.cs

@@ -305 +305 @@
       foreach (KnapsackSimilarityCalculator op in Operators.OfType<KnapsackSimilarityCalculator>()) {
         op.SolutionVariableName = SolutionCreator.BinaryVectorParameter.ActualName;
+        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
       }
     }

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TestFunctions/3.3/Improvers/SingleObjectiveTestFunctionImprovementOperator.cs

@@ -36 +36 @@
   /// </summary>
   /// <remarks>
-  /// It is implemented as described in Gao, F. and Han, L. (2010). Implementing the Nelder-Mead simplex algorithm with adaptive parameters. Computational Optimization and Applications, Vol. 51. Springer.<br />
-  /// The operator is an implementation of the Nelder-Mead method and conducts relection, expansion, contraction and reduction on the test functions solution.
+  /// It is implemented as described in Laguna, M. and Martí, R. (2003). Scatter Search: Methodology and Implementations in C. Operations Research/Computer Science Interfaces Series, Vol. 24. Springer.<br />
+  /// The operator uses an implementation of the Nelder-Mead method with adaptive parameters as described in Gao, F. and Han, L. (2010). Implementing the Nelder-Mead simplex algorithm with adaptive parameters. Computational Optimization and Applications, Vol. 51. Springer. and conducts relection, expansion, contraction and reduction on the test functions solution.
   /// </remarks>
   [Item("SingleObjectiveTestFunctionImprovementOperator", "An operator that improves test functions solutions.")]

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TestFunctions/3.3/PathRelinkers/SingleObjectiveTestFunctionPathRelinker.cs

@@ -36 +36 @@
   /// </summary>
   /// <remarks>
-  /// TODO: add reference and remarks
+  /// It is implemented as described in Duarte, A., Martí, R., and Gortazar, F. (2011). Path Relinking for Large Scale Global Optimization. Soft Computing, Vol. 15.
+  /// The operator incrementally assimilates the initiating solution into the guiding solution by adapting the solution vector's elements.
   /// </remarks>
   [Item("SingleObjectiveTestFunctionPathRelinker", "An operator that relinks paths between test functions solutions.")]

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TestFunctions/3.3/SingleObjectiveTestFunctionProblem.cs

@@ -377 +377 @@
       foreach (SingleObjectiveTestFunctionSimilarityCalculator op in Operators.OfType<SingleObjectiveTestFunctionSimilarityCalculator>()) {
         op.SolutionVariableName = SolutionCreator.RealVectorParameter.ActualName;
+        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
         op.Bounds = Bounds;
       }

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/PathRelinkers/TSPMultipleGuidesPathRelinker.cs

@@ -85 +85 @@
         int bestCityIndex = (i + 1) % v1.Length;
         double currDistance = distances[v1[currCityIndex], v1[bestCityIndex]];
+        // check each guiding solution
         targets.ToList().ForEach(solution => {
-          var node = solution.Select((x, index) => new { Id = x, Index = index }).First(x => x.Id == v1[currCityIndex]);
+          // locate current city
+          var node = solution.Select((x, index) => new { Id = x, Index = index }).Single(x => x.Id == v1[currCityIndex]);
           int pred = solution[(node.Index - 1 + solution.Length) % solution.Length];
           int succ = solution[(node.Index + 1) % solution.Length];
+          // get distances to neighbors
           var results = new[] { pred, succ }.Select(x => new { Id = x, Distance = distances[x, node.Id] });
-          if (results.Any(x => x.Distance < currDistance)) {
-            var bestCity = results.OrderBy(x => x.Distance).First();
-            bestCityIndex = v1.Select((x, index) => new { Id = x, Index = index }).First(x => x.Id == bestCity.Id).Index;
+          var bestCity = results.Where(x => x.Distance < currDistance).OrderBy(x => x.Distance).FirstOrDefault();
+          if (bestCity != null) {
+            bestCityIndex = v1.Select((x, index) => new { Id = x, Index = index }).Single(x => x.Id == bestCity.Id).Index;
             currDistance = bestCity.Distance;
           }

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/SimilarityCalculators/TSPSimilarityCalculator.cs

@@ -67 +67 @@
     private static double CalculateAbsolute(Permutation left, Permutation right) {
       double similarity = 0.0;
-      for (int i = 0; i < left.Length && left[i] == right[i]; similarity = ++i) ;
+      for (int i = 0; i < left.Length; i++)
+        if (left[i] == right[i]) similarity++;
+
       return similarity / left.Length;
     }
 
     private static double CalculateRelativeDirected(Permutation left, Permutation right) {
-      throw new NotImplementedException();
+      int[] edges = new int[right.Length];
+      for (int i = 0; i < right.Length; i++)
+        edges[right[i]] = right[(i + 1) % right.Length];
+
+      double similarity = 0.0;
+      for (int i = 0; i < left.Length; i++)
+        if (left[(i + 1) % left.Length] == edges[left[i]]) similarity++;
+
+      return similarity / left.Length;
     }
 

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.TravelingSalesman/3.3/TravelingSalesmanProblem.cs

@@ -352 +352 @@
       foreach (TSPSimilarityCalculator op in Operators.OfType<TSPSimilarityCalculator>()) {
         op.SolutionVariableName = SolutionCreator.PermutationParameter.ActualName;
+        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
       }
     }

branches/ScatterSearch (trunk integration)/HeuristicLab.Problems.VehicleRouting/3.3/VehicleRoutingProblem.cs

@@ -531 +531 @@
       foreach (VRPSimilarityCalculator op in Operators.OfType<VRPSimilarityCalculator>()) {
         op.SolutionVariableName = SolutionCreator.VRPToursParameter.ActualName;
+        op.QualityVariableName = Evaluator.QualityParameter.ActualName;
       }
     }