Changeset 15907


Ignore:
Timestamp:
04/16/18 15:19:58 (4 years ago)
Author:
lkammere
Message:

#2886: Changes in search heuristic for solving Poly-10 problem. Adapt tree evaluation to cover non-terminal symbols.

Location:
branches/2886_SymRegGrammarEnumeration
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/Grammar.cs

    r15883 r15907  
    176176
    177177    public double EvaluatePhrase(SymbolString s, IRegressionProblemData problemData, bool optimizeConstants) {
    178       // Create sentences without Expression symbols.
    179       Symbol[] sEval = new Symbol[s.Count()];
    180 
    181       for (int i = 0; i < sEval.Length; i++) {
    182         Symbol currSym = s[i];
    183         if (currSym is NonterminalSymbol && currSym != Expr)
    184           return 0.0;
    185 
    186         if (currSym == Expr) {
    187           sEval[i] = Const;
    188         } else {
    189           sEval[i] = currSym;
    190         }
    191       }
    192 
    193       SymbolicExpressionTree tree = ParseSymbolicExpressionTree(new SymbolString(sEval));
     178      SymbolicExpressionTree tree = ParseSymbolicExpressionTree(s);
     179
    194180      double r2 = RSquaredEvaluator.Evaluate(problemData, tree, optimizeConstants);
    195181
     
    208194    public SymbolicExpressionTree ParseSymbolicExpressionTree(SymbolString sentence) {
    209195      Debug.Assert(sentence.Any(), "Trying to evaluate empty sentence!");
    210       Debug.Assert(sentence.All(s => s is TerminalSymbol), "Trying to evaluate symbol sequence with nonterminalsymbols!");
    211196
    212197      var rootNode = rootSy.CreateTreeNode();
     
    214199      rootNode.AddSubtree(startNode);
    215200
    216       Stack<TerminalSymbol> parseStack = new Stack<TerminalSymbol>(sentence.OfType<TerminalSymbol>());
     201      Stack<Symbol> parseStack = new Stack<Symbol>(sentence);
    217202      startNode.AddSubtree(ParseSymbolicExpressionTree(parseStack));
    218203
     
    220205    }
    221206
    222     public ISymbolicExpressionTreeNode ParseSymbolicExpressionTree(Stack<TerminalSymbol> parseStack) {
    223       TerminalSymbol currentSymbol = parseStack.Pop();
     207    public ISymbolicExpressionTreeNode ParseSymbolicExpressionTree(Stack<Symbol> parseStack) {
     208      Symbol currentSymbol = parseStack.Pop();
    224209
    225210      ISymbolicExpressionTreeNode parsedSubTree = null;
     
    273258        varNode.VariableName = currentSymbol.StringRepresentation;
    274259        parsedSubTree = varNode;
     260
     261      } else if (currentSymbol is NonterminalSymbol) {
     262        ConstantTreeNode constNode = (ConstantTreeNode)constSy.CreateTreeNode();
     263        constNode.Value = 0.0;
     264        parsedSubTree = constNode;
    275265      }
    276266
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/GrammarEnumerationAlgorithm.cs

    r15883 r15907  
    186186
    187187              // Is the best solution found? (only if RSquaredEvaluator is activated)
    188               if (Results.ContainsKey(RSquaredEvaluator.BestTrainingQualityResultName) && ((DoubleValue)Results[RSquaredEvaluator.BestTrainingQualityResultName].Value).Value == 1.0) {
    189                 UpdateView(force: true);
    190                 return;
     188              if (Results.ContainsKey(RSquaredEvaluator.BestTrainingQualityResultName)) {
     189                double r2 = ((DoubleValue)Results[RSquaredEvaluator.BestTrainingQualityResultName].Value).Value;
     190                if (r2.IsAlmost(1.0)) {
     191                  UpdateView(force: true);
     192                  return;
     193                }
    191194              }
    192195
     
    210213
    211214    protected double GetPriority(SymbolString phrase) {
    212       return 1.0 - Grammar.EvaluatePhrase(phrase, Problem.ProblemData, OptimizeConstants);
     215      double complexity = (double)Grammar.GetComplexity(phrase);
     216
     217      double length = phrase.Count();
     218      double relLength = (length - 2) / (MaxComplexity * 7);
     219      double r2 = Grammar.EvaluatePhrase(phrase, Problem.ProblemData, OptimizeConstants);
     220      double error = 1.0 - r2;
     221
     222      double variables = 0;
     223      for (int i = 0; i < phrase.Count(); i++) {
     224        if (phrase[i] is VariableTerminalSymbol) variables++;
     225      }
     226
     227      double variableRatio = 1.0 - variables / complexity;
     228
     229      return 1.5*relLength + error;
    213230    }
    214231
  • branches/2886_SymRegGrammarEnumeration/HeuristicLab.Algorithms.DataAnalysis.SymRegGrammarEnumeration/GrammarEnumeration/SearchDataStructure.cs

    r15883 r15907  
    4848
    4949    private void InitPriorityQueue() {
    50       PriorityQueue<double, int> queue = new PriorityQueue<double, int>(double.MaxValue, double.MinValue, (int)Math.Pow(2.0, 20.0) / 4);
     50      int capacity = 10000000;
     51      PriorityQueue<double, int> queue = new PriorityQueue<double, int>(double.MaxValue, double.MinValue, capacity);
    5152      storeInternal = (hash, prio) => queue.Insert(prio, hash);
    5253      fetchInternal = () => {
  • branches/2886_SymRegGrammarEnumeration/Test/GrammarEnumerationTest.cs

    r15883 r15907  
    304304        xSymbol, ySymbol, mulSymbol, ySymbol, mulSymbol, constSymbol, mulSymbol,
    305305        ySymbol, ySymbol, mulSymbol, constSymbol, mulSymbol, addSymbol, constSymbol, addSymbol, invSymbol,
    306         constSymbol, addSymbol 
     306        constSymbol, addSymbol
    307307      });
    308308
     
    339339        ySymbol, ySymbol, mulSymbol, constSymbol, mulSymbol, addSymbol,
    340340        ySymbol, constSymbol, mulSymbol, addSymbol,
    341         constSymbol, addSymbol 
     341        constSymbol, addSymbol
    342342      });
    343343
     
    362362
    363363      alg.Start();
    364      
     364
    365365      TerminalSymbol constSymbol = alg.Grammar.Const;
    366366      TerminalSymbol xSymbol = alg.Grammar.VarTerminals.First();
     
    370370      TerminalSymbol divSymbol = alg.Grammar.Inv;
    371371
    372      
     372
    373373      // x x mul c mul y y mul c mul add const add inv const mul const add
    374374      SymbolString targetSolution = new SymbolString(new[] {
    375         xSymbol, xSymbol, mulSymbol, constSymbol, mulSymbol, 
     375        xSymbol, xSymbol, mulSymbol, constSymbol, mulSymbol,
    376376        ySymbol, ySymbol, mulSymbol, constSymbol, mulSymbol, addSymbol,
    377377        constSymbol, addSymbol, divSymbol,
     
    410410        xSymbol, xSymbol, mulSymbol, xSymbol, mulSymbol, constSymbol, mulSymbol,
    411411        ySymbol, ySymbol, mulSymbol, ySymbol, mulSymbol, constSymbol, mulSymbol, addSymbol,
    412         ySymbol, constSymbol, mulSymbol, addSymbol, 
     412        ySymbol, constSymbol, mulSymbol, addSymbol,
    413413        xSymbol, constSymbol, mulSymbol, addSymbol,
    414414        constSymbol, addSymbol
     
    422422
    423423      // Evaluate
     424      EvaluateGrammarEnumeration();
     425    }
     426
     427    [TestMethod]
     428    [TestProperty("Goal", "Poly-10 derivatives")]
     429    public void MctsSymbReg_NoConstants_Poly10_Part1() {
     430      alg.MaxComplexity = 12;
     431      alg.OptimizeConstants = false;
     432      var regProblem = new PolyTen(123).GenerateRegressionData();
     433
     434      //  Y = X1*X2 + X3*X4 + X5*X6 + X1*X7*X9 + X3*X6*X10
     435      //  Y' = X1*X2 + X3*X4 + X5*X6
     436      // simplify problem by changing target
     437      var ds = ((Dataset)regProblem.Dataset).ToModifiable();
     438      var ys = ds.GetDoubleValues("Y").ToArray();
     439      var x1 = ds.GetDoubleValues("X1").ToArray();
     440      var x2 = ds.GetDoubleValues("X2").ToArray();
     441      var x3 = ds.GetDoubleValues("X3").ToArray();
     442      var x4 = ds.GetDoubleValues("X4").ToArray();
     443      var x5 = ds.GetDoubleValues("X5").ToArray();
     444      var x6 = ds.GetDoubleValues("X6").ToArray();
     445      var x7 = ds.GetDoubleValues("X7").ToArray();
     446      var x8 = ds.GetDoubleValues("X8").ToArray();
     447      var x9 = ds.GetDoubleValues("X9").ToArray();
     448      var x10 = ds.GetDoubleValues("X10").ToArray();
     449      for (int i = 0; i < ys.Length; i++) {
     450        //ys[i] -= x1[i] * x7[i] * x9[i];
     451        //ys[i] -= x3[i] * x6[i] * x10[i];
     452      }
     453      ds.ReplaceVariable("Y", ys.ToList());
     454
     455      alg.Problem.ProblemData = new RegressionProblemData(ds, regProblem.AllowedInputVariables, regProblem.TargetVariable);
     456
     457      alg.Start();
     458
    424459      EvaluateGrammarEnumeration();
    425460    }
Note: See TracChangeset for help on using the changeset viewer.