Free cookie consent management tool by TermsFeed Policy Generator

Changeset 11799


Ignore:
Timestamp:
01/19/15 20:09:12 (9 years ago)
Author:
gkronber
Message:

#2283: performance tuning and reactivated random-roll-out policy in sequential search

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

Legend:

Unmodified
Added
Removed
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/BoltzmannExplorationPolicy.cs

    r11747 r11799  
    4141                : Math.Exp(beta * valueFunction(aInfo));
    4242
    43       var bestAction = myActionInfos
    44         .Select((aInfo, idx) => new { aInfo, idx })
    45         .SampleProportional(random, w)
    46         .Select(p => p.idx)
    47         .First();
     43      var bestAction = Enumerable.Range(0, myActionInfos.Count()).SampleProportional(random, w);
    4844      Debug.Assert(bestAction >= 0);
    4945      return bestAction;
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/BanditPolicies/GenericThompsonSamplingPolicy.cs

    r11742 r11799  
    3939
    4040    public override string ToString() {
    41       return string.Format("GenericThompsonSamplingPolicy(\"{0}\")", model);
     41      return string.Format("GenericThompsonSamplingPolicy({0})", model);
    4242    }
    4343  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Bandits/GaussianMixtureBandit.cs

    r11731 r11799  
    4444      double x = 0;
    4545      do {
    46         var k = Enumerable.Range(0, componentProb[arm].Length).SampleProportional(random, componentProb[arm]).First();
     46        var k = Enumerable.Range(0, componentProb[arm].Length).SampleProportional(random, componentProb[arm]);
    4747
    4848        var z = Rand.RandNormal(random);
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/GenericGrammarPolicy.cs

    r11793 r11799  
    1414    private readonly IProblem problem;
    1515    private readonly IBanditPolicy banditPolicy;
    16     //private readonly HashSet<string> done;
    1716
    1817    public GenericGrammarPolicy(IProblem problem, IBanditPolicy banditPolicy, bool useCanonicalState = false) {
     
    2120      this.banditPolicy = banditPolicy;
    2221      this.stateInfo = new Dictionary<string, IBanditPolicyActionInfo>();
    23       //this.done = new HashSet<string>();
    2422    }
    2523
     
    2927        // fail because all follow states have already been visited => also disable the current state (if we can be sure that it has been fully explored)
    3028
    31         GetStateInfo(curState).Disable(0.0); // should the value be max of afterstate values instead of 0.0?
     29        GetStateInfo(curState).Disable(afterStates.Select(afterState => GetStateInfo(afterState).Value).Max());
    3230        selectedStateIdx = -1;
    3331        return false;
     
    5048
    5149    public virtual void UpdateReward(IEnumerable<string> stateTrajectory, double reward) {
    52       // the last state could be terminal
    53       var lastState = stateTrajectory.Last();
    54       if (problem.Grammar.IsTerminal(lastState)) {
    55         GetStateInfo(lastState).Disable(reward);
    56       }
     50      foreach (var state in stateTrajectory) {
     51        GetStateInfo(state).UpdateReward(reward);
    5752
    58       // update remaining states
    59       foreach (var state in stateTrajectory.Reverse().Skip(1)) {
    60         GetStateInfo(state).UpdateReward(reward);
     53        // only the last state can be terminal
     54        if (problem.Grammar.IsTerminal(state)) {
     55          GetStateInfo(state).Disable(reward);
     56        }
    6157      }
    6258    }
     
    6460    public virtual void Reset() {
    6561      stateInfo.Clear();
    66       //done.Clear();
    6762    }
    6863
     
    8176    protected string CanonicalState(string state) {
    8277      if (useCanonicalState) {
    83         if (problem.Grammar.IsTerminal(state))
    84           return problem.CanonicalRepresentation(state);
    85         else {
    86           // for non-terminal phrases make sure we don't disable canonical states that have not yet been fully explored
    87           // e.g. if for the ant problem we have the phrase lllS (and we are limited to 4 symbols) and lllr as well as llll are explored
    88           // then we are not allowed to disable rS (canonical of lllS) because rS might not have been fully explored
    89           // solution: we disable the state rS4
    90           return problem.CanonicalRepresentation(state) + state.Length;
    91         }
     78        return problem.CanonicalRepresentation(state);
    9279      } else
    9380        return state;
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/GrammarPolicies/TDPolicy.cs

    r11793 r11799  
    3535        return false;
    3636      }
    37       throw new NotImplementedException(); // TODO: remap indices of reduced action enumerable to indices of original enumerable
     37      throw new NotImplementedException(); // TODO: remap indices of reduced action enumerable to indices of original enumerable (see genericgrammarpolicy)
    3838
    3939      //return epsGreedy.TrySelect(random, curState, afterStates, out selectedState);
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.Bandits/Models/GaussianMixtureModel.cs

    r11747 r11799  
    2424
    2525    public double SampleExpectedReward(Random random) {
    26       var k = Enumerable.Range(0, numComponents).SampleProportional(random, componentProbs).First();
     26      var k = Enumerable.Range(0, numComponents).SampleProportional(random, componentProbs);
    2727      return alglib.invnormaldistribution(random.NextDouble()) * Math.Sqrt(componentVars[k]) + componentMeans[k];
    2828    }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialSearch.cs

    r11793 r11799  
    7070      Reset();
    7171
    72       for (int i = 0; bestQuality < 1.0 && !Done() && i < maxIterations; i++) {
     72      for (int i = 0; /*!bestQuality.IsAlmost(1.0) && */!Done() && i < maxIterations; i++) {
    7373        var phrase = SampleSentence(problem.Grammar);
    7474        // can fail on the last sentence
     
    9797        stateChain.Clear();
    9898        phrase = new Sequence(rootNode.phrase);
    99         //var startPhrase = new Sequence("a*b+c*d+e*f+E");
    10099      } while (!Done() && !TryCompleteSentence(grammar, ref phrase));
    101100      return phrase;
     
    110109
    111110      while (!phrase.IsTerminal) {
    112 
    113 
    114         //if (n.randomTries < randomTries) {
    115         //  n.randomTries++;
    116         //  curDepth = Math.Max(curDepth, curDepth);
    117         //  g.CompleteSentenceRandomly(random, phrase, maxLen);
    118         //  return true;
    119         //} else {
    120         // => select using bandit policy
    121         // failure means we simply restart
    122         GenerateFollowStates(n); // creates child nodes for node n
    123 
    124         int selectedChildIdx;
    125         if (!behaviourPolicy.TrySelect(random, n.phrase, n.children.Select(ch => ch.phrase), out selectedChildIdx)) {
    126           return false;
    127         }
    128         phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, n.children[selectedChildIdx].alternative);
    129 
    130         // prepare for next iteration
    131         n = n.children[selectedChildIdx];
    132         stateChain.Add(n.phrase);
    133         curDepth++;
    134         //}
     111        if (n.randomTries < randomTries) {
     112          n.randomTries++;
     113          maxSearchDepth = Math.Max(maxSearchDepth, curDepth);
     114          g.CompleteSentenceRandomly(random, phrase, maxLen);
     115          return true;
     116        } else {
     117          // => select using bandit policy
     118          // failure means we simply restart
     119          GenerateFollowStates(n); // creates child nodes for node n
     120
     121          int selectedChildIdx;
     122          if (!behaviourPolicy.TrySelect(random, n.phrase, n.children.Select(ch => ch.phrase), out selectedChildIdx)) {
     123            return false;
     124          }
     125          phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, n.children[selectedChildIdx].alternative);
     126
     127          // prepare for next iteration
     128          n = n.children[selectedChildIdx];
     129          stateChain.Add(n.phrase);
     130          curDepth++;
     131        }
    135132      } // while
    136133
     
    157154        int idx = 0;
    158155        foreach (var alt in alts) {
    159           var newPhrase = new Sequence(phrase); // clone
    160           newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
    161           children[idx++] = new TreeNode(newPhrase.ToString(), alt);
     156          // var newPhrase = new Sequence(phrase); // clone
     157          // newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
     158          // children[idx++] = new TreeNode(newPhrase.ToString(), alt);
     159
     160          // since we are not using a sequence later on we might directly transform the current sequence to a string and replace there
     161          var phraseStr = phrase.ToString();
     162          var sb = new StringBuilder(phraseStr);
     163          sb.Remove(phrase.FirstNonTerminalIndex, 1).Insert(phrase.FirstNonTerminalIndex, alt.ToString());
     164          children[idx++] = new TreeNode(sb.ToString(), alt);
    162165        }
    163166        n.children = children;
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/Extensions.cs

    r11742 r11799  
    1212
    1313    public static T SelectRandom<T>(this IEnumerable<T> xs, Random rand) {
    14       var xsArr = xs.ToArray();
    15       return xsArr[rand.Next(xsArr.Length)];
     14      var n = xs.Count();
     15      return xs.ElementAt(rand.Next(n));
    1616    }
    1717
    18     public static IEnumerable<T> SampleProportional<T>(this IEnumerable<T> source, Random random, IEnumerable<double> weights) {
    19       var sourceArray = source.ToArray();
    20       var valueArray = weights.ToArray();
    21       double total = valueArray.Sum();
     18    public static T SampleProportional<T>(this IEnumerable<T> elements, Random random, IEnumerable<double> weights) {
     19      double total = weights.Sum();
    2220
    23       while (true) {
    24         int index = 0;
    25         double ball = valueArray[index], sum = random.NextDouble() * total;
    26         while (ball < sum)
    27           ball += valueArray[++index];
    28         yield return sourceArray[index];
     21      var elemEnumerator = elements.GetEnumerator();
     22      elemEnumerator.MoveNext();
     23      var weightEnumerator = weights.GetEnumerator();
     24      weightEnumerator.MoveNext();
     25
     26      var r = random.NextDouble() * total;
     27      var agg = weightEnumerator.Current;
     28
     29      while (agg < r) {
     30        weightEnumerator.MoveNext();
     31        elemEnumerator.MoveNext();
     32        agg += weightEnumerator.Current;
    2933      }
     34      return elemEnumerator.Current;
    3035    }
    3136
     
    4449        var y = yEnum.Current;
    4550        s += (x - meanX) * (y - meanY);
    46         ssX += Math.Pow(x - meanX, 2);
    47         ssY += Math.Pow(y - meanY, 2);
     51        ssX += (x - meanX) * (x - meanX);
     52        ssY += (y - meanY) * (y - meanY);
    4853      }
    4954      if (xEnum.MoveNext() | yEnum.MoveNext()) throw new ArgumentException("lengths are not equal");
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/HeuristicLab.Common.csproj

    r11745 r11799  
    4343    <Compile Include="ConsoleEx.cs" />
    4444    <Compile Include="Extensions.cs" />
     45    <Compile Include="MostRecentlyUsedCache.cs" />
    4546    <Compile Include="Properties\AssemblyInfo.cs" />
    4647    <Compile Include="Rand.cs" />
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/FindPhrasesProblem.cs

    r11793 r11799  
    123123    }
    124124
     125    // TODO: cache canonical phrases in most-recently used dictionary for increased performance (see symbolicregressionpoly10problem)
    125126    private string CanonicalPhrase(string phrase) {
    126127      if (phrasesAsSets) return string.Join("", phrase.OrderBy(ch => (byte)ch));
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Grammar.cs

    r11793 r11799  
    203203    public bool IsTerminal(string phrase) {
    204204      // reverse because for our grammars and left-canonical derivation it is more likely that NTs occur near the end of the sequence
    205       return phrase.Reverse().All(IsTerminal);
     205      for (int i = phrase.Length - 1; i >= 0; i--) {
     206        if (!IsTerminal(phrase[i])) return false;
     207      }
     208      return true;
    206209    }
    207210
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalPhraseSequenceProblem.cs

    r11770 r11799  
    107107    }
    108108
     109    // TODO: cache canonical phrases in most-recently used dictionary for increased performance (see symbolicregressionpoly10problem)
    109110    private string CanonicalPhrase(string phrase) {
    110111      if (phrasesAsSets) return string.Join("", phrase.OrderBy(ch => (byte)ch));
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/RoyalSequenceProblem.cs

    r11792 r11799  
    3131      this.correctReward = correctReward;
    3232      this.incorrectReward = incorrectReward;
    33       var sentenceSymbol = 'S';
     33      const char sentenceSymbol = 'S';
    3434      var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray();
    35       var nonTerminalSymbols = new char[] { 'S' };
    36       var rules = terminalSymbols.Select(t => Tuple.Create('S', t.ToString()))
    37         .Concat(terminalSymbols.Select(t => Tuple.Create('S', t + "S")));
     35      var nonTerminalSymbols = new char[] { sentenceSymbol };
     36      var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString()))
     37        .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString())));
    3838      //var rules = terminalSymbols.Select(t => Tuple.Create('S', t + "S"))
    3939      //  .Concat(terminalSymbols.Select(t => Tuple.Create('S', t.ToString())));
     
    6464      // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
    6565      Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
    66       // as long as only correct symbols are found we increase the reward by +1
    67       // on the first incorrect symbol we return
    6866      var reward = 0.0;
    6967      for (int i = 0; i < Math.Min(sentence.Length, sequenceLen); i++) {
     
    7169          reward += correctReward;
    7270        } else {
    73           // alternatively reduce reward by number of remaining symbols
     71          // reduce reward by number of remaining symbols
    7472          return Math.Max(0.0, reward + incorrectReward * (sentence.Length - i));
    75           // stop on first incorrect symbol and return reward
    76           //return reward;
    7773        }
    7874      }
     
    8076    }
    8177
     78    // in each position there could be multiple correct and incorrect symbols
    8279    public string CanonicalRepresentation(string terminalPhrase) {
    83       throw new NotImplementedException();
    84       return terminalPhrase;
     80      var sb = new StringBuilder();
     81      for (int i = 0; i < terminalPhrase.Length; i++) {
     82        if (optimalSymbolsForPos[i].Contains(terminalPhrase[i])) {
     83          sb.Append(optimalSymbolsForPos[i].First()); // all symbols in the set are equivalent
     84        } else {
     85          sb.Append(terminalPhrase[i]);
     86        }
     87      }
     88      return sb.ToString();
    8589    }
    8690  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SantaFeAntProblem.cs

    r11793 r11799  
    22using System.Collections.Generic;
    33using System.Linq;
     4using System.Runtime.InteropServices;
    45using System.Runtime.Remoting.Messaging;
    56using System.Text;
     7using System.Text.RegularExpressions;
    68
    79namespace HeuristicLab.Problems.GrammaticalOptimization {
     
    101103
    102104    public string CanonicalRepresentation(string terminalPhrase) {
     105      var sb = new StringBuilder(terminalPhrase);
     106      string canonicalPhrase = terminalPhrase;
    103107      string oldPhrase;
    104108      do {
    105         oldPhrase = terminalPhrase;
    106         terminalPhrase = terminalPhrase.Replace("ll", "rr").Replace("rl", "lr").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l");
    107       } while (terminalPhrase != oldPhrase);
    108       return terminalPhrase;
     109        oldPhrase = canonicalPhrase;
     110        sb.Replace("ll", "rr").Replace("rl", "lr").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l");
     111        canonicalPhrase = sb.ToString();
     112      } while (canonicalPhrase != oldPhrase);
     113      sb.Append(terminalPhrase.Length - canonicalPhrase.Length);
     114      return sb.ToString();
    109115    }
    110116  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SymbolicRegressionPoly10Problem.cs

    r11792 r11799  
    11using System;
     2using System.Collections.Concurrent;
    23using System.Collections.Generic;
     4using System.Collections.Specialized;
    35using System.Linq;
    46using System.Net;
     
    7274
    7375
     76    // most-recently-used caching (with limited capacity) for canonical representations
     77    MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
    7478    // right now only + and * is supported
    75     //private Dictionary<string, string> cache = new Dictionary<string, string>();
    7679    public string CanonicalRepresentation(string phrase) {
    77       string res;
    78       //if (!cache.TryGetValue(phrase, out res)) {
    79       var terms = phrase.Split('+').Select(t => t.Replace("*", ""));
    80       var terminalTerms = terms.Where(t => t.All(ch => grammar.IsTerminal(ch)));
    81       var nonTerminalTerms = terms.Where(t => t.Any(ch => grammar.IsNonTerminal(ch)));
     80      string canonicalPhrase;
     81      if (!canonicalPhraseCache.TryGetValue(phrase, out canonicalPhrase)) {
     82        var terms = phrase.Split('+');
     83        var canonicalTerms = new SortedSet<string>();
     84        // only the last term might contain a NT-symbol. make sure this term is added at the end
     85        for (int i = 0; i < terms.Length - 1; i++) {
     86          canonicalTerms.Add(CanonicalTerm(terms[i]));
     87        }
    8288
    83       res = string.Join("+", terminalTerms.Select(term => CanonicalTerm(term)).OrderBy(term => term).Concat(nonTerminalTerms.Select(term => CanonicalTerm(term))));
    84       //cache[phrase] = res;
    85       //}
    86       return res;
     89        var sb = new StringBuilder(phrase.Length);
     90        foreach (var t in canonicalTerms)
     91          sb.Append(t).Append('+');
     92
     93        sb.Append(CanonicalTerm(terms[terms.Length - 1]));
     94        sb.Append(phrase.Length - sb.Length);
     95        canonicalPhrase = sb.ToString();
     96        canonicalPhraseCache.Add(phrase, canonicalPhrase);
     97      }
     98      return canonicalPhrase;
    8799    }
    88100
     101    // cache the canonical form of terms for performance reasons
     102    private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
    89103    private string CanonicalTerm(string term) {
    90       return string.Join("", term.OrderByDescending(ch => (byte)ch)); // we want to have the up-case characters last
     104      string canonicalTerm;
     105      if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm)) {
     106        // add
     107        var chars = term.ToCharArray();
     108        Array.Sort(chars);
     109        var sb = new StringBuilder(chars.Length);
     110        // we want to have the up-case characters last
     111        for (int i = chars.Length - 1; i >= 0; i--) {
     112          if (chars[i] != '*') sb.Append(chars[i]);
     113        }
     114        canonicalTerm = sb.ToString();
     115        canonicalTermDictionary.Add(term, canonicalTerm);
     116      }
     117      return canonicalTerm;
    91118    }
    92119  }
  • branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs

    r11795 r11799  
    2424      CultureInfo.DefaultThreadCurrentCulture = CultureInfo.InvariantCulture;
    2525
    26       //RunDemo();
    27       RunGridTest();
     26      RunDemo();
     27      //RunGridTest();
    2828    }
    2929
     
    3232      //var globalRandom = new Random(31415);
    3333      var localRandSeed = 31415;
    34       var reps = 5;
    35 
    36       var policies = new Func<IBanditPolicy>[]
     34      var reps = 10;
     35
     36      var policyFactories = new Func<IBanditPolicy>[]
    3737        {
    3838         () => new RandomPolicy(),
     
    7272         () => new ChernoffIntervalEstimationPolicy( 0.1),
    7373         () => new ChernoffIntervalEstimationPolicy( 0.2),
     74         () => new ThresholdAscentPolicy(5, 0.01),
     75         () => new ThresholdAscentPolicy(5, 0.05),
     76         () => new ThresholdAscentPolicy(5, 0.1),
     77         () => new ThresholdAscentPolicy(5, 0.2),
    7478         () => new ThresholdAscentPolicy(10, 0.01),
    7579         () => new ThresholdAscentPolicy(10, 0.05),
    7680         () => new ThresholdAscentPolicy(10, 0.1),
    7781         () => new ThresholdAscentPolicy(10, 0.2),
     82         () => new ThresholdAscentPolicy(50, 0.01),
     83         () => new ThresholdAscentPolicy(50, 0.05),
     84         () => new ThresholdAscentPolicy(50, 0.1),
     85         () => new ThresholdAscentPolicy(50, 0.2),
    7886         () => new ThresholdAscentPolicy(100, 0.01),
    7987         () => new ThresholdAscentPolicy(100, 0.05),
    8088         () => new ThresholdAscentPolicy(100, 0.1),
    8189         () => new ThresholdAscentPolicy(100, 0.2),
    82          () => new ThresholdAscentPolicy(100, 0.01),
    83          () => new ThresholdAscentPolicy(100, 0.05),
    84          () => new ThresholdAscentPolicy(100, 0.1),
    85          () => new ThresholdAscentPolicy(100, 0.2),
    86          //() => new ThresholdAscentPolicy(1000, 0.01),
    87          //() => new ThresholdAscentPolicy(1000, 0.05),
    88          //() => new ThresholdAscentPolicy(1000, 0.1),
    89          //() => new ThresholdAscentPolicy(1000, 0.2),
     90         () => new ThresholdAscentPolicy(500, 0.01),
     91         () => new ThresholdAscentPolicy(500, 0.05),
     92         () => new ThresholdAscentPolicy(500, 0.1),
     93         () => new ThresholdAscentPolicy(500, 0.2),
    9094         //() => new ThresholdAscentPolicy(5000, 0.01),
    9195         //() => new ThresholdAscentPolicy(10000, 0.01),
    9296        };
    9397
    94       foreach (var problem in new Tuple<IProblem, int>[]
    95         {
    96           Tuple.Create((IProblem)new SantaFeAntProblem(), 17),
    97           Tuple.Create((IProblem)new SymbolicRegressionPoly10Problem(), 23),
    98         })
    99         foreach (var useCanonical in new bool[] { true, false })
    100           foreach (var randomTries in new int[] { 0, /*1, 10, /* 5, 100 /*, 500, 1000 */}) {
    101             foreach (var policy in policies) {
     98      var instanceFactories = new Func<Random, Tuple<IProblem, int>>[]
     99      {
     100        (rand) => Tuple.Create((IProblem)new SantaFeAntProblem(), 17),
     101        (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:false ), 15),
     102        (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:0, correctReward:1, decoyReward:0, phrasesAsSets:true ), 15),
     103        (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:false), 15),
     104        (rand) => Tuple.Create((IProblem)new FindPhrasesProblem(rand, 10, numPhrases:5, phraseLen:3, numOptimalPhrases:5, numDecoyPhrases:200, correctReward:1, decoyReward:0.5, phrasesAsSets:true), 15),
     105        (rand) => Tuple.Create((IProblem)new SymbolicRegressionPoly10Problem(), 23)
     106      };
     107
     108      foreach (var instanceFactory in instanceFactories) {
     109        foreach (var useCanonical in new bool[] { true, false }) {
     110          foreach (var randomTries in new int[] { 0, 1, 10, /* 5, 100 /*, 500, 1000 */}) {
     111            foreach (var policyFactory in policyFactories) {
    102112              var myRandomTries = randomTries;
    103113              var localRand = new Random(localRandSeed);
    104114              var options = new ParallelOptions();
    105               options.MaxDegreeOfParallelism = 1;
     115              options.MaxDegreeOfParallelism = 4;
    106116              Parallel.For(0, reps, options, (i) => {
    107                 //var t = Task.Run(() => {
    108117                Random myLocalRand;
    109118                lock (localRand)
    110119                  myLocalRand = new Random(localRand.Next());
    111 
    112                 //for (int i = 0; i < reps; i++) {
    113120
    114121                int iterations = 0;
     
    121128                //var problem = new RoyalPairProblem();
    122129                //var problem = new EvenParityProblem();
    123                 // var alg = new MctsSampler(problem.Item1, problem.Item2, myLocalRand, myRandomTries, policy()); // TODO: Make sure we generate the same random numbers for each
    124                 var alg = new SequentialSearch(problem.Item1, problem.Item2, myLocalRand, myRandomTries, new GenericGrammarPolicy(problem.Item1, policy(), useCanonical));
     130                // var alg = new MctsSampler(problem.Item1, problem.Item2, myLocalRand, myRandomTries, policy());
     131                var instance = instanceFactory(myLocalRand);
     132                var problem = instance.Item1;
     133                var maxLen = instance.Item2;
     134                var alg = new SequentialSearch(problem, maxLen, myLocalRand, myRandomTries,
     135                  new GenericGrammarPolicy(problem, policyFactory(), useCanonical));
    125136                //var alg = new ExhaustiveBreadthFirstSearch(problem, 25);
    126137                //var alg = new AlternativesContextSampler(problem, 25);
     
    129140                  iterations++;
    130141                  globalStatistics.AddSentence(sentence, quality);
    131                   if (iterations % 1000 == 0) {
    132                     Console.WriteLine("{0,5} {1,25} {2} {3}", myRandomTries, policy(), useCanonical, globalStatistics);
     142                  if (iterations % 10000 == 0) {
     143                    Console.WriteLine("{0,3} {1,5} \"{2,25}\" {3} {4}", i, myRandomTries, policyFactory(), useCanonical, globalStatistics);
    133144                  }
    134145                };
    135146                alg.FoundNewBestSolution += (sentence, quality) => {
    136                   Console.WriteLine("{0,5} {1,25} {2} {3}", myRandomTries, policy(), useCanonical, globalStatistics);
     147                  //Console.WriteLine("{0,5} {1,25} {2} {3}",
     148                  //  myRandomTries, policyFactory(), useCanonical,
     149                  //  globalStatistics);
    137150                };
    138151
    139 
    140152                alg.Run(maxIterations);
    141 
    142                 //Console.WriteLine("{0,5} {1} {2}", randomTries, policyFactory(1), globalStatistics);
    143                 //}
    144                 //});
    145                 //tasks.Add(t);
    146153              });
    147154            }
    148155          }
    149       //Task.WaitAll(tasks.ToArray());
     156        }
     157      }
    150158    }
    151159
    152160    private static void RunDemo() {
    153       // TODO: clone problem for parallel grid test
    154161      // TODO: move problem instances into a separate folder
    155       // TODO: improve performance of SequentialSearch (memory allocations related to sequences)
    156162      // TODO: implement bridge to HL-GP
    157163      // TODO: unify MCTS, TD and ContextMCTS Solvers (stateInfos)
     
    183189      var random = new Random();
    184190
     191
     192      var problem = new RoyalSequenceProblem(random, 10, 30, 2, 1, 0);
    185193      //var phraseLen = 3;
    186194      //var numPhrases = 5;
    187195      //var problem = new RoyalPhraseSequenceProblem(random, 15, numPhrases, phraseLen: phraseLen, numCorrectPhrases: 1, correctReward: 1, incorrectReward: 0.0, phrasesAsSets: true);
    188196
    189       // var phraseLen = 2;
     197      // var phraseLen = 3;
    190198      // var numPhrases = 5;
    191       // var problem = new FindPhrasesProblem(random, 15, numPhrases, phraseLen, numOptimalPhrases: numPhrases, numDecoyPhrases: 0, correctReward: 1.0, decoyReward: 0.0, phrasesAsSets: true);
     199      // var problem = new FindPhrasesProblem(random, 10, numPhrases, phraseLen, numOptimalPhrases: numPhrases, numDecoyPhrases: 200, correctReward: 1.0, decoyReward: 0.5, phrasesAsSets: true);
    192200
    193201      // good results for symb-reg
     
    197205      // - GenericThompsonSamplingPolicy("")
    198206      // - UCTPolicy(0.10) (5 of 5 runs, 35000 iters avg.)
    199      
     207
    200208      // good results for artificial ant:
    201209      // prev results:
     
    203211      // - GaussianModelWithUnknownVariance (and Q= 0.99-quantil) also works well for Ant
    204212      // 2015 01 19: grid test with canonical states (non-canonical slightly worse)
    205       // - Threshold Ascent (best 100, 0.01; all variants relatively good
    206 
    207       //var problem = new SymbolicRegressionPoly10Problem();   
    208      
    209       var problem = new SantaFeAntProblem();
     213      // - Threshold Ascent (best 100, 0.01; all variants relatively good)
     214      // - Policies where the variance has a large weight compared to the mean? (Gaussian(compatible), Gaussian with fixed variance, UCT with large c, alle TA)
     215
     216      //var problem = new SymbolicRegressionPoly10Problem();
     217
     218      //var problem = new SantaFeAntProblem();
    210219      //var problem = new SymbolicRegressionProblem("Tower");
    211220      //var problem = new PalindromeProblem();
     
    216225      //var alg = new MctsSampler(problem, 23, random, 0, new BoltzmannExplorationPolicy(100));
    217226      //var alg = new MctsSampler(problem, 23, random, 0, new EpsGreedyPolicy(0.1));
    218       var alg = new SequentialSearch(problem, 17, random, 0,
    219         new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericGrammarPolicy(problem, new BoltzmannExplorationPolicy(10), true));
     227      var alg = new SequentialSearch(problem, 30, random, 0,
     228        new HeuristicLab.Algorithms.Bandits.GrammarPolicies.GenericGrammarPolicy(problem, new EpsGreedyPolicy(0.1), true));
    220229      //var alg = new MctsQLearningSampler(problem, sentenceLen, random, 0, null);
    221230      //var alg = new MctsQLearningSampler(problem, 30, random, 0, new EpsGreedyPolicy(0.2));
     
    236245        iterations++;
    237246        globalStatistics.AddSentence(sentence, quality);
    238         if (iterations % 100 == 0) {
     247        if (iterations % 1000 == 0) {
    239248          if (iterations % 1000 == 0) Console.Clear();
    240249          Console.SetCursorPosition(0, 0);
Note: See TracChangeset for help on using the changeset viewer.