Free cookie consent management tool by TermsFeed Policy Generator

Ignore:
Timestamp:
07/28/09 19:24:23 (15 years ago)
Author:
gkronber
Message:

Created a branch for #713

Location:
branches/GP-Refactoring-713
Files:
2 copied

Legend:

Unmodified
Added
Removed

  • branches/GP-Refactoring-713/sources/HeuristicLab.GP/3.3/FunctionGroup.cs

    r2183 r2202  
    3131
    3232namespace HeuristicLab.GP {
    33   public class GPOperatorGroup : OperatorGroup {
    34     private Dictionary<IOperator, int> minTreeHeight = new Dictionary<IOperator, int>();
    35     private Dictionary<IOperator, int> minTreeSize = new Dictionary<IOperator, int>();
    36     private SubOperatorsConstraintAnalyser constraintAnalyser = new SubOperatorsConstraintAnalyser();
    37 
    38     public GPOperatorGroup()
    39       : base() {
    40     }
    41 
    42     public override void AddOperator(IOperator op) {
    43       base.AddOperator(op);
    44       var localVariableInfos = op.VariableInfos.Where(f => f.Local);
    45 
    46       if(op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT) == null) {
    47         op.AddVariable(new Variable(GPOperatorLibrary.MIN_TREE_HEIGHT, new IntData(-1)));
    48       }
    49       if(op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE) == null) {
    50         op.AddVariable(new Variable(GPOperatorLibrary.MIN_TREE_SIZE, new IntData(-1)));
    51       }
    52       if(op.GetVariable(GPOperatorLibrary.TICKETS) == null) {
    53         op.AddVariable(new Variable(GPOperatorLibrary.TICKETS, new DoubleData(1.0)));
    54       }
    55       foreach(IConstraint c in op.Constraints) {
    56         if(c is SubOperatorTypeConstraint || c is AllSubOperatorsTypeConstraint) c.Changed += new EventHandler(UpdateTreeBounds);
    57       }
    58       RecalculateMinimalTreeBounds();
    59       OnOperatorAdded(op);
    60     }
    61 
    62     void UpdateTreeBounds(object sender, EventArgs e) {
    63       RecalculateMinimalTreeBounds();
    64     }
    65 
    66     private void RecalculateMinimalTreeBounds() {
    67       minTreeHeight.Clear();
    68       minTreeSize.Clear();
    69       constraintAnalyser.AllPossibleOperators = Operators;
    70 
    71       foreach(IOperator op in Operators) {
    72         ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data = RecalculateMinimalTreeHeight(op);
    73         ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data = RecalculateMinimalTreeSize(op);
    74       }
    75     }
    76 
    77     private int RecalculateMinimalTreeSize(IOperator op) {
    78       // check for memoized value
    79       if(minTreeSize.ContainsKey(op)) {
    80         return minTreeSize[op];
    81       }
    82 
    83       int minArity;
    84       int maxArity;
    85       GetMinMaxArity(op, out minArity, out maxArity);
    86       // no suboperators possible => minimalTreeSize == 1 (the current node)
    87       if(minArity == 0 && maxArity == 0) {
    88         minTreeSize[op] = 1;
    89         return 1;
    90       }
    91 
    92       // when suboperators are necessary we have to find the smallest possible tree (recursively)
    93       // the minimal size of the parent is 1 + the sum of the minimal sizes of all subtrees
    94       int subTreeSizeSum = 0;
    95 
    96       // mark the currently processed operator to prevent infinite recursions and stack overflow
    97       minTreeSize[op] = 9999;
    98       for(int i = 0; i < minArity; i++) {
    99         // calculate the minTreeSize of all allowed sub-operators
    100         // if the list of allowed suboperators is empty because the operator needs suboperators
    101         // but there are no valid suboperators defined in the current group then we just use an impossible
    102         // tree size here to indicate that there was a problem.
    103         // usually as more operators are added to the group the problem will be corrected (by adding the missing operator).
    104         // however if the missing operator is never added the high min tree size here has the effect that this operator
    105         // will not be included in generated subtrees because the resulting size would always be higher than a reasonably set
    106         // maximal tree size.
    107         int minSubTreeSize = constraintAnalyser.GetAllowedOperators(op, i).Select(subOp => RecalculateMinimalTreeSize(subOp))
    108           .Concat(Enumerable.Repeat(9999, 1)).Min();
    109         subTreeSizeSum += minSubTreeSize;
    110       }
    111 
    112       minTreeSize[op] = subTreeSizeSum + 1;
    113       return subTreeSizeSum + 1;
    114     }
    115 
    116     private int RecalculateMinimalTreeHeight(IOperator op) {
    117       // check for memoized value
    118       if(minTreeHeight.ContainsKey(op)) {
    119         return minTreeHeight[op];
    120       }
    121 
    122       int minArity;
    123       int maxArity;
    124       GetMinMaxArity(op, out minArity, out maxArity);
    125       // no suboperators possible => minimalTreeHeight == 1
    126       if(minArity == 0 && maxArity == 0) {
    127         minTreeHeight[op] = 1;
    128         return 1;
    129       }
    130 
    131       // when suboperators are necessary we have to find the smallest possible tree (recursively)
    132       // the minimal height of the parent is 1 + the height of the largest subtree
    133       int maxSubTreeHeight = 0;
    134 
    135       // mark the currently processed operator to prevent infinite recursions leading to stack overflow
    136       minTreeHeight[op] = 9999;
    137       for(int i = 0; i < minArity; i++) {
    138         // calculate the minTreeHeight of all possible sub-operators.
    139         // use the smallest possible subTree as lower bound for the subTreeHeight.
    140         // if the list of allowed suboperators is empty because the operator needs suboperators
    141         // but there are no valid suboperators defined in the current group then we use an impossible tree height
    142         // to indicate that there was a problem.
    143         // usually as more operators are added to the group the problem will be corrected (by adding the missing operator).
    144         // however if the missing operator is never added the high min tree height here has the effect that this operator
    145         // will not be included in generated subtrees because the resulting (virtual) height would always be higher than a reasonably set
    146         // maximal tree height.
    147         int minSubTreeHeight = constraintAnalyser.GetAllowedOperators(op, i).Select(subOp => RecalculateMinimalTreeHeight(subOp))
    148           .Concat(Enumerable.Repeat(9999, 1)).Min();
    149 
    150         // if the smallest height of this subtree is larger than all other subtrees before we have to update the min height of the parent
    151         if(minSubTreeHeight > maxSubTreeHeight) {
    152           maxSubTreeHeight = minSubTreeHeight;
    153         }
    154       }
    155 
    156       minTreeHeight[op] = maxSubTreeHeight + 1;
    157       return maxSubTreeHeight + 1;
    158     }
    159 
    160     private void GetMinMaxArity(IOperator op, out int minArity, out int maxArity) {
    161       foreach(IConstraint constraint in op.Constraints) {
    162         NumberOfSubOperatorsConstraint theConstraint = constraint as NumberOfSubOperatorsConstraint;
    163         if(theConstraint != null) {
    164           minArity = theConstraint.MinOperators.Data;
    165           maxArity = theConstraint.MaxOperators.Data;
    166           return;
    167         }
    168       }
    169       // the default arity is 2
    170       minArity = 2;
    171       maxArity = 2;
    172     }
    173 
    174     public override void AddSubGroup(IOperatorGroup group) {
    175       throw new NotSupportedException();
    176     }
    177 
    178     public override void RemoveOperator(IOperator op) {
    179       base.RemoveOperator(op);
    180       op.RemoveVariable(GPOperatorLibrary.MIN_TREE_SIZE);
    181       op.RemoveVariable(GPOperatorLibrary.MIN_TREE_HEIGHT);
    182       op.RemoveVariable(GPOperatorLibrary.TICKETS);
    183       foreach(IConstraint c in op.Constraints) {
    184         if(c is SubOperatorTypeConstraint || c is AllSubOperatorsTypeConstraint) c.Changed -= new EventHandler(UpdateTreeBounds);
    185       }
    186 
    187       // remove the operator from the allowed sub-functions of the remaining operators
    188       foreach(IOperator o in Operators) {
    189         if(o != op) {
    190           foreach(IConstraint c in o.Constraints) {
    191             if(c is SubOperatorTypeConstraint) {
    192               ((SubOperatorTypeConstraint)c).RemoveOperator(op);
    193             } else if(c is AllSubOperatorsTypeConstraint) {
    194               ((AllSubOperatorsTypeConstraint)c).RemoveOperator(op);
    195             }
    196           }
    197         }
    198       }
    199       OnOperatorRemoved(op);
    200     }
    201 
    202     public override void RemoveSubGroup(IOperatorGroup group) {
    203       throw new NotSupportedException();
    204     }
    205 
    206     public event EventHandler OperatorAdded;
    207     public event EventHandler OperatorRemoved;
    208 
    209     protected virtual void OnOperatorAdded(IOperator op) {
    210       if(OperatorAdded != null) {
    211         OperatorAdded(this, new OperatorEventArgs(op));
    212       }
    213     }
    214     protected virtual void OnOperatorRemoved(IOperator op) {
    215       if(OperatorRemoved != null) {
    216         OperatorRemoved(this, new OperatorEventArgs(op));
    217       }
    218     }
    219   }
    220 
    221   internal class OperatorEventArgs : EventArgs {
    222     public IOperator op;
    223 
    224     public OperatorEventArgs(IOperator op) {
    225       this.op = op;
    226     }
    227   }
     33  public class FunctionGroup : StorableBase {
    22834}
Note: See TracChangeset for help on using the changeset viewer.