Changeset 11865 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization
- Timestamp:
- 02/02/15 20:41:11 (10 years ago)
- Location:
- branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization
- Files:
-
- 1 deleted
- 6 edited
- 1 copied
Legend:
- Unmodified
- Added
- Removed
-
branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj
r11857 r11865 78 78 <Compile Include="Interfaces\IGrammar.cs" /> 79 79 <Compile Include="Interfaces\IProblem.cs" /> 80 <Compile Include="Interfaces\ISymbolicExpressionTreeProblem.cs" /> 80 81 <Compile Include="Problems\EvenParityProblem.cs" /> 81 82 <Compile Include="Problems\FindPhrasesProblem.cs" /> … … 95 96 <Compile Include="Sequence.cs" /> 96 97 <Compile Include="Properties\AssemblyInfo.cs" /> 97 <Compile Include="TreeRepresentation\ISymbolicExpressionTreeProblem.cs" />98 98 </ItemGroup> 99 99 <ItemGroup> -
branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/FindPhrasesProblem.cs
r11851 r11865 3 3 using System.Diagnostics; 4 4 using System.Linq; 5 using System.Text; 5 6 using HeuristicLab.Common; 7 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; 6 8 7 9 namespace HeuristicLab.Problems.GrammaticalOptimization { … … 19 21 // this problem should be similar to symbolic regression and should be easier for approaches using a state esimation value and the canoncial state 20 22 // when phrases are symbol sets instead of sequences then value-estimation routines should be better (TD) 21 public class FindPhrasesProblem : I Problem {23 public class FindPhrasesProblem : ISymbolicExpressionTreeProblem { 22 24 23 25 private readonly IGrammar grammar; … … 45 47 this.phrasesAsSets = phrasesAsSets; 46 48 47 // create grammar48 49 var sentenceSymbol = 'S'; 49 50 var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray(); 50 var nonTerminalSymbols = new char[] { 'S' }; 51 var rules = terminalSymbols.Select(t => Tuple.Create('S', t.ToString())) 52 .Concat(terminalSymbols.Select(t => Tuple.Create('S', t + "S"))); 51 var nonTerminalSymbols = new char[] { sentenceSymbol }; 53 52 54 this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules); 53 { 54 // create grammar 55 // S -> a..z | aS .. zS 56 var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString())) 57 .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString()))); 58 59 this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules); 60 } 61 { 62 // create grammar for tree-based GP 63 // S -> a..z | SS 64 var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString())) 65 .Concat(new Tuple<char, string>[] { Tuple.Create(sentenceSymbol, sentenceSymbol.ToString() + sentenceSymbol) }); 66 67 this.TreeBasedGPGrammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules); 68 } 55 69 56 70 // generate optimal phrases … … 144 158 } 145 159 146 public IEnumerable<Feature> GetFeatures(string phrase) 147 { 160 public IEnumerable<Feature> GetFeatures(string phrase) { 148 161 throw new NotImplementedException(); 149 162 } … … 153 166 optimalPhrases.Count, correctReward, decoyPhrases.Count, decoyReward, phrasesAsSets); 154 167 } 168 169 public IGrammar TreeBasedGPGrammar { get; private set; } 170 public string ConvertTreeToSentence(ISymbolicExpressionTree tree) { 171 var sb = new StringBuilder(); 172 foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) { 173 if (s.Symbol.Name == "S") continue; 174 sb.Append(s.Symbol.Name); 175 } 176 return sb.ToString(); 177 } 155 178 } 156 179 } -
branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalPhraseSequenceProblem.cs
r11832 r11865 6 6 using System.Text.RegularExpressions; 7 7 using HeuristicLab.Common; 8 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; 8 9 9 10 namespace HeuristicLab.Problems.GrammaticalOptimization { … … 21 22 // for phraseLen > 1 this should be harder than RoyalSymbolProblem 22 23 // when phrases are symbol sets instead of sequences then value-estimation routines should be better (TD) 23 public class RoyalPhraseSequenceProblem : I Problem {24 public class RoyalPhraseSequenceProblem : ISymbolicExpressionTreeProblem { 24 25 25 26 private readonly IGrammar grammar; … … 43 44 this.incorrectReward = incorrectReward; 44 45 this.phrasesAsSets = phrasesAsSets; 46 45 47 var sentenceSymbol = 'S'; 46 48 var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray(); 47 var nonTerminalSymbols = new char[] { 'S' }; 48 var rules = terminalSymbols.Select(t => Tuple.Create('S', t.ToString())) 49 .Concat(terminalSymbols.Select(t => Tuple.Create('S', t + "S"))); 49 var nonTerminalSymbols = new char[] { sentenceSymbol }; 50 50 51 this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules); 51 { 52 // create grammar 53 // S -> a..z | aS .. zS 54 var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString())) 55 .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString()))); 56 57 this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules); 58 } 59 { 60 // create grammar for tree-based GP 61 // S -> a..z | SS 62 var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString())) 63 .Concat(new Tuple<char, string>[] { Tuple.Create(sentenceSymbol, sentenceSymbol.ToString() + sentenceSymbol) }); 64 65 this.TreeBasedGPGrammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules); 66 } 52 67 53 68 this.optimalPhrasesForPos = new SortedSet<string>[sequenceLen]; … … 133 148 } 134 149 135 public IEnumerable<Feature> GetFeatures(string phrase) 136 { 150 public IEnumerable<Feature> GetFeatures(string phrase) { 137 151 throw new NotImplementedException(); 152 } 153 154 public IGrammar TreeBasedGPGrammar { get; private set; } 155 public string ConvertTreeToSentence(ISymbolicExpressionTree tree) { 156 var sb = new StringBuilder(); 157 foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) { 158 if (s.Symbol.Name == "S") continue; 159 sb.Append(s.Symbol.Name); 160 } 161 return sb.ToString(); 138 162 } 139 163 } -
branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalSequenceProblem.cs
r11832 r11865 6 6 using System.Text.RegularExpressions; 7 7 using HeuristicLab.Common; 8 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; 8 9 9 10 namespace HeuristicLab.Problems.GrammaticalOptimization { … … 15 16 // 16 17 // this problem should be hard for GP and easy for MCTS (TD should not have an advantage compared to MCTS) 17 public class RoyalSequenceProblem : I Problem {18 public class RoyalSequenceProblem : ISymbolicExpressionTreeProblem { 18 19 19 20 private readonly IGrammar grammar; … … 31 32 this.correctReward = correctReward; 32 33 this.incorrectReward = incorrectReward; 34 33 35 const char sentenceSymbol = 'S'; 34 36 var terminalSymbols = Enumerable.Range(0, alphabetSize).Select(off => (char)((byte)'a' + off)).ToArray(); 35 37 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()))); 38 //var rules = terminalSymbols.Select(t => Tuple.Create('S', t + "S")) 39 // .Concat(terminalSymbols.Select(t => Tuple.Create('S', t.ToString()))); 40 this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules); 38 39 { 40 // create grammar for sequential search 41 // S -> a..z | aS .. zS 42 var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString())) 43 .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString()))); 44 this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules); 45 } 46 { 47 // create grammar for sequential search 48 // S -> a..z | SS 49 var rules = terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t.ToString())) 50 .Concat(terminalSymbols.Select(t => Tuple.Create(sentenceSymbol, t + sentenceSymbol.ToString()))); 51 this.grammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols, rules); 52 } 41 53 42 54 this.optimalSymbolsForPos = new SortedSet<char>[sequenceLen]; … … 89 101 } 90 102 91 public IEnumerable<Feature> GetFeatures(string phrase) 92 { 103 public IEnumerable<Feature> GetFeatures(string phrase) { 93 104 throw new NotImplementedException(); 105 } 106 107 public IGrammar TreeBasedGPGrammar { get; private set; } 108 public string ConvertTreeToSentence(ISymbolicExpressionTree tree) { 109 var sb = new StringBuilder(); 110 foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) { 111 if (s.Symbol.Name == "S") continue; 112 sb.Append(s.Symbol.Name); 113 } 114 return sb.ToString(); 94 115 } 95 116 } -
branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/RoyalTreeProblem.cs
r11832 r11865 1 1 using System; 2 2 using System.Collections.Generic; 3 using System.Diagnostics; 3 4 using System.Linq; 4 5 using System.Text; 6 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding; 5 7 6 8 namespace HeuristicLab.Problems.GrammaticalOptimization { 7 public class RoyalTreeProblem : I Problem {9 public class RoyalTreeProblem : ISymbolicExpressionTreeProblem { 8 10 // Punch: "How Effective Are Multiple Populations in Genetic Programming", 1998 9 private const string grammarString = @" 10 G(S): 11 S -> 0 12 "; 11 // In fact, for a new GP system it is dicult to judge whether it is performing 12 // as intended or not, since the programs it generates are not necessarily identical to 13 // those generated by other GP systems. This raised two questions: what constitutes 14 // a "standard" problem in GP, and how do we rate the performance of a system on 15 // such a problem. 16 // One of the goals of this research was to create a benchmark problem to test how 17 // well a particular GP configuration would perform as compared to other configurations. 18 // ... 19 // We were interested in addressing the same issues, showing how GP could address 20 // difficult problems as well as providing a tunable benchmark for comparing GP con- 21 // figurations. Furthermore, we were interested in creating and using this benchmark 22 // to test the effectiveness of coarse-grain parallel GP's as compared to single population 23 // GP's. 24 // ... 25 // A suitable benchmark problem which has only a single, unique tree as an answer can remove this obstruction. 13 26 14 27 private readonly IGrammar grammar; 15 public RoyalTreeProblem() { 16 this.grammar = new Grammar(grammarString); 17 } 28 private readonly char targetRootSymbol; 29 // the number of levels determines the number of non-terminal symbols 30 // non-terminal A has only one argument, non-terminal B has two arguments ... 31 // optimal level-e tree has quality 122880, 32 // level-a (a) tree has 33 // level-f (6) tree "is extremely difficult" 34 // level-g (7) tree "never succeeded" 35 public RoyalTreeProblem(int levels) { 36 if (levels < 1 || levels > 7) throw new ArgumentException(); 37 var sentenceSymbol = 'S'; 38 var terminalSymbols = new char[] { 'x', 'y', 'z' }; 39 // originally non-terminal-symbols (but for the sequential search grammar these are only alternatives 40 var nonTerminalSymbols = Enumerable.Range(0, levels).Select(lvl => (char)(lvl + (byte)'A')).ToArray(); // [A, B ... ] 41 var arities = Enumerable.Range(1, levels).ToArray(); // [1, 2, ... levels] 42 this.targetRootSymbol = char.ToLower(nonTerminalSymbols.Last()); 43 { 44 // grammar for sequential search 45 // S -> x | y | z | aS | bSS | cSSS ... 46 47 var rules = new List<Tuple<char, string>>(); 48 foreach (var symb in terminalSymbols) { 49 rules.Add(Tuple.Create('S', symb.ToString())); 50 } 51 for (int ntIdx = 0; ntIdx < nonTerminalSymbols.Length; ntIdx++) { 52 var opSymb = char.ToLower(nonTerminalSymbols[ntIdx]); 53 var remChain = string.Join("", Enumerable.Repeat('S', arities[ntIdx])); 54 rules.Add(Tuple.Create('S', opSymb + remChain)); 55 } 56 57 this.grammar = new Grammar(sentenceSymbol, terminalSymbols.Concat(nonTerminalSymbols.Select(char.ToLower)), new char[] { 'S' }, rules); 58 } 59 60 { 61 // grammar for tree-based GP 62 // S -> x | y | z | A | B | C ... 63 // A -> S 64 // B -> SS 65 // C -> SSS 66 var rules = new List<Tuple<char, string>>(); 67 foreach (var symb in terminalSymbols.Concat(nonTerminalSymbols)) { 68 rules.Add(Tuple.Create('S', symb.ToString())); 69 } 70 71 for (int ntIdx = 0; ntIdx < nonTerminalSymbols.Length; ntIdx++) { 72 var ntSymb = nonTerminalSymbols[ntIdx]; 73 var alt = string.Join("", Enumerable.Repeat('S', arities[ntIdx])); 74 rules.Add(Tuple.Create(ntSymb, alt)); 75 } 76 this.TreeBasedGPGrammar = new Grammar(sentenceSymbol, terminalSymbols, nonTerminalSymbols.Concat(new char[] { 'S' }), rules); 77 } 78 79 maxSizeForLevel = new int[8]; 80 optimalSentencesForLevel = new string[8]; 81 optimalQualityForLevel = new double[8]; 82 maxSizeForLevel[0] = 1; // lvl-0 (x | y) 83 maxSizeForLevel[1] = 2; // lvl-1 (e.g. ax) 84 optimalSentencesForLevel[0] = "x"; 85 optimalQualityForLevel[0] = 1; 86 //optimalSentencesForLevel[1] = "ax"; 87 //optimalQualityForLevel[1] = 4; 88 89 for (int i = 1; i < maxSizeForLevel.Length; i++) { 90 maxSizeForLevel[i] = i * maxSizeForLevel[i - 1] + 1; // e.g. lvl-2: baxax 91 92 var opSymb = char.ToLower(nonTerminalSymbols[i - 1]); 93 optimalSentencesForLevel[i] = opSymb + 94 string.Join("", 95 Enumerable.Repeat(optimalSentencesForLevel[i - 1], arities[i - 1])); 96 97 optimalQualityForLevel[i] = Evaluate(optimalSentencesForLevel[i]); 98 } 99 100 // from the paper 101 Debug.Assert(maxSizeForLevel[5] == 326); 102 Debug.Assert(maxSizeForLevel[6] == 1957); 103 } 104 105 private readonly string[] optimalSentencesForLevel; 106 private readonly double[] optimalQualityForLevel; 107 private readonly int[] maxSizeForLevel; 18 108 19 109 public double BestKnownQuality(int maxLen) { 20 // for now only an upper bound is returned, ideally all fitness cases are predicted correctly 21 throw new NotImplementedException(); 110 // search for corresponding level 111 int level = 0; 112 while (maxSizeForLevel[level + 1] < maxLen) level++; 113 // ASSERT: maxSizeForLevel[level + 1] >= maxLen 114 return optimalQualityForLevel[level]; 22 115 } 23 116 … … 27 120 28 121 public double Evaluate(string sentence) { 29 throw new NotImplementedException(); 30 } 122 int pos = 0; 123 bool perfect; 124 return Evaluate(sentence, ref pos, out perfect); 125 } 126 127 private double Evaluate(string sentence, ref int pos, out bool perfect) { 128 const double completeBonus = 2.0; 129 double t = 0.0; 130 double weight = 0.0; 131 double sum = 0.0; 132 bool correctRoot = false; 133 bool allPerfect = true, tPerfect; 134 int arity; 135 switch (sentence[pos]) { 136 case 'a': 137 pos++; 138 correctRoot = (sentence[pos] == 'x'); 139 t = Evaluate(sentence, ref pos, out tPerfect); // ignores the perfect flag (false for terminals) 140 weight = GetWeight(correctRoot, true); 141 sum = weight * t; 142 perfect = correctRoot; 143 if (correctRoot) sum *= completeBonus; 144 return sum; 145 case 'b': { 146 arity = 2; 147 pos++; 148 for (int i = 0; i < arity; i++) { 149 correctRoot = (sentence[pos] == 'a'); 150 t = Evaluate(sentence, ref pos, out tPerfect); 151 weight = GetWeight(correctRoot, tPerfect); 152 allPerfect &= correctRoot & tPerfect; 153 sum += weight * t; 154 } 155 perfect = allPerfect; 156 if (allPerfect) sum *= completeBonus; 157 return sum; 158 } 159 case 'c': { 160 arity = 3; 161 sum = 0.0; 162 pos++; 163 for (int i = 0; i < arity; i++) { 164 correctRoot = (sentence[pos] == 'b'); 165 t = Evaluate(sentence, ref pos, out tPerfect); 166 weight = GetWeight(correctRoot, tPerfect); 167 allPerfect &= correctRoot & tPerfect; 168 sum += weight * t; 169 } 170 perfect = allPerfect; 171 if (allPerfect) sum *= completeBonus; 172 return sum; 173 } 174 case 'd': { 175 arity = 4; 176 sum = 0.0; 177 pos++; 178 for (int i = 0; i < arity; i++) { 179 correctRoot = (sentence[pos] == 'c'); 180 t = Evaluate(sentence, ref pos, out tPerfect); 181 weight = GetWeight(correctRoot, tPerfect); 182 allPerfect &= correctRoot & tPerfect; 183 sum += weight * t; 184 } 185 perfect = allPerfect; 186 if (allPerfect) sum *= completeBonus; 187 return sum; 188 } 189 case 'e': { 190 arity = 5; 191 sum = 0.0; 192 pos++; 193 for (int i = 0; i < arity; i++) { 194 correctRoot = (sentence[pos] == 'd'); 195 t = Evaluate(sentence, ref pos, out tPerfect); 196 weight = GetWeight(correctRoot, tPerfect); 197 allPerfect &= correctRoot & tPerfect; 198 sum += weight * t; 199 } 200 perfect = allPerfect; 201 if (allPerfect) sum *= completeBonus; 202 return sum; 203 } 204 case 'f': { 205 arity = 6; 206 sum = 0.0; 207 pos++; 208 for (int i = 0; i < arity; i++) { 209 correctRoot = (sentence[pos] == 'e'); 210 t = Evaluate(sentence, ref pos, out tPerfect); 211 weight = GetWeight(correctRoot, tPerfect); 212 allPerfect &= correctRoot & tPerfect; 213 sum += weight * t; 214 } 215 perfect = allPerfect; 216 if (allPerfect) sum *= completeBonus; 217 return sum; 218 } 219 case 'g': { 220 arity = 7; 221 sum = 0.0; 222 pos++; 223 for (int i = 0; i < arity; i++) { 224 correctRoot = (sentence[pos] == 'f'); 225 t = Evaluate(sentence, ref pos, out tPerfect); 226 weight = GetWeight(correctRoot, tPerfect); 227 allPerfect &= correctRoot & tPerfect; 228 sum += weight * t; 229 } 230 perfect = allPerfect; 231 if (allPerfect) sum *= completeBonus; 232 return sum; 233 } 234 case 'x': 235 pos++; 236 perfect = false; 237 return 1.0; 238 case 'y': 239 case 'z': 240 pos++; 241 perfect = false; 242 return 0.0; 243 default: throw new ArgumentException(); 244 } 245 } 246 247 private double GetWeight(bool correctRoot, bool perfect) { 248 const double fullBonus = 2.0; 249 const double partialBonus = 1.0; 250 const double penalty = 0.33; 251 if (correctRoot && perfect) return fullBonus; 252 else if (correctRoot) return partialBonus; 253 else return penalty; 254 } 255 31 256 public string CanonicalRepresentation(string phrase) { 32 257 throw new NotImplementedException(); … … 34 259 } 35 260 36 public IEnumerable<Feature> GetFeatures(string phrase) 37 { 261 public IEnumerable<Feature> GetFeatures(string phrase) { 38 262 throw new NotImplementedException(); 263 } 264 265 public IGrammar TreeBasedGPGrammar { get; private set; } 266 public string ConvertTreeToSentence(ISymbolicExpressionTree tree) { 267 var sb = new StringBuilder(); 268 foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) { 269 if (s.Symbol.Name == "S") continue; 270 sb.Append(s.Symbol.Name.ToLower()); 271 } 272 return sb.ToString(); 39 273 } 40 274 } -
branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SentenceSetStatistics.cs
r11847 r11865 23 23 public SentenceSetStatistics(double bestKnownQuality = 1.0) { 24 24 this.bestKnownQuality = bestKnownQuality; 25 BestSentenceQuality = double.NegativeInfinity; 26 BestSentence = string.Empty; 27 FirstSentence = string.Empty; 28 LastSentence = string.Empty; 25 29 } 26 30
Note: See TracChangeset
for help on using the changeset viewer.