Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/26/13 15:13:05 (11 years ago)
Author:
ascheibe
Message:

#2069

  • added license headers
  • corrected version information
  • fixed formatting
Location:
branches/Robocode.TrunkInt/HeuristicLab.Problems.Robocode/3.3/Crossover
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • branches/Robocode.TrunkInt/HeuristicLab.Problems.Robocode/3.3/Crossover/RobocodeCrossover.cs

    r9565 r9790  
    11#region License Information
    22/* HeuristicLab
    3  * Copyright (C) 2002-2012 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     3 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    44 *
    55 * This file is part of HeuristicLab.
    … …  
    2626using HeuristicLab.Core;
    2727using HeuristicLab.Data;
     28using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    2829using HeuristicLab.Parameters;
    2930using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    30 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    3131
    3232namespace HeuristicLab.Problems.Robocode {

  • branches/Robocode.TrunkInt/HeuristicLab.Problems.Robocode/3.3/Crossover/RobocodeMethodCrossover.cs

    r9565 r9790  
    1 using System;
     1#region License Information
     2/* HeuristicLab
     3 * Copyright (C) 2002-2013 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     4 *
     5 * This file is part of HeuristicLab.
     6 *
     7 * HeuristicLab is free software: you can redistribute it and/or modify
     8 * it under the terms of the GNU General Public License as published by
     9 * the Free Software Foundation, either version 3 of the License, or
     10 * (at your option) any later version.
     11 *
     12 * HeuristicLab is distributed in the hope that it will be useful,
     13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
     15 * GNU General Public License for more details.
     16 *
     17 * You should have received a copy of the GNU General Public License
     18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
     19 */
     20#endregion
     21
    222using System.Collections.Generic;
    323using System.Linq;
    … …  
    525using HeuristicLab.Core;
    626using HeuristicLab.Data;
     27using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    728using HeuristicLab.Parameters;
    829using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    9 using HeuristicLab.Encodings.SymbolicExpressionTreeEncoding;
    10 
    11 namespace HeuristicLab.Problems.Robocode
    12 {
    13     /// <summary>
    14     /// Takes two parent individuals P0 and P1 each. Selects a random node N0 of P0 and a random node N1 of P1.
    15     /// And replaces the branch with root0 N0 in P0 with N1 from P1 if the tree-size limits are not violated.
    16     /// When recombination with N0 and N1 would create a tree that is too large or invalid the operator randomly selects new N0 and N1
    17     /// until a valid configuration is found.
    18     /// </summary> 
    19     [Item("RobocodeMethodCrossover", "An operator which performs crossover of randomly chosen statements with a method.")]
    20     [StorableClass]
    21     public class RobocodeMethodCrossover : SymbolicExpressionTreeCrossover//, ISymbolicExpressionTreeSizeConstraintOperator
     30
     31namespace HeuristicLab.Problems.Robocode {
     32  /// <summary>
     33  /// Takes two parent individuals P0 and P1 each. Selects a random node N0 of P0 and a random node N1 of P1.
     34  /// And replaces the branch with root0 N0 in P0 with N1 from P1 if the tree-size limits are not violated.
     35  /// When recombination with N0 and N1 would create a tree that is too large or invalid the operator randomly selects new N0 and N1
     36  /// until a valid configuration is found.
     37  /// </summary> 
     38  [Item("RobocodeMethodCrossover", "An operator which performs crossover of randomly chosen statements with a method.")]
     39  [StorableClass]
     40  public class RobocodeMethodCrossover : SymbolicExpressionTreeCrossover//, ISymbolicExpressionTreeSizeConstraintOperator
     41  {
     42
     43    #region Parameter Names
     44
     45    private const string HomologousCrossoverPrameterName = "HomologousCrossover";
     46    private const string MaximumCrossoverMethodsParameterName = "MaximumCrossoverMethods";
     47
     48    #endregion
     49
     50    #region Parameter Properties
     51
     52    public IValueLookupParameter<BoolValue> HomologousCrossoverParameter {
     53      get { return (IValueLookupParameter<BoolValue>)Parameters[HomologousCrossoverPrameterName]; }
     54    }
     55
     56    public IValueLookupParameter<IntValue> MaximumCrossoverMethodsParameter {
     57      get { return (IValueLookupParameter<IntValue>)Parameters[MaximumCrossoverMethodsParameterName]; }
     58    }
     59    #endregion
     60
     61    #region Properties
     62
     63    public BoolValue HomologousCrossover {
     64      get { return HomologousCrossoverParameter.ActualValue; }
     65    }
     66
     67    public IntValue MaximumCrossoverMethods {
     68      get { return MaximumCrossoverMethodsParameter.ActualValue; }
     69    }
     70
     71    #endregion
     72
     73    [StorableConstructor]
     74    protected RobocodeMethodCrossover(bool deserializing) : base(deserializing) { }
     75    protected RobocodeMethodCrossover(RobocodeMethodCrossover original, Cloner cloner) :
     76      base(original, cloner) { }
     77    public RobocodeMethodCrossover()
     78      : base() {
     79      Parameters.Add(new ValueLookupParameter<BoolValue>(HomologousCrossoverPrameterName,
     80          "Specifies if the number of statements exchanged between the two parents is the same.", new BoolValue(false)));
     81      Parameters.Add(new ValueLookupParameter<IntValue>(MaximumCrossoverMethodsParameterName,
     82          "The maximal methods to apply crossover on (0 or a number higher than the count of " +
     83          "methods means applying crossover to them all).", new IntValue(0)));
     84    }
     85
     86    public override IDeepCloneable Clone(Cloner cloner) {
     87      return new RobocodeMethodCrossover(this, cloner);
     88    }
     89
     90    public override ISymbolicExpressionTree Crossover(IRandom random,
     91      ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1) {
     92      return Cross(random, parent0, parent1, HomologousCrossover.Value,
     93        MaximumCrossoverMethods.Value);
     94    }
     95
     96    public static ISymbolicExpressionTree Cross(IRandom random,
     97      ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1,
     98      bool homologous, int maximumCrossoverMethods) {
     99      // select a random crossover point in the first parent
     100      List<CutPoint> crossoverPoints0;
     101      SelectCrossoverPoint(random, parent0, maximumCrossoverMethods, out crossoverPoints0);
     102
     103      foreach (CutPoint c in crossoverPoints0) {
     104        List<ISymbolicExpressionTreeNode> allowedBranches = new List<ISymbolicExpressionTreeNode>();
     105        parent1.Root.ForEachNodePostfix((n) => {
     106          if (n.Symbol.GetType() == c.Child.Symbol.GetType())
     107            allowedBranches.Add(n);
     108        });
     109
     110        if (allowedBranches.Count == 0) {
     111          break;
     112        } else {
     113          ISymbolicExpressionTreeNode branch = allowedBranches.FirstOrDefault();
     114          int startBranchParent0 = (c.Child.SubtreeCount <= 2) ? 0 : random.Next(0, c.Child.SubtreeCount - 2);
     115          int endBranchParent0 = (c.Child.SubtreeCount <= 2) ? 1 : random.Next(startBranchParent0 + 1, c.Child.SubtreeCount - 1);
     116          int Parent0Branches = endBranchParent0 - startBranchParent0;
     117
     118          for (int i = 0; i < Parent0Branches; i++) {
     119            c.Child.RemoveSubtree(startBranchParent0);
     120          }
     121
     122          if (homologous) {
     123            for (int j = startBranchParent0; j <= endBranchParent0; j++) {
     124              c.Child.AddSubtree(branch.GetSubtree(j));
     125            }
     126          } else {
     127            int startBranchParent1 = (branch.SubtreeCount <= 2) ? 0 : random.Next(0, branch.SubtreeCount - 2);
     128            int endBranchParent1 = (branch.SubtreeCount <= 2) ? 1 : random.Next(startBranchParent1 + 1, branch.SubtreeCount - 1);
     129            int Parent1Branches = endBranchParent1 - startBranchParent1;
     130
     131            for (int j = startBranchParent1; j <= endBranchParent1 && c.Child.SubtreeCount < c.Child.Symbol.MaximumArity; j++) {
     132              c.Child.AddSubtree(branch.GetSubtree(j));
     133            }
     134          }
     135        }
     136      }
     137
     138      return parent0;
     139    }
     140
     141    private static void SelectCrossoverPoint(IRandom random, ISymbolicExpressionTree parent0,
     142        int maximumCrossoverMethods, out List<CutPoint> crossoverPoints) {
     143      List<CutPoint> MethodPoints = new List<CutPoint>();
     144      parent0.Root.ForEachNodePostfix((n) => {
     145        if (n.SubtreeCount > 0 && n != parent0.Root) {
     146          foreach (var child in n.Subtrees) {
     147            if (child.Symbol is Run ||
     148                child.Symbol is OnBulletHit ||
     149                child.Symbol is OnBulletMissed ||
     150                child.Symbol is OnHitByBullet ||
     151                child.Symbol is OnHitRobot ||
     152                child.Symbol is OnHitWall ||
     153                child.Symbol is OnScannedRobot)
     154              MethodPoints.Add(new CutPoint(n, child));
     155          }
     156        }
     157      });
     158
     159      if (maximumCrossoverMethods == 0)
     160        crossoverPoints = MethodPoints;
     161      else {
     162        crossoverPoints = new List<CutPoint>();
     163        for (int i = 0; i < maximumCrossoverMethods; i++) {
     164          CutPoint c = MethodPoints.SelectRandom(random);
     165          crossoverPoints.Add(c);
     166          MethodPoints.Remove(c);
     167          if (MethodPoints.Count == 0) break;
     168        }
     169      }
     170    }
     171
     172    /*private static ISymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<ISymbolicExpressionTreeNode> branches, double internalNodeProbability)
    22173    {
    23 
    24         #region Parameter Names
    25 
    26         private const string HomologousCrossoverPrameterName = "HomologousCrossover";
    27         private const string MaximumCrossoverMethodsParameterName = "MaximumCrossoverMethods";
    28 
    29         #endregion
    30 
    31         #region Parameter Properties
    32 
    33         public IValueLookupParameter<BoolValue> HomologousCrossoverParameter
     174        if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
     175        List<ISymbolicExpressionTreeNode> allowedInternalBranches;
     176        List<ISymbolicExpressionTreeNode> allowedLeafBranches;
     177        if (random.NextDouble() < internalNodeProbability)
    34178        {
    35             get { return (IValueLookupParameter<BoolValue>)Parameters[HomologousCrossoverPrameterName]; }
    36         }
    37 
    38         public IValueLookupParameter<IntValue> MaximumCrossoverMethodsParameter
     179            // select internal node if possible
     180            allowedInternalBranches = (from branch in branches
     181                                       where branch != null && branch.SubtreeCount > 0
     182                                       select branch).ToList();
     183            if (allowedInternalBranches.Count > 0)
     184            {
     185                return allowedInternalBranches.SelectRandom(random);
     186            }
     187            else
     188            {
     189                // no internal nodes allowed => select leaf nodes
     190                allowedLeafBranches = (from branch in branches
     191                                       where branch == null || branch.SubtreeCount == 0
     192                                       select branch).ToList();
     193                return allowedLeafBranches.SelectRandom(random);
     194            }
     195        }
     196        else
    39197        {
    40             get { return (IValueLookupParameter<IntValue>)Parameters[MaximumCrossoverMethodsParameterName]; }
    41         }
    42         #endregion
    43 
    44         #region Properties
    45 
    46         public BoolValue HomologousCrossover
    47         {
    48             get { return HomologousCrossoverParameter.ActualValue; }
    49         }
    50 
    51         public IntValue MaximumCrossoverMethods
    52         {
    53             get { return MaximumCrossoverMethodsParameter.ActualValue; }
    54         }
    55 
    56         #endregion
    57 
    58         [StorableConstructor]
    59         protected RobocodeMethodCrossover(bool deserializing) : base(deserializing) { }
    60         protected RobocodeMethodCrossover(RobocodeMethodCrossover original, Cloner cloner) :
    61             base(original, cloner) { }
    62         public RobocodeMethodCrossover()
    63             : base()
    64         {
    65             Parameters.Add(new ValueLookupParameter<BoolValue>(HomologousCrossoverPrameterName,
    66                 "Specifies if the number of statements exchanged between the two parents is the same.", new BoolValue(false)));
    67             Parameters.Add(new ValueLookupParameter<IntValue>(MaximumCrossoverMethodsParameterName,
    68                 "The maximal methods to apply crossover on (0 or a number higher than the count of " +
    69                 "methods means applying crossover to them all).", new IntValue(0)));
    70         }
    71 
    72         public override IDeepCloneable Clone(Cloner cloner)
    73         {
    74             return new RobocodeMethodCrossover(this, cloner);
    75         }
    76 
    77         public override ISymbolicExpressionTree Crossover(IRandom random,
    78           ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1)
    79         {
    80             return Cross(random, parent0, parent1, HomologousCrossover.Value,
    81               MaximumCrossoverMethods.Value);
    82         }
    83 
    84         public static ISymbolicExpressionTree Cross(IRandom random,
    85           ISymbolicExpressionTree parent0, ISymbolicExpressionTree parent1,
    86           bool homologous, int maximumCrossoverMethods)
    87         {
    88             // select a random crossover point in the first parent
    89             List<CutPoint> crossoverPoints0;
    90             SelectCrossoverPoint(random, parent0, maximumCrossoverMethods, out crossoverPoints0);
    91 
    92             foreach (CutPoint c in crossoverPoints0)
    93             {
    94                 List<ISymbolicExpressionTreeNode> allowedBranches = new List<ISymbolicExpressionTreeNode>();
    95                 parent1.Root.ForEachNodePostfix((n) =>
    96                 {
    97                     if (n.Symbol.GetType() == c.Child.Symbol.GetType())
    98                         allowedBranches.Add(n);
    99                 });
    100 
    101                 if (allowedBranches.Count == 0)
    102                 {
    103                     break;
    104                 }
    105                 else
    106                 {
    107                     ISymbolicExpressionTreeNode branch = allowedBranches.FirstOrDefault();
    108                     int startBranchParent0 = (c.Child.SubtreeCount <= 2)? 0 : random.Next(0, c.Child.SubtreeCount - 2);
    109                     int endBranchParent0 = (c.Child.SubtreeCount <= 2) ? 1 : random.Next(startBranchParent0 + 1, c.Child.SubtreeCount - 1);
    110                     int Parent0Branches = endBranchParent0 - startBranchParent0;
    111 
    112                     for (int i = 0; i < Parent0Branches; i++)
    113                     {
    114                         c.Child.RemoveSubtree(startBranchParent0);
    115                     }
    116 
    117                     if (homologous)
    118                     {
    119                         for (int j = startBranchParent0; j <= endBranchParent0; j++)
    120                         {
    121                             c.Child.AddSubtree(branch.GetSubtree(j));
    122                         }
    123                     }
    124                     else
    125                     {
    126                         int startBranchParent1 = (branch.SubtreeCount <= 2) ? 0 : random.Next(0, branch.SubtreeCount - 2);
    127                         int endBranchParent1 = (branch.SubtreeCount <= 2) ? 1 : random.Next(startBranchParent1 + 1, branch.SubtreeCount - 1);
    128                         int Parent1Branches = endBranchParent1 - startBranchParent1;
    129 
    130                         for (int j = startBranchParent1; j <= endBranchParent1 && c.Child.SubtreeCount < c.Child.Symbol.MaximumArity; j++)
    131                         {
    132                             c.Child.AddSubtree(branch.GetSubtree(j));
    133                         }
    134                     }
    135                 }
    136             }
    137 
    138             return parent0;
    139         }
    140 
    141         private static void SelectCrossoverPoint(IRandom random, ISymbolicExpressionTree parent0,
    142             int maximumCrossoverMethods, out List<CutPoint> crossoverPoints)
    143         {
    144             List<CutPoint> MethodPoints = new List<CutPoint>();
    145             parent0.Root.ForEachNodePostfix((n) =>
    146             {
    147                 if (n.SubtreeCount > 0 && n != parent0.Root)
    148                 {
    149                     foreach (var child in n.Subtrees)
    150                     {
    151                         if (child.Symbol is Run ||
    152                             child.Symbol is OnBulletHit ||
    153                             child.Symbol is OnBulletMissed ||
    154                             child.Symbol is OnHitByBullet ||
    155                             child.Symbol is OnHitRobot ||
    156                             child.Symbol is OnHitWall ||
    157                             child.Symbol is OnScannedRobot)
    158                             MethodPoints.Add(new CutPoint(n, child));
    159                     }
    160                 }
    161             });
    162 
    163             if (maximumCrossoverMethods == 0)
    164                 crossoverPoints = MethodPoints;
     198            // select leaf node if possible
     199            allowedLeafBranches = (from branch in branches
     200                                   where branch == null || branch.SubtreeCount == 0
     201                                   select branch).ToList();
     202            if (allowedLeafBranches.Count > 0)
     203            {
     204                return allowedLeafBranches.SelectRandom(random);
     205            }
    165206            else
    166207            {
    167                 crossoverPoints = new List<CutPoint>();
    168                 for (int i = 0; i < maximumCrossoverMethods; i++)
    169                 {
    170                     CutPoint c = MethodPoints.SelectRandom(random);
    171                     crossoverPoints.Add(c);
    172                     MethodPoints.Remove(c);
    173                     if (MethodPoints.Count == 0) break;
    174                 }
    175             }
    176         }
    177 
    178         /*private static ISymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<ISymbolicExpressionTreeNode> branches, double internalNodeProbability)
    179         {
    180             if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
    181             List<ISymbolicExpressionTreeNode> allowedInternalBranches;
    182             List<ISymbolicExpressionTreeNode> allowedLeafBranches;
    183             if (random.NextDouble() < internalNodeProbability)
    184             {
    185                 // select internal node if possible
    186208                allowedInternalBranches = (from branch in branches
    187209                                           where branch != null && branch.SubtreeCount > 0
    188210                                           select branch).ToList();
    189                 if (allowedInternalBranches.Count > 0)
    190                 {
    191                     return allowedInternalBranches.SelectRandom(random);
    192                 }
    193                 else
    194                 {
    195                     // no internal nodes allowed => select leaf nodes
    196                     allowedLeafBranches = (from branch in branches
    197                                            where branch == null || branch.SubtreeCount == 0
    198                                            select branch).ToList();
    199                     return allowedLeafBranches.SelectRandom(random);
    200                 }
    201             }
    202             else
    203             {
    204                 // select leaf node if possible
    205                 allowedLeafBranches = (from branch in branches
    206                                        where branch == null || branch.SubtreeCount == 0
    207                                        select branch).ToList();
    208                 if (allowedLeafBranches.Count > 0)
    209                 {
    210                     return allowedLeafBranches.SelectRandom(random);
    211                 }
    212                 else
    213                 {
    214                     allowedInternalBranches = (from branch in branches
    215                                                where branch != null && branch.SubtreeCount > 0
    216                                                select branch).ToList();
    217                     return allowedInternalBranches.SelectRandom(random);
    218                 }
    219             }
    220         }*/
    221     }
     211                return allowedInternalBranches.SelectRandom(random);
     212            }
     213        }
     214    }*/
     215  }
    222216}
Note: See TracChangeset for help on using the changeset viewer.