source: branches/HeuristicLab.Problems.GrammaticalOptimization/Test/TestSolvers.cs @ 13780

using System;
using HeuristicLab.Algorithms.GeneticProgramming;
using HeuristicLab.Algorithms.GrammaticalOptimization;
using HeuristicLab.Problems.GrammaticalOptimization.SymbReg;
using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace HeuristicLab.Problems.GrammaticalOptimization.Test {
  [TestClass]
  public class TestSolvers {
    [TestMethod]
    public void TestExhaustiveBFS() {
      {
        // G(A): A -> l | r | m | ?(A)(A) | lA | rA | mA 
        var prob = new SantaFeAntProblem();
        var comb = 3;
        TestBFS(prob, 1, comb);

        comb = comb * 3 + 3;
        TestBFS(prob, 2, comb);

        comb = comb * 3 + 3;
        TestBFS(prob, 3, comb);

        comb = comb * 3 + 3;
        TestBFS(prob, 4, comb);

        comb = comb * 3 + 3;
        TestBFS(prob, 5, comb);

        comb = comb * 3 + 3;
        TestBFS(prob, 6, comb);

        comb = comb * 3 + 3 + (3 * 3); // additionally for ?(A)(A)
        TestBFS(prob, 7, comb);
      }
      {
        // G(E):
        // E -> V | V+E | V-E | V*E | V/E | (E)
        // V -> a .. j 
        /* grammar has been change ... unit test not yet adapted 
        var prob = new SymbolicRegressionPoly10Problem();
        var comb = 10;
        TestDFS(prob, 1, comb);
        TestDFS(prob, 2, comb);
        
        comb = comb + 10 * 4 * comb + comb;
        TestDFS(prob, 3, comb);
        TestDFS(prob, 4, comb);
        
        comb = comb + 10 * 4 * comb + 10; // ((E)) 
        TestDFS(prob, 5, comb);
        TestDFS(prob, 6, comb);
        
        comb = comb + 10 * 4 * comb + 10; // (((E)))  */
        // takes too long
        //TestDFS(prob, 7, comb);
        //TestDFS(prob, 8, comb);
      }
    }

    private void TestBFS(IProblem prob, int len, int numExpectedSols) {
      var solver = new ExhaustiveBreadthFirstSearch(prob, len);
      int numSols = 0;

      solver.SolutionEvaluated += (s, d) => { numSols++; };

      solver.Run(int.MaxValue);
      Assert.AreEqual(numExpectedSols, numSols);
    }

    [TestMethod]
    public void TestExhaustiveDFS() {
      {
        // G(A): A -> l | r | m | ?(A)(A) | lA | rA | mA 
        var prob = new SantaFeAntProblem();
        var comb = 3;
        TestDFS(prob, 1, comb);

        comb = comb * 3 + 3;
        TestDFS(prob, 2, comb);

        comb = comb * 3 + 3;
        TestDFS(prob, 3, comb);

        comb = comb * 3 + 3;
        TestDFS(prob, 4, comb);

        comb = comb * 3 + 3;
        TestDFS(prob, 5, comb);

        comb = comb * 3 + 3;
        TestDFS(prob, 6, comb);

        comb = comb * 3 + 3 + (3 * 3); // additionally for ?(A)(A)
        TestDFS(prob, 7, comb);
      }
      {
        // G(E):
        // E -> V | V+E | V-E | V*E | V/E | (E)
        // V -> a .. j 
        /* grammar has been change ... unit test not yet adapted 
        var prob = new SymbolicRegressionPoly10Problem();
        var comb = 10;
        TestDFS(prob, 1, comb);
        TestDFS(prob, 2, comb);

        comb = comb + 10 * 4 * comb + comb;
        TestDFS(prob, 3, comb);
        TestDFS(prob, 4, comb);

        comb = comb + 10 * 4 * comb + 10; // ((E)) 
        TestDFS(prob, 5, comb);
        TestDFS(prob, 6, comb);

        comb = comb + 10 * 4 * comb + 10; // (((E))) */
        // takes too long
        //TestDFS(prob, 7, comb);
        //TestDFS(prob, 8, comb);
      }
    }

    private void TestDFS(IProblem prob, int len, int numExpectedSols) {
      var solver = new ExhaustiveDepthFirstSearch(prob, len);
      int numSols = 0;

      solver.SolutionEvaluated += (s, d) => { numSols++; Console.WriteLine(s); };

      solver.Run(int.MaxValue);
      Assert.AreEqual(numExpectedSols, numSols);
    }

    [TestMethod]
    public void TestStandardGP() {
      var prob = new SymbolicRegressionPoly10Problem();
      var rand = new Random(31415);
      var sgp = new StandardGP(prob, rand);
      sgp.PopulationSize = 10000;
      sgp.MaxSolutionSize = 50;
      sgp.MaxSolutionDepth = 20;

      string bestSentence = string.Empty;
      double bestQuality = double.NegativeInfinity;

      sgp.FoundNewBestSolution += (sentence, quality) => {
        Assert.Inconclusive(string.Format("{0:N3} {1}", quality, sentence));
        bestSentence = sentence;
        bestQuality = quality;
      };

      sgp.Run(100000);

      Assert.AreEqual(1.0, bestQuality, 1E-6);
      Assert.AreEqual("", bestSentence);
    }

    [TestMethod]
    public void TestOSGP()
    {
      const int seed = 31415;
      var prob = new SymbolicRegressionProblem(new Random(seed), "Tower");
      var rand = new Random(31415);
      var osgp = new OffspringSelectionGP(prob, rand);
      osgp.PopulationSize = 500;
      osgp.MaxSolutionSize = 100;
      osgp.MaxSolutionDepth = 20;

      string bestSentence = string.Empty;
      double bestQuality = double.NegativeInfinity;

      osgp.FoundNewBestSolution += (sentence, quality) => {
        // Assert.Inconclusive(string.Format("{0:N3} {1}", quality, sentence));
        bestSentence = sentence;
        bestQuality = quality;
      };

      osgp.Run(100000);

      Assert.AreEqual(1.0, bestQuality, 1E-6);
      Assert.AreEqual("", bestSentence);
    }
  }
}