Changeset 11727 for branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization

Timestamp:

12/29/14 11:02:36 (10 years ago)

Author:

gkronber

Message:

#2283: worked on grammatical optimization problem solvers (simple MCTS done)

Location:

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization

Files:

• AlternativesContextSampler.cs (added)
• AlternativesSampler.cs (added)
• ExhaustiveBreadthFirstSearch.cs (modified) (3 diffs)
• ExhaustiveDepthFirstSearch.cs (modified) (2 diffs)
• HeuristicLab.Algorithms.GrammaticalOptimization.csproj (modified) (2 diffs)
• MctsSampler.cs (added)

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveBreadthFirstSearch.cs

@@ -12 +12 @@
     private readonly int maxLen;
     private readonly Queue<string> bfsQueue = new Queue<string>();
+    private readonly IProblem problem;
 
-    public ExhaustiveBreadthFirstSearch(int maxLen) {
+    public ExhaustiveBreadthFirstSearch(IProblem problem, int maxLen) {
+      this.problem = problem;
       this.maxLen = maxLen;
     }
 
-    public void Run(IProblem problem, int maxIterations) {
+    public void Run(int maxIterations) {
       double bestQuality = double.MinValue;
       bfsQueue.Enqueue(problem.Grammar.SentenceSymbol.ToString());
@@ -24 +26 @@
       for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
         var sentence = sentenceEnumerator.Current;
-        var quality = problem.Evaluate(sentence);
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen); 
         RaiseSolutionEvaluated(sentence, quality);
 
@@ -39 +41 @@
         var phrase = bfsQueue.Dequeue();
 
-        var nt = phrase.First(grammar.IsNonTerminal);
-        var ntIdx = phrase.IndexOf(nt); // TODO perf
+        char nt;
+        int ntIdx;
+        Grammar.FindFirstNonTerminal(grammar, phrase, out nt, out ntIdx);
         var alts = grammar.GetAlternatives(nt);
         foreach (var alt in alts) {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/ExhaustiveDepthFirstSearch.cs

@@ -24 +24 @@
       for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
         var sentence = sentenceEnumerator.Current;
-        var quality = problem.Evaluate(sentence);
+        var quality = problem.Evaluate(sentence) / problem.GetBestKnownQuality(maxLen);
         RaiseSolutionEvaluated(sentence, quality);
 
@@ -39 +39 @@
         var phrase = stack.Pop();
 
-        var nt = phrase.First(grammar.IsNonTerminal);
-        var ntIdx = phrase.IndexOf(nt); // TODO perf
+        char nt;
+        int ntIdx;
+        Grammar.FindFirstNonTerminal(grammar, phrase, out nt, out ntIdx);
         var alts = grammar.GetAlternatives(nt);
         foreach (var alt in alts) {

branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization.csproj

@@ -43 +43 @@
   </ItemGroup>
   <ItemGroup>
+    <Compile Include="AlternativesSampler.cs" />
+    <Compile Include="AlternativesContextSampler.cs" />
+    <Compile Include="MctsSampler.cs" />
     <Compile Include="ExhaustiveDepthFirstSearch.cs" />
     <Compile Include="ExhaustiveBreadthFirstSearch.cs" />
@@ -49 +52 @@
   </ItemGroup>
   <ItemGroup>
+    <ProjectReference Include="..\HeuristicLab.Algorithms.Bandits\HeuristicLab.Algorithms.Bandits.csproj">
+      <Project>{24408F7D-EE0F-4886-A08B-EC324D662E47}</Project>
+      <Name>HeuristicLab.Algorithms.Bandits</Name>
+    </ProjectReference>
+    <ProjectReference Include="..\HeuristicLab.Common\HeuristicLab.Common.csproj">
+      <Project>{3A2FBBCB-F9DF-4970-87F3-F13337D941AD}</Project>
+      <Name>HeuristicLab.Common</Name>
+    </ProjectReference>
     <ProjectReference Include="..\HeuristicLab.Problems.GrammaticalOptimization\HeuristicLab.Problems.GrammaticalOptimization.csproj">
       <Project>{cb9dccf6-667e-4a13-b82d-dbd6b45a045e}</Project>