Free cookie consent management tool by TermsFeed Policy Generator

Changeset 617


Ignore:
Timestamp:
10/02/08 00:10:14 (16 years ago)
Author:
gkronber
Message:

renamed the crossover operator that we used as default in HL2 and HL3 to StandardCrossOver and implemented SizeFairCrossOver (#108)

Location:
trunk/sources/HeuristicLab.StructureIdentification
Files:
1 added
2 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.StructureIdentification/HeuristicLab.StructureIdentification.csproj

    r582 r617  
    33    <Configuration Condition=" '$(Configuration)' == '' ">Debug</Configuration>
    44    <Platform Condition=" '$(Platform)' == '' ">AnyCPU</Platform>
    5     <ProductVersion>9.0.30729</ProductVersion>
     5    <ProductVersion>9.0.21022</ProductVersion>
    66    <SchemaVersion>2.0</SchemaVersion>
    77    <ProjectGuid>{5948F299-0A5E-43B9-8F17-2D15298EEC34}</ProjectGuid>
     
    101101    <Compile Include="Properties\AssemblyInfo.cs" />
    102102    <Compile Include="RampedTreeCreator.cs" />
     103    <Compile Include="Recombination\StandardCrossOver.cs" />
    103104    <Compile Include="Recombination\SizeFairCrossOver.cs" />
    104105    <Compile Include="TreeGardener.cs" />
  • trunk/sources/HeuristicLab.StructureIdentification/Recombination/SizeFairCrossOver.cs

    r526 r617  
    3333
    3434namespace HeuristicLab.StructureIdentification {
     35  /// <summary>
     36  /// Implementation of a size fair crossover operator as described in:
     37  /// William B. Langdon
     38  /// Size Fair and Homologous Tree Genetic Programming Crossovers,
     39  /// Genetic Programming and Evolvable Machines, Vol. 1, Number 1/2, pp. 95-119, April 2000
     40  /// </summary>
    3541  public class SizeFairCrossOver : OperatorBase {
    3642    private const int MAX_RECOMBINATION_TRIES = 20;
    3743    public override string Description {
    3844      get {
    39         return @"Takes two parent individuals P0 and P1 each. Selects a random node N0 of P0 and a random node N1 of P1.
    40 And replaces the branch with root0 N0 in P0 with N1 from P1 if the tree-size limits are not violated.
    41 When recombination with N0 and N1 would create a tree that is too large or invalid the operator randomly selects new N0 and N1
    42 until a valid configuration is found.";
     45        return @"";
    4346      }
    4447    }
     
    130133        int rootSize = tree0Size;
    131134
    132         // select a random suboperators of the two trees at a random level
    133         int tree0Level = random.Next(root0Height - 1); // since we checked before that the height of tree0 is > 1 this is OK
    134         int tree1Level = random.Next(root1Height);
    135         tree0 = gardener.GetRandomBranch(tree0, tree0Level);
    136         tree1 = gardener.GetRandomBranch(tree1, tree1Level);
    137 
    138         // recalculate the size and height of tree1 (the one that we want to insert) because we need to check constraints later on
    139         tree1Size = tree1.Size;
    140         tree1Height = tree1.Height;
    141 
    142         List<int> possibleChildIndices = new List<int>();
    143 
    144         // Now tree0 is supposed to take tree1 as one if its children. If this is not possible,
    145         // then go down in either of the two trees as far as possible. If even then it is not possible
    146         // to merge the trees then throw an exception
    147         // find the list of allowed indices (regarding allowed sub-trees, maxTreeSize and maxTreeHeight)
    148         for(int i = 0; i < tree0.SubTrees.Count; i++) {
    149           int subTreeSize = tree0.SubTrees[i].Size;
    150 
    151           // the index is ok when the function is allowed as sub-tree and we don't violate the maxSize and maxHeight constraints
    152           if(gardener.GetAllowedSubFunctions(tree0.Function, i).Contains(tree1.Function) &&
    153             rootSize - subTreeSize + tree1Size < maxTreeSize &&
    154             tree0Level + tree1Height < maxTreeHeight) {
    155             possibleChildIndices.Add(i);
    156           }
    157         }
     135        // select a random suboperator of the 'receiving' tree
     136        IFunctionTree crossoverPoint = gardener.GetRandomParentNode(root0);
     137        int removedBranchIndex;
     138        IFunctionTree removedBranch;
     139        IList<IFunction> allowedFunctions;
     140        if(crossoverPoint == null) {
     141          removedBranchIndex = 0;
     142          removedBranch = root0;
     143          allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
     144        } else {
     145          removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
     146          removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
     147          allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
     148        }
     149        int removedBranchSize = removedBranch.Size;
     150        int maxBranchSize = maxTreeSize - (root0.Size - removedBranchSize);
     151        int maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(root0, removedBranch);
     152        IFunctionTree insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, root1, removedBranchSize, maxBranchSize, maxBranchHeight);
     153
    158154        int tries = 0;
    159         while(possibleChildIndices.Count == 0) {
     155        while(insertedBranch == null) {
    160156          if(tries++ > MAX_RECOMBINATION_TRIES) {
    161157            if(random.Next() > 0.5) return root1;
    162158            else return root0;
    163159          }
    164           // we couln't find a possible configuration given the current tree0 and tree1
    165           // possible reasons for this are:
    166           //  - tree1 is not allowed as sub-tree of tree0
    167           //  - appending tree1 as child of tree0 would create a tree that exceedes the maxTreeHeight
    168           //  - replacing any child of tree0 with tree1 woulde create a tree that exceedes the maxTeeSize
    169           // thus we just try until we find a valid configuration
    170 
    171           tree0Level = random.Next(root0Height - 1);
    172           tree1Level = random.Next(root1Height);
    173           tree0 = gardener.GetRandomBranch(root0, tree0Level);
    174           tree1 = gardener.GetRandomBranch(root1, tree1Level);
    175 
    176           // recalculate the size and height of tree1 (the one that we want to insert) because we need to check constraints later on
    177           tree1Size = tree1.Size;
    178           tree1Height = tree1.Height;
    179           // recalculate the list of possible indices
    180           possibleChildIndices.Clear();
    181           for(int i = 0; i < tree0.SubTrees.Count; i++) {
    182             int subTreeSize = tree0.SubTrees[i].Size;
    183 
    184             // when the function is allowed as sub-tree and we don't violate the maxSize and maxHeight constraints
    185             // the index is ok
    186             if(gardener.GetAllowedSubFunctions(tree0.Function, i).Contains(tree1.Function) &&
    187               rootSize - subTreeSize + tree1Size < maxTreeSize &&
    188               tree0Level + tree1Height < maxTreeHeight) {
    189               possibleChildIndices.Add(i);
    190             }
     160
     161          // retry with a different crossoverPoint       
     162          crossoverPoint = gardener.GetRandomParentNode(root0);
     163          if(crossoverPoint == null) {
     164            removedBranchIndex = 0;
     165            removedBranch = root0;
     166            allowedFunctions = gardener.GetAllowedSubFunctions(null, 0);
     167          } else {
     168            removedBranchIndex = random.Next(crossoverPoint.SubTrees.Count);
     169            removedBranch = crossoverPoint.SubTrees[removedBranchIndex];
     170            allowedFunctions = gardener.GetAllowedSubFunctions(crossoverPoint.Function, removedBranchIndex);
    191171          }
    192         }
    193         // replace the existing sub-tree at a random index in tree0 with tree1
    194         int selectedIndex = possibleChildIndices[random.Next(possibleChildIndices.Count)];
    195         tree0.RemoveSubTree(selectedIndex);
    196         tree0.InsertSubTree(selectedIndex, tree1);
    197         return root0;
     172          removedBranchSize = removedBranch.Size;
     173          maxBranchSize = maxTreeSize - (root0.Size - removedBranchSize);
     174          maxBranchHeight = maxTreeHeight - gardener.GetBranchLevel(root0, removedBranch) + 1;
     175          insertedBranch = GetReplacementBranch(random, gardener, allowedFunctions, root1, removedBranchSize, maxBranchSize, maxBranchHeight);
     176        }
     177        if(crossoverPoint != null) {
     178          // replace the branch below the crossoverpoint with the selected branch from root1
     179          crossoverPoint.RemoveSubTree(removedBranchIndex);
     180          crossoverPoint.InsertSubTree(removedBranchIndex, insertedBranch);
     181          return root0;
     182        } else {
     183          return insertedBranch;
     184        }
     185      }
     186    }
     187
     188    private IFunctionTree GetReplacementBranch(IRandom random, TreeGardener gardener, IList<IFunction> allowedFunctions, IFunctionTree tree, int removedBranchSize, int maxBranchSize, int maxBranchHeight) {
     189      var branches = gardener.GetAllSubTrees(tree).Where(t => allowedFunctions.Contains(t.Function) && t.Size < maxBranchSize && t.Height < maxBranchHeight)
     190        .Select(t => new { Tree = t, Size = t.Size }).Where(s => s.Size < 2 * removedBranchSize + 1);
     191
     192      var shorterBranches = branches.Where(t => t.Size < removedBranchSize);
     193      var longerBranches = branches.Where(t => t.Size > removedBranchSize);
     194      var equalLengthBranches = branches.Where(t => t.Size == removedBranchSize);
     195
     196      if(shorterBranches.Count() == 0 || longerBranches.Count() == 0) {
     197        if(equalLengthBranches.Count() == 0) {
     198          return null;
     199        } else {
     200          return equalLengthBranches.ElementAt(random.Next(equalLengthBranches.Count())).Tree;
     201        }
     202      } else {
     203        // invariant: |shorterBranches| > 0  and |longerBranches| > 0
     204        double pEqualLength = equalLengthBranches.Count() > 0 ? 1.0 / removedBranchSize : 0.0;
     205        double pLonger = (1.0 - pEqualLength) / (longerBranches.Count() * (1.0 + longerBranches.Average(t => t.Size) / shorterBranches.Average(t => t.Size)));
     206        double pShorter = (1.0 - pEqualLength - pLonger);
     207
     208        double r = random.NextDouble();
     209        if(r < pLonger) {
     210          return longerBranches.ElementAt(random.Next(longerBranches.Count())).Tree;
     211        } else if(r < pLonger + pShorter) {
     212          return shorterBranches.ElementAt(random.Next(shorterBranches.Count())).Tree;
     213        } else {
     214          return equalLengthBranches.ElementAt(random.Next(equalLengthBranches.Count())).Tree;
     215        }
    198216      }
    199217    }
Note: See TracChangeset for help on using the changeset viewer.