Free cookie consent management tool by TermsFeed Policy Generator

Changeset 2566 for trunk


Ignore:
Timestamp:
12/21/09 16:14:40 (15 years ago)
Author:
gkronber
Message:

Added new predefined function libraries for symbolic regression algorithms. Changed CEDMA dispatcher to choose a function library randomly. #813 (GP structure-identification algorithms that use only a simple function library)

Location:
trunk/sources
Files:
6 added
2 deleted
14 edited
1 moved

Legend:

Unmodified
Added
Removed

  • trunk/sources/HeuristicLab.CEDMA.Server/3.3/HeuristicLab.CEDMA.Server-3.3.csproj

    r2391 r2566  
    140140      <Name>HeuristicLab.Data-3.2</Name>
    141141    </ProjectReference>
     142    <ProjectReference Include="..\..\HeuristicLab.GP.Interfaces\3.3\HeuristicLab.GP.Interfaces-3.3.csproj">
     143      <Project>{924B6BEA-9A99-40FE-9334-5C01E8D540EC}</Project>
     144      <Name>HeuristicLab.GP.Interfaces-3.3</Name>
     145    </ProjectReference>
     146    <ProjectReference Include="..\..\HeuristicLab.GP.StructureIdentification\3.3\HeuristicLab.GP.StructureIdentification-3.3.csproj">
     147      <Project>{74223A32-C726-4978-BE78-37113A18373C}</Project>
     148      <Name>HeuristicLab.GP.StructureIdentification-3.3</Name>
     149    </ProjectReference>
     150    <ProjectReference Include="..\..\HeuristicLab.GP\3.3\HeuristicLab.GP-3.3.csproj">
     151      <Project>{1F1CF3ED-374C-4288-995B-93F6B872F571}</Project>
     152      <Name>HeuristicLab.GP-3.3</Name>
     153    </ProjectReference>
    142154    <ProjectReference Include="..\..\HeuristicLab.Grid.HiveBridge\3.2\HeuristicLab.Grid.HiveBridge-3.2.csproj">
    143155      <Project>{DFAC1BEA-6D9D-477F-AC7B-E64977644DDB}</Project>

  • trunk/sources/HeuristicLab.CEDMA.Server/3.3/SimpleDispatcher.cs

    r2440 r2566  
    3434using HeuristicLab.Modeling.Database;
    3535using HeuristicLab.DataAnalysis;
     36using HeuristicLab.GP.Interfaces;
     37using HeuristicLab.GP;
     38using HeuristicLab.GP.StructureIdentification;
    3639
    3740namespace HeuristicLab.CEDMA.Server {
    … …  
    196199      }
    197200      algo.AllowedVariables = allowedFeatures;
     201
     202      IGeneticProgrammingAlgorithm structIdAlgo = algo as IGeneticProgrammingAlgorithm;
     203      if (structIdAlgo != null) {
     204        var funLib = SelectRandomFunctionLibrary();
     205        structIdAlgo.FunctionLibraryInjector = funLib;
     206      }
     207    }
     208
     209    private IOperator SelectRandomFunctionLibrary() {
     210      DiscoveryService ds = new DiscoveryService();
     211      var injectors = from injector in ds.GetInstances<FunctionLibraryInjectorBase>()
     212                      where injector.GetType().GetCustomAttributes(typeof(SymbolicRegressionFunctionLibraryInjectorAttribute), true).Count() > 0
     213                      select injector;
     214
     215      return injectors.ElementAt(random.Next(injectors.Count()));
    198216    }
    199217

  • trunk/sources/HeuristicLab.GP.Algorithms/3.2/AlgorithmBase.cs

    r2385 r2566  
    3131using HeuristicLab.Selection;
    3232using HeuristicLab.GP.Operators;
     33using HeuristicLab.GP.Interfaces;
    3334
    3435namespace HeuristicLab.GP.Algorithms {
    35   public abstract class AlgorithmBase : ItemBase {
     36  public abstract class AlgorithmBase : ItemBase, IGeneticProgrammingAlgorithm {
    3637    public virtual string Name { get { return "GP"; } }
    3738    public virtual string Description { get { return "TODO"; } }

  • trunk/sources/HeuristicLab.GP.Algorithms/3.2/HeuristicLab.GP.Algorithms-3.2.csproj

    r2474 r2566  
    119119      <Name>HeuristicLab.Evolutionary-3.2</Name>
    120120    </ProjectReference>
     121    <ProjectReference Include="..\..\HeuristicLab.GP.Interfaces\3.3\HeuristicLab.GP.Interfaces-3.3.csproj">
     122      <Project>{924B6BEA-9A99-40FE-9334-5C01E8D540EC}</Project>
     123      <Name>HeuristicLab.GP.Interfaces-3.3</Name>
     124    </ProjectReference>
    121125    <ProjectReference Include="..\..\HeuristicLab.GP.Operators\3.3\HeuristicLab.GP.Operators-3.3.csproj">
    122126      <Project>{45D11FBD-A71B-48D3-8A94-8EB0DFE8E06A}</Project>

  • trunk/sources/HeuristicLab.GP.Algorithms/3.2/HeuristicLabGpAlgorithmsPlugin.cs

    r2474 r2566  
    2929  [PluginFile(Filename = "HeuristicLab.GP.Algorithms-3.2.dll", Filetype = PluginFileType.Assembly)]
    3030  [Dependency(Dependency = "HeuristicLab.Common-3.2")]
     31  [Dependency(Dependency = "HeuristicLab.Core-3.2")]
     32  [Dependency(Dependency = "HeuristicLab.Data-3.2")]
     33  [Dependency(Dependency = "HeuristicLab.Evolutionary-3.2")]
     34  [Dependency(Dependency = "HeuristicLab.GP-3.3")]
     35  [Dependency(Dependency = "HeuristicLab.GP.Interfaces-3.3")]
     36  [Dependency(Dependency = "HeuristicLab.GP.Operators-3.3")]
     37  [Dependency(Dependency = "HeuristicLab.Logging-3.2")]
     38  [Dependency(Dependency = "HeuristicLab.Operators-3.2")]
     39  [Dependency(Dependency = "HeuristicLab.Random-3.2")]
     40  [Dependency(Dependency = "HeuristicLab.Selection-3.2")]
     41  [Dependency(Dependency = "HeuristicLab.Selection.OffspringSelection-3.2")]
     42  [Dependency(Dependency = "HeuristicLab.SequentialEngine-3.2")]
    3143  public class HeuristicLabGpAlgorithmsPlugin : PluginBase {
    3244  }

  • trunk/sources/HeuristicLab.GP.Interfaces/3.3/HeuristicLab.GP.Interfaces-3.3.csproj

    r2364 r2566  
    8888    <Compile Include="IFunction.cs" />
    8989    <Compile Include="IFunctionTree.cs" />
     90    <Compile Include="IGeneticProgrammingAlgorithm.cs" />
    9091    <Compile Include="Properties\AssemblyInfo.cs" />
    9192  </ItemGroup>

  • trunk/sources/HeuristicLab.GP.Operators/3.3/Initialization/ProbabilisticTreeCreator.cs

    r2560 r2566  
    5757
    5858    public static IFunctionTree Create(IRandom random, FunctionLibrary funLib, int minSize, int maxSize, int maxHeight) {
    59       int treeSize = random.Next(minSize, maxSize + 1);
     59      int treeSize = random.Next(minSize, maxSize);
    6060      IFunctionTree root;
    6161      int tries = 0;
    … …  
    6565        if (tries++ >= MAX_TRIES) {
    6666          // try a different size
    67           treeSize = random.Next(minSize, maxSize + 1);
     67          treeSize = random.Next(minSize, maxSize);
    6868          tries = 0;
    6969        }

  • trunk/sources/HeuristicLab.GP.StructureIdentification.TimeSeries/3.3/OffspringSelectionGPTimeSeriesPrognosis.cs

    r2361 r2566  
    5858      op.Name = "FunctionLibraryInjector";
    5959      SequentialProcessor seq = new SequentialProcessor();
    60       FunctionLibraryInjector funLibInjector = new FunctionLibraryInjector();
     60      DefaultFunctionLibraryInjector funLibInjector = new DefaultFunctionLibraryInjector();
    6161      funLibInjector.GetVariable("Differentials").Value = new BoolData(true);
    6262      seq.AddSubOperator(funLibInjector);

  • trunk/sources/HeuristicLab.GP.StructureIdentification.TimeSeries/3.3/StandardGPTimeSeriesPrognosis.cs

    r2361 r2566  
    5858      op.Name = "FunctionLibraryInjector";
    5959      SequentialProcessor seq = new SequentialProcessor();
    60       FunctionLibraryInjector funLibInjector = new FunctionLibraryInjector();
     60      DefaultFunctionLibraryInjector funLibInjector = new DefaultFunctionLibraryInjector();
    6161      funLibInjector.GetVariable("Differentials").Value = new BoolData(true);
    6262      seq.AddSubOperator(funLibInjector);

  • trunk/sources/HeuristicLab.GP.StructureIdentification/3.3/DefaultStructureIdentificationOperators.cs

    r2553 r2566  
    3535      op.Name = "FunctionLibraryInjector";
    3636      SequentialProcessor seq = new SequentialProcessor();
    37       seq.AddSubOperator(new FunctionLibraryInjector());
    38       seq.AddSubOperator(new HL3TreeEvaluatorInjector());
    39       op.OperatorGraph.AddOperator(seq);
    40       op.OperatorGraph.InitialOperator = seq;
    41       return op;
    42     }
    43 
    44     public static IOperator CreateSimpleFunctionLibraryInjector() {
    45       CombinedOperator op = new CombinedOperator();
    46       op.Name = "FunctionLibraryInjector";
    47       SequentialProcessor seq = new SequentialProcessor();
    48       var funLibInjector = new FunctionLibraryInjector();
    49       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.CONSTANTS_ALLOWED, null, false).Data = true;
    50       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.VARIABLES_ALLOWED, null, false).Data = true;
    51       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.ADDITION_ALLOWED, null, false).Data = true;
    52       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.SUBTRACTION_ALLOWED, null, false).Data = true;
    53       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.MULTIPLICATION_ALLOWED, null, false).Data = true;
    54 
    55       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.AND_ALLOWED, null, false).Data = false;
    56       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.AVERAGE_ALLOWED, null, false).Data = false;
    57       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.COSINUS_ALLOWED, null, false).Data = false;
    58       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.DIFFERENTIALS_ALLOWED, null, false).Data = false;
    59       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.DIVISION_ALLOWED, null, false).Data = false;
    60       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.EQUAL_ALLOWED, null, false).Data = false;
    61       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.EXPONENTIAL_ALLOWED, null, false).Data = false;
    62       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.GREATERTHAN_ALLOWED, null, false).Data = false;
    63       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.IFTHENELSE_ALLOWED, null, false).Data = false;
    64       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.LESSTHAN_ALLOWED, null, false).Data = false;
    65       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.LOGARTIHM_ALLOWED, null, false).Data = false;
    66       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.NOT_ALLOWED, null, false).Data = false;
    67       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.OR_ALLOWED, null, false).Data = false;
    68       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.POWER_ALLOWED, null, false).Data = false;
    69       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.SIGNUM_ALLOWED, null, false).Data = false;
    70       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.SINUS_ALLOWED, null, false).Data = false;
    71       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.SQRT_ALLOWED, null, false).Data = false;
    72       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.TANGENS_ALLOWED, null, false).Data = false;
    73       funLibInjector.GetVariableValue<BoolData>(FunctionLibraryInjector.XOR_ALLOWED, null, false).Data = false;
    74       seq.AddSubOperator(funLibInjector);
     37      seq.AddSubOperator(new DefaultFunctionLibraryInjector());
    7538      seq.AddSubOperator(new HL3TreeEvaluatorInjector());
    7639      op.OperatorGraph.AddOperator(seq);

  • trunk/sources/HeuristicLab.GP.StructureIdentification/3.3/FunctionLibraryInjectors/DefaultFunctionLibraryInjector.cs

    r2564 r2566  
    2727
    2828namespace HeuristicLab.GP.StructureIdentification {
    29   public class FunctionLibraryInjector : FunctionLibraryInjectorBase {
     29  [SymbolicRegressionFunctionLibraryInjector]
     30  public class DefaultFunctionLibraryInjector : FunctionLibraryInjectorBase {
    3031    public const string MINTIMEOFFSET = "MinTimeOffset";
    3132    public const string MAXTIMEOFFSET = "MaxTimeOffset";
    … …  
    6364    }
    6465
    65     public FunctionLibraryInjector()
     66    public DefaultFunctionLibraryInjector()
    6667      : base() {
    6768      AddVariableInfo(new VariableInfo(MINTIMEOFFSET, "Minimal time offset for all features", typeof(IntData), VariableKind.In));

  • trunk/sources/HeuristicLab.GP.StructureIdentification/3.3/HeuristicLab.GP.StructureIdentification-3.3.csproj

    r2553 r2566  
    8585    <Compile Include="BaseClasses\FunctionTreeBase.cs" />
    8686    <Compile Include="BaseClasses\TreeEvaluatorBase.cs" />
    87     <Compile Include="OffspringSelectionGPSimpleRegression.cs" />
    88     <Compile Include="StandardGPSimpleRegression.cs" />
     87    <Compile Include="FunctionLibraryInjectors\ArithmeticFunctionLibraryInjector.cs" />
     88    <Compile Include="FunctionLibraryInjectors\SymbolicRegressionFunctionLibraryInjectorAttribute.cs" />
     89    <Compile Include="FunctionLibraryInjectors\UnconstrainedFunctionLibraryInjector.cs" />
     90    <Compile Include="FunctionLibraryInjectors\DefaultFunctionLibraryInjector.cs" />
     91    <Compile Include="FunctionLibraryInjectors\SimpleFunctionLibraryInjector.cs" />
    8992    <Compile Include="DefaultStructureIdentificationOperators.cs" />
    9093    <Compile Include="Evaluators\NodeBasedVariableImpactCalculator.cs" />
    … …  
    133136    <Compile Include="ITreeEvaluator.cs" />
    134137    <Compile Include="Evaluators\MeanAbsolutePercentageOfRangeErrorEvaluator.cs" />
    135     <Compile Include="FunctionLibraryInjector.cs" />
    136138    <Compile Include="Evaluators\CoefficientOfDeterminationEvaluator.cs" />
    137139    <Compile Include="Evaluators\UncertainMeanSquaredErrorEvaluator.cs" />

  • trunk/sources/HeuristicLab.GP.StructureIdentification/3.3/OffspringSelectionGPRegression.cs

    r2440 r2566  
    116116        problemInjector.OperatorGraph.AddOperator(value);
    117117        problemInjector.OperatorGraph.InitialOperator.AddSubOperator(value, 0);
     118      }
     119    }
     120
     121    public override IOperator FunctionLibraryInjector {
     122      get {
     123        CombinedOperator funLibInjector = (CombinedOperator)GetInitializationOperator().SubOperators[1];
     124        return funLibInjector.OperatorGraph.InitialOperator.SubOperators[0];
     125      }
     126      set {
     127        CombinedOperator funLibInjector = (CombinedOperator)GetInitializationOperator().SubOperators[1];
     128        IOperator seq = funLibInjector.OperatorGraph.InitialOperator;
     129        seq.RemoveSubOperator(0);
     130        seq.AddSubOperator(value, 0);
    118131      }
    119132    }

  • trunk/sources/HeuristicLab.GP.StructureIdentification/3.3/StandardGPRegression.cs

    r2440 r2566  
    117117        problemInjector.OperatorGraph.AddOperator(value);
    118118        problemInjector.OperatorGraph.InitialOperator.AddSubOperator(value, 0);
     119      }
     120    }
     121
     122    public override IOperator FunctionLibraryInjector {
     123      get {
     124        CombinedOperator funLibInjector = (CombinedOperator)GetInitializationOperator().SubOperators[1];
     125        return funLibInjector.OperatorGraph.InitialOperator.SubOperators[0];
     126      }
     127      set {
     128        CombinedOperator funLibInjector = (CombinedOperator)GetInitializationOperator().SubOperators[1];
     129        IOperator seq = funLibInjector.OperatorGraph.InitialOperator;
     130        seq.RemoveSubOperator(0);
     131        seq.AddSubOperator(value, 0);
    119132      }
    120133    }

  • trunk/sources/HeuristicLab.GP/3.3/TreeGardener.cs

    r2222 r2566  
    5151      functions = new List<IFunction>();
    5252      // init functions and terminals based on constraints
    53       foreach(IFunction fun in funLibrary.Functions) {
    54         if(fun.MaxSubTrees == 0) {
     53      foreach (IFunction fun in funLibrary.Functions) {
     54        if (fun.MaxSubTrees == 0) {
    5555          terminals.Add(fun);
    5656          allFunctions.Add(fun);
    … …  
    112112        list.Add(new object[] { root, i, 2 });
    113113      }
    114 
    115       while (list.Count > 0 && totalListMinSize + currentSize < size) {
    116         int randomIndex = random.Next(list.Count);
    117         object[] nextExtension = list[randomIndex];
    118         list.RemoveAt(randomIndex);
    119         IFunctionTree parent = (IFunctionTree)nextExtension[0];
    120         int a = (int)nextExtension[1];
    121         int d = (int)nextExtension[2];
    122         if (d == maxDepth) {
    123           parent.RemoveSubTree(a);
    124           IFunctionTree branch = CreateRandomTree(GetAllowedSubFunctions(parent.Function, a), 1, 1);
    125           parent.InsertSubTree(a, branch); // insert a smallest possible tree
    126           currentSize += branch.GetSize();
    127           totalListMinSize -= branch.GetSize();
    128         } else {
    129           IFunction selectedFunction = TreeGardener.RandomSelect(random, GetAllowedSubFunctions(parent.Function, a).Where(
    130             f => !TreeGardener.IsTerminal(f) && f.MinTreeHeight + (d - 1) <= maxDepth).ToArray());
    131           IFunctionTree newTree = selectedFunction.GetTreeNode();
    132           parent.RemoveSubTree(a);
    133           parent.InsertSubTree(a, newTree);
    134           currentSize++;
    135           totalListMinSize--;
    136 
    137           minArity = selectedFunction.MinSubTrees;
    138           maxArity = selectedFunction.MaxSubTrees;
    139           if (maxArity >= size) {
    140             maxArity = size;
     114      if (IsRecursiveExpansionPossible(root.Function)) {
     115        while (list.Count > 0 && totalListMinSize + currentSize < size) {
     116          int randomIndex = random.Next(list.Count);
     117          object[] nextExtension = list[randomIndex];
     118          list.RemoveAt(randomIndex);
     119          IFunctionTree parent = (IFunctionTree)nextExtension[0];
     120          int a = (int)nextExtension[1];
     121          int d = (int)nextExtension[2];
     122          if (d == maxDepth) {
     123            parent.RemoveSubTree(a);
     124            IFunctionTree branch = CreateRandomTree(GetAllowedSubFunctions(parent.Function, a), 1, 1);
     125            parent.InsertSubTree(a, branch); // insert a smallest possible tree
     126            currentSize += branch.GetSize();
     127            totalListMinSize -= branch.GetSize();
     128          } else {
     129            IFunction selectedFunction = TreeGardener.RandomSelect(random, GetAllowedSubFunctions(parent.Function, a).Where(
     130              f => IsRecursiveExpansionPossible(f) && f.MinTreeHeight + (d - 1) <= maxDepth).ToArray());
     131            IFunctionTree newTree = selectedFunction.GetTreeNode();
     132            parent.RemoveSubTree(a);
     133            parent.InsertSubTree(a, newTree);
     134            currentSize++;
     135            totalListMinSize--;
     136
     137            minArity = selectedFunction.MinSubTrees;
     138            maxArity = selectedFunction.MaxSubTrees;
     139            if (maxArity >= size) {
     140              maxArity = size;
     141            }
     142            actualArity = random.Next(minArity, maxArity + 1);
     143            for (int i = 0; i < actualArity; i++) {
     144              // insert a dummy sub-tree and add the pending extension to the list
     145              newTree.AddSubTree(null);
     146              list.Add(new object[] { newTree, i, d + 1 });
     147            }
     148            totalListMinSize += newTree.Function.MinTreeSize - 1;
    141149          }
    142           actualArity = random.Next(minArity, maxArity + 1);
    143           for (int i = 0; i < actualArity; i++) {
    144             // insert a dummy sub-tree and add the pending extension to the list
    145             newTree.AddSubTree(null);
    146             list.Add(new object[] { newTree, i, d + 1 });
    147           }
    148           totalListMinSize += newTree.Function.MinTreeSize - 1;
    149150        }
    150151      }
    … …  
    162163      return root;
    163164    }
    164  
     165
     166    private bool IsRecursiveExpansionPossible(IFunction parent) {
     167      return FindCycle(parent, new Stack<IFunction>());
     168    }
     169
     170    private Dictionary<IFunction, bool> inCycle = new Dictionary<IFunction, bool>();
     171    private bool FindCycle(IFunction parent, Stack<IFunction> parentChain) {
     172      if (inCycle.ContainsKey(parent)) {
     173        return inCycle[parent];
     174      } else if (IsTerminal(parent)) {
     175        inCycle[parent] = false;
     176        return false;
     177      } else if (parentChain.Contains(parent)) {
     178        inCycle[parent] = true;
     179        return true;
     180      } else {
     181        parentChain.Push(parent);
     182        bool result = false;
     183        // all slot indexes
     184        for (int i = 0; i < parent.MaxSubTrees; i++) {
     185          foreach (IFunction subFunction in GetAllowedSubFunctions(parent, i)) {
     186            result |= FindCycle(subFunction, parentChain);
     187          }
     188        }
     189
     190        parentChain.Pop();
     191        inCycle[parent] = result;
     192        return result;
     193      }
     194    }
     195
    165196    /// <summary>
    166197    /// selects a random function from allowedFunctions and creates a random (unbalanced) tree with maximal size and height.
    … …  
    173204      // get the minimal needed height based on allowed functions and extend the max-height if necessary
    174205      int minTreeHeight = allowedFunctions.Select(f => f.MinTreeHeight).Min();
    175       if(minTreeHeight > maxTreeHeight)
     206      if (minTreeHeight > maxTreeHeight)
    176207        maxTreeHeight = minTreeHeight;
    177208      // get the minimal needed size based on allowed functions and extend the max-size if necessary
    178209      int minTreeSize = allowedFunctions.Select(f => f.MinTreeSize).Min();
    179       if(minTreeSize > maxTreeSize)
     210      if (minTreeSize > maxTreeSize)
    180211        maxTreeSize = minTreeSize;
    181212
    … …  
    204235
    205236      TreeForEach(tree, delegate(IFunctionTree possibleParentNode) {
    206         if(possibleParentNode.SubTrees.Count > 0) {
     237        if (possibleParentNode.SubTrees.Count > 0) {
    207238          parentNodes.Add(possibleParentNode);
    208239        }
    … …  
    234265    // 'tail-recursive' helper
    235266    private int GetBranchLevelHelper(IFunctionTree tree, IFunctionTree branch, int level) {
    236       if(branch == tree) return level;
    237 
    238       foreach(IFunctionTree subTree in tree.SubTrees) {
     267      if (branch == tree) return level;
     268
     269      foreach (IFunctionTree subTree in tree.SubTrees) {
    239270        int result = GetBranchLevelHelper(subTree, branch, level + 1);
    240         if(result != -1) return result;
     271        if (result != -1) return result;
    241272      }
    242273
    … …  
    245276
    246277    public bool IsValidTree(IFunctionTree tree) {
    247       for(int i = 0; i < tree.SubTrees.Count; i++) {
    248         if(!tree.Function.GetAllowedSubFunctions(i).Contains(tree.SubTrees[i].Function)) return false;
    249       }
    250 
    251       if(tree.SubTrees.Count < tree.Function.MinSubTrees || tree.SubTrees.Count > tree.Function.MaxSubTrees)
     278      for (int i = 0; i < tree.SubTrees.Count; i++) {
     279        if (!tree.Function.GetAllowedSubFunctions(i).Contains(tree.SubTrees[i].Function)) return false;
     280      }
     281
     282      if (tree.SubTrees.Count < tree.Function.MinSubTrees || tree.SubTrees.Count > tree.Function.MaxSubTrees)
    252283        return false;
    253       foreach(IFunctionTree subTree in tree.SubTrees) {
    254         if(!IsValidTree(subTree)) return false;
     284      foreach (IFunctionTree subTree in tree.SubTrees) {
     285        if (!IsValidTree(subTree)) return false;
    255286      }
    256287      return true;
    … …  
    259290    // returns a random branch from the specified level in the tree
    260291    public IFunctionTree GetRandomBranch(IFunctionTree tree, int level) {
    261       if(level == 0) return tree;
     292      if (level == 0) return tree;
    262293      List<IFunctionTree> branches = new List<IFunctionTree>();
    263294      GetBranchesAtLevel(tree, level, branches);
    … …  
    269300    internal ICollection<IFunction> GetPossibleParents(List<IFunction> list) {
    270301      List<IFunction> result = new List<IFunction>();
    271       foreach(IFunction f in functions) {
    272         if(IsPossibleParent(f, list)) {
     302      foreach (IFunction f in functions) {
     303        if (IsPossibleParent(f, list)) {
    273304          result.Add(f);
    274305        }
    … …  
    284315      // when the maxArity of this function is smaller than the list of operators that
    285316      // should be included as sub-operators then it can't be a parent
    286       if(maxArity < children.Count()) {
     317      if (maxArity < children.Count()) {
    287318        return false;
    288319      }
    … …  
    294325      // allowed functions for this slot.
    295326      // we only count those slots that can hold at least one of the children that we should combine
    296       for(int slot = 0; slot < nSlots; slot++) {
     327      for (int slot = 0; slot < nSlots; slot++) {
    297328        HashSet<IFunction> functionSet = new HashSet<IFunction>(f.GetAllowedSubFunctions(slot));
    298         if(functionSet.Count() > 0) {
     329        if (functionSet.Count() > 0) {
    299330          slotSets.Add(functionSet);
    300331        }
    … …  
    306337      // we can never combine all children as sub-trees of the function and thus the function
    307338      // can't be a parent.
    308       if(slotSets.Count() < children.Count()) {
     339      if (slotSets.Count() < children.Count()) {
    309340        return false;
    310341      }
    … …  
    317348
    318349      int assignments = 0;
    319       for(int i = 0; i < slotSets.Count() - 1; i++) {
    320         if(slotSets[i].Count > 0) {
     350      for (int i = 0; i < slotSets.Count() - 1; i++) {
     351        if (slotSets[i].Count > 0) {
    321352          IFunction selected = slotSets[i].ElementAt(0);
    322353          assignments++;
    323           for(int j = i + 1; j < slotSets.Count(); j++) {
     354          for (int j = i + 1; j < slotSets.Count(); j++) {
    324355            slotSets[j].Remove(selected);
    325356          }
    … …  
    328359
    329360      // sanity check
    330       if(assignments > children.Count) throw new InvalidProgramException();
     361      if (assignments > children.Count) throw new InvalidProgramException();
    331362      return assignments == children.Count - 1;
    332363    }
    333364    public IList<IFunction> GetAllowedParents(IFunction child, int childIndex) {
    334365      List<IFunction> parents = new List<IFunction>();
    335       foreach(IFunction function in functions) {
     366      foreach (IFunction function in functions) {
    336367        ICollection<IFunction> allowedSubFunctions = GetAllowedSubFunctions(function, childIndex);
    337         if(allowedSubFunctions.Contains(child)) {
     368        if (allowedSubFunctions.Contains(child)) {
    338369          parents.Add(function);
    339370        }
    … …  
    345376    }
    346377    public ICollection<IFunction> GetAllowedSubFunctions(IFunction f, int index) {
    347       if(f == null) {
     378      if (f == null) {
    348379        return allFunctions;
    349380      } else {
    … …  
    355386    #region private utility methods
    356387    public IFunction GetRandomRoot(int maxTreeSize, int maxTreeHeight) {
    357       if(maxTreeHeight == 1 || maxTreeSize == 1) {
     388      if (maxTreeHeight == 1 || maxTreeSize == 1) {
    358389        IFunction selectedTerminal = RandomSelect(terminals);
    359390        return selectedTerminal;
    360391      } else {
    361         IFunction[] possibleFunctions = functions.Where(f => f.MinTreeHeight <= maxTreeHeight &&
    362           f.MinTreeSize <= maxTreeSize).ToArray();
    363         IFunction selectedFunction = RandomSelect(possibleFunctions);
    364         return selectedFunction;
     392        int minExpandableTreeSize = (from f in functions
     393                                     where IsRecursiveExpansionPossible(f)
     394                                     select f.MinTreeSize).Min();
     395        int minExpandableTreeHeight = (from f in functions
     396                                       where IsRecursiveExpansionPossible(f)
     397                                       select f.MinTreeHeight).Min();
     398        IFunction[] possibleFunctions;
     399        if (maxTreeSize < minExpandableTreeSize || maxTreeHeight < minExpandableTreeHeight) {
     400          possibleFunctions = functions.Where(f => f.MinTreeHeight <= maxTreeHeight &&
     401            f.MinTreeSize <= maxTreeSize).ToArray();
     402        } else {
     403          possibleFunctions = functions.Where(f => f.MinTreeHeight <= maxTreeHeight &&
     404            f.MinTreeSize <= maxTreeSize && IsRecursiveExpansionPossible(f)).ToArray();
     405        }
     406        return RandomSelect(possibleFunctions);
    365407      }
    366408    }
    … …  
    368410
    369411    private IFunctionTree MakeUnbalancedTree(IFunction parent, int maxTreeHeight) {
    370       if(maxTreeHeight == 0) return parent.GetTreeNode();
     412      if (maxTreeHeight == 0) return parent.GetTreeNode();
    371413      int minArity = parent.MinSubTrees;
    372414      int maxArity = parent.MaxSubTrees;
    373415      int actualArity = random.Next(minArity, maxArity + 1);
    374       if(actualArity > 0) {
     416      if (actualArity > 0) {
    375417        IFunctionTree parentTree = parent.GetTreeNode();
    376         for(int i = 0; i < actualArity; i++) {
     418        for (int i = 0; i < actualArity; i++) {
    377419          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => f.MinTreeHeight <= maxTreeHeight).ToArray();
    378420          IFunction selectedFunction = RandomSelect(possibleFunctions);
    … …  
    389431    // types of possible sub-functions which can indirectly impose a limit for the depth of a given sub-tree
    390432    private IFunctionTree MakeBalancedTree(IFunction parent, int maxTreeHeight) {
    391       if(maxTreeHeight == 0) return parent.GetTreeNode();
     433      if (maxTreeHeight == 0) return parent.GetTreeNode();
    392434      int minArity = parent.MinSubTrees;
    393435      int maxArity = parent.MaxSubTrees;
    394436      int actualArity = random.Next(minArity, maxArity + 1);
    395       if(actualArity > 0) {
     437      if (actualArity > 0) {
    396438        IFunctionTree parentTree = parent.GetTreeNode();
    397         for(int i = 0; i < actualArity; i++) {
     439        for (int i = 0; i < actualArity; i++) {
    398440          // first try to find a function that fits into the maxHeight limit
    399441          IFunction[] possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => f.MinTreeHeight <= maxTreeHeight &&
    400442            !IsTerminal(f)).ToArray();
    401443          // no possible function found => extend function set to terminals
    402           if(possibleFunctions.Length == 0) {
     444          if (possibleFunctions.Length == 0) {
    403445            possibleFunctions = GetAllowedSubFunctions(parent, i).Where(f => IsTerminal(f)).ToArray();
    404446            IFunction selectedTerminal = RandomSelect(possibleFunctions);
    … …  
    418460    private static void TreeForEach(IFunctionTree tree, Action<IFunctionTree> action) {
    419461      action(tree);
    420       foreach(IFunctionTree subTree in tree.SubTrees) {
     462      foreach (IFunctionTree subTree in tree.SubTrees) {
    421463        TreeForEach(subTree, action);
    422464      }
    … …  
    424466
    425467    private static void GetBranchesAtLevel(IFunctionTree tree, int level, List<IFunctionTree> result) {
    426       if(level == 1) result.AddRange(tree.SubTrees);
    427       foreach(IFunctionTree subTree in tree.SubTrees) {
    428         if(subTree.GetHeight() >= level - 1)
     468      if (level == 1) result.AddRange(tree.SubTrees);
     469      foreach (IFunctionTree subTree in tree.SubTrees) {
     470        if (subTree.GetHeight() >= level - 1)
    429471          GetBranchesAtLevel(subTree, level - 1, result);
    430472      }
Note: See TracChangeset for help on using the changeset viewer.