Free cookie consent management tool by TermsFeed Policy Generator

source: branches/HeuristicLab.Algorithms.IteratedSentenceConstruction/HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction/3.3/IteratedSymbolicExpressionConstruction.cs @ 12909

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

#2471: initial import of basic algorithm and framework (state value approximation not yet supported)

File size: 10.0 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2015 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 * and the BEACON Center for the Study of Evolution in Action.
5 *
6 * This file is part of HeuristicLab.
7 *
8 * HeuristicLab is free software: you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation, either version 3 of the License, or
11 * (at your option) any later version.
12 *
13 * HeuristicLab is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16 * GNU General Public License for more details.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
20 */
21#endregion
22
23using System;
24using System.Collections.Generic;
25using System.Threading;
26using HeuristicLab.Analysis;
27using HeuristicLab.Common;
28using HeuristicLab.Core;
29using HeuristicLab.Data;
30using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
31using HeuristicLab.Optimization;
32using HeuristicLab.Parameters;
33using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
34using HeuristicLab.PluginInfrastructure;
35using HeuristicLab.Random;
36
37namespace HeuristicLab.Algorithms.IteratedSymbolicExpressionConstruction {
38  [Item("Iterated Symbolic Expression Construction", "Generates symbolic expression trees iteratively.")]
39  [StorableClass]
40  [Creatable(CreatableAttribute.Categories.SingleSolutionAlgorithms, Priority = 400)]
41  public class IteratedSymbolicExpressionConstruction : BasicAlgorithm {
42    public override Type ProblemType {
43      get { return typeof(SymbolicExpressionTreeProblem); }
44    }
45    public new SymbolicExpressionTreeProblem Problem {
46      get { return (SymbolicExpressionTreeProblem)base.Problem; }
47      set { base.Problem = value; }
48    }
49
50    #region ParameterNames
51    private const string MaximumEvaluationsParameterName = "Maximum Evaluations";
52    private const string SeedParameterName = "Seed";
53    private const string SetSeedRandomlyParameterName = "SetSeedRandomly";
54    private const string ResultUpdateIntervalParameterName = "ResultUpdateInterval";
55    private const string PolicyParameterName = "Policy";
56    #endregion
57
58    #region ParameterProperties
59    public IFixedValueParameter<IntValue> MaximumEvaluationsParameter {
60      get { return (IFixedValueParameter<IntValue>)Parameters[MaximumEvaluationsParameterName]; }
61    }
62    public IFixedValueParameter<IntValue> SeedParameter {
63      get { return (IFixedValueParameter<IntValue>)Parameters[SeedParameterName]; }
64    }
65    public IFixedValueParameter<BoolValue> SetSeedRandomlyParameter {
66      get { return (IFixedValueParameter<BoolValue>)Parameters[SetSeedRandomlyParameterName]; }
67    }
68    public IFixedValueParameter<IntValue> ResultUpdateIntervalParameter {
69      get { return (IFixedValueParameter<IntValue>)Parameters[ResultUpdateIntervalParameterName]; }
70    }
71    public IValueParameter<ISymbolicExpressionConstructionPolicy> PolicyParameter {
72      get {
73        return (IValueParameter<ISymbolicExpressionConstructionPolicy>)Parameters[PolicyParameterName];
74      }
75    }
76    #endregion
77
78    #region Properties
79    public int MaximumEvaluations {
80      get { return MaximumEvaluationsParameter.Value.Value; }
81      set { MaximumEvaluationsParameter.Value.Value = value; }
82    }
83    public int Seed {
84      get { return SeedParameter.Value.Value; }
85      set { SeedParameter.Value.Value = value; }
86    }
87    public bool SetSeedRandomly {
88      get { return SetSeedRandomlyParameter.Value.Value; }
89      set { SetSeedRandomlyParameter.Value.Value = value; }
90    }
91    public int ResultUpdateInterval {
92      get { return ResultUpdateIntervalParameter.Value.Value; }
93      set { ResultUpdateIntervalParameter.Value.Value = value; }
94    }
95    #endregion
96
97    #region ResultsProperties
98    public double ResultsBestQuality {
99      get { return ((DoubleValue)Results["Best Quality"].Value).Value; }
100    }
101    public int ResultsBestFoundOnEvaluation {
102      get { return ((IntValue)Results["Evaluation Best Solution Was Found"].Value).Value; }
103    }
104    public int ResultsEvaluations {
105      get { return ((IntValue)Results["Evaluations"].Value).Value; }
106    }
107    public DataTable ResultsQualities {
108      get { return ((DataTable)Results["Qualities"].Value); }
109    }
110    public DataRow ResultsQualitiesBest {
111      get { return ResultsQualities.Rows["Best Quality"]; }
112    }
113    public DataRow ResultQualitiesAverage {
114      get { return ResultsQualities.Rows["Average Quality"]; }
115    }
116    #endregion
117
118    private readonly IRandom random = new MersenneTwister();
119
120
121    [StorableConstructor]
122    protected IteratedSymbolicExpressionConstruction(bool deserializing) : base(deserializing) { }
123
124    protected IteratedSymbolicExpressionConstruction(IteratedSymbolicExpressionConstruction original, Cloner cloner)
125      : base(original, cloner) {
126    }
127
128    public override IDeepCloneable Clone(Cloner cloner) {
129      return new IteratedSymbolicExpressionConstruction(this, cloner);
130    }
131
132    public IteratedSymbolicExpressionConstruction() {
133      Parameters.Add(new FixedValueParameter<IntValue>(MaximumEvaluationsParameterName, "", new IntValue(500000)));
134      Parameters.Add(new FixedValueParameter<IntValue>(ResultUpdateIntervalParameterName, "The update interval for the result values in number of evaluations", new IntValue(100)));
135      Parameters.Add(new FixedValueParameter<IntValue>(SeedParameterName, "The random seed used to initialize the new pseudo random number generator.", new IntValue(0)));
136      Parameters.Add(new FixedValueParameter<BoolValue>(SetSeedRandomlyParameterName, "True if the random seed should be set to a random value, otherwise false.", new BoolValue
137(true)));
138      Parameters.Add(new ValueParameter<ISymbolicExpressionConstructionPolicy>(PolicyParameterName, "The policy to use for exploring the search tree", new UcbSymbolicExpressionConstructionPolicy()));
139    }
140
141    protected override void Run(CancellationToken cancellationToken) {
142      // TODO minimization problems
143      if (!Problem.Maximization) throw new NotSupportedException("Minimization problems are not supported");
144
145      // Set up the algorithm
146      if (SetSeedRandomly) Seed = new System.Random().Next();
147      random.Reset(Seed);
148
149      //var policy = new RandomSymbolicExpressionConstructionPolicy(Problem, random);
150      //var policy = new EpsGreedySymbolicExpressionConstructionPolicy<string>(Problem, random, new TabularMaxQualityFunction<string>(new DefaultStateFunction()));
151      //var policy = new EpsGreedySymbolicExpressionConstructionPolicy(Problem, random, new TabularAvgQualityFunction<string>(new DefaultStateFunction()));
152      //var policy = new EpsGreedySymbolicExpressionConstructionPolicy(Problem, random, new TabularMaxQualityFunction<string>(new ParentChildStateFunction()));
153      //var policy = new EpsGreedySymbolicExpressionConstructionPolicy(Problem, random, new TabularAvgQualityFunction<string>(new ParentChildStateFunction()));
154      //var policy = new UcbSymbolicExpressionConstructionPolicy<string>(Problem, random, new TabularMaxQualityFunction<string>(new DefaultStateFunction()));
155      //var policy = new UcbWithStateAggregationSymbolicExpressionConstructionPolicy(Problem, random, 40);
156
157      var policy = PolicyParameter.Value;
158      policy.Initialize(Problem, random);
159
160      IntValue evaluations = new IntValue(0);
161      DoubleValue bestQuality = new DoubleValue(Double.NegativeInfinity);
162      IntValue bestFoundOnEvaluation = new IntValue(0);
163
164      // Set up the results display
165      Results.Add(new Result("Evaluations", evaluations));
166      Results.Add(new Result("Best Quality", bestQuality));
167      Results.Add(new Result("Evaluation Best Solution Was Found", bestFoundOnEvaluation));
168
169      var table = new DataTable("Qualities");
170      var bestQualityRow = new DataRow("Best Quality");
171      table.Rows.Add(bestQualityRow);
172
173      var currentQualityRow = new DataRow("Average Quality");
174      currentQualityRow.VisualProperties.LineStyle = DataRowVisualProperties.DataRowLineStyle.Dot;
175      table.Rows.Add(currentQualityRow);
176
177      Results.Add(new Result("Qualities", table));
178
179      // for problem-specific analyzer
180      ISymbolicExpressionTree[] solutions = new ISymbolicExpressionTree[1];
181      double[] qualities = new double[1];
182
183      // the algorithm
184      // Loop until iteration limit reached or canceled.
185      int evals = 0;
186      double sumQuality = 0; // for average quality calculation
187      int resultUpdateInterval = ResultUpdateInterval;
188      while (evals < MaximumEvaluations) {
189        double quality = double.NaN;
190        ISymbolicExpressionTree tree = null;
191        IEnumerable<Tuple<object, int>> actionSequence;
192        tree = policy.Sample(out actionSequence);
193        quality = Problem.Evaluate(tree, random);
194        evals++;
195        sumQuality += quality;
196
197        policy.Update(actionSequence, quality);
198
199        // update statistics results in regular update intervals
200        if ((evals - 1) % resultUpdateInterval == resultUpdateInterval - 1) {
201          evaluations.Value = evals;
202          bestQualityRow.Values.Add(bestQuality.Value);
203          currentQualityRow.Values.Add(sumQuality / (double)resultUpdateInterval);
204          sumQuality = 0;
205        }
206
207        // update best solution results whenever a new better solution is found
208        if (Problem.IsBetter(quality, bestQuality.Value)) {
209          bestQuality.Value = quality;
210          bestFoundOnEvaluation.Value = evals;
211
212          // for problem-specific analyzer
213          solutions[0] = tree;
214          qualities[0] = quality;
215        }
216
217        // run problem-specific analyzer in each iteration
218        Problem.Analyze(solutions, qualities, Results, random);
219
220        cancellationToken.ThrowIfCancellationRequested();
221      }
222    }
223
224  }
225}
Note: See TracBrowser for help on using the repository browser.