Random Initialisation of Programs

A random tree is generated simply by starting with a new node of type ROOT, picking a random element from the array stored in $F{ROOT}, creating new nodes wherever {TYPE} is seen. This is illustrated below:

 1  $genome{nodeROOT0}      = '{nodeSTATEMENT0}';

 2  $genome{nodeSTATEMENT0} = '{nodeSTATEMENT1} {nodeSTATEMENT2}';

 3  $genome{nodeSTATEMENT1} = '$s = "{nodeWORD0}";';

 4  $genome{nodeSTATEMENT2} = 'print "{nodeSTRING0}!\n";';

 5  $genome{nodeSTRING0}    = '{nodeSTRING1}, {nodeSTRING2}';

 6  $genome{nodeSTRING1}    = '{nodeWORD1}';

 7  $genome{nodeSTRING2}    = '{nodeWORD2}';

 8  $genome{nodeWORD0}      = 'donuts';

 9  $genome{nodeWORD1}      = 'mmm';

10  $genome{nodeWORD2}      = '$s';

To make a new tree: start with a ROOT node, assign a new genome key nodeROOT0 and pick one of the available ROOT type functions from the grammar (see Section 7.2). In this case there is only one choice (line 1). The contents of the new node require a new STATEMENT type node to be created, and a random function of that type is chosen (line 2). Now there are two child nodes to be expanded (lines 3 and 4). The process continues recursively along all branches and when a function can not be found, a terminal node is used instead.

Here are a few examples of random code generated from the actual grammar defined in Section 7.2, generated with the utility program perlgp-rand-prog.pl, each separated by a blank line.

print "$s, donuts, mmm, mmm, $s!\n";
print "$s, mmm, $s!\n";
print "$s!\n";

$s = "$s";

print "mmm, mmm!\n";
$s = "$s";
print "mmm, $s, $s, mmm, mmm, $s!\n";
print "donuts!\n";
$s = "mmm";
print "mmm, donuts, mmm, mmm, mmm, $s, mmm, donuts, $s, mmm, $s, $s, donuts,
 donuts, donuts, donuts, mmm, $s, donuts, donuts, donuts, donuts, mmm!\n";
print "$s, $s!\n";

$s = "donuts";
$s = "donuts";
$s = "mmm";
$s = "$s";
print "donuts!\n";

$s = "donuts";

Tree termination and size control can be achieved in three ways. I prefer to construct the Grammar with biased frequencies of branching and non-branching functions so that trees terminate naturally.

Whereas the following grammar definition tends to produce very deep trees:

$F{STRING} = ['{STRING}, {STRING}','{WORD}'];,

this modification produces more reasonably sized trees:

$F{STRING} = ['{STRING}, {STRING}','{WORD}','{WORD}','{WORD}'];

because the WORD type is non-branching and only terminals are defined for it.

Alternatively or additionally, maximum and minimum tree sizes (number of nodes) can be imposed, along with an early termination probability and a maximum tree depth limit.