Changeset 12363 for branches/VOSGA/HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm

Timestamp:

04/29/15 16:00:38 (10 years ago)

Author:

ascheibe

Message:

#2267 added another offspring selector

Location:

branches/VOSGA/HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm

Files:

• Comparators/EliteWeightedParentsQualityComparator.cs (copied) (copied from branches/VOSGA/HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm/Comparators/WeightedParentsQualityComparator.cs) (5 diffs)
• HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm-3.3.csproj (modified) (1 diff)
• OffspringSelectors/EliteOffspringSelector.cs (copied) (copied from branches/VOSGA/HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm/OffspringSelectors/PopDivOffspringSelector.cs) (5 diffs)
• OffspringSelectors/PopDivOffspringSelector.cs (modified) (1 diff)

branches/VOSGA/HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm/Comparators/EliteWeightedParentsQualityComparator.cs

@@ -31 +31 @@
 
 namespace HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm {
-  [Item("WeightedParentsQualityComparator", "Compares the quality against that of its parents (assumes the parents are subscopes to the child scope). This operator works with any number of subscopes > 0.")]
+  [Item("EliteWeightedParentsQualityComparator", "M2")]
   [StorableClass]
-  public class WeightedParentsQualityComparator : SingleSuccessorOperator, ISubScopesQualityComparatorOperator {
+  public class EliteWeightedParentsQualityComparator : SingleSuccessorOperator, ISubScopesQualityComparatorOperator {
     public IValueLookupParameter<BoolValue> MaximizationParameter {
       get { return (IValueLookupParameter<BoolValue>)Parameters["Maximization"]; }
@@ -46 +46 @@
       get { return (ILookupParameter<BoolValue>)Parameters["Result"]; }
     }
+    public ILookupParameter<BoolValue> ResultImprovementParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters["ResultImprovement"]; }
+    }
     public ValueLookupParameter<DoubleValue> ComparisonFactorParameter {
       get { return (ValueLookupParameter<DoubleValue>)Parameters["ComparisonFactor"]; }
@@ -51 +54 @@
 
     [StorableConstructor]
-    protected WeightedParentsQualityComparator(bool deserializing) : base(deserializing) { }
-    protected WeightedParentsQualityComparator(WeightedParentsQualityComparator original, Cloner cloner) : base(original, cloner) { }
-    public WeightedParentsQualityComparator()
+    protected EliteWeightedParentsQualityComparator(bool deserializing) : base(deserializing) { }
+    protected EliteWeightedParentsQualityComparator(EliteWeightedParentsQualityComparator original, Cloner cloner) : base(original, cloner) { }
+    public EliteWeightedParentsQualityComparator()
       : base() {
       Parameters.Add(new ValueLookupParameter<BoolValue>("Maximization", "True if the problem is a maximization problem, false otherwise"));
@@ -59 +62 @@
       Parameters.Add(new ScopeTreeLookupParameter<DoubleValue>("RightSide", "The qualities of the parents."));
       Parameters.Add(new LookupParameter<BoolValue>("Result", "The result of the comparison: True means Quality is better, False means it is worse than parents."));
+      Parameters.Add(new LookupParameter<BoolValue>("ResultImprovement", "A solution has improved if it is better than the worse parent."));
       Parameters.Add(new ValueLookupParameter<DoubleValue>("ComparisonFactor", "Determines if the quality should be compared to the better parent (1.0), to the worse (0.0) or to any linearly interpolated value between them."));
     }
 
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new WeightedParentsQualityComparator(this, cloner);
+      return new EliteWeightedParentsQualityComparator(this, cloner);
     }
 
@@ -122 +126 @@
       }
 
+      bool resultImprovement = maximization && leftQuality > rightQualities.Min(x => x.Value) ||
+                              !maximization && leftQuality < rightQualities.Max(x => x.Value);
+      BoolValue resultImprovementValue = ResultImprovementParameter.ActualValue;
+      if (resultImprovementValue == null) {
+        ResultImprovementParameter.ActualValue = new BoolValue(resultImprovement);
+      } else {
+        resultImprovementValue.Value = resultImprovement;
+      }
+
       return base.Apply();
     }

branches/VOSGA/HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm/HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm-3.3.csproj

@@ -176 +176 @@
     <Compile Include="Comparators\UnwantedMutationsComparator.cs" />
     <Compile Include="Comparators\WeightedParentsDiversityComparator.cs" />
+    <Compile Include="Comparators\EliteWeightedParentsQualityComparator.cs" />
     <Compile Include="Comparators\WeightedParentsQualityComparator.cs" />
     <Compile Include="ISubScopesQualityComparatorOperator.cs" />
     <Compile Include="OffspringCollector.cs" />
     <Compile Include="OffspringSelectors\IOffspringSelector.cs" />
+    <Compile Include="OffspringSelectors\EliteOffspringSelector.cs" />
     <Compile Include="OffspringSelectors\PopDivOffspringSelector.cs" />
     <Compile Include="OffspringSelectors\StandardOffspringSelector.cs" />

branches/VOSGA/HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm/OffspringSelectors/EliteOffspringSelector.cs

@@ -34 +34 @@
 
 namespace HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm {
-  [Item("PopDivOffspringSelector", "")]
+  [Item("EliteOffspringSelector", "M2")]
   [StorableClass]
-  public class PopDivOffspringSelector : InstrumentedOperator, IOffspringSelector {
+  public class EliteOffspringSelector : InstrumentedOperator, IOffspringSelector {
 
     private const string SuccessRatioChart = "SuccessRatioChart";
@@ -91 +91 @@
 
     [StorableConstructor]
-    protected PopDivOffspringSelector(bool deserializing) : base(deserializing) { }
-    protected PopDivOffspringSelector(PopDivOffspringSelector original, Cloner cloner)
+    protected EliteOffspringSelector(bool deserializing) : base(deserializing) { }
+    protected EliteOffspringSelector(EliteOffspringSelector original, Cloner cloner)
       : base(original, cloner) {
     }
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new PopDivOffspringSelector(this, cloner);
-    }
-    public PopDivOffspringSelector()
+      return new EliteOffspringSelector(this, cloner);
+    }
+    public EliteOffspringSelector()
       : base() {
       Parameters.Add(new ValueLookupParameter<DoubleValue>("MaximumSelectionPressure", "The maximum selection pressure which prematurely terminates the offspring selection step."));
@@ -192 +192 @@
       int worseOffspringNeeded = (int)((1 - successRatio) * populationSize) - (population.Count - successfulOffspring.Value);
       int successfulOffspringAdded = 0;
-
       double avgPopDiv = DiversityComparisonFactorParameter.Value.Value;
-      bool takeWorseOffspring = false;
 
       // implement the ActualValue fetch here - otherwise the parent scope would also be included, given that there may be 1000 or more parents, this is quite unnecessary
       string tname = SuccessfulOffspringParameter.TranslatedName;
       double tmpSelPress = selectionPressure.Value, tmpSelPressInc = 1.0 / populationSize;
-      int cnt = 0;
-      int stepWidth = offspring.SubScopes.Count / 5;
       for (int i = 0; i < offspring.SubScopes.Count; i++) {
-        //calculate population diversity so far
-        if (cnt != 0 && cnt % stepWidth == 0) {
-          Scope tmpScope = new Scope();
-          tmpScope.SubScopes.AddRange(population);
-          double popDiversity = SimilarityCalculatorParameter.ActualValue.CalculateSolutionCrowdSimilarity(tmpScope).Average(x => x.Average());
-          //this assumes that low-quality solutions are of high diversity
-          if (popDiversity > avgPopDiv) {
-            takeWorseOffspring = true;
-          } else {
-            takeWorseOffspring = false;
-          }
-        }
-        cnt++;
-
         // fetch value
         IVariable tmpVar;
@@ -222 +204 @@
         if (tmp == null) throw new InvalidOperationException(Name + ": The variable that indicates whether an offspring is successful or not must contain a BoolValue.");
 
-        if (takeWorseOffspring) {
-          IScope currentOffspring = offspring.SubScopes[i];
-          Scope tmpScope = new Scope();
-          tmpScope.SubScopes.AddRange(population);
-          Scope tmpCurrentScope = new Scope();
-          tmpCurrentScope.SubScopes.Add(currentOffspring);
-          double curDiv = SimilarityCalculatorParameter.ActualValue.CalculateSolutionCrowdSimilarity(tmpCurrentScope, tmpScope)[0].Average();
-          if (curDiv < avgPopDiv) {
-            offspring.SubScopes.Remove(currentOffspring);
-            i--;
-            population.Add(currentOffspring);
-            worseOffspringNeeded--;
-          }
-        } else if (tmp.Value) {
+        if (!offspring.SubScopes[i].Variables.TryGetValue("ResultImprovement", out tmpVar)) throw new InvalidOperationException(Name + ": Could not find ResultImprovment.");
+        BoolValue betterThanWorseParent = (tmpVar.Value as BoolValue);
+        if (betterThanWorseParent == null) throw new InvalidOperationException(Name + ": Could not find ResultImprovment.");
+
+        //this is an "elite" solution candidate
+        double tmpCurSuccRatio = (successfulOffspring.Value + successfulOffspringAdded) / (double)populationSize;
+        if (tmp.Value && tmpCurSuccRatio <= successRatio) {
+          //this overrides the diversity mechanism; always fill up elites if there is space
           IScope currentOffspring = offspring.SubScopes[i];
           offspring.SubScopes.Remove(currentOffspring);
@@ -241 +217 @@
           population.Add(currentOffspring);
           successfulOffspringAdded++;
-        } else if (worseOffspringNeeded > 0 || tmpSelPress >= maxSelPress) {
-          IScope currentOffspring;
-          if (!fillPopulationWithParents || worseOffspringNeeded > 0) {
-            currentOffspring = offspring.SubScopes[i];
+        } else if (!tmp.Value && betterThanWorseParent.Value) {
+          //quality is ok, check for diversity
+          IScope currentOffspring = offspring.SubScopes[i];
+
+          if (!population.Any()) {
             offspring.SubScopes.Remove(currentOffspring);
             i--;
             worseOffspringNeeded--;
+            population.Add(currentOffspring);
           } else {
-            currentOffspring = parents.SubScopes[i];
+            Scope tmpScope = new Scope();
+            tmpScope.SubScopes.AddRange(population);
+            Scope tmpCurrentScope = new Scope();
+            tmpCurrentScope.SubScopes.Add(currentOffspring);
+            double curDiv = SimilarityCalculatorParameter.ActualValue.CalculateSolutionCrowdSimilarity(tmpCurrentScope, tmpScope)[0].Average();
+            if (curDiv < avgPopDiv) {
+              if (worseOffspringNeeded > 0 || tmpSelPress >= maxSelPress) {
+                if (!fillPopulationWithParents || worseOffspringNeeded > 0) {
+                  offspring.SubScopes.Remove(currentOffspring);
+                  i--;
+                  worseOffspringNeeded--;
+                } else {
+                  currentOffspring = parents.SubScopes[i];
+                }
+                population.Add(currentOffspring);
+              }
+            }
           }
-          population.Add(currentOffspring);
         }
+
         tmpSelPress += tmpSelPressInc;
         if (population.Count >= populationSize) break;

branches/VOSGA/HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm/OffspringSelectors/PopDivOffspringSelector.cs

@@ -34 +34 @@
 
 namespace HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm {
-  [Item("PopDivOffspringSelector", "")]
+  [Item("PopDivOffspringSelector", "M1")]
   [StorableClass]
   public class PopDivOffspringSelector : InstrumentedOperator, IOffspringSelector {