Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
04/23/10 14:27:06 (15 years ago)
Author:
gkronber
Message:

Implemented manipulation operators. #937 (Data types and operators for symbolic expression tree encoding)

Location:
trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3
Files:
4 edited

Legend:

Unmodified
Added
Removed

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

    r3462 r3512  
    9898    <Compile Include="Creators\SymbolicExpressionTreeCreator.cs" />
    9999    <Compile Include="Crossovers\SymbolicExpressionTreeCrossover.cs" />
     100    <Compile Include="Manipulators\ChangeNodeTypeManipulation.cs" />
     101    <Compile Include="Manipulators\FullTreeShaker.cs" />
     102    <Compile Include="Manipulators\OnePointShaker.cs" />
    100103    <Compile Include="Manipulators\SymbolicExpressionTreeManipulator.cs" />
    101104    <Compile Include="SymbolicExpressionTreeTopLevelNode.cs" />

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Manipulators/ChangeNodeTypeManipulation.cs

    r3219 r3512  
    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.
    … …  
    2020#endregion
    2121
    22 using System.Collections.Generic;
    2322using System.Linq;
    2423using HeuristicLab.Core;
     24using HeuristicLab.Operators;
    2525using HeuristicLab.Random;
    26 using System.Diagnostics;
    27 using HeuristicLab.GP.Interfaces;
     26using HeuristicLab.Data;
     27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2828
    29 namespace HeuristicLab.Encodings.SymbolicExpressionTree {
    30   public class ChangeNodeTypeManipulation : GPManipulatorBase {
    31 
    32     public override string Description {
    33       get {
    34         return @"This manipulation operator selects a random tree-node and changes the function type.
    35 If this leads to a constraint-violation (wrong number or type of sub-trees) the sub-trees are repaired
    36 resulting in a valid tree again.";
    37       }
    38     }
     29namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Manipulators {
     30  [StorableClass]
     31  [Item("ChangeNodeTypeManipulation", "Selects a random tree node and changes the symbol size.")]
     32  public class ChangeNodeTypeManipulation : SymbolicExpressionTreeManipulator {
    3933
    4034    public ChangeNodeTypeManipulation()
    … …  
    4236    }
    4337
    44     internal override IOperation Manipulate(MersenneTwister random, IGeneticProgrammingModel gpModel, FunctionLibrary library, int maxTreeSize, int maxTreeHeight, IScope scope) {
    45       TreeGardener gardener = new TreeGardener(random, library);
    46       IFunctionTree parent = gardener.GetRandomParentNode(gpModel.FunctionTree);
    47       IFunctionTree selectedChild;
    48       int selectedChildIndex;
    49       if (parent == null) {
    50         selectedChildIndex = 0;
    51         selectedChild = gpModel.FunctionTree;
    52       } else {
    53         selectedChildIndex = random.Next(parent.SubTrees.Count);
    54         selectedChild = parent.SubTrees[selectedChildIndex];
     38    protected override void Manipulate(IRandom random, SymbolicExpressionTree symbolicExpressionTree, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight, out bool success) {
     39
     40      // select any node except the with a parent where the parent is not the root node)
     41      var manipulationPoint = (from parent in symbolicExpressionTree.Root.IterateNodesPrefix().Skip(1)
     42                               from subtree in parent.SubTrees
     43                               select new { Parent = parent, Node = subtree, Index = parent.SubTrees.IndexOf(subtree) }).SelectRandom(random);
     44      // find possible symbols for the node (also considering the existing branches below it)
     45      var allowedSymbols = from symbol in manipulationPoint.Parent.GetAllowedSymbols(manipulationPoint.Index)
     46                           where manipulationPoint.Node.SubTrees.Count <= manipulationPoint.Node.Grammar.GetMaxSubtreeCount(symbol)
     47                           where manipulationPoint.Node.SubTrees.Count >= manipulationPoint.Node.Grammar.GetMinSubtreeCount(symbol)
     48                           select symbol;
     49
     50      if (allowedSymbols.Count() <= 1) {
     51        success = false;
     52        return;
    5553      }
     54      var node = manipulationPoint.Node;
     55      // keep only symbols that are still possible considering the existing sub-trees
     56      var constrainedSymbols = from symbol in allowedSymbols
     57                               let disallowedSubtrees =
     58                                     from subtree in node.SubTrees
     59                                     where !node.Grammar.IsAllowedChild(symbol, subtree.Symbol, node.SubTrees.IndexOf(subtree))
     60                                     select subtree
     61                               where disallowedSubtrees.Count() == 0
     62                               select symbol;
     63      if (constrainedSymbols.Count() <= 1) {
     64        success = false;
     65        return;
     66      }
     67      var newSymbol = constrainedSymbols.SelectRandom(random);
    5668
    57       if (selectedChild.SubTrees.Count == 0) {
    58         IFunctionTree newTerminal = ChangeTerminalType(parent, selectedChild, selectedChildIndex, gardener, random);
    59         if (parent == null) {
    60           // no parent means the new child is the initial operator
    61           gpModel.FunctionTree = newTerminal;
    62         } else {
    63           parent.RemoveSubTree(selectedChildIndex);
    64           parent.InsertSubTree(selectedChildIndex, newTerminal);
    65           // updating the variable is not necessary because it stays the same
    66         }
    67         Debug.Assert(gardener.IsValidTree(gpModel.FunctionTree));
    68         // size and height stays the same when changing a terminal so no need to update the variables
    69         // schedule an operation to initialize the new terminal
    70         return Util.CreateInitializationOperation(TreeGardener.GetAllSubTrees(newTerminal), scope);
    71       } else {
    72         List<IFunctionTree> uninitializedBranches;
    73         IFunctionTree newFunctionTree = ChangeFunctionType(parent, selectedChild, selectedChildIndex, gardener, random, out uninitializedBranches);
    74         // in rare cases the function creates a tree that breaks the size limits
    75         // calculate the height and size difference and
    76         // check if the size of the new tree is still in the allowed bounds
    77         int oldChildSize = selectedChild.GetSize();
    78         int oldChildHeight = selectedChild.GetHeight();
    79         int newChildSize = newFunctionTree.GetSize();
    80         int newChildHeight = newFunctionTree.GetHeight();
    81         if ((gpModel.Height - oldChildHeight) + newChildHeight > maxTreeHeight ||
    82           (gpModel.Size - oldChildSize) + newChildSize > maxTreeSize) {
    83           // if size-constraints are violated don't change anything
    84           return null;
    85         }
    86         if (parent == null) {
    87           // no parent means the new function is the initial operator
    88           gpModel.FunctionTree = newFunctionTree;
    89         } else {
    90           // remove the old child
    91           parent.RemoveSubTree(selectedChildIndex);
    92           // add the new child as sub-tree of parent
    93           parent.InsertSubTree(selectedChildIndex, newFunctionTree);
    94         }
    95         // update size and height
    96         gpModel.Size = gpModel.Size - oldChildSize + newChildSize;
    97         gpModel.Height = gpModel.FunctionTree.GetHeight(); // must recalculate height because we can't know wether the manipulated branch was the deepest branch
    98         // check if whole tree is ok
    99         Debug.Assert(gardener.IsValidTree(gpModel.FunctionTree));
    100         // return a composite operation that initializes all created sub-trees
    101         return Util.CreateInitializationOperation(uninitializedBranches, scope);
    102       }
    103     }
    104 
    105     private IFunctionTree ChangeTerminalType(IFunctionTree parent, IFunctionTree child, int childIndex, TreeGardener gardener, MersenneTwister random) {
    106       IList<IFunction> allowedTerminals;
    107       if (parent == null) {
    108         allowedTerminals = gardener.Terminals;
    109       } else {
    110         allowedTerminals = new List<IFunction>();
    111         var allAllowedChildren = gardener.GetAllowedSubFunctions(parent.Function, childIndex);
    112         foreach (IFunction c in allAllowedChildren) {
    113           if (TreeGardener.IsTerminal(c)) allowedTerminals.Add(c);
    114         }
    115       }
    116       // selecting from the terminals should always work since the current child was also a terminal
    117       // so in the worst case we will just create a new terminal of the same type again.
    118       return gardener.CreateRandomTree(allowedTerminals, 1, 1);
    119     }
    120 
    121     private IFunctionTree ChangeFunctionType(IFunctionTree parent, IFunctionTree child, int childIndex, TreeGardener gardener, MersenneTwister random,
    122       out List<IFunctionTree> uninitializedBranches) {
    123       // since there are subtrees, we have to check which
    124       // and how many of the existing subtrees we can reuse.
    125       // first let's choose the function we want to use instead of the old child. For this we have to determine the
    126       // pool of allowed functions based on constraints of the parent if there is one.
    127       List<IFunction> allowedFunctions = new List<IFunction>(gardener.GetAllowedSubFunctions(parent != null ? parent.Function : null, childIndex));
    128       // try to make a tree with the same arity as the old child.
    129       int actualArity = child.SubTrees.Count;
    130       // create a new tree-node for a randomly selected function
    131       IFunction selectedFunction = allowedFunctions[random.Next(allowedFunctions.Count)];
    132       // arity of the selected operator
    133       int minArity = selectedFunction.MinSubTrees;
    134       int maxArity = selectedFunction.MaxSubTrees;
    135       // if the old child had too many sub-trees then the new child should keep as many sub-trees as possible
    136       if (actualArity > maxArity)
    137         actualArity = maxArity;
    138       if (actualArity < minArity)
    139         actualArity = minArity;
    140       // create a list that holds old sub-trees that we can reuse in the new tree
    141       List<IFunctionTree> availableSubTrees = new List<IFunctionTree>(child.SubTrees);
    142       List<IFunctionTree> freshSubTrees = new List<IFunctionTree>();
    143       IFunctionTree newTree = selectedFunction.GetTreeNode();
    144       // randomly select the sub-trees that we keep
    145       for (int i = 0; i < actualArity; i++) {
    146         // fill all sub-tree slots of the new tree
    147         // if for a given slot i there are multiple existing sub-trees that can be used in that slot
    148         // then use a random existing sub-tree. When there are no existing sub-trees
    149         // that fit in the given slot then create a new random tree and use it for the slot
    150         ICollection<IFunction> allowedSubFunctions = gardener.GetAllowedSubFunctions(selectedFunction, i);
    151         var matchingSubTrees = availableSubTrees.Where(subTree => allowedSubFunctions.Contains(subTree.Function));
    152         if (matchingSubTrees.Count() > 0) {
    153           IFunctionTree selectedSubTree = matchingSubTrees.ElementAt(random.Next(matchingSubTrees.Count()));
    154           // we can just add it as subtree
    155           newTree.InsertSubTree(i, selectedSubTree);
    156           availableSubTrees.Remove(selectedSubTree); // the branch shouldn't be available for the following slots
    157         } else {
    158           // no existing matching tree found => create a new tree of minimal size
    159           IFunctionTree freshTree = gardener.CreateRandomTree(allowedSubFunctions, 1, 1);
    160           freshSubTrees.AddRange(TreeGardener.GetAllSubTrees(freshTree));
    161           newTree.InsertSubTree(i, freshTree);
    162         }
    163       }
    164       freshSubTrees.Add(newTree);
    165       uninitializedBranches = freshSubTrees;
    166       return newTree;
     69      // replace the old node with the new node
     70      var newNode = newSymbol.CreateTreeNode();
     71      if (newNode.HasLocalParameters)
     72        newNode.ResetLocalParameters(random);
     73      foreach (var subtree in node.SubTrees)
     74        newNode.AddSubTree(subtree);
     75      manipulationPoint.Parent.RemoveSubTree(manipulationPoint.Index);
     76      manipulationPoint.Parent.InsertSubTree(manipulationPoint.Index, newNode);
     77      success = true;
    16778    }
    16879  }

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Manipulators/FullTreeShaker.cs

    r3219 r3512  
    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.
    … …  
    2525using HeuristicLab.Random;
    2626using HeuristicLab.Data;
     27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2728
    28 namespace HeuristicLab.Encodings.SymbolicExpressionTree {
    29   public class FullTreeShaker : DelegatingOperator {
    30     public override string Description {
    31       get { return "Manipulates all tree nodes for which a manipulator is defined."; }
    32     }
     29namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Manipulators {
     30  [StorableClass]
     31  [Item("FullTreeShaker", "Manipulates all nodes that have local parameters.")]
     32  public class FullTreeShaker : SymbolicExpressionTreeManipulator {
    3333
    3434    public FullTreeShaker()
    3535      : base() {
    36       AddVariableInfo(new VariableInfo("Random", "A random generator (uniform)", typeof(MersenneTwister), VariableKind.In));
    37       AddVariableInfo(new VariableInfo("FunctionLibrary", "Function library that defines function mutations", typeof(FunctionLibrary), VariableKind.In));
    38       AddVariableInfo(new VariableInfo("ShakingFactor", "Variable that determines the force of the shaking operation", typeof(DoubleData), VariableKind.In));
    39       AddVariableInfo(new VariableInfo("FunctionTree", "The function tree that should be mutated", typeof(IGeneticProgrammingModel), VariableKind.In | VariableKind.Out));
    4036    }
    4137
    42     public override IOperation Apply(IScope scope) {
    43       FunctionLibrary library = GetVariableValue<FunctionLibrary>("FunctionLibrary", scope, true);
    44       IGeneticProgrammingModel gpModel = GetVariableValue<IGeneticProgrammingModel>("FunctionTree", scope, false);
    45       MersenneTwister mt = GetVariableValue<MersenneTwister>("Random", scope, true);
    46 
    47       // save all existing sub-scopes in a backup scope
    48       Scope backupScope = new Scope("backup");
    49       foreach (Scope subScope in scope.SubScopes) {
    50         backupScope.AddSubScope(subScope);
     38    protected override void Manipulate(IRandom random, SymbolicExpressionTree symbolicExpressionTree, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight, out bool success) {
     39      foreach (var node in symbolicExpressionTree.IterateNodesPrefix()) {
     40        if (node.HasLocalParameters) {
     41          node.ShakeLocalParameters(random, 1.0);
     42        }
    5143      }
    52 
    53       // create a scope for all shaking operations
    54       Scope tempScope = new Scope("Temp. manipulation scope");
    55       scope.AddSubScope(tempScope); // scope containing a subscope for each manipulation
    56       scope.AddSubScope(backupScope); // scope containing the old subscopes
    57 
    58       // create a composite operation for all shaking operations
    59       CompositeOperation next = new CompositeOperation();
    60       next.ExecuteInParallel = false;
    61 
    62       // enqueue all shaking operations
    63       foreach (IFunctionTree subTree in TreeGardener.GetAllSubTrees(gpModel.FunctionTree).Where(x=>x.HasLocalParameters)) {
    64         IOperation shakingOperation = subTree.CreateShakingOperation(tempScope);
    65         next.AddOperation(shakingOperation);
    66       }
    67 
    68       // schedule a reducer operation to delete all temporary scopes and restore
    69       // the subscopes of the backup scope after all manipulations are finished.
    70       next.AddOperation(new AtomicOperation(new RightReducer(), scope));
    71       return next;
     44      success = true;
    7245    }
    7346  }

  • trunk/sources/HeuristicLab.Encodings.SymbolicExpressionTreeEncoding/3.3/Manipulators/OnePointShaker.cs

    r3219 r3512  
    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.
    … …  
    2525using HeuristicLab.Random;
    2626using HeuristicLab.Data;
     27using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
    2728
    28 namespace HeuristicLab.Encodings.SymbolicExpressionTree {
    29   public class OnePointShaker : DelegatingOperator {
    30     public override string Description {
    31       get { return "Selects a random node of all tree-nodes that have a manipulator defined and manipulates the selected node."; }
    32     }
     29namespace HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.Manipulators {
     30  [StorableClass]
     31  [Item("OnePointShaker", "Selects a random node with local parameters and manipulates the selected node.")]
     32  public class OnePointShaker : SymbolicExpressionTreeManipulator {
    3333
    3434    public OnePointShaker()
    3535      : base() {
    36       AddVariableInfo(new VariableInfo("FunctionLibrary", "Function library that defines mutation operations for functions", typeof(FunctionLibrary), VariableKind.In));
    37       AddVariableInfo(new VariableInfo("Random", "A random generator (uniform)", typeof(MersenneTwister), VariableKind.In));
    38       AddVariableInfo(new VariableInfo("ShakingFactor", "Factor that determines the force of the shaking operation", typeof(DoubleData), VariableKind.In));
    39       AddVariableInfo(new VariableInfo("FunctionTree", "The function tree that should be mutated", typeof(IGeneticProgrammingModel), VariableKind.In | VariableKind.Out));
    4036    }
    4137
    42     public override IOperation Apply(IScope scope) {
    43       FunctionLibrary library = GetVariableValue<FunctionLibrary>("FunctionLibrary", scope, true);
    44       IGeneticProgrammingModel gpModel = GetVariableValue<IGeneticProgrammingModel>("FunctionTree", scope, false);
    45       MersenneTwister mt = GetVariableValue<MersenneTwister>("Random", scope, true);
     38    protected override void Manipulate(IRandom random, SymbolicExpressionTree symbolicExpressionTree, ISymbolicExpressionGrammar grammar, IntValue maxTreeSize, IntValue maxTreeHeight, out bool success) {
    4639
    47       // get all nodes with local parameters
    48       var parametricBranches = TreeGardener.GetAllSubTrees(gpModel.FunctionTree).Where(branch => branch.HasLocalParameters);
    49       if (parametricBranches.Count() == 0) return null; // don't manipulate anything if there are no nodes with a manipulation operator
    50       IFunctionTree selectedBranch = parametricBranches.ElementAt(mt.Next(parametricBranches.Count()));
     40      SymbolicExpressionTreeNode selectedPoint = (from node in symbolicExpressionTree.IterateNodesPrefix()
     41                                                  where node.HasLocalParameters
     42                                                  select node).SelectRandom(random);
    5143
    52       // save the exising sub-scopes in a backup scope
    53       Scope backupScope = new Scope("backup");
    54       foreach (Scope subScope in scope.SubScopes) {
    55         backupScope.AddSubScope(subScope);
    56       }
    57 
    58       // create a scope for all shaking operations
    59       Scope tempScope = new Scope("Temp. manipulation scope");
    60      
    61       // add the new sub-scopes
    62       scope.AddSubScope(tempScope);
    63       scope.AddSubScope(backupScope);
    64 
    65       CompositeOperation next = new CompositeOperation();
    66       next.ExecuteInParallel = false;
    67       // the next operation should first manipulate and then restore the sub-scopes from the backup scope
    68       next.AddOperation(selectedBranch.CreateShakingOperation(tempScope));
    69       next.AddOperation(new AtomicOperation(new RightReducer(), scope));
    70 
    71       return next;
     44      selectedPoint.ShakeLocalParameters(random, 1.0);
     45      success = true;
    7246    }
    7347  }
Note: See TracChangeset for help on using the changeset viewer.