Changeset 7744 for branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch

Timestamp:

04/20/12 17:00:09 (13 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

Location:

branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3

Files:

• DiversityCalculator.cs (added)
• HeuristicLab.Algorithms.ScatterSearch-3.3.csproj (modified) (2 diffs)
• IScatterSearchTargetProcessor.cs (added)
• Knapsack/BinaryVectorDiversityCalculator.cs (added)
• Knapsack/DiversityCalculator.cs (deleted)
• Knapsack/KnapsackImprovementOperator.cs (added)
• Knapsack/NBinaryVectorCrossover.cs (modified) (1 diff)
• Knapsack/NChildCrossover.cs (modified) (3 diffs)
• OffspringProcessor.cs (added)
• PopulationRebuildMethod.cs (modified) (4 diffs)
• ReferenceSetUpdateMethod.cs (modified) (4 diffs)
• ScatterSearch.cs (modified) (7 diffs)
• ScatterSearchImprovementOperator.cs (deleted)
• ScatterSearchMainLoop.cs (modified) (3 diffs)
• SolutionPoolUpdateMethod.cs (modified) (5 diffs)
• TravelingSalesman (added)
• TravelingSalesman/PermutationDiversityCalculator.cs (added)
• TravelingSalesman/TravelingSalesmanImprovementOperator.cs (added)

branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/HeuristicLab.Algorithms.ScatterSearch-3.3.csproj

@@ -86 +86 @@
   </ItemGroup>
   <ItemGroup>
-    <Compile Include="Knapsack\DiversityCalculator.cs" />
+    <Compile Include="DiversityCalculator.cs" />
+    <Compile Include="Knapsack\BinaryVectorDiversityCalculator.cs" />
     <Compile Include="Knapsack\INBinaryVectorCrossover.cs" />
+    <Compile Include="IScatterSearchTargetProcessor.cs" />
     <Compile Include="Knapsack\NBinaryVectorCrossover.cs" />
     <Compile Include="Knapsack\NChildCrossover.cs" />
     <Compile Include="OffspringProcessor.cs" />
-    <Compile Include="TSPPopulationRebuildMethod.cs" />
-    <Compile Include="TSPSolutionPoolUpdateMethod.cs" />
-    <Compile Include="TSPReferenceSetUpdateMethod.cs" />
-    <Compile Include="TSPScatterSearchImprovementOperator.cs" />
+    <Compile Include="TravelingSalesman\PermutationDiversityCalculator.cs" />
+    <Compile Include="TravelingSalesman\TravelingSalesmanImprovementOperator.cs" />
     <None Include="HeuristicLab.snk" />
     <None Include="Plugin.cs.frame" />
@@ -103 +103 @@
     <Compile Include="PopulationRebuildMethod.cs" />
     <Compile Include="ScatterSearch.cs" />
-    <Compile Include="ScatterSearchImprovementOperator.cs" />
+    <Compile Include="Knapsack\KnapsackImprovementOperator.cs" />
     <Compile Include="ScatterSearchMainLoop.cs" />
     <Compile Include="SolutionPoolUpdateMethod.cs" />

branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack/NBinaryVectorCrossover.cs

@@ -71 +71 @@
 
     public sealed override IOperation Apply() {
-      //ChildrenParameter.ActualValue = Cross(RandomParameter.ActualValue, ParentsParameter.ActualValue);
       var offspringSolutions = Cross(RandomParameter.ActualValue, ParentsParameter.ActualValue);
       for (int i = 0; i < offspringSolutions.Length; i++) {

branches/ScatterSearch/HeuristicLab.Algorithms.ScatterSearch/3.3/Knapsack/NChildCrossover.cs

@@ -35 +35 @@
   [StorableClass]
   public sealed class NChildCrossover : NBinaryVectorCrossover {
+    #region Parameter properties
     public IValueLookupParameter<IntValue> NParameter {
       get { return (IValueLookupParameter<IntValue>)Parameters["N"]; }
     }
+    #endregion
 
     [StorableConstructor]
@@ -44 +46 @@
     public NChildCrossover()
       : base() {
+      #region Create parameters
       Parameters.Add(new ValueLookupParameter<IntValue>("N", "Number of children.", new IntValue(2)));
+      #endregion
     }
 
@@ -53 +57 @@
     public static ItemArray<BinaryVector> Apply(IRandom random, BinaryVector parent1, BinaryVector parent2, IntValue n) {
       if (parent1.Length != parent2.Length)
-        throw new ArgumentException("NPointCrossover: The parents are of different length.");
+        throw new ArgumentException("NChildCrossover: The parents are of different length.");
 
       if (n.Value > Math.Pow(2, parent1.Length) - 2)
-        throw new ArgumentException("NPointCrossover: There cannot be more breakpoints than the size of the parents.");
+        throw new ArgumentException("NChildCrossover: There cannot be more children than 2^size of parents - 2.");
 
       if (n.Value < 1)
-        throw new ArgumentException("NPointCrossover: N cannot be < 1.");
+        throw new ArgumentException("NChildCrossover: N cannot be < 1.");
 
       var solutions = new BinaryVector[n.Value];

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

@@ -39 +39 @@
       get { return (ScopeParameter)Parameters["CurrentScope"]; }
     }
+    public IValueLookupParameter<BoolValue> MaximizationParameter {
+      get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
+    }
     public IValueLookupParameter<IntValue> NumberOfHighQualitySolutionsParameter {
       get { return (IValueLookupParameter<IntValue>)Parameters["NumberOfHighQualitySolutions"]; }
@@ -53 +56 @@
     private IScope CurrentScope {
       get { return CurrentScopeParameter.ActualValue; }
+    }
+    private BoolValue Maximization {
+      get { return MaximizationParameter.ActualValue; }
+      set { MaximizationParameter.ActualValue = value; }
     }
     private IntValue NumberOfHighQualitySolutions {
@@ -79 +86 @@
       #region Create parameters
       Parameters.Add(new ScopeParameter("CurrentScope"));
+      Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization"));
       Parameters.Add(new ValueLookupParameter<IntValue>("NumberOfHighQualitySolutions"));
       Parameters.Add(new ValueLookupParameter<IntValue>("ReferenceSetSize"));
@@ -86 +94 @@
 
     public override IOperation Apply() {
-      var population = CurrentScope.SubScopes[0];
-      var refSet = CurrentScope.SubScopes[1];
-      refSet.SubScopes.Replace(refSet.SubScopes.OrderByDescending(r => r.Variables[QualityParameter.ActualName].Value)
-                                               .Take(NumberOfHighQualitySolutions.Value).ToList());
-      population.SubScopes.Clear();
+      var populationScope = CurrentScope.SubScopes[0];
+      var referenceSetScope = CurrentScope.SubScopes[1];
+      var orderedReferenceSet = Maximization.Value ? referenceSetScope.SubScopes.OrderByDescending(r => r.Variables[QualityParameter.ActualName].Value) :
+                                                     referenceSetScope.SubScopes.OrderBy(r => r.Variables[QualityParameter.ActualName].Value);
+      referenceSetScope.SubScopes.Replace(orderedReferenceSet.Take(NumberOfHighQualitySolutions.Value).ToList());
+      populationScope.SubScopes.Clear();
       return base.Apply();
     }

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

@@ -46 +46 @@
       get { return (IValueLookupParameter<IntValue>)Parameters["ReferenceSetSize"]; }
     }
-    public IValueLookupParameter<IItem> QualityParameter {
-      get { return (IValueLookupParameter<IItem>)Parameters["Quality"]; }
+    public IValueLookupParameter<IItem> TargetParameter {
+      get { return (IValueLookupParameter<IItem>)Parameters["Target"]; }
+    }
+    public IValueLookupParameter<DiversityCalculator> DiversityCalculatorParameter {
+      get { return (IValueLookupParameter<DiversityCalculator>)Parameters["DiversityCalculator"]; }
     }
     #endregion
@@ -61 +64 @@
       get { return ReferenceSetSizeParameter.ActualValue; }
     }
-    private IItem Quality {
-      get { return QualityParameter.ActualValue; }
+    private IItem Target {
+      get { return TargetParameter.ActualValue; }
+    }
+    private DiversityCalculator DiversityCalculator {
+      get { return DiversityCalculatorParameter.ActualValue; }
     }
     #endregion
@@ -80 +86 @@
       Parameters.Add(new ValueLookupParameter<IntValue>("NumberOfHighQualitySolutions"));
       Parameters.Add(new ValueLookupParameter<IntValue>("ReferenceSetSize"));
-      Parameters.Add(new ValueLookupParameter<IItem>("Quality"));
+      Parameters.Add(new ValueLookupParameter<IItem>("Target"));
+      Parameters.Add(new ValueLookupParameter<DiversityCalculator>("DiversityCalculator"));
       #endregion
+      TargetParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem
     }
 
@@ -88 +96 @@
       foreach (var pScope in CurrentScope.SubScopes[0].SubScopes) {
         int diversity = 0;
-        var pSol = pScope.Variables[QualityParameter.ActualName].Value;
+        var pSol = pScope.Variables[TargetParameter.ActualName].Value;
         foreach (var rScope in CurrentScope.SubScopes[1].SubScopes) {
-          var rSol = rScope.Variables[QualityParameter.ActualName].Value;
-          if (pSol != null && rSol != null) diversity += Knapsack.DiversityCalculator.CalculateDiversity(pSol, rSol);
+          var rSol = rScope.Variables[TargetParameter.ActualName].Value;
+          diversity += DiversityCalculator.ExecuteCalculation(pSol, rSol);
         }
         population[pScope] = diversity;

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

@@ -61 +61 @@
       get { return (ConstrainedValueParameter<ICrossover>)Parameters["Crossover"]; }
     }
-    public IValueParameter<ILocalImprovementOperator> ImproverParameter {
-      get { return (IValueParameter<ILocalImprovementOperator>)Parameters["Improver"]; }
+    public ConstrainedValueParameter<ILocalImprovementOperator> ImproverParameter {
+      get { return (ConstrainedValueParameter<ILocalImprovementOperator>)Parameters["Improver"]; }
+    }
+    public ConstrainedValueParameter<DiversityCalculator> DiversityCalculatorParameter {
+      get { return (ConstrainedValueParameter<DiversityCalculator>)Parameters["DiversityCalculator"]; }
     }
     public IValueParameter<IntValue> MaximumIterationsParameter {
@@ -96 +99 @@
       get { return ImproverParameter.Value; }
       set { ImproverParameter.Value = value; }
+    }
+    private DiversityCalculator DiversityCalculator {
+      get { return DiversityCalculatorParameter.Value; }
+      set { DiversityCalculatorParameter.Value = value; }
     }
     private IntValue MaximumIterations {
@@ -154 +161 @@
       Parameters.Add(new ValueParameter<MultiAnalyzer>("Analyzer", "The operator used to analyze the solution and moves.", new MultiAnalyzer()));
       Parameters.Add(new ConstrainedValueParameter<ICrossover>("Crossover", "The operator used to combine solutions."));
-      Parameters.Add(new ValueParameter<ILocalImprovementOperator>("Improver", "The operator used to improve solutions.", new ScatterSearchImprovementOperator()));
-      Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(1000)));
-      Parameters.Add(new ValueParameter<IntValue>("NumberOfHighQualitySolutions", "The number of high quality solutions that should be added to the reference set.", new IntValue(5)));
-      Parameters.Add(new ValueParameter<IntValue>("PopulationSize", "The size of the population.", new IntValue(30)));
-      Parameters.Add(new ValueParameter<IntValue>("ReferenceSetSize", "The size of the reference set.", new IntValue(10)));
+      Parameters.Add(new ConstrainedValueParameter<ILocalImprovementOperator>("Improver", "The operator used to improve solutions."));
+      Parameters.Add(new ConstrainedValueParameter<DiversityCalculator>("DiversityCalculator", "The operator used to calculate the diversity of two solutions."));
+      Parameters.Add(new ValueParameter<IntValue>("MaximumIterations", "The maximum number of generations which should be processed.", new IntValue(100)));
+      Parameters.Add(new ValueParameter<IntValue>("NumberOfHighQualitySolutions", "The number of high quality solutions that should be added to the reference set.", new IntValue(10)));
+      Parameters.Add(new ValueParameter<IntValue>("PopulationSize", "The size of the population.", new IntValue(300)));
+      Parameters.Add(new ValueParameter<IntValue>("ReferenceSetSize", "The size of the reference set.", new IntValue(100)));
       Parameters.Add(new ValueParameter<IntValue>("Seed", "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
       Parameters.Add(new ValueParameter<BoolValue>("SetSeedRandomly", "True if the random seed should be set to a random value, otherwise false.", new BoolValue(true)));
@@ -241 +249 @@
       UpdateAnalyzers();
       UpdateCrossovers();
+      UpdateDiversityCalculators();
+      UpdateImprovers();
+      UpdateDiversityCalculators();
       Problem.Evaluator.QualityParameter.ActualNameChanged += new EventHandler(Evaluator_QualityParameter_ActualNameChanged);
       base.OnProblemChanged();
@@ -261 +272 @@
       UpdateAnalyzers();
       UpdateCrossovers();
+      UpdateDiversityCalculators();
+      UpdateImprovers();
       ParameterizeMainLoop();
       ParameterizeAnalyzers();
@@ -307 +320 @@
         CrossoverParameter.Value = defaultCrossover;
     }
+    private void UpdateDiversityCalculators() {
+      DiversityCalculator oldDiversityCalculator = DiversityCalculatorParameter.Value;
+      DiversityCalculatorParameter.ValidValues.Clear();
+      DiversityCalculator defaultDiversityCalculator = Problem.Operators.OfType<DiversityCalculator>().FirstOrDefault();
+
+      DiversityCalculatorParameter.ValidValues.Add(new Knapsack.BinaryVectorDiversityCalculator());
+      DiversityCalculatorParameter.ValidValues.Add(new TravelingSalesman.PermutationDiversityCalculator());
+
+      foreach (DiversityCalculator diversityCalculator in Problem.Operators.OfType<DiversityCalculator>().OrderBy(x => x.Name))
+        DiversityCalculatorParameter.ValidValues.Add(diversityCalculator);
+
+      if (oldDiversityCalculator != null) {
+        DiversityCalculator diversityCalculator = DiversityCalculatorParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldDiversityCalculator.GetType());
+        if (diversityCalculator != null) DiversityCalculatorParameter.Value = diversityCalculator;
+        else oldDiversityCalculator = null;
+      }
+      if (oldDiversityCalculator == null && defaultDiversityCalculator != null)
+        DiversityCalculatorParameter.Value = defaultDiversityCalculator;
+    }
+    private void UpdateImprovers() {
+      ILocalImprovementOperator oldImprover = ImproverParameter.Value;
+      ImproverParameter.ValidValues.Clear();
+      ILocalImprovementOperator defaultImprover = Problem.Operators.OfType<ILocalImprovementOperator>().FirstOrDefault();
+
+      ImproverParameter.ValidValues.Add(new Knapsack.KnapsackImprovementOperator());
+      ImproverParameter.ValidValues.Add(new TravelingSalesman.TravelingSalesmanImprovementOperator());
+
+      foreach (ILocalImprovementOperator improver in Problem.Operators.OfType<ILocalImprovementOperator>().OrderBy(x => x.Name))
+        ImproverParameter.ValidValues.Add(improver);
+
+      foreach (var improver in ImproverParameter.ValidValues.OfType<IScatterSearchTargetProcessor>())
+        improver.TargetParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem
+
+      if (oldImprover != null) {
+        ILocalImprovementOperator improver = ImproverParameter.ValidValues.FirstOrDefault(x => x.GetType() == oldImprover.GetType());
+        if (improver != null) ImproverParameter.Value = improver;
+        else oldImprover = null;
+      }
+      if (oldImprover == null && defaultImprover != null)
+        ImproverParameter.Value = defaultImprover;
+    }
     private void ParameterizeSolutionsCreator() {
       SolutionsCreator.EvaluatorParameter.ActualName = Problem.EvaluatorParameter.Name;
@@ -325 +379 @@
       }
     }
+    //private void ParameterizeScatterSearchTargetProcessor(IOperator op) {
+    //  if (op is IScatterSearchTargetProcessor) {
+    //    IScatterSearchTargetProcessor ssOp = (IScatterSearchTargetProcessor)op;
+    //    ssOp.TargetParameter.ActualName = "KnapsackSolution"; // temporary solution for the knapsack problem
+    //    ssOp.TargetParameter.Hidden = true;
+    //  }
+    //}
     private void ParameterizeAnalyzers() {
       qualityAnalyzer.ResultsParameter.ActualName = "Results";

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

@@ -46 +46 @@
       get { return (IValueLookupParameter<IOperator>)Parameters["Improver"]; }
     }
+    public IValueLookupParameter<DiversityCalculator> DiversityCalculatorParameter {
+      get { return (IValueLookupParameter<DiversityCalculator>)Parameters["DiversityCalculator"]; }
+    }
     public IValueLookupParameter<IntValue> NumberOfHighQualitySolutionsParameter {
       get { return (IValueLookupParameter<IntValue>)Parameters["NumberOfHighQualitySolutions"]; }
@@ -99 +102 @@
       get { return ImproverParameter.ActualValue; }
       set { ImproverParameter.ActualValue = value; }
+    }
+    private DiversityCalculator DiversityCalculator {
+      get { return DiversityCalculatorParameter.ActualValue; }
+      set { DiversityCalculatorParameter.ActualValue = value; }
     }
     private IntValue NumberOfHighQualitySolutions {
@@ -168 +175 @@
       Parameters.Add(new ValueLookupParameter<ICrossover>("Crossover", "The operator used to combine solutions."));
       Parameters.Add(new ValueLookupParameter<IOperator>("Improver", "The operator used to improve solutions."));
+      Parameters.Add(new ValueLookupParameter<DiversityCalculator>("DiversityCalculator", "The operator used to calculate the diversity of two solutions."));
       Parameters.Add(new ValueLookupParameter<IntValue>("NumberOfHighQualitySolutions", "The number of high quality solutions that should be added to the reference set."));
       Parameters.Add(new ValueLookupParameter<IntValue>("PopulationSize", "The size of the population."));

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;
+        }
       }