source: branches/Robocode/HeuristicLab.Problems.Robocode/Crossover/RobocodeMethodCrossover.cs @ 12933

using System;
using System.Collections.Generic;
using System.Linq;
using HeuristicLab.Common;
using HeuristicLab.Core;
using HeuristicLab.Data;
using HeuristicLab.Parameters;
using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;

namespace HeuristicLab.Problems.Robocode
{
    /// <summary>
    /// Takes two parent individuals P0 and P1 each. Selects a random node N0 of P0 and a random node N1 of P1.
    /// And replaces the branch with root0 N0 in P0 with N1 from P1 if the tree-size limits are not violated.
    /// When recombination with N0 and N1 would create a tree that is too large or invalid the operator randomly selects new N0 and N1 
    /// until a valid configuration is found.
    /// </summary>  
    [Item("RobocodeMethodCrossover", "An operator which performs crossover of randomly chosen statements with a method.")]
    [StorableClass]
    public class RobocodeMethodCrossover : SymbolicExpressionTreeCrossover//, ISymbolicExpressionTreeSizeConstraintOperator
    {

        #region Parameter Names

        private const string HomologousCrossoverPrameterName = "HomologousCrossover";
        private const string MaximumCrossoverMethodsParameterName = "MaximumCrossoverMethods";

        #endregion

        #region Parameter Properties

        public IValueLookupParameter<BoolValue> HomologousCrossoverParameter
        {
            get { return (IValueLookupParameter<BoolValue>)Parameters[HomologousCrossoverPrameterName]; }
        }

        public IValueLookupParameter<IntValue> MaximumCrossoverMethodsParameter
        {
            get { return (IValueLookupParameter<IntValue>)Parameters[MaximumCrossoverMethodsParameterName]; }
        }
        #endregion

        #region Properties

        public BoolValue HomologousCrossover
        {
            get { return HomologousCrossoverParameter.ActualValue; }
        }

        public IntValue MaximumCrossoverMethods
        {
            get { return MaximumCrossoverMethodsParameter.ActualValue; }
        }

        #endregion

        [StorableConstructor]
        protected RobocodeMethodCrossover(bool deserializing) : base(deserializing) { }
        protected RobocodeMethodCrossover(RobocodeMethodCrossover original, Cloner cloner) :
            base(original, cloner) { }
        public RobocodeMethodCrossover()
            : base()
        {
            Parameters.Add(new ValueLookupParameter<BoolValue>(HomologousCrossoverPrameterName,
                "Specifies if the number of statements exchanged between the two parents is the same.", new BoolValue(false)));
            Parameters.Add(new ValueLookupParameter<IntValue>(MaximumCrossoverMethodsParameterName,
                "The maximal methods to apply crossover on (0 or a number higher than the count of " +
                "methods means applying crossover to them all).", new IntValue(0)));
        }

        public override IDeepCloneable Clone(Cloner cloner)
        {
            return new RobocodeMethodCrossover(this, cloner);
        }

        public override ISymbolicExpressionTree Crossover(IRandom random,
          ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1)
        {
            return Cross(random, parent0, parent1, HomologousCrossover.Value,
              MaximumCrossoverMethods.Value);
        }

        public static ISymbolicExpressionTree Cross(IRandom random,
          ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1,
          bool homologous, int maximumCrossoverMethods)
        {
            // select a random crossover point in the first parent 
            List<CutPoint> crossoverPoints0;
            SelectCrossoverPoint(random, parent0, maximumCrossoverMethods, out crossoverPoints0);

            foreach (CutPoint c in crossoverPoints0)
            {
                List<ISymbolicExpressionTreeNode> allowedBranches = new List<ISymbolicExpressionTreeNode>();
                parent1.Root.ForEachNodePostfix((n) =>
                {
                    if (n.Symbol.GetType() == c.Child.Symbol.GetType())
                        allowedBranches.Add(n);
                });

                if (allowedBranches.Count == 0)
                {
                    break;
                }
                else
                {
                    ISymbolicExpressionTreeNode branch = allowedBranches.FirstOrDefault();
                    int startBranchParent0 = (c.Child.SubtreeCount <= 2)? 0 : random.Next(0, c.Child.SubtreeCount - 2);
                    int endBranchParent0 = (c.Child.SubtreeCount <= 2) ? 1 : random.Next(startBranchParent0 + 1, c.Child.SubtreeCount - 1);
                    int Parent0Branches = endBranchParent0 - startBranchParent0;

                    for (int i = 0; i < Parent0Branches; i++)
                    {
                        c.Child.RemoveSubtree(startBranchParent0);
                    }

                    if (homologous)
                    {
                        for (int j = startBranchParent0; j <= endBranchParent0; j++)
                        {
                            c.Child.AddSubtree(branch.GetSubtree(j));
                        }
                    }
                    else
                    {
                        int startBranchParent1 = (branch.SubtreeCount <= 2) ? 0 : random.Next(0, branch.SubtreeCount - 2);
                        int endBranchParent1 = (branch.SubtreeCount <= 2) ? 1 : random.Next(startBranchParent1 + 1, branch.SubtreeCount - 1);
                        int Parent1Branches = endBranchParent1 - startBranchParent1;

                        for (int j = startBranchParent1; j <= endBranchParent1 && c.Child.SubtreeCount < c.Child.Symbol.MaximumArity; j++)
                        {
                            c.Child.AddSubtree(branch.GetSubtree(j));
                        }
                    }
                }
            }

            return parent0;
        }

        private static void SelectCrossoverPoint(IRandom random, ISymbolicExpressionTree parent0,
            int maximumCrossoverMethods, out List<CutPoint> crossoverPoints)
        {
            List<CutPoint> MethodPoints = new List<CutPoint>();
            parent0.Root.ForEachNodePostfix((n) =>
            {
                if (n.SubtreeCount > 0 && n != parent0.Root)
                {
                    foreach (var child in n.Subtrees)
                    {
                        if (child.Symbol is Run ||
                            child.Symbol is OnBulletHit ||
                            child.Symbol is OnBulletMissed ||
                            child.Symbol is OnHitByBullet ||
                            child.Symbol is OnHitRobot ||
                            child.Symbol is OnHitWall ||
                            child.Symbol is OnScannedRobot)
                            MethodPoints.Add(new CutPoint(n, child));
                    }
                }
            });

            if (maximumCrossoverMethods == 0)
                crossoverPoints = MethodPoints;
            else
            {
                crossoverPoints = new List<CutPoint>();
                for (int i = 0; i < maximumCrossoverMethods; i++)
                {
                    CutPoint c = MethodPoints.SelectRandom(random);
                    crossoverPoints.Add(c);
                    MethodPoints.Remove(c);
                    if (MethodPoints.Count == 0) break;
                }
            }
        }

        /*private static ISymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<ISymbolicExpressionTreeNode> branches, double internalNodeProbability)
        {
            if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
            List<ISymbolicExpressionTreeNode> allowedInternalBranches;
            List<ISymbolicExpressionTreeNode> allowedLeafBranches;
            if (random.NextDouble() < internalNodeProbability)
            {
                // select internal node if possible
                allowedInternalBranches = (from branch in branches
                                           where branch != null && branch.SubtreeCount > 0
                                           select branch).ToList();
                if (allowedInternalBranches.Count > 0)
                {
                    return allowedInternalBranches.SelectRandom(random);
                }
                else
                {
                    // no internal nodes allowed => select leaf nodes
                    allowedLeafBranches = (from branch in branches
                                           where branch == null || branch.SubtreeCount == 0
                                           select branch).ToList();
                    return allowedLeafBranches.SelectRandom(random);
                }
            }
            else
            {
                // select leaf node if possible
                allowedLeafBranches = (from branch in branches
                                       where branch == null || branch.SubtreeCount == 0
                                       select branch).ToList();
                if (allowedLeafBranches.Count > 0)
                {
                    return allowedLeafBranches.SelectRandom(random);
                }
                else
                {
                    allowedInternalBranches = (from branch in branches
                                               where branch != null && branch.SubtreeCount > 0
                                               select branch).ToList();
                    return allowedInternalBranches.SelectRandom(random);
                }
            }
        }*/
    }
}