Free cookie consent management tool by TermsFeed Policy Generator

Changeset 12815 for branches


Ignore:
Timestamp:
07/30/15 16:37:14 (9 years ago)
Author:
aballeit
Message:

#2283 added SelectionIndicator for MCTS and problems SantaFeAnt, SymbolicRegression10, RoyalSymbol; updated SantaFeAnt grammar

Location:
branches/HeuristicLab.Problems.GrammaticalOptimization
Files:
1 added
22 edited

Legend:

Unmodified
Added
Removed

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

    r12781 r12815  
    5656    <Compile Include="FoundSolution.cs" />
    5757    <Compile Include="Run.cs" />
     58    <Compile Include="SelectionIndicator.cs" />
    5859    <Compile Include="ViewModel\EvaluationViewModel.cs" />
    5960    <Page Include="MainWindow.xaml">

  • branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/MainWindow.xaml

    r12781 r12815  
    7171                <TextBlock Margin="2" Grid.Column="0" Grid.Row="0" VerticalAlignment="Center">Runs:</TextBlock>
    7272                <TextBox Name="TextBoxRuns" Margin="2" Grid.Column="1" Grid.Row="0" Width="100" VerticalAlignment="Center" TextAlignment="Right" Text="{Binding NrRuns}"></TextBox>
    73                 <TextBlock Margin="2" Grid.Column="0" Grid.Row="1" VerticalAlignment="Center">MaxEvaluations:</TextBlock>
    74                 <TextBox Name="TextBoxMaxEvaluations" Margin="2" Grid.Column="1" Grid.Row="1" Width="100" VerticalAlignment="Center" TextAlignment="Right" Text="{Binding MaxEvaluations}"></TextBox>
     73                <TextBlock Margin="2" Grid.Column="0" Grid.Row="1" VerticalAlignment="Center">MaxIterations:</TextBlock>
     74                <TextBox Name="TextBoxMaxIterations" Margin="2" Grid.Column="1" Grid.Row="1" Width="100" VerticalAlignment="Center" TextAlignment="Right" Text="{Binding MaxIterations}"></TextBox>
    7575                <TextBlock Margin="2" Grid.Column="2" Grid.Row="0" VerticalAlignment="Center">MaxLen:</TextBlock>
    7676                <TextBox Name="TextBoxMaxLen" Margin="2" Grid.Column="3" Grid.Row="0" Width="100" VerticalAlignment="Center" TextAlignment="Right" Text="{Binding MaxLen}"></TextBox>
    … …  
    9898                        <ListBox Name="ListBoxRuns" Grid.Column="0" Width="100" ItemsSource="{Binding Runs}" SelectionChanged="ListBoxRuns_OnSelectionChanged"/>
    9999                        <TabControl Grid.Column="1">
    100                             <TabItem Header="Chart">
     100                            <TabItem Header="Quality-Chart">
    101101                                <Grid>
    102102                                    <Grid.RowDefinitions>
    … …  
    107107                                        <ColumnDefinition Width="*"></ColumnDefinition>
    108108                                    </Grid.ColumnDefinitions>
    109                                     <d3:ChartPlotter Grid.Column="1" x:Name="ChartPlotter" LegendVisible="False" EnableSmoothPanningForNumericAxes="True">
    110                                         <d3:Header Content="{Binding HeaderString}"/>
    111                                         <d3:VerticalAxisTitle Content="{Binding VerticalAxisString}" />
    112                                         <d3:HorizontalAxisTitle Content="{Binding HorizontalAxisString}"/>
     109                                    <d3:ChartPlotter Grid.Column="1" x:Name="QualityChartPlotter" LegendVisible="False" EnableSmoothPanningForNumericAxes="True">
     110                                        <d3:Header Content="Quality-Chart"/>
     111                                        <d3:VerticalAxisTitle Content="Quality" />
     112                                        <d3:HorizontalAxisTitle Content="Evaluation"/>
     113                                    </d3:ChartPlotter>
     114                                </Grid>
     115                            </TabItem>
     116                            <TabItem Header="SelectionIndicator-Chart">
     117                                <Grid>
     118                                    <Grid.RowDefinitions>
     119                                        <RowDefinition Height="*"></RowDefinition>
     120                                    </Grid.RowDefinitions>
     121                                    <Grid.ColumnDefinitions>
     122                                        <ColumnDefinition Width="Auto"></ColumnDefinition>
     123                                        <ColumnDefinition Width="*"></ColumnDefinition>
     124                                    </Grid.ColumnDefinitions>
     125                                    <d3:ChartPlotter Grid.Column="1" x:Name="SelectionChartPlotter" LegendVisible="False" EnableSmoothPanningForNumericAxes="True">
     126                                        <d3:Header Content="SelectionIndicator-Chart"/>
     127                                        <d3:VerticalAxisTitle Content="SelectionIndicator" />
     128                                        <d3:HorizontalAxisTitle Content="SelectedNodes"/>
    113129                                    </d3:ChartPlotter>
    114130                                </Grid>
    … …  
    204220                    <RowDefinition Height="Auto" />
    205221                    <RowDefinition Height="Auto" />
     222                    <RowDefinition Height="Auto" />
    206223                </Grid.RowDefinitions>
    207224                <Grid.ColumnDefinitions>
    … …  
    215232                <TextBlock Grid.Row="2" Grid.Column="0">Evaluations:</TextBlock>
    216233                <TextBlock Grid.Row="2" Grid.Column="1" Text="{Binding SelectedRun.Evaluations}" Margin="5,0,0,0" HorizontalAlignment="Right"/>
    217                 <TextBlock Grid.Row="3" Grid.Column="0">MaxEvaluations:</TextBlock>
    218                 <TextBlock Grid.Row="3" Grid.Column="1" Text="{Binding SelectedRun.MaxEvaluations}" Margin="5,0,0,0" HorizontalAlignment="Right"/>
     234                <TextBlock Grid.Row="3" Grid.Column="0">MaxIterations:</TextBlock>
     235                <TextBlock Grid.Row="3" Grid.Column="1" Text="{Binding SelectedRun.MaxIterations}" Margin="5,0,0,0" HorizontalAlignment="Right"/>
    219236                <TextBlock Grid.Row="4" Grid.Column="0">BestQuality:</TextBlock>
    220237                <TextBlock Grid.Row="4" Grid.Column="1" Text="{Binding SelectedRun.BestQuality}" Margin="5,0,0,0" HorizontalAlignment="Right"/>
    … …  
    228245                <TextBlock Grid.Row="8" Grid.Column="1" Text="{Binding SelectedRun.BestSolutionFoundAt}" Margin="5,0,0,0" HorizontalAlignment="Right"/>
    229246                <TextBlock Grid.Row="9" Grid.Column="0">BestSolution:</TextBlock>
    230                 <TextBlock Grid.Row="9" Grid.Column="1" Text="{Binding SelectedRun.BestSolution}" TextWrapping="Wrap" Margin="5,0,0,0" HorizontalAlignment="Right" MaxWidth="100"/>
     247                <TextBlock Grid.Row="9" Grid.Column="1" Text="{Binding SelectedRun.BestSolution}" TextWrapping="Wrap" Margin="5,0,0,0" HorizontalAlignment="Right" MaxWidth="100" MaxHeight="50"/>
     248                <TextBlock Grid.Row="10" Grid.Column="0">SelectionIndicator:</TextBlock>
     249                <TextBlock Grid.Row="10" Grid.Column="1" Text="{Binding SelectedRun.CurrentSelectionIndicator.Indicator}" TextWrapping="Wrap" Margin="5,0,0,0" HorizontalAlignment="Right" MaxWidth="100"/>
    231250            </Grid>
    232251        </Grid>

  • branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/MainWindow.xaml.cs

    r12781 r12815  
    11using System.Collections.ObjectModel;
     2using System.Security.AccessControl;
    23using System.Threading;
    34using System.Xml.Serialization;
    … …  
    3233        private EvaluationViewModel vm;
    3334
    34         private DispatcherTimer updateCollectionTimer;
    35 
    3635        private DrawingPage treeDrawingPage;
    3736
    … …  
    4241            this.DataContext = vm = new EvaluationViewModel();
    4342            vm.MaxLen = 100;
    44             vm.MaxEvaluations = 1000000;
     43            vm.MaxIterations = 1000000;
    4544            vm.NrRuns = 10;
    46             vm.VerticalAxisString = "SolutionQuality";
    47             vm.HorizontalAxisString = "Iteration";
    4845        }
    4946
    … …  
    5855        }
    5956
    60         private void DrawLineChart(Run run)
     57        private void DrawQualityChart(Run run)
    6158        {
    6259            List<FoundSolution> solutions = new List<FoundSolution>(run.FoundSolutions);
    … …  
    7673
    7774            graph.StrokeThickness = 2;
    78             graph.AddToPlotter(ChartPlotter);
     75            graph.AddToPlotter(QualityChartPlotter);
     76        }
     77
     78        private void DrawSelectionChart(Run run)
     79        {
     80            List<SelectionIndicator> selectionIndicators = new List<SelectionIndicator>(run.SelectionIndicators);
     81
     82            var ds = new EnumerableDataSource<SelectionIndicator>(selectionIndicators);
     83
     84            ds.SetXMapping(x => x.TotalSelections);
     85            ds.SetYMapping(y => y.Indicator);
     86
     87            LineGraph graph = new LineGraph(ds);
     88
     89            graph.StrokeThickness = 2;
     90            graph.AddToPlotter(SelectionChartPlotter);
    7991        }
    8092
    … …  
    93105            run.StartTime = DateTime.Now;
    94106
    95             run.Solver.Run(run.MaxEvaluations);
     107            run.Solver.Run(run.MaxIterations);
    96108
    97109            run.EndTime = DateTime.Now;
    … …  
    136148        {
    137149            ButtonRun.IsEnabled = true;
    138             TextBoxMaxEvaluations.IsEnabled = true;
     150            TextBoxMaxIterations.IsEnabled = true;
    139151            TextBoxMaxLen.IsEnabled = true;
    140152            TextBoxRuns.IsEnabled = true;
    … …  
    162174                policyInstance = new ThresholdAscentPolicy();
    163175            }
     176            else if (policy == typeof(BoltzmannExplorationPolicy))
     177            {
     178                policyInstance = new BoltzmannExplorationPolicy(2);
     179            }
    164180            else
    165181            {
    … …  
    197213                }
    198214
    199                 Run run = new Run(problem, policyInstance, solver, i + 1, vm.MaxEvaluations, vm.MaxLen);
     215                Run run = new Run(problem, policyInstance, solver, i + 1, vm.MaxIterations, vm.MaxLen);
    200216
    201217                vm.Runs.Add(run);
    … …  
    205221        }
    206222
    207         private void ClearLineChart()
    208         {
    209             ChartPlotter.Children.RemoveAll<LineGraph>();
     223        private void ClearQualityChart()
     224        {
     225            QualityChartPlotter.Children.RemoveAll<LineGraph>();
    210226        }
    211227
    … …  
    215231        }
    216232
     233        private void ClearSelectionChart()
     234        {
     235            SelectionChartPlotter.Children.RemoveAll<LineGraph>();
     236        }
     237
    217238        private void ButtonRun_OnClick(object sender, RoutedEventArgs e)
    218239        {
    219             ClearLineChart();
     240            ClearQualityChart();
    220241            ClearComparisonChart();
     242            ClearSelectionChart();
    221243
    222244            vm.Runs.Clear();
    223245            vm.SelectedRun = null;
    224246            ButtonRun.IsEnabled = false;
    225             TextBoxMaxEvaluations.IsEnabled = false;
     247            TextBoxMaxIterations.IsEnabled = false;
    226248            TextBoxMaxLen.IsEnabled = false;
    227249            TextBoxRuns.IsEnabled = false;
    … …  
    287309                vm.SelectedRun.Solver.FoundNewBestSolution += SelectedRun_FoundNewBestSolution;
    288310
    289                 ClearLineChart();
    290                 DrawLineChart(vm.SelectedRun);
     311                ClearQualityChart();
     312                DrawQualityChart(vm.SelectedRun);
     313
     314                if (vm.SelectedRun.RunState == RunState.Finished)
     315                {
     316                    ClearSelectionChart();
     317                    DrawSelectionChart(vm.SelectedRun);
     318                }
    291319                //DrawTreeChart(vm.SelectedRun);
    292320            }
    … …  
    301329            Dispatcher.BeginInvoke(new Action(() =>
    302330            {
    303                 ClearLineChart();
    304                 DrawLineChart(vm.SelectedRun);
     331                ClearQualityChart();
     332                DrawQualityChart(vm.SelectedRun);
    305333            }));
    306334        }

  • branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/Run.cs

    r12781 r12815  
    11using HeuristicLab.Algorithms.Bandits;
    22using HeuristicLab.Algorithms.GrammaticalOptimization;
     3using HeuristicLab.Algorithms.MonteCarloTreeSearch;
    34using HeuristicLab.Algorithms.MonteCarloTreeSearch.Base;
    45using HeuristicLab.Problems.GrammaticalOptimization;
    … …  
    2627
    2728        public Run(ISymbolicExpressionTreeProblem problem, IBanditPolicy banditPolicy, ISolver solver, int runNumber,
    28             int maxEvaluations, int maxLen)
     29            int maxIterations, int maxLen)
    2930        {
    3031            Problem = problem;
    … …  
    3233            Solver = solver;
    3334            RunNumber = runNumber;
    34             MaxEvaluations = maxEvaluations;
     35            MaxIterations = maxIterations;
    3536            MaxLen = maxLen;
    3637
     38            selectionIndicators = new List<SelectionIndicator>();
    3739            Evaluations = 0;
    3840            BestQuality = double.MinValue;
    3941            RunState = RunState.NotStarted;
    4042            FoundSolutions = new List<FoundSolution>();
     43            CurrentSelectionIndicator = new SelectionIndicator(0, 0);
    4144
    4245            BestKnownQuality = problem.BestKnownQuality(maxLen);
    … …  
    5255                }
    5356            };
     57            if (solver is MonteCarloTreeSearch)
     58            {
     59                MonteCarloTreeSearch mcts = (MonteCarloTreeSearch)solver;
     60                mcts.NodeSelected += mcts_NodeSelected;
     61            }
     62        }
     63
     64        private void mcts_NodeSelected(int goodSelections, int totalSelections)
     65        {
     66            CurrentSelectionIndicator.GoodSelections = goodSelections;
     67            CurrentSelectionIndicator.TotalSelections = totalSelections;
     68            this.OnPropertyChanged("CurrentSelectionIndicator");
     69            //CurrentSelectionIndicator = new SelectionIndicator(goodSelections, totalSelections);
     70            //selectionIndicators.Add(CurrentSelectionIndicator);
     71        }
     72
     73        private List<SelectionIndicator> selectionIndicators;
     74
     75        public List<SelectionIndicator> SelectionIndicators { get { return selectionIndicators; } }
     76
     77
     78        private SelectionIndicator currentSelectionIndicator;
     79
     80        public SelectionIndicator CurrentSelectionIndicator
     81        {
     82            get { return this.currentSelectionIndicator; }
     83            set { this.currentSelectionIndicator = value; this.OnPropertyChanged("CurrentSelectionIndicator"); }
    5484        }
    5585
    … …  
    102132        }
    103133
    104         private int maxEvaluations;
    105 
    106         public int MaxEvaluations
    107         {
    108             get { return this.maxEvaluations; }
    109             set
    110             {
    111                 this.maxEvaluations = value;
    112                 this.OnPropertyChanged("MaxEvaluations");
     134        private int maxIterations;
     135
     136        public int MaxIterations
     137        {
     138            get { return this.maxIterations; }
     139            set
     140            {
     141                this.maxIterations = value;
     142                this.OnPropertyChanged("MaxIterations");
    113143            }
    114144        }
    … …  
    297327        protected void OnPropertyChanged(string propertyName)
    298328        {
    299             if (PropertyChanged != null)
    300                 this.PropertyChanged(this, new PropertyChangedEventArgs(propertyName));
     329            try
     330            {
     331                if (PropertyChanged != null)
     332                    this.PropertyChanged(this, new PropertyChangedEventArgs(propertyName));
     333            }
     334            catch (Exception) { }
    301335        }
    302336

  • branches/HeuristicLab.Problems.GrammaticalOptimization/Evaluation/ViewModel/EvaluationViewModel.cs

    r12781 r12815  
    9898        }
    9999
    100         private int maxEvaluations;
    101 
    102         public int MaxEvaluations
    103         {
    104             get { return this.maxEvaluations; }
    105             set
    106             {
    107                 this.maxEvaluations = value;
    108                 this.OnPropertyChanged("MaxEvaluations");
    109             }
    110         }
    111 
    112         private string headerString;
    113 
    114         public string HeaderString
    115         {
    116             get { return this.headerString; }
    117             set
    118             {
    119                 headerString = value;
    120                 this.OnPropertyChanged("HeaderString");
    121             }
    122         }
    123 
    124         private string verticalAxisString;
    125 
    126         public string VerticalAxisString
    127         {
    128             get { return this.verticalAxisString; }
    129             set
    130             {
    131                 verticalAxisString = value;
    132                 this.OnPropertyChanged("VerticalAxisString");
    133             }
    134         }
    135 
    136         private string horizontalAxisString;
    137 
    138         public string HorizontalAxisString
    139         {
    140             get { return this.horizontalAxisString; }
    141             set
    142             {
    143                 horizontalAxisString = value;
    144                 this.OnPropertyChanged("HorizontalAxisString");
     100        private int maxIterations;
     101
     102        public int MaxIterations
     103        {
     104            get { return this.maxIterations; }
     105            set
     106            {
     107                this.maxIterations = value;
     108                this.OnPropertyChanged("MaxIterations");
    145109            }
    146110        }

  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.GeneticProgramming/StandardGP.cs

    r11972 r12815  
    3131      TournamentGroupSize = 4;
    3232      MutationRate = 0.15;
    33       MaxSolutionSize = 100;
     33      MaxSolutionSize = 30;
    3434      MaxSolutionDepth = 17;
    3535      this.saveAlg = saveAlg;

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

    r12781 r12815  
    11using System;
    22using System.Collections.Generic;
     3using System.Diagnostics;
    34using System.Drawing;
    45using System.Linq;
    … …  
    2122    {
    2223        protected readonly int maxLen;
    23         protected readonly IProblem problem;
     24        protected readonly ISymbolicExpressionTreeProblem problem;
    2425        protected readonly IGrammar grammar;
    2526        protected readonly Random random;
    … …  
    2930        protected bool isPaused = false;
    3031        protected object pauseLock = new object();
    31 
    32         public MonteCarloTreeSearch(IProblem problem, int maxLen, Random random, IBanditPolicy behaviourPolicy,
     32        protected int goodSelections;
     33
     34        public MonteCarloTreeSearch(ISymbolicExpressionTreeProblem problem, int maxLen, Random random, IBanditPolicy behaviourPolicy,
    3335            ISimulation simulationPolicy)
    3436        {
    … …  
    3941            this.behaviourPolicy = behaviourPolicy;
    4042            this.simulation = simulationPolicy;
     43
     44            this.problem.GenerateProblemSolutions(maxLen);
     45        }
     46
     47        public event Action<int, int> NodeSelected;
     48
     49        protected virtual void OnNodeSelectedChanged(int value, int selections)
     50        {
     51            RaiseNodeSelectedChanged(value, selections);
     52        }
     53
     54        private void RaiseNodeSelectedChanged(int value, int selections)
     55        {
     56            var handler = NodeSelected;
     57            if (handler != null) handler(value, selections);
    4158        }
    4259
    … …  
    4865        }
    4966
     67        public int GoodSelections { get { return this.goodSelections; } }
     68
     69        protected void CheckSelection(TreeNode node, int selections)
     70        {
     71            if (problem.IsParentOfProblemSolution(node.phrase, maxLen))
     72            {
     73                goodSelections++;
     74            }
     75
     76            OnNodeSelectedChanged(goodSelections, selections);
     77        }
     78
    5079        public override void Run(int maxIterations)
    5180        {
    5281            Reset();
     82            int selections = 0;
    5383            for (int i = 0; !StopRequested && i < maxIterations; i++)
    5484            {
    … …  
    6797                        currentNode.GetChildActionInfos());
    6898                    currentNode = currentNode.children[currentActionIndex];
     99                    selections++;
     100                    CheckSelection(currentNode, selections);
    69101                }
    70102
    … …  
    77109                        currentNode.children[behaviourPolicy.SelectAction(random, currentNode.GetChildActionInfos())
    78110                            ];
     111                    selections++;
     112                    CheckSelection(currentNode, selections);
    79113                }
    80114                if (currentNode.phrase.Length <= maxLen)
    … …  
    122156        protected void Reset()
    123157        {
     158            goodSelections = 0;
    124159            StopRequested = false;
    125160            bestQuality = 0.0;

  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Algorithms.MonteCarloTreeSearch/MonteCarloTreeSearch_PruneLeaves.cs

    r12781 r12815  
    1 using HeuristicLab.Algorithms.Bandits;
     1using System.Diagnostics;
     2using HeuristicLab.Algorithms.Bandits;
    23using HeuristicLab.Algorithms.MonteCarloTreeSearch.Base;
    34using HeuristicLab.Algorithms.MonteCarloTreeSearch.Simulation;
    … …  
    1112    public class MonteCarloTreeSearch_PruneLeaves : MonteCarloTreeSearch
    1213    {
    13         public MonteCarloTreeSearch_PruneLeaves(IProblem problem, int maxLen, Random random, IBanditPolicy behaviourPolicy,
    14             ISimulation simulationPolicy):base(problem,maxLen,random,behaviourPolicy,simulationPolicy)
     14        public MonteCarloTreeSearch_PruneLeaves(ISymbolicExpressionTreeProblem problem, int maxLen, Random random, IBanditPolicy behaviourPolicy,
     15            ISimulation simulationPolicy)
     16            : base(problem, maxLen, random, behaviourPolicy, simulationPolicy)
    1517        {
    1618        }
    … …  
    1921        {
    2022            Reset();
     23            int selections = 0;
    2124            for (int i = 0; !StopRequested && i < maxIterations; i++)
    2225            {
    … …  
    3538                        currentNode.GetChildActionInfos());
    3639                    currentNode = currentNode.children[currentActionIndex];
     40                    selections++;
     41                    CheckSelection(currentNode, selections);
    3742                }
    3843
    … …  
    5459                            currentNode.children[behaviourPolicy.SelectAction(random, currentNode.GetChildActionInfos())
    5560                                ];
     61                        selections++;
     62                        CheckSelection(currentNode, selections);
    5663                    }
    5764                    else
    … …  
    6976
    7077                    Propagate(currentNode, quality);
    71 
    7278                }
    7379            }

  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization.SymbReg/SymbolicRegressionProblem.cs

    r12099 r12815  
    265265      }
    266266    }
     267
     268
     269    public void GenerateProblemSolutions(int maxLen)
     270    {
     271        throw new NotImplementedException();
     272    }
     273
     274    public bool IsParentOfProblemSolution(string sentence, int maxLen)
     275    {
     276        throw new NotImplementedException();
     277    }
    267278  }
    268279}

  • branches/HeuristicLab.Problems.GrammaticalOptimization/HeuristicLab.Problems.GrammaticalOptimization/Interfaces/ISymbolicExpressionTreeProblem.cs

    r11865 r12815  
    55using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    66
    7 namespace HeuristicLab.Problems.GrammaticalOptimization {
    8   // represents a grammatical optimization problem that can also be used with tree-based GP in HeuristicLab
    9   public interface ISymbolicExpressionTreeProblem : IProblem {
    10     IGrammar TreeBasedGPGrammar { get; } // grammar for HL GP
    11     string ConvertTreeToSentence(ISymbolicExpressionTree tree);
    12   }
     7namespace HeuristicLab.Problems.GrammaticalOptimization
     8{
     9    // represents a grammatical optimization problem that can also be used with tree-based GP in HeuristicLab
     10    public interface ISymbolicExpressionTreeProblem : IProblem
     11    {
     12        IGrammar TreeBasedGPGrammar { get; } // grammar for HL GP
     13        string ConvertTreeToSentence(ISymbolicExpressionTree tree);
     14        void GenerateProblemSolutions(int maxLen);
     15        bool IsParentOfProblemSolution(string sentence, int maxLen);
     16    }
    1317}

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

    r12099 r12815  
    127127      }
    128128    }
     129
     130
     131    public void GenerateProblemSolutions(int maxLen)
     132    {
     133        throw new NotImplementedException();
     134    }
     135
     136    public bool IsParentOfProblemSolution(string sentence, int maxLen)
     137    {
     138        throw new NotImplementedException();
     139    }
    129140  }
    130141}

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

    r12099 r12815  
    177177      return sb.ToString();
    178178    }
     179
     180
     181    public void GenerateProblemSolutions(int maxLen)
     182    {
     183        throw new NotImplementedException();
     184    }
     185
     186    public bool IsParentOfProblemSolution(string sentence, int maxLen)
     187    {
     188        throw new NotImplementedException();
     189    }
    179190  }
    180191}

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

    r12099 r12815  
    6565      return sb.ToString();
    6666    }
     67    public void GenerateProblemSolutions(int maxLen)
     68    {
     69        throw new NotImplementedException();
     70    }
     71    public bool IsParentOfProblemSolution(string sentence, int maxLen)
     72    {
     73        throw new NotImplementedException();
     74    }
    6775  }
    6876}

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

    r12099 r12815  
    106106      return sb.ToString();
    107107    }
     108
     109    public void GenerateProblemSolutions(int maxLen)
     110    {
     111        throw new NotImplementedException();
     112    }
     113
     114    public bool IsParentOfProblemSolution(string sentence, int maxLen)
     115    {
     116        throw new NotImplementedException();
     117    }
     118
    108119  }
    109120}

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

    r12099 r12815  
    5656      return sb.ToString();
    5757    }
     58    public void GenerateProblemSolutions(int maxLen)
     59    {
     60        throw new NotImplementedException();
     61    }
     62
     63    public bool IsParentOfProblemSolution(string sentence, int maxLen)
     64    {
     65        throw new NotImplementedException();
     66    }
    5867  }
    5968}

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

    r12099 r12815  
    6060      return sb.ToString();
    6161    }
     62
     63
     64    public void GenerateProblemSolutions(int maxLen)
     65    {
     66        throw new NotImplementedException();
     67    }
     68
     69    public bool IsParentOfProblemSolution(string sentence, int maxLen)
     70    {
     71        throw new NotImplementedException();
     72    }
    6273  }
    6374}

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

    r12099 r12815  
    161161      return sb.ToString();
    162162    }
     163
     164
     165    public void GenerateProblemSolutions(int maxLen)
     166    {
     167        throw new NotImplementedException();
     168    }
     169
     170    public bool IsParentOfProblemSolution(string sentence, int maxLen)
     171    {
     172        throw new NotImplementedException();
     173    }
    163174  }
    164175}

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

    r12099 r12815  
    114114      return sb.ToString();
    115115    }
     116
     117
     118    public void GenerateProblemSolutions(int maxLen)
     119    {
     120        throw new NotImplementedException();
     121    }
     122
     123    public bool IsParentOfProblemSolution(string sentence, int maxLen)
     124    {
     125        throw new NotImplementedException();
     126    }
    116127  }
    117128}

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

    r12099 r12815  
    33using System.Diagnostics;
    44using System.Linq;
     5using System.Security.Authentication.ExtendedProtection.Configuration;
    56using System.Text;
    67using System.Text.RegularExpressions;
    78using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    89
    9 namespace HeuristicLab.Problems.GrammaticalOptimization {
    10   // counts the number of times a symbol occurs in a sentence
    11   public class RoyalSymbolProblem : ISymbolicExpressionTreeProblem {
    12     private const string grammarString = @"
     10namespace HeuristicLab.Problems.GrammaticalOptimization
     11{
     12    // counts the number of times a symbol occurs in a sentence
     13    public class RoyalSymbolProblem : ISymbolicExpressionTreeProblem
     14    {
     15        private const string grammarString = @"
    1316G(S):
    1417S -> a | aS | b | bS
    1518";
    1619
    17     private const string hlGrammarString = @"
     20        private const string hlGrammarString = @"
    1821G(S):
    1922S -> a | b | SS
    2023";
    2124
    22     // Obj(s \in L(G(S))) = Anzahl "a"-Symbole in s
     25        // Obj(s \in L(G(S))) = Anzahl "a"-Symbole in s
    2326
    24     private readonly IGrammar grammar;
    25     public string Name { get { return "RoyalSymbol"; } }
    26     public RoyalSymbolProblem() {
    27       this.grammar = new Grammar(grammarString);
    28       this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
    29       //TODO: allow configuration of the number of symbols
     27        private readonly IGrammar grammar;
     28        public string Name { get { return "RoyalSymbol"; } }
     29        public RoyalSymbolProblem()
     30        {
     31            this.grammar = new Grammar(grammarString);
     32            this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
     33            //TODO: allow configuration of the number of symbols
     34        }
     35
     36        public double BestKnownQuality(int maxLen)
     37        {
     38            return maxLen;
     39        }
     40
     41        public IGrammar Grammar
     42        {
     43            get { return grammar; }
     44        }
     45
     46        private Regex regex = new Regex("a"); // count the number of "a"s
     47        public double Evaluate(string sentence)
     48        {
     49            // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
     50            Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
     51            return regex.Matches(sentence).Count;
     52        }
     53        public string CanonicalRepresentation(string phrase)
     54        {
     55            return phrase;
     56        }
     57
     58        public IEnumerable<Feature> GetFeatures(string phrase)
     59        {
     60            throw new NotImplementedException();
     61        }
     62
     63        public IGrammar TreeBasedGPGrammar { get; private set; }
     64        public string ConvertTreeToSentence(ISymbolicExpressionTree tree)
     65        {
     66            var sb = new StringBuilder();
     67            foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix())
     68            {
     69                if (s.Symbol.Name == "S") continue;
     70                sb.Append(s.Symbol.Name);
     71            }
     72            return sb.ToString();
     73        }
     74
     75        private string solution = string.Empty;
     76
     77        public void GenerateProblemSolutions(int maxLen)
     78        {
     79            StringBuilder sb = new StringBuilder();
     80            for (int i = 0; i < maxLen; i++)
     81            {
     82                sb.Append('a');
     83            }
     84            solution = sb.ToString();
     85        }
     86
     87        private readonly Regex isParentSolution = new Regex("a+S");
     88        public bool IsParentOfProblemSolution(string sentence, int maxLen)
     89        {
     90            if (sentence.Length < maxLen)
     91            {
     92                return isParentSolution.IsMatch(sentence);
     93            }
     94            else
     95            {
     96                return solution == sentence;
     97            }
     98        }
    3099    }
    31 
    32     public double BestKnownQuality(int maxLen) {
    33       return maxLen;
    34     }
    35 
    36     public IGrammar Grammar {
    37       get { return grammar; }
    38     }
    39 
    40     private Regex regex = new Regex("a"); // count the number of "a"s
    41     public double Evaluate(string sentence) {
    42       // sentence must contain only terminal symbols, we are not checking if the sentence is syntactically valid here because it would be too slow!
    43       Debug.Assert(sentence.Any(c => grammar.IsTerminal(c)));
    44       return regex.Matches(sentence).Count;
    45     }
    46     public string CanonicalRepresentation(string phrase) {
    47       return phrase;
    48     }
    49 
    50     public IEnumerable<Feature> GetFeatures(string phrase) {
    51       throw new NotImplementedException();
    52     }
    53 
    54     public IGrammar TreeBasedGPGrammar { get; private set; }
    55     public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
    56       var sb = new StringBuilder();
    57       foreach (var s in tree.Root.GetSubtree(0).GetSubtree(0).IterateNodesPrefix()) {
    58         if (s.Symbol.Name == "S") continue;
    59         sb.Append(s.Symbol.Name);
    60       }
    61       return sb.ToString();
    62     }
    63   }
    64100}

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

    r12099 r12815  
    273273      return sb.ToString();
    274274    }
     275    public void GenerateProblemSolutions(int maxLen)
     276    {
     277        throw new NotImplementedException();
     278    }
     279
     280    public bool IsParentOfProblemSolution(string sentence, int maxLen)
     281    {
     282        throw new NotImplementedException();
     283    }
    275284  }
    276285}

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

    r12762 r12815  
    99using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    1010
    11 namespace HeuristicLab.Problems.GrammaticalOptimization {
    12   public class SantaFeAntProblem : ISymbolicExpressionTreeProblem {
    13     private const string grammarString = @"
     11namespace HeuristicLab.Problems.GrammaticalOptimization
     12{
     13    public class SantaFeAntProblem : ISymbolicExpressionTreeProblem
     14    {
     15        private const string grammarString = @"
    1416G(A):
    15 A -> l | r | m | ?(A)(A) | lA | rA | mA
     17A -> l | r | m | ?(A)(A) | ?(A)(A)A | lA | rA | mA
    1618";
    17     // for tree-based GP in HL we need a different grammar for the same language
    18     // A = Ant, P = Prog2 and Prog3, I = IfFoodAhead
    19     private const string hlGrammarString = @"
     19        // for tree-based GP in HL we need a different grammar for the same language
     20        // A = Ant, P = Prog2 and Prog3, I = IfFoodAhead
     21        private const string hlGrammarString = @"
    2022    G(A):
    2123    A -> l | r | m | P | I
    … …  
    2527
    2628
    27     // original koza grammar
    28     // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
    29     //
    30     // here we use a modified grammar which has only one syntax tree for each sentence
    31 
    32 
    33     private readonly IGrammar grammar;
    34     public string Name { get { return "SantaFeAnt"; } }
    35 
    36     public SantaFeAntProblem() {
    37       this.grammar = new Grammar(grammarString);
    38       this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
     29        // original koza grammar
     30        // Ant -> left | right | move | if-food-ahead Ant Ant | Ant Ant | Ant Ant Ant
     31        //
     32        // here we use a modified grammar which has only one syntax tree for each sentence
     33
     34
     35        private readonly IGrammar grammar;
     36        public string Name { get { return "SantaFeAnt"; } }
     37
     38        public SantaFeAntProblem()
     39        {
     40            this.grammar = new Grammar(grammarString);
     41            this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
     42        }
     43
     44        public double BestKnownQuality(int maxLen)
     45        {
     46            // for now only an upper bound is returned, ideally all food pellets are discovered
     47            return 89;
     48        }
     49
     50        public IGrammar Grammar
     51        {
     52            get { return grammar; }
     53        }
     54
     55        public double Evaluate(string sentence)
     56        {
     57            var ant = new Ant();
     58            int p = 0;
     59            Run(ant, sentence, ref p);
     60            return ant.FoodEaten;
     61        }
     62
     63        private static void Run(Ant ant, string sentence, ref int p, bool stopAfterFirst = false)
     64        {
     65            while (!ant.Done())
     66            {
     67                if (p >= sentence.Length)
     68                {
     69                    if (stopAfterFirst) return;
     70                    p = 0; // restart
     71                }
     72                switch (sentence[p])
     73                {
     74                    case 'r':
     75                        {
     76                            ant.TurnRight();
     77                            p++;
     78                            break;
     79                        }
     80                    case 'l':
     81                        {
     82                            ant.TurnLeft();
     83                            p++;
     84                            break;
     85                        }
     86                    case 'm':
     87                        {
     88                            ant.Move();
     89                            p++;
     90                            break;
     91                        }
     92                    case '?':
     93                        {
     94                            p++; // skip p
     95                            if (ant.IsFoodAhead())
     96                            {
     97                                if (sentence[p] != '(') throw new ArgumentException();
     98                                p++;
     99                                Run(ant, sentence, ref p);      // it cannot happen that we run over the the end of the sentence here
     100                                if (ant.Done()) return;
     101                                if (sentence[p] != '(') throw new ArgumentException();
     102                                p++;
     103                                Skip(sentence, ref p);
     104                            }
     105                            else
     106                            {
     107                                if (sentence[p] != '(') throw new ArgumentException();
     108                                p++;
     109                                Skip(sentence, ref p);
     110                                if (sentence[p] != '(') throw new ArgumentException();
     111                                p++;
     112                                Run(ant, sentence, ref p);    // it cannot happen that we run over the the end of the sentence here
     113                            }
     114                            break;
     115                        }
     116                    case '.':
     117                        {
     118                            // nop
     119                            p++;
     120                            ant.Nop();
     121                            break;
     122                        }
     123                    case ')':
     124                        {
     125                            p++; // skip
     126                            return;     // caller must continue processing
     127                        }
     128                    default:
     129                        {
     130                            throw new ArgumentException();
     131                        }
     132                }
     133            }
     134        }
     135
     136        private static void Skip(string sentence, ref int p)
     137        {
     138            int openCount = 1;
     139            while (openCount > 0)
     140            {
     141                if (sentence[p] == '(') openCount++;
     142                else if (sentence[p] == ')') openCount--;
     143                p++;
     144            }
     145        }
     146
     147        public string CanonicalRepresentation(string phrase)
     148        {
     149            //phrase = phrase.Replace("A", ".");
     150            var sb = new StringBuilder(phrase);
     151            string canonicalPhrase = phrase;
     152            string oldPhrase;
     153            do
     154            {
     155                oldPhrase = canonicalPhrase;
     156                sb.Replace("ll", "rr").Replace("rl", "").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l").Replace("?()()", "");
     157                //sb.Replace("?(m)(m)", "?()()m").Replace("?(l)(l)", "?()()l").Replace("?(r)(r)", "?()()r");
     158                canonicalPhrase = sb.ToString();
     159            } while (canonicalPhrase != oldPhrase);
     160            return canonicalPhrase;
     161        }
     162
     163        public IEnumerable<Feature> GetFeatures(string phrase)
     164        {
     165            phrase = CanonicalRepresentation(phrase);
     166            var isTerminal = grammar.IsTerminal(phrase);
     167
     168            yield return new Feature(isTerminal + ToString(), 1.0);
     169
     170            yield return new Feature("$" + (phrase.Length > 0 ? phrase[0] : ' '), 1.0);
     171            if (!isTerminal)
     172            {
     173                for (int i = 4; i < phrase.Length; i++)
     174                {
     175                    if (!grammar.IsTerminal(phrase[i]))
     176                    {
     177                        yield return new Feature(phrase[i - 4].ToString() + phrase[i - 3].ToString() + phrase[i - 2] + phrase[i - 1], 1.0);
     178                        break;
     179                    }
     180                }
     181            }
     182
     183            yield return new Feature(phrase, 1.0);
     184        }
     185
     186        public IGrammar TreeBasedGPGrammar { get; private set; }
     187        public string ConvertTreeToSentence(ISymbolicExpressionTree tree)
     188        {
     189            var sb = new StringBuilder();
     190            ConvertTreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
     191            return sb.ToString();
     192        }
     193        private void ConvertTreeToSentence(ISymbolicExpressionTreeNode node, StringBuilder sb)
     194        {
     195            if (node.SubtreeCount == 0)
     196            {
     197                // terminal
     198                sb.Append(node.Symbol.Name);
     199            }
     200            else if (node.Symbol.Name == "I")
     201            {
     202                Debug.Assert(node.SubtreeCount == 2);
     203                sb.Append("?(");
     204                ConvertTreeToSentence(node.GetSubtree(0), sb);
     205                sb.Append(")(");
     206                ConvertTreeToSentence(node.GetSubtree(1), sb);
     207                sb.Append(")");
     208            }
     209            else
     210            {
     211                foreach (var subTree in node.Subtrees) { ConvertTreeToSentence(subTree, sb); }
     212            }
     213        }
     214
     215        private string[] solutions;
     216
     217        public void GenerateProblemSolutions(int maxLen)
     218        {
     219            if (maxLen > 17)
     220            {
     221                throw new NotImplementedException();
     222            }
     223            solutions = new string[12];
     224            solutions[0] = "?(m)(ll?(m)(r))mr";
     225            solutions[1] = "?(m)(rr?(m)(l))ml";
     226            solutions[2] = "r?(m)(ll?(m)(r))m";
     227            solutions[3] = "l?(m)(rr?(m)(l))m";
     228            solutions[4] = "mr?(m)(ll?(m)(r))";
     229            solutions[5] = "ml?(m)(rr?(m)(l))";
     230            solutions[6] = "?(m)(ll?(m)(l))ml";
     231            solutions[7] = "?(m)(rr?(m)(r))mr";
     232            solutions[8] = "l?(m)(ll?(m)(l))m";
     233            solutions[9] = "r?(m)(rr?(m)(r))m";
     234            solutions[10] = "ml?(m)(ll?(m)(l))";
     235            solutions[11] = "mr?(m)(rr?(m)(r))";
     236
     237            // A
     238            // rA
     239            // lA
     240            // mA
     241            // mlA
     242            // mrA
     243            // ?(A)(A)A
     244            // mr?(m)(ll?(A)(A))
     245            // ?(A)(A)?(A)(A)
     246        }
     247
     248        private readonly List<string> validStarts3 = new List<string> { "A", "rA", "lA", "mA", "mlA", "mrA" };
     249
     250
     251        public bool IsParentOfProblemSolution(string sentence, int maxLen)
     252        {
     253            //INFO: only works with maxlen 17!!
     254
     255            // eliminate wrong parents..
     256            if (sentence.Length < 17 && !sentence.Contains('A'))
     257            {
     258                return false;
     259            }
     260            if (sentence.Length > 3 && !sentence.Contains('?'))
     261            {
     262                return false;
     263            }
     264            if (sentence.Length <= 3)
     265            {
     266                return validStarts3.Contains(sentence);
     267            }
     268            if (sentence.Contains("m?"))
     269            {
     270                return false;
     271            }
     272
     273            if (sentence.Length <= 17 && sentence.Contains('A'))
     274            {
     275                // check front part of solutions..
     276                // contains A, contains ?(x)(x), length > 3
     277                int index = sentence.IndexOf('?');
     278                if (index > 2) return false;
     279
     280                int firstCloseBracket = sentence.IndexOf(')');
     281                // only one item in bracket
     282                if ((firstCloseBracket - index) != 3) return false;
     283                // must be m or A
     284                if (sentence[firstCloseBracket - 1] != 'm' && sentence[firstCloseBracket - 1] != 'A') return false;
     285
     286                // check back and front part of solutions..
     287                int lastCloseBracket = sentence.LastIndexOf(')');
     288                // before first ? and after last ) either 1 left one right, or only two left (also A), or only two right (also A)
     289                int diff;
     290                if (index == 0)
     291                {
     292                    // must end with mr, ml, mA, A
     293                    diff = sentence.Length - 1 - lastCloseBracket;
     294                    if (diff == 0 || diff > 2) return false;
     295                    if (diff == 1 && sentence[sentence.Length - 1] != 'A') return false;
     296                    if (diff == 2 && (sentence[sentence.Length - 2] != 'm' || sentence[sentence.Length - 1] == 'm'))
     297                        return false;
     298                }
     299                else if (index == 1 && (sentence[0] == 'm' || (sentence[sentence.Length - 1] != 'm' && sentence[sentence.Length - 1] != 'A'))) return false;
     300                else if (index == 2)
     301                {
     302                    // must start with ml, mr, mA
     303                    // must end with )
     304                    if (sentence[sentence.Length - 1] != ')') return false;
     305                    if (sentence[0] != 'm' || sentence[1] == 'm') return false;
     306                }
     307
     308                // check middle part of solutions ..(ll?(m)(l))..
     309                int index2 = sentence.IndexOf('?', index + 1);
     310                if (index2 == -1)
     311                {
     312                    // no second ? so far..
     313                    // allowed within second (..): A, lA, llA, rA, rrA
     314                    int lastOpenBracket = sentence.LastIndexOf('(', lastCloseBracket);
     315                    diff = lastCloseBracket - lastOpenBracket;
     316                    if (diff > 4) return false;
     317                    // last item must be A
     318                    if (sentence[lastCloseBracket - 1] != 'A') return false;
     319                    // first item must not be m
     320                    if (sentence[lastOpenBracket + 1] == 'm') return false;
     321                    // ll or rr
     322                    if (diff == 4 && sentence[lastOpenBracket + 1] != sentence[lastOpenBracket + 2]) return false;
     323                }
     324                else
     325                {
     326                    // second ? there..
     327                    // ?(x)(..?(x)(x))
     328                    int secondLastCloseBracket = sentence.LastIndexOf(')', lastCloseBracket - 1);
     329                    // has to end with '))'
     330                    if (lastCloseBracket - secondLastCloseBracket != 1) return false;
     331                    // only one item within second brackets
     332                    if (sentence[secondLastCloseBracket - 2] != '(') return false;
     333                    // the one item can be A, l or r
     334                    if (sentence[secondLastCloseBracket - 1] == 'm') return false;
     335                    // only one item in first brackets
     336                    if (sentence[index2 + 3] != ')') return false;
     337                    // only m or A allowed
     338                    if (sentence[index2 + 2] == 'l' || sentence[index2 + 2] == 'r') return false;
     339                    // ll or rr before second ? must already be there..
     340                    if (sentence[index2 - 1] != 'l' && sentence[index2 - 1] != 'r') return false;
     341                    if (sentence[index2 - 1] != sentence[index2 - 2]) return false;
     342                }
     343            }
     344            else
     345            {
     346                // has to be solution or false..
     347                return solutions.Any(solution => solution == sentence);
     348            }
     349
     350            return true;
     351        }
    39352    }
    40353
    41     public double BestKnownQuality(int maxLen) {
    42       // for now only an upper bound is returned, ideally all food pellets are discovered
    43       return 89;
     354    public class Ant
     355    {
     356        private int maxSteps = 600;
     357        public int MaxSteps { get { return maxSteps; } set { maxSteps = value; } }
     358        public enum HeadingEnum { North, East, South, West };
     359        public int FoodEaten { get; private set; }
     360        private readonly char[][] world = new char[32][];
     361        private int posX;
     362        private int posY;
     363        private int steps;
     364        private HeadingEnum heading;
     365        public int PosX { get { return posX; } }
     366        public int PosY { get { return posY; } }
     367        public HeadingEnum Heading { get { return heading; } }
     368        private bool recordTrail = false;
     369        private StringBuilder trailBuilder;
     370
     371        public string Trail
     372        {
     373            get
     374            {
     375                if (!recordTrail) throw new NotSupportedException();
     376                else return trailBuilder.ToString() + heading; // add final heading as state
     377            }
     378        }
     379
     380        public Ant(bool recordTrail = false)
     381        {
     382            world[00] = " ###                            ".ToCharArray();
     383            world[01] = "   #                            ".ToCharArray();
     384            world[02] = "   #                    .###..  ".ToCharArray();
     385            world[03] = "   #                    #    #  ".ToCharArray();
     386            world[04] = "   #                    #    #  ".ToCharArray();
     387            world[05] = "   ####.#####       .##..    .  ".ToCharArray();
     388            world[06] = "            #       .        #  ".ToCharArray();
     389            world[07] = "            #       #        .  ".ToCharArray();
     390            world[08] = "            #       #        .  ".ToCharArray();
     391            world[09] = "            #       #        #  ".ToCharArray();
     392            world[10] = "            .       #        .  ".ToCharArray();
     393            world[11] = "            #       .        .  ".ToCharArray();
     394            world[12] = "            #       .        #  ".ToCharArray();
     395            world[13] = "            #       #        .  ".ToCharArray();
     396            world[14] = "            #       #  ...###.  ".ToCharArray();
     397            world[15] = "            .   .#...  #        ".ToCharArray();
     398            world[16] = "            .   .      .        ".ToCharArray();
     399            world[17] = "            #   .      .        ".ToCharArray();
     400            world[18] = "            #   #      .#...    ".ToCharArray();
     401            world[19] = "            #   #          #    ".ToCharArray();
     402            world[20] = "            #   #          .    ".ToCharArray();
     403            world[21] = "            #   #          .    ".ToCharArray();
     404            world[22] = "            #   .      ...#.    ".ToCharArray();
     405            world[23] = "            #   .      #        ".ToCharArray();
     406            world[24] = " ..##..#####.   #               ".ToCharArray();
     407            world[25] = " #              #               ".ToCharArray();
     408            world[26] = " #              #               ".ToCharArray();
     409            world[27] = " #     .#######..               ".ToCharArray();
     410            world[28] = " #     #                        ".ToCharArray();
     411            world[29] = " .     #                        ".ToCharArray();
     412            world[30] = " .####..                        ".ToCharArray();
     413            world[31] = "                                ".ToCharArray();
     414
     415            posX = 0;
     416            posY = 0;
     417            heading = HeadingEnum.East;
     418            FoodEaten = 0;
     419            steps = 0;
     420
     421            this.recordTrail = recordTrail;
     422            if (this.recordTrail) trailBuilder = new StringBuilder();
     423        }
     424
     425        public bool Done()
     426        {
     427            return steps > maxSteps;
     428        }
     429
     430        public void TurnRight()
     431        {
     432            if (steps <= maxSteps)
     433            {
     434                steps++;
     435                if (heading == HeadingEnum.West) heading = HeadingEnum.North;
     436                else heading++;
     437            }
     438        }
     439
     440        public void TurnLeft()
     441        {
     442            if (steps <= maxSteps)
     443            {
     444                steps++;
     445                if (heading == HeadingEnum.North) heading = HeadingEnum.West;
     446                else heading--;
     447            }
     448        }
     449
     450        public void Move()
     451        {
     452            if (steps <= maxSteps)
     453            {
     454                steps++;
     455                MoveInternal(ref posX, ref posY);
     456                if (world[posY][posX] == '#')
     457                {
     458                    FoodEaten++;
     459                    world[posY][posX] = '.';
     460                }
     461                if (recordTrail) trailBuilder.Append("m" + posX + "x" + posY); // record position change
     462            }
     463        }
     464
     465        public void Nop()
     466        {
     467            // wait one time step
     468            if (steps <= maxSteps)
     469            {
     470                steps++;
     471            }
     472        }
     473
     474        private void MoveInternal(ref int posX, ref int posY)
     475        {
     476            switch (heading)
     477            {
     478                case HeadingEnum.North:
     479                    posY = (posY + 31) % 32;
     480                    break;
     481                case HeadingEnum.East:
     482                    posX = (posX + 1) % 32;
     483                    break;
     484                case HeadingEnum.South:
     485                    posY = (posY + 1) % 32;
     486                    break;
     487                case HeadingEnum.West:
     488                    posX = (posX + 31) % 32;
     489                    break;
     490            }
     491        }
     492
     493        public bool IsFoodAhead()
     494        {
     495            int nextPosX = posX;
     496            int nextPosY = posY;
     497            MoveInternal(ref nextPosX, ref nextPosY);
     498
     499            if (recordTrail) trailBuilder.Append("?" + nextPosX + "x" + nextPosY); // record check
     500
     501            return world[nextPosY][nextPosX] == '#';
     502        }
    44503    }
    45 
    46     public IGrammar Grammar {
    47       get { return grammar; }
    48     }
    49 
    50     public double Evaluate(string sentence) {
    51       var ant = new Ant();
    52       int p = 0;
    53       Run(ant, sentence, ref p);
    54       return ant.FoodEaten;
    55     }
    56 
    57     private static void Run(Ant ant, string sentence, ref int p, bool stopAfterFirst = false) {
    58       while (!ant.Done()) {
    59         if (p >= sentence.Length) {
    60           if (stopAfterFirst) return;
    61           p = 0; // restart
    62         }
    63         switch (sentence[p]) {
    64           case 'r': {
    65               ant.TurnRight();
    66               p++;
    67               break;
    68             }
    69           case 'l': {
    70               ant.TurnLeft();
    71               p++;
    72               break;
    73             }
    74           case 'm': {
    75               ant.Move();
    76               p++;
    77               break;
    78             }
    79           case '?': {
    80               p++; // skip p
    81               if (ant.IsFoodAhead()) {
    82                 if (sentence[p] != '(') throw new ArgumentException();
    83                 p++;
    84                 Run(ant, sentence, ref p);      // it cannot happen that we run over the the end of the sentence here
    85                 if (ant.Done()) return;
    86                 if (sentence[p] != '(') throw new ArgumentException();
    87                 p++;
    88                 Skip(sentence, ref p);
    89               } else {
    90                 if (sentence[p] != '(') throw new ArgumentException();
    91                 p++;
    92                 Skip(sentence, ref p);
    93                 if (sentence[p] != '(') throw new ArgumentException();
    94                 p++;
    95                 Run(ant, sentence, ref p);    // it cannot happen that we run over the the end of the sentence here
    96               }
    97               break;
    98             }
    99           case '.': {
    100               // nop
    101               p++;
    102               ant.Nop();
    103               break;
    104             }
    105           case ')': {
    106               p++; // skip
    107               return;     // caller must continue processing
    108             }
    109           default: {
    110               throw new ArgumentException();
    111             }
    112         }
    113       }
    114     }
    115 
    116     private static void Skip(string sentence, ref int p) {
    117       int openCount = 1;
    118       while (openCount > 0) {
    119         if (sentence[p] == '(') openCount++;
    120         else if (sentence[p] == ')') openCount--;
    121         p++;
    122       }
    123     }
    124 
    125     public string CanonicalRepresentation(string phrase) {
    126       //phrase = phrase.Replace("A", ".");
    127       var sb = new StringBuilder(phrase);
    128       string canonicalPhrase = phrase;
    129       string oldPhrase;
    130       do {
    131         oldPhrase = canonicalPhrase;
    132         sb.Replace("ll", "rr").Replace("rl", "").Replace("lr", "").Replace("lll", "r").Replace("rrr", "l").Replace("?()()", "");
    133         //sb.Replace("?(m)(m)", "?()()m").Replace("?(l)(l)", "?()()l").Replace("?(r)(r)", "?()()r");
    134         canonicalPhrase = sb.ToString();
    135       } while (canonicalPhrase != oldPhrase);
    136       return canonicalPhrase;
    137     }
    138 
    139     public IEnumerable<Feature> GetFeatures(string phrase) {
    140       phrase = CanonicalRepresentation(phrase);
    141       var isTerminal = grammar.IsTerminal(phrase);
    142 
    143       yield return new Feature(isTerminal + ToString(), 1.0);
    144      
    145       yield return new Feature("$" + (phrase.Length > 0 ? phrase[0] : ' '), 1.0);
    146       if (!isTerminal) {
    147         for (int i = 4; i < phrase.Length; i++) {
    148           if (!grammar.IsTerminal(phrase[i])) {
    149             yield return new Feature(phrase[i - 4].ToString() + phrase[i - 3].ToString() + phrase[i - 2] + phrase[i - 1], 1.0);
    150             break;
    151           }
    152         }
    153       }
    154    
    155       yield return new Feature(phrase, 1.0);
    156     }
    157 
    158     public IGrammar TreeBasedGPGrammar { get; private set; }
    159     public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
    160       var sb = new StringBuilder();
    161       ConvertTreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
    162       return sb.ToString();
    163     }
    164     private void ConvertTreeToSentence(ISymbolicExpressionTreeNode node, StringBuilder sb) {
    165       if (node.SubtreeCount == 0) {
    166         // terminal
    167         sb.Append(node.Symbol.Name);
    168       } else if (node.Symbol.Name == "I") {
    169         Debug.Assert(node.SubtreeCount == 2);
    170         sb.Append("?(");
    171         ConvertTreeToSentence(node.GetSubtree(0), sb);
    172         sb.Append(")(");
    173         ConvertTreeToSentence(node.GetSubtree(1), sb);
    174         sb.Append(")");
    175       } else {
    176         foreach (var subTree in node.Subtrees) { ConvertTreeToSentence(subTree, sb); }
    177       }
    178     }
    179   }
    180 
    181   public class Ant {
    182     private int maxSteps = 600;
    183     public int MaxSteps { get { return maxSteps; } set { maxSteps = value; } }
    184     public enum HeadingEnum { North, East, South, West };
    185     public int FoodEaten { get; private set; }
    186     private readonly char[][] world = new char[32][];
    187     private int posX;
    188     private int posY;
    189     private int steps;
    190     private HeadingEnum heading;
    191     public int PosX { get { return posX; } }
    192     public int PosY { get { return posY; } }
    193     public HeadingEnum Heading { get { return heading; } }
    194     private bool recordTrail = false;
    195     private StringBuilder trailBuilder;
    196 
    197     public string Trail {
    198       get {
    199         if (!recordTrail) throw new NotSupportedException();
    200         else return trailBuilder.ToString() + heading; // add final heading as state
    201       }
    202     }
    203 
    204     public Ant(bool recordTrail = false) {
    205       world[00] = " ###                            ".ToCharArray();
    206       world[01] = "   #                            ".ToCharArray();
    207       world[02] = "   #                    .###..  ".ToCharArray();
    208       world[03] = "   #                    #    #  ".ToCharArray();
    209       world[04] = "   #                    #    #  ".ToCharArray();
    210       world[05] = "   ####.#####       .##..    .  ".ToCharArray();
    211       world[06] = "            #       .        #  ".ToCharArray();
    212       world[07] = "            #       #        .  ".ToCharArray();
    213       world[08] = "            #       #        .  ".ToCharArray();
    214       world[09] = "            #       #        #  ".ToCharArray();
    215       world[10] = "            .       #        .  ".ToCharArray();
    216       world[11] = "            #       .        .  ".ToCharArray();
    217       world[12] = "            #       .        #  ".ToCharArray();
    218       world[13] = "            #       #        .  ".ToCharArray();
    219       world[14] = "            #       #  ...###.  ".ToCharArray();
    220       world[15] = "            .   .#...  #        ".ToCharArray();
    221       world[16] = "            .   .      .        ".ToCharArray();
    222       world[17] = "            #   .      .        ".ToCharArray();
    223       world[18] = "            #   #      .#...    ".ToCharArray();
    224       world[19] = "            #   #          #    ".ToCharArray();
    225       world[20] = "            #   #          .    ".ToCharArray();
    226       world[21] = "            #   #          .    ".ToCharArray();
    227       world[22] = "            #   .      ...#.    ".ToCharArray();
    228       world[23] = "            #   .      #        ".ToCharArray();
    229       world[24] = " ..##..#####.   #               ".ToCharArray();
    230       world[25] = " #              #               ".ToCharArray();
    231       world[26] = " #              #               ".ToCharArray();
    232       world[27] = " #     .#######..               ".ToCharArray();
    233       world[28] = " #     #                        ".ToCharArray();
    234       world[29] = " .     #                        ".ToCharArray();
    235       world[30] = " .####..                        ".ToCharArray();
    236       world[31] = "                                ".ToCharArray();
    237 
    238       posX = 0;
    239       posY = 0;
    240       heading = HeadingEnum.East;
    241       FoodEaten = 0;
    242       steps = 0;
    243 
    244       this.recordTrail = recordTrail;
    245       if (this.recordTrail) trailBuilder = new StringBuilder();
    246     }
    247 
    248     public bool Done() {
    249       return steps > maxSteps;
    250     }
    251 
    252     public void TurnRight() {
    253       if (steps <= maxSteps) {
    254         steps++;
    255         if (heading == HeadingEnum.West) heading = HeadingEnum.North;
    256         else heading++;
    257       }
    258     }
    259 
    260     public void TurnLeft() {
    261       if (steps <= maxSteps) {
    262         steps++;
    263         if (heading == HeadingEnum.North) heading = HeadingEnum.West;
    264         else heading--;
    265       }
    266     }
    267 
    268     public void Move() {
    269       if (steps <= maxSteps) {
    270         steps++;
    271         MoveInternal(ref posX, ref posY);
    272         if (world[posY][posX] == '#') {
    273           FoodEaten++;
    274           world[posY][posX] = '.';
    275         }
    276         if (recordTrail) trailBuilder.Append("m" + posX + "x" + posY); // record position change
    277       }
    278     }
    279 
    280     public void Nop() {
    281       // wait one time step
    282       if (steps <= maxSteps) {
    283         steps++;
    284       }
    285     }
    286 
    287     private void MoveInternal(ref int posX, ref int posY) {
    288       switch (heading) {
    289         case HeadingEnum.North:
    290           posY = (posY + 31) % 32;
    291           break;
    292         case HeadingEnum.East:
    293           posX = (posX + 1) % 32;
    294           break;
    295         case HeadingEnum.South:
    296           posY = (posY + 1) % 32;
    297           break;
    298         case HeadingEnum.West:
    299           posX = (posX + 31) % 32;
    300           break;
    301       }
    302     }
    303 
    304     public bool IsFoodAhead() {
    305       int nextPosX = posX;
    306       int nextPosY = posY;
    307       MoveInternal(ref nextPosX, ref nextPosY);
    308 
    309       if (recordTrail) trailBuilder.Append("?" + nextPosX + "x" + nextPosY); // record check
    310 
    311       return world[nextPosY][nextPosX] == '#';
    312     }
    313   }
    314504}

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

    r12099 r12815  
    1212using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    1313
    14 namespace HeuristicLab.Problems.GrammaticalOptimization {
    15   public class SymbolicRegressionPoly10Problem : ISymbolicExpressionTreeProblem {
    16     //    private const string grammarString = @"
    17     //    G(E):
    18     //    E -> V | V+E | V-E | V*E | (E)
    19     //    V -> a .. j
    20     //    ";
    21     private const string grammarString = @"
     14namespace HeuristicLab.Problems.GrammaticalOptimization
     15{
     16    public class SymbolicRegressionPoly10Problem : ISymbolicExpressionTreeProblem
     17    {
     18        //    private const string grammarString = @"
     19        //    G(E):
     20        //    E -> V | V+E | V-E | V*E | (E)
     21        //    V -> a .. j
     22        //    ";
     23        private const string grammarString = @"
    2224    G(E):
    2325    E -> a | b | c | d | e | f | g | h | i | j | a+E | b+E | c+E | d+E | e+E | f+E | g+E | h+E | i+E | j+E | a*E | b*E | c*E | d*E | e*E | f*E | g*E | h*E | i*E | j*E
    2426    ";
    2527
    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 = @"
     28        // for tree-based GP in HL we need a different grammar for the same language
     29        // E = expr, S = sum, P = product
     30        private const string hlGrammarString = @"
    2931    G(E):
    3032    E -> S | P | a | b | c | d | e | f | g | h | i | j
    … …  
    3234    P -> EE | EEE
    3335    ";
    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     public IGrammar TreeBasedGPGrammar { get; private set; }
    50 
    51     private readonly IGrammar grammar;
    52 
    53     private readonly int N;
    54     private readonly double[][] x;
    55     private readonly double[] y;
    56     public string Name { get { return "SymbolicRegressionPoly10"; } }
    57 
    58     public SymbolicRegressionPoly10Problem() {
    59       this.grammar = new Grammar(grammarString);
    60       this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
    61 
    62       this.N = 500;
    63       this.x = new double[N][];
    64       this.y = new double[N];
    65 
    66       GenerateData();
     36        // mininmal tree for the optimal expr (40 nodes)
     37        // E S
     38        //     E S
     39        //         E P
     40        //           E a E b
     41        //         E P
     42        //           E c E d
     43        //         E P
     44        //           E e E f
     45        //     E S
     46        //         E P
     47        //           E a E g E i
     48        //         E P
     49        //           E c E f E j
     50
     51        public IGrammar TreeBasedGPGrammar { get; private set; }
     52
     53        private readonly IGrammar grammar;
     54
     55        private readonly int N;
     56        private readonly double[][] x;
     57        private readonly double[] y;
     58        public string Name { get { return "SymbolicRegressionPoly10"; } }
     59
     60        public SymbolicRegressionPoly10Problem()
     61        {
     62            this.grammar = new Grammar(grammarString);
     63            this.TreeBasedGPGrammar = new Grammar(hlGrammarString);
     64
     65            this.N = 500;
     66            this.x = new double[N][];
     67            this.y = new double[N];
     68
     69            GenerateData();
     70        }
     71
     72        private void GenerateData()
     73        {
     74            // generate data with fixed seed to make sure that data is always the same
     75            var rand = new Random(31415);
     76            for (int i = 0; i < N; i++)
     77            {
     78                x[i] = new double[10];
     79                for (int j = 0; j < 10; j++)
     80                {
     81                    x[i][j] = rand.NextDouble() * 2 - 1;
     82                }
     83                // poly-10 no noise
     84                /* a*b + c*d + e*f + a*g*i + c*f*j */
     85                y[i] = x[i][0] * x[i][1] +
     86                       x[i][2] * x[i][3] +
     87                       x[i][4] * x[i][5] +
     88                       x[i][0] * x[i][6] * x[i][8] +
     89                       x[i][2] * x[i][5] * x[i][9];
     90            }
     91        }
     92
     93        public double BestKnownQuality(int maxLen)
     94        {
     95            // for now only an upper bound is returned, ideally we have an R² of 1.0
     96            // the optimal R² can only be reached for sentences of at least 23 symbols
     97            return 1.0;
     98        }
     99
     100        public IGrammar Grammar
     101        {
     102            get { return grammar; }
     103        }
     104
     105        public double Evaluate(string sentence)
     106        {
     107            var interpreter = new ExpressionInterpreter();
     108            return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])).ToArray());
     109        }
     110
     111
     112        // most-recently-used caching (with limited capacity) for canonical representations
     113        MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
     114        // right now only + and * is supported
     115        public string CanonicalRepresentation(string phrase)
     116        {
     117            string canonicalPhrase;
     118            if (!canonicalPhraseCache.TryGetValue(phrase, out canonicalPhrase))
     119            {
     120                var terms = phrase.Split('+');
     121                var canonicalTerms = new SortedSet<string>();
     122                // only the last term might contain a NT-symbol. make sure this term is added at the end
     123                for (int i = 0; i < terms.Length - 1; i++)
     124                {
     125                    canonicalTerms.Add(CanonicalTerm(terms[i]));
     126                }
     127
     128                var sb = new StringBuilder(phrase.Length);
     129                foreach (var t in canonicalTerms)
     130                    sb.Append(t).Append('+');
     131
     132                sb.Append(CanonicalTerm(terms[terms.Length - 1]));
     133                canonicalPhrase = sb.ToString();
     134                canonicalPhraseCache.Add(phrase, canonicalPhrase);
     135            }
     136            return canonicalPhrase;
     137        }
     138
     139        // cache the canonical form of terms for performance reasons
     140        private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
     141        private string CanonicalTerm(string term)
     142        {
     143            string canonicalTerm;
     144            if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm))
     145            {
     146                // add
     147                var chars = term.ToCharArray();
     148                Array.Sort(chars);
     149                var sb = new StringBuilder(chars.Length);
     150                // we want to have the up-case characters last
     151                for (int i = chars.Length - 1; i > 0; i--)
     152                {
     153                    if (chars[i] != '*')
     154                    {
     155                        sb.Append(chars[i]);
     156                        if (chars[i - 1] != '*') sb.Append('*');
     157                    }
     158                }
     159                if (chars[0] != '*') sb.Append(chars[0]); // last term
     160                canonicalTerm = sb.ToString();
     161                canonicalTermDictionary.Add(term, canonicalTerm);
     162            }
     163            return canonicalTerm;
     164        }
     165
     166        // splits the phrase into terms and creates (sparse) term-occurrance features
     167        public IEnumerable<Feature> GetFeatures(string phrase)
     168        {
     169            var canonicalTerms = new HashSet<string>();
     170            foreach (string t in phrase.Split('+'))
     171            {
     172                canonicalTerms.Add(CanonicalTerm(t));
     173            }
     174            return canonicalTerms.Select(entry => new Feature(entry, 1.0))
     175              .Concat(new Feature[] { new Feature(CanonicalRepresentation(phrase), 1.0) });
     176        }
     177
     178        public string ConvertTreeToSentence(ISymbolicExpressionTree tree)
     179        {
     180            var sb = new StringBuilder();
     181
     182            TreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
     183
     184            return sb.ToString();
     185        }
     186
     187        private void TreeToSentence(ISymbolicExpressionTreeNode treeNode, StringBuilder sb)
     188        {
     189            if (treeNode.SubtreeCount == 0)
     190            {
     191                // terminal
     192                sb.Append(treeNode.Symbol.Name);
     193            }
     194            else
     195            {
     196                string op = string.Empty;
     197                switch (treeNode.Symbol.Name)
     198                {
     199                    case "S": op = "+"; break;
     200                    case "P": op = "*"; break;
     201                    default:
     202                        {
     203                            Debug.Assert(treeNode.SubtreeCount == 1);
     204                            break;
     205                        }
     206                }
     207                // nonterminal
     208                if (op == "+") sb.Append("(");
     209                TreeToSentence(treeNode.Subtrees.First(), sb);
     210                foreach (var subTree in treeNode.Subtrees.Skip(1))
     211                {
     212                    sb.Append(op);
     213                    TreeToSentence(subTree, sb);
     214                }
     215                if (op == "+") sb.Append(")");
     216            }
     217        }
     218
     219        public void GenerateProblemSolutions(int maxLen)
     220        {
     221        }
     222
     223        private readonly List<string> canonicaSolutionTerms3 = new List<string> { "b*a", "d*c", "f*e" };
     224        private readonly List<string> canonicaSolutionTerms5 = new List<string> { "i*g*a", "j*f*c" };
     225
     226        public bool IsParentOfProblemSolution(string sentence, int maxLen)
     227        {
     228            /* a*b + c*d + e*f + a*g*i + c*f*j */
     229
     230            bool containsE = sentence.EndsWith("E");
     231
     232            if (!containsE && sentence.Length != 23 || sentence.Length > 23)
     233            {
     234                return false;
     235            }
     236
     237            // now: contains E or has solution length..
     238            string[] terms = sentence.Split('+');
     239
     240            bool[] terms3 = new bool[3];
     241            bool[] terms5 = new bool[2];
     242
     243            // run through addends without E
     244            for (int i = 0; i < terms.Length - 1; i++)
     245            {
     246                string term = terms[i];
     247                if (term.Length == 3)
     248                {
     249                    string canonicalTerm = CanonicalTerm(term);
     250                    int index = canonicaSolutionTerms3.IndexOf(canonicalTerm);
     251                    if (index < 0 || terms3[index])
     252                    {
     253                        // term is not part of solution or twice in solution
     254                        return false;
     255                    }
     256                    terms3[index] = true;
     257                }
     258                else if (term.Length == 5)
     259                {
     260                    string canonicalTerm = CanonicalTerm(term);
     261                    int index = canonicaSolutionTerms5.IndexOf(canonicalTerm);
     262                    if (index < 0 || terms5[index])
     263                    {
     264                        // term is not part of solution or twice in solution
     265                        return false;
     266                    }
     267                    terms5[index] = true;
     268                }
     269                else
     270                {
     271                    return false;
     272                }
     273            }
     274
     275            string lastTerm = terms[terms.Length - 1];
     276            if (containsE)
     277            {
     278                if (lastTerm.Length == 1)
     279                {
     280                    // is E
     281                    return true;
     282                }
     283                string withoutE = lastTerm.Substring(0, lastTerm.Length - 2);
     284                if (lastTerm.Length == 3)
     285                {
     286                    for (int i = 0; i < 3; i++)
     287                    {
     288                        if (!terms3[i] && canonicaSolutionTerms3[i].Contains(withoutE))
     289                        {
     290                            return true;
     291                        }
     292                    }
     293
     294                }
     295                else if (lastTerm.Length == 5)
     296                {
     297                    for (int i = 0; i < 2; i++)
     298                    {
     299                        if (!terms5[i] && canonicaSolutionTerms5[i].Contains(withoutE))
     300                        {
     301                            return true;
     302                        }
     303                    }
     304                }
     305            }
     306            else
     307            {
     308                // check if it is already correct solution
     309                if (lastTerm.Length == 3)
     310                {
     311                    for (int i = 0; i < 3; i++)
     312                    {
     313                        if (!terms3[i] && canonicaSolutionTerms3[i] == lastTerm)
     314                        {
     315                            return true;
     316                        }
     317                    }
     318
     319                }
     320                else if (lastTerm.Length == 5)
     321                {
     322                    for (int i = 0; i < 2; i++)
     323                    {
     324                        if (!terms5[i] && canonicaSolutionTerms5[i] == lastTerm)
     325                        {
     326                            return true;
     327                        }
     328                    }
     329                }
     330            }
     331
     332            return false;
     333        }
    67334    }
    68 
    69     private void GenerateData() {
    70       // generate data with fixed seed to make sure that data is always the same
    71       var rand = new Random(31415);
    72       for (int i = 0; i < N; i++) {
    73         x[i] = new double[10];
    74         for (int j = 0; j < 10; j++) {
    75           x[i][j] = rand.NextDouble() * 2 - 1;
    76         }
    77         // poly-10 no noise
    78         /* a*b + c*d + e*f + a*g*i + c*f*j */
    79         y[i] = x[i][0] * x[i][1] +
    80                x[i][2] * x[i][3] +
    81                x[i][4] * x[i][5] +
    82                x[i][0] * x[i][6] * x[i][8] +
    83                x[i][2] * x[i][5] * x[i][9];
    84       }
    85     }
    86 
    87     public double BestKnownQuality(int maxLen) {
    88       // for now only an upper bound is returned, ideally we have an R² of 1.0
    89       // the optimal R² can only be reached for sentences of at least 23 symbols
    90       return 1.0;
    91     }
    92 
    93     public IGrammar Grammar {
    94       get { return grammar; }
    95     }
    96 
    97     public double Evaluate(string sentence) {
    98       var interpreter = new ExpressionInterpreter();
    99       return HeuristicLab.Common.Extensions.RSq(y, Enumerable.Range(0, N).Select(i => interpreter.Interpret(sentence, x[i])).ToArray());
    100     }
    101 
    102 
    103     // most-recently-used caching (with limited capacity) for canonical representations
    104     MostRecentlyUsedCache<string, string> canonicalPhraseCache = new MostRecentlyUsedCache<string, string>(100000);
    105     // right now only + and * is supported
    106     public string CanonicalRepresentation(string phrase) {
    107       string canonicalPhrase;
    108       if (!canonicalPhraseCache.TryGetValue(phrase, out canonicalPhrase)) {
    109         var terms = phrase.Split('+');
    110         var canonicalTerms = new SortedSet<string>();
    111         // only the last term might contain a NT-symbol. make sure this term is added at the end
    112         for (int i = 0; i < terms.Length - 1; i++) {
    113           canonicalTerms.Add(CanonicalTerm(terms[i]));
    114         }
    115 
    116         var sb = new StringBuilder(phrase.Length);
    117         foreach (var t in canonicalTerms)
    118           sb.Append(t).Append('+');
    119 
    120         sb.Append(CanonicalTerm(terms[terms.Length - 1]));
    121         canonicalPhrase = sb.ToString();
    122         canonicalPhraseCache.Add(phrase, canonicalPhrase);
    123       }
    124       return canonicalPhrase;
    125     }
    126 
    127     // cache the canonical form of terms for performance reasons
    128     private Dictionary<string, string> canonicalTermDictionary = new Dictionary<string, string>();
    129     private string CanonicalTerm(string term) {
    130       string canonicalTerm;
    131       if (!canonicalTermDictionary.TryGetValue(term, out canonicalTerm)) {
    132         // add
    133         var chars = term.ToCharArray();
    134         Array.Sort(chars);
    135         var sb = new StringBuilder(chars.Length);
    136         // we want to have the up-case characters last
    137         for (int i = chars.Length - 1; i > 0; i--) {
    138           if (chars[i] != '*') {
    139             sb.Append(chars[i]);
    140             if (chars[i - 1] != '*') sb.Append('*');
    141           }
    142         }
    143         if (chars[0] != '*') sb.Append(chars[0]); // last term
    144         canonicalTerm = sb.ToString();
    145         canonicalTermDictionary.Add(term, canonicalTerm);
    146       }
    147       return canonicalTerm;
    148     }
    149 
    150     // splits the phrase into terms and creates (sparse) term-occurrance features
    151     public IEnumerable<Feature> GetFeatures(string phrase) {
    152       var canonicalTerms = new HashSet<string>();
    153       foreach (string t in phrase.Split('+')) {
    154         canonicalTerms.Add(CanonicalTerm(t));
    155       }
    156       return canonicalTerms.Select(entry => new Feature(entry, 1.0))
    157         .Concat(new Feature[] { new Feature(CanonicalRepresentation(phrase), 1.0) });
    158     }
    159 
    160     public string ConvertTreeToSentence(ISymbolicExpressionTree tree) {
    161       var sb = new StringBuilder();
    162 
    163       TreeToSentence(tree.Root.GetSubtree(0).GetSubtree(0), sb);
    164 
    165       return sb.ToString();
    166     }
    167 
    168     private void TreeToSentence(ISymbolicExpressionTreeNode treeNode, StringBuilder sb) {
    169       if (treeNode.SubtreeCount == 0) {
    170         // terminal
    171         sb.Append(treeNode.Symbol.Name);
    172       } else {
    173         string op = string.Empty;
    174         switch (treeNode.Symbol.Name) {
    175           case "S": op = "+"; break;
    176           case "P": op = "*"; break;
    177           default: {
    178               Debug.Assert(treeNode.SubtreeCount == 1);
    179               break;
    180             }
    181         }
    182         // nonterminal
    183         if (op == "+") sb.Append("(");
    184         TreeToSentence(treeNode.Subtrees.First(), sb);
    185         foreach (var subTree in treeNode.Subtrees.Skip(1)) {
    186           sb.Append(op);
    187           TreeToSentence(subTree, sb);
    188         }
    189         if (op == "+") sb.Append(")");
    190       }
    191     }
    192   }
    193335}
Note: See TracChangeset for help on using the changeset viewer.