Free cookie consent management tool by TermsFeed Policy Generator

Changeset 3237


Ignore:
Timestamp:
03/30/10 19:38:22 (14 years ago)
Author:
gkronber
Message:

Worked on symbolic expression tree encoding.
Added view for expression trees (simple textual view in s-exp format).
Implemented SubtreeCrossover.
Fixed bugs in ProbabilisticTreeCreator.
#937 (Data types and operators for symbolic expression tree encoding)

Location:
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3
Files:
4 added
1 deleted
7 edited
1 moved

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Creators/ProbabilisticTreeCreator.cs

    r3223 r3237  
    5151      do {
    5252        try {
    53           // determine possible root symbols to create a tree of the target size
    54           var possibleRootSymbols = from symbol in grammar.AllowedSymbols(grammar.StartSymbol, 0)
    55                                     where treeSize <= grammar.MaximalExpressionLength(symbol)
    56                                     where treeSize >= grammar.MinimalExpressionLength(symbol)
    57                                     select symbol;
    58           Symbol rootSymbol = SelectRandomSymbol(random, possibleRootSymbols);
    59           tree.Root = PTC2(random, grammar, rootSymbol, treeSize, maxTreeHeight);
     53          tree.Root = PTC2(random, grammar, grammar.StartSymbol, treeSize+1, maxTreeHeight+1);
     54          //// determine possible root symbols to create a tree of the target size
     55          //var possibleRootSymbols = from symbol in grammar.AllowedSymbols(grammar.StartSymbol, 0)
     56          //                          where treeSize <= grammar.MaximalExpressionLength(symbol)
     57          //                          where treeSize >= grammar.MinimalExpressionLength(symbol)
     58          //                          select symbol;
     59          //Symbol rootSymbol = SelectRandomSymbol(random, possibleRootSymbols);
     60          //tree.Root = PTC2(random, grammar, rootSymbol, treeSize, maxTreeHeight);
    6061        }
    6162        catch (ArgumentException) {
    … …  
    149150      int minArity = grammar.MinSubTrees(symbol);
    150151      int maxArity = grammar.MaxSubTrees(symbol);
    151       if (maxArity >= targetSize) {
     152      if (maxArity > targetSize) {
    152153        maxArity = targetSize;
    153154      }
    154155      // the min number of sub-trees has to be set to a value that is large enough so that the largest possible tree is at least tree size
    155156      // if 1..3 trees are possible and the largest possible first sub-tree is smaller larger than the target size then minArity should be at least 2
    156       int aggregatedLongestExpressionLength = 1;
     157      long aggregatedLongestExpressionLength = 0;
    157158      for (int i = 0; i < maxArity; i++) {
    158159        aggregatedLongestExpressionLength += (from s in grammar.AllowedSymbols(symbol, i)
    159                                               select grammar.MaximalExpressionLength(symbol)).Max();
     160                                              select grammar.MaximalExpressionLength(s)).Max();
    160161        if (aggregatedLongestExpressionLength < targetSize) minArity = i;
    161162        else break;
    … …  
    164165      // the max number of sub-trees has to be set to a value that is small enough so that the smallest possible tree is at most tree size
    165166      // if 1..3 trees are possible and the smallest possible first sub-tree is already larger than the target size then maxArity should be at most 0
    166       int aggregatedShortestExpressionLength = 1;
     167      long aggregatedShortestExpressionLength = 0;
    167168      for (int i = 0; i < maxArity; i++) {
    168169        aggregatedShortestExpressionLength += (from s in grammar.AllowedSymbols(symbol, i)
    169                                                select grammar.MinimalExpressionLength(symbol)).Min();
     170                                               select grammar.MinimalExpressionLength(s)).Min();
    170171        if (aggregatedShortestExpressionLength > targetSize) {
    171172          maxArity = i;

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Crossovers/SubtreeCrossover.cs

    r3232 r3237  
    11#region License Information
    22/* HeuristicLab
    3  * Copyright (C) 2002-2008 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
     3 * Copyright (C) 2002-2010 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
    44 *
    55 * This file is part of HeuristicLab.
    … …  
    2222using System.Collections.Generic;
    2323using HeuristicLab.Core;
    24 using HeuristicLab.GP.Interfaces;
     24using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     25using HeuristicLab.Data;
     26using System.Linq;
     27using System;
     28using HeuristicLab.Parameters;
     29namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    2530
    26 namespace HeuristicLab.Encodings.SymbolicExpressionTree {
    27   public class StandardCrossOver : SizeConstrictedGPCrossoverBase {
    28     private int MaxRecombinationTries { get { return 20; } }
    2931
    30     public override string Description {
    31       get {
    32         return @"Takes two parent individuals P0 and P1 each. Selects a random node N0 of P0 and a random node N1 of P1.
    33 And replaces the branch with root0 N0 in P0 with N1 from P1 if the tree-size limits are not violated.
    34 When recombination with N0 and N1 would create a tree that is too large or invalid the operator randomly selects new N0 and N1
    35 until a valid configuration is found.";
     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("SubtreeCrossover", "An operator which performs subtree swapping crossover.")]
     39  [StorableClass]
     40  public class SubtreeCrossover : SymbolicExpressionTreeCrossover {
     41    private const int MAX_TRIES = 100;
     42
     43    public IValueLookupParameter<PercentValue> InternalCrossoverPointProbabilityParameter {
     44      get { return (IValueLookupParameter<PercentValue>)Parameters["InternalCrossoverPointProbability"]; }
     45    }
     46
     47    public SubtreeCrossover()
     48      : base() {
     49      Parameters.Add(new ValueLookupParameter<PercentValue>("InternalCrossoverPointProbability", "The probability to select an internal crossover point (instead of a leaf node).", new PercentValue(0.9)));
     50    }
     51
     52    protected override SymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionGrammar grammar,
     53      SymbolicExpressionTree parent0, SymbolicExpressionTree parent1,
     54      IntValue maxTreeSize, IntValue maxTreeHeight) {
     55      return Apply(random, grammar, parent0, parent1, InternalCrossoverPointProbabilityParameter.ActualValue.Value, maxTreeSize.Value, maxTreeHeight.Value);
     56    }
     57
     58    public static SymbolicExpressionTree Apply(IRandom random, ISymbolicExpressionGrammar grammar,
     59      SymbolicExpressionTree parent0, SymbolicExpressionTree parent1,
     60      double internalCrossoverPointProbability, int maxTreeSize, int maxTreeHeight) {
     61      int tries = 0;
     62      while (tries++ < MAX_TRIES) {
     63        // select a random crossover point in the first parent
     64        SymbolicExpressionTreeNode crossoverPoint0;
     65        int replacedSubtreeIndex;
     66        SelectCrossoverPoint(random, parent0, internalCrossoverPointProbability, out crossoverPoint0, out replacedSubtreeIndex);
     67
     68        // calculate the max size and height that the inserted branch can have
     69        int maxInsertedBranchSize = maxTreeSize - (parent0.Size - crossoverPoint0.SubTrees[replacedSubtreeIndex].GetSize());
     70        int maxInsertedBranchHeight = maxTreeHeight - GetBranchLevel(parent0.Root, crossoverPoint0);
     71
     72        var allowedBranches = from branch in IterateNodes(parent1.Root)
     73                              where branch.GetSize() < maxInsertedBranchSize
     74                              where branch.GetHeight() < maxInsertedBranchHeight
     75                              where grammar.AllowedSymbols(crossoverPoint0.Symbol, replacedSubtreeIndex).Contains(branch.Symbol)
     76                              select branch;
     77
     78        if (allowedBranches.Count() > 0) {
     79          var selectedBranch = SelectRandomBranch(random, allowedBranches, internalCrossoverPointProbability);
     80
     81          // manipulate the tree of parent0 in place
     82          // replace the branch in tree0 with the selected branch from tree1
     83          crossoverPoint0.RemoveSubTree(replacedSubtreeIndex);
     84          crossoverPoint0.InsertSubTree(replacedSubtreeIndex, selectedBranch);
     85          return parent0;
     86        }
     87      }
     88
     89      // TODO: we should have a way to track the number of failed crossover attempts
     90      // for now just return the first parent unchanged
     91      return parent0;
     92    }
     93
     94    private static void SelectCrossoverPoint(IRandom random, SymbolicExpressionTree parent0, double internalNodeProbability, out SymbolicExpressionTreeNode crossoverPoint, out int subtreeIndex) {
     95      var crossoverPoints = from branch in IterateNodes(parent0.Root)
     96                            where branch.SubTrees.Count > 0
     97                            from index in Enumerable.Range(0, branch.SubTrees.Count)
     98                            let p = new { CrossoverPoint = branch, SubtreeIndex = index, IsLeaf = branch.SubTrees[index].SubTrees.Count == 0 }
     99                            select p;
     100      var internalCrossoverPoints = (from p in crossoverPoints
     101                                     where !p.IsLeaf
     102                                     select p).ToList();
     103      // select internal crossover point or leaf
     104      if (random.NextDouble() < internalNodeProbability && internalCrossoverPoints.Count > 0) {
     105        var selectedCrossoverPoint = internalCrossoverPoints[random.Next(internalCrossoverPoints.Count)];
     106        crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
     107        subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
     108      } else {
     109        var leafCrossoverPoints = (from p in crossoverPoints
     110                                   where p.IsLeaf
     111                                   select p).ToList();
     112        var selectedCrossoverPoint = leafCrossoverPoints[random.Next(leafCrossoverPoints.Count)];
     113        crossoverPoint = selectedCrossoverPoint.CrossoverPoint;
     114        subtreeIndex = selectedCrossoverPoint.SubtreeIndex;
    36115      }
    37116    }
    38117
    39     internal override IFunctionTree Cross(TreeGardener gardener, IRandom random, IFunctionTree tree0, IFunctionTree tree1, int maxTreeSize, int maxTreeHeight) {
    40       int tries = 0;
    41       List<IFunctionTree> allowedCrossoverPoints = null;
    42       IFunctionTree parent0;
    43       int replacedChildIndex;
    44       do {
    45         // select a random crossover point in the first parent tree0
    46         parent0 = null;
    47         while (parent0 == null) parent0 = gardener.GetRandomParentNode(tree0);
    48         // select a random branch to replace
    49         replacedChildIndex = random.Next(parent0.SubTrees.Count);
    50 
    51         // calculate the max size and height that the inserted branch can have
    52         int maxInsertedBranchSize = maxTreeSize - (tree0.GetSize() - parent0.SubTrees[replacedChildIndex].GetSize());
    53         int maxInsertedBranchHeight = maxTreeHeight - gardener.GetBranchLevel(tree0, parent0); // branchlevel is 1 if tree0==parent0
    54 
    55         IList<IFunction> allowedFunctions = new List<IFunction>(gardener.GetAllowedSubFunctions(parent0.Function, replacedChildIndex));
    56         allowedCrossoverPoints = GetPossibleCrossoverPoints(tree1, maxInsertedBranchSize, maxInsertedBranchHeight, allowedFunctions);
    57       } while (allowedCrossoverPoints.Count == 0 && tries++ < MaxRecombinationTries);
    58 
    59       if (allowedCrossoverPoints.Count > 0) {
    60         IFunctionTree branch1 = allowedCrossoverPoints[random.Next(allowedCrossoverPoints.Count)];
    61 
    62         // replace the branch in tree0 with the selected branch from tree1
    63         parent0.RemoveSubTree(replacedChildIndex);
    64         parent0.InsertSubTree(replacedChildIndex, branch1);
     118    private static SymbolicExpressionTreeNode SelectRandomBranch(IRandom random, IEnumerable<SymbolicExpressionTreeNode> branches, double internalNodeProbability) {
     119      if (internalNodeProbability < 0.0 || internalNodeProbability > 1.0) throw new ArgumentException("internalNodeProbability");
     120      var groupedBranches = from branch in branches
     121                            group branch by branch.SubTrees.Count into g
     122                            select g;
     123      var allowedInternalBranches = (from g in groupedBranches
     124                                     where g.Key > 0
     125                                     from branch in g
     126                                     select branch).ToList();
     127      if (random.NextDouble() < internalNodeProbability && allowedInternalBranches.Count > 0) {
     128        return allowedInternalBranches[random.Next(allowedInternalBranches.Count)];
     129      } else {
     130        var allowedLeafBranches = (from g in groupedBranches
     131                                   where g.Key == 0
     132                                   from leaf in g
     133                                   select leaf).ToList();
     134        return allowedLeafBranches[random.Next(allowedLeafBranches.Count)];
    65135      }
    66       return tree0;
    67136    }
    68137
    69     private List<IFunctionTree> GetPossibleCrossoverPoints(IFunctionTree tree, int maxInsertedBranchSize, int maxInsertedBranchHeight, IList<IFunction> allowedFunctions) {
    70       List<IFunctionTree> crossoverPoints = new List<IFunctionTree>();
    71       foreach (IFunctionTree possiblePoint in TreeGardener.GetAllSubTrees(tree)) {
    72         if (allowedFunctions.Contains(possiblePoint.Function) && possiblePoint.GetSize() <= maxInsertedBranchSize && possiblePoint.GetHeight() <= maxInsertedBranchHeight)
    73           crossoverPoints.Add(possiblePoint);
     138    private static IEnumerable<SymbolicExpressionTreeNode> IterateNodes(SymbolicExpressionTreeNode root) {
     139      foreach (var subTree in root.SubTrees) {
     140        foreach (var branch in IterateNodes(subTree)) {
     141          yield return branch;
     142        }
    74143      }
    75       return crossoverPoints;
     144      yield return root;
     145    }
     146
     147    private static int GetBranchLevel(SymbolicExpressionTreeNode root, SymbolicExpressionTreeNode point) {
     148      if (root == point) return 0;
     149      foreach (var subtree in root.SubTrees) {
     150        int branchLevel = GetBranchLevel(subtree, point);
     151        if (branchLevel < int.MaxValue) return 1 + branchLevel;
     152      }
     153      return int.MaxValue;
    76154    }
    77155  }

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.3.csproj

    r3223 r3237  
    2424    <ErrorReport>prompt</ErrorReport>
    2525    <WarningLevel>4</WarningLevel>
     26    <CheckForOverflowUnderflow>true</CheckForOverflowUnderflow>
    2627  </PropertyGroup>
    2728  <PropertyGroup Condition=" '$(Configuration)|$(Platform)' == 'Release|AnyCPU' ">
    … …  
    7071      <RequiredTargetFramework>3.5</RequiredTargetFramework>
    7172    </Reference>
     73    <Reference Include="System.Drawing" />
     74    <Reference Include="System.Windows.Forms" />
    7275    <Reference Include="System.Xml.Linq">
    7376      <RequiredTargetFramework>3.5</RequiredTargetFramework>
    … …  
    8083  </ItemGroup>
    8184  <ItemGroup>
     85    <Compile Include="Crossovers\SubtreeCrossover.cs" />
    8286    <Compile Include="Interfaces\ISymbolicExpressionGrammar.cs" />
    8387    <Compile Include="Creators\ProbabilisticTreeCreator.cs" />
    … …  
    8892    <Compile Include="Properties\AssemblyInfo.cs" />
    8993    <Compile Include="Symbol.cs" />
     94    <Compile Include="SymbolicExpressionTreeCrossover.cs" />
    9095    <Compile Include="SymbolicExpressionTreeNode.cs" />
     96    <Compile Include="Views\SymbolicExpressionTreeView.cs">
     97      <SubType>UserControl</SubType>
     98    </Compile>
     99    <Compile Include="Views\SymbolicExpressionTreeView.Designer.cs">
     100      <DependentUpon>SymbolicExpressionTreeView.cs</DependentUpon>
     101    </Compile>
    91102  </ItemGroup>
    92103  <ItemGroup>
    … …  
    100111      <Name>HeuristicLab.Collections-3.3</Name>
    101112    </ProjectReference>
     113    <ProjectReference Include="..\..\HeuristicLab.Core.Views\3.3\HeuristicLab.Core.Views-3.3.csproj">
     114      <Project>{E226881D-315F-423D-B419-A766FE0D8685}</Project>
     115      <Name>HeuristicLab.Core.Views-3.3</Name>
     116    </ProjectReference>
    102117    <ProjectReference Include="..\..\HeuristicLab.Core\3.3\HeuristicLab.Core-3.3.csproj">
    103118      <Project>{C36BD924-A541-4A00-AFA8-41701378DDC5}</Project>
    … …  
    107122      <Project>{BBAB9DF5-5EF3-4BA8-ADE9-B36E82114937}</Project>
    108123      <Name>HeuristicLab.Data-3.3</Name>
     124    </ProjectReference>
     125    <ProjectReference Include="..\..\HeuristicLab.MainForm.WindowsForms\3.2\HeuristicLab.MainForm.WindowsForms-3.2.csproj">
     126      <Project>{AB687BBE-1BFE-476B-906D-44237135431D}</Project>
     127      <Name>HeuristicLab.MainForm.WindowsForms-3.2</Name>
     128    </ProjectReference>
     129    <ProjectReference Include="..\..\HeuristicLab.MainForm\3.2\HeuristicLab.MainForm-3.2.csproj">
     130      <Project>{3BD61258-31DA-4B09-89C0-4F71FEF5F05A}</Project>
     131      <Name>HeuristicLab.MainForm-3.2</Name>
    109132    </ProjectReference>
    110133    <ProjectReference Include="..\..\HeuristicLab.Operators\3.3\HeuristicLab.Operators-3.3.csproj">
    … …  
    134157  </ItemGroup>
    135158  <ItemGroup>
    136     <Folder Include="Crossovers\" />
     159    <EmbeddedResource Include="Views\SymbolicExpressionTreeView.resx">
     160      <DependentUpon>SymbolicExpressionTreeView.cs</DependentUpon>
     161    </EmbeddedResource>
     162  </ItemGroup>
     163  <ItemGroup>
    137164    <Folder Include="Manipulators\" />
    138165  </ItemGroup>

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Interfaces/ISymbolicExpressionGrammar.cs

    r3223 r3237  
    4242    int MinSubTrees(Symbol start);
    4343    int MaxSubTrees(Symbol start);
     44
     45    bool IsValidExpression(SymbolicExpressionTree expression);
    4446  }
    4547}

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionGrammar.cs

    r3223 r3237  
    8181      get { return startSymbol; }
    8282    }
    83    
     83
    8484    public IEnumerable<Symbol> AllowedSymbols(Symbol parent, int argumentIndex) {
    8585      return allowedSymbols[parent][argumentIndex];
    … …  
    106106    }
    107107
     108    public bool IsValidExpression(SymbolicExpressionTree expression) {
     109      throw new NotImplementedException();
     110    }
     111
    108112    #endregion
    109113  }

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTree.cs

    r3223 r3237  
    2626using System.Xml;
    2727using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     28using HeuristicLab.Data;
    2829
    2930namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeCrossover.cs

    r3223 r3237  
    2626using HeuristicLab.Parameters;
    2727using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
     28using System;
     29using System.Diagnostics;
    2830
    2931namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding {
    3032  /// <summary>
    31   /// A base class for operators that perform a crossover of real-valued vectors.
     33  /// A base class for operators that perform a crossover of symbolic expression trees.
    3234  /// </summary>
    33   [Item("RealVectorCrossover", "A base class for operators that perform a crossover of real-valued vectors.")]
     35  [Item("SymbolicExpressionTreeCrossover", "A base class for operators that perform a crossover of symbolic expression trees.")]
    3436  [StorableClass]
    35   public abstract class RealVectorCrossover : SingleSuccessorOperator, IRealVectorCrossover, IStochasticOperator {
     37  public abstract class SymbolicExpressionTreeCrossover : SingleSuccessorOperator, ICrossover, IStochasticOperator {
    3638    public override bool CanChangeName {
    3739      get { return false; }
    … …  
    4143      get { return (LookupParameter<IRandom>)Parameters["Random"]; }
    4244    }
    43     public ILookupParameter<ItemArray<RealVector>> ParentsParameter {
    44       get { return (SubScopesLookupParameter<RealVector>)Parameters["Parents"]; }
     45    public ILookupParameter<ItemArray<SymbolicExpressionTree>> ParentsParameter {
     46      get { return (SubScopesLookupParameter<SymbolicExpressionTree>)Parameters["Parents"]; }
    4547    }
    46     public ILookupParameter<RealVector> ChildParameter {
    47       get { return (ILookupParameter<RealVector>)Parameters["Child"]; }
     48    public ILookupParameter<SymbolicExpressionTree> ChildParameter {
     49      get { return (ILookupParameter<SymbolicExpressionTree>)Parameters["Child"]; }
    4850    }
    49     public IValueLookupParameter<DoubleMatrix> BoundsParameter {
    50       get { return (IValueLookupParameter<DoubleMatrix>)Parameters["Bounds"]; }
     51    public IValueLookupParameter<IntValue> MaxTreeSizeParameter {
     52      get { return (IValueLookupParameter<IntValue>)Parameters["MaxTreeSize"]; }
     53    }
     54    public IValueLookupParameter<IntValue> MaxTreeHeightParameter {
     55      get { return (IValueLookupParameter<IntValue>)Parameters["MaxTreeHeight"]; }
     56    }
     57    public ILookupParameter<ISymbolicExpressionGrammar> SymbolicExpressionGrammarParameter {
     58      get { return (ILookupParameter<ISymbolicExpressionGrammar>)Parameters["SymbolicExpressionGrammar"]; }
    5159    }
    5260
    53     protected RealVectorCrossover()
     61    protected SymbolicExpressionTreeCrossover()
    5462      : base() {
    5563      Parameters.Add(new LookupParameter<IRandom>("Random", "The pseudo random number generator which should be used for stochastic crossover operators."));
    56       Parameters.Add(new SubScopesLookupParameter<RealVector>("Parents", "The parent vectors which should be crossed."));
    57       Parameters.Add(new LookupParameter<RealVector>("Child", "The child vector resulting from the crossover."));
    58       Parameters.Add(new ValueLookupParameter<DoubleMatrix>("Bounds", "The lower and upper bounds of the real vector."));
     64      Parameters.Add(new SubScopesLookupParameter<SymbolicExpressionTree>("Parents", "The parent symbolic expression trees which should be crossed."));
     65      Parameters.Add(new ValueLookupParameter<IntValue>("MaxTreeSize", "The maximal size (number of nodes) of the symbolic expression tree that should be initialized."));
     66      Parameters.Add(new ValueLookupParameter<IntValue>("MaxTreeHeight", "The maximal height of the symbolic expression tree that should be initialized (a tree with one node has height = 0)."));
     67      Parameters.Add(new LookupParameter<ISymbolicExpressionGrammar>("SymbolicExpressionGrammar", "The grammar that defines the allowed symbols and syntax of the symbolic expression trees."));
     68      Parameters.Add(new LookupParameter<SymbolicExpressionTree>("Child", "The child symbolic expression tree resulting from the crossover."));
    5969    }
    6070
    6171    public sealed override IOperation Apply() {
    62       RealVector result = Cross(RandomParameter.ActualValue, ParentsParameter.ActualValue);
    63       DoubleMatrix bounds = BoundsParameter.ActualValue;
    64       if (bounds != null) BoundsChecker.Apply(result, bounds);
     72      if (ParentsParameter.ActualValue.Length != 2)
     73        throw new ArgumentException("Number of parents must be exactly two for symbolic expression tree crossover operators.");
     74
     75      SymbolicExpressionTree parent0 = ParentsParameter.ActualValue[0];
     76      SymbolicExpressionTree parent1 = ParentsParameter.ActualValue[1];
     77
     78      IRandom random = RandomParameter.ActualValue;
     79      ISymbolicExpressionGrammar grammar = SymbolicExpressionGrammarParameter.ActualValue;
     80
     81      // randomly swap parents to remove a possible bias from selection (e.g. when using gender-specific selection)
     82      if (random.NextDouble() < 0.5) {
     83        var tmp = parent0;
     84        parent0 = parent1;
     85        parent1 = tmp;
     86      }
     87
     88      SymbolicExpressionTree result = Cross(random, grammar, parent0, parent1,
     89        MaxTreeSizeParameter.ActualValue, MaxTreeHeightParameter.ActualValue);
     90      Debug.Assert(result.Size <= MaxTreeSizeParameter.ActualValue.Value);
     91      Debug.Assert(result.Height <= MaxTreeHeightParameter.ActualValue.Value);
     92      Debug.Assert(grammar.IsValidExpression(result));
    6593      ChildParameter.ActualValue = result;
    6694      return base.Apply();
    6795    }
    6896
    69     protected abstract RealVector Cross(IRandom random, ItemArray<RealVector> parents);
     97    protected abstract SymbolicExpressionTree Cross(IRandom random, ISymbolicExpressionGrammar grammar,
     98      SymbolicExpressionTree parent0, SymbolicExpressionTree parent1,
     99      IntValue maxTreeSize, IntValue maxTreeHeight);
    70100  }
    71101}

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/SymbolicExpressionTreeNode.cs

    r3223 r3237  
    9393      SubTrees.RemoveAt(index);
    9494    }
     95
     96    public override IDeepCloneable Clone(Cloner cloner) {
     97      SymbolicExpressionTreeNode clone = new SymbolicExpressionTreeNode(symbol);
     98      cloner.RegisterClonedObject(this, clone);
     99      foreach (var subtree in SubTrees) {
     100        clone.AddSubTree((SymbolicExpressionTreeNode)subtree.Clone(cloner));
     101      }
     102      return clone;
     103    }
    95104  }
    96105}
Note: See TracChangeset for help on using the changeset viewer.