Changeset 12350

Timestamp:

04/28/15 14:37:20 (10 years ago)

Author:

ascheibe

Message:

#2267 added a new offspring selector

Location:

branches/VOSGA/HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm

Files:

• HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm-3.3.csproj (modified) (1 diff)
• OffspringSelectors/PopDivOffspringSelector.cs (copied) (copied from branches/VOSGA/HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm/OffspringSelectors/StandardOffspringSelector.cs) (9 diffs)

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

@@ -180 +180 @@
     <Compile Include="OffspringCollector.cs" />
     <Compile Include="OffspringSelectors\IOffspringSelector.cs" />
+    <Compile Include="OffspringSelectors\PopDivOffspringSelector.cs" />
     <Compile Include="OffspringSelectors\StandardOffspringSelector.cs" />
     <Compile Include="ProbabilitiesGenerator.cs" />

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

@@ -21 +21 @@
 
 using System;
+using System.Linq;
+using HeuristicLab.Analysis;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
 using HeuristicLab.Data;
 using HeuristicLab.Operators;
+using HeuristicLab.Optimization;
+using HeuristicLab.Optimization.Operators;
 using HeuristicLab.Parameters;
 using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
+using HeuristicLab.PluginInfrastructure;
 
 namespace HeuristicLab.Algorithms.VOffspringSelectionGeneticAlgorithm {
-  [Item("StandardOffspringSelector", "Selects among the offspring population those that are designated successful and discards the unsuccessful offspring, except for some lucky losers. It expects the parent scopes to be below the first sub-scope, and offspring scopes to be below the second sub-scope separated again in two sub-scopes, the first with the failed offspring and the second with successful offspring.")]
+  [Item("PopDivOffspringSelector", "")]
   [StorableClass]
-  public class StandardOffspringSelector : InstrumentedOperator, IOffspringSelector {
+  public class PopDivOffspringSelector : InstrumentedOperator, IOffspringSelector {
+
+    private const string SuccessRatioChart = "SuccessRatioChart";
+    private const string SuccessRatioDataRow = "SuccessRatio";
+
+
     public ValueLookupParameter<DoubleValue> MaximumSelectionPressureParameter {
       get { return (ValueLookupParameter<DoubleValue>)Parameters["MaximumSelectionPressure"]; }
@@ -59 +69 @@
       get { return (ILookupParameter<BoolValue>)Parameters["EnoughChildrenGenerated"]; }
     }
-
+    public IValueLookupParameter<ISolutionSimilarityCalculator> SimilarityCalculatorParameter {
+      get { return (IValueLookupParameter<ISolutionSimilarityCalculator>)Parameters["SimilarityCalculator"]; }
+    }
+    public ValueLookupParameter<ResultCollection> ResultsParameter {
+      get { return (ValueLookupParameter<ResultCollection>)Parameters["Results"]; }
+    }
+
+    public ValueLookupParameter<DoubleValue> DiversityComparisonFactorParameter {
+      get { return (ValueLookupParameter<DoubleValue>)Parameters["DiversityComparisonFactor"]; }
+    }
+    private ValueLookupParameter<DoubleValue> ComparisonFactorLowerBoundParameter {
+      get { return (ValueLookupParameter<DoubleValue>)Parameters["DiversityComparisonFactorLowerBound"]; }
+    }
+    private ValueLookupParameter<DoubleValue> ComparisonFactorUpperBoundParameter {
+      get { return (ValueLookupParameter<DoubleValue>)Parameters["DiversityComparisonFactorUpperBound"]; }
+    }
+
+    public IConstrainedValueParameter<IDiscreteDoubleValueModifier> ComparisonFactorModifierParameter {
+      get { return (IConstrainedValueParameter<IDiscreteDoubleValueModifier>)Parameters["ComparisonFactorModifier"]; }
+    }
 
     [StorableConstructor]
-    protected StandardOffspringSelector(bool deserializing) : base(deserializing) { }
-    [StorableHook(HookType.AfterDeserialization)]
-    private void AfterDeserialization() {
-      // BackwardsCompatibility3.3
-      #region Backwards compatible code, remove with 3.4
-      if (Parameters.ContainsKey("FillPopulationWithParents") && Parameters["FillPopulationWithParents"] is FixedValueParameter<BoolValue>)
-        Parameters.Remove("FillPopulationWithParents");
-      if (!Parameters.ContainsKey("FillPopulationWithParents"))
-        Parameters.Add(new ValueLookupParameter<BoolValue>("FillPopulationWithParents", "True if the population should be filled with parent individuals instead of lucky losers."));
-      #endregion
-    }
-
-    protected StandardOffspringSelector(StandardOffspringSelector original, Cloner cloner) : base(original, cloner) { }
+    protected PopDivOffspringSelector(bool deserializing) : base(deserializing) { }
+    protected PopDivOffspringSelector(PopDivOffspringSelector original, Cloner cloner)
+      : base(original, cloner) {
+    }
     public override IDeepCloneable Clone(Cloner cloner) {
-      return new StandardOffspringSelector(this, cloner);
-    }
-    public StandardOffspringSelector()
+      return new PopDivOffspringSelector(this, cloner);
+    }
+    public PopDivOffspringSelector()
       : base() {
       Parameters.Add(new ValueLookupParameter<DoubleValue>("MaximumSelectionPressure", "The maximum selection pressure which prematurely terminates the offspring selection step."));
@@ -89 +109 @@
       Parameters.Add(new ValueLookupParameter<BoolValue>("FillPopulationWithParents", "True if the population should be filled with parent individual or false if worse children should be used when the maximum selection pressure is exceeded."));
       Parameters.Add(new LookupParameter<BoolValue>("EnoughChildrenGenerated", "True if enough children have been generated, otherwise false."));
+      Parameters.Add(new ValueLookupParameter<ISolutionSimilarityCalculator>("SimilarityCalculator", "The similarity calculator that should be used to calculate solution similarity."));
+      Parameters.Add(new ValueLookupParameter<ResultCollection>("Results", "The result collection where the population diversity analysis results should be stored."));
+
+      Parameters.Add(new ValueLookupParameter<DoubleValue>("DiversityComparisonFactor", "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.", new DoubleValue(0.0)));
+      Parameters.Add(new ValueLookupParameter<DoubleValue>("DiversityComparisonFactorLowerBound", "The lower bound of the comparison factor (start).", new DoubleValue(0.5)));
+      Parameters.Add(new ValueLookupParameter<DoubleValue>("DiversityComparisonFactorUpperBound", "The upper bound of the comparison factor (end).", new DoubleValue(1.0)));
+      Parameters.Add(new OptionalConstrainedValueParameter<IDiscreteDoubleValueModifier>("ComparisonFactorModifier", "The operator used to modify the comparison factor.", new ItemSet<IDiscreteDoubleValueModifier>(new IDiscreteDoubleValueModifier[] { new LinearDiscreteDoubleValueModifier() }), new LinearDiscreteDoubleValueModifier()));
+
+
+      foreach (IDiscreteDoubleValueModifier modifier in ApplicationManager.Manager.GetInstances<IDiscreteDoubleValueModifier>().OrderBy(x => x.Name))
+        ComparisonFactorModifierParameter.ValidValues.Add(modifier);
+      IDiscreteDoubleValueModifier linearModifier = ComparisonFactorModifierParameter.ValidValues.FirstOrDefault(x => x.GetType().Name.Equals("LinearDiscreteDoubleValueModifier"));
+      if (linearModifier != null) ComparisonFactorModifierParameter.Value = linearModifier;
+      ParameterizeComparisonFactorModifiers();
+
+      this.AfterExecutionOperators.Clear();
+      this.AfterExecutionOperators.Add(ComparisonFactorModifierParameter.Value);
+      ComparisonFactorModifierParameter.ValueChanged += ComparisonFactorModifierParameter_ValueChanged;
+    }
+
+    void ComparisonFactorModifierParameter_ValueChanged(object sender, EventArgs e) {
+      this.AfterExecutionOperators.Clear();
+      this.AfterExecutionOperators.Add(ComparisonFactorModifierParameter.Value);
+    }
+
+    private void ParameterizeComparisonFactorModifiers() {
+      //TODO: does not work if Generations parameter names are changed
+      foreach (IDiscreteDoubleValueModifier modifier in ComparisonFactorModifierParameter.ValidValues) {
+        modifier.IndexParameter.ActualName = "Generations";
+        modifier.EndIndexParameter.ActualName = "MaximumGenerations";
+        modifier.EndValueParameter.ActualName = ComparisonFactorUpperBoundParameter.Name;
+        modifier.StartIndexParameter.Value = new IntValue(0);
+        modifier.StartValueParameter.ActualName = ComparisonFactorLowerBoundParameter.Name;
+        modifier.ValueParameter.ActualName = "DiversityComparisonFactor";
+      }
     }
 
@@ -112 +167 @@
         currentSuccessRatio = new DoubleValue(0);
         CurrentSuccessRatioParameter.ActualValue = currentSuccessRatio;
+      }
+
+      DataTable successRatioDataTable;
+      if (ResultsParameter.ActualValue.ContainsKey(SuccessRatioChart)) {
+        successRatioDataTable = (DataTable)ResultsParameter.ActualValue[SuccessRatioChart].Value;
+      } else {
+        successRatioDataTable = new DataTable(SuccessRatioChart);
+        successRatioDataTable.Rows.Add(new DataRow(SuccessRatioDataRow));
+        ResultsParameter.ActualValue.Add(new Result(SuccessRatioChart, successRatioDataTable));
       }
 
@@ -129 +193 @@
       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;
@@ -139 +222 @@
         if (tmp == null) throw new InvalidOperationException(Name + ": The variable that indicates whether an offspring is successful or not must contain a BoolValue.");
 
-        // add to population
-        if (tmp.Value) {
+        if (takeWorseOffspring) {
+          IScope currentOffspring = offspring.SubScopes[i];
+          offspring.SubScopes.Remove(currentOffspring);
+          i--;
+          population.Add(currentOffspring);
+          worseOffspringNeeded--;
+        } else if (tmp.Value) {
           IScope currentOffspring = offspring.SubScopes[i];
           offspring.SubScopes.Remove(currentOffspring);
@@ -159 +247 @@
         }
         tmpSelPress += tmpSelPressInc;
-        if (population.Count == populationSize) break;
+        if (population.Count >= populationSize) break;
       }
       successfulOffspring.Value += successfulOffspringAdded;
@@ -166 +254 @@
       selectionPressure.Value = tmpSelPress;
       currentSuccessRatio.Value = successfulOffspring.Value / ((double)populationSize);
-
+      successRatioDataTable.Rows[SuccessRatioDataRow].Values.Add(currentSuccessRatio.Value);
 
       if (EnoughChildrenGeneratedParameter.ActualValue == null) {
@@ -192 +280 @@
         EnoughChildrenGeneratedParameter.ActualValue.Value = true;
       }
+
       return base.InstrumentedApply();
     }