Free cookie consent management tool by TermsFeed Policy Generator

Changeset 437


Ignore:
Timestamp:
08/04/08 08:30:52 (16 years ago)
Author:
gkronber
Message:

fixed #228 by simplifying the crossover operator

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/sources/HeuristicLab.StructureIdentification/Recombination/SizeFairCrossOver.cs

    r324 r437  
    3838      get {
    3939        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 root 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 the operator randomly either goes
    42 up in P0 (parent of N0) or down in P1 (random child of N1) until a valid configuration is found.";
     40And replaces the branch with root0 N0 in P0 with N1 from P1 if the tree-size limits are not violated.
     41When recombination with N0 and N1 would create a tree that is too large or invalid the operator randomly selects new N0 and N1
     42until a valid configuration is found.";
    4343      }
    4444    }
     
    122122        }
    123123
    124         // save the root because later on we change tree0 and tree1 while searching a valid tree configuration
    125         IFunctionTree root = tree0;
     124        // save the roots because later on we change tree0 and tree1 while searching a valid tree configuration
     125        IFunctionTree root0 = tree0;
     126        IFunctionTree root1 = tree1;
     127        int root0Height = tree0Height;
     128        int root1Height = tree1Height;
    126129        int rootSize = tree0Size;
    127130
    128131        // select a random suboperators of the two trees at a random level
    129         int tree0Level = random.Next(tree0Height - 1); // since we checked before that the height of tree0 is > 1 this is OK
    130         int tree1Level = random.Next(tree1Height);
     132        int tree0Level = random.Next(root0Height - 1); // since we checked before that the height of tree0 is > 1 this is OK
     133        int tree1Level = random.Next(root1Height);
    131134        tree0 = gardener.GetRandomBranch(tree0, tree0Level);
    132135        tree1 = gardener.GetRandomBranch(tree1, tree1Level);
     
    152155          }
    153156        }
    154 
    155157        while(possibleChildIndices.Count == 0) {
    156158          // we couln't find a possible configuration given the current tree0 and tree1
     
    159161          //  - appending tree1 as child of tree0 would create a tree that exceedes the maxTreeHeight
    160162          //  - replacing any child of tree0 with tree1 woulde create a tree that exceedes the maxTeeSize
    161           // thus we have to either:
    162           //  - go up in tree0 => the insert position allows larger trees
    163           //  - go down in tree1 => the tree that is inserted becomes smaller
    164           //  - however we have to get lucky to solve the 'allowed sub-trees' problem
    165           if(tree1Height == 1 || (tree0Level > 0 && random.Next(2) == 0)) {
    166             // go up in tree0
    167             tree0Level--;
    168             tree0 = gardener.GetRandomBranch(root, tree0Level);
    169           } else if(tree1.SubTrees.Count > 0) {
    170             // go down in node2:
    171             tree1 = tree1.SubTrees[random.Next(tree1.SubTrees.Count)];
    172             tree1Size = tree1.Size;
    173             tree1Height = tree1.Height;
    174           } else {
    175             // could neither go up or down ... don't know what to do ... give up
    176             throw new InvalidProgramException();
    177           }
    178 
     163          // thus we just try until we find a valid configuration
     164
     165          tree0Level = random.Next(root0Height - 1);
     166          tree1Level = random.Next(root1Height);
     167          tree0 = gardener.GetRandomBranch(root0, tree0Level);
     168          tree1 = gardener.GetRandomBranch(root1, tree1Level);
     169
     170          // recalculate the size and height of tree1 (the one that we want to insert) because we need to check constraints later on
     171          tree1Size = tree1.Size;
     172          tree1Height = tree1.Height;
    179173          // recalculate the list of possible indices
    180174          possibleChildIndices.Clear();
     
    191185          }
    192186        }
    193 
    194         // no possible configuration found this indicates that there is a bigger problem
    195         if(possibleChildIndices.Count == 0) {
    196           throw new InvalidProgramException();
    197         }
    198 
    199187        // replace the existing sub-tree at a random index in tree0 with tree1
    200188        int selectedIndex = possibleChildIndices[random.Next(possibleChildIndices.Count)];
     
    204192        // no new operators where needed
    205193        newBranches = new List<IFunctionTree>();
    206         return root;
     194        return root0;
    207195      }
    208196    }
Note: See TracChangeset for help on using the changeset viewer.