source: branches/Robocode.TrunkInt/HeuristicLab.Problems.Robocode/3.3/Crossover/RobocodeMethodCrossover.cs @ 9844

#region License Information
/* HeuristicLab
 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
 *
 * This file is part of HeuristicLab.
 *
 * HeuristicLab is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * HeuristicLab is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
 */
#endregion

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

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);
            }
        }
    }*/
  }
}