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