1  using System;


2  using System.Collections.Generic;


3  using System.Linq;


4  using System.Security;


5  using System.Security.AccessControl;


6  using System.Text;


7  using HeuristicLab.Common;


8 


9  namespace HeuristicLab.Problems.GrammaticalOptimization {


10  public class SymbolicRegressionPoly10Problem : IProblem {


11  // private const string grammarString = @"


12  // G(E):


13  // E > V  V+E  VE  V*E  (E)


14  // V > a .. j


15  // ";


16  private const string grammarString = @"


17  G(E):


18  E > a  b  c  d  e  f  g  h  i  j  a+E  b+E  c+E  d+E  e+E  f+E  g+E  h+E  i+E  j+E  a*E  b*E  c*E  d*E  e*E  f*E  g*E  h*E  i*E  j*E


19  ";


20 


21 


22  private readonly IGrammar grammar;


23  private readonly ExpressionInterpreter interpreter;


24 


25  private readonly int N;


26  private readonly double[][] x;


27  private readonly double[] y;


28 


29  public SymbolicRegressionPoly10Problem() {


30  this.grammar = new Grammar(grammarString);


31  this.interpreter = new ExpressionInterpreter();


32 


33  this.N = 500;


34  this.x = new double[N][];


35  this.y = new double[N];


36 


37  GenerateData();


38  }


39 


40  private void GenerateData() {


41  // generate data with fixed seed to make sure that data is always the same


42  var rand = new Random(31415);


43  for (int i = 0; i < N; i++) {


44  x[i] = new double[10];


45  for (int j = 0; j < 10; j++) {


46  x[i][j] = rand.NextDouble() * 2  1;


47  }


48  // poly10 no noise


49  /* a*b + c*d + e*f + a*g*i + c*f*j */


50  y[i] = x[i][0] * x[i][1] +


51  x[i][2] * x[i][3] +


52  x[i][4] * x[i][5] +


53  x[i][0] * x[i][6] * x[i][8] +


54  x[i][2] * x[i][5] * x[i][9];


55  }


56  }


57 


58  public double GetBestKnownQuality(int maxLen) {


59  // for now only an upper bound is returned, ideally we have an R² of 1.0


60  // the optimal R² can only be reached for sentences of at least 23 symbols


61  return 1.0;


62  }


63 


64  public IGrammar Grammar {


65  get { return grammar; }


66  }


67 


68  public double Evaluate(string sentence) {


69  return RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])).ToArray());


70  }


71 


72  private double RSq(IEnumerable<double> xs, IEnumerable<double> ys) {


73  // two pass implementation, but we don't care


74  var meanX = xs.Average();


75  var meanY = ys.Average();


76 


77  var s = 0.0;


78  var ssX = 0.0;


79  var ssY = 0.0;


80  foreach (var p in xs.Zip(ys, (x, y) => new { x, y })) {


81  s += (p.x  meanX) * (p.y  meanY);


82  ssX += Math.Pow(p.x  meanX, 2);


83  ssY += Math.Pow(p.y  meanY, 2);


84  }


85 


86  if (s.IsAlmost(0)) return 0;


87  if (ssX.IsAlmost(0)  ssY.IsAlmost(0)) return 0;


88  return s * s / (ssX * ssY);


89  }


90 


91 


92  // right now only + and * is supported


93  public string Hash(string terminalPhrase) {


94  var terms = terminalPhrase.Split('+');


95  return string.Join("+", terms.Select(term => string.Join("", term.Replace("*", "").OrderBy(ch => ch)))


96  .OrderBy(term => term));


97  }


98  }


99  }

