source: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/Test/RunMctsExperiments.cs @ 13825

using System;
using System.Collections.Generic;
using System.Globalization;
using HeuristicLab.Algorithms.Bandits;
using HeuristicLab.Algorithms.Bandits.BanditPolicies;
using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
using HeuristicLab.Algorithms.Bandits.Models;
using HeuristicLab.Algorithms.GrammaticalOptimization;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using RandomPolicy = HeuristicLab.Algorithms.Bandits.BanditPolicies.RandomPolicy;

namespace HeuristicLab.Problems.GrammaticalOptimization.Test {

  [TestClass]
  public class RunMctsExperiments {
    private readonly static int randSeed = 31415;

    internal class Configuration {
      public ISymbolicExpressionTreeProblem Problem;
      public IBanditPolicy Policy;
      public int MaxSize;
      public int RandSeed;

      public override string ToString() {
        return string.Format("{0} {1} {2} {3}", RandSeed, Problem, Policy, MaxSize);
      }
    }

    private Func<IBanditPolicy>[] policyFactories = new Func<IBanditPolicy>[]
    {
          () => new RandomPolicy(), 
          () => new ActiveLearningPolicy(),  
         () => new GaussianThompsonSamplingPolicy(true), 
         () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1)), 
         () => new GenericThompsonSamplingPolicy(new GaussianModel(0.5, 10, 1, 1)), 
         () => new GenericThompsonSamplingPolicy(new BernoulliModel(1, 1)), 
         () => new EpsGreedyPolicy(0.01), 
         () => new EpsGreedyPolicy(0.05), 
         () => new EpsGreedyPolicy(0.1), 
         () => new EpsGreedyPolicy(0.2), 
         () => new EpsGreedyPolicy(0.5), 
         () => new UCTPolicy(0.01),
         () => new UCTPolicy(0.05),
         () => new UCTPolicy(0.1),
         () => new UCTPolicy(0.5),
         () => new UCTPolicy(1),
         () => new UCTPolicy(2),
         () => new UCTPolicy( 5),
         () => new UCTPolicy( 10),
         () => new ModifiedUCTPolicy(0.01),
         () => new ModifiedUCTPolicy(0.05),
         () => new ModifiedUCTPolicy(0.1),
         () => new ModifiedUCTPolicy(0.5),
         () => new ModifiedUCTPolicy(1),
         () => new ModifiedUCTPolicy(2),
         () => new ModifiedUCTPolicy( 5),
         () => new ModifiedUCTPolicy( 10),
         () => new UCB1Policy(), 
         () => new UCB1TunedPolicy(), 
         () => new UCBNormalPolicy(), 
         () => new BoltzmannExplorationPolicy(1),
         () => new BoltzmannExplorationPolicy(10),
         () => new BoltzmannExplorationPolicy(20),
         () => new BoltzmannExplorationPolicy(100),
         () => new BoltzmannExplorationPolicy(200),
         () => new BoltzmannExplorationPolicy(500),
          () => new ChernoffIntervalEstimationPolicy( 0.01), 
          () => new ChernoffIntervalEstimationPolicy( 0.05),
          () => new ChernoffIntervalEstimationPolicy( 0.1),
          () => new ChernoffIntervalEstimationPolicy( 0.2),
         () => new ThresholdAscentPolicy(5, 0.01), 
         () => new ThresholdAscentPolicy(5, 0.05),
         () => new ThresholdAscentPolicy(5, 0.1),
         () => new ThresholdAscentPolicy(5, 0.2),
         () => new ThresholdAscentPolicy(10, 0.01), 
         () => new ThresholdAscentPolicy(10, 0.05),
         () => new ThresholdAscentPolicy(10, 0.1),
         () => new ThresholdAscentPolicy(10, 0.2),
         () => new ThresholdAscentPolicy(50, 0.01), 
         () => new ThresholdAscentPolicy(50, 0.05),
         () => new ThresholdAscentPolicy(50, 0.1),
         () => new ThresholdAscentPolicy(50, 0.2),
         () => new ThresholdAscentPolicy(100, 0.01), 
         () => new ThresholdAscentPolicy(100, 0.05),
         () => new ThresholdAscentPolicy(100, 0.1),
         () => new ThresholdAscentPolicy(100, 0.2),
         () => new ThresholdAscentPolicy(500, 0.01), 
         () => new ThresholdAscentPolicy(500, 0.05),
         () => new ThresholdAscentPolicy(500, 0.1),
         () => new ThresholdAscentPolicy(500, 0.2),
         () => new ThresholdAscentPolicy(5000, 0.01), 
         () => new ThresholdAscentPolicy(10000, 0.01),  
    };

    #region artificial ant
    [TestMethod]
    [Timeout(1000 * 60 * 60 * 72)] // 72 hours
    public void RunMctsArtificialAntProblem() {
      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;

      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
      {
        (randSeed) => (ISymbolicExpressionTreeProblem) new SantaFeAntProblem(), 
      };

      var maxSizes = new int[] { 17 }; // size of sequential representation is 17
      int nReps = 30;
      int maxIterations = 100000; // randomsearch finds the optimum almost always for 100000 evals
      foreach (var instanceFactory in instanceFactories) {
        foreach (var policyFactory in policyFactories) {
          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
          }
        }
      }
    }

    #endregion

    #region symb-reg-poly-10
    [TestMethod]
    [Timeout(1000 * 60 * 60 * 120)] // 120 hours
    public void RunMctsPoly10Problem() {
      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;

      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
      {
        (randSeed) => (ISymbolicExpressionTreeProblem) new SymbolicRegressionPoly10Problem(), 
      };

      var maxSizes = new int[] { 23 }; // size of sequential representation is 23
      int nReps = 30;
      int maxIterations = 100000; // sequentialsearch should find the optimum within 100000 evals
      foreach (var instanceFactory in instanceFactories) {
        foreach (var policyFactory in policyFactories) {
          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
          }
        }
      }
    }
    #endregion

    #region hardpalindrome
    [TestMethod]
    [Timeout(1000 * 60 * 60 * 120)] // 120 hours
    public void RunMctsPalindromeProblem() {
      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;

      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
      {
        (randSeed) => (ISymbolicExpressionTreeProblem) new HardPalindromeProblem(), 
      };

      var maxSizes = new int[] { 10, 20, 30, 40, 50 }; 
      int nReps = 30;
      int maxIterations = 30000; 
      foreach (var instanceFactory in instanceFactories) {
        foreach (var policyFactory in policyFactories) {
          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
          }
        }
      }
    }
    #endregion

    #region royalpair
    [TestMethod]
    [Timeout(1000 * 60 * 60 * 120)] // 120 hours
    public void RunMctsRoyalPairProblem() {
      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;

      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
      {
        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalPairProblem(2), 
        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalPairProblem(4), 
        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalPairProblem(8), 
        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalPairProblem(16), 
      };

      var maxSizes = new int[] { /*10, 20, 30, 40,*/ 25, 50 };
      int nReps = 30;
      int maxIterations = 20000;
      foreach (var instanceFactory in instanceFactories) {
        foreach (var policyFactory in policyFactories) {
          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
          }
        }
      }
    }
    #endregion

    #region royalseq
    [TestMethod]
    [Timeout(1000 * 60 * 60 * 120)] // 120 hours
    public void RunMctsRoyalSequenceProblem() {
      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;

      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
      {
        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalSequenceProblem(new Random(randSeed), 3, 50), 
        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalSequenceProblem(new Random(randSeed), 5, 50), 
        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalSequenceProblem(new Random(randSeed), 10, 50), 
        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalSequenceProblem(new Random(randSeed), 20, 50), 
      };

      var maxSizes = new int[] { 10, 20, 30, 40, 50 };
      int nReps = 30;
      int maxIterations = 30000;
      foreach (var instanceFactory in instanceFactories) {
        foreach (var policyFactory in policyFactories) {
          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
          }
        }
      }
    }
    #endregion

    #region royaltree
    [TestMethod]
    [Timeout(1000 * 60 * 60 * 120)] // 120 hours
    public void RunMctsRoyalTreeProblem() {
      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;

      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
      {
        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalTreeProblem(3), 
        (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalTreeProblem(4), 
        // (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalTreeProblem(5), 
        // (randSeed) => (ISymbolicExpressionTreeProblem) new RoyalTreeProblem(6), 
      };

      var maxSizes = new int[] { 30, 100, 200 };
      int nReps = 30;
      int maxIterations = 30000;
      foreach (var instanceFactory in instanceFactories) {
        foreach (var policyFactory in policyFactories) {
          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
          }
        }
      }
    }
    #endregion

    #region findphrases
    [TestMethod]
    [Timeout(1000 * 60 * 60 * 120)] // 120 hours
    public void RunMctsFindPhrasesProblem() {
      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;

      var instanceFactories = new Func<int, ISymbolicExpressionTreeProblem>[]
      {
        (randSeed) => (ISymbolicExpressionTreeProblem) new FindPhrasesProblem(new Random(randSeed), 10, 10, 3, 10, 0, 1.0, 0.0, true),
      };

      var maxSizes = new int[] { 9, 12, 15, 21, 30 };
      int nReps = 30;
      int maxIterations = 30000;
      foreach (var instanceFactory in instanceFactories) {
        foreach (var policyFactory in policyFactories) {
          foreach (var conf in GenerateConfigurations(instanceFactory, policyFactory, nReps, maxSizes)) {
            RunMctsForProblem(conf.RandSeed, conf.Problem, conf.Policy, maxIterations, conf.MaxSize);
          }
        }
      }
    }
    #endregion
    
    #region helpers
    private IEnumerable<Configuration> GenerateConfigurations(
      Func<int, ISymbolicExpressionTreeProblem> problemFactory,
      Func<IBanditPolicy> policyFactory,
      int nReps,
      IEnumerable<int> maxSizes
      ) {
      var seedRand = new Random(randSeed);
      // the problem seed is the same for all configuratons 
      // this guarantees that we solve the _same_ problem each time
      // with different solvers and multiple repetitions
      var problemSeed = randSeed;
      for (int i = 0; i < nReps; i++) {
        // in each repetition use the same random seed for all solver configuratons
        // do nReps with different seeds for each configuration
        var solverSeed = seedRand.Next();
        foreach (var maxSize in maxSizes) {
          yield return new Configuration {
            MaxSize = maxSize,
            Problem = problemFactory(problemSeed),
            Policy = policyFactory(),
            RandSeed = solverSeed
          };
        }
      }
    }

    private static void RunMctsForProblem(
      int randSeed,
      IProblem problem,
      IBanditPolicy policy,
      int maxIters,
      int maxSize
      ) {
      var solver = new SequentialSearch(problem, maxSize, new Random(randSeed), 0,
        new GenericGrammarPolicy(problem, policy, false));
      var problemName = problem.Name;
      RunSolver(solver, problemName, policy.ToString(), maxIters, maxSize);
    }

    private static void RunSolver(ISolver solver, string problemName, string policyName, int maxIters, int maxSize) {
      int iterations = 0;
      var globalStatistics = new SentenceSetStatistics(1.0);
      var solverName = solver.GetType().Name;
      solver.SolutionEvaluated += (sentence, quality) => {
        iterations++;
        globalStatistics.AddSentence(sentence, quality);

        if (iterations % 1000 == 0) {
          Console.WriteLine("\"{0,25}\" {1} \"{2,25}\" \"{3}\" {4}", solverName, maxSize, problemName, policyName, globalStatistics);
        }
      };

      solver.Run(maxIters);
    }
    #endregion
  }
}