Changeset 17768


Ignore:
Timestamp:
10/02/20 11:36:34 (13 months 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
Location:
branches/3073_IA_constraint_splitting
Files:
1 added
1 deleted
6 edited

Legend:

Unmodified
Added
Removed
  • branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r17763 r17768  
    242242    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeBatchInterpreter.cs" />
    243243    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeNativeInterpreter.cs" />
     244    <Compile Include="IntervalUtil.cs" />
    244245    <Compile Include="Selectors\DiversitySelector.cs" />
    245246    <Compile Include="SymbolicDataAnalysisExpressionTreeAverageSimilarityCalculator.cs" />
  • branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interfaces/IBoundsEstimator.cs

    r17763 r17768  
    1616      ISymbolicExpressionTree tree, IntervalCollection variableRanges);
    1717
     18    double CheckConstraint(
     19      ISymbolicExpressionTree tree, IntervalCollection variableRanges, IntervalConstraint constraint);
     20
     21    bool IsCompatible(ISymbolicExpressionTree tree);
     22
    1823    int EvaluatedSolutions { get; set; }
    19   }
     24    }
    2025}
  • branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IABoundsEstimator.cs

    r17763 r17768  
    33using System.Collections.ObjectModel;
    44using System.Linq;
    5 using System.Text;
    6 using System.Threading.Tasks;
    75using HEAL.Attic;
    86using HeuristicLab.Common;
     
    1513  [StorableType("C8539434-6FB0-47D0-9F5A-2CAE5D8B8B4F")]
    1614  [Item("IA Bounds Estimator", "Interpreter for calculation of intervals of symbolic models.")]
    17   public sealed class IABoundsEstimator : ParameterizedNamedItem, IBoundsEstimator{
     15  public sealed class IABoundsEstimator : ParameterizedNamedItem, IBoundsEstimator {
    1816    #region Parameters
    1917
     
    5452      set => SplittingWidthParameter.Value.Value = value;
    5553    }
     54
    5655    #endregion
    5756
     
    6059    [StorableConstructor]
    6160    private IABoundsEstimator(StorableConstructorFlag _) : base(_) { }
    62        
     61
    6362    private IABoundsEstimator(IABoundsEstimator original, Cloner cloner) : base(original, cloner) { }
    6463
    65     public IABoundsEstimator() : base("IA Bounds Estimator", "Estimates the bounds of the model with interval arithmetic") {
    66       Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName, "A counter for the total number of solutions the estimator has evaluated.", new IntValue(0)));
    67       Parameters.Add(new FixedValueParameter<BoolValue>(UseIntervalSplittingParameterName, "Defines whether interval splitting is activated or not.", new BoolValue(false)));
    68       Parameters.Add(new FixedValueParameter<IntValue>(SplittingIterationsParameterName, "Defines the number of iterations of splitting.", new IntValue(200)));
    69       Parameters.Add(new FixedValueParameter<DoubleValue>(SplittingWidthParameterName, "Width of interval, after the splitting should stop.", new DoubleValue(0.0)));
     64    public IABoundsEstimator() : base("IA Bounds Estimator",
     65      "Estimates the bounds of the model with interval arithmetic") {
     66      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName,
     67        "A counter for the total number of solutions the estimator has evaluated.", new IntValue(0)));
     68      Parameters.Add(new FixedValueParameter<BoolValue>(UseIntervalSplittingParameterName,
     69        "Defines whether interval splitting is activated or not.", new BoolValue(false)));
     70      Parameters.Add(new FixedValueParameter<IntValue>(SplittingIterationsParameterName,
     71        "Defines the number of iterations of splitting.", new IntValue(200)));
     72      Parameters.Add(new FixedValueParameter<DoubleValue>(SplittingWidthParameterName,
     73        "Width of interval, after the splitting should stop.", new DoubleValue(0.0)));
    7074    }
    7175
     
    7478    }
    7579
    76         #endregion
     80    #endregion
    7781
    7882    #region IStatefulItem Members
     
    8690    public void ClearState() { }
    8791
    88         #endregion
     92    #endregion
    8993
    9094    #region Evaluation
     
    261265    }
    262266
    263         #endregion
     267    #endregion
    264268
    265269    #region Helpers
    266270
    267     private static IDictionary<string, Interval> GetOccurringVariableRanges(ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
     271    private static IDictionary<string, Interval> GetOccurringVariableRanges(
     272      ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
    268273      var variables = tree.IterateNodesPrefix().OfType<VariableTreeNode>().Select(v => v.VariableName).Distinct()
    269274                          .ToList();
     
    321326    public static Interval EvaluateWithSplitting(Instruction[] instructions,
    322327                                                 IDictionary<string, Interval> variableIntervals,
    323                                                  List<string> multipleOccurenceVariables, int splittingIterations, double splittingWidth, IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals = null) {
    324       var savedIntervals = variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value);
    325       var min = FindBound(instructions, variableIntervals, multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
     328                                                 List<string> multipleOccurenceVariables, int splittingIterations,
     329                                                 double splittingWidth,
     330                                                 IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals =
     331                                                   null) {
     332      var min = FindBound(instructions, variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value),
     333        multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
    326334        minimization: true);
    327       var max = FindBound(instructions, savedIntervals,  multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
     335      var max = FindBound(instructions, variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value),
     336        multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
    328337        minimization: false);
    329338
     
    333342    private static double FindBound(Instruction[] instructions,
    334343                                    IDictionary<string, Interval> variableIntervals,
    335                                     List<string> multipleOccurenceVariables, int splittingIterations, double splittingWidth, IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals = null, bool minimization = true) {
     344                                    List<string> multipleOccurenceVariables, int splittingIterations,
     345                                    double splittingWidth,
     346                                    IDictionary<ISymbolicExpressionTreeNode, Interval> nodeIntervals = null,
     347                                    bool minimization = true, bool stopAtLimit = false, double limit = 0) {
    336348      SortedSet<BoxBound> prioQ = new SortedSet<BoxBound>();
    337 
    338349      var ic = 0;
     350      var stop = false;
    339351      //Calculate full box
    340       //IReadOnlyDictionary<string, Interval> readonlyRanges =
    341       //  variableIntervals.ToDictionary(k => k.Key, k => k.Value);
    342       var interval = Evaluate(instructions, ref ic, nodeIntervals, variableIntervals:variableIntervals);
     352      var interval = Evaluate(instructions, ref ic, nodeIntervals, variableIntervals: variableIntervals);
    343353      // the order of keys in a dictionary is guaranteed to be the same order as values in a dictionary
    344354      // https://docs.microsoft.com/en-us/dotnet/api/system.collections.idictionary.keys?view=netcore-3.1#remarks
     
    348358      if (minimization) {
    349359        prioQ.Add(new BoxBound(box, interval.LowerBound));
     360        if (stopAtLimit && interval.LowerBound >= limit) stop = true;
    350361      } else {
    351362        prioQ.Add(new BoxBound(box, -interval.UpperBound));
     363        if (stopAtLimit && interval.UpperBound <= limit) stop = true;
    352364      }
    353365
    354366      var discardedBound = double.MaxValue;
    355367      var runningBound = double.MaxValue;
    356       for (var depth = 0; depth < splittingIterations && prioQ.Count > 0; ++depth) {
     368      for (var depth = 0; depth < splittingIterations && prioQ.Count > 0 && !stop; ++depth) {
    357369        var currentBound = prioQ.Min;
    358370        prioQ.Remove(currentBound);
     
    382394          var res = Evaluate(instructions, ref ic, nodeIntervals,
    383395            new ReadOnlyDictionary<string, Interval>(variableIntervals));
    384           //if (minimization) {
    385           //  prioQ.Add(new BoxBound(newBox, res.LowerBound));
    386           //} else {
    387           //  prioQ.Add(new BoxBound(newBox, -res.UpperBound));
    388           //}
     396
    389397          var boxBound = new BoxBound(newBox, minimization ? res.LowerBound : -res.UpperBound);
    390398          prioQ.Add(boxBound);
     
    394402        runningBound = innerBound;
    395403
     404        if (minimization) {
     405          if (stopAtLimit && innerBound >= limit)
     406            stop = true;
     407        } else {
     408          if (stopAtLimit && innerBound <= limit)
     409            stop = true;
     410        }
    396411      }
    397412
     
    413428
    414429    private static IEnumerable<IEnumerable<Interval>> Split(List<Interval> box, double minWidth) {
    415       List<Interval> toList(Tuple<Interval, Interval> t) => new List<Interval>{t.Item1, t.Item2};
     430      List<Interval> toList(Tuple<Interval, Interval> t) => new List<Interval> {t.Item1, t.Item2};
    416431      var boxes = box.Select(region => region.Width > minWidth ? toList(region.Split()) : new List<Interval> {region})
    417432                     .ToList();
     
    435450      } else {
    436451        var vars = ContainsVariableMultipleTimes(tree, out var variables);
    437         resultInterval = EvaluateWithSplitting(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth);
     452        resultInterval = EvaluateWithSplitting(instructions, occuringVariableRanges, variables, SplittingIterations,
     453          SplittingWidth);
    438454      }
    439455
     
    445461    }
    446462
    447     public IDictionary<ISymbolicExpressionTreeNode, Interval> GetModelNodesBounds(ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
     463    public IDictionary<ISymbolicExpressionTreeNode, Interval> GetModelNodesBounds(
     464      ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
    448465      throw new NotImplementedException();
    449466    }
    450467
    451    
     468    public double CheckConstraint(
     469      ISymbolicExpressionTree tree, IntervalCollection variableRanges, IntervalConstraint constraint) {
     470      var occuringVariableRanges = GetOccurringVariableRanges(tree, variableRanges);
     471      var instructions = PrepareInterpreterState(tree, occuringVariableRanges);
     472      if (!UseIntervalSplitting) {
     473        var instructionCounter = 0;
     474        var modelBound = Evaluate(instructions, ref instructionCounter, variableIntervals: occuringVariableRanges);
     475        if (constraint.Interval.Contains(modelBound)) return 0.0;
     476        return Math.Abs(modelBound.LowerBound - constraint.Interval.LowerBound) +
     477               Math.Abs(modelBound.UpperBound - constraint.Interval.UpperBound);
     478      }
     479
     480      if (double.IsNegativeInfinity(constraint.Interval.LowerBound) &&
     481          double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
     482        return 0.0;
     483      }
     484
     485      ContainsVariableMultipleTimes(tree, out var variables);
     486
     487      var upperBound = 0.0;
     488      var lowerBound = 0.0;
     489      if (double.IsNegativeInfinity(constraint.Interval.LowerBound)) {
     490        upperBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
     491          minimization: false, stopAtLimit: true, limit: constraint.Interval.UpperBound);
     492
     493        return upperBound <= constraint.Interval.UpperBound
     494          ? 0.0
     495          : Math.Abs(upperBound - constraint.Interval.UpperBound);
     496      }
     497
     498      if (double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
     499        lowerBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
     500          minimization: true, stopAtLimit: true, limit: constraint.Interval.LowerBound);
     501
     502        return lowerBound <= constraint.Interval.LowerBound
     503          ? 0.0
     504          : Math.Abs(lowerBound - constraint.Interval.LowerBound);
     505      }
     506
     507      upperBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
     508        minimization: false, stopAtLimit: true, limit: constraint.Interval.UpperBound);
     509      lowerBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
     510        minimization: true, stopAtLimit: true, limit: constraint.Interval.LowerBound);
     511
     512
     513      var res = 0.0;
     514
     515      res += upperBound <= constraint.Interval.UpperBound ? 0.0 : Math.Abs(upperBound - constraint.Interval.UpperBound);
     516      res += lowerBound <= constraint.Interval.LowerBound ? 0.0 : Math.Abs(lowerBound - constraint.Interval.LowerBound);
     517
     518      return res;
     519    }
     520
     521
     522    public bool IsCompatible(ISymbolicExpressionTree tree) {
     523      var containsUnknownSymbols = (
     524        from n in tree.Root.GetSubtree(0).IterateNodesPrefix()
     525        where
     526          !(n.Symbol is Variable) &&
     527          !(n.Symbol is Constant) &&
     528          !(n.Symbol is StartSymbol) &&
     529          !(n.Symbol is Addition) &&
     530          !(n.Symbol is Subtraction) &&
     531          !(n.Symbol is Multiplication) &&
     532          !(n.Symbol is Division) &&
     533          !(n.Symbol is Sine) &&
     534          !(n.Symbol is Cosine) &&
     535          !(n.Symbol is Tangent) &&
     536          !(n.Symbol is HyperbolicTangent) &&
     537          !(n.Symbol is Logarithm) &&
     538          !(n.Symbol is Exponential) &&
     539          !(n.Symbol is Square) &&
     540          !(n.Symbol is SquareRoot) &&
     541          !(n.Symbol is Cube) &&
     542          !(n.Symbol is CubeRoot) &&
     543          !(n.Symbol is Absolute) &&
     544          !(n.Symbol is AnalyticQuotient)
     545        select n).Any();
     546      return !containsUnknownSymbols;
     547    }
    452548  }
    453549}
  • branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis/3.4/HeuristicLab.Problems.DataAnalysis-3.4.csproj

    r17765 r17768  
    192192    <Compile Include="Implementation\Interval\IntervalConstraint.cs" />
    193193    <Compile Include="Implementation\Interval\IntervalConstraintsParser.cs" />
    194     <Compile Include="Implementation\Interval\Region.cs" />
    195194    <Compile Include="Implementation\Regression\ConfidenceBoundRegressionSolution.cs" />
    196195    <Compile Include="Implementation\Regression\ConstantRegressionModel.cs" />
  • branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis/3.4/Implementation/Interval/IntervalConstraint.cs

    r17767 r17768  
    115115    }
    116116
    117     [Storable] private IEnumerable<Region> regions;
    118     public IEnumerable<Region> Regions {
     117    [Storable] private IntervalCollection regions;
     118    public IntervalCollection Regions {
    119119      get => regions;
    120120      set {
     
    146146                              Interval interval, double weight, bool enabled)
    147147      : this(expression, variable, target, numberOfDerivations,
    148              interval, Enumerable.Empty<Region>(), weight, enabled) { }
     148             interval, new IntervalCollection(), weight, enabled) { }
    149149
    150150    public IntervalConstraint(string expression, string variable, string target, int numberOfDerivations,
    151                               Interval interval, IEnumerable<Region> regions, double weight, bool enabled) {
     151                              Interval interval, IntervalCollection regions, double weight, bool enabled) {
    152152      this.regions = regions;
    153153      this.weight = weight;
     
    166166    private IntervalConstraint(IntervalConstraint original, Cloner cloner)
    167167      : base(original, cloner) {
    168       Regions = new List<Region>(original.Regions?.Select(r => cloner.Clone(r)) ?? Enumerable.Empty<Region>());
     168      Regions = original.Regions;
    169169      Expression = original.Expression;
    170170      Variable = original.Variable;
     
    207207                                   "]");
    208208        if(Regions != null) {
    209           foreach (var region in Regions)
    210             expression += $", {region.VariableName}=({region.Interval.LowerBound} .. {region.Interval.UpperBound})";
     209          foreach (var region in Regions.GetReadonlyDictionary())
     210            expression += $", {region.Key}=({region.Value.LowerBound} .. {region.Value.UpperBound})";
    211211        }
    212212       
     
    224224                                 GetDerivationString(numberOfDerivations));
    225225      if (Regions != null) {
    226         foreach (var region in Regions)
    227           expression += $", {region.VariableName}=({region.Interval.LowerBound} .. {region.Interval.UpperBound})";
     226        foreach (var region in Regions.GetReadonlyDictionary())
     227          expression += $", {region.Key}=({region.Value.LowerBound} .. {region.Value.UpperBound})";
    228228      }
    229229      Expression = expression;
  • branches/3073_IA_constraint_splitting/HeuristicLab.Problems.DataAnalysis/3.4/Implementation/Interval/IntervalConstraintsParser.cs

    r17765 r17768  
    9393            if (match.Groups[10].Success)
    9494            {
    95               IList<Region> regions = new List<Region>();
     95              IntervalCollection regions = new IntervalCollection();
    9696              // option variables found
    9797              for(int idx = 0; idx < match.Groups[10].Captures.Count; ++idx)
    9898              {
    99                 Region region = ParseRegion(
     99                KeyValuePair<string, Interval> region = ParseRegion(
    100100                  match.Groups[11].Captures[idx].Value,
    101101                  match.Groups[13].Captures[idx].Value,
    102102                  match.Groups[15].Captures[idx].Value);
    103                 if(!regions.Any(r => r.VariableName == region.VariableName))
    104                   regions.Add(region);
     103                if (regions.GetReadonlyDictionary().All(r => r.Key != region.Key))
     104                  regions.AddInterval(region.Key, region.Value);
    105105                else
    106106                  throw new ArgumentException("A constraint cannot contain multiple regions of the same variable.");
     
    184184            if(match.Groups[17].Success)
    185185            {
    186               IList<Region> regions = new List<Region>();
     186              IntervalCollection regions = new IntervalCollection();
    187187              // option variables found
    188188              for (int idx = 0; idx < match.Groups[17].Captures.Count; ++idx)
    189189              {
    190                 Region region = ParseRegion(
     190                KeyValuePair<string, Interval> region = ParseRegion(
    191191                  match.Groups[18].Captures[idx].Value,
    192192                  match.Groups[20].Captures[idx].Value,
    193193                  match.Groups[22].Captures[idx].Value);
    194                 if (!regions.Any(r => r.VariableName == region.VariableName))
    195                   regions.Add(region);
     194                if (regions.GetReadonlyDictionary().All(r => r.Key != region.Key))
     195                  regions.AddInterval(region.Key, region.Value);
    196196                else
    197197                  throw new ArgumentException("A constraint cannot contain multiple regions of the same variable.");
     
    217217    }
    218218
    219     private static Region ParseRegion(string variable, string lb, string ub)
     219    private static KeyValuePair<string, Interval> ParseRegion(string variable, string lb, string ub)
    220220    {
    221221      var regionLb = ParseIntervalBounds(lb);
    222222      var regionUb = ParseIntervalBounds(ub);
    223       return new Region(variable, new Interval(regionLb, regionUb));
     223      return new KeyValuePair<string, Interval>(variable, new Interval(regionLb, regionUb));
     224      //return new Region(variable, new Interval(regionLb, regionUb));
    224225    }
    225226
Note: See TracChangeset for help on using the changeset viewer.