Changeset 3740

Timestamp:

05/10/10 15:10:36 (14 years ago)

Author:

abeham

Message:

#893

• Changed the way offspring selection works
• Added depth parameter to ScopeTreeLookupParameter

Location:

trunk/sources

Files:

• HeuristicLab.Algorithms.OffspringSelectionGeneticAlgorithm/3.3/OffspringSelectionGeneticAlgorithmMainOperator.cs (modified) (3 diffs)
• HeuristicLab.Parameters/3.3/ScopeTreeLookupParameter.cs (modified) (1 diff)
• HeuristicLab.Selection/3.3/OffspringSelector.cs (modified) (5 diffs)

trunk/sources/HeuristicLab.Algorithms.OffspringSelectionGeneticAlgorithm/3.3/OffspringSelectionGeneticAlgorithmMainOperator.cs

@@ -134 +134 @@
       WeightedParentsQualityComparator qualityComparer2 = new WeightedParentsQualityComparator();
       SubScopesRemover subScopesRemover = new SubScopesRemover();
-      ConditionalSelector conditionalSelector = new ConditionalSelector();
       OffspringSelector offspringSelector = new OffspringSelector();
       SubScopesProcessor subScopesProcessor2 = new SubScopesProcessor();
@@ -201 +200 @@
       subScopesRemover.RemoveAllSubScopes = true;
 
-      conditionalSelector.CopySelected = new BoolValue(false);
-      conditionalSelector.ConditionParameter.ActualName = "SuccessfulOffspring";
-
       offspringSelector.CurrentSuccessRatioParameter.ActualName = CurrentSuccessRatioParameter.Name;
-      offspringSelector.LuckyLosersParameter.ActualName = "OSLuckyLosers";
       offspringSelector.MaximumSelectionPressureParameter.ActualName = MaximumSelectionPressureParameter.Name;
       offspringSelector.SelectionPressureParameter.ActualName = SelectionPressureParameter.Name;
       offspringSelector.SuccessRatioParameter.ActualName = SuccessRatioParameter.Name;
-      offspringSelector.WinnersParameter.ActualName = "OSWinners";
+      offspringSelector.OffspringPopulationParameter.ActualName = "OffspringPopulation";
+      offspringSelector.OffspringPopulationWinnersParameter.ActualName = "OffspringPopulationWinners";
+      offspringSelector.SuccessfulOffspringParameter.ActualName = "SuccessfulOffspring";
 
       bestSelector.CopySelected = new BoolValue(false);
@@ -230 +227 @@
       childrenCreator.Successor = uniformSubScopesProcessor;
       uniformSubScopesProcessor.Operator = crossover;
-      uniformSubScopesProcessor.Successor = conditionalSelector;
+      uniformSubScopesProcessor.Successor = null;
       crossover.Successor = osBeforeMutationBranch;
       osBeforeMutationBranch.TrueBranch = evaluator1;

trunk/sources/HeuristicLab.Parameters/3.3/ScopeTreeLookupParameter.cs

@@ -55 +55 @@
       depth = 1;
     }
+    public ScopeTreeLookupParameter(string name, int depth)
+      : base(name) {
+      this.depth = depth;
+    }
     public ScopeTreeLookupParameter(string name, string description)
       : base(name, description) {
       depth = 1;
     }
+    public ScopeTreeLookupParameter(string name, string description, int depth)
+      : base(name, description) {
+      this.depth = depth;
+    }
     public ScopeTreeLookupParameter(string name, string description, string actualName)
       : base(name, description, actualName) {
       depth = 1;
+    }
+    public ScopeTreeLookupParameter(string name, string description, string actualName, int depth)
+      : base(name, description, actualName) {
+      this.depth = depth;
     }
     [StorableConstructor]

trunk/sources/HeuristicLab.Selection/3.3/OffspringSelector.cs

@@ -46 +46 @@
       get { return (LookupParameter<DoubleValue>)Parameters["CurrentSuccessRatio"]; }
     }
-    public LookupParameter<ItemList<IScope>> WinnersParameter {
-      get { return (LookupParameter<ItemList<IScope>>)Parameters["Winners"]; }
+    public LookupParameter<ItemList<IScope>> OffspringPopulationParameter {
+      get { return (LookupParameter<ItemList<IScope>>)Parameters["OffspringPopulation"]; }
     }
-    public LookupParameter<ItemList<IScope>> LuckyLosersParameter {
-      get { return (LookupParameter<ItemList<IScope>>)Parameters["LuckyLosers"]; }
+    public LookupParameter<IntValue> OffspringPopulationWinnersParameter {
+      get { return (LookupParameter<IntValue>)Parameters["OffspringPopulationWinners"]; }
+    }
+    public ScopeTreeLookupParameter<BoolValue> SuccessfulOffspringParameter {
+      get { return (ScopeTreeLookupParameter<BoolValue>)Parameters["SuccessfulOffspring"]; }
     }
     public OperatorParameter OffspringCreatorParameter {
@@ -67 +70 @@
       Parameters.Add(new ValueLookupParameter<DoubleValue>("SelectionPressure", "The amount of selection pressure currently necessary to fulfill the success ratio."));
       Parameters.Add(new ValueLookupParameter<DoubleValue>("CurrentSuccessRatio", "The current success ratio indicates how much of the successful offspring have already been generated."));
-      Parameters.Add(new LookupParameter<ItemList<IScope>>("Winners", "Temporary store of the successful offspring."));
-      Parameters.Add(new LookupParameter<ItemList<IScope>>("LuckyLosers", "Temporary store of the lucky losers."));
+      Parameters.Add(new LookupParameter<ItemList<IScope>>("OffspringPopulation", "Temporary store of the offspring population."));
+      Parameters.Add(new LookupParameter<IntValue>("OffspringPopulationWinners", "Temporary store the number of successful offspring in the offspring population."));
+      Parameters.Add(new ScopeTreeLookupParameter<BoolValue>("SuccessfulOffspring", "True if the offspring was more successful than its parents.", 2));
       Parameters.Add(new OperatorParameter("OffspringCreator", "The operator used to create new offspring."));
     }
@@ -77 +81 @@
       IScope scope = ExecutionContext.Scope;
       IScope parents = scope.SubScopes[0];
-      IScope children = scope.SubScopes[1];
+      IScope offspring = scope.SubScopes[1];
       int populationSize = parents.SubScopes.Count;
+      int offspringSize = offspring.SubScopes.Count;
 
       // retrieve actual selection pressure and success ratio
@@ -92 +97 @@
       }
 
-      // retrieve winners and lucky losers
-      ItemList<IScope> winners = WinnersParameter.ActualValue;
-      if (winners == null) {
-        winners = new ItemList<IScope>();
-        WinnersParameter.ActualValue = winners;
+      // retrieve next population
+      ItemList<IScope> population = OffspringPopulationParameter.ActualValue;
+      IntValue successfulOffspring;
+      if (population == null) {
+        population = new ItemList<IScope>();
+        OffspringPopulationParameter.ActualValue = population;
         selectionPressure.Value = 0; // initialize selection pressure for this round
         currentSuccessRatio.Value = 0; // initialize current success ratio for this round
+        successfulOffspring = new IntValue(0);
+        OffspringPopulationWinnersParameter.ActualValue = successfulOffspring;
+      } else successfulOffspring = OffspringPopulationWinnersParameter.ActualValue;
+      
+      int worseOffspringNeeded = (int)((1 - successRatio) * populationSize) - (population.Count - successfulOffspring.Value);
+      int successfulOffspringAdded = 0;
+
+      // 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;
+      for (int i = 0; i < offspringSize; i++) {
+        // fetch value
+        IVariable tmpVar;
+        if (!offspring.SubScopes[i].Variables.TryGetValue(tname, out tmpVar)) throw new InvalidOperationException(Name + ": Could not determine if an offspring was successful or not.");
+        BoolValue tmp = (tmpVar.Value as BoolValue);
+        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) {
+          population.Add(offspring.SubScopes[i]);
+          successfulOffspringAdded++;
+        } else if (worseOffspringNeeded > 0 || tmpSelPress >= maxSelPress) {
+          population.Add(offspring.SubScopes[i]);
+          worseOffspringNeeded--;
+        }
+        tmpSelPress += tmpSelPressInc;
+        if (population.Count == populationSize) break;
       }
-      ItemList<IScope> luckyLosers = LuckyLosersParameter.ActualValue;
-      if (luckyLosers == null) {
-        luckyLosers = new ItemList<IScope>();
-        LuckyLosersParameter.ActualValue = luckyLosers;
-      }
-
-      // separate new offspring in winners and lucky losers, the unlucky losers are discarded, sorry guys
-      int winnersCount = 0;
-      int losersCount = 0;
-      ScopeList offspring = children.SubScopes[1].SubScopes; // the winners
-      winnersCount += offspring.Count;
-      winners.AddRange(offspring);
-      offspring = children.SubScopes[0].SubScopes; // the losers
-      losersCount += offspring.Count;
-      while (offspring.Count > 0 && ((1 - successRatio) * populationSize > luckyLosers.Count ||
-            selectionPressure.Value >= maxSelPress)) {
-        luckyLosers.Add(offspring[0]);
-        offspring.RemoveAt(0);
-      }
+      successfulOffspring.Value += successfulOffspringAdded;
 
       // calculate actual selection pressure and success ratio
-      selectionPressure.Value += (winnersCount + losersCount) / ((double)populationSize);
-      currentSuccessRatio.Value = winners.Count / ((double)populationSize);
+      selectionPressure.Value += offspringSize / (double)populationSize;
+      currentSuccessRatio.Value = successfulOffspring.Value / ((double)populationSize);
 
       // check if enough children have been generated
       if (((selectionPressure.Value < maxSelPress) && (currentSuccessRatio.Value < successRatio)) ||
-          ((winners.Count + luckyLosers.Count) < populationSize)) {
+          (population.Count < populationSize)) {
         // more children required -> reduce left and start children generation again
         scope.SubScopes.Remove(parents);
-        scope.SubScopes.Remove(children);
+        scope.SubScopes.Remove(offspring);
         while(parents.SubScopes.Count > 0)
           scope.SubScopes.Add(parents.SubScopes[0]);
@@ -138 +153 @@
       } else {
         // enough children generated
-        children.SubScopes.Clear();
-        while (children.SubScopes.Count < populationSize) {
-          if (winners.Count > 0) {
-            children.SubScopes.Add((IScope)winners[0]);
-            winners.RemoveAt(0);
-          } else {
-            children.SubScopes.Add((IScope)luckyLosers[0]);
-            luckyLosers.RemoveAt(0);
-          }
-        }
+        offspring.SubScopes.Clear();
+        offspring.SubScopes.AddRange(population);
 
-        scope.Variables.Remove(WinnersParameter.ActualName);
-        scope.Variables.Remove(LuckyLosersParameter.ActualName);
+        scope.Variables.Remove(OffspringPopulationParameter.ActualName);
+        scope.Variables.Remove(OffspringPopulationWinnersParameter.ActualName);
         return base.Apply();
       }