Changeset 17768 for branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IABoundsEstimator.cs

Timestamp:

10/02/20 11:36:34 (4 years ago)

Author:

chaider

Message:

#3073

• Removed Region class and used IntervallCollection instead
• Changed Parser to work with IntervalColletions
• Moved CheckConstraint methods from Analyzer to IntervalUtil class
• Added CheckConstraint method to interface to check if an interval is in a given constraint
• Added possibility to stop splitting as soon as a constraint is fulfiled

File:

• branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IABoundsEstimator.cs (modified) (15 diffs)

branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IABoundsEstimator.cs

@@ -3 +3 @@
 using System.Collections.ObjectModel;
 using System.Linq;
-using System.Text;
-using System.Threading.Tasks;
 using HEAL.Attic;
 using HeuristicLab.Common;
@@ -15 +13 @@
   [StorableType("C8539434-6FB0-47D0-9F5A-2CAE5D8B8B4F")]
   [Item("IA Bounds Estimator", "Interpreter for calculation of intervals of symbolic models.")]
-  public sealed class IABoundsEstimator : ParameterizedNamedItem, IBoundsEstimator{
+  public sealed class IABoundsEstimator : ParameterizedNamedItem, IBoundsEstimator {
     #region Parameters
 
@@ -54 +52 @@
       set => SplittingWidthParameter.Value.Value = value;
     }
+
     #endregion
 
@@ -60 +59 @@
     [StorableConstructor]
     private IABoundsEstimator(StorableConstructorFlag _) : base(_) { }
-        
+
     private IABoundsEstimator(IABoundsEstimator original, Cloner cloner) : base(original, cloner) { }
 
-    public IABoundsEstimator() : base("IA Bounds Estimator", "Estimates the bounds of the model with interval arithmetic") {
-      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName, "A counter for the total number of solutions the estimator has evaluated.", new IntValue(0)));
-      Parameters.Add(new FixedValueParameter<BoolValue>(UseIntervalSplittingParameterName, "Defines whether interval splitting is activated or not.", new BoolValue(false)));
-      Parameters.Add(new FixedValueParameter<IntValue>(SplittingIterationsParameterName, "Defines the number of iterations of splitting.", new IntValue(200)));
-      Parameters.Add(new FixedValueParameter<DoubleValue>(SplittingWidthParameterName, "Width of interval, after the splitting should stop.", new DoubleValue(0.0)));
+    public IABoundsEstimator() : base("IA Bounds Estimator",
+      "Estimates the bounds of the model with interval arithmetic") {
+      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName,
+        "A counter for the total number of solutions the estimator has evaluated.", new IntValue(0)));
+      Parameters.Add(new FixedValueParameter<BoolValue>(UseIntervalSplittingParameterName,
+        "Defines whether interval splitting is activated or not.", new BoolValue(false)));
+      Parameters.Add(new FixedValueParameter<IntValue>(SplittingIterationsParameterName,
+        "Defines the number of iterations of splitting.", new IntValue(200)));
+      Parameters.Add(new FixedValueParameter<DoubleValue>(SplittingWidthParameterName,
+        "Width of interval, after the splitting should stop.", new DoubleValue(0.0)));
     }
 
@@ -74 +78 @@
     }
 
-        #endregion
+    #endregion
 
     #region IStatefulItem Members
@@ -86 +90 @@
     public void ClearState() { }
 
-        #endregion
+    #endregion
 
     #region Evaluation
@@ -261 +265 @@
     }
 
-        #endregion
+    #endregion
 
     #region Helpers
 
-    private static IDictionary<string, Interval> GetOccurringVariableRanges(ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
+    private static IDictionary<string, Interval> GetOccurringVariableRanges(
+      ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
       var variables = tree.IterateNodesPrefix().OfType<VariableTreeNode>().Select(v => v.VariableName).Distinct()
                           .ToList();
@@ -321 +326 @@
     public static Interval EvaluateWithSplitting(Instruction[] instructions,
                                                  IDictionary<string, Interval> variableIntervals,
-                                                 List<string> multipleOccurenceVariables, int splittingIterations, double splittingWidth, IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals = null) {
-      var savedIntervals = variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value);
-      var min = FindBound(instructions, variableIntervals, multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
+                                                 List<string> multipleOccurenceVariables, int splittingIterations,
+                                                 double splittingWidth,
+                                                 IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals =
+                                                   null) {
+      var min = FindBound(instructions, variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value),
+        multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
         minimization: true);
-      var max = FindBound(instructions, savedIntervals,  multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
+      var max = FindBound(instructions, variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value),
+        multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
         minimization: false);
 
@@ -333 +342 @@
     private static double FindBound(Instruction[] instructions,
                                     IDictionary<string, Interval> variableIntervals,
-                                    List<string> multipleOccurenceVariables, int splittingIterations, double splittingWidth, IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals = null, bool minimization = true) {
+                                    List<string> multipleOccurenceVariables, int splittingIterations,
+                                    double splittingWidth,
+                                    IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals = null,
+                                    bool minimization = true, bool stopAtLimit = false, double limit = 0) {
       SortedSet<BoxBound> prioQ = new SortedSet<BoxBound>();
-
       var ic = 0;
+      var stop = false;
       //Calculate full box
-      //IReadOnlyDictionary<string, Interval> readonlyRanges =
-      //  variableIntervals.ToDictionary(k => k.Key, k => k.Value);
-      var interval = Evaluate(instructions, ref ic, nodeIntervals, variableIntervals:variableIntervals);
+      var interval = Evaluate(instructions, ref ic, nodeIntervals, variableIntervals: variableIntervals);
       // the order of keys in a dictionary is guaranteed to be the same order as values in a dictionary
       // https://docs.microsoft.com/en-us/dotnet/api/system.collections.idictionary.keys?view=netcore-3.1#remarks
@@ -348 +358 @@
       if (minimization) {
         prioQ.Add(new BoxBound(box, interval.LowerBound));
+        if (stopAtLimit && interval.LowerBound >= limit) stop = true;
       } else {
         prioQ.Add(new BoxBound(box, -interval.UpperBound));
+        if (stopAtLimit && interval.UpperBound <= limit) stop = true;
       }
 
       var discardedBound = double.MaxValue;
       var runningBound = double.MaxValue;
-      for (var depth = 0; depth < splittingIterations && prioQ.Count > 0; ++depth) {
+      for (var depth = 0; depth < splittingIterations && prioQ.Count > 0 && !stop; ++depth) {
         var currentBound = prioQ.Min;
         prioQ.Remove(currentBound);
@@ -382 +394 @@
           var res = Evaluate(instructions, ref ic, nodeIntervals,
             new ReadOnlyDictionary<string, Interval>(variableIntervals));
-          //if (minimization) {
-          //  prioQ.Add(new BoxBound(newBox, res.LowerBound));
-          //} else {
-          //  prioQ.Add(new BoxBound(newBox, -res.UpperBound));
-          //}
+
           var boxBound = new BoxBound(newBox, minimization ? res.LowerBound : -res.UpperBound);
           prioQ.Add(boxBound);
@@ -394 +402 @@
         runningBound = innerBound;
 
+        if (minimization) {
+          if (stopAtLimit && innerBound >= limit)
+            stop = true;
+        } else {
+          if (stopAtLimit && innerBound <= limit)
+            stop = true;
+        }
       }
 
@@ -413 +428 @@
 
     private static IEnumerable<IEnumerable<Interval>> Split(List<Interval> box, double minWidth) {
-      List<Interval> toList(Tuple<Interval, Interval> t) => new List<Interval>{t.Item1, t.Item2};
+      List<Interval> toList(Tuple<Interval, Interval> t) => new List<Interval> {t.Item1, t.Item2};
       var boxes = box.Select(region => region.Width > minWidth ? toList(region.Split()) : new List<Interval> {region})
                      .ToList();
@@ -435 +450 @@
       } else {
         var vars = ContainsVariableMultipleTimes(tree, out var variables);
-        resultInterval = EvaluateWithSplitting(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth);
+        resultInterval = EvaluateWithSplitting(instructions, occuringVariableRanges, variables, SplittingIterations,
+          SplittingWidth);
       }
 
@@ -445 +461 @@
     }
 
-    public IDictionary<ISymbolicExpressionTreeNode, Interval> GetModelNodesBounds(ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
+    public IDictionary<ISymbolicExpressionTreeNode, Interval> GetModelNodesBounds(
+      ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
       throw new NotImplementedException();
     }
 
-    
+    public double CheckConstraint(
+      ISymbolicExpressionTree tree, IntervalCollection variableRanges, IntervalConstraint constraint) {
+      var occuringVariableRanges = GetOccurringVariableRanges(tree, variableRanges);
+      var instructions = PrepareInterpreterState(tree, occuringVariableRanges);
+      if (!UseIntervalSplitting) {
+        var instructionCounter = 0;
+        var modelBound = Evaluate(instructions, ref instructionCounter, variableIntervals: occuringVariableRanges);
+        if (constraint.Interval.Contains(modelBound)) return 0.0;
+        return Math.Abs(modelBound.LowerBound - constraint.Interval.LowerBound) +
+               Math.Abs(modelBound.UpperBound - constraint.Interval.UpperBound);
+      }
+
+      if (double.IsNegativeInfinity(constraint.Interval.LowerBound) &&
+          double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
+        return 0.0;
+      }
+
+      ContainsVariableMultipleTimes(tree, out var variables);
+
+      var upperBound = 0.0;
+      var lowerBound = 0.0;
+      if (double.IsNegativeInfinity(constraint.Interval.LowerBound)) {
+        upperBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
+          minimization: false, stopAtLimit: true, limit: constraint.Interval.UpperBound);
+
+        return upperBound <= constraint.Interval.UpperBound
+          ? 0.0
+          : Math.Abs(upperBound - constraint.Interval.UpperBound);
+      }
+
+      if (double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
+        lowerBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
+          minimization: true, stopAtLimit: true, limit: constraint.Interval.LowerBound);
+
+        return lowerBound <= constraint.Interval.LowerBound
+          ? 0.0
+          : Math.Abs(lowerBound - constraint.Interval.LowerBound);
+      }
+
+      upperBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
+        minimization: false, stopAtLimit: true, limit: constraint.Interval.UpperBound);
+      lowerBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
+        minimization: true, stopAtLimit: true, limit: constraint.Interval.LowerBound);
+
+
+      var res = 0.0;
+
+      res += upperBound <= constraint.Interval.UpperBound ? 0.0 : Math.Abs(upperBound - constraint.Interval.UpperBound);
+      res += lowerBound <= constraint.Interval.LowerBound ? 0.0 : Math.Abs(lowerBound - constraint.Interval.LowerBound);
+
+      return res;
+    }
+
+
+    public bool IsCompatible(ISymbolicExpressionTree tree) {
+      var containsUnknownSymbols = (
+        from n in tree.Root.GetSubtree(0).IterateNodesPrefix()
+        where
+          !(n.Symbol is Variable) &&
+          !(n.Symbol is Constant) &&
+          !(n.Symbol is StartSymbol) &&
+          !(n.Symbol is Addition) &&
+          !(n.Symbol is Subtraction) &&
+          !(n.Symbol is Multiplication) &&
+          !(n.Symbol is Division) &&
+          !(n.Symbol is Sine) &&
+          !(n.Symbol is Cosine) &&
+          !(n.Symbol is Tangent) &&
+          !(n.Symbol is HyperbolicTangent) &&
+          !(n.Symbol is Logarithm) &&
+          !(n.Symbol is Exponential) &&
+          !(n.Symbol is Square) &&
+          !(n.Symbol is SquareRoot) &&
+          !(n.Symbol is Cube) &&
+          !(n.Symbol is CubeRoot) &&
+          !(n.Symbol is Absolute) &&
+          !(n.Symbol is AnalyticQuotient)
+        select n).Any();
+      return !containsUnknownSymbols;
+    }
   }
 }