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

namespace HeuristicLab.Problems.ProgramSynthesis.Push.Generators {
  using System;
  using System.Collections.Generic;
  using System.Linq;
  using HeuristicLab.Core;
  using HeuristicLab.Problems.ProgramSynthesis.Push.Configuration;
  using HeuristicLab.Problems.ProgramSynthesis.Push.Data.Pool;
  using HeuristicLab.Problems.ProgramSynthesis.Push.Expressions;
  using HeuristicLab.Random;

  /// <summary>
  ///     The following is the standard Push random code generation algorithm, which is used for the CODE.RAND instruction.
  ///     It may also be useful for the initialization of programs in evolutionary computation systems, and it is used for
  ///     this purpose in PushGP.
  ///     It produces a uniform distribution of sizes and what seems to be a reasonable distribution of shapes, in a
  ///     reasonable amount of time.
  /// </summary>
  /// <see cref="http://faculty.hampshire.edu/lspector/push3-description.html#RandomCode" />
  public class RecursiveCodeGenerator {

    public static PushProgram RandomProgram(IManagedPool<PushProgram> pool, int maxPoints, IRandom random = null, IReadOnlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
      var code = RandomCode(maxPoints, random, pushGpConfiguration, customExpressions);

      return PushProgram.Create(pool, code.ToArray());
    }

    public static PushProgram RandomProgram(int maxPoints, IRandom random = null, IReadOnlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
      var code = RandomCode(maxPoints, random, pushGpConfiguration, customExpressions);

      return new PushProgram(code.ToArray());
    }

    public static IEnumerable<Expression> RandomCode(int maxPoints, IRandom random = null, IReadOnlyPushConfiguration pushGpConfiguration = null, IDictionary<string, Expression> customExpressions = null) {
      if (maxPoints == 0)
        return new Expression[0];

      random = random ?? new FastRandom();
      pushGpConfiguration = pushGpConfiguration ?? new PushConfiguration();

      if (pushGpConfiguration.EnabledExpressions.Count == 0)
        return new Expression[0];

      var actualPoints = maxPoints == 1 ? 1 : random.Next(1, Math.Max(1, maxPoints));

      return RandomCodeWithSize(actualPoints, random, pushGpConfiguration, customExpressions);
    }

    private static IEnumerable<Expression> RandomCodeWithSize(int points, IRandom random, IReadOnlyPushConfiguration pushGpConfiguration, IDictionary<string, Expression> customExpressions = null) {
      if (points == 1) {

        // check if erc expression should be taken
        return random.NextDouble() <= pushGpConfiguration.ErcProbability
          ? new[] { CreateRandomErcExpression(random, pushGpConfiguration) }
          : new[] { CreateExpression(random, pushGpConfiguration, customExpressions) };
      }

      var maxParts = points - 1;

      return Decompose(maxParts, maxParts, random)
        .SelectMany(size => RandomCodeWithSize(size, random, pushGpConfiguration, customExpressions));
    }

    private static IEnumerable<int> Decompose(int number, int maxParts, IRandom random) {
      if ((number == 1) || (maxParts == 1))
        return new[] { number };

      var thisPart = number == 2 ? 1 : random.Next(1, number - 1);

      return new[] { thisPart }.Concat(Decompose(number - thisPart, maxParts - 1, random));
    }

    private static Expression CreateExpression(IRandom random, IReadOnlyPushConfiguration pushGpConfiguration, IDictionary<string, Expression> customExpressions = null) {
      var customCount = customExpressions == null ? 0 : customExpressions.Count - 1;
      var index = random.Next(0, pushGpConfiguration.EnabledExpressions.Count + customCount - 1);

      if ((index >= 0) && (index < pushGpConfiguration.EnabledExpressions.Count)) {
        var name = pushGpConfiguration.EnabledExpressions[index];
        return ExpressionTable.GetExpression(name);
      }

      if (customExpressions == null)
        throw new IndexOutOfRangeException();

      return customExpressions.ElementAt(index - (pushGpConfiguration.EnabledExpressions.Count - 1)).Value;
    }

    private static Expression CreateRandomErcExpression(IRandom random, IReadOnlyPushConfiguration pushGpConfiguration) {
      var value = random.Next(0, 3);

      switch (value) {
        case 0:
          return new IntegerPushExpression(random.Next(
            pushGpConfiguration.MinRandomInteger,
            pushGpConfiguration.MaxRandomInteger));

        case 1:
          return new FloatPushExpression(
            random.NextDouble() *
            (pushGpConfiguration.MaxRandomFloat - pushGpConfiguration.MinRandomFloat) +
            pushGpConfiguration.MinRandomFloat);

        case 2:
          return new BooleanPushExpression(random.NextDouble() > 0.5);

        case 3:
          return new NamePushExpression(NameGenerator.RandomName(random));

        default:
          throw new NotImplementedException();
      }
    }
  }
}