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

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using HeuristicLab.Problems.GrammaticalOptimization;

namespace HeuristicLab.Algorithms.GrammaticalOptimization {
  public class ExhaustiveRandomFirstSearch {
    public event Action<string, double> FoundNewBestSolution;
    public event Action<string, double> SolutionEvaluated;

    private readonly int maxLen;
    private readonly System.Collections.Generic.SortedList<double, Sequence> sortedList = new SortedList<double, Sequence>();
    private readonly IProblem problem;
    private readonly System.Random random;

    public ExhaustiveRandomFirstSearch(IProblem problem, System.Random random, int maxLen) {
      this.maxLen = maxLen;
      this.problem = problem;
      this.random = new System.Random();
    }

    public void Run(int maxIterations) {
      double bestQuality = double.MinValue;
      sortedList.Add(0, new Sequence(problem.Grammar.SentenceSymbol));
      var sentences = GenerateLanguage(problem.Grammar);
      var sentenceEnumerator = sentences.GetEnumerator();
      for (int i = 0; sentenceEnumerator.MoveNext() && i < maxIterations; i++) {
        var sentence = sentenceEnumerator.Current.ToString();
        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
        RaiseSolutionEvaluated(sentence, quality);

        if (quality > bestQuality) {
          bestQuality = quality;
          RaiseFoundNewBestSolution(sentence, quality);
        }
      }
    }

    // create sentences lazily
    private IEnumerable<Sequence> GenerateLanguage(IGrammar grammar) {
      while (sortedList.Any()) {
        var phrase = sortedList.First().Value;
        sortedList.RemoveAt(0);

        char nt = phrase.FirstNonTerminal;
        var alts = grammar.GetAlternatives(nt);
        foreach (var alt in alts) {
          var newPhrase = new Sequence(phrase);
          newPhrase.ReplaceAt(newPhrase.FirstNonTerminalIndex, 1, alt);

          if (newPhrase.IsTerminal && newPhrase.Length <= maxLen) {
            yield return newPhrase;
          } else if (grammar.MinPhraseLength(newPhrase) <= maxLen) {
            var r = random.NextDouble();
            Sequence t;
            while (sortedList.TryGetValue(r, out t)) { r = random.NextDouble(); }
            sortedList.Add(r, newPhrase);
          }
        }
      }
    }


    private void RaiseSolutionEvaluated(string sentence, double quality) {
      var handler = SolutionEvaluated;
      if (handler != null) handler(sentence, quality);
    }
    private void RaiseFoundNewBestSolution(string sentence, double quality) {
      var handler = FoundNewBestSolution;
      if (handler != null) handler(sentence, quality);
    }
  }
}