Changeset 7786 for branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPool2TierUpdateMethod.cs

Timestamp:

05/09/12 12:22:33 (12 years ago)

Author:

jkarder

Message:

#1331:

• fixed bug in path relinking selection
• fixed bug in ScatterSearch.Prepare()
• added custom interface (IImprovementOperator) for Scatter Search specific improvement operators
• switched from diversity calculation to similarity calculation
• separated IPathRelinker from ICrossover
• changed TestFunctionsImprovementOperator to use reflection for evaluating functions
• changed SolutionPoolUpdateMethod to use similarity calculation for solution comparison
• improved TravelingSalesmanImprovementOperator
• improved operator graph
• removed specific operators used to evaluate TestFunctions problems
• removed custom crossover operator (NChildCrossover)
• added parameters and adjusted types
• adjusted event handling
• changed access levels
• minor code improvements

File:

• branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPool2TierUpdateMethod.cs (modified) (7 diffs)

branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPool2TierUpdateMethod.cs

@@ -36 +36 @@
   [Item("SolutionPool2TierUpdateMethod", "An operator that updates the solution pool using a 2-tier strategy.")]
   [StorableClass]
-  public sealed class SolutionPool2TierUpdateMethod : SingleSuccessorOperator, IScatterSearchTargetProcessor {
+  public sealed class SolutionPool2TierUpdateMethod : SingleSuccessorOperator {
     #region Parameter properties
     public ScopeParameter CurrentScopeParameter {
       get { return (ScopeParameter)Parameters["CurrentScope"]; }
     }
-    public IValueLookupParameter<DiversityCalculator> DiversityCalculatorParameter {
-      get { return (IValueLookupParameter<DiversityCalculator>)Parameters["DiversityCalculator"]; }
+    public IValueLookupParameter<SimilarityCalculator> SimilarityCalculatorParameter {
+      get { return (IValueLookupParameter<SimilarityCalculator>)Parameters["SimilarityCalculator"]; }
     }
     public IValueLookupParameter<BoolValue> MaximizationParameter {
@@ -53 +53 @@
       get { return (IValueLookupParameter<IntValue>)Parameters["NumberOfHighQualitySolutions"]; }
     }
+    public IValueLookupParameter<IItem> QualityParameter {
+      get { return (IValueLookupParameter<IItem>)Parameters["Quality"]; }
+    }
     public IValueLookupParameter<IntValue> ReferenceSetSizeParameter {
       get { return (IValueLookupParameter<IntValue>)Parameters["ReferenceSetSize"]; }
-    }
-    public IValueLookupParameter<IItem> QualityParameter {
-      get { return (IValueLookupParameter<IItem>)Parameters["Quality"]; }
     }
     public IValueLookupParameter<IItem> TargetParameter {
@@ -68 +68 @@
       get { return CurrentScopeParameter.ActualValue; }
     }
-    private DiversityCalculator DiversityCalculator {
-      get { return DiversityCalculatorParameter.ActualValue; }
+    private SimilarityCalculator SimilarityCalculator {
+      get { return SimilarityCalculatorParameter.ActualValue; }
     }
     private BoolValue Maximization {
@@ -81 +81 @@
       get { return NumberOfHighQualitySolutionsParameter.ActualValue; }
     }
+    private IItem Quality {
+      get { return QualityParameter.ActualValue; }
+    }
     private IntValue ReferenceSetSize {
       get { return ReferenceSetSizeParameter.ActualValue; }
       set { ReferenceSetSizeParameter.ActualValue = value; }
-    }
-    private IItem Quality {
-      get { return QualityParameter.ActualValue; }
     }
     private IItem Target {
@@ -105 +105 @@
       #region Create parameters
       Parameters.Add(new ScopeParameter("CurrentScope"));
-      Parameters.Add(new ValueLookupParameter<DiversityCalculator>("DiversityCalculator"));
       Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization"));
       Parameters.Add(new ValueLookupParameter<BoolValue>("NewSolutions"));
       Parameters.Add(new ValueLookupParameter<IntValue>("NumberOfHighQualitySolutions"));
+      Parameters.Add(new ValueLookupParameter<IItem>("Quality"));
       Parameters.Add(new ValueLookupParameter<IntValue>("ReferenceSetSize"));
-      Parameters.Add(new ValueLookupParameter<IItem>("Quality"));
+      Parameters.Add(new ValueLookupParameter<SimilarityCalculator>("SimilarityCalculator"));
       Parameters.Add(new ValueLookupParameter<IItem>("Target"));
       #endregion
-      TargetParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem
     }
 
     public override IOperation Apply() {
-      var parentsScope = new Scope("Parents");
-      var offspringScope = new Scope("Offspring");
+      IScope parentsScope = new Scope("Parents");
+      IScope offspringScope = new Scope("Offspring");
 
       // split parents and offspring
@@ -132 +131 @@
 
       var highQualityParents = orderedParents.Take(NumberOfHighQualitySolutions.Value).ToList();
-      var highDiversityParents = new List<Tuple<IScope, double>>();
+      IList<Tuple<IScope, double>> highSimilarityParents = new List<Tuple<IScope, double>>();
       foreach (var oScope in orderedParents.Skip(NumberOfHighQualitySolutions.Value)) {
-        double diversity = 0.0;
-        var oSol = oScope.Variables[TargetParameter.ActualName].Value;
+        double similarity = 0.0;
         foreach (var hScope in highQualityParents) {
-          var hSol = hScope.Variables[TargetParameter.ActualName].Value;
-          diversity += DiversityCalculator.ExecuteCalculation(oSol, hSol);
+          similarity += SimilarityCalculator.ExecuteCalculation(oScope, hScope);
         }
-        highDiversityParents.Add(new Tuple<IScope, double>(oScope, diversity));
+        highSimilarityParents.Add(new Tuple<IScope, double>(oScope, similarity));
       }
 
-      var offspring = new List<Tuple<IScope, double>>();
+      IList<Tuple<IScope, double>> offspring = new List<Tuple<IScope, double>>();
       foreach (var oScope in orderedOffspring) {
-        double diversity = 0.0;
-        var oSol = oScope.Variables[TargetParameter.ActualName].Value;
+        double similarity = 0.0;
         foreach (var hScope in highQualityParents) {
-          var hSol = hScope.Variables[TargetParameter.ActualName].Value;
-          diversity += DiversityCalculator.ExecuteCalculation(oSol, hSol);
+          similarity += SimilarityCalculator.ExecuteCalculation(oScope, hScope);
         }
-        offspring.Add(new Tuple<IScope, double>(oScope, diversity));
+        offspring.Add(new Tuple<IScope, double>(oScope, similarity));
       }
 
@@ -171 +166 @@
 
       // update diversity part of the reference set
-      var hasBetterDiversity = (Func<Tuple<IScope, double>, bool>)(x => { return x.Item2 > highDiversityParents.OrderBy(y => y.Item2).First().Item2; });
+      var hasBetterDiversity = (Func<Tuple<IScope, double>, bool>)(x => { return x.Item2 < highSimilarityParents.OrderByDescending(y => y.Item2).First().Item2; });
       if (offspring.Any(hasBetterDiversity)) NewSolutions.Value = true;
       while (offspring.Any(hasBetterDiversity)) { // better offspring available
         // select best offspring
-        var bestChild = offspring.OrderByDescending(x => x.Item2).First();
+        var bestChild = offspring.OrderBy(x => x.Item2).First();
         // select worst parent
-        var worstParent = highDiversityParents.OrderBy(x => x.Item2).First();
-        highDiversityParents.Remove(worstParent);
-        highDiversityParents.Add(bestChild);
+        var worstParent = highSimilarityParents.OrderByDescending(x => x.Item2).First();
+        highSimilarityParents.Remove(worstParent);
+        highSimilarityParents.Add(bestChild);
         offspring.Remove(bestChild);
       }
 
-      CurrentScope.SubScopes.Replace(highQualityParents.Concat(highDiversityParents.Select(x => x.Item1)).ToList());
+      CurrentScope.SubScopes.Replace(highQualityParents.Concat(highSimilarityParents.Select(x => x.Item1)).ToList());
 
       return base.Apply();
     }
-
-    private class KeyEqualityComparer<T> : IEqualityComparer<T> {
-      private readonly Func<T, object> keyExtractor;
-
-      public KeyEqualityComparer(Func<T, object> keyExtractor) {
-        this.keyExtractor = keyExtractor;
-      }
-
-      public bool Equals(T x, T y) {
-        return keyExtractor(x).Equals(keyExtractor(y));
-      }
-
-      public int GetHashCode(T obj) {
-        return keyExtractor(obj).GetHashCode();
-      }
-    }
   }
 }