Free cookie consent management tool by TermsFeed Policy Generator

source: branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Problem/PushProblem.cs @ 14746

Last change on this file since 14746 was 14746, checked in by pkimmesw, 7 years ago

#2665 PooledPushProgram reduces memory usage and increases performance

File size: 18.5 KB
Line 
1using System;
2
3namespace HeuristicLab.Problems.ProgramSynthesis.Push.Problem {
4  using System.Collections.Generic;
5  using System.Linq;
6  using Common;
7  using Configuration;
8  using Core;
9  using Encodings.IntegerVectorEncoding;
10  using Expressions;
11
12  using HeuristicLab.BenchmarkSuite;
13  using HeuristicLab.Data;
14  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Pool;
15
16  using Instances;
17  using Interpreter;
18  using Optimization;
19  using Parameters;
20  using Persistence.Default.CompositeSerializers.Storable;
21  using Stack;
22
23  [StorableClass]
24  [Creatable(CreatableAttribute.Categories.GeneticProgrammingProblems, Priority = 180)]
25  [Item("Push Problem", "")]
26  public class PushProblem : SingleObjectiveBasicProblem<IntegerVectorEncoding>, IProblemInstanceConsumer<IBenchmarkSuiteDataDescriptor> {
27    [Storable]
28    private readonly PushConfiguration config;
29    private PushInterpreterPool pool;
30    private ManagedPoolProvider<PushProgram> pushProgramPoolProvider;
31
32    public PushProblem() {
33      config = new PushConfiguration();
34      pool = new PushInterpreterPool(config);
35
36      pushProgramPoolProvider = new ManagedPoolProvider<PushProgram>(1024);
37      pushProgramPoolProvider.InitDummyPartition(() => new PushProgram());
38
39      InitEvents();
40      InitParameters();
41      Instructions = config;
42    }
43
44    [StorableConstructor]
45    public PushProblem(bool deserializing)
46      : base(deserializing) {
47    }
48
49    public PushProblem(PushProblem original, Cloner cloner)
50      : base(original, cloner) {
51      config = cloner.Clone(original.config);
52      pool = new PushInterpreterPool(config);
53
54      Instructions = config;
55
56      this.InitEvents();
57    }
58
59    [StorableHook(HookType.AfterDeserialization)]
60    // ReSharper disable once UnusedMember.Local
61    private void AfterDeserialization() {
62      pool = new PushInterpreterPool(config);
63      Instructions = config;
64
65      pushProgramPoolProvider = new ManagedPoolProvider<PushProgram>(1024);
66      pushProgramPoolProvider.InitDummyPartition(() => new PushProgram());
67
68      InitEvents();
69    }
70
71    private void InitEvents() {
72      config.EnabledExpressionsChanged += EnabledExpressionsChanged;
73    }
74
75    private void EnabledExpressionsChanged(object sender, EnabledExpressionsChangedEventArgs e) {
76      this.Encoding.Bounds[0, 1] = config.EnabledExpressions.Count - 1;
77      this.Encoding.BoundsParameter.Value[0, 1] = config.EnabledExpressions.Count - 1;
78    }
79
80    #region Parameters
81
82    private const string EvalPushLimitParameterName = "EvalPushLimit";
83    private const string EvalPushLimitParameterDescription = "This is the maximum allowed number of \"executions\" in a single top-level call to the interpreter. The execution of a single Push instruction counts as one execution, as does the processing of a single literal, as does the descent into one layer of parentheses (that is, the processing of the \"(\" counts as one execution).";
84    private const string MaxProgramLengthParameterName = "MaxProgramLength";
85    private const string MaxProgramLengthParameterDescription = "This is the maximum size of an item on the CODE stack, expressed as a number of points. A point is an instruction, a literal, or a pair of parentheses.";
86    private const string TopLevelPushCodeParameterName = "TopLevelPushCode";
87    private const string TopLevelPushCodeParameterDescription = "When TRUE (which is the default), code passed to the top level of the interpreter will be pushed onto the CODE stack prior to execution.";
88    private const string TopLevelPopCodeParameterName = "TopLevelPopCode";
89    private const string TopLevelPopCodeParameterDescription = "When TRUE, the CODE stack will be popped at the end of top level calls to the interpreter. The default is FALSE.";
90    private const string InstructionsParameterName = "Instructions";
91    private const string InstructionsParameterDescription = "Enables/Disables Instructions";
92    private const string DataParameterName = "Data";
93    private const string DataParameterDescription = "Program Synthesis";
94    private const string MinRandomIntegerParameterName = "MinRandomInteger";
95    private const string MinRandomIntegerParameterDescription = "The minimum INTEGER that will be produced as an ephemeral random INTEGER constant or from a call to INTEGER.RAND.";
96    private const string MaxRandomIntegerParameterName = "MaxRandomInteger";
97    private const string MaxRandomIntegerParameterDescription = "The maximum INTEGER that will be produced as an ephemeral random INTEGER constant or from a call to INTEGER.RAND.";
98    private const string MinRandomFloatParameterName = "MinRandomFloat";
99    private const string MinRandomFloatParameterDescription = "The minimum FLOAT that will be produced as an ephemeral random FLOAT constant or from a call to FLOAT.RAND.";
100    private const string MaxRandomFloatParameterName = "MaxRandomFloat";
101    private const string MaxRandomFloatParameterDescription = "The maximum FLOAT that will be produced as an ephemeral random FLOAT constant or from a call to FLOAT.RAND.";
102    private const string NewErcNameProbabilityParameterName = "NewErcNameProbability";
103    private const string NewErcNameProbabilityParameterDescription = "The probability that the selection of the ephemeral random NAME constant for inclusion in randomly generated code will produce a new name.";
104    private const string ErcProbabilityParameterName = "ErcProbability";
105    private const string ErcProbabilityParameterDescription = "The probability that the selection of a epheral random literal constant for inclusion in randomly generated code will produce a new literal.";
106    private const string MaxPointsInRandomInstructionParameterName = "MaxPointsInRandomInstruction";
107    private const string MaxPointsInRandomInstructionParameterDescription = "MaxPointsInRandomInstruction";
108    private const string DataBoundsParameterName = "DataBounds";
109
110    private void InitParameters() {
111      var bounds = new IntMatrix(1, 3, new[] { "Training Start", "Training End | Test Start", "Test End" });
112      bounds.ItemChanged += (s, e) => {
113        if (this.DataDescriptor == null)
114          return;
115
116        var max = this.DataDescriptor.OriginalTestCount + this.DataDescriptor.OriginalTrainingCount - 1;
117        bounds[0, 0] = Math.Min(Math.Max(bounds[0, 0], 0), max);
118        bounds[0, 2] = Math.Max(Math.Min(bounds[0, 2], max), 0);
119        bounds[0, 1] = Math.Min(Math.Max(bounds[0, 0], bounds[0, 1]), bounds[0, 2]);
120      };
121
122      Parameters.Add(new FixedValueParameter<IntMatrix>(
123        DataBoundsParameterName,
124        bounds));
125
126      Parameters.Add(new FixedValueParameter<IntValue>(
127        EvalPushLimitParameterName,
128        EvalPushLimitParameterDescription,
129        new IntValue(config.EvalPushLimit)));
130
131      Parameters.Add(new FixedValueParameter<IntValue>(
132        MaxProgramLengthParameterName,
133        MaxProgramLengthParameterDescription,
134        new IntValue(config.MaxPointsInProgram)));
135
136      Parameters.Add(new FixedValueParameter<BoolValue>(
137        TopLevelPushCodeParameterName,
138        TopLevelPushCodeParameterDescription,
139        new BoolValue(config.TopLevelPushCode)) { Hidden = true });
140
141      Parameters.Add(new FixedValueParameter<BoolValue>(
142        TopLevelPopCodeParameterName,
143        TopLevelPopCodeParameterDescription,
144        new BoolValue(config.TopLevelPopCode)) { Hidden = true });
145
146      Parameters.Add(new ValueParameter<IEnabledExpressionsConfiguration>(
147        InstructionsParameterName,
148        InstructionsParameterDescription));
149
150      Parameters.Add(new FixedValueParameter<IntValue>(
151        MinRandomIntegerParameterName,
152        MinRandomIntegerParameterDescription,
153        new IntValue(config.MinRandomInteger)) { Hidden = true });
154
155      Parameters.Add(new FixedValueParameter<IntValue>(
156        MaxRandomIntegerParameterName,
157        MaxRandomIntegerParameterDescription,
158        new IntValue(config.MaxRandomInteger)) { Hidden = true });
159
160      Parameters.Add(new FixedValueParameter<DoubleValue>(
161        MinRandomFloatParameterName,
162        MinRandomFloatParameterDescription,
163        new DoubleValue(config.MinRandomFloat)) { Hidden = true });
164
165      Parameters.Add(new FixedValueParameter<DoubleValue>(
166        MaxRandomFloatParameterName,
167        MaxRandomFloatParameterDescription,
168        new DoubleValue(config.MaxRandomFloat)) { Hidden = true });
169
170      Parameters.Add(new FixedValueParameter<PercentValue>(
171        NewErcNameProbabilityParameterName,
172        NewErcNameProbabilityParameterDescription,
173        new PercentValue(config.NewErcNameProbability)) { Hidden = true });
174
175      Parameters.Add(new FixedValueParameter<PercentValue>(
176        ErcProbabilityParameterName,
177        ErcProbabilityParameterDescription,
178        new PercentValue(config.ErcProbability)) { Hidden = true });
179
180      Parameters.Add(new FixedValueParameter<IntValue>(
181        MaxPointsInRandomInstructionParameterName,
182        MaxPointsInRandomInstructionParameterDescription,
183        new IntValue(config.MaxPointsInRandomExpression)) { Hidden = true });
184
185      Parameters.Add(new ValueParameter<IBenchmarkSuiteDataDescriptor>(DataParameterName, DataParameterDescription));
186
187      Encoding.Bounds[0, 0] = 0;
188      Encoding.Bounds[0, 1] = config.EnabledExpressions.Count - 1;
189      Encoding.Length = config.MaxPointsInProgram;
190    }
191
192    public IValueParameter<IntMatrix> DataBoundsParameter
193    {
194      get { return (IValueParameter<IntMatrix>)Parameters[DataBoundsParameterName]; }
195    }
196
197    public IntMatrix DataBounds
198    {
199      get { return DataBoundsParameter.Value; }
200      set { DataBoundsParameter.Value = value; }
201    }
202
203
204    public IValueParameter<IEnabledExpressionsConfiguration> InstructionsParameter
205    {
206      get { return (IValueParameter<IEnabledExpressionsConfiguration>)Parameters[InstructionsParameterName]; }
207    }
208
209    public IEnabledExpressionsConfiguration Instructions
210    {
211      get { return InstructionsParameter.Value; }
212      set { InstructionsParameter.Value = value; }
213    }
214
215    public IValueParameter<IBenchmarkSuiteDataDescriptor> DataParameter
216    {
217      get { return (IValueParameter<IBenchmarkSuiteDataDescriptor>)Parameters[DataParameterName]; }
218    }
219
220    public IBenchmarkSuiteDataDescriptor DataDescriptor
221    {
222      get { return DataParameter.Value; }
223      set { DataParameter.Value = value; }
224    }
225
226    public IValueParameter<IntValue> EvalPushLimitParameter
227    {
228      get { return (IValueParameter<IntValue>)this.Parameters[EvalPushLimitParameterName]; }
229    }
230
231    public int EvalPushLimit
232    {
233      get { return config.EvalPushLimit; }
234      set
235      {
236        this.EvalPushLimitParameter.Value.Value = value;
237        config.EvalPushLimit = value;
238      }
239    }
240
241    public IValueParameter<IntValue> MaxProgramLengthParameter
242    {
243      get { return (IValueParameter<IntValue>)this.Parameters[MaxProgramLengthParameterName]; }
244    }
245
246    public int MaxProgramLength
247    {
248      get { return config.MaxPointsInProgram; }
249      set
250      {
251        this.MaxProgramLengthParameter.Value.Value = value;
252        this.Encoding.LengthParameter.Value.Value = value;
253        config.MaxPointsInProgram = value;
254      }
255    }
256
257    public IValueParameter<BoolValue> TopLevelPushParameter
258    {
259      get { return (IValueParameter<BoolValue>)this.Parameters[TopLevelPushCodeParameterName]; }
260    }
261
262    public bool TopLevelPushCode
263    {
264      get { return config.TopLevelPushCode; }
265      set
266      {
267        this.TopLevelPushParameter.Value.Value = value;
268        config.TopLevelPushCode = value;
269      }
270    }
271
272    public IValueParameter<BoolValue> TopLevelPopParameter
273    {
274      get { return (IValueParameter<BoolValue>)this.Parameters[TopLevelPopCodeParameterName]; }
275    }
276
277    public bool TopLevelPopCode
278    {
279      get { return config.TopLevelPopCode; }
280      set
281      {
282        this.TopLevelPushParameter.Value.Value = value;
283        config.TopLevelPopCode = value;
284      }
285    }
286
287    public IValueParameter<IntValue> MinRandomIntegerParameter
288    {
289      get { return (IValueParameter<IntValue>)this.Parameters[MinRandomIntegerParameterName]; }
290    }
291
292    public int MinRandomInteger
293    {
294      get { return config.MinRandomInteger; }
295      set
296      {
297        this.MinRandomIntegerParameter.Value.Value = value;
298        config.MinRandomInteger = value;
299      }
300    }
301
302    public IValueParameter<IntValue> MaxRandomIntegerParameter
303    {
304      get { return (IValueParameter<IntValue>)this.Parameters[MaxRandomIntegerParameterName]; }
305    }
306
307    public int MaxRandomInteger
308    {
309      get { return config.MaxRandomInteger; }
310      set
311      {
312        this.MaxRandomIntegerParameter.Value.Value = value;
313        config.MaxRandomInteger = value;
314      }
315    }
316
317    public IValueParameter<DoubleValue> MinRandomFloatParameter
318    {
319      get { return (IValueParameter<DoubleValue>)this.Parameters[MinRandomFloatParameterName]; }
320    }
321
322    public double MinRandomFloat
323    {
324      get { return config.MinRandomFloat; }
325      set
326      {
327        this.MinRandomFloatParameter.Value.Value = value;
328        config.MinRandomFloat = value;
329      }
330    }
331
332    public IValueParameter<DoubleValue> MaxRandomFloatParameter
333    {
334      get { return (IValueParameter<DoubleValue>)this.Parameters[MaxRandomFloatParameterName]; }
335    }
336
337    public double MaxRandomFloat
338    {
339      get { return config.MaxRandomFloat; }
340      set
341      {
342        this.MaxRandomFloatParameter.Value.Value = value;
343        config.MaxRandomFloat = value;
344      }
345    }
346
347    public IValueParameter<PercentValue> NewErcNameProbabilityParameter
348    {
349      get { return (IValueParameter<PercentValue>)this.Parameters[NewErcNameProbabilityParameterName]; }
350    }
351
352    public double NewErcNameProbability
353    {
354      get { return config.NewErcNameProbability; }
355      set
356      {
357        this.NewErcNameProbabilityParameter.Value.Value = value;
358        config.NewErcNameProbability = value;
359      }
360    }
361
362    public IValueParameter<PercentValue> ErcProbabilityParameter
363    {
364      get { return (IValueParameter<PercentValue>)this.Parameters[ErcProbabilityParameterName]; }
365    }
366
367    public double ErcProbability
368    {
369      get { return config.ErcProbability; }
370      set
371      {
372        this.ErcProbabilityParameter.Value.Value = value;
373        config.ErcProbability = value;
374      }
375    }
376
377    public IValueParameter<IntValue> MaxPointsInRandomInstructionParameter
378    {
379      get { return (IValueParameter<IntValue>)Parameters[MaxPointsInRandomInstructionParameterName]; }
380    }
381
382    public int MaxPointsInRandomInstruction
383    {
384      get { return config.MaxPointsInRandomExpression; }
385      set
386      {
387        this.MaxPointsInRandomInstructionParameter.Value.Value = value;
388        config.MaxPointsInRandomExpression = value;
389      }
390    }
391
392    #endregion
393
394    public override bool Maximization { get { return false; } }
395
396    public override IDeepCloneable Clone(Cloner cloner) {
397      return new PushProblem(this, cloner);
398    }
399
400    public override void Analyze(Individual[] individuals, double[] qualities, ResultCollection results, IRandom random) {
401      const string bestSolutionResultName = "Best Solution";
402      var bestQuality = Maximization ? qualities.Max() : qualities.Min();
403      var bestIdx = Array.IndexOf(qualities, bestQuality);
404      var bestIndividual = individuals[bestIdx];
405      var solution = new PushSolution(bestIndividual.IntegerVector(), bestQuality, DataDescriptor, random, config);
406
407      if (!results.ContainsKey(bestSolutionResultName)) {
408        results.Add(new Result(bestSolutionResultName, solution));
409      } else if (((PushSolution)results[bestSolutionResultName].Value).Quality < qualities[bestIdx]) {
410        results[bestSolutionResultName].Value = solution;
411      }
412    }
413
414    public override double Evaluate(Individual individual, IRandom random) {
415      if (DataBounds[0, 1] <= 0) return default(double);
416
417      var program = individual.PushProgram(config.EnabledExpressions as IReadOnlyList<string>);
418      var result = 0d;
419
420      using (var interpreter = pool.GetInstance(random)) {
421        for (var i = DataBounds[0, 0]; i < DataBounds[0, 1]; i++) {
422          var example = DataDescriptor.Examples[i];
423
424          interpreter.BooleanStack.Push(example.InputBoolean);
425          interpreter.IntegerStack.Push(example.InputInt);
426          interpreter.FloatStack.Push(example.InputFloat);
427
428          using (interpreter.PushProgramPool = pushProgramPoolProvider.CreatePool()) {
429            interpreter.Run(program);
430          }
431
432          result += GetDiff(example.OutputInt, interpreter.IntegerStack, DataDescriptor.WorstResult, LongDiffer)
433                  + GetDiff(example.OutputFloat, interpreter.FloatStack, DataDescriptor.WorstResult, DoubleDiffer)
434                  + GetDiff(example.OutputBoolean, interpreter.BooleanStack, DataDescriptor.WorstResult, BooleanDiffer);
435
436          interpreter.Clear();
437        }
438      }
439
440      return result / DataBounds[0, 1];
441    }
442
443    private static double DoubleDiffer(double a, double b) {
444      var result = a - b;
445
446      return result == double.MinValue ? double.MaxValue : Math.Abs(result);
447    }
448
449    private static double LongDiffer(long a, long b) {
450      var result = a - b;
451
452      return result == long.MinValue ? long.MaxValue : Math.Abs(result);
453    }
454
455    private static double BooleanDiffer(bool a, bool b) {
456      return a && b ? 0 : a || b ? 1 : 2;
457    }
458
459    private static double GetDiff<T>(IReadOnlyList<T> estimated, IStack<T> resultStack, double worstResult, Func<T, T, double> differ)
460      where T : IComparable {
461
462      var count = Math.Min(estimated.Count, resultStack.Count);
463      var result = resultStack.Peek(count);
464      var comparableLength = Math.Min(estimated.Count, result.Length);
465      var diff = 0d;
466
467      for (var i = 0; i < comparableLength; i++) {
468        diff += Math.Min(differ(estimated[i], result[0]), worstResult);
469      }
470
471      if (estimated.Count > result.Length) {
472        diff += worstResult * (estimated.Count - comparableLength);
473      }
474
475      return diff;
476    }
477
478    public void Load(IBenchmarkSuiteDataDescriptor descriptor) {
479      this.DataDescriptor = descriptor;
480      BestKnownQuality = descriptor.BestResult;
481
482      DataBounds[0, 0] = 0;
483      DataBounds[0, 2] = this.DataDescriptor.OriginalTrainingCount + this.DataDescriptor.OriginalTestCount;
484      DataBounds[0, 1] = this.DataDescriptor.OriginalTrainingCount;
485    }
486  }
487}
Note: See TracBrowser for help on using the repository browser.