Opened 8 years ago

Closed 8 years ago

#1472 closed defect (done)

StackOverflowException when SymbolicExpressionGrammar is configured wrong

Reported by: cneumuel Owned by: swagner
Priority: medium Milestone: HeuristicLab 3.3.4
Component: Encodings.SymbolicExpressionTreeEncoding Version: 3.3.4
Keywords: Cc:

Description

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.dll!HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode.Grammar.get() Line 98 + 0x32 bytes	C#
 	HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll!HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode.Grammar.get() Line 98 + 0x34 bytes	C#
 	HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll!HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode.Grammar.get() Line 98 + 0x34 bytes	C#
	...
	~1577 calls
	...
 	HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll!HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode.Grammar.get() Line 98 + 0x34 bytes	C#
 	HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll!HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode.Grammar.get() Line 98 + 0x34 bytes	C#
 	HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll!HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeNode.Grammar.get() Line 98 + 0x34 bytes	C#
 	HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll!HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ProbabilisticTreeCreator.ReplaceWithMinimalTree.AnonymousMethod__11(HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ISymbol s) Line 204 + 0x33 bytes	C#
 	[External Code]	
 	HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll!HeuristicLab.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.dll!HeuristicLab.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.dll!HeuristicLab.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.dll!HeuristicLab.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.dll!HeuristicLab.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.dll!HeuristicLab.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.dll!HeuristicLab.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.dll!HeuristicLab.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.dll!HeuristicLab.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.dll!HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.ProbabilisticTreeCreator.Create(HeuristicLab.Core.IRandom random) Line 78 + 0x7e bytes	C#
 	HeuristicLab.Encodings.SymbolicExpressionTreeEncoding-3.4.dll!HeuristicLab.Encodings.SymbolicExpressionTreeEncoding.SymbolicExpressionTreeCreator.Apply() Line 58 + 0x3c bytes	C#
 	HeuristicLab.Operators-3.3.dll!HeuristicLab.Operators.Operator.Execute(HeuristicLab.Core.IExecutionContext context, System.Threading.CancellationToken cancellationToken) Line 115 + 0x18 bytes	C#
 	HeuristicLab.SequentialEngine-3.3.dll!HeuristicLab.SequentialEngine.SequentialEngine.Run(System.Threading.CancellationToken cancellationToken) Line 60 + 0x70 bytes	C#
 	HeuristicLab.Core-3.3.dll!HeuristicLab.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.

Change History (8)

comment:1 follow-up: Changed 8 years ago by cneumuel

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.

comment:2 in reply to: ↑ 1 Changed 8 years ago by gkronber

Replying to 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 <).

comment:3 Changed 8 years ago by gkronber

  • Component changed from Problems.DataAnalysis.Regression to Encodings.SymbolicExpressionTreeEncoding
  • Status changed from new to accepted

comment:4 Changed 8 years ago by gkronber

  • Milestone set to HeuristicLab 3.3.4

comment:5 Changed 8 years ago by gkronber

r6009:

  • implemented a check in PTC2 operator
  • fixed bugs in SymbolicExpressionGrammarBase
  • made some small changes in both classes to prevent numeric overflow exceptions

comment:6 Changed 8 years ago by gkronber

  • Owner changed from gkronber to cneumuel
  • Status changed from accepted to reviewing

comment:7 Changed 8 years ago by cneumuel

  • Owner changed from cneumuel to swagner
  • Status changed from reviewing to readytorelease

comment:8 Changed 8 years ago by swagner

  • Resolution set to done
  • Status changed from readytorelease to closed
  • Version changed from 3.3.3 to 3.3.4
Note: See TracTickets for help on using tickets.