Changeset 18235

Timestamp:

03/14/22 11:37:51 (3 years ago)

Author:

pfleck

Message:

#3040 Added GuidedRangeManipulator for nested index optimization.

Location:

branches/3040_VectorBasedGP

Files:

• HeuristicLab.Encodings.IntegerVectorEncoding/3.3/Manipulators/UniformOnePositionManipulator.cs (modified) (2 diffs)
• HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Mutators/NestedOptimizerSubVectorImprovementManipulator.cs (modified) (6 diffs)

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

@@ -85 +85 @@
       if (bounds == null || bounds.Rows == 0 || bounds.Columns < 2) throw new ArgumentException("UniformOnePositionManipulator: Invalid bounds specified", "bounds");
       int min = bounds[index % bounds.Rows, 0], max = bounds[index % bounds.Rows, 1], step = 1;
-      if (min == max) {
+      if (min == max || min == max - 1) {
         vector[index] = min;
       } else {
@@ -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);
-        if (min == max)
-          vector[index] = min;
-        else
-          vector[index] = RoundFeasible(min, max, step, random.Next(min, max));
+        vector[index] = RoundFeasible(min, max, step, random.Next(min, max + 1));
       }
     }

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

@@ -210 +210 @@
 
       protected override void ManipulateBounded(IRandom random, IntegerVector integerVector, IntMatrix bounds) {
-        if (MutationTypeParameter.Value.Value == MutationType.AllPosition) {
+        var mutationType = MutationTypeParameter.Value.Value;
+
+        if (mutationType == 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) {
+        } else if(mutationType == MutationType.SinglePosition) {
           int dim = random.Next(integerVector.Length);
           var gradient = Enumerable.Repeat(0.0, integerVector.Length).ToArray();
@@ -226 +228 @@
         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];
+          int min = bounds[i % bounds.Rows, 0], max = bounds[i % bounds.Rows, 1];
+          int lower = gradient[i] < 0 ? position[i] - 1 : min; // exclude current
+          int upper = gradient[i] > 0 ? position[i] + 1 : max; // exclude current
+          limitedBounds[i, 0] = RoundFeasible(min, max, 1, lower); 
+          limitedBounds[i, 1] = RoundFeasible(min, max, 1, upper);
+        }
+        return limitedBounds;
+      }
+    }
+
+    [Item("GuidedDirectionManipulator", "")]
+    [StorableType("3034E82F-FE7B-4723-90E6-887AE82BB86D")]
+    public class GuidedRangeManipulator : SubVectorGradientMutator {
+
+      [StorableType("560E2F2A-2B34-48CC-B747-DE82119DA652")]
+      public enum MutationType {
+        SinglePosition,
+        AllPosition
+      }
+
+      public IFixedValueParameter<EnumValue<MutationType>> MutationTypeParameter {
+        get { return (IFixedValueParameter<EnumValue<MutationType>>)Parameters["MutationType"]; }
+      }
+      public IFixedValueParameter<DoubleRange> StepSizeParameter {
+        get { return (IFixedValueParameter<DoubleRange>)Parameters["StepSize"]; }
+      }
+      public IFixedValueParameter<IntValue> RangeParameter {
+        get { return (IFixedValueParameter<IntValue>)Parameters["Range"]; }
+      }
+
+      public GuidedRangeManipulator(SubVectorOptimizationProblem problem)
+      : base(problem) {
+        Parameters.Add(new FixedValueParameter<EnumValue<MutationType>>("MutationType", new EnumValue<MutationType>(MutationType.AllPosition)));
+        Parameters.Add(new FixedValueParameter<DoubleRange>("StepSize", new DoubleRange(0.001, 1000.0)));
+        Parameters.Add(new FixedValueParameter<IntValue>("Range", new IntValue(10)));
+      }
+
+      protected GuidedRangeManipulator(GuidedRangeManipulator original, Cloner cloner)
+        : base(original, cloner) {
+      }
+      public override IDeepCloneable Clone(Cloner cloner) {
+        return new GuidedRangeManipulator(this, cloner);
+      }
+
+      [StorableConstructor]
+      protected GuidedRangeManipulator(StorableConstructorFlag _) : base(_) {
+      }
+      [StorableHook(HookType.AfterDeserialization)]
+      private void AfterDeserialization() {
+      }
+
+      protected override void ManipulateBounded(IRandom random, IntegerVector integerVector, IntMatrix bounds) {
+        var mutationType = MutationTypeParameter.Value.Value;
+        var stepSizeRange = StepSizeParameter.Value;
+        var range = RangeParameter.Value.Value;
+
+        var stepSize = LogUniformRandom(stepSizeRange, random);
+
+        if (mutationType == MutationType.AllPosition) {
+          var gradient = CalculateGradient(integerVector, bounds);
+          var limitedBounds = LimitBounds(bounds, integerVector, gradient, stepSize, range);
+          UniformSomePositionsManipulator.Apply(random, integerVector, limitedBounds, probability: 1.0);
+        } else if (mutationType == 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, stepSize, range);
+          UniformOnePositionManipulator.Manipulate(random, integerVector, limitedBounds, dim);
+        }
+      }
+
+      private static double LogUniformRandom(DoubleRange range, IRandom random) {
+        double logStart = Math.Log(range.Start);
+        double logEnd = Math.Log(range.End);
+        double logResult = logStart + random.NextDouble() * (logEnd - logStart);
+        return Math.Exp(logResult);
+      }
+
+      private static IntMatrix LimitBounds(IntMatrix bounds, IntegerVector position, double[] gradient, double stepSize, int range) {
+        var limitedBounds = new IntMatrix(gradient.Length, 2);
+        for (int i = 0; i < gradient.Length; i++) {
+          int min = bounds[i % bounds.Rows, 0], max = bounds[i % bounds.Rows, 1];
+          var newPoint = position[i] - gradient[i] * stepSize;
+          var lower = newPoint - range / 2.0;
+          var upper = newPoint + range / 2.0;
+          limitedBounds[i, 0] = RoundFeasible(min, max, 1, lower);
+          limitedBounds[i, 1] = RoundFeasible(min, max, 1, upper);
         }
         return limitedBounds;
@@ -284 +371 @@
       gdes.MutatorParameter.ValidValues.Add(gdMutator);
       gdes.Mutator = gdMutator;
+
+      var gres = new EvolutionStrategy() {
+        Problem = problem,
+        PlusSelection = new BoolValue(true),
+        PopulationSize = new IntValue(10),
+        Children = new IntValue(10),
+        MaximumGenerations = new IntValue(100)
+      };
+      gres.Name = "Guided Range " + gres.Name;
+      var grMutator = new GuidedRangeManipulator(problem);
+      problem.Encoding.ConfigureOperator(grMutator);
+      gres.MutatorParameter.ValidValues.Add(grMutator);
+      gres.Mutator = grMutator;
 
       var ga = new GeneticAlgorithm() {
@@ -309 +409 @@
       #endregion
 
-      var optimizers = new ItemSet<IAlgorithm>() { rs, es, gdes, ga, osga };
+      var optimizers = new ItemSet<IAlgorithm>() { rs, es, gdes, gres, ga, osga };
 
       Parameters.Add(new OptionalConstrainedValueParameter<IAlgorithm>("NestedOptimizer", optimizers, rs));
@@ -325 +425 @@
     [StorableHook(HookType.AfterDeserialization)]
     private void AfterDeserialization() {
-      if (Parameters.TryGetValue("NestedOptimizer", out var param)) {
-        if (param is ConstrainedValueParameter<IAlgorithm> constrainedParam) {
-          Parameters.Remove("NestedOptimizer");
-          Parameters.Add(new OptionalConstrainedValueParameter<IAlgorithm>("NestedOptimizer", 
-            new ItemSet<IAlgorithm>(constrainedParam.ValidValues), constrainedParam.Value)
-          );
-        }
+      if (Parameters.TryGetValue("NestedOptimizer", out var param) && param is ConstrainedValueParameter<IAlgorithm> constrainedParam) {
+        Parameters.Remove("NestedOptimizer");
+        Parameters.Add(new OptionalConstrainedValueParameter<IAlgorithm>("NestedOptimizer", 
+          new ItemSet<IAlgorithm>(constrainedParam.ValidValues), constrainedParam.Value)
+        );
       }
     }
@@ -371 +469 @@
 
       int numSelect = (int)Math.Round(subVectorNodes.Count * PercentOptimizedSubVectorNodes.Value);
-      var selectedSubVectorNodes = Enumerable.Range(0, subVectorNodes.Count).SampleRandomWithoutRepetition(random, numSelect).ToList();
-      return selectedSubVectorNodes;
+      var selectedSubVectorNodes = Enumerable.Range(0, subVectorNodes.Count).SampleRandomWithoutRepetition(random, numSelect);
+      return selectedSubVectorNodes.ToList();
     }