search

heal-research / HeuristicLab

HeuristicLab - An environment for heuristic and evolutionary optimization
https://dev.heuristiclab.com
GNU General Public License v3.0
39 stars 16 forks source link

StackOverflowException when SymbolicExpressionGrammar is configured wrong #1472

Closed HeuristicLab-Trac-Bot closed 13 years ago

HeuristicLab-Trac-Bot commented 13 years ago

Issue migrated from trac ticket # 1472

milestone: HeuristicLab 3.3.4 | component: Encodings.SymbolicExpressionTreeEncoding | priority: medium | resolution: done

2011-04-13 00:04:04: @discostu105 created the issue

When a symbolic regression problem with a TypeCoherentExpressionGrammar is configured like this (the numbers in brackets indicate the InitialFrequency):

ProgramRootSymbol (0)
StartSymbol (0)
Defun (1)
Addition (1)
Subtraction (1)
Multiplication (0)
Division (0)
Average (1)
Sine (1)
Cosine (0)
Tangent (0)
Logarithm (1)
Power (1)
Root (1)
Exponential (0)
IfThenElse (1)
GreaterThan (1)
LessThan (1)
And (1)
Or (1)
Not (0)
TimeLag (1)
Integral (1)
Derivative (1)
Constant (0)
Variable (0)
LaggedVariable (0)
Variable Condition (0)

the execution of the algorithm (such as a GeneticAlgorithm) causes the process to crash due to a StackOverflowException. This is the the (shortened) stacktrace:

    ---> StackOverFlowException
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode.Grammar.get() Line 98 + 0x32 bytes    C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode.Grammar.get() Line 98 + 0x34 bytes    C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode.Grammar.get() Line 98 + 0x34 bytes    C#
  ...
  ~1577 calls
  ...
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode.Grammar.get() Line 98 + 0x34 bytes    C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode.Grammar.get() Line 98 + 0x34 bytes    C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode.Grammar.get() Line 98 + 0x34 bytes    C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ProbabilisticTreeCreator.ReplaceWithMinimalTree.AnonymousMethod__11(HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbol s) Line 204 + 0x33 bytes   C#
  [External Code] 
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ProbabilisticTreeCreator.ReplaceWithMinimalTree(HeuristicLab.Core.IRandom random, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode root, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode parent, int childIndex) Line 202 + 0x291 bytes   C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ProbabilisticTreeCreator.ReplaceWithMinimalTree(HeuristicLab.Core.IRandom random, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode root, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode parent, int childIndex) Line 223 + 0x1f bytes    C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ProbabilisticTreeCreator.ReplaceWithMinimalTree(HeuristicLab.Core.IRandom random, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode root, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode parent, int childIndex) Line 223 + 0x1f bytes    C#
  ...
  ~1576 calls
  ...
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ProbabilisticTreeCreator.ReplaceWithMinimalTree(HeuristicLab.Core.IRandom random, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode root, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode parent, int childIndex) Line 223 + 0x1f bytes    C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ProbabilisticTreeCreator.ReplaceWithMinimalTree(HeuristicLab.Core.IRandom random, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode root, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode parent, int childIndex) Line 223 + 0x1f bytes    C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ProbabilisticTreeCreator.ReplaceWithMinimalTree(HeuristicLab.Core.IRandom random, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode root, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode parent, int childIndex) Line 223 + 0x1f bytes    C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ProbabilisticTreeCreator.TryCreateFullTreeFromSeed(HeuristicLab.Core.IRandom random, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode root, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeGrammar globalGrammar, int targetLength, int maxDepth) Line 194 + 0x25 bytes   C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ProbabilisticTreeCreator.PTC2(HeuristicLab.Core.IRandom random, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionTreeNode seedNode, int maxLength, int maxDepth) Line 115 + 0x89 bytes   C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ProbabilisticTreeCreator.Create(HeuristicLab.Core.IRandom random, HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbolicExpressionGrammar grammar, int maxTreeLength, int maxTreeDepth) Line 92 + 0x22 bytes    C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ProbabilisticTreeCreator.Create(HeuristicLab.Core.IRandom random) Line 78 + 0x7e bytes   C#
  HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dllHeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeCreator.Apply() Line 58 + 0x3c bytes   C#
  HeuristicLab.Operators-3.3.dllHeuristicLab.Operators.Operator.Execute(HeuristicLab.Core.IExecutionContext context, System.Threading.CancellationToken cancellationToken) Line 115 + 0x18 bytes  C#
  HeuristicLab.SequentialEngine-3.3.dllHeuristicLab.SequentialEngine.SequentialEngine.Run(System.Threading.CancellationToken cancellationToken) Line 60 + 0x70 bytes  C#
  HeuristicLab.Core-3.3.dllHeuristicLab.Core.Engine.Run(object state) Line 153 + 0x1c bytes   C#
  [External Code]

While it is clear that not selecting Variable and Constant will prevent the algorithm to work correctly, the process should not crash. The algorithm should instead just throw an exception.

This is important especially in MetaOptimization where this kind of parameterization can be chosen randomly.

HeuristicLab-Trac-Bot commented 13 years ago

2011-04-13 00:25:46: @discostu105 commented

Here are other configurations which also caused a StackOverflowException:

ProgramRootSymbol (0)
StartSymbol (0)
Defun (1)
Addition (1)
Subtraction (0)
Multiplication (0)
Division (0)
Average (0)
Sine (1)
Cosine (1)
Tangent (0)
Logarithm (1)
Power (1)
Root (0)
Exponential (0)
IfThenElse (1)
GreaterThan (0)
LessThan (0)
And (0)
Or (0)
Not (1)
TimeLag (1)
Integral (0)
Derivative (0)
Constant (1)
Variable (1)
LaggedVariable (0)
Variable Condition (1)
ProgramRootSymbol (1)
StartSymbol (1)
Defun (1)
Addition (0)
Subtraction (0)
Multiplication (1)
Division (1)
Average (0)
Sine (1)
Cosine (1)
Tangent (1)
Logarithm (1)
Power (0)
Root (1)
Exponential (1)
IfThenElse (1)
GreaterThan (0)
LessThan (0)
And (0)
Or (1)
Not (1)
TimeLag (1)
Integral (0)
Derivative (0)
Constant (1)
Variable (1)
LaggedVariable (1)
Variable Condition (0)

I can't exactly figure out, what the error in the configuration is.

HeuristicLab-Trac-Bot commented 13 years ago

2011-04-13 11:18:23: @gkronber commented

Replying to [comment:1 cneumuel]:

Here are other configurations which also caused a StackOverflowException:

[...]

I can't exactly figure out, what the error in the configuration is.

In the type coherent grammar the IfThenElse symbol is configured in such a way that it needs a boolean value for the condition. Boolean values can only be generated from variables and constants through relational operators (> and <).

HeuristicLab-Trac-Bot commented 13 years ago

2011-04-13 11:20:01: @gkronber changed status from new to accepted

HeuristicLab-Trac-Bot commented 13 years ago

2011-04-13 11:20:01: @gkronber changed component from Problems.DataAnalysis.Regression to Encodings.SymbolicExpressionTreeEncoding

HeuristicLab-Trac-Bot commented 13 years ago

2011-04-13 11:20:09: @gkronber removed milestone

HeuristicLab-Trac-Bot commented 13 years ago

2011-04-13 16:03:04: @gkronber commented

r6009:

  • implemented a check in PTC2 operator
  • fixed bugs in SymbolicExpressionGrammarBase
  • made some small changes in both classes to prevent numeric overflow exceptions
HeuristicLab-Trac-Bot commented 13 years ago

2011-04-13 16:03:14: @gkronber changed status from accepted to reviewing

HeuristicLab-Trac-Bot commented 13 years ago

2011-04-13 16:03:14: @gkronber changed owner from gkronber to cneumuel

HeuristicLab-Trac-Bot commented 13 years ago

2011-04-20 15:33:12: @discostu105 changed status from reviewing to readytorelease

HeuristicLab-Trac-Bot commented 13 years ago

2011-04-20 15:33:12: @discostu105 changed owner from cneumuel to swagner

HeuristicLab-Trac-Bot commented 13 years ago

2011-05-04 19:43:12: @s-wagner changed status from readytorelease to closed

HeuristicLab-Trac-Bot commented 13 years ago

2011-05-04 19:43:12: @s-wagner removed resolution