source: branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestCanonicalExpressions.cs @ 13918

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using HeuristicLab.Algorithms.Bandits;
using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
using HeuristicLab.Algorithms.GrammaticalOptimization;
using HeuristicLab.Problems.GrammaticalOptimization.SymbReg;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
  [TestClass]
  public class TestCanonicalExpressions {
    [TestMethod]
    public void TestFactorReordering() {
      var extender = new ExpressionExtender();
      Assert.AreEqual("a*b", extender.CanonicalRepresentation("b*a"));
      Assert.AreEqual("a*b*c", extender.CanonicalRepresentation("b*a*c"));
      Assert.AreEqual("a*b*E", extender.CanonicalRepresentation("b*a*E"));
    }

    [TestMethod]
    public void TestDuplicateTerms() {
      var extender = new ExpressionExtender();
      Assert.AreEqual("a", extender.CanonicalRepresentation("a+a"));
      Assert.AreEqual("a+b", extender.CanonicalRepresentation("b+a+b"));
      Assert.AreEqual("a+b", extender.CanonicalRepresentation("b+a-b")); // even though b-b canceles should keep this as we might find a non-zero factor for b
    }

    [TestMethod]
    public void TestSimpleTermReordering() {
      var extender = new ExpressionExtender();
      Assert.AreEqual("a+b", extender.CanonicalRepresentation("b+a"));
      Assert.AreEqual("a+b+c", extender.CanonicalRepresentation("b+a+c"));
      Assert.AreEqual("a+b+E", extender.CanonicalRepresentation("b+a+E"));
    }

    [TestMethod]
    public void TestCombinedTermReordering() {
      var extender = new ExpressionExtender();
      Assert.AreEqual("a+b+a*b+E", extender.CanonicalRepresentation("b*a+b+a+E"));
      Assert.AreEqual("a+b+b*c+E", extender.CanonicalRepresentation("c*b+b+a+E"));
      Assert.AreEqual("a+b+b*c+a*b*c+E", extender.CanonicalRepresentation("c*b+b*a*c+b+a+E"));
    }
    [TestMethod]
    public void TestNegativeAndReorderTerms() {
      var extender = new ExpressionExtender();
      // when using constant opt the negative sign is not necessary because a negative factor can be produced
      Assert.AreEqual("a+b", extender.CanonicalRepresentation("b-a"));
      Assert.AreEqual("a+b+c", extender.CanonicalRepresentation("b-a-c"));
      Assert.AreEqual("a+b+E", extender.CanonicalRepresentation("b-a-E"));
    }
    [TestMethod]
    public void TestFactorExpansion() {
      var extender = new ExpressionExtender();
      Assert.AreEqual("a+b", extender.CanonicalRepresentation("(b+a)"));
      Assert.AreEqual("a+b", extender.CanonicalRepresentation("(b)+(a)"));
      Assert.AreEqual("a+b", extender.CanonicalRepresentation("(b+(a))"));
      Assert.AreEqual("a+b", extender.CanonicalRepresentation("((b)+a)"));

      Assert.AreEqual("a+b+c", extender.CanonicalRepresentation("b-(a-c)"));
      Assert.AreEqual("a+b+c", extender.CanonicalRepresentation("b-(a+c)"));
      Assert.AreEqual("a+b+E", extender.CanonicalRepresentation("b-(a-E)"));

      // when using constant opt the negative sign is not necessary because a negative factor can be produced
      Assert.AreEqual("a*b+b*c", extender.CanonicalRepresentation("b*(c-a)"));
      Assert.AreEqual("a*b+a*d+b*c+c*d", extender.CanonicalRepresentation("(b-d)*(c-a)"));
      Assert.AreEqual("/(a+b)", extender.CanonicalRepresentation("c%c%(a+b)"));
    }
    [TestMethod]
    public void TestDivisionExpansion() {
      var extender = new ExpressionExtender();
      Assert.AreEqual("a*/c+b*/c", extender.CanonicalRepresentation("(b+a)%c"));
      Assert.AreEqual("a*/c*/d+b*/c*/d", extender.CanonicalRepresentation("(b+a)%(d*c)"));
      Assert.AreEqual("a*/(c+d)+b*/(c+d)", extender.CanonicalRepresentation("(b-a)%(d-c)"));
      Assert.AreEqual("a*b*/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)"));

      Assert.AreEqual("a*b*/(a+b)*/(c+d)", extender.CanonicalRepresentation("(b*a)%(d-c)%(a+b)"));
      Assert.AreEqual("a*b*/(c+d)*/(a*/e+b*/e)", extender.CanonicalRepresentation("((b*a)%(d-c))%((a+b)%e)"));
      // a*b*e%(c+d)%(a+b)
    }
    [TestMethod]
    public void TestDivisionCancellation() {
      var extender = new ExpressionExtender();
      Assert.AreEqual("1", extender.CanonicalRepresentation("a%a"));
      Assert.AreEqual("a", extender.CanonicalRepresentation("a*a%a"));
      Assert.AreEqual("/a", extender.CanonicalRepresentation("(a%a)%a"));
      Assert.AreEqual("/a", extender.CanonicalRepresentation("a%a%a"));
      Assert.AreEqual("a", extender.CanonicalRepresentation("a%(a%a)"));
      Assert.AreEqual("1", extender.CanonicalRepresentation("(a+b)%(b+a)"));
      Assert.AreEqual("/a+/b", extender.CanonicalRepresentation("(a+b)%(a*b)"));
      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)"));
      Assert.AreEqual("1", extender.CanonicalRepresentation("(a%a%a+b%b%b)%(a%a*a%a%a+b%b*b%b%b)"));
      Assert.AreEqual("1", extender.CanonicalRepresentation("(a%(a%a)+b%(b%b))%(a+b)"));
    }

    [TestMethod]
    public void TestRandomExpressions() {
      // samples sentences for the Tower dataset with the random MCTS policy 
      // and evaluates the original and the extended expression
      // the results must be the same

      var problem = new SymbolicRegressionProblem(new Random(), "Tower");
      var random = new Random(31415);
      var solver = new SequentialSearch(problem, 30, random, 0, new RandomPolicy(problem, true));

      var extender = new ExpressionExtender();

      solver.SolutionEvaluated += (sentence, quality) => {
        var canonicalSentence = extender.CanonicalRepresentation(sentence);

        Assert.AreEqual(problem.SimpleEvaluate(sentence), problem.SimpleEvaluate(canonicalSentence), 1E-4, string.Format("{0} <> {1}", sentence, canonicalSentence));
      };

      solver.Run(10000);
    }
  }
}