Changeset 11730 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization
- Timestamp:
- 01/02/15 16:08:21 (10 years ago)
- Location:
- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesContextSampler.cs
r11727 r11730 17 17 private readonly Random random; 18 18 private readonly int contextLen; 19 private readonly Func<Random, int, IPolicy> policyFactory; 19 20 20 public AlternativesContextSampler(IProblem problem, int maxLen) {21 public AlternativesContextSampler(IProblem problem, Random random, int maxLen, int contextLen, Func<Random, int, IPolicy> policyFactory) { 21 22 this.maxLen = maxLen; 22 23 this.problem = problem; 23 this.random = new Random(31415); 24 this.contextLen = 25; 24 this.random = random; 25 this.contextLen = contextLen; 26 this.policyFactory = policyFactory; 25 27 } 26 28 … … 29 31 InitPolicies(problem.Grammar); 30 32 for (int i = 0; i < maxIterations; i++) { 31 var sentence = SampleSentence(problem.Grammar) ;32 var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 33 var sentence = SampleSentence(problem.Grammar).ToString(); 34 var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 33 35 DistributeReward(quality); 34 36 … … 45 47 private Dictionary<string, IPolicy> ntPolicy; 46 48 private List<Tuple<string, int>> updateChain; 49 47 50 private void InitPolicies(IGrammar grammar) { 48 51 this.ntPolicy = new Dictionary<string, IPolicy>(); … … 50 53 } 51 54 52 private stringSampleSentence(IGrammar grammar) {55 private Sequence SampleSentence(IGrammar grammar) { 53 56 updateChain.Clear(); 54 return CompleteSentence(grammar, grammar.SentenceSymbol.ToString());57 return CompleteSentence(grammar, new Sequence(grammar.SentenceSymbol)); 55 58 } 56 59 57 public string CompleteSentence(IGrammar g, stringphrase) {60 public Sequence CompleteSentence(IGrammar g, Sequence phrase) { 58 61 if (phrase.Length > maxLen) throw new ArgumentException(); 59 62 if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException(); 60 bool done = phrase. All(g.IsTerminal); // terminal phrase means we are done63 bool done = phrase.IsTerminal; // terminal phrase means we are done 61 64 while (!done) { 62 int ntIdx; char nt; 63 Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx); 65 char nt = phrase.FirstNonTerminal; 64 66 65 67 int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2 … … 67 69 68 70 var alts = g.GetAlternatives(nt); 69 stringselectedAlt;71 Sequence selectedAlt; 70 72 // if the choice is restricted then one of the allowed alternatives is selected randomly 71 73 if (alts.Any(alt => g.MinPhraseLength(alt) > maxLenOfReplacement)) { … … 76 78 } else { 77 79 // all alts are allowed => select using bandit policy 80 var ntIdx = phrase.FirstNonTerminalIndex; 78 81 var startIdx = Math.Max(0, ntIdx - contextLen); 79 82 var endIdx = Math.Min(startIdx + contextLen, ntIdx); 80 var lft = phrase.Subs tring(startIdx, endIdx - startIdx + 1);83 var lft = phrase.Subsequence(startIdx, endIdx - startIdx + 1).ToString(); 81 84 lft = problem.Hash(lft); 82 85 if (!ntPolicy.ContainsKey(lft)) { 83 ntPolicy.Add(lft, new UCB1TunedPolicy(g.GetAlternatives(nt).Count()));86 ntPolicy.Add(lft, policyFactory(random, g.GetAlternatives(nt).Count())); 84 87 } 85 88 var selectedAltIdx = ntPolicy[lft].SelectAction(); … … 89 92 90 93 // replace nt with alt 91 phrase = phrase.Remove(ntIdx, 1); 92 phrase = phrase.Insert(ntIdx, selectedAlt); 94 phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt); 93 95 94 done = phrase. All(g.IsTerminal); // terminal phrase means we are done96 done = phrase.IsTerminal; // terminal phrase means we are done 95 97 } 96 98 return phrase; -
branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/AlternativesSampler.cs
r11727 r11730 27 27 InitPolicies(problem.Grammar); 28 28 for (int i = 0; i < maxIterations; i++) { 29 var sentence = SampleSentence(problem.Grammar) ;30 var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 29 var sentence = SampleSentence(problem.Grammar).ToString(); 30 var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 31 31 DistributeReward(quality); 32 32 … … 52 52 } 53 53 54 private stringSampleSentence(IGrammar grammar) {54 private Sequence SampleSentence(IGrammar grammar) { 55 55 updateChain.Clear(); 56 return CompleteSentence(grammar, grammar.SentenceSymbol.ToString());56 return CompleteSentence(grammar, new Sequence(grammar.SentenceSymbol)); 57 57 } 58 58 59 public string CompleteSentence(IGrammar g, stringphrase) {59 public Sequence CompleteSentence(IGrammar g, Sequence phrase) { 60 60 if (phrase.Length > maxLen) throw new ArgumentException(); 61 61 if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException(); 62 bool done = phrase. All(g.IsTerminal); // terminal phrase means we are done62 bool done = phrase.IsTerminal; // terminal phrase means we are done 63 63 while (!done) { 64 int ntIdx; char nt; 65 Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx); 64 char nt = phrase.FirstNonTerminal; 66 65 67 66 int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2 … … 69 68 70 69 var alts = g.GetAlternatives(nt); 71 stringselectedAlt;70 Sequence selectedAlt; 72 71 // if the choice is restricted then one of the allowed alternatives is selected randomly 73 72 if (alts.Any(alt => g.MinPhraseLength(alt) > maxLenOfReplacement)) { … … 84 83 85 84 // replace nt with alt 86 phrase = phrase.Remove(ntIdx, 1); 87 phrase = phrase.Insert(ntIdx, selectedAlt); 85 phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt); 88 86 89 done = phrase. All(g.IsTerminal); // terminal phrase means we are done87 done = phrase.IsTerminal; // terminal phrase means we are done 90 88 } 91 89 return phrase; -
branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs
r11727 r11730 11 11 12 12 private readonly int maxLen; 13 private readonly Queue< string> bfsQueue = new Queue<string>();13 private readonly Queue<Sequence> bfsQueue = new Queue<Sequence>(); 14 14 private readonly IProblem problem; 15 15 … … 21 21 public void Run(int maxIterations) { 22 22 double bestQuality = double.MinValue; 23 bfsQueue.Enqueue( problem.Grammar.SentenceSymbol.ToString());23 bfsQueue.Enqueue(new Sequence(problem.Grammar.SentenceSymbol)); 24 24 var sentences = GenerateLanguage(problem.Grammar); 25 25 var sentenceEnumerator = sentences.GetEnumerator(); 26 26 for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) { 27 var sentence = sentenceEnumerator.Current ;28 var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 27 var sentence = sentenceEnumerator.Current.ToString(); 28 var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 29 29 RaiseSolutionEvaluated(sentence, quality); 30 30 … … 37 37 38 38 // create sentences lazily 39 private IEnumerable< string> GenerateLanguage(IGrammar grammar) {39 private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) { 40 40 while (bfsQueue.Any()) { 41 41 var phrase = bfsQueue.Dequeue(); 42 42 43 char nt ;43 char nt = phrase.FirstNonTerminal; 44 44 int ntIdx; 45 Grammar.FindFirstNonTerminal(grammar, phrase, out nt, out ntIdx); 45 46 46 var alts = grammar.GetAlternatives(nt); 47 47 foreach (var alt in alts) { 48 var newPhrase = phrase.Remove(ntIdx, 1).Insert(ntIdx, alt); 49 if (newPhrase.All(grammar.IsTerminal) && newPhrase.Length <= maxLen) { 48 var newPhrase = new Sequence(phrase); 49 newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt); 50 if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) { 50 51 yield return newPhrase; 51 52 } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) { -
branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs
r11727 r11730 11 11 12 12 private readonly int maxLen; 13 private readonly Stack<string> stack = new Stack<string>(); 13 private readonly Stack<Sequence> stack = new Stack<Sequence>(); 14 private readonly IProblem problem; 14 15 15 public ExhaustiveDepthFirstSearch( int maxLen) {16 public ExhaustiveDepthFirstSearch(IProblem problem, int maxLen) { 16 17 this.maxLen = maxLen; 18 this.problem = problem; 17 19 } 18 20 19 public void Run( IProblem problem,int maxIterations) {21 public void Run(int maxIterations) { 20 22 double bestQuality = double.MinValue; 21 stack.Push( problem.Grammar.SentenceSymbol.ToString());23 stack.Push(new Sequence(problem.Grammar.SentenceSymbol)); 22 24 var sentences = GenerateLanguage(problem.Grammar); 23 25 var sentenceEnumerator = sentences.GetEnumerator(); 24 26 for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) { 25 var sentence = sentenceEnumerator.Current ;27 var sentence = sentenceEnumerator.Current.ToString(); 26 28 var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 27 29 RaiseSolutionEvaluated(sentence, quality); … … 35 37 36 38 // create sentences lazily 37 private IEnumerable< string> GenerateLanguage(IGrammar grammar) {39 private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) { 38 40 while (stack.Any()) { 39 41 var phrase = stack.Pop(); 40 42 41 char nt; 42 int ntIdx; 43 Grammar.FindFirstNonTerminal(grammar, phrase, out nt, out ntIdx); 43 char nt = phrase.FirstNonTerminal; 44 44 var alts = grammar.GetAlternatives(nt); 45 45 foreach (var alt in alts) { 46 var newPhrase = phrase.Remove(ntIdx, 1).Insert(ntIdx, alt); 47 if (newPhrase.All(grammar.IsTerminal) && newPhrase.Length <= maxLen) { 46 var newPhrase = new Sequence(phrase); 47 newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt); 48 49 if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) { 48 50 yield return newPhrase; 49 51 } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) { -
branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/MctsSampler.cs
r11727 r11730 10 10 public class MctsSampler { 11 11 private class TreeNode { 12 public string ident; 12 13 public int randomTries; 14 public int policyTries; 13 15 public IPolicy policy; 14 16 public TreeNode[] children; 15 17 public bool done = false; 16 18 19 public TreeNode(string id) { 20 this.ident = id; 21 } 22 17 23 public override string ToString() { 18 return string.Format("Node( random-tries: {0}, done: {1}, policy: {2})", randomTries, done, policy);24 return string.Format("Node({0} tries: {1}, done: {2}, policy: {3})", ident, randomTries + policyTries, done, policy); 19 25 } 20 26 } 27 21 28 22 29 public event Action<string, double> FoundNewBestSolution; … … 27 34 private readonly Random random; 28 35 private readonly int randomTries; 29 private readonly Func< int, IPolicy> policyFactory;36 private readonly Func<Random, int, IPolicy> policyFactory; 30 37 31 38 private List<Tuple<TreeNode, int>> updateChain; 32 39 private TreeNode rootNode; 33 40 41 public int treeDepth; 42 public int treeSize; 43 34 44 public MctsSampler(IProblem problem, int maxLen, Random random) : 35 this(problem, maxLen, random, 10, ( numActions) => new EpsGreedyPolicy(random, numActions, 0.1)) {45 this(problem, maxLen, random, 10, (rand, numActions) => new EpsGreedyPolicy(rand, numActions, 0.1)) { 36 46 37 47 } 38 48 39 public MctsSampler(IProblem problem, int maxLen, Random random, int randomTries, Func< int, IPolicy> policyFactory) {49 public MctsSampler(IProblem problem, int maxLen, Random random, int randomTries, Func<Random, int, IPolicy> policyFactory) { 40 50 this.maxLen = maxLen; 41 51 this.problem = problem; … … 47 57 public void Run(int maxIterations) { 48 58 double bestQuality = double.MinValue; 49 InitPolicies( );59 InitPolicies(problem.Grammar); 50 60 for (int i = 0; !rootNode.done && i < maxIterations; i++) { 51 var sentence = SampleSentence(problem.Grammar) ;61 var sentence = SampleSentence(problem.Grammar).ToString(); 52 62 var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 53 63 Debug.Assert(quality >= 0 && quality <= 1.0); … … 61 71 } 62 72 } 73 74 // clean up 75 InitPolicies(problem.Grammar); GC.Collect(); 63 76 } 64 77 65 private void InitPolicies() { 66 this.updateChain = new List<Tuple<TreeNode, int>>(); 67 rootNode = new TreeNode(); 78 public void PrintStats() { 79 var n = rootNode; 80 Console.WriteLine("depth: {0,5} size: {1,10} root tries {2,10}", treeDepth, treeSize, rootNode.policyTries + rootNode.randomTries); 81 while (n.policy != null) { 82 Console.WriteLine(); 83 Console.WriteLine("{0,5}->{1,-50}", n.ident, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.ident)))); 84 Console.WriteLine("{0,5} {1,-50}", string.Empty, string.Join(" ", n.children.Select(ch => string.Format("{0,4}", ch.randomTries + ch.policyTries)))); 85 //n.policy.PrintStats(); 86 n = n.children.OrderByDescending(c => c.policyTries).First(); 87 } 88 Console.ReadLine(); 68 89 } 69 90 70 private string SampleSentence(IGrammar grammar) { 71 updateChain.Clear(); 72 return CompleteSentence(grammar, grammar.SentenceSymbol.ToString()); 91 private void InitPolicies(IGrammar grammar) { 92 this.updateChain = new List<Tuple<TreeNode, int>>(); 93 94 rootNode = new TreeNode(grammar.SentenceSymbol.ToString()); 95 treeDepth = 0; 96 treeSize = 0; 73 97 } 74 98 75 public string CompleteSentence(IGrammar g, string phrase) { 99 private Sequence SampleSentence(IGrammar grammar) { 100 updateChain.Clear(); 101 var startPhrase = new Sequence(grammar.SentenceSymbol); 102 return CompleteSentence(grammar, startPhrase); 103 } 104 105 private Sequence CompleteSentence(IGrammar g, Sequence phrase) { 76 106 if (phrase.Length > maxLen) throw new ArgumentException(); 77 107 if (g.MinPhraseLength(phrase) > maxLen) throw new ArgumentException(); 78 108 TreeNode n = rootNode; 79 bool done = phrase. All(g.IsTerminal); // terminal phrase means we are done109 bool done = phrase.IsTerminal; 80 110 int selectedAltIdx = -1; 111 var curDepth = 0; 81 112 while (!done) { 82 int ntIdx; char nt; 83 Grammar.FindFirstNonTerminal(g, phrase, out nt, out ntIdx); 113 char nt = phrase.FirstNonTerminal; 84 114 85 115 int maxLenOfReplacement = maxLen - (phrase.Length - 1); // replacing aAb with maxLen 4 means we can only use alternatives with a minPhraseLen <= 2 … … 90 120 if (n.randomTries < randomTries) { 91 121 n.randomTries++; 122 123 treeDepth = Math.Max(treeDepth, curDepth); 124 92 125 return g.CompleteSentenceRandomly(random, phrase, maxLen); 93 126 } else if (n.randomTries == randomTries && n.policy == null) { 94 n.policy = policyFactory(alts.Count()); 95 n.children = alts.Select(_ => new TreeNode()).ToArray(); // create a new node for each alternative 127 n.policy = policyFactory(random, alts.Count()); 128 //n.children = alts.Select(alt => new TreeNode(alt.ToString())).ToArray(); // create a new node for each alternative 129 n.children = alts.Select(alt => new TreeNode(string.Empty)).ToArray(); // create a new node for each alternative 130 131 treeSize += n.children.Length; 96 132 } 97 133 n.policyTries++; 98 134 // => select using bandit policy 99 135 selectedAltIdx = n.policy.SelectAction(); 100 string selectedAlt = alts.ElementAt(selectedAltIdx); 136 Sequence selectedAlt = alts.ElementAt(selectedAltIdx); 137 101 138 // replace nt with alt 102 phrase = phrase.Remove(ntIdx, 1); 103 phrase = phrase.Insert(ntIdx, selectedAlt); 139 phrase.ReplaceAt(phrase.FirstNonTerminalIndex, 1, selectedAlt); 104 140 105 141 updateChain.Add(Tuple.Create(n, selectedAltIdx)); 106 142 107 done = phrase.All(g.IsTerminal); // terminal phrase means we are done 143 curDepth++; 144 145 done = phrase.IsTerminal; 108 146 if (!done) { 109 147 // prepare for next iteration … … 116 154 n.children[selectedAltIdx].done = true; 117 155 156 treeDepth = Math.Max(treeDepth, curDepth); 118 157 return phrase; 119 158 } … … 127 166 var policy = node.policy; 128 167 var action = e.Item2; 168 //policy.UpdateReward(action, reward / updateChain.Count); 129 169 policy.UpdateReward(action, reward); 130 170 -
branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs
r11690 r11730 13 13 private readonly int maxLen; 14 14 private readonly Random random; 15 private readonly IProblem problem; 15 16 16 public RandomSearch( int maxLen) {17 public RandomSearch(IProblem problem, Random random, int maxLen) { 17 18 this.maxLen = maxLen; 18 this.random = new Random(31415); 19 this.random = random; 20 this.problem = problem; 19 21 } 20 22 21 public void Run( IProblem problem,int maxIterations) {23 public void Run(int maxIterations) { 22 24 double bestQuality = double.MinValue; 23 25 for (int i = 0; i < maxIterations; i++) { 24 var sentence = CreateSentence(problem.Grammar) ;25 var quality = problem.Evaluate(sentence) ;26 var sentence = CreateSentence(problem.Grammar).ToString(); 27 var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 26 28 RaiseSolutionEvaluated(sentence, quality); 27 29 … … 33 35 } 34 36 35 private stringCreateSentence(IGrammar grammar) {36 var sentence = grammar.SentenceSymbol.ToString();37 private Sequence CreateSentence(IGrammar grammar) { 38 var sentence = new Sequence(grammar.SentenceSymbol); 37 39 return grammar.CompleteSentenceRandomly(random, sentence, maxLen); 38 40 }
Note: See TracChangeset
for help on using the changeset viewer.