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.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 static class CodeGenerator {
|
---|
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 IEnumerable<Expression> RandomCode(int maxPoints, IRandom random = null, IReadonlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
|
---|
28 | if (maxPoints == 0)
|
---|
29 | return new Expression[0];
|
---|
30 |
|
---|
31 | random = random ?? new FastRandom();
|
---|
32 | pushGpConfiguration = pushGpConfiguration ?? new PushConfiguration();
|
---|
33 |
|
---|
34 | if (pushGpConfiguration.EnabledExpressions.Count == 0)
|
---|
35 | return new Expression[0];
|
---|
36 |
|
---|
37 | var actualPoints = maxPoints == 1 ? 1 : random.Next(1, Math.Max(1, maxPoints));
|
---|
38 |
|
---|
39 | return RandomCodeWithSize(actualPoints, random, pushGpConfiguration, customExpressions);
|
---|
40 | }
|
---|
41 |
|
---|
42 | private static IEnumerable<Expression> RandomCodeWithSize(int points, IRandom random, IReadonlyPushConfiguration pushGpConfiguration, IDictionary<string, Expression> customExpressions = null) {
|
---|
43 | if (points == 1) {
|
---|
44 |
|
---|
45 | // check if erc expression should be taken
|
---|
46 | return random.NextDouble() <= pushGpConfiguration.ErcProbability
|
---|
47 | ? new[] { CreateRandomErcExpression(random, pushGpConfiguration) }
|
---|
48 | : new[] { CreateExpression(random, pushGpConfiguration, customExpressions) };
|
---|
49 | }
|
---|
50 |
|
---|
51 | var maxParts = points - 1;
|
---|
52 |
|
---|
53 | return Decompose(maxParts, maxParts, random)
|
---|
54 | .SelectMany(size => RandomCodeWithSize(size, random, pushGpConfiguration, customExpressions));
|
---|
55 | }
|
---|
56 |
|
---|
57 | private static IEnumerable<int> Decompose(int number, int maxParts, IRandom random) {
|
---|
58 | if ((number == 1) || (maxParts == 1))
|
---|
59 | return new[] { number };
|
---|
60 |
|
---|
61 | var thisPart = number == 2 ? 1 : random.Next(1, number - 1);
|
---|
62 |
|
---|
63 | return new[] { thisPart }.Concat(Decompose(number - thisPart, maxParts - 1, random));
|
---|
64 | }
|
---|
65 |
|
---|
66 | private static Expression CreateExpression(IRandom random, IReadonlyPushConfiguration pushGpConfiguration, IDictionary<string, Expression> customExpressions = null) {
|
---|
67 | var customCount = customExpressions == null ? 0 : customExpressions.Count - 1;
|
---|
68 | var index = random.Next(0, pushGpConfiguration.EnabledExpressions.Count + customCount - 1);
|
---|
69 |
|
---|
70 | if ((index >= 0) && (index < pushGpConfiguration.EnabledExpressions.Count)) {
|
---|
71 | var name = pushGpConfiguration.EnabledExpressions[index];
|
---|
72 | return ExpressionTable.GetExpression(name);
|
---|
73 | }
|
---|
74 |
|
---|
75 | if (customExpressions == null)
|
---|
76 | throw new IndexOutOfRangeException();
|
---|
77 |
|
---|
78 | return customExpressions.ElementAt(index - (pushGpConfiguration.EnabledExpressions.Count - 1)).Value;
|
---|
79 | }
|
---|
80 |
|
---|
81 | private static Expression CreateRandomErcExpression(IRandom random, IReadonlyPushConfiguration pushGpConfiguration) {
|
---|
82 | var value = random.Next(0, 3);
|
---|
83 |
|
---|
84 | switch (value) {
|
---|
85 | case 0:
|
---|
86 | return new IntegerPushExpression(random.Next(
|
---|
87 | pushGpConfiguration.MinRandomInteger,
|
---|
88 | pushGpConfiguration.MaxRandomInteger));
|
---|
89 |
|
---|
90 | case 1:
|
---|
91 | return new FloatPushExpression(
|
---|
92 | random.NextDouble() *
|
---|
93 | (pushGpConfiguration.MaxRandomFloat - pushGpConfiguration.MinRandomFloat) +
|
---|
94 | pushGpConfiguration.MinRandomFloat);
|
---|
95 |
|
---|
96 | case 2:
|
---|
97 | return new BooleanPushExpression(random.NextDouble() > 0.5);
|
---|
98 |
|
---|
99 | case 3:
|
---|
100 | return new NamePushExpression(NameGenerator.RandomName(random));
|
---|
101 |
|
---|
102 | default:
|
---|
103 | throw new NotImplementedException();
|
---|
104 | }
|
---|
105 | }
|
---|
106 | }
|
---|
107 | } |
---|