Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Problems.GrammaticalOptimization-gkr/HeuristicLab.Algorithms.GrammaticalOptimization/Solvers/ExhaustiveRandomFirstSearch.cs @ 13234

Last change on this file since 13234 was 12893, checked in by gkronber, 9 years ago

#2283: experiments on grammatical optimization algorithms (maxreward instead of avg reward, ...)

File size: 2.7 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using HeuristicLab.Problems.GrammaticalOptimization;
6
7namespace HeuristicLab.Algorithms.GrammaticalOptimization {
8  public class ExhaustiveRandomFirstSearch {
9    public event Action<string, double> FoundNewBestSolution;
10    public event Action<string, double> SolutionEvaluated;
11
12    private readonly int maxLen;
13    private readonly System.Collections.Generic.SortedList<double, Sequence> sortedList = new SortedList<double, Sequence>();
14    private readonly IProblem problem;
15    private readonly System.Random random;
16
17    public ExhaustiveRandomFirstSearch(IProblem problem, System.Random random, int maxLen) {
18      this.maxLen = maxLen;
19      this.problem = problem;
20      this.random = new System.Random();
21    }
22
23    public void Run(int maxIterations) {
24      double bestQuality = double.MinValue;
25      sortedList.Add(0, new Sequence(problem.Grammar.SentenceSymbol));
26      var sentences = GenerateLanguage(problem.Grammar);
27      var sentenceEnumerator = sentences.GetEnumerator();
28      for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
29        var sentence = sentenceEnumerator.Current.ToString();
30        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
31        RaiseSolutionEvaluated(sentence, quality);
32
33        if (quality > bestQuality) {
34          bestQuality = quality;
35          RaiseFoundNewBestSolution(sentence, quality);
36        }
37      }
38    }
39
40    // create sentences lazily
41    private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) {
42      while (sortedList.Any()) {
43        var phrase = sortedList.First().Value;
44        sortedList.RemoveAt(0);
45
46        char nt = phrase.FirstNonTerminal;
47        var alts = grammar.GetAlternatives(nt);
48        foreach (var alt in alts) {
49          var newPhrase = new Sequence(phrase);
50          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);
51
52          if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) {
53            yield return newPhrase;
54          } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
55            var r = random.NextDouble();
56            Sequence t;
57            while (sortedList.TryGetValue(r, out t)) { r = random.NextDouble(); }
58            sortedList.Add(r, newPhrase);
59          }
60        }
61      }
62    }
63
64
65    private void RaiseSolutionEvaluated(string sentence, double quality) {
66      var handler = SolutionEvaluated;
67      if (handler != null) handler(sentence, quality);
68    }
69    private void RaiseFoundNewBestSolution(string sentence, double quality) {
70      var handler = FoundNewBestSolution;
71      if (handler != null) handler(sentence, quality);
72    }
73  }
74}
Note: See TracBrowser for help on using the repository browser.