Changeset 11846


Ignore:
Timestamp:
02/01/15 16:32:26 (8 years ago)
Author:
gkronber
Message:

#2283 implemented bridge to HL (solve grammatical optimization problem instances with StandardGP and OffspringSelectionGP)

Location:
branches/HeuristicLab.Problems.GrammaticalOptimization
Files:
13 added
13 edited

Legend:

Unmodified
Added
Removed

  • branches/HeuristicLab.Problems.GrammaticalOptimization/GrammaticalOptimization.sln

    r11732 r11846  
    1515EndProject
    1616Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Problems.GrammaticalOptimization.SymbReg", "HeuristicLab.Problems.GrammaticalOptimization.SymbReg\HeuristicLab.Problems.GrammaticalOptimization.SymbReg.csproj", "{17A7A380-86CE-482D-8D22-CBD70CC97F0D}"
     17EndProject
     18Project("{FAE04EC0-301F-11D3-BF4B-00C04F79EFBC}") = "HeuristicLab.Algorithms.GeneticProgramming", "HeuristicLab.Algorithms.GeneticProgramming\HeuristicLab.Algorithms.GeneticProgramming.csproj", "{14BEC23F-63FD-4954-B8AE-E2F4962E9B57}"
    1719EndProject
    1820Global
    … …  
    5052    {17A7A380-86CE-482D-8D22-CBD70CC97F0D}.Release|Any CPU.ActiveCfg = Release|Any CPU
    5153    {17A7A380-86CE-482D-8D22-CBD70CC97F0D}.Release|Any CPU.Build.0 = Release|Any CPU
     54    {14BEC23F-63FD-4954-B8AE-E2F4962E9B57}.Debug|Any CPU.ActiveCfg = Debug|Any CPU
     55    {14BEC23F-63FD-4954-B8AE-E2F4962E9B57}.Debug|Any CPU.Build.0 = Debug|Any CPU
     56    {14BEC23F-63FD-4954-B8AE-E2F4962E9B57}.Release|Any CPU.ActiveCfg = Release|Any CPU
     57    {14BEC23F-63FD-4954-B8AE-E2F4962E9B57}.Release|Any CPU.Build.0 = Release|Any CPU
    5258  EndGlobalSection
    5359  GlobalSection(SolutionProperties) = preSolution

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

    r11806 r11846  
    4545    <Compile Include="AlternativesSampler.cs" />
    4646    <Compile Include="AlternativesContextSampler.cs" />
     47    <Compile Include="SolverBase.cs" />
     48    <Compile Include="ISolver.cs" />
    4749    <Compile Include="SequentialSearch.cs" />
    4850    <Compile Include="ExhaustiveRandomFirstSearch.cs" />

  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/RandomSearch.cs

    r11793 r11846  
    33
    44namespace HeuristicLab.Algorithms.GrammaticalOptimization {
    5   public class RandomSearch {
    6     public event Action<string, double> FoundNewBestSolution;
    7     public event Action<string, double> SolutionEvaluated;
    8 
     5  public class RandomSearch : SolverBase {
    96    private readonly int maxLen;
    107    private readonly Random random;
    … …  
    1714    }
    1815
    19     public void Run(int maxIterations) {
    20       double bestQuality = double.MinValue;
     16    public override void Run(int maxIterations) {
    2117      for (int i = 0; i < maxIterations; i++) {
    2218        var sentence = CreateSentence(problem.Grammar).ToString();
    2319        var quality = problem.Evaluate(sentence) / problem.BestKnownQuality(maxLen);
    24         RaiseSolutionEvaluated(sentence, quality);
    25 
    26         if (quality > bestQuality) {
    27           bestQuality = quality;
    28           RaiseFoundNewBestSolution(sentence, quality);
    29         }
     20        OnSolutionEvaluated(sentence, quality);
    3021      }
    3122    }
    … …  
    3526      return grammar.CompleteSentenceRandomly(random, sentence, maxLen);
    3627    }
    37 
    38     private void RaiseSolutionEvaluated(string sentence, double quality) {
    39       var handler = SolutionEvaluated;
    40       if (handler != null) handler(sentence, quality);
    41     }
    42     private void RaiseFoundNewBestSolution(string sentence, double quality) {
    43       var handler = FoundNewBestSolution;
    44       if (handler != null) handler(sentence, quality);
    45     }
    4628  }
    4729}

  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GrammaticalOptimization/SequentialSearch.cs

    r11806 r11846  
    2323  //    ... until phrase is terminal
    2424  // 3) Collect reward and update policy (feedback: state of visited rewards from step 2)
    25   public class SequentialSearch {
     25  public class SequentialSearch : SolverBase {
    2626    // only for storing states so that it is not necessary to allocate new state strings whenever we select a follow state using the policy
    2727    private class TreeNode {
    … …  
    3737    }
    3838
    39 
    40     public event Action<string, double> FoundNewBestSolution;
    41     public event Action<string, double> SolutionEvaluated;
    4239
    4340    private readonly int maxLen;
    … …  
    5249    private int maxSearchDepth;
    5350
    54     private double bestQuality;
    5551    private string bestPhrase;
    5652    private readonly List<string> stateChain;
    … …  
    6662    }
    6763
    68     public void Run(int maxIterations) {
    69       bestQuality = double.MinValue;
     64    public override void Run(int maxIterations) {
    7065      Reset();
    7166
    … …  
    7974          if (double.IsNaN(quality)) quality = 0.0;
    8075          Debug.Assert(quality >= 0 && quality <= 1.0);
     76
     77          if (quality > bestQuality) {
     78            bestPhrase = sentence;
     79          }
     80
     81          OnSolutionEvaluated(sentence, quality);
    8182          DistributeReward(quality);
    8283
    83           RaiseSolutionEvaluated(sentence, quality);
    84 
    85           if (quality > bestQuality) {
    86             bestQuality = quality;
    87             bestPhrase = sentence;
    88             RaiseFoundNewBestSolution(sentence, quality);
    89           }
    9084        }
    9185      }
    … …  
    244238    }
    245239    #endregion
    246 
    247     private void RaiseSolutionEvaluated(string sentence, double quality) {
    248       var handler = SolutionEvaluated;
    249       if (handler != null) handler(sentence, quality);
    250     }
    251     private void RaiseFoundNewBestSolution(string sentence, double quality) {
    252       var handler = FoundNewBestSolution;
    253       if (handler != null) handler(sentence, quality);
    254     }
     240 
    255241  }
    256242}

  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Common/Extensions.cs

    r11799 r11846  
    77namespace HeuristicLab.Common {
    88  public static class Extensions {
     9   
    910    public static bool IsAlmost(this double x, double y) {
    1011      return Math.Abs(x - y) < 1.0e-12;

  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.Test/HeuristicLab.Problems.GrammaticalOptimization.Test.csproj

    r11732 r11846  
    3939  </PropertyGroup>
    4040  <ItemGroup>
     41    <Reference Include="HeuristicLab.Common-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     42      <SpecificVersion>False</SpecificVersion>
     43      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>
     44    </Reference>
     45    <Reference Include="HeuristicLab.Core-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     46      <SpecificVersion>False</SpecificVersion>
     47      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Core-3.3.dll</HintPath>
     48    </Reference>
     49    <Reference Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4, Version=3.4.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     50      <SpecificVersion>False</SpecificVersion>
     51      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll</HintPath>
     52    </Reference>
    4153    <Reference Include="HeuristicLab.Problems.Instances-3.3">
    4254      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Problems.Instances-3.3.dll</HintPath>

  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.csproj

    r11842 r11846  
    3434  </PropertyGroup>
    3535  <ItemGroup>
     36    <Reference Include="HeuristicLab.Collections-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     37      <SpecificVersion>False</SpecificVersion>
     38      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Collections-3.3.dll</HintPath>
     39    </Reference>
     40    <Reference Include="HeuristicLab.Common-3.3">
     41      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Common-3.3.dll</HintPath>
     42    </Reference>
     43    <Reference Include="HeuristicLab.Core-3.3">
     44      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Core-3.3.dll</HintPath>
     45    </Reference>
     46    <Reference Include="HeuristicLab.Data-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     47      <SpecificVersion>False</SpecificVersion>
     48      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Data-3.3.dll</HintPath>
     49    </Reference>
     50    <Reference Include="HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4">
     51      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll</HintPath>
     52    </Reference>
     53    <Reference Include="HeuristicLab.Operators-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     54      <SpecificVersion>False</SpecificVersion>
     55      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Operators-3.3.dll</HintPath>
     56    </Reference>
     57    <Reference Include="HeuristicLab.Optimization-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     58      <SpecificVersion>False</SpecificVersion>
     59      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Optimization-3.3.dll</HintPath>
     60    </Reference>
     61    <Reference Include="HeuristicLab.Parameters-3.3, Version=3.3.0.0, Culture=neutral, PublicKeyToken=ba48961d6f65dcec, processorArchitecture=MSIL">
     62      <SpecificVersion>False</SpecificVersion>
     63      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Parameters-3.3.dll</HintPath>
     64    </Reference>
     65    <Reference Include="HeuristicLab.Persistence-3.3">
     66      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Persistence-3.3.dll</HintPath>
     67    </Reference>
     68    <Reference Include="HeuristicLab.PluginInfrastructure-3.3">
     69      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.PluginInfrastructure-3.3.dll</HintPath>
     70    </Reference>
     71    <Reference Include="HeuristicLab.SequentialEngine-3.3">
     72      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.SequentialEngine-3.3.dll</HintPath>
     73    </Reference>
    3674    <Reference Include="System" />
    3775    <Reference Include="System.Core" />
     76    <Reference Include="System.Drawing" />
    3877    <Reference Include="System.Xml.Linq" />
    3978    <Reference Include="System.Data.DataSetExtensions" />
    … …  
    4382  </ItemGroup>
    4483  <ItemGroup>
     84    <Compile Include="ISymbolicExpressionTreeProblem.cs" />
    4585    <Compile Include="Feature.cs" />
     86    <Compile Include="Problems\GrammaticalOptimizationEvaluator.cs" />
     87    <Compile Include="Problems\IGrammaticalOptimizationEvaluator.cs" />
     88    <Compile Include="Problems\GenericSymbExprProblem.cs" />
     89    <Compile Include="Problems\GenericSymbExprGrammar.cs" />
    4690    <Compile Include="Problems\EvenParityProblem.cs" />
    4791    <Compile Include="Problems\ExpressionInterpreter.cs" />

  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/IProblem.cs

    r11832 r11846  
    33using System.Linq;
    44using System.Text;
     5using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    56
    67namespace HeuristicLab.Problems.GrammaticalOptimization {
     8  // represents a grammatical optimization problem
    79  public interface IProblem {
    810    double BestKnownQuality(int maxLen);

  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/ExpressionInterpreter.cs

    r11832 r11846  
    3535      var d = new double[vars.Length];
    3636      for (int i = 0; i < vars.Length; i++) d[i] = vars[i] ? 1.0 : 0.0;
    37       return !(Expr(d, erc).IsAlmost(0));
     37      return ! DoubleExtensions.IsAlmost(Expr(d, erc), 0);
    3838    }
    3939
    … …  
    6363    // helper for xor
    6464    private double Not(double x) {
    65       return x.IsAlmost(0) ? 1.0 : 0.0;
     65      return DoubleExtensions.IsAlmost(x, 0) ? 1.0 : 0.0;
    6666    }
    6767

  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Problems/SymbolicRegressionPoly10Problem.cs

    r11832 r11846  
    33using System.Collections.Generic;
    44using System.Collections.Specialized;
     5using System.Diagnostics;
    56using System.Linq;
    67using System.Net;
    … …  
    910using System.Text;
    1011using HeuristicLab.Common;
     12using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    1113
    1214namespace HeuristicLab.Problems.GrammaticalOptimization {
    13   public class SymbolicRegressionPoly10Problem : IProblem {
     15  public class SymbolicRegressionPoly10Problem : ISymbolicExpressionTreeProblem {
    1416    //    private const string grammarString = @"
    1517    //    G(E):
    … …  
    2224    ";
    2325
     26    // for tree-based GP in HL we need a different grammar for the same language
     27    // E = expr, S = sum, P = product
     28    private const string hlGrammarString = @"
     29    G(E):
     30    E -> S | P | a | b | c | d | e | f | g | h | i | j
     31    S -> EE | EEE
     32    P -> EE | EEE
     33    ";
     34    // mininmal tree for the optimal expr (40 nodes)
     35    // E S
     36    //     E S
     37    //         E P
     38    //           E a E b
     39    //         E P
     40    //           E c E d
     41    //         E P
     42    //           E e E f
     43    //     E S
     44    //         E P
     45    //           E a E g E i
     46    //         E P
     47    //           E c E f E j
     48
     49    private SymbolicExpressionGrammar symbExprGrammar;
     50    public ISymbolicExpressionGrammar SymbolicExpressionGrammar {
     51      get {
     52        return symbExprGrammar;
     53      }
     54    }
    2455
    2556    private readonly IGrammar grammar;
    … …  
    3162    public SymbolicRegressionPoly10Problem() {
    3263      this.grammar = new Grammar(grammarString);
     64      this.symbExprGrammar = new GenericSymbExprGrammar(new Grammar(hlGrammarString));
    3365
    3466      this.N = 500;
    … …  
    71103      return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])).ToArray());
    72104    }
    73 
    74105
    75106
    … …  
    130161    }
    131162
     163    public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
     164      var sb = new StringBuilder();
     165
     166      TreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
     167
     168      return sb.ToString();
     169    }
     170
     171    private void TreeToSentence(ISymbolicExpressionTreeNode treeNode, StringBuilder sb) {
     172      if (treeNode.SubtreeCount == 0) {
     173        // terminal
     174        sb.Append(treeNode.Symbol.Name);
     175      } else {
     176        string op = string.Empty;
     177        switch (treeNode.Symbol.Name) {
     178          case "S": op = "+"; break;
     179          case "P": op = "*"; break;
     180          default: {
     181              Debug.Assert(treeNode.SubtreeCount == 1);
     182              break;
     183            }
     184        }
     185        // nonterminal
     186        if (op == "+") sb.Append("(");
     187        TreeToSentence(treeNode.Subtrees.First(), sb);
     188        foreach (var subTree in treeNode.Subtrees.Skip(1)) {
     189          sb.Append(op);
     190          TreeToSentence(subTree, sb);
     191        }
     192        if (op == "+") sb.Append(")");
     193      }
     194    }
    132195  }
    133196}

  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/SentenceSetStatistics.cs

    r11730 r11846  
    4141    public override string ToString() {
    4242      return
    43         string.Format("Sentences: {0,10} avg.-quality {1,7:F5} best {2,7:F5} {3,2} {4,10} {5} first {6,7:F5} {7} last {8,7:F5} {9}",
     43        string.Format("Sentences: {0,10} avg.-quality {1,7:F5} best {2,7:F5} {3,2} {4,10} {5,30} first {6,7:F5} {7,20} last {8,7:F5} {9,20}",
    4444      NumberOfSentences, AverageQuality,
    45       BestSentenceQuality, BestSentenceQuality.IsAlmost(1.0)?1.0:0.0,
    46       BestSentenceIndex, BestSentence,
    47       FirstSentenceQuality, FirstSentence,
    48       LastSentenceQuality, LastSentence
     45      BestSentenceQuality, DoubleExtensions.IsAlmost(BestSentenceQuality, 1.0) ? 1.0 : 0.0,
     46      BestSentenceIndex, TrimToSize(BestSentence, 30),
     47      FirstSentenceQuality, TrimToSize(FirstSentence, 20),
     48      LastSentenceQuality, TrimToSize(LastSentence, 20)
    4949     );
     50    }
     51
     52    private string TrimToSize(string s, int len) {
     53      if (s.Length < len) return s;
     54      else {
     55        var sb = new StringBuilder(len);
     56        sb.Append(s.Substring(0, len - 3));
     57        sb.Append("...");
     58        return sb.ToString();
     59      }
    5060    }
    5161  }

  • branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Main.csproj

    r11732 r11846  
    3636  </PropertyGroup>
    3737  <ItemGroup>
     38    <Reference Include="HeuristicLab.Algorithms.GeneticAlgorithm-3.3">
     39      <HintPath>..\..\..\trunk\sources\bin\HeuristicLab.Algorithms.GeneticAlgorithm-3.3.dll</HintPath>
     40    </Reference>
    3841    <Reference Include="System" />
    3942    <Reference Include="System.Core" />
    40     <Reference Include="System.Xml.Linq" />
    41     <Reference Include="System.Data.DataSetExtensions" />
    42     <Reference Include="Microsoft.CSharp" />
    43     <Reference Include="System.Data" />
    44     <Reference Include="System.Xml" />
    4543  </ItemGroup>
    4644  <ItemGroup>
    … …  
    5250      <Project>{24408F7D-EE0F-4886-A08B-EC324D662E47}</Project>
    5351      <Name>HeuristicLab.Algorithms.Bandits</Name>
     52    </ProjectReference>
     53    <ProjectReference Include="..\HeuristicLab.Algorithms.GeneticProgramming\HeuristicLab.Algorithms.GeneticProgramming.csproj">
     54      <Project>{14BEC23F-63FD-4954-B8AE-E2F4962E9B57}</Project>
     55      <Name>HeuristicLab.Algorithms.GeneticProgramming</Name>
    5456    </ProjectReference>
    5557    <ProjectReference Include="..\HeuristicLab.Algorithms.GrammaticalOptimization\HeuristicLab.Algorithms.GrammaticalOptimization.csproj">

  • branches/HeuristicLab.Problems.GrammaticalOptimization/Main/Program.cs

    r11832 r11846  
    11using System;
    22using System.Collections.Generic;
    3 using System.Data;
    43using System.Diagnostics;
    54using System.Globalization;
    6 using System.Linq;
    75using System.Text;
     6using System.Threading;
    87using System.Threading.Tasks;
    98using HeuristicLab.Algorithms.Bandits;
    … …  
    1110using HeuristicLab.Algorithms.Bandits.GrammarPolicies;
    1211using HeuristicLab.Algorithms.Bandits.Models;
     12using HeuristicLab.Algorithms.GeneticProgramming;
    1313using HeuristicLab.Algorithms.GrammaticalOptimization;
    1414using HeuristicLab.Problems.GrammaticalOptimization;
    15 using HeuristicLab.Problems.GrammaticalOptimization.SymbReg;
    1615using BoltzmannExplorationPolicy = HeuristicLab.Algorithms.Bandits.BanditPolicies.BoltzmannExplorationPolicy;
    1716using EpsGreedyPolicy = HeuristicLab.Algorithms.Bandits.BanditPolicies.EpsGreedyPolicy;
     17using IProblem = HeuristicLab.Problems.GrammaticalOptimization.IProblem;
    1818using RandomPolicy = HeuristicLab.Algorithms.Bandits.BanditPolicies.RandomPolicy;
    1919using UCTPolicy = HeuristicLab.Algorithms.Bandits.BanditPolicies.UCTPolicy;
    … …  
    2525
    2626      //RunDemo();
    27       RunGridTest();
     27      RunGpDemo();
     28      // RunGridTest();
    2829    }
    2930
    … …  
    296297        (double)sw.ElapsedMilliseconds * 1000 / maxIterations);
    297298    }
     299
     300    public static void RunGpDemo() {
     301
     302      int iterations = 0;
     303      const int maxIterations = 100000;
     304      const int seed = 31415;
     305      var globalStatistics = new SentenceSetStatistics();
     306
     307      var gp = new StandardGP(new SymbolicRegressionPoly10Problem(), new Random(seed));
     308      gp.FoundNewBestSolution += (sentence, quality) => {
     309        Console.WriteLine("{0}", globalStatistics);
     310      };
     311      gp.SolutionEvaluated += (sentence, quality) => {
     312        iterations++;
     313        globalStatistics.AddSentence(sentence, quality);
     314
     315        if (iterations % 10000 == 0) {
     316          Console.WriteLine("{0}", globalStatistics);
     317        }
     318      };
     319
     320      var sw = new Stopwatch();
     321
     322      sw.Start();
     323      gp.Run(maxIterations);
     324      sw.Stop();
     325
     326      Console.WriteLine(globalStatistics);
     327      Console.WriteLine("{0:F2} sec {1,10:F1} sols/sec {2,10:F1} ns/sol",
     328        sw.Elapsed.TotalSeconds,
     329        maxIterations / (double)sw.Elapsed.TotalSeconds,
     330        (double)sw.ElapsedMilliseconds * 1000 / maxIterations);
     331    }
    298332  }
    299333}
Note: See TracChangeset for help on using the changeset viewer.