[14392] | 1 | using System;
|
---|
| 2 | using System.Collections.Generic;
|
---|
[14323] | 3 | using System.Linq;
|
---|
| 4 | using HeuristicLab.Algorithms.PushGP.Expressions;
|
---|
[14392] | 5 | using HeuristicLab.Algorithms.PushGP.Interpreter;
|
---|
| 6 | using HeuristicLab.Core;
|
---|
[14328] | 7 | using HeuristicLab.Random;
|
---|
[14323] | 8 |
|
---|
| 9 | namespace HeuristicLab.Algorithms.PushGP.Generators
|
---|
| 10 | {
|
---|
[14392] | 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 this purpose in PushGP.
|
---|
| 14 | /// It produces a uniform distribution of sizes and what seems to be a reasonable distribution of shapes, in a reasonable amount of time.
|
---|
| 15 | /// </summary>
|
---|
| 16 | /// <see cref="http://faculty.hampshire.edu/lspector/push3-description.html#RandomCode"/>
|
---|
| 17 | public class CodeGenerator
|
---|
[14323] | 18 | {
|
---|
[14392] | 19 | private static IRandom random = new FastRandom();
|
---|
| 20 | private readonly IInterpreter interpreter;
|
---|
| 21 |
|
---|
| 22 | public CodeGenerator(IInterpreter interpreter)
|
---|
[14323] | 23 | {
|
---|
[14392] | 24 | this.interpreter = interpreter;
|
---|
| 25 | }
|
---|
[14323] | 26 |
|
---|
[14392] | 27 | /// <summary>
|
---|
| 28 | /// Generates a random program with a given max size
|
---|
| 29 | /// </summary>
|
---|
| 30 | /// <param name="maxPoints"></param>
|
---|
| 31 | /// <returns>Returns an ExpandExpression if maxPoints smaller or equal to Configuration.MaxProgramPoints and Noop otherwise</returns>
|
---|
| 32 | public Expression RandomProgram(int maxPoints)
|
---|
| 33 | {
|
---|
| 34 | return ExecExpandExpression.TryCreate(interpreter.CodeGenerator.RandomCode(maxPoints).ToArray(), interpreter.Configuration);
|
---|
[14323] | 35 | }
|
---|
| 36 |
|
---|
[14392] | 37 | public IEnumerable<Expression> RandomCode(int maxPoints)
|
---|
[14323] | 38 | {
|
---|
[14392] | 39 | var actualPoints = random.Next(1, Math.Max(1, maxPoints));
|
---|
| 40 |
|
---|
| 41 | return RandomCodeWithSize(actualPoints);
|
---|
| 42 | }
|
---|
| 43 |
|
---|
| 44 | private IEnumerable<Expression> RandomCodeWithSize(int points)
|
---|
| 45 | {
|
---|
[14323] | 46 | if (points == 1)
|
---|
| 47 | {
|
---|
[14392] | 48 | var index = random.Next(0, ExpressionTable.Count + this.interpreter.CustomExpressions.Count - 2);
|
---|
| 49 | return new[] { this.CreateExpression(index) };
|
---|
[14323] | 50 | }
|
---|
| 51 | else
|
---|
| 52 | {
|
---|
| 53 | var sizesThisLevel = Decompose(points - 1, points - 1);
|
---|
[14328] | 54 | return sizesThisLevel.SelectMany(size => RandomCodeWithSize(size)).Shuffle(random);
|
---|
[14323] | 55 | }
|
---|
| 56 | }
|
---|
| 57 |
|
---|
[14392] | 58 | private IEnumerable<int> Decompose(int number, int maxParts)
|
---|
[14323] | 59 | {
|
---|
| 60 | if (number == 1 || maxParts == 1)
|
---|
| 61 | {
|
---|
| 62 | return new[] { number };
|
---|
| 63 | }
|
---|
| 64 | else
|
---|
| 65 | {
|
---|
[14328] | 66 | var thisPart = random.Next(1, number - 1);
|
---|
[14323] | 67 | return new[] { thisPart }.Concat(Decompose(number - thisPart, maxParts - 1));
|
---|
| 68 | }
|
---|
| 69 | }
|
---|
[14392] | 70 |
|
---|
| 71 | private Expression CreateExpression(int index)
|
---|
| 72 | {
|
---|
| 73 | return (index >= 0 && index < ExpressionTable.Count)
|
---|
| 74 | ? ExpressionTable.GetExpression(index)
|
---|
| 75 | : new NameDefineXExecExpression(this.interpreter.CustomExpressions.ElementAt(index - (ExpressionTable.Count - 1)).Key);
|
---|
| 76 | }
|
---|
[14323] | 77 | }
|
---|
| 78 | }
|
---|