[14777] | 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 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 | } |
---|