Changeset 12014


Ignore:
Timestamp:
02/16/15 09:14:38 (7 years ago)
Author:
gkronber
Message:

#2283: worked on transformation of arithmetic expressions to canonical form

Location:
branches/HeuristicLab.Problems.GrammaticalOptimization
Files:
1 added
9 edited

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/ExpressionExtender.cs

    r11981 r12014  
    1919    // supports the grammar
    2020    // G(E):
    21     //     E -> V | V+E | V-E | V*E | V%E | (E)
     21    //     E -> V | V+E | V-E | V*E | V%E | V/E | (E)
    2222    //     V -> <variables>
    2323    //     ";
    2424
    25     // transformations:
    26     // - transform c*b*a to a*b*c (lexicographic ordering for factors, cached)
    27     // - transfrom - to + (assumed optimized constants for terms)
    28 
     25    // might produce expressions of the form |/x
     26    // the pipe symbol | is used for the constant one (in comparison to other constants)
    2927    private string sentence;
    3028    private int syIdx;
    3129
    3230    public string CanonicalRepresentation(string phrase) {
    33       throw new NotImplementedException();
    3431      InitLex(phrase);
    3532      var e = CanonicalExpr();
    36       return e.ToString();
     33      return e.ToString(); 
    3734    }
    3835
     
    9794          NewSy();
    9895          f = CanonicalFact();
    99           f.Invert();
    100           if (f != null) factors.Add(f);
     96          // if there is only one term we can add multiple inverted simple factors instead of the whole inverted expression
     97          if (!f.IsSimpleFactor && f.Expr.Terms.Count == 1) {
     98            foreach (var invF in f.Expr.Terms.First().Factors) {
     99              if (invF.ToString() == "|") continue;
     100              invF.Invert();
     101              factors.Add(invF);
     102            }
     103          } else {
     104            f.Invert();
     105            if (f != null) factors.Add(f);
     106          }
    101107        }
    102108        curSy = CurSy();
    103109      }
     110
     111      factors = CancelFactors(factors).ToList();
    104112      return ExpandFactors(factors);
    105113    }
    106114
    107     /*
    108     private List<Factor> CancelFactors(Term t) {
    109       var nonInvF = t.Factors.Where(f => !f.IsInverse).ToArray();
    110       var invF = t.Factors.Where(f => f.IsInverse).ToArray();
    111 
    112       var result = new List<Factor>();
    113       foreach (var f in nonInvF) {
    114         if (!invF.Contains(f)) {
    115           result.Add(f);
    116         }
    117       }
    118       if (result.Count == 0) result.Add(new Factor('1'));
    119       return result;
    120     }
    121     */
    122115    // canonical fact returns a factor (either a singe variable, or a set of terms)
    123116    private Factor CanonicalFact() {
     
    144137
    145138    // a list of factors (symbols, or expressions, and possibly inverses are read
    146     // a lis to factors symbols or expressions and possibly inverses are produced
     139    // a list to factors symbols or expressions and possibly inverses are produced
    147140    // all non-inverse expression factors are expanded
    148141    private Expr ExpandFactors(IEnumerable<Factor> factors) {
     
    154147      Expr currentFact = null;
    155148      var firstFactor = factors.First();
    156       if (firstFactor.IsSimpleFactor) currentFact = new Expr(new Term(firstFactor));
     149      if (firstFactor.IsSimpleFactor || firstFactor.IsInverse) currentFact = new Expr(new Term(firstFactor));
    157150      else currentFact = firstFactor.Expr;
    158151
     
    180173      var results = new List<Factor>(factors);
    181174      foreach (var f in factorsArr) {
    182         if (f.ToString() == "1") results.Remove(f);
     175        if (f.ToString() == "|") results.Remove(f);
     176        if (f.ToString() == "|/(|)") results.Remove(f);
    183177        if (f.IsInverse) {
    184178          // find matching
    185179          Factor match;
    186           if (f.IsSimpleFactor) match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Symbol.Equals(other.Symbol));
    187           else match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Expr.Equals(other.Expr));
     180          match = factorsArr.FirstOrDefault(other => !other.IsInverse && f.Cancels(other));
    188181          if (match != null) {
     182            results.Remove(f);
     183            var idx = results.IndexOf(match);
     184
    189185            results.Remove(match);
    190             results.Remove(f);
     186            if (!results.Any())
     187              results.Insert(idx, new Factor('|')); // when the factor is the last one then insert a one
     188
     189            // also mark as cancelled in the factorsArr
     190            idx = Array.IndexOf(factorsArr, match);
     191            factorsArr[idx] = new Factor('|');
    191192          }
    192193        }
    193194      }
    194       if (results.Count == 0) results.Add(new Factor('1'));
     195      // remove all unnecessary "1* factors"
     196
     197      if (results.Count == 0) results.Add(new Factor('|'));
    195198      return results;
    196199    }
     
    273276        this.inv = !inv;
    274277      }
     278      public bool Cancels(Factor other) {
     279        if (this.inv == other.inv) return false;
     280        if (this.Expr != null && other.Expr == null) return false;
     281        if (this.Expr == null && other.Expr != null) return false;
     282        if (Expr == null) return this.Symbol.Equals(other.symbol);
     283        else return this.Expr.CompareTo(other.Expr) == 0;
     284      }
    275285
    276286      public int CompareTo(Factor other) {
     
    294304        var s = Expr == null ? symbol.ToString() : "(" + expr.ToString() + ")";
    295305        if (IsInverse) {
    296           return "1/" + s;
     306          return "|/" + s;
    297307        } else return s;
    298308      }
     
    356366        var other = obj as Expr;
    357367        if (other == null) return false;
    358         //if (this.Inverse != other.Inverse) return false;
    359368        if (this.Terms.Count() != other.Terms.Count()) return false;
    360369        return this.Terms.Intersect(other.Terms).Count() == this.Terms.Count;
    361370      }
     371
    362372      public override int GetHashCode() {
    363373        var h = 31415;
     
    388398      return ContainsNonTerminal(term.Factors);
    389399    }
    390 
    391 
    392     /*
    393 
    394     internal class FactorComparer : IComparer<char> {
    395       public int Compare(char x, char y) {
    396         if (IsNonTerminal(x) && !IsNonTerminal(y)) {
    397           return 1;
    398         } else if (!IsNonTerminal(x) && IsNonTerminal(y)) {
    399           return -1;
    400         } else if (IsNonTerminal(x) && IsNonTerminal(y)) {
    401           return x.CompareTo(y);
    402         } else {
    403           return x.CompareTo(y);
    404         }
    405       }
    406     }*/
    407400  }
    408401}
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/ExpressionCompiler.cs

    r11972 r12014  
    1717    // does not compile to IL it is only necessary to calculate gradients for parameter optimization
    1818    // Expr -> Term { ('+' | '-' | '^' ) Term }
    19     // Term -> Fact { ('*' | '%') Fact }
    20     // Fact -> '!' Expr | '(' Expr ')' | Var | const
     19    // Term -> Fact { ('*' | '%' | '/') Fact }
     20    // Fact -> '!' Expr | '(' Expr ')' | Var | const | one
    2121    // Var -> 'a'..'z'
    2222    // const -> '0' .. '9'
     23    // one -> |    // pipe symbol for constant one instead of ERC 1
    2324
    2425    // constants are completely ignored, instead we introduce a multiplicative constant factor for each term and an additive constant term for each expression
     
    9495      if (f != null) factors.Add(f);
    9596      var curSy = CurSy();
    96       while (curSy == '*' || curSy == '%') {
     97      while (curSy == '*' || curSy == '%' || curSy == '/') { // division and protected division symbols are handled in the same way
    9798        if (curSy == '*') {
    9899          NewSy();
     
    134135        r = variables[varIdx];
    135136        NewSy();
     137      } else if (curSy == '|') {
     138        // pipe symbol is used in the expressionextender to represent constant one (|/x).
     139        // this is necessary because we also use symbols 0..9 as indices for ERCs
     140        r = 1.0;
     141        NewSy();
    136142      } else if (curSy >= '0' && curSy <= '9') {
    137143        int o = (byte)curSy - (byte)'0';
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs

    r11981 r12014  
    99using System.Text;
    1010using AutoDiff;
     11using HeuristicLab.Algorithms.Bandits;
    1112using HeuristicLab.Common;
    1213using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
     
    128129        return OptimizeConstantsAndEvaluate(sentence);
    129130      else {
     131        var extender = new ExpressionExtender();
     132
     133        Debug.Assert(SimpleEvaluate(sentence) == SimpleEvaluate(extender.CanonicalRepresentation(sentence)));
    130134        return SimpleEvaluate(sentence);
    131135      }
     
    143147
    144148    public string CanonicalRepresentation(string phrase) {
    145       return phrase;
     149      var extender = new ExpressionExtender();
     150      return extender.CanonicalRepresentation(phrase);
    146151    }
    147152
    148153    public IEnumerable<Feature> GetFeatures(string phrase) {
    149       // first generate canonical expression (which must not contain ())
    150       // recursively split into expressions
    151       // for each expression split into terms
    152       // for each term order factors to canonical // ../E = * 1/E
     154      phrase = CanonicalRepresentation(phrase);
    153155      return new Feature[] { new Feature(phrase, 1.0) };
    154156    }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/ExpressionInterpreter.cs

    r11981 r12014  
    9292      r = Fact(d, erc);
    9393      var curSy = CurSy();
    94       while (curSy == '*' || curSy == '%') {
     94      while (curSy == '*' || curSy == '%' || curSy == '/') { // division and protected division symbols are handled in the same way
    9595        if (curSy == '*') {
    9696          NewSy();
     
    124124        r = d[o];
    125125        NewSy();
     126      } else if (curSy == '|') {
     127        // pipe symbol is used in the expressionextender to represent constant one (|/x).
     128        // this is necessary because we also use symbols 0..9 as indices for ERCs
     129        r = 1.0;
     130        NewSy();
    126131      } else /* if (curSy >= '0' && curSy <= '9') */ {
    127132        int o = (byte)curSy - (byte)'0';
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs

    r11980 r12014  
    184184        Debug.Assert(maxLenOfReplacement > 0);
    185185
    186         var alts = GetTerminalAlternatives(nt).Where(alt => MinPhraseLength(alt) <= maxLenOfReplacement);
     186        var alts = GetAlternatives(nt).Where(alt => MinPhraseLength(alt) <= maxLenOfReplacement);
    187187        Debug.Assert(alts.Any());
    188188
  • branches/HeuristicLab.Problems.GrammaticalOptimization/Test/RunDemo.cs

    r11981 r12014  
    77using HeuristicLab.Algorithms.Bandits.BanditPolicies;
    88using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
     9using HeuristicLab.Algorithms.Bandits.Models;
    910using HeuristicLab.Algorithms.GrammaticalOptimization;
     11using Microsoft.VisualStudio.TestTools.UnitTesting;
     12using RandomPolicy = HeuristicLab.Algorithms.Bandits.BanditPolicies.RandomPolicy;
    1013
    1114namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
    12   class RunDemo {
    13     private static void RunGridTest() {
    14       int maxIterations = 200000; // for poly-10 with 50000 evaluations no successful try with hl yet
     15  [TestClass]
     16  public class RunDemo {
     17    [TestMethod]
     18    public void RunGridTest() {
     19      int maxIterations = 20000; // for poly-10 with 50000 evaluations no successful try with hl yet
    1520      //var globalRandom = new Random(31415);
    1621      var localRandSeed = new Random().Next();
     
    1924      var policyFactories = new Func<IBanditPolicy>[]
    2025        {
    21          //() => new RandomPolicy(),
    22          // () => new ActiveLearningPolicy(), 
    23          //() => new EpsGreedyPolicy(0.01, (aInfo)=> aInfo.MaxReward, "max"),
    24          //() => new EpsGreedyPolicy(0.05, (aInfo)=> aInfo.MaxReward, "max"),
    25          //() => new EpsGreedyPolicy(0.1, (aInfo)=> aInfo.MaxReward, "max"),
    26          //() => new EpsGreedyPolicy(0.2, (aInfo)=> aInfo.MaxReward, "max"),
    27          ////() => new GaussianThompsonSamplingPolicy(),
    28          //() => new GaussianThompsonSamplingPolicy(true),
    29          //() => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1)),
    30          //() => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1, 1)),
    31          ////() => new BernoulliThompsonSamplingPolicy(),
    32          //() => new GenericThompsonSamplingPolicy(new BernoulliModel(1, 1)),
    33          //() => new EpsGreedyPolicy(0.01),
    34          //() => new EpsGreedyPolicy(0.05),
    35          //() => new EpsGreedyPolicy(0.1),
    36          //() => new EpsGreedyPolicy(0.2),
    37          //() => new EpsGreedyPolicy(0.5),
    38          //() => new UCTPolicy(0.01),
    39          //() => new UCTPolicy(0.05),
    40          //() => new UCTPolicy(0.1),
    41          //() => new UCTPolicy(0.5),
    42          //() => new UCTPolicy(1),
    43          //() => new UCTPolicy(2),
    44          //() => new UCTPolicy( 5),
    45          //() => new UCTPolicy( 10),
    46          //() => new ModifiedUCTPolicy(0.01),
    47          //() => new ModifiedUCTPolicy(0.05),
    48          //() => new ModifiedUCTPolicy(0.1),
    49          //() => new ModifiedUCTPolicy(0.5),
    50          //() => new ModifiedUCTPolicy(1),
    51          //() => new ModifiedUCTPolicy(2),
    52          //() => new ModifiedUCTPolicy( 5),
    53          //() => new ModifiedUCTPolicy( 10),
    54          //() => new UCB1Policy(),
    55          //() => new UCB1TunedPolicy(),
    56          //() => new UCBNormalPolicy(),
    57          //() => new BoltzmannExplorationPolicy(1),
    58          //() => new BoltzmannExplorationPolicy(10),
    59          //() => new BoltzmannExplorationPolicy(20),
    60          //() => new BoltzmannExplorationPolicy(100),
    61          //() => new BoltzmannExplorationPolicy(200),
    62          //() => new BoltzmannExplorationPolicy(500),
    63          // () => new ChernoffIntervalEstimationPolicy( 0.01),
    64          // () => new ChernoffIntervalEstimationPolicy( 0.05),
    65          // () => new ChernoffIntervalEstimationPolicy( 0.1),
    66          // () => new ChernoffIntervalEstimationPolicy( 0.2),
    67          //() => new ThresholdAscentPolicy(5, 0.01),
    68          //() => new ThresholdAscentPolicy(5, 0.05),
    69          //() => new ThresholdAscentPolicy(5, 0.1),
    70          //() => new ThresholdAscentPolicy(5, 0.2),
    71          //() => new ThresholdAscentPolicy(10, 0.01),
    72          //() => new ThresholdAscentPolicy(10, 0.05),
    73          //() => new ThresholdAscentPolicy(10, 0.1),
    74          //() => new ThresholdAscentPolicy(10, 0.2),
    75          //() => new ThresholdAscentPolicy(50, 0.01),
    76          //() => new ThresholdAscentPolicy(50, 0.05),
    77          //() => new ThresholdAscentPolicy(50, 0.1),
    78          //() => new ThresholdAscentPolicy(50, 0.2),
    79          //() => new ThresholdAscentPolicy(100, 0.01),
     26         () => new RandomPolicy(),
     27          () => new ActiveLearningPolicy(), 
     28         () => new EpsGreedyPolicy(0.01, (aInfo)=> aInfo.MaxReward, "max"),
     29         () => new EpsGreedyPolicy(0.05, (aInfo)=> aInfo.MaxReward, "max"),
     30         () => new EpsGreedyPolicy(0.1, (aInfo)=> aInfo.MaxReward, "max"),
     31         () => new EpsGreedyPolicy(0.2, (aInfo)=> aInfo.MaxReward, "max"),
     32         //() => new GaussianThompsonSamplingPolicy(),
     33         () => new GaussianThompsonSamplingPolicy(true),
     34         () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1)),
     35         () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1, 1)),
     36         //() => new BernoulliThompsonSamplingPolicy(),
     37         () => new GenericThompsonSamplingPolicy(new BernoulliModel(1, 1)),
     38         () => new EpsGreedyPolicy(0.01),
     39         () => new EpsGreedyPolicy(0.05),
     40         () => new EpsGreedyPolicy(0.1),
     41         () => new EpsGreedyPolicy(0.2),
     42         () => new EpsGreedyPolicy(0.5),
     43         () => new UCTPolicy(0.01),
     44         () => new UCTPolicy(0.05),
     45         () => new UCTPolicy(0.1),
     46         () => new UCTPolicy(0.5),
     47         () => new UCTPolicy(1),
     48         () => new UCTPolicy(2),
     49         () => new UCTPolicy( 5),
     50         () => new UCTPolicy( 10),
     51         () => new ModifiedUCTPolicy(0.01),
     52         () => new ModifiedUCTPolicy(0.05),
     53         () => new ModifiedUCTPolicy(0.1),
     54         () => new ModifiedUCTPolicy(0.5),
     55         () => new ModifiedUCTPolicy(1),
     56         () => new ModifiedUCTPolicy(2),
     57         () => new ModifiedUCTPolicy( 5),
     58         () => new ModifiedUCTPolicy( 10),
     59         () => new UCB1Policy(),
     60         () => new UCB1TunedPolicy(),
     61         () => new UCBNormalPolicy(),
     62         () => new BoltzmannExplorationPolicy(1),
     63         () => new BoltzmannExplorationPolicy(10),
     64         () => new BoltzmannExplorationPolicy(20),
     65         () => new BoltzmannExplorationPolicy(100),
     66         () => new BoltzmannExplorationPolicy(200),
     67         () => new BoltzmannExplorationPolicy(500),
     68          () => new ChernoffIntervalEstimationPolicy( 0.01),
     69          () => new ChernoffIntervalEstimationPolicy( 0.05),
     70          () => new ChernoffIntervalEstimationPolicy( 0.1),
     71          () => new ChernoffIntervalEstimationPolicy( 0.2),
     72         () => new ThresholdAscentPolicy(5, 0.01),
     73         () => new ThresholdAscentPolicy(5, 0.05),
     74         () => new ThresholdAscentPolicy(5, 0.1),
     75         () => new ThresholdAscentPolicy(5, 0.2),
     76         () => new ThresholdAscentPolicy(10, 0.01),
     77         () => new ThresholdAscentPolicy(10, 0.05),
     78         () => new ThresholdAscentPolicy(10, 0.1),
     79         () => new ThresholdAscentPolicy(10, 0.2),
     80         () => new ThresholdAscentPolicy(50, 0.01),
     81         () => new ThresholdAscentPolicy(50, 0.05),
     82         () => new ThresholdAscentPolicy(50, 0.1),
     83         () => new ThresholdAscentPolicy(50, 0.2),
     84         () => new ThresholdAscentPolicy(100, 0.01),
    8085         () => new ThresholdAscentPolicy(100, 0.05),
    81          //() => new ThresholdAscentPolicy(100, 0.1),
    82          //() => new ThresholdAscentPolicy(100, 0.2),
    83          //() => new ThresholdAscentPolicy(500, 0.01),
    84          //() => new ThresholdAscentPolicy(500, 0.05),
    85          //() => new ThresholdAscentPolicy(500, 0.1),
    86          //() => new ThresholdAscentPolicy(500, 0.2),
    87          //() => new ThresholdAscentPolicy(5000, 0.01),
    88          //() => new ThresholdAscentPolicy(10000, 0.01),
     86         () => new ThresholdAscentPolicy(100, 0.1),
     87         () => new ThresholdAscentPolicy(100, 0.2),
     88         () => new ThresholdAscentPolicy(500, 0.01),
     89         () => new ThresholdAscentPolicy(500, 0.05),
     90         () => new ThresholdAscentPolicy(500, 0.1),
     91         () => new ThresholdAscentPolicy(500, 0.2),
     92         () => new ThresholdAscentPolicy(5000, 0.01),
     93         () => new ThresholdAscentPolicy(10000, 0.01),
    8994        };
    9095
     
    96101        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:false), 15),
    97102        //(rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:true), 15),
    98         (rand) => Tuple.Create((IProblem)new SymbolicRegressionPoly10Problem(), 23)
     103        //(rand) => Tuple.Create((IProblem)new SymbolicRegressionPoly10Problem(), 23)
     104        (rand) => Tuple.Create((IProblem)new SantaFeAntProblem(), 17)
    99105      };
    100106
    101107      foreach (var instanceFactory in instanceFactories) {
    102108        foreach (var useCanonical in new bool[] { true /*, false */ }) {
    103           foreach (var randomTries in new int[] { 1 /*, 1, 10 /*, /* 5, 100 /*, 500, 1000 */}) {
     109          foreach (var randomTries in new int[] { 0 /*, 1, 10 /*, /* 5, 100 /*, 500, 1000 */}) {
    104110            foreach (var policyFactory in policyFactories) {
    105111              var myRandomTries = randomTries;
  • branches/HeuristicLab.Problems.GrammaticalOptimization/Test/Test.csproj

    r11981 r12014  
    88    <AppDesignerFolder>Properties</AppDesignerFolder>
    99    <RootNamespace>HeuristicLab.Problems.GrammaticalOptimization.Test</RootNamespace>
    10     <AssemblyName>HeuristicLab.Problems.GrammaticalOptimization.Test</AssemblyName>
     10    <AssemblyName>Test</AssemblyName>
    1111    <TargetFrameworkVersion>v4.5</TargetFrameworkVersion>
    1212    <FileAlignment>512</FileAlignment>
     
    6868    <Compile Include="Properties\AssemblyInfo.cs" />
    6969    <Compile Include="TestSolvers.cs" />
     70    <Compile Include="TestTunedSettings.cs" />
    7071  </ItemGroup>
    7172  <ItemGroup>
  • branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs

    r11972 r12014  
    55using System.Threading.Tasks;
    66using HeuristicLab.Algorithms.Bandits;
     7using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
     8using HeuristicLab.Algorithms.GrammaticalOptimization;
     9using HeuristicLab.Problems.GrammaticalOptimization.SymbReg;
    710using Microsoft.VisualStudio.TestTools.UnitTesting;
    811
     
    6467      Assert.AreEqual("a*b+b*c", extender.CanonicalRepresentation("b*(c-a)"));
    6568      Assert.AreEqual("a*b+a*d+b*c+c*d", extender.CanonicalRepresentation("(b-d)*(c-a)"));
     69      Assert.AreEqual("|/(a+b)", extender.CanonicalRepresentation("c%c%(a+b)"));
    6670    }
    6771    [TestMethod]
    6872    public void TestDivisionExpansion() {
    6973      var extender = new ExpressionExtender();
    70       Assert.AreEqual("a*1/c+b*1/c", extender.CanonicalRepresentation("(b+a)%c"));
    71       Assert.AreEqual("a*1/c*1/d+b*1/c*1/d", extender.CanonicalRepresentation("(b+a)%(d*c)"));
    72       Assert.AreEqual("a*1/(c+d)+b*1/(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)"));
    73       Assert.AreEqual("a*b*1/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)"));
     74      Assert.AreEqual("a*|/c+b*|/c", extender.CanonicalRepresentation("(b+a)%c"));
     75      Assert.AreEqual("a*|/c*|/d+b*|/c*|/d", extender.CanonicalRepresentation("(b+a)%(d*c)"));
     76      Assert.AreEqual("a*|/(c+d)+b*|/(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)"));
     77      Assert.AreEqual("a*b*|/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)"));
    7478
    75       Assert.AreEqual("a*b*1/(a+b)*1/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
    76       Assert.AreEqual("a*b*1/(a*1/e+b*1/e)*1/(c+d)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
     79      Assert.AreEqual("a*b*|/(a+b)*|/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
     80      Assert.AreEqual("a*b*|/(c+d)*|/(a*|/e+b*|/e)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
    7781      // a*b*e%(c+d)%(a+b)
    7882    }
     
    8084    public void TestDivisionCancellation() {
    8185      var extender = new ExpressionExtender();
    82       Assert.AreEqual("1", extender.CanonicalRepresentation("a%a"));
     86      Assert.AreEqual("|", extender.CanonicalRepresentation("a%a"));
    8387      Assert.AreEqual("a", extender.CanonicalRepresentation("a*a%a"));
    84       Assert.AreEqual("1/a", extender.CanonicalRepresentation("(a%a)%a"));
    85       Assert.AreEqual("1/a", extender.CanonicalRepresentation("a%a%a"));
     88      Assert.AreEqual("|/a", extender.CanonicalRepresentation("(a%a)%a"));
     89      Assert.AreEqual("|/a", extender.CanonicalRepresentation("a%a%a"));
    8690      Assert.AreEqual("a", extender.CanonicalRepresentation("a%(a%a)"));
    87       Assert.AreEqual("1", extender.CanonicalRepresentation("(a+b)%(b+a)"));
    88       Assert.AreEqual("1/a+1/b", extender.CanonicalRepresentation("(a+b)%(a*b)"));
    89       Assert.AreEqual("a*1/(a*c*1/b+e*1/d*1/f)+b*1/(a*c*1/b+e*1/d*1/f)", extender.CanonicalRepresentation("(a+b)%(a%b*c+e%f%d)"));
     91      Assert.AreEqual("|", extender.CanonicalRepresentation("(a+b)%(b+a)"));
     92      Assert.AreEqual("|/a+|/b", extender.CanonicalRepresentation("(a+b)%(a*b)"));
     93      Assert.AreEqual("a*|/(a*c*|/b+e*|/d*|/f)+b*|/(a*c*|/b+e*|/d*|/f)", extender.CanonicalRepresentation("(a+b)%(a%b*c+e%f%d)"));
     94      Assert.AreEqual("|", extender.CanonicalRepresentation("(a%a%a+b%b%b)%(a%a*a%a%a+b%b*b%b%b)"));
     95      Assert.AreEqual("|", extender.CanonicalRepresentation("(a%(a%a)+b%(b%b))%(a+b)"));
     96    }
     97
     98    [TestMethod]
     99    public void TestRandomExpressions() {
     100      // samples sentences for the Tower dataset with the random MCTS policy
     101      // and evaluates the original and the extended expression
     102      // the results must be the same
     103
     104      var problem = new SymbolicRegressionProblem(new Random(), "Tower");
     105      var random = new Random(31415);
     106      var solver = new SequentialSearch(problem, 30, random, 0, new RandomPolicy(problem, true));
     107
     108      var extender = new ExpressionExtender();
     109
     110      solver.SolutionEvaluated += (sentence, quality) => {
     111        var canonicalSentence = extender.CanonicalRepresentation(sentence);
     112
     113        Assert.AreEqual(problem.SimpleEvaluate(sentence), problem.SimpleEvaluate(canonicalSentence), 1E-4, string.Format("{0} <> {1}", sentence, canonicalSentence));
     114      };
     115
     116      solver.Run(10000);
    90117    }
    91118  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSymbRegInstances.cs

    r11895 r12014  
    11using System;
    22using System.Linq;
     3using HeuristicLab.Algorithms.Bandits.BanditPolicies;
     4using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
    35using HeuristicLab.Algorithms.GeneticProgramming;
    46using HeuristicLab.Algorithms.GrammaticalOptimization;
     
    1214    [TestMethod]
    1315    public void TestGetDataDescriptors() {
     16      var problem = new SymbolicRegressionProblem(new Random(), "Tower");
     17      Assert.IsNotNull(problem);
     18    }
    1419
     20    [TestMethod]
     21    public void TestConstantOptimization() {
     22      double r2;
    1523      var problem = new SymbolicRegressionProblem(new Random(), "Tower");
    16       double r2;
    1724      Assert.AreEqual(problem.Evaluate("a*b"), problem.OptimizeConstantsAndEvaluate("a*b"));
    1825      Assert.AreEqual(problem.OptimizeConstantsAndEvaluate("a*b"), problem.Evaluate("a*b"));
     
    2330      Assert.IsTrue(problem.OptimizeConstantsAndEvaluate("0*a+1*b") >= problem.Evaluate("a+b"));
    2431    }
     32
     33    [TestMethod]
     34    public void TestSequentialSolverForTower() {
     35      var problem = new SymbolicRegressionProblem(new Random(), "Tower");
     36      var random = new Random(31415);
     37      var solver = new SequentialSearch(problem, 30, random, 0, new GenericGrammarPolicy(problem, new UCB1TunedPolicy(), true));
     38      solver.FoundNewBestSolution += (s, d) => {
     39        Console.WriteLine("{0:F3} {1}", d, s);
     40      };
     41      solver.Run(100);
     42    }
     43
    2544  }
    2645}
Note: See TracChangeset for help on using the changeset viewer.