Free cookie consent management tool by TermsFeed Policy Generator

source: branches/Operator Architecture Refactoring/HeuristicLab.GP/3.4/GPOperatorGroup.cs @ 1992

Last change on this file since 1992 was 1914, checked in by epitzer, 15 years ago

Migration of DataAnalysis, GP, GP.StructureIdentification and Modeling to new Persistence-3.3 (#603)

File size: 9.4 KB
Line 
1#region License Information
2/* HeuristicLab
3 * Copyright (C) 2002-2008 Heuristic and Evolutionary Algorithms Laboratory (HEAL)
4 *
5 * This file is part of HeuristicLab.
6 *
7 * HeuristicLab is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * HeuristicLab is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with HeuristicLab. If not, see <http://www.gnu.org/licenses/>.
19 */
20#endregion
21
22using System;
23using System.Collections.Generic;
24using System.Linq;
25using System.Text;
26using HeuristicLab.Core;
27using HeuristicLab.Operators;
28using HeuristicLab.Data;
29using HeuristicLab.Random;
30using HeuristicLab.Constraints;
31using HeuristicLab.Persistence.Default.CompositeSerializers.Storable;
32
33namespace HeuristicLab.GP {
34
35  [EmptyStorableClass]
36  public class GPOperatorGroup : OperatorGroup {
37    private Dictionary<IOperator, int> minTreeHeight = new Dictionary<IOperator, int>();
38    private Dictionary<IOperator, int> minTreeSize = new Dictionary<IOperator, int>();
39    private SubOperatorsConstraintAnalyser constraintAnalyser = new SubOperatorsConstraintAnalyser();
40
41    public GPOperatorGroup()
42      : base() {
43    }
44
45    public override void AddOperator(IOperator op) {
46      base.AddOperator(op);
47      var localVariableInfos = op.VariableInfos.Where(f => f.Local);
48
49      if(op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT) == null) {
50        op.AddVariable(new Variable(GPOperatorLibrary.MIN_TREE_HEIGHT, new IntData(-1)));
51      }
52      if(op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE) == null) {
53        op.AddVariable(new Variable(GPOperatorLibrary.MIN_TREE_SIZE, new IntData(-1)));
54      }
55      if(op.GetVariable(GPOperatorLibrary.TICKETS) == null) {
56        op.AddVariable(new Variable(GPOperatorLibrary.TICKETS, new DoubleData(1.0)));
57      }
58      foreach(IConstraint c in op.Constraints) {
59        if(c is SubOperatorTypeConstraint || c is AllSubOperatorsTypeConstraint) c.Changed += new EventHandler(UpdateTreeBounds);
60      }
61      RecalculateMinimalTreeBounds();
62      OnOperatorAdded(op);
63    }
64
65    void UpdateTreeBounds(object sender, EventArgs e) {
66      RecalculateMinimalTreeBounds();
67    }
68
69    private void RecalculateMinimalTreeBounds() {
70      minTreeHeight.Clear();
71      minTreeSize.Clear();
72      constraintAnalyser.AllPossibleOperators = Operators;
73
74      foreach(IOperator op in Operators) {
75        ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data = RecalculateMinimalTreeHeight(op);
76        ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data = RecalculateMinimalTreeSize(op);
77      }
78    }
79
80    private int RecalculateMinimalTreeSize(IOperator op) {
81      // check for memoized value
82      if(minTreeSize.ContainsKey(op)) {
83        return minTreeSize[op];
84      }
85
86      int minArity;
87      int maxArity;
88      GetMinMaxArity(op, out minArity, out maxArity);
89      // no suboperators possible => minimalTreeSize == 1 (the current node)
90      if(minArity == 0 && maxArity == 0) {
91        minTreeSize[op] = 1;
92        return 1;
93      }
94
95      // when suboperators are necessary we have to find the smallest possible tree (recursively)
96      // the minimal size of the parent is 1 + the sum of the minimal sizes of all subtrees
97      int subTreeSizeSum = 0;
98
99      // mark the currently processed operator to prevent infinite recursions and stack overflow
100      minTreeSize[op] = 9999;
101      for(int i = 0; i < minArity; i++) {
102        // calculate the minTreeSize of all allowed sub-operators
103        // if the list of allowed suboperators is empty because the operator needs suboperators
104        // but there are no valid suboperators defined in the current group then we just use an impossible
105        // tree size here to indicate that there was a problem.
106        // usually as more operators are added to the group the problem will be corrected (by adding the missing operator).
107        // however if the missing operator is never added the high min tree size here has the effect that this operator
108        // will not be included in generated subtrees because the resulting size would always be higher than a reasonably set
109        // maximal tree size.
110        int minSubTreeSize = constraintAnalyser.GetAllowedOperators(op, i).Select(subOp => RecalculateMinimalTreeSize(subOp))
111          .Concat(Enumerable.Repeat(9999, 1)).Min();
112        subTreeSizeSum += minSubTreeSize;
113      }
114
115      minTreeSize[op] = subTreeSizeSum + 1;
116      return subTreeSizeSum + 1;
117    }
118
119    private int RecalculateMinimalTreeHeight(IOperator op) {
120      // check for memoized value
121      if(minTreeHeight.ContainsKey(op)) {
122        return minTreeHeight[op];
123      }
124
125      int minArity;
126      int maxArity;
127      GetMinMaxArity(op, out minArity, out maxArity);
128      // no suboperators possible => minimalTreeHeight == 1
129      if(minArity == 0 && maxArity == 0) {
130        minTreeHeight[op] = 1;
131        return 1;
132      }
133
134      // when suboperators are necessary we have to find the smallest possible tree (recursively)
135      // the minimal height of the parent is 1 + the height of the largest subtree
136      int maxSubTreeHeight = 0;
137
138      // mark the currently processed operator to prevent infinite recursions leading to stack overflow
139      minTreeHeight[op] = 9999;
140      for(int i = 0; i < minArity; i++) {
141        // calculate the minTreeHeight of all possible sub-operators.
142        // use the smallest possible subTree as lower bound for the subTreeHeight.
143        // if the list of allowed suboperators is empty because the operator needs suboperators
144        // but there are no valid suboperators defined in the current group then we use an impossible tree height
145        // to indicate that there was a problem.
146        // usually as more operators are added to the group the problem will be corrected (by adding the missing operator).
147        // however if the missing operator is never added the high min tree height here has the effect that this operator
148        // will not be included in generated subtrees because the resulting (virtual) height would always be higher than a reasonably set
149        // maximal tree height.
150        int minSubTreeHeight = constraintAnalyser.GetAllowedOperators(op, i).Select(subOp => RecalculateMinimalTreeHeight(subOp))
151          .Concat(Enumerable.Repeat(9999, 1)).Min();
152
153        // if the smallest height of this subtree is larger than all other subtrees before we have to update the min height of the parent
154        if(minSubTreeHeight > maxSubTreeHeight) {
155          maxSubTreeHeight = minSubTreeHeight;
156        }
157      }
158
159      minTreeHeight[op] = maxSubTreeHeight + 1;
160      return maxSubTreeHeight + 1;
161    }
162
163    private void GetMinMaxArity(IOperator op, out int minArity, out int maxArity) {
164      foreach(IConstraint constraint in op.Constraints) {
165        NumberOfSubOperatorsConstraint theConstraint = constraint as NumberOfSubOperatorsConstraint;
166        if(theConstraint != null) {
167          minArity = theConstraint.MinOperators.Data;
168          maxArity = theConstraint.MaxOperators.Data;
169          return;
170        }
171      }
172      // the default arity is 2
173      minArity = 2;
174      maxArity = 2;
175    }
176
177    public override void AddSubGroup(IOperatorGroup group) {
178      throw new NotSupportedException();
179    }
180
181    public override void RemoveOperator(IOperator op) {
182      base.RemoveOperator(op);
183      op.RemoveVariable(GPOperatorLibrary.MIN_TREE_SIZE);
184      op.RemoveVariable(GPOperatorLibrary.MIN_TREE_HEIGHT);
185      op.RemoveVariable(GPOperatorLibrary.TICKETS);
186      foreach(IConstraint c in op.Constraints) {
187        if(c is SubOperatorTypeConstraint || c is AllSubOperatorsTypeConstraint) c.Changed -= new EventHandler(UpdateTreeBounds);
188      }
189
190      // remove the operator from the allowed sub-functions of the remaining operators
191      foreach(IOperator o in Operators) {
192        if(o != op) {
193          foreach(IConstraint c in o.Constraints) {
194            if(c is SubOperatorTypeConstraint) {
195              ((SubOperatorTypeConstraint)c).RemoveOperator(op);
196            } else if(c is AllSubOperatorsTypeConstraint) {
197              ((AllSubOperatorsTypeConstraint)c).RemoveOperator(op);
198            }
199          }
200        }
201      }
202      OnOperatorRemoved(op);
203    }
204
205    public override void RemoveSubGroup(IOperatorGroup group) {
206      throw new NotSupportedException();
207    }
208
209    public event EventHandler OperatorAdded;
210    public event EventHandler OperatorRemoved;
211
212    protected virtual void OnOperatorAdded(IOperator op) {
213      if(OperatorAdded != null) {
214        OperatorAdded(this, new OperatorEventArgs(op));
215      }
216    }
217    protected virtual void OnOperatorRemoved(IOperator op) {
218      if(OperatorRemoved != null) {
219        OperatorRemoved(this, new OperatorEventArgs(op));
220      }
221    }
222  }
223
224  internal class OperatorEventArgs : EventArgs {
225    public IOperator op;
226
227    public OperatorEventArgs(IOperator op) {
228      this.op = op;
229    }
230  }
231}
Note: See TracBrowser for help on using the repository browser.