Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
03/12/21 16:41:42 (4 years ago)
Author:
gkronber
Message:

#3073 refactoring to prepare for trunk reintegration

Location:
branches/3073_IA_constraint_splitting_reintegration
Files:
4 edited
2 moved

Legend:

Unmodified
Added
Removed

  • branches/3073_IA_constraint_splitting_reintegration

    • Property svn:ignore

      •  

        old new  
        11bin
         2TestResults

  • branches/3073_IA_constraint_splitting_reintegration/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/HeuristicLab.Problems.DataAnalysis.Symbolic-3.4.csproj

    r17772 r17891  
    237237    <Compile Include="Interpreter\BatchInstruction.cs" />
    238238    <Compile Include="Interpreter\BatchOperations.cs" />
    239     <Compile Include="Interpreter\IABoundsEstimator.cs" />
     239    <Compile Include="Interpreter\IntervalArithBoundsEstimator.cs" />
     240    <Compile Include="Interpreter\IntervalArithCompiledExpressionBoundsEstimator.cs" />
    240241    <Compile Include="Interpreter\IntervalInterpreter.cs" />
    241242    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionCompiledTreeInterpreter.cs" />
    242243    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeBatchInterpreter.cs" />
    243     <Compile Include="Interpreter\IACompiledExpressionBoundsEstimator.cs" />
    244244    <Compile Include="Interpreter\SymbolicDataAnalysisExpressionTreeNativeInterpreter.cs" />
    245245    <Compile Include="IntervalUtil.cs" />

  • branches/3073_IA_constraint_splitting_reintegration/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interfaces/IBoundsEstimator.cs

    r17887 r17891  
    1313
    1414    // returns the size of the violation which is the distance to one of the bounds
    15     double CheckConstraint(
     15    double GetConstraintViolation(
    1616      ISymbolicExpressionTree tree, IntervalCollection variableRanges, ShapeConstraint constraint);
    1717

  • branches/3073_IA_constraint_splitting_reintegration/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IntervalArithBoundsEstimator.cs

    r17890 r17891  
    1212namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    1313  [StorableType("C8539434-6FB0-47D0-9F5A-2CAE5D8B8B4F")]
    14   [Item("IA Bounds Estimator", "Interpreter for calculation of intervals of symbolic models.")]
    15   public sealed class IABoundsEstimator : ParameterizedNamedItem, IBoundsEstimator {
     14  [Item("Interval Arithmetic Bounds Estimator", "Interpreter for calculation of intervals of symbolic models.")]
     15  public sealed class IntervalArithBoundsEstimator : ParameterizedNamedItem, IBoundsEstimator {
    1616    #region Parameters
    1717
    1818    private const string EvaluatedSolutionsParameterName = "EvaluatedSolutions";
    19     private const string UseIntervalSplittingParameterName = "Use Interval splitting";
    20     private const string SplittingIterationsParameterName = "Splitting Iterations";
    21     private const string SplittingWidthParameterName = "Splitting width";
    2219
    2320    public IFixedValueParameter<IntValue> EvaluatedSolutionsParameter =>
    24       (IFixedValueParameter<IntValue>) Parameters[EvaluatedSolutionsParameterName];
    25 
    26     public IFixedValueParameter<BoolValue> UseIntervalSplittingParameter =>
    27       (IFixedValueParameter<BoolValue>) Parameters[UseIntervalSplittingParameterName];
    28 
    29     public IFixedValueParameter<IntValue> SplittingIterationsParameter =>
    30       (IFixedValueParameter<IntValue>) Parameters[SplittingIterationsParameterName];
    31 
    32     public IFixedValueParameter<DoubleValue> SplittingWidthParameter =>
    33       (IFixedValueParameter<DoubleValue>) Parameters[SplittingWidthParameterName];
     21      (IFixedValueParameter<IntValue>)Parameters[EvaluatedSolutionsParameterName];
    3422
    3523    public int EvaluatedSolutions {
    … …  
    3725      set => EvaluatedSolutionsParameter.Value.Value = value;
    3826    }
    39 
    40     public bool UseIntervalSplitting {
    41       get => UseIntervalSplittingParameter.Value.Value;
    42       set => UseIntervalSplittingParameter.Value.Value = value;
    43     }
    44 
    45     public int SplittingIterations {
    46       get => SplittingIterationsParameter.Value.Value;
    47       set => SplittingIterationsParameter.Value.Value = value;
    48     }
    49 
    50     public double SplittingWidth {
    51       get => SplittingWidthParameter.Value.Value;
    52       set => SplittingWidthParameter.Value.Value = value;
    53     }
    54 
    5527    #endregion
    5628
    … …  
    5830
    5931    [StorableConstructor]
    60     private IABoundsEstimator(StorableConstructorFlag _) : base(_) { }
    61 
    62     private IABoundsEstimator(IABoundsEstimator original, Cloner cloner) : base(original, cloner) { }
    63 
    64     public IABoundsEstimator() : base("IA Bounds Estimator",
     32    private IntervalArithBoundsEstimator(StorableConstructorFlag _) : base(_) { }
     33
     34    private IntervalArithBoundsEstimator(IntervalArithBoundsEstimator original, Cloner cloner) : base(original, cloner) { }
     35
     36    public IntervalArithBoundsEstimator() : base("IA Bounds Estimator",
    6537      "Estimates the bounds of the model with interval arithmetic") {
    6638      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName,
    6739        "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)));
    7440    }
    7541
    7642    public override IDeepCloneable Clone(Cloner cloner) {
    77       return new IABoundsEstimator(this, cloner);
     43      return new IntervalArithBoundsEstimator(this, cloner);
    7844    }
    7945
    … …  
    9864      IDictionary<string, Interval> variableRanges) {
    9965      if (variableRanges == null)
    100         throw new ArgumentNullException("No variablew ranges are present!", nameof(variableRanges));
    101 
    102       //Check if all variables used in the tree are present in the dataset
     66        throw new ArgumentNullException("No variable ranges are present!", nameof(variableRanges));
     67
     68      // Check if all variables used in the tree are present in the dataset
    10369      foreach (var variable in tree.IterateNodesPrefix().OfType<VariableTreeNode>().Select(n => n.VariableName)
    10470                                   .Distinct())
    … …  
    10874      var code = SymbolicExpressionTreeCompiler.Compile(tree, OpCodes.MapSymbolToOpCode);
    10975      foreach (var instr in code.Where(i => i.opCode == OpCodes.Variable)) {
    110         var variableTreeNode = (VariableTreeNode) instr.dynamicNode;
     76        var variableTreeNode = (VariableTreeNode)instr.dynamicNode;
    11177        instr.data = variableRanges[variableTreeNode.VariableName];
    11278      }
    … …  
    11581    }
    11682
     83    // Use ref parameter, because the tree will be iterated through recursively from the left-side branch to the right side
     84    // Update instructionCounter, whenever Evaluate is called
    11785    public static Interval Evaluate(
    11886      Instruction[] instructions, ref int instructionCounter,
    … …  
    12088      IDictionary<string, Interval> variableIntervals = null) {
    12189      var currentInstr = instructions[instructionCounter];
    122       //Use ref parameter, because the tree will be iterated through recursively from the left-side branch to the right side
    123       //Update instructionCounter, whenever Evaluate is called
    12490      instructionCounter++;
    125       Interval result = null;
     91      Interval result;
    12692
    12793      switch (currentInstr.opCode) {
    128         //Variables, Constants, ...
    12994        case OpCodes.Variable: {
    130           var variableTreeNode = (VariableTreeNode) currentInstr.dynamicNode;
    131           var weightInterval = new Interval(variableTreeNode.Weight, variableTreeNode.Weight);
    132 
    133           Interval variableInterval;
    134           if (variableIntervals != null && variableIntervals.ContainsKey(variableTreeNode.VariableName))
    135             variableInterval = variableIntervals[variableTreeNode.VariableName];
    136           else
    137             variableInterval = (Interval) currentInstr.data;
    138 
    139           result = Interval.Multiply(variableInterval, weightInterval);
    140           break;
    141         }
     95            var variableTreeNode = (VariableTreeNode)currentInstr.dynamicNode;
     96            var weightInterval = new Interval(variableTreeNode.Weight, variableTreeNode.Weight);
     97
     98            Interval variableInterval;
     99            if (variableIntervals != null && variableIntervals.ContainsKey(variableTreeNode.VariableName))
     100              variableInterval = variableIntervals[variableTreeNode.VariableName];
     101            else
     102              variableInterval = (Interval)currentInstr.data;
     103
     104            result = Interval.Multiply(variableInterval, weightInterval);
     105            break;
     106          }
    142107        case OpCodes.Constant: {
    143           var constTreeNode = (ConstantTreeNode) currentInstr.dynamicNode;
    144           result = new Interval(constTreeNode.Value, constTreeNode.Value);
    145           break;
    146         }
    147         //Elementary arithmetic rules
     108            var constTreeNode = (ConstantTreeNode)currentInstr.dynamicNode;
     109            result = new Interval(constTreeNode.Value, constTreeNode.Value);
     110            break;
     111          }
    148112        case OpCodes.Add: {
    149           result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    150           for (var i = 1; i < currentInstr.nArguments; i++) {
    151             var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    152             result = Interval.Add(result, argumentInterval);
    153           }
    154 
    155           break;
    156         }
     113            result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     114            for (var i = 1; i < currentInstr.nArguments; i++) {
     115              var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     116              result = Interval.Add(result, argumentInterval);
     117            }
     118
     119            break;
     120          }
    157121        case OpCodes.Sub: {
    158           result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    159           if (currentInstr.nArguments == 1)
    160             result = Interval.Multiply(new Interval(-1, -1), result);
    161 
    162           for (var i = 1; i < currentInstr.nArguments; i++) {
    163             var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    164             result = Interval.Subtract(result, argumentInterval);
    165           }
    166 
    167           break;
    168         }
     122            result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     123            if (currentInstr.nArguments == 1)
     124              result = Interval.Multiply(new Interval(-1, -1), result);
     125
     126            for (var i = 1; i < currentInstr.nArguments; i++) {
     127              var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     128              result = Interval.Subtract(result, argumentInterval);
     129            }
     130
     131            break;
     132          }
    169133        case OpCodes.Mul: {
    170           result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    171           for (var i = 1; i < currentInstr.nArguments; i++) {
    172             var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    173             result = Interval.Multiply(result, argumentInterval);
    174           }
    175 
    176           break;
    177         }
     134            result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     135            for (var i = 1; i < currentInstr.nArguments; i++) {
     136              var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     137              result = Interval.Multiply(result, argumentInterval);
     138            }
     139
     140            break;
     141          }
    178142        case OpCodes.Div: {
    179           result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    180           if (currentInstr.nArguments == 1)
    181             result = Interval.Divide(new Interval(1, 1), result);
    182 
    183           for (var i = 1; i < currentInstr.nArguments; i++) {
    184             var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    185             result = Interval.Divide(result, argumentInterval);
    186           }
    187 
    188           break;
    189         }
    190         //Trigonometric functions
     143            result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     144            if (currentInstr.nArguments == 1)
     145              result = Interval.Divide(new Interval(1, 1), result);
     146
     147            for (var i = 1; i < currentInstr.nArguments; i++) {
     148              var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     149              result = Interval.Divide(result, argumentInterval);
     150            }
     151
     152            break;
     153          }
    191154        case OpCodes.Sin: {
    192           var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    193           result = Interval.Sine(argumentInterval);
    194           break;
    195         }
     155            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     156            result = Interval.Sine(argumentInterval);
     157            break;
     158          }
    196159        case OpCodes.Cos: {
    197           var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    198           result = Interval.Cosine(argumentInterval);
    199           break;
    200         }
     160            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     161            result = Interval.Cosine(argumentInterval);
     162            break;
     163          }
    201164        case OpCodes.Tan: {
    202           var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    203           result = Interval.Tangens(argumentInterval);
    204           break;
    205         }
     165            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     166            result = Interval.Tangens(argumentInterval);
     167            break;
     168          }
    206169        case OpCodes.Tanh: {
    207           var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    208           result = Interval.HyperbolicTangent(argumentInterval);
    209           break;
    210         }
    211         //Exponential functions
     170            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     171            result = Interval.HyperbolicTangent(argumentInterval);
     172            break;
     173          }
    212174        case OpCodes.Log: {
    213           var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    214           result = Interval.Logarithm(argumentInterval);
    215           break;
    216         }
     175            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     176            result = Interval.Logarithm(argumentInterval);
     177            break;
     178          }
    217179        case OpCodes.Exp: {
    218           var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    219           result = Interval.Exponential(argumentInterval);
    220           break;
    221         }
     180            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     181            result = Interval.Exponential(argumentInterval);
     182            break;
     183          }
    222184        case OpCodes.Square: {
    223           var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    224           result = Interval.Square(argumentInterval);
    225           break;
    226         }
     185            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     186            result = Interval.Square(argumentInterval);
     187            break;
     188          }
    227189        case OpCodes.SquareRoot: {
    228           var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    229           result = Interval.SquareRoot(argumentInterval);
    230           break;
    231         }
     190            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     191            result = Interval.SquareRoot(argumentInterval);
     192            break;
     193          }
    232194        case OpCodes.Cube: {
    233           var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    234           result = Interval.Cube(argumentInterval);
    235           break;
    236         }
     195            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     196            result = Interval.Cube(argumentInterval);
     197            break;
     198          }
    237199        case OpCodes.CubeRoot: {
    238           var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    239           result = Interval.CubicRoot(argumentInterval);
    240           break;
    241         }
     200            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     201            result = Interval.CubicRoot(argumentInterval);
     202            break;
     203          }
    242204        case OpCodes.Absolute: {
    243           var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    244           result = Interval.Absolute(argumentInterval);
    245           break;
    246         }
     205            var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     206            result = Interval.Absolute(argumentInterval);
     207            break;
     208          }
    247209        case OpCodes.AnalyticQuotient: {
    248           result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    249           for (var i = 1; i < currentInstr.nArguments; i++) {
    250             var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
    251             result = Interval.AnalyticalQuotient(result, argumentInterval);
    252           }
    253 
    254           break;
    255         }
     210            result = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     211            for (var i = 1; i < currentInstr.nArguments; i++) {
     212              var argumentInterval = Evaluate(instructions, ref instructionCounter, nodeIntervals, variableIntervals);
     213              result = Interval.AnalyticalQuotient(result, argumentInterval);
     214            }
     215
     216            break;
     217          }
    256218        default:
    257219          throw new NotSupportedException(
    … …  
    277239    }
    278240
    279     private static bool ContainsVariableMultipleTimes(ISymbolicExpressionTree tree, out List<String> variables) {
    280       variables = new List<string>();
    281       var varlist = tree.IterateNodesPrefix().OfType<VariableTreeNode>().GroupBy(x => x.VariableName);
    282       foreach (var group in varlist) {
    283         if (group.Count() > 1) {
    284           variables.Add(group.Key);
    285         }
    286       }
    287 
    288       return varlist.Any(group => group.Count() > 1);
    289     }
    290 
    291     // a multi-dimensional box with an associated bound
    292     // boxbounds are ordered first by bound (smaller first), then by size of box (larger first) then by distance of bottom left corner to origin
    293     private class BoxBound : IComparable<BoxBound> {
    294       public List<Interval> box;
    295       public double bound;
    296 
    297       public BoxBound(IEnumerable<Interval> box, double bound) {
    298         this.box = new List<Interval>(box);
    299         this.bound = bound;
    300       }
    301 
    302       public int CompareTo(BoxBound other) {
    303         if (bound != other.bound) return bound.CompareTo(other.bound);
    304 
    305         var thisSize = box.Aggregate(1.0, (current, dimExtent) => current * dimExtent.Width);
    306         var otherSize = other.box.Aggregate(1.0, (current, dimExtent) => current * dimExtent.Width);
    307         if (thisSize != otherSize) return -thisSize.CompareTo(otherSize);
    308 
    309         var thisDist = box.Sum(dimExtent => dimExtent.LowerBound * dimExtent.LowerBound);
    310         var otherDist = other.box.Sum(dimExtent => dimExtent.LowerBound * dimExtent.LowerBound);
    311         if (thisDist != otherDist) return thisDist.CompareTo(otherDist);
    312 
    313         // which is smaller first along the dimensions?
    314         for (int i = 0; i < box.Count; i++) {
    315           if (box[i].LowerBound != other.box[i].LowerBound) return box[i].LowerBound.CompareTo(other.box[i].LowerBound);
    316         }
    317 
    318         return 0;
    319       }
    320     }
    321 
    322     #endregion
    323 
    324     #region Splitting
    325 
    326     public static Interval EvaluateWithSplitting(Instruction[] instructions,
    327                                                  IDictionary<string, Interval> variableIntervals,
    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,
    334         minimization: true);
    335       var max = FindBound(instructions, variableIntervals.ToDictionary(entry => entry.Key, entry => entry.Value),
    336         multipleOccurenceVariables, splittingIterations, splittingWidth, nodeIntervals,
    337         minimization: false);
    338 
    339       return new Interval(min, max);
    340     }
    341 
    342     private static double FindBound(Instruction[] instructions,
    343                                     IDictionary<string, Interval> variableIntervals,
    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) {
    348       SortedSet<BoxBound> prioQ = new SortedSet<BoxBound>();
    349       var ic = 0;
    350       var stop = false;
    351       //Calculate full box
    352       var interval = Evaluate(instructions, ref ic, nodeIntervals, variableIntervals: variableIntervals);
    353       // the order of keys in a dictionary is guaranteed to be the same order as values in a dictionary
    354       // https://docs.microsoft.com/en-us/dotnet/api/system.collections.idictionary.keys?view=netcore-3.1#remarks
    355       //var box = variableIntervals.Values;
    356       //Box only contains intervals from multiple occurence variables
    357       var box = multipleOccurenceVariables.Select(k => variableIntervals[k]);
    358       if (minimization) {
    359         prioQ.Add(new BoxBound(box, interval.LowerBound));
    360         if (stopAtLimit && interval.LowerBound >= limit) stop = true;
    361       } else {
    362         prioQ.Add(new BoxBound(box, -interval.UpperBound));
    363         if (stopAtLimit && interval.UpperBound <= limit) stop = true;
    364       }
    365 
    366       var discardedBound = double.MaxValue;
    367       var runningBound = double.MaxValue;
    368       for (var depth = 0; depth < splittingIterations && prioQ.Count > 0 && !stop; ++depth) {
    369         var currentBound = prioQ.Min;
    370         prioQ.Remove(currentBound);
    371 
    372         if (currentBound.box.All(x => x.Width < splittingWidth)) {
    373           discardedBound = Math.Min(discardedBound, currentBound.bound);
    374           continue;
    375         }
    376 
    377         var newBoxes = Split(currentBound.box, splittingWidth);
    378 
    379         var innerBound = double.MaxValue;
    380         foreach (var newBox in newBoxes) {
    381           //var intervalEnum = newBox.GetEnumerator();
    382           //var keyEnum = readonlyRanges.Keys.GetEnumerator();
    383           //while (intervalEnum.MoveNext() & keyEnum.MoveNext()) {
    384           //  variableIntervals[keyEnum.Current] = intervalEnum.Current;
    385           //}
    386           //Set the splitted variables
    387           var intervalEnum = newBox.GetEnumerator();
    388           foreach (var key in multipleOccurenceVariables) {
    389             intervalEnum.MoveNext();
    390             variableIntervals[key] = intervalEnum.Current;
    391           }
    392 
    393           ic = 0;
    394           var res = Evaluate(instructions, ref ic, nodeIntervals,
    395             new ReadOnlyDictionary<string, Interval>(variableIntervals));
    396 
    397           var boxBound = new BoxBound(newBox, minimization ? res.LowerBound : -res.UpperBound);
    398           prioQ.Add(boxBound);
    399           innerBound = Math.Min(innerBound, boxBound.bound);
    400         }
    401 
    402         runningBound = innerBound;
    403 
    404         if (minimization) {
    405           if (stopAtLimit && innerBound >= limit)
    406             stop = true;
    407         } else {
    408           if (stopAtLimit && innerBound <= limit)
    409             stop = true;
    410         }
    411       }
    412 
    413       var bound = Math.Min(runningBound, discardedBound);
    414       if (bound == double.MaxValue)
    415         return minimization ? interval.LowerBound : interval.UpperBound;
    416 
    417       return minimization ? bound : -bound;
    418       //return minimization ? prioQ.First().bound : -prioQ.First().bound;
    419     }
    420 
    421     private static IEnumerable<IEnumerable<Interval>> Split(List<Interval> box) {
    422       var boxes = box.Select(region => region.Split())
    423                      .Select(split => new List<Interval> {split.Item1, split.Item2})
    424                      .ToList();
    425 
    426       return boxes.CartesianProduct();
    427     }
    428 
    429     private static IEnumerable<IEnumerable<Interval>> Split(List<Interval> box, double minWidth) {
    430       List<Interval> toList(Tuple<Interval, Interval> t) => new List<Interval> {t.Item1, t.Item2};
    431       var boxes = box.Select(region => region.Width > minWidth ? toList(region.Split()) : new List<Interval> {region})
    432                      .ToList();
    433 
    434       return boxes.CartesianProduct();
    435     }
    436 
    437     #endregion
    438 
     241    #endregion
     242 
    439243    public Interval GetModelBound(ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
    440244      lock (syncRoot) {
    … …  
    445249      var instructions = PrepareInterpreterState(tree, occuringVariableRanges);
    446250      Interval resultInterval;
    447       if (!UseIntervalSplitting) {
    448         var instructionCounter = 0;
    449         resultInterval = Evaluate(instructions, ref instructionCounter, variableIntervals: occuringVariableRanges);
    450       } else {
    451         var vars = ContainsVariableMultipleTimes(tree, out var variables);
    452         resultInterval = EvaluateWithSplitting(instructions, occuringVariableRanges, variables, SplittingIterations,
    453           SplittingWidth);
    454       }
     251      var instructionCounter = 0;
     252      resultInterval = Evaluate(instructions, ref instructionCounter, variableIntervals: occuringVariableRanges);
    455253
    456254      // because of numerical errors the bounds might be incorrect
    … …  
    466264    }
    467265
    468     public double CheckConstraint(
     266    public double GetConstraintViolation(
    469267      ISymbolicExpressionTree tree, IntervalCollection variableRanges, ShapeConstraint constraint) {
    470268      var occuringVariableRanges = GetOccurringVariableRanges(tree, variableRanges);
    471269      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 
    477 
    478         var error = 0.0;
    479 
    480         if (!constraint.Interval.Contains(modelBound.LowerBound)) {
    481             error += Math.Abs(modelBound.LowerBound - constraint.Interval.LowerBound);
    482         }
    483 
    484         if (!constraint.Interval.Contains(modelBound.UpperBound)) {
    485             error += Math.Abs(modelBound.UpperBound - constraint.Interval.UpperBound);
    486         }
    487 
    488         return error;
    489         // return Math.Abs(modelBound.LowerBound - constraint.Interval.LowerBound) +
    490         //Math.Abs(modelBound.UpperBound - constraint.Interval.UpperBound);
    491       }
    492 
    493       if (double.IsNegativeInfinity(constraint.Interval.LowerBound) &&
    494           double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
    495         return 0.0;
    496       }
    497 
    498       ContainsVariableMultipleTimes(tree, out var variables);
    499 
    500       var upperBound = 0.0;
    501       var lowerBound = 0.0;
    502       if (double.IsNegativeInfinity(constraint.Interval.LowerBound)) {
    503         upperBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
    504           minimization: false, stopAtLimit: true, limit: constraint.Interval.UpperBound);
    505 
    506         return upperBound <= constraint.Interval.UpperBound
    507           ? 0.0
    508           : Math.Abs(upperBound - constraint.Interval.UpperBound);
    509       }
    510 
    511       if (double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
    512         lowerBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
    513           minimization: true, stopAtLimit: true, limit: constraint.Interval.LowerBound);
    514 
    515         return lowerBound >= constraint.Interval.LowerBound
    516           ? 0.0
    517           : Math.Abs(lowerBound - constraint.Interval.LowerBound);
    518       }
    519 
    520       upperBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
    521         minimization: false, stopAtLimit: true, limit: constraint.Interval.UpperBound);
    522       lowerBound = FindBound(instructions, occuringVariableRanges, variables, SplittingIterations, SplittingWidth,
    523         minimization: true, stopAtLimit: true, limit: constraint.Interval.LowerBound);
    524 
    525 
    526       var res = 0.0;
    527 
    528       res += upperBound <= constraint.Interval.UpperBound ? 0.0 : Math.Abs(upperBound - constraint.Interval.UpperBound);
    529       res += lowerBound <= constraint.Interval.LowerBound ? 0.0 : Math.Abs(lowerBound - constraint.Interval.LowerBound);
    530 
    531       return res;
     270      var instructionCounter = 0;
     271      var modelBound = Evaluate(instructions, ref instructionCounter, variableIntervals: occuringVariableRanges);
     272      if (constraint.Interval.Contains(modelBound)) return 0.0;
     273
     274
     275      var error = 0.0;
     276
     277      if (!constraint.Interval.Contains(modelBound.LowerBound)) {
     278        error += Math.Abs(modelBound.LowerBound - constraint.Interval.LowerBound);
     279      }
     280
     281      if (!constraint.Interval.Contains(modelBound.UpperBound)) {
     282        error += Math.Abs(modelBound.UpperBound - constraint.Interval.UpperBound);
     283      }
     284
     285      return error;
    532286    }
    533287

  • branches/3073_IA_constraint_splitting_reintegration/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/Interpreter/IntervalArithCompiledExpressionBoundsEstimator.cs

    r17890 r17891  
    11using HEAL.Attic;
    2 
    32using HeuristicLab.Common;
    43using HeuristicLab.Core;
    … …  
    65using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    76using HeuristicLab.Parameters;
    8 
    97using System;
    108using System.Collections.Generic;
    … …  
    1210using System.Linq.Expressions;
    1311
    14 namespace HeuristicLab.Problems.DataAnalysis.Symbolic
    15 {
     12namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    1613  [StorableType("60015D64-5D8B-408A-90A1-E4111BC114D4")]
    17   [Item("IA Compiled Expression Bounds Estimator", "Compile a symbolic model into a lambda and use it to evaluate model bounds.")]
    18   public class IACompiledExpressionBoundsEstimator : ParameterizedNamedItem, IBoundsEstimator
    19   {
     14  [Item("Interval Arithmetic Compiled Expression Bounds Estimator", "Compile a symbolic model into a lambda and use it to evaluate model bounds.")]
     15  public class IntervalArithCompiledExpressionBoundsEstimator : ParameterizedNamedItem, IBoundsEstimator {
    2016    // interval method names
    2117    private static readonly Dictionary<byte, string> methodName = new Dictionary<byte, string>() {
    … …  
    3935
    4036    private const string EvaluatedSolutionsParameterName = "EvaluatedSolutions";
    41     private const string UseIntervalSplittingParameterName = "Use Interval splitting";
    42     private const string MaxSplitParameterName = "MaxSplit";
    43     private const string MinWidthParameterName = "MinWidth";
    44 
    4537    public IFixedValueParameter<IntValue> EvaluatedSolutionsParameter {
    4638      get => (IFixedValueParameter<IntValue>)Parameters[EvaluatedSolutionsParameterName];
    4739    }
    48 
    49     public IFixedValueParameter<BoolValue> UseIntervalSplittingParameter {
    50       get => (IFixedValueParameter<BoolValue>)Parameters[UseIntervalSplittingParameterName];
    51     }
    52 
    53     public IFixedValueParameter<IntValue> MaxSplitParameter {
    54       get => (IFixedValueParameter<IntValue>)Parameters[MaxSplitParameterName];
    55     }
    56 
    57     public IFixedValueParameter<DoubleValue> MinWidthParameter {
    58       get => (IFixedValueParameter<DoubleValue>)Parameters[MinWidthParameterName];
    59     }
    60 
    61     public int MaxSplit {
    62       get => MaxSplitParameter.Value.Value;
    63       set => MaxSplitParameter.Value.Value = value;
    64     }
    65 
    66     public double MinWidth {
    67       get => MinWidthParameter.Value.Value;
    68       set => MinWidthParameter.Value.Value = value;
    69     }
    70 
    7140    public int EvaluatedSolutions {
    7241      get => EvaluatedSolutionsParameter.Value.Value;
    … …  
    7443    }
    7544
    76     public bool UseIntervalSplitting {
    77       get => UseIntervalSplittingParameter.Value.Value;
    78       set => UseIntervalSplittingParameter.Value.Value = value;
    79     }
    80 
    8145    private readonly object syncRoot = new object();
    8246
    83     public IACompiledExpressionBoundsEstimator() : base("IA Bounds Estimator",
     47    public IntervalArithCompiledExpressionBoundsEstimator() : base("Interval Arith Bounds Estimator",
    8448      "Estimates the bounds of the model with interval arithmetic, by first compiling the model into a lambda.") {
    8549      Parameters.Add(new FixedValueParameter<IntValue>(EvaluatedSolutionsParameterName,
    8650        "A counter for the total number of solutions the estimator has evaluated.", new IntValue(0)));
    87       Parameters.Add(new FixedValueParameter<BoolValue>(UseIntervalSplittingParameterName,
    88         "Defines whether interval splitting is activated or not.", new BoolValue(false)));
    89       Parameters.Add(new FixedValueParameter<IntValue>(MaxSplitParameterName,
    90         "Defines the number of iterations of splitting.", new IntValue(200)));
    91       Parameters.Add(new FixedValueParameter<DoubleValue>(MinWidthParameterName,
    92         "Width of interval, after the splitting should stop.", new DoubleValue(0.0)));
    9351    }
    9452
    9553    [StorableConstructor]
    96     private IACompiledExpressionBoundsEstimator(StorableConstructorFlag _) : base(_) { }
    97 
    98     private IACompiledExpressionBoundsEstimator(IACompiledExpressionBoundsEstimator original, Cloner cloner) : base(original, cloner) { }
     54    private IntervalArithCompiledExpressionBoundsEstimator(StorableConstructorFlag _) : base(_) { }
     55
     56    private IntervalArithCompiledExpressionBoundsEstimator(IntervalArithCompiledExpressionBoundsEstimator original, Cloner cloner) : base(original, cloner) { }
    9957
    10058    public override IDeepCloneable Clone(Cloner cloner) {
    101       return new IACompiledExpressionBoundsEstimator(this, cloner);
    102     }
    103 
    104 
    105 
    106     public double CheckConstraint(ISymbolicExpressionTree tree, IntervalCollection variableRanges, ShapeConstraint constraint) {
    107       if (!UseIntervalSplitting) {
    108         var modelBound = GetModelBound(tree, variableRanges);
    109         if (constraint.Interval.Contains(modelBound)) return 0.0;
    110         return Math.Abs(modelBound.LowerBound - constraint.Interval.LowerBound) +
    111                Math.Abs(modelBound.UpperBound - constraint.Interval.UpperBound);
    112       }
    113 
    114       if (double.IsNegativeInfinity(constraint.Interval.LowerBound) &&
    115           double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
    116         return 0.0;
    117       }
    118 
    119       //ContainsVariableMultipleTimes(tree, out var variables);
    120 
    121       lock (syncRoot) { EvaluatedSolutions++; }
    122 
    123       double upperBound;
    124       if (double.IsNegativeInfinity(constraint.Interval.LowerBound)) {
    125         upperBound = EstimateUpperBound(tree, variableRanges.GetReadonlyDictionary(), MaxSplit, MinWidth);
    126 
    127         return upperBound <= constraint.Interval.UpperBound
    128           ? 0.0
    129           : Math.Abs(upperBound - constraint.Interval.UpperBound);
    130       }
    131 
    132       double lowerBound;
    133       if (double.IsPositiveInfinity(constraint.Interval.UpperBound)) {
    134         lowerBound = EstimateLowerBound(tree, variableRanges.GetReadonlyDictionary(), MaxSplit, MinWidth);
    135 
    136         return lowerBound <= constraint.Interval.LowerBound
    137           ? 0.0
    138           : Math.Abs(lowerBound - constraint.Interval.LowerBound);
    139       }
    140 
    141       var ranges = variableRanges.GetReadonlyDictionary();
    142       lowerBound = EstimateLowerBound(tree, ranges, MaxSplit, MinWidth);
    143       upperBound = EstimateUpperBound(tree, ranges, MaxSplit, MinWidth);
    144 
    145       var res = 0.0;
    146 
    147       res += upperBound <= constraint.Interval.UpperBound ? 0.0 : Math.Abs(upperBound - constraint.Interval.UpperBound);
    148       res += lowerBound <= constraint.Interval.LowerBound ? 0.0 : Math.Abs(lowerBound - constraint.Interval.LowerBound);
    149 
    150       return res;
     59      return new IntervalArithCompiledExpressionBoundsEstimator(this, cloner);
     60    }
     61
     62    public double GetConstraintViolation(ISymbolicExpressionTree tree, IntervalCollection variableRanges, ShapeConstraint constraint) {
     63      var modelBound = GetModelBound(tree, variableRanges);
     64      if (constraint.Interval.Contains(modelBound)) return 0.0;
     65      return Math.Abs(modelBound.LowerBound - constraint.Interval.LowerBound) +
     66             Math.Abs(modelBound.UpperBound - constraint.Interval.UpperBound);
    15167    }
    15268
    … …  
    15773    public Interval GetModelBound(ISymbolicExpressionTree tree, IntervalCollection variableRanges) {
    15874      lock (syncRoot) { EvaluatedSolutions++; }
    159       var resultInterval = UseIntervalSplitting
    160         ? EstimateBounds(tree, variableRanges.GetReadonlyDictionary(), MaxSplit, MinWidth)
    161         : EstimateBounds(tree, variableRanges.GetReadonlyDictionary());
     75      var resultInterval = EstimateBounds(tree, variableRanges.GetReadonlyDictionary());
    16276
    16377      if (resultInterval.IsInfiniteOrUndefined || resultInterval.LowerBound <= resultInterval.UpperBound)
    … …  
    298212        }
    299213      }
    300       Array.Resize<Interval>(ref inputIntervals, count);
     214      Array.Resize(ref inputIntervals, count);
    301215      return variableIndices;
    302216    }
    … …  
    309223    }
    310224
    311     public static Interval EstimateBounds(ISymbolicExpressionTree tree, IReadOnlyDictionary<string, Interval> variableRanges, int n = 0, double w = 1e-5) {
     225    public static Interval EstimateBounds(ISymbolicExpressionTree tree, IReadOnlyDictionary<string, Interval> variableRanges) {
    312226      var variableIndices = GetVariableIndices(tree, variableRanges, out Interval[] x);
    313227      var f = Compile(tree, variableRanges, variableIndices);
    314       if (n == 0) return f(x);
    315       var inf = EstimateBound(x, f, true, n, w);
    316       var sup = EstimateBound(x, f, false, n, w);
    317       return inf < sup ? new Interval(inf, sup) : new Interval(sup, inf);
    318     }
    319     public  double EstimateLowerBound(ISymbolicExpressionTree tree, IReadOnlyDictionary<string, Interval> variableRanges, int n = 1000, double w = 1e-5) {
    320       var variableIndices = GetVariableIndices(tree, variableRanges, out Interval[] x);
    321       var f = Compile(tree, variableRanges, variableIndices);
    322       var inf = EstimateBound(x, f, true, n, w);
    323       return inf;
    324     }
    325 
    326     public double EstimateUpperBound(ISymbolicExpressionTree tree, IReadOnlyDictionary<string, Interval> variableRanges, int n = 1000, double w = 1e-5) {
    327       var variableIndices = GetVariableIndices(tree, variableRanges, out Interval[] x);
    328       var f = Compile(tree, variableRanges, variableIndices);
    329       var sup = EstimateBound(x, f, false, n, w);
    330       return sup;
    331     }
    332 
    333     static double EstimateBound(Interval[] x, Func<Interval[], Interval> f, bool m = false, int n = 1000, double w = 1e-4) {
    334       double getBound(Interval iv) => m ? iv.LowerBound : -iv.UpperBound;
    335       double getVolume(Interval[] box) => box.Aggregate(1.0, (acc, iv) => acc * iv.Width);
    336 
    337       var splits = Enumerable.Range(0, x.Length).Select(_ => new List<Interval>()).ToArray();
    338       var newbox = new Interval[x.Length];
    339 
    340       int compare(Tuple<double, double, Interval[]> a, Tuple<double, double, Interval[]> b) {
    341         var res = a.Item1.CompareTo(b.Item1);
    342         if (res == 0) {
    343           res = b.Item2.CompareTo(a.Item2);
    344         }
    345         return res;
    346       }
    347 
    348       var q = new SortedSet<Tuple<double, double, Interval[]>>(Comparer<Tuple<double, double, Interval[]>>.Create(compare)) {
    349         Tuple.Create(getBound(f(x)), getVolume(x), x)
    350       };
    351 
    352 
    353       var bestBound = double.MaxValue;
    354 
    355       // examine all the ordered pairs in the cartesian product
    356       void next_pair(int i) {
    357         if (i == splits.Length) {
    358           var tmp = newbox.ToArray(); // make a copy to put in the queue
    359           q.Add(Tuple.Create(getBound(f(tmp)), getVolume(tmp), tmp));
    360           return;
    361         }
    362 
    363         foreach (var iv in splits[i]) {
    364           newbox[i] = iv;
    365           next_pair(i + 1);
    366         }
    367       }
    368 
    369       while (q.Count > 0 && n-- > 0) {
    370         var currentBound = q.Min; q.Remove(currentBound);
    371         var bound = currentBound.Item1;
    372         var box = currentBound.Item3;
    373 
    374         if (!box.Any(b => b.Width > w)) {
    375           bestBound = Math.Min(bestBound, bound);
    376           continue;
    377         }
    378 
    379         // do the splits
    380         for (int i = 0; i < box.Length; ++i) {
    381           splits[i].Clear();
    382           var iv = box[i];
    383           if (iv.Width > w) {
    384             var t = iv.Split();
    385             splits[i].Add(t.Item1);
    386             splits[i].Add(t.Item2);
    387           } else {
    388             splits[i].Add(iv);
    389           }
    390         }
    391         next_pair(0);
    392       }
    393       if (q.Count > 0) {
    394         bestBound = Math.Min(bestBound, q.First().Item1);
    395       }
    396       return m ? bestBound : -bestBound;
     228      return f(x);
    397229    }
    398230    #endregion

  • branches/3073_IA_constraint_splitting_reintegration/HeuristicLab.Problems.DataAnalysis.Symbolic/3.4/IntervalUtil.cs

    r17887 r17891  
    66namespace HeuristicLab.Problems.DataAnalysis.Symbolic {
    77  public static class IntervalUtil {
    8     public static double IntervalConstraintViolation(
    9       ShapeConstraint constraint, IBoundsEstimator estimator, IntervalCollection intervalCollection,
     8    public static IEnumerable<double> GetConstraintViolations(
     9      IEnumerable<ShapeConstraint> constraints, IBoundsEstimator estimator, IntervalCollection intervalCollection,
    1010      ISymbolicExpressionTree solution) {
    11       var variableRanges = intervalCollection.GetReadonlyDictionary();
     11      return constraints.Select(constraint => GetConstraintViolation(constraint, estimator, intervalCollection, solution)).ToList();
     12    }
    1213
    13       if (constraint.Variable != null && !variableRanges.ContainsKey(constraint.Variable)) {
     14    public static double GetConstraintViolation(
     15      ShapeConstraint constraint, IBoundsEstimator estimator, IntervalCollection variableRanges,
     16      ISymbolicExpressionTree tree) {
     17      var varRanges = variableRanges.GetReadonlyDictionary();
     18
     19      if (constraint.Variable != null && !varRanges.ContainsKey(constraint.Variable)) {
    1420        throw new ArgumentException(
    1521          $"The given variable {constraint.Variable} in the constraint does not exist in the model.",
    16           nameof(ShapeConstraintsParser));
     22          nameof(constraint));
    1723      }
    1824
    19       //Create new variable ranges for defined regions
     25      // Create new variable ranges for defined regions
    2026      var regionRanges = new IntervalCollection();
    21       foreach (var kvp in variableRanges) {
    22         if (kvp.Key != constraint.Target && constraint.Regions.GetReadonlyDictionary().TryGetValue(kvp.Key, out var val)) {
     27      foreach (var kvp in varRanges) {
     28        if (constraint.Regions.GetReadonlyDictionary().TryGetValue(kvp.Key, out var val)) {
    2329          regionRanges.AddInterval(kvp.Key, val);
    2430        } else {
    … …  
    2733      }
    2834
    29       var error = 0.0;
    3035      if (!constraint.IsDerivative) {
    31         error = estimator.CheckConstraint(solution, regionRanges, constraint);
     36        return estimator.GetConstraintViolation(tree, regionRanges, constraint);
    3237      } else {
    33         var tree = solution;
    3438        for (var i = 0; i < constraint.NumberOfDerivations; ++i) {
    3539          if (!estimator.IsCompatible(tree) || !DerivativeCalculator.IsCompatible(tree)) {
    36             throw new ArgumentException("Cube, Root, Power symbols are not supported.");
     40            throw new ArgumentException("The tree contains an unsupported symbol.");
    3741          }
    3842
    … …  
    4044        }
    4145
    42         error = estimator.CheckConstraint(tree, regionRanges, constraint);
     46        return estimator.GetConstraintViolation(tree, regionRanges, constraint);
    4347      }
    44 
    45       return error;
    4648    }
    4749
    48     public static IEnumerable<double> IntervalConstraintsViolation(
    49       IEnumerable<ShapeConstraint> constraints, IBoundsEstimator estimator, IntervalCollection intervalCollection,
    50       ISymbolicExpressionTree solution) {
    51       return constraints.Select(constraint => IntervalConstraintViolation(constraint, estimator, intervalCollection, solution)).ToList();
    52     }
    5350  }
    5451}
Note: See TracChangeset for help on using the changeset viewer.