source: branches/PushGP/HeuristicLab.PushGP/HeuristicLab.Problems.ProgramSynthesis/Push/Generators/RecursiveCodeGenerator.cs @ 14777

Last change on this file since 14777 was 14777, checked in by pkimmesw, 2 years ago

#2665 simplifier, push solution results view, performance improvements, small bug fixes, ui fixes

File size: 5.0 KB
Line 
1namespace HeuristicLab.Problems.ProgramSynthesis.Push.Generators {
2  using System;
3  using System.Collections.Generic;
4  using System.Linq;
5  using HeuristicLab.Core;
6  using HeuristicLab.Problems.ProgramSynthesis.Push.Configuration;
7  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Pool;
8  using HeuristicLab.Problems.ProgramSynthesis.Push.Expressions;
9  using HeuristicLab.Random;
10
11  /// <summary>
12  ///     The following is the standard Push random code generation algorithm, which is used for the CODE.RAND instruction.
13  ///     It may also be useful for the initialization of programs in evolutionary computation systems, and it is used for
14  ///     this purpose in PushGP.
15  ///     It produces a uniform distribution of sizes and what seems to be a reasonable distribution of shapes, in a
16  ///     reasonable amount of time.
17  /// </summary>
18  /// <see cref="http://faculty.hampshire.edu/lspector/push3-description.html#RandomCode" />
19  public class RecursiveCodeGenerator {
20
21    public static PushProgram RandomProgram(IManagedPool<PushProgram> pool, int maxPoints, IRandom random = null, IReadOnlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
22      var code = RandomCode(maxPoints, random, pushGpConfiguration, customExpressions);
23
24      return PushProgram.Create(pool, code.ToArray());
25    }
26
27    public static PushProgram RandomProgram(int maxPoints, IRandom random = null, IReadOnlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
28      var code = RandomCode(maxPoints, random, pushGpConfiguration, customExpressions);
29
30      return new PushProgram(code.ToArray());
31    }
32
33    public static IEnumerable<Expression> RandomCode(int maxPoints, IRandom random = null, IReadOnlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
34      if (maxPoints == 0)
35        return new Expression[0];
36
37      random = random ?? new FastRandom();
38      pushGpConfiguration = pushGpConfiguration ?? new PushConfiguration();
39
40      if (pushGpConfiguration.EnabledExpressions.Count == 0)
41        return new Expression[0];
42
43      var actualPoints = maxPoints == 1 ? 1 : random.Next(1, Math.Max(1, maxPoints));
44
45      return RandomCodeWithSize(actualPoints, random, pushGpConfiguration, customExpressions);
46    }
47
48    private static IEnumerable<Expression> RandomCodeWithSize(int points, IRandom random, IReadOnlyPushConfiguration pushGpConfiguration, IDictionary<string, Expression> customExpressions = null) {
49      if (points == 1) {
50
51        // check if erc expression should be taken
52        return random.NextDouble() <= pushGpConfiguration.ErcProbability
53          ? new[] { CreateRandomErcExpression(random, pushGpConfiguration) }
54          : new[] { CreateExpression(random, pushGpConfiguration, customExpressions) };
55      }
56
57      var maxParts = points - 1;
58
59      return Decompose(maxParts, maxParts, random)
60        .SelectMany(size => RandomCodeWithSize(size, random, pushGpConfiguration, customExpressions));
61    }
62
63    private static IEnumerable<int> Decompose(int number, int maxParts, IRandom random) {
64      if ((number == 1) || (maxParts == 1))
65        return new[] { number };
66
67      var thisPart = number == 2 ? 1 : random.Next(1, number - 1);
68
69      return new[] { thisPart }.Concat(Decompose(number - thisPart, maxParts - 1, random));
70    }
71
72    private static Expression CreateExpression(IRandom random, IReadOnlyPushConfiguration pushGpConfiguration, IDictionary<string, Expression> customExpressions = null) {
73      var customCount = customExpressions == null ? 0 : customExpressions.Count - 1;
74      var index = random.Next(0, pushGpConfiguration.EnabledExpressions.Count + customCount - 1);
75
76      if ((index >= 0) && (index < pushGpConfiguration.EnabledExpressions.Count)) {
77        var name = pushGpConfiguration.EnabledExpressions[index];
78        return ExpressionTable.GetExpression(name);
79      }
80
81      if (customExpressions == null)
82        throw new IndexOutOfRangeException();
83
84      return customExpressions.ElementAt(index - (pushGpConfiguration.EnabledExpressions.Count - 1)).Value;
85    }
86
87    private static Expression CreateRandomErcExpression(IRandom random, IReadOnlyPushConfiguration pushGpConfiguration) {
88      var value = random.Next(0, 3);
89
90      switch (value) {
91        case 0:
92          return new IntegerPushExpression(random.Next(
93            pushGpConfiguration.MinRandomInteger,
94            pushGpConfiguration.MaxRandomInteger));
95
96        case 1:
97          return new FloatPushExpression(
98            random.NextDouble() *
99            (pushGpConfiguration.MaxRandomFloat - pushGpConfiguration.MinRandomFloat) +
100            pushGpConfiguration.MinRandomFloat);
101
102        case 2:
103          return new BooleanPushExpression(random.NextDouble() > 0.5);
104
105        case 3:
106          return new NamePushExpression(NameGenerator.RandomName(random));
107
108        default:
109          throw new NotImplementedException();
110      }
111    }
112  }
113}
Note: See TracBrowser for help on using the repository browser.