Free cookie consent management tool by TermsFeed Policy Generator

source: trunk/sources/HeuristicLab.StructureIdentification/GPOperatorGroup.cs @ 123

Last change on this file since 123 was 2, checked in by swagner, 17 years ago

Added HeuristicLab 3.0 sources from former SVN repository at revision 52

File size: 12.9 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;
31
32namespace HeuristicLab.StructureIdentification {
33  public class GPOperatorGroup : OperatorGroup {
34
35    public GPOperatorGroup()
36      : base() {
37    }
38
39    public override void AddOperator(IOperator op) {
40      base.AddOperator(op);
41
42      var localVariableInfos = op.VariableInfos.Where(f => f.Local);
43
44      if(op.GetVariable(GPOperatorLibrary.MANIPULATION) == null) {
45        CombinedOperator manipulationOperator = new CombinedOperator();
46        SequentialProcessor manipulationSequence = new SequentialProcessor();
47        foreach(IVariableInfo variableInfo in localVariableInfos) {
48          IOperator manipulator = GetDefaultManipulationOperator(variableInfo);
49          if (manipulator != null) {
50            manipulationSequence.AddSubOperator(manipulator);
51          }
52        }
53        if(manipulationSequence.SubOperators.Count > 0) {
54          op.AddVariable(new Variable(GPOperatorLibrary.MANIPULATION, manipulationOperator));
55
56          manipulationOperator.OperatorGraph.AddOperator(manipulationSequence);
57          manipulationOperator.OperatorGraph.InitialOperator = manipulationSequence;
58          foreach(IOperator subOp in manipulationSequence.SubOperators) {
59            manipulationOperator.OperatorGraph.AddOperator(subOp);
60          }
61        }
62      }
63
64      if(op.GetVariable(GPOperatorLibrary.INITIALIZATION) == null) {
65        CombinedOperator initOperator = new CombinedOperator();
66        SequentialProcessor initSequence = new SequentialProcessor();
67        foreach(IVariableInfo variableInfo in localVariableInfos) {
68          IOperator initializer = GetDefaultInitOperator(variableInfo);
69          if (initializer != null) {
70            initSequence.AddSubOperator(initializer);
71          }
72        }
73        if(initSequence.SubOperators.Count > 0) {
74          op.AddVariable(new Variable(GPOperatorLibrary.INITIALIZATION, initOperator));
75          initOperator.OperatorGraph.AddOperator(initSequence);
76          initOperator.OperatorGraph.InitialOperator = initSequence;
77          foreach(IOperator subOp in initSequence.SubOperators) {
78            initOperator.OperatorGraph.AddOperator(subOp);
79          }
80        }
81      }
82
83      // add a new typeid if necessary
84      if(op.GetVariable(GPOperatorLibrary.TYPE_ID) == null) {
85        op.AddVariable(new Variable(GPOperatorLibrary.TYPE_ID, new StringData(Guid.NewGuid().ToString())));
86      }
87
88      if(op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT) == null) {
89        op.AddVariable(new Variable(GPOperatorLibrary.MIN_TREE_HEIGHT, new IntData(-1)));
90      }
91      if(op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE) == null) {
92        op.AddVariable(new Variable(GPOperatorLibrary.MIN_TREE_SIZE, new IntData(-1)));
93      }
94      if(op.GetVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS) == null) {
95        op.AddVariable(new Variable(GPOperatorLibrary.ALLOWED_SUBOPERATORS, new ItemList()));
96      }
97
98      RecalculateAllowedSuboperators();
99      RecalculateMinimalTreeBounds();
100
101      OnOperatorAdded(op);
102    }
103
104
105    private Dictionary<string, int> minTreeHeight = new Dictionary<string, int>();
106    private Dictionary<string, int> minTreeSize = new Dictionary<string, int>();
107    private SubOperatorsConstraintAnalyser constraintAnalyser = new SubOperatorsConstraintAnalyser();
108
109    private void RecalculateAllowedSuboperators() {
110      foreach(IOperator op in Operators) {
111        RecalculateAllowedSuboperators(op);
112      }
113    }
114
115    private void RecalculateAllowedSuboperators(IOperator op) {
116      constraintAnalyser.AllPossibleOperators = Operators;
117      int minArity;
118      int maxArity;
119      GetMinMaxArity(op, out minArity, out maxArity);
120      ItemList slotsList = (ItemList)op.GetVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS).Value;
121      slotsList.Clear();
122      for(int i = 0; i < maxArity; i++) {
123        ItemList slotList = new ItemList();
124        foreach(IOperator allowedOp in constraintAnalyser.GetAllowedOperators(op, i)) {
125          slotList.Add(allowedOp);
126        }
127        slotsList.Add(slotList);
128      }
129    }
130
131
132    private void RecalculateMinimalTreeBounds() {
133      minTreeHeight.Clear();
134      minTreeSize.Clear();
135      constraintAnalyser.AllPossibleOperators = Operators;
136
137      foreach(IOperator op in Operators) {
138        ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_HEIGHT).Value).Data = RecalculateMinimalTreeHeight(op);
139        ((IntData)op.GetVariable(GPOperatorLibrary.MIN_TREE_SIZE).Value).Data = RecalculateMinimalTreeSize(op);
140      }
141    }
142
143    private int RecalculateMinimalTreeSize(IOperator op) {
144      string typeId = GetTypeId(op);
145      // check for memoized value
146      if(minTreeSize.ContainsKey(typeId)) {
147        return minTreeSize[typeId];
148      }
149
150      int minArity;
151      int maxArity;
152      GetMinMaxArity(op, out minArity, out maxArity);
153      // no suboperators possible => minimalTreeSize == 1 (the current node)
154      if(minArity == 0 && maxArity == 0) {
155        minTreeSize[typeId] = 1;
156        return 1;
157      }
158
159      // when suboperators are necessary we have to find the smallest possible tree (recursively)
160      // the minimal size of the parent is 1 + the sum of the minimal sizes of all subtrees
161      int subTreeSizeSum = 0;
162
163      // mark the currently processed operator to prevent infinite recursions and stack overflow
164      minTreeSize[typeId] = 9999;
165      for(int i = 0; i < minArity; i++) {
166        // calculate the minTreeSize of all allowed sub-operators
167        // if the list of allowed suboperators is empty because the operator needs suboperators
168        // but there are no valid suboperators defined in the current group then we just use an impossible
169        // tree size here to indicate that there was a problem.
170        // usually as more operators are added to the group the problem will be corrected (by adding the missing operator).
171        // however if the missing operator is never added the high min tree size here has the effect that this operator
172        // will not be included in generated subtrees because the resulting size would always be higher than a reasonably set
173        // maximal tree size.
174        int minSubTreeSize = constraintAnalyser.GetAllowedOperators(op, i).Select(subOp => RecalculateMinimalTreeSize(subOp))
175          .Concat(Enumerable.Repeat(9999, 1)).Min();
176        subTreeSizeSum += minSubTreeSize;
177      }
178
179      minTreeSize[typeId] = subTreeSizeSum + 1;
180      return subTreeSizeSum + 1;
181    }
182
183
184    private int RecalculateMinimalTreeHeight(IOperator op) {
185      string typeId = GetTypeId(op);
186      // check for memoized value
187      if(minTreeHeight.ContainsKey(typeId)) {
188        return minTreeHeight[typeId];
189      }
190
191      int minArity;
192      int maxArity;
193      GetMinMaxArity(op, out minArity, out maxArity);
194      // no suboperators possible => minimalTreeHeight == 1
195      if(minArity == 0 && maxArity == 0) {
196        minTreeHeight[typeId] = 1;
197        return 1;
198      }
199
200      // when suboperators are necessary we have to find the smallest possible tree (recursively)
201      // the minimal height of the parent is 1 + the height of the largest subtree
202      int maxSubTreeHeight = 0;
203
204      // mark the currently processed operator to prevent infinite recursions leading to stack overflow
205      minTreeHeight[typeId] = 9999;
206      for(int i = 0; i < minArity; i++) {
207        // calculate the minTreeHeight of all possible sub-operators.
208        // use the smallest possible subTree as lower bound for the subTreeHeight.
209        // if the list of allowed suboperators is empty because the operator needs suboperators
210        // but there are no valid suboperators defined in the current group then we use an impossible tree height
211        // to indicate that there was a problem.
212        // usually as more operators are added to the group the problem will be corrected (by adding the missing operator).
213        // however if the missing operator is never added the high min tree height here has the effect that this operator
214        // will not be included in generated subtrees because the resulting (virtual) height would always be higher than a reasonably set
215        // maximal tree height.
216        int minSubTreeHeight = constraintAnalyser.GetAllowedOperators(op, i).Select(subOp => RecalculateMinimalTreeHeight(subOp))
217          .Concat(Enumerable.Repeat(9999, 1)).Min();
218
219        // if the smallest height of this subtree is larger than all other subtrees before we have to update the min height of the parent
220        if(minSubTreeHeight > maxSubTreeHeight) {
221          maxSubTreeHeight = minSubTreeHeight;
222        }
223      }
224
225      minTreeHeight[typeId] = maxSubTreeHeight + 1;
226      return maxSubTreeHeight + 1;
227    }
228
229    private void GetMinMaxArity(IOperator op, out int minArity, out int maxArity) {
230      foreach(IConstraint constraint in op.Constraints) {
231        NumberOfSubOperatorsConstraint theConstraint = constraint as NumberOfSubOperatorsConstraint;
232        if(theConstraint != null) {
233          minArity = theConstraint.MinOperators.Data;
234          maxArity = theConstraint.MaxOperators.Data;
235          return;
236        }
237      }
238      // the default arity is 2
239      minArity = 2;
240      maxArity = 2;
241    }
242
243    private string GetTypeId(IOperator op) {
244      return ((StringData)op.GetVariable(GPOperatorLibrary.TYPE_ID).Value).Data;
245    }
246
247
248    private IOperator GetDefaultManipulationOperator(IVariableInfo variableInfo) {
249      IOperator shaker;
250      if(variableInfo.DataType == typeof(ConstrainedDoubleData) ||
251        variableInfo.DataType == typeof(ConstrainedIntData) ||
252        variableInfo.DataType == typeof(DoubleData) ||
253        variableInfo.DataType == typeof(IntData)) {
254        shaker = new UniformRandomAdder();
255      } else {
256        return null;
257      }
258      shaker.GetVariableInfo("Value").ActualName = variableInfo.FormalName;
259      shaker.Name = variableInfo.FormalName + " manipulation";
260      return shaker;
261    }
262
263    private IOperator GetDefaultInitOperator(IVariableInfo variableInfo) {
264      IOperator shaker;
265      if(variableInfo.DataType == typeof(ConstrainedDoubleData) ||
266        variableInfo.DataType == typeof(ConstrainedIntData) ||
267        variableInfo.DataType == typeof(DoubleData) ||
268        variableInfo.DataType == typeof(IntData)) {
269        shaker = new UniformRandomizer();
270      } else {
271        return null;
272      }
273      shaker.GetVariableInfo("Value").ActualName = variableInfo.FormalName;
274      shaker.Name = variableInfo.FormalName + " initialization";
275      return shaker;
276    }
277
278
279    public override void AddSubGroup(IOperatorGroup group) {
280      throw new NotSupportedException();
281    }
282
283    public override void RemoveOperator(IOperator op) {
284      base.RemoveOperator(op);
285
286      op.RemoveVariable(GPOperatorLibrary.MANIPULATION);
287      op.RemoveVariable(GPOperatorLibrary.INITIALIZATION);
288      op.RemoveVariable(GPOperatorLibrary.TYPE_ID);
289      op.RemoveVariable(GPOperatorLibrary.MIN_TREE_SIZE);
290      op.RemoveVariable(GPOperatorLibrary.MIN_TREE_HEIGHT);
291      op.RemoveVariable(GPOperatorLibrary.ALLOWED_SUBOPERATORS);
292
293      OnOperatorRemoved(op);
294    }
295
296    public override void RemoveSubGroup(IOperatorGroup group) {
297      throw new NotSupportedException();
298    }
299
300    public event EventHandler OperatorAdded;
301    public event EventHandler OperatorRemoved;
302
303    protected virtual void OnOperatorAdded(IOperator op) {
304      if(OperatorAdded != null) {
305        OperatorAdded(this, new OperatorEventArgs(op));
306      }
307    }
308    protected virtual void OnOperatorRemoved(IOperator op) {
309      if(OperatorRemoved != null) {
310        OperatorRemoved(this, new OperatorEventArgs(op));
311      }
312    }
313  }
314
315
316  internal class OperatorEventArgs : EventArgs {
317    public IOperator op;
318
319    public OperatorEventArgs(IOperator op) {
320      this.op = op;
321    }
322  }
323}
Note: See TracBrowser for help on using the repository browser.