Changeset 13296

Timestamp:

11/19/15 13:34:42 (9 years ago)

Author:

gkronber

Message:

#2478: merged r13237,r13261 from trunk to stable

Location:

stable

Files:

• . (modified) (1 prop)
• HeuristicLab.Algorithms.OffspringSelectionEvolutionStrategy/3.3/OffspringSelectionEvolutionStrategy.cs (modified) (previous)
• HeuristicLab.Optimization.Operators/3.3/ChildrenCopyCreator.cs (modified) (3 diffs)
• HeuristicLab.Selection/3.3/EvolutionStrategyOffspringSelector.cs (modified) (9 diffs)
• HeuristicLab.Tests (modified) (1 prop)
• HeuristicLab.Tests/HeuristicLab-3.3/Samples/OSESGriewankSampleTest.cs (copied) (copied from trunk/sources/HeuristicLab.Tests/HeuristicLab-3.3/Samples/OSESGriewankSampleTest.cs)
• HeuristicLab.Tests/HeuristicLab-3.3/Samples/SamplesUtils.cs (modified) (3 diffs)
• HeuristicLab.Tests/HeuristicLab.Tests.csproj (modified) (2 diffs)

stable/HeuristicLab.Optimization.Operators/3.3/ChildrenCopyCreator.cs

@@ -20 +20 @@
 #endregion
 
+using System;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -48 +49 @@
     public ChildrenCopyCreator()
       : base() {
-      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope whose sub-scopes represent the parents."));
+      Parameters.Add(new ScopeParameter("CurrentScope", "The current scope whose sub-scopes should be copied."));
     }
 
@@ -56 +57 @@
 
     public override IOperation Apply() {
-      int parents = CurrentScope.SubScopes.Count;
+      int nChildren = CurrentScope.SubScopes.Count;
 
-      for (int i = 0; i < parents; i++) {
-        IScope parent = CurrentScope.SubScopes[i];
-        parent.SubScopes.Clear();
+      for (int i = 0; i < nChildren; i++) {
+        IScope child = CurrentScope.SubScopes[i];
+        if (child.SubScopes.Count > 0) throw new ArgumentException("The sub-scope that should be cloned has further sub-scopes.");
 
-        //copy parent
-        IScope child = new Scope(i.ToString());
-        foreach (IVariable var in parent.Variables)
-          child.Variables.Add((IVariable)var.Clone());
+        IScope childCopy = new Scope(i.ToString());
+        var cloner = new Cloner();
+        foreach (IVariable var in child.Variables)
+          childCopy.Variables.Add(cloner.Clone(var));
 
-        parent.SubScopes.Add(child);
+        child.SubScopes.Add(childCopy);
       }
       return base.Apply();

stable/HeuristicLab.Selection/3.3/EvolutionStrategyOffspringSelector.cs

@@ -22 +22 @@
 using System;
 using System.Collections.Generic;
+using System.Runtime.InteropServices;
 using HeuristicLab.Common;
 using HeuristicLab.Core;
@@ -34 +35 @@
   public class EvolutionStrategyOffspringSelector : SingleSuccessorOperator {
 
-    private class QualityComparer : IComparer<IScope> {
+    private class FitnessComparer : IComparer<IScope> {
 
       #region IComparer<IScope> Member
 
       private String qualityParameterName;
-
-      public QualityComparer(String qualityParamName) {
+      private bool maximization;
+
+      public FitnessComparer(String qualityParamName, bool maximization) {
         this.qualityParameterName = qualityParamName;
-      }
-
+        this.maximization = maximization;
+      }
+
+      // less than zero if x is-better-than y 
+      // larger than zero if y is-better-than x
+      // zero if both are the same
       public int Compare(IScope x, IScope y) {
-          IVariable quality1, quality2;
-
-          if (x.Variables.TryGetValue(qualityParameterName, out quality1)
-            && y.Variables.TryGetValue(qualityParameterName, out quality2)) {
-            DoubleValue dblVal = quality1.Value as DoubleValue;
-            DoubleValue dblVal2 = quality2.Value as DoubleValue;
-            return dblVal.CompareTo(dblVal2);
-          }
-          else
-            throw new Exception("ERROR!!! Quality Param: "+qualityParameterName);
+        IVariable quality1, quality2;
+
+        if (x.Variables.TryGetValue(qualityParameterName, out quality1)
+          && y.Variables.TryGetValue(qualityParameterName, out quality2)) {
+          DoubleValue left = quality1.Value as DoubleValue;
+          DoubleValue right = quality2.Value as DoubleValue;
+          var res = left.CompareTo(right);
+          if (maximization) return -res; // in the maximization case the largest value should preceed all others in the sort order
+          else return res;
+        } else
+          throw new ArgumentException("Quality variable " + qualityParameterName + " not found.");
       }
 
@@ -95 +102 @@
     public ILookupParameter<DoubleValue> QualityParameter {
       get { return (ILookupParameter<DoubleValue>)Parameters["Quality"]; }
+    }
+    public ILookupParameter<BoolValue> MaximizationParameter {
+      get { return (ILookupParameter<BoolValue>)Parameters["Maximization"]; }
     }
 
@@ -119 +129 @@
       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."));
-      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of times solutions have been evaluated."));
+      Parameters.Add(new LookupParameter<IntValue>("EvaluatedSolutions", "The number of solution evaluations."));
       Parameters.Add(new LookupParameter<IntValue>("MaximumEvaluatedSolutions", "The maximum number of evaluated solutions (approximately)."));
       Parameters.Add(new LookupParameter<DoubleValue>("Quality", "The quality of a child"));
+      Parameters.Add(new LookupParameter<BoolValue>("Maximization", "Flag that indicates if the problem is a maximization problem"));
     }
 
@@ -165 +176 @@
       // 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;
+      double tmpSelPress = selectionPressure.Value;
+      double tmpSelPressInc = 1.0 / populationSize;
       for (int i = 0; i < offspring.SubScopes.Count; i++) {
         // fetch value
@@ -176 +188 @@
         if (tmp.Value) {
           IScope currentOffspring = offspring.SubScopes[i];
-          offspring.SubScopes.Remove(currentOffspring);
-          i--;
+          offspring.SubScopes.RemoveAt(i);
+          i--; // next loop should continue with the subscope at index i which replaced currentOffspring
           population.Add(currentOffspring);
           successfulOffspringAdded++;
-        }
-        else {
+        } else {
           IScope currentOffspring = offspring.SubScopes[i];
-          offspring.SubScopes.Remove(currentOffspring);
+          offspring.SubScopes.RemoveAt(i);
           i--;
-          virtual_population.Add(currentOffspring);
+          virtual_population.Add(currentOffspring); // add to losers pool
         }
         tmpSelPress += tmpSelPressInc;
 
-        double tmpSuccessRatio = (successfulOffspring.Value+successfulOffspringAdded) / ((double)populationSize);
+        double tmpSuccessRatio = (successfulOffspring.Value + successfulOffspringAdded) / ((double)populationSize);
         if (tmpSuccessRatio >= successRatio && (population.Count + virtual_population.Count) >= populationSize)
           break;
@@ -200 +211 @@
 
       // check if enough children have been generated (or limit of selection pressure or evaluted solutions is reached)
-      if (((EvaluatedSolutionsParameter.ActualValue.Value < MaximumEvaluatedSolutionsParameter.ActualValue.Value) 
-          && (selectionPressure.Value < maxSelPress) 
-          && (currentSuccessRatio.Value < successRatio)) 
+      if (((EvaluatedSolutionsParameter.ActualValue.Value < MaximumEvaluatedSolutionsParameter.ActualValue.Value)
+          && (selectionPressure.Value < maxSelPress)
+          && (currentSuccessRatio.Value < successRatio))
         || ((population.Count + virtual_population.Count) < populationSize)) {
         // more children required -> reduce left and start children generation again
@@ -209 +220 @@
         while (parents.SubScopes.Count > 0) {
           IScope parent = parents.SubScopes[0];
-          parents.SubScopes.RemoveAt(0);
-          scope.SubScopes.Add(parent);
-        }
-
-        IOperator moreOffspring = OffspringCreatorParameter.ActualValue as IOperator;
-        if (moreOffspring == null) throw new InvalidOperationException(Name + ": More offspring are required, but no operator specified for creating them.");
-        return ExecutionContext.CreateOperation(moreOffspring);
+          parents.SubScopes.RemoveAt(0); // TODO: repeated call of RemoveAt(0) is inefficient?
+          scope.SubScopes.Add(parent); // order of subscopes is reversed
+        }
+
+        IOperator offspringCreator = OffspringCreatorParameter.ActualValue as IOperator;
+        if (offspringCreator == null) throw new InvalidOperationException(Name + ": More offspring are required, but no operator specified for creating them.");
+        return ExecutionContext.CreateOperation(offspringCreator); // this assumes that this operator will be called again indirectly or directly
       } else {
         // enough children generated
-        QualityComparer qualityComparer = new QualityComparer(QualityParameter.TranslatedName);
-        population.Sort(qualityComparer);
-
-        //only keep minimum best successful children in population
+        var fitnessComparer = new FitnessComparer(QualityParameter.TranslatedName, MaximizationParameter.ActualValue.Value);
+        population.Sort(fitnessComparer); // sort individuals by descending fitness
+
+        // keeps only the best successRatio * populationSize solutions in the population (the remaining ones are added to the virtual population)
         int removed = 0;
         for (int i = 0; i < population.Count; i++) {
           double tmpSuccessRatio = i / (double)populationSize;
           if (tmpSuccessRatio > successRatio) {
-              virtual_population.Add(population[i]);
-              removed++;
+            virtual_population.Add(population[i]);
+            removed++;
           }
         }
@@ -233 +244 @@
 
         //fill up population with best remaining children (successful or unsuccessful)
-        virtual_population.Sort(qualityComparer);
+        virtual_population.Sort(fitnessComparer);
         int offspringNeeded = populationSize - population.Count;
         for (int i = 0; i < offspringNeeded && i < virtual_population.Count; i++) {
-          population.Add(virtual_population[i]);
+          population.Add(virtual_population[i]); // children are sorted by descending fitness
         }
 

stable/HeuristicLab.Tests/HeuristicLab-3.3/Samples/SamplesUtils.cs

@@ -5 +5 @@
 using HeuristicLab.Algorithms.EvolutionStrategy;
 using HeuristicLab.Algorithms.GeneticAlgorithm;
+using HeuristicLab.Algorithms.OffspringSelectionEvolutionStrategy;
 using HeuristicLab.Algorithms.OffspringSelectionGeneticAlgorithm;
 using HeuristicLab.Data;
@@ -71 +72 @@
     }
 
+    public static void ConfigureOffspringSelectionEvolutionStrategyParameters<R, M, SC, SR, SM>(OffspringSelectionEvolutionStrategy es, int popSize,
+      double successRatio, double comparisonFactor, double maxSelPres, int parentsPerChild, int maxGens, bool plusSelection)
+      where R : ICrossover
+      where M : IManipulator
+      where SC : IStrategyParameterCreator
+      where SR : IStrategyParameterCrossover
+      where SM : IStrategyParameterManipulator {
+      es.PopulationSize.Value = popSize;
+      es.ComparisonFactor.Value = comparisonFactor;
+      es.SuccessRatio.Value = successRatio;
+      es.MaximumSelectionPressure.Value = maxSelPres;
+      es.ParentsPerChild.Value = parentsPerChild;
+      es.SelectedParents.Value = popSize * parentsPerChild;
+      es.MaximumGenerations.Value = maxGens;
+      es.PlusSelection.Value = false;
+
+      es.Seed.Value = 0;
+      es.SetSeedRandomly.Value = true;
+
+      es.Recombinator = es.RecombinatorParameter.ValidValues
+        .OfType<R>()
+        .Single();
+
+      es.Mutator = es.MutatorParameter.ValidValues
+        .OfType<M>()
+        .Single();
+
+      es.StrategyParameterCreator = es.StrategyParameterCreatorParameter.ValidValues
+        .OfType<SC>()
+        .Single();
+      es.StrategyParameterCrossover = es.StrategyParameterCrossoverParameter.ValidValues
+        .OfType<SR>()
+        .Single();
+      es.StrategyParameterManipulator = es.StrategyParameterManipulatorParameter.ValidValues
+        .OfType<SM>()
+        .Single();
+      es.Engine = new ParallelEngine.ParallelEngine();
+    }
+
     public static void ConfigureGeneticAlgorithmParameters<S, C, M>(GeneticAlgorithm ga, int popSize, int elites, int maxGens, double mutationRate, int tournGroupSize = 0)
       where S : ISelector
@@ -194 +234 @@
 
       ga.MaximumGenerations = maxGens;
-      
+
       ga.Engine = new ParallelEngine.ParallelEngine();
     }

stable/HeuristicLab.Tests/HeuristicLab.Tests.csproj

@@ -131 +131 @@
     <Reference Include="HeuristicLab.Algorithms.LocalSearch-3.3">
       <HintPath>..\bin\HeuristicLab.Algorithms.LocalSearch-3.3.dll</HintPath>
+      <Private>False</Private>
+    </Reference>
+    <Reference Include="HeuristicLab.Algorithms.OffspringSelectionEvolutionStrategy-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
+      <HintPath>..\bin\HeuristicLab.Algorithms.OffspringSelectionEvolutionStrategy-3.3.dll</HintPath>
       <Private>False</Private>
     </Reference>
@@ -436 +440 @@
     <Compile Include="HeuristicLab-3.3\PluginLoader.cs" />
     <Compile Include="HeuristicLab-3.3\Samples\AlpsSampleTest.cs" />
+    <Compile Include="HeuristicLab-3.3\Samples\OSESGriewankSampleTest.cs" />
     <Compile Include="HeuristicLab-3.3\Samples\GAGroupingProblemSampleTest.cs" />
     <Compile Include="HeuristicLab-3.3\Samples\VnsOpSampleTest.cs" />