Changeset 18233

Timestamp:

03/10/22 09:53:58 (3 years ago)

Author:

pfleck

Message:

#3040 Added Guided Direction Mutation for nested Optimizers.

Location:

branches/3040_VectorBasedGP

Files:

• HeuristicLab.Encodings.IntegerVectorEncoding/3.3/Manipulators/UniformOnePositionManipulator.cs (modified) (1 diff)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Mutators/NestedOptimizerSubVectorImprovementManipulator.cs (modified) (7 diffs)
• HeuristicLab.Problems.Instances.DataAnalysis/3.3/SegmentOptimization/SegmentOptimizationInstanceProvider.cs (modified) (1 diff)

branches/3040_VectorBasedGP/HeuristicLab.Encodings.IntegerVectorEncoding/3.3/Manipulators/UniformOnePositionManipulator.cs

@@ -93 +93 @@
         // but 99 is not a feasible value, so max needs to be adjusted => min = 0, max = 95
         max = FloorFeasible(min, max, step, max - 1);
-        vector[index] = RoundFeasible(min, max, step, random.Next(min, max));
+        if (min == max)
+          vector[index] = min;
+        else
+          vector[index] = RoundFeasible(min, max, step, random.Next(min, max));
       }
     }

branches/3040_VectorBasedGP/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Mutators/NestedOptimizerSubVectorImprovementManipulator.cs

@@ -26 +26 @@
     [Item("SubVectorOptimizationProblem", "")]
     [StorableType("EA3D3221-B274-4F2F-8B58-23CB2D091FD7")]
-    private class SubVectorOptimizationProblem : SingleObjectiveBasicProblem<IntegerVectorEncoding> {
+    public class SubVectorOptimizationProblem : SingleObjectiveBasicProblem<IntegerVectorEncoding> {
       #region Fixed Problem Parameters
       [Storable]
@@ -45 +45 @@
       #endregion
 
+      private IFixedValueParameter<BoolValue> UseCacheParameter {
+        get { return (IFixedValueParameter<BoolValue>)Parameters["UseCache"]; }
+      }
+
+      public bool UseCache {
+        get { return UseCacheParameter.Value.Value; }
+        set { UseCacheParameter.Value.Value = value; }
+      }
+
+      private readonly IDictionary<IntegerVector, double> cache;
+      
       public override bool Maximization { get { return false; } }
 
@@ -50 +61 @@
         Encoding = new IntegerVectorEncoding("bounds");
         Parameters.Add(new ResultParameter<IntegerVector>(BestSolutionParameterName, ""));
-      }
+
+        Parameters.Add(new FixedValueParameter<BoolValue>("UseCache", new BoolValue(true)));
+        cache = new Dictionary<IntegerVector, double>(new IntegerVectorEqualityComparer());
+      }
+
       private SubVectorOptimizationProblem(SubVectorOptimizationProblem original, Cloner cloner)
-        : base(original, cloner) { }
+        : base(original, cloner) {
+        this.cache = new Dictionary<IntegerVector, double>(original.cache, new IntegerVectorEqualityComparer());
+      }
       public override IDeepCloneable Clone(Cloner cloner) {
         return new SubVectorOptimizationProblem(this, cloner);
       }
+
       [StorableConstructor]
-      private SubVectorOptimizationProblem(StorableConstructorFlag _) : base(_) { }
+      private SubVectorOptimizationProblem(StorableConstructorFlag _) : base(_) {
+        cache = new Dictionary<IntegerVector, double>(new IntegerVectorEqualityComparer());
+      }
+      [StorableHook(HookType.AfterDeserialization)]
+      private void AfterDeserialization() {
+        if (!Parameters.ContainsKey("UseCache"))
+          Parameters.Add(new FixedValueParameter<BoolValue>("UseCache", new BoolValue(true)));
+      }
 
       public override double Evaluate(Individual individual, IRandom random) {
-        var solution = individual.IntegerVector(Encoding.Name);
+        return Evaluate(individual.IntegerVector(Encoding.Name));
+      }
+
+      public double Evaluate(IntegerVector solution) {
+        if (UseCache && cache.TryGetValue(solution, out double cachedQuality)) {
+          return cachedQuality;
+        }
 
         var updatedTree = (ISymbolicExpressionTree)tree.Clone();
         UpdateFromVector(updatedTree, selectedSubVectorNodes, solution, Encoding.Bounds[0, 1]);
-        
+
         var quality = evaluator.Evaluate(executionContext, updatedTree, problemData, rows);
         if (evaluator.Maximization)
           quality = -quality;
+
+        if (UseCache) {
+          cache.Add(solution, quality);
+        }
+
         return quality;
       }
@@ -83 +119 @@
         this.rows = rows;
         this.executionContext = executionContext;
+        cache.Clear();
       }
       public void SetInstanceData(ISymbolicExpressionTree tree, List<int> selectedSubVectorNodes, int vectorLength) {
@@ -88 +125 @@
         this.selectedSubVectorNodes = selectedSubVectorNodes;
         Encoding.Length = selectedSubVectorNodes.Count * 2;
-        Encoding.Bounds = new IntMatrix(new int[,] { { 0, vectorLength } });
-      }
-    }
-
+        Encoding.Bounds = new IntMatrix(new int[,] { { 0, vectorLength + 1 } });
+        cache.Clear();
+      }
+    }
+
+    [Item("SubVectorGradientMutator", "")]
+    [StorableType("DC5EC7CE-AD51-4655-8F75-28601345B4C7")]
+    public abstract class SubVectorGradientMutator : BoundedIntegerVectorManipulator {
+
+      [Storable]
+      private readonly SubVectorOptimizationProblem problem;
+
+      protected SubVectorGradientMutator(SubVectorOptimizationProblem problem) {
+        this.problem = problem;
+      }
+      protected SubVectorGradientMutator(SubVectorGradientMutator original, Cloner cloner)
+        : base(original, cloner) {
+        this.problem = cloner.Clone(original.problem);
+      }
+
+      [StorableConstructor]
+      protected SubVectorGradientMutator(StorableConstructorFlag _) : base(_) {
+      }
+      [StorableHook(HookType.AfterDeserialization)]
+      private void AfterDeserialization() {
+      }
+
+      public double FivePointStencil(IntegerVector position, int dim, IntMatrix bounds, int h = 1) {
+        double f(int i) {
+          var modified = new IntegerVector(position);
+          modified[dim] = FloorFeasible(bounds[dim % bounds.Rows, 0], bounds[dim % bounds.Rows, 1], 1, i);
+          return problem.Evaluate(modified);
+        }
+
+        int x = position[dim];
+        var slope = (
+            + 1 * f(x - 2*h)
+            - 8 * f(x - 1*h)
+            + 8 * f(x + 1*h)
+            - 1 * f(x + 2*h)
+          ) / 12;
+
+        return slope;
+      }
+
+      public double[] CalculateGradient(IntegerVector position, IntMatrix bounds, int h = 1) {
+        return Enumerable.Range(0, position.Length)
+          .Select((x, dim) => FivePointStencil(position, dim, bounds, h)).ToArray();
+      }
+    }
+
+    [Item("GuidedDirectionManipulator", "")]
+    [StorableType("8781F827-BB46-4041-AAC4-25E76C5EF1F5")]
+    public class GuidedDirectionManipulator : SubVectorGradientMutator {
+
+      [StorableType("AED631BC-C1A3-4408-AA39-18A81018E159")]
+      public enum MutationType {
+        SinglePosition,
+        AllPosition
+      }
+
+      public IFixedValueParameter<EnumValue<MutationType>> MutationTypeParameter {
+        get { return (IFixedValueParameter<EnumValue<MutationType>>)Parameters["MutationType"]; }
+      }
+
+      public GuidedDirectionManipulator(SubVectorOptimizationProblem problem)
+      : base (problem) {
+        Parameters.Add(new FixedValueParameter<EnumValue<MutationType>>("MutationType", new EnumValue<MutationType>(MutationType.AllPosition)));
+      }
+
+      protected GuidedDirectionManipulator(GuidedDirectionManipulator original, Cloner cloner)
+        : base(original, cloner) {
+      }
+      public override IDeepCloneable Clone(Cloner cloner) {
+        return new GuidedDirectionManipulator(this, cloner);
+      }
+
+      [StorableConstructor]
+      protected GuidedDirectionManipulator(StorableConstructorFlag _) : base(_) {
+      }
+      [StorableHook(HookType.AfterDeserialization)]
+      private void AfterDeserialization() {
+      }
+
+      protected override void ManipulateBounded(IRandom random, IntegerVector integerVector, IntMatrix bounds) {
+        if (MutationTypeParameter.Value.Value == MutationType.AllPosition) {
+          var gradient = CalculateGradient(integerVector, bounds);
+          var limitedBounds = LimitBounds(bounds, integerVector, gradient);
+          UniformSomePositionsManipulator.Apply(random, integerVector, limitedBounds, probability: 1.0);
+        } else if(MutationTypeParameter.Value.Value == MutationType.SinglePosition) {
+          int dim = random.Next(integerVector.Length);
+          var gradient = Enumerable.Repeat(0.0, integerVector.Length).ToArray();
+          gradient[dim] = FivePointStencil(integerVector, dim, bounds);
+          var limitedBounds = LimitBounds(bounds, integerVector, gradient);
+          UniformOnePositionManipulator.Manipulate(random, integerVector, limitedBounds, dim);
+        }
+      }
+
+      private static IntMatrix LimitBounds(IntMatrix bounds, IntegerVector position, double[] gradient) {
+        var limitedBounds = new IntMatrix(gradient.Length, 2);
+        for (int i = 0; i < gradient.Length; i++) {
+          limitedBounds[i, 0] = gradient[i] < 0 ? position[i] + 0 : bounds[i % bounds.Rows, 0];
+          limitedBounds[i, 1] = gradient[i] > 0 ? position[i] + 1 : bounds[i % bounds.Rows, 1];
+        }
+        return limitedBounds;
+      }
+    }
 
     #region Parameter Properties
@@ -131 +271 @@
       };
       es.Mutator = es.MutatorParameter.ValidValues.OfType<UniformSomePositionsManipulator>().Single();
+
+      var gdes = new EvolutionStrategy() {
+        Problem = problem,
+        PlusSelection = new BoolValue(true),
+        PopulationSize = new IntValue(10),
+        Children = new IntValue(10),
+        MaximumGenerations = new IntValue(100)
+      };
+      gdes.Name = "Guided Direction " + gdes.Name;
+      var gdMutator = new GuidedDirectionManipulator(problem);
+      problem.Encoding.ConfigureOperator(gdMutator);
+      gdes.MutatorParameter.ValidValues.Add(gdMutator);
+      gdes.Mutator = gdMutator;
 
       var ga = new GeneticAlgorithm() {
@@ -156 +309 @@
       #endregion
 
-      var optimizers = new ItemSet<IAlgorithm>() { rs, es, ga, osga };
+      var optimizers = new ItemSet<IAlgorithm>() { rs, es, gdes, ga, osga };
 
       Parameters.Add(new OptionalConstrainedValueParameter<IAlgorithm>("NestedOptimizer", optimizers, rs));

branches/3040_VectorBasedGP/HeuristicLab.Problems.Instances.DataAnalysis/3.3/SegmentOptimization/SegmentOptimizationInstanceProvider.cs

@@ -182 +182 @@
   }
 
+  public class SegmentOptimizationLargeNoNoiseFileInstanceProvider : SegmentOptimizationLargeFileInstanceProvider {
+    public override string Name {
+      get { return "SOP Large File NoNoise"; }
+    }
+
+    public override string Description {
+      get { return "SOP Large File NoNoise"; }
+    }
+    
+    public override IEnumerable<IDataDescriptor> GetDataDescriptors() {
+      return base.GetDataDescriptors().Select(id => {
+        var descriptor = (SOPDataDescriptor)id;
+        descriptor.Name += "_m";
+        descriptor.VariableName += "_m";
+        return descriptor;
+      });
+    }
+  }
+
   public class SegmentOptimizationCombinationsLargeFileInstanceProvider : SegmentOptimizationFileInstanceProvider {
     public override string Name {