Changeset 7744 for branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPoolUpdateMethod.cs

Timestamp:

04/20/12 17:00:09 (12 years ago)

Author:

jkarder

Message:

#1331:

• added problem specific improvement operators (KnapsackImprovementOperator, TravelingSalesmanImprovementOperator)
• added custom interface (IScatterSearchTargetProcessor) for Scatter Search specific operators that use a target parameter
• added custom operator (OffspringProcessor) to process multiple children that were created by crossovers
• extracted diversity calculation and added problem/encoding specific operators (BinaryVectorDiversityCalculator, PermutationDiversityCalculator) for it
• added parameters and adjusted types
• adjusted event handling
• minor code improvements

File:

• branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/SolutionPoolUpdateMethod.cs (modified) (5 diffs)

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

@@ -36 +36 @@
   [Item("SolutionPoolUpdateMethod", "An operator that updates the solution pool.")]
   [StorableClass]
-  public sealed class SolutionPoolUpdateMethod : SingleSuccessorOperator {
+  public sealed class SolutionPoolUpdateMethod : SingleSuccessorOperator, IScatterSearchTargetProcessor {
     #region Parameter properties
     public ScopeParameter CurrentScopeParameter {
       get { return (ScopeParameter)Parameters["CurrentScope"]; }
+    }
+    public IValueLookupParameter<BoolValue> MaximizationParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
     }
     public IValueLookupParameter<BoolValue> NewSolutionsParameter {
@@ -50 +53 @@
       get { return (IValueLookupParameter<IItem>)Parameters["Quality"]; }
     }
-    public IValueLookupParameter<IItem> SolutionParameter {
-      get { return (IValueLookupParameter<IItem>)Parameters["Solution"]; }
+    public IValueLookupParameter<IItem> TargetParameter {
+      get { return (IValueLookupParameter<IItem>)Parameters["Target"]; }
     }
     #endregion
@@ -58 +61 @@
     private IScope CurrentScope {
       get { return CurrentScopeParameter.ActualValue; }
+    }
+    private BoolValue Maximization {
+      get { return MaximizationParameter.ActualValue; }
+      set { MaximizationParameter.ActualValue = value; }
     }
     private BoolValue NewSolutions {
@@ -68 +75 @@
     private IItem Quality {
       get { return QualityParameter.ActualValue; }
+    }
+    private IItem Target {
+      get { return TargetParameter.ActualValue; }
     }
     #endregion
@@ -83 +93 @@
       #region Create parameters
       Parameters.Add(new ScopeParameter("CurrentScope"));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization"));
       Parameters.Add(new ValueLookupParameter<BoolValue>("NewSolutions"));
       Parameters.Add(new ValueLookupParameter<IntValue>("ReferenceSetSize"));
       Parameters.Add(new ValueLookupParameter<IItem>("Quality"));
-      Parameters.Add(new ValueLookupParameter<IItem>("Solution"));
+      Parameters.Add(new ValueLookupParameter<IItem>("Target"));
       #endregion
-      SolutionParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem
+      TargetParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem
     }
 
     public override IOperation Apply() {
-      IScope parents = new Scope("Parents");
-      IScope offspring = new Scope("Offspring");
+      var parentsScope = new Scope("Parents");
+      var offspringScope = new Scope("Offspring");
+
+      // split parents and offspring
       foreach (var scope in CurrentScope.SubScopes) {
-        parents.SubScopes.AddRange(scope.SubScopes.Take(scope.SubScopes.Count - 1));
-        offspring.SubScopes.AddRange(scope.SubScopes.Last().SubScopes);
+        parentsScope.SubScopes.AddRange(scope.SubScopes.Take(scope.SubScopes.Count - 1));
+        offspringScope.SubScopes.AddRange(scope.SubScopes.Last().SubScopes);
       }
+
       CurrentScope.SubScopes.Clear();
-      CurrentScope.SubScopes.AddRange(parents.SubScopes.OrderByDescending(o => o.Variables[QualityParameter.ActualName].Value));
-      if ((offspring.SubScopes.OrderByDescending(o => o.Variables[QualityParameter.ActualName].Value).First().Variables[QualityParameter.ActualName].Value as DoubleValue).Value
-          > (parents.SubScopes.OrderByDescending(o => o.Variables[QualityParameter.ActualName].Value).Last().Variables[QualityParameter.ActualName].Value as DoubleValue).Value) {
-        CurrentScope.SubScopes.Replace(parents.SubScopes.Concat(offspring.SubScopes.Distinct(new KeyEqualityComparer<IScope>(x => x.Variables[SolutionParameter.ActualName].Value.ToString()))).OrderByDescending(o => o.Variables[QualityParameter.ActualName].Value).Take(ReferenceSetSize.Value));
-        NewSolutions.Value = true;
+
+      var orderedParents = Maximization.Value ? parentsScope.SubScopes.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value) :
+                                                parentsScope.SubScopes.OrderBy(x => x.Variables[QualityParameter.ActualName].Value);
+      var orderedOffspring = Maximization.Value ? offspringScope.SubScopes.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value) :
+                                                  offspringScope.SubScopes.OrderBy(x => x.Variables[QualityParameter.ActualName].Value);
+
+      CurrentScope.SubScopes.AddRange(orderedParents);
+
+      var worstParentQuality = (orderedParents.Last().Variables[QualityParameter.ActualName].Value as DoubleValue).Value;
+
+      var Constraint = Maximization.Value ? (Func<IScope, bool>)(x => { return (x.Variables[QualityParameter.ActualName].Value as DoubleValue).Value > worstParentQuality; }) :
+                                            (Func<IScope, bool>)(x => { return (x.Variables[QualityParameter.ActualName].Value as DoubleValue).Value < worstParentQuality; });
+
+      // is there any offspring better than the worst parent?
+      if (orderedOffspring.Any(Constraint)) {
+        // produce the set union
+        // attention: distinction might cause a too small reference set! (e.g. reference set = {1, 2, 2, 2, ..., 2} -> union = {1, 2}
+        var union = orderedParents.Union(orderedOffspring.Where(Constraint), new KeyEqualityComparer<IScope>(x => x.Variables[TargetParameter.ActualName].Value.ToString()));
+        if (union.Count() > orderedParents./*Distinct(new KeyEqualityComparer<IScope>(x => x.Variables[TargetParameter.ActualName].Value.ToString())).*/Count()) {
+          var orderedUnion = Maximization.Value ? union.OrderByDescending(x => x.Variables[QualityParameter.ActualName].Value) :
+                                                  union.OrderBy(x => x.Variables[QualityParameter.ActualName].Value);
+          CurrentScope.SubScopes.Replace(orderedUnion.Take(ReferenceSetSize.Value).ToList());
+          NewSolutions.Value = true;
+        }
       }