Please help with solution min/max boundaries ❓

[logindejavu27]

Hello guys,

first I want to say big thanks for amazing library!

I have a question how to avoid useless small rules and start initialization with bigger number of rules combinations.
I tried using MIN_INIT_TREE_DEPTH but could not manage to achieve this.

here is my gramma:

<solution> ::= <rule>
<rule> ::= <rule> and <rule>|<bool-expr>|<rule>
<bool-expr> ::= p<idx> > p<idx>|p<idx> < p<idx>
<idx> ::= 0|1|2|3|4|5|6|7|8|9|10|11|12

this producing phenotypes like:

• p5 < p2
• p2 > p5
• p6 > p7 and p1 > p8
• p3 > p7 and p1 > p6
• ...

is it possible somehow to initialize the search that the minimum phenotype will start from 5 rules and maximum will be for example 10 rules. Something like:

• 5 rules(minimum) p6 > p7 and p1 > p8 and p2 > p3 and p3 > p9 and p1 > p10
  or
• 6 rules p6 > p7 and p1 > p8 and p2 > p3 and p3 > p9 and p1 > p10 and p2 < p10
  or
• 10 rules(maximum) p6 > p7 and p1 > p8 and p2 > p3 and p3 > p9 and p1 > p10 and p2 < p10 and p3 < p4 and p4 < p5 and p5 < p6 and p7 < p8

Could somebody please help with the direction?

P.S. by rule I mean single boolean expression like p5 < p2

[jmmcd]

One approach is to use the grammar, something like this:

<solution> ::= <five_rules> <zero_to_five_rules>
<five_rules> ::= <rule> and <rule> and ...
<zero_to_five_rules> ::= "" | <rule> | <rule> and <rule> | ...

But this would control the min/max size for the entire run, not only during initialisation.

(BTW I don't think you should have <rule> as one of the productions for itself.)

The min/max tree depth should control tree depth, but in your grammar that should indeed control the number of rules. What went wrong?

[logindejavu27]

yes, this will work, but I provided simplified version
hardcoding all variations seems a bit strange, something like this

<solution> ::= <rule5> | <rule6> | <rule7> ...
...
<rule5> ::= <rule> and <rule> and <rule> and <rule> and <rule>
<rule6> ::= <rule> and <rule> ...
<rule7> ::= <rule> and <rule> ...

for example if I need rule be from 5-40, or from 50-100, but I do not want any solution which is smaller than 5/50 rules
ofc, I can try to give lower fitness to small solutions, but then search will take longer then I will be on this planet 😄

but if there is no other way, then I will be forced to create gramma with code where I will generate all this crazy combinations of rules. Just want to make sure maybe is somehow possible with configuration

so when I'm trying to use

MIN_INIT_TREE_DEPTH:     5
MAX_INIT_TREE_DEPTH:     10

it still gives me rules like:

p12 > p8
p9 > p10
p0 < p1 and p10 < p6
...

[jmmcd]

Ok, I see.

The point is that the depth is not the same as the number of ands.

First, remove the <rule> ::= <rule> as this creates a deeper tree without doing anything, so it confuses the calculation.

<solution> ::= <rule>
<rule> ::= <rule> and <rule>|<bool-expr>
<bool-expr> ::= p<idx> > p<idx>|p<idx> < p<idx>
<idx> ::= 0|1|2|3|4|5|6|7|8|9|10|11|12

Second, because of the various rules, even a single and will need a depth of 4 (or 5, I probably have an off-by-one error).

So, try a command like this:

python ponyge.py --grammar ../grammars/test.bnf --min_init_tree_depth 8 --max_init_tree_depth 10 --population_size 1000

[logindejavu27]

using gramma like you provided with following settings

...
CODON_SIZE:             100
GRAMMAR_FILE:           test20.pybnf
FITNESS_FUNCTION:       test20
POPULATION_SIZE:        300
GENERATIONS:            50
MIN_INIT_TREE_DEPTH:     8
MAX_INIT_TREE_DEPTH:     10
...

this still gives me following:

...
**********
p7 < p4 and p2 > p9
**********
p12 < p6 and p6 > p6 and p5 > p1 and p7 > p10 and p0 > p9 and p11 < p11 and p0 < p2 and p4 > p4 and p7 < p9
**********
p7 > p12 and p8 > p4
**********
p1 < p4 and p6 > p2
**********
p9 > p2 and p5 < p0
...

here is fitness for debug (I always return 0 fitness, because first I want to see that it gives me the correct expressions):

class test20(base_ff):

    maximise = True

    def __init__(self):
        super().__init__()

    def evaluate(self, ind, **kwargs):
        
        p, d = ind.phenotype, {}

        print("**********")
        print(p)
        return 0

I start thinking that maybe each part of expression counted like <, and, p0 but even then expression sizes are not correct 😢

Indeed it stop giving me single rules, but this is because I removed single <rule> as you suggested. But still returns rules starting from 2 rules and more

[jmmcd]

Ok! Progress here, but also I do see a bug or two.

First, if I change the recursion to be singly-recursive as follows (notice it's no longer <rule> and <rule>)...

<solution> ::= <rule>
<rule> ::= <rule> and <bool-expr>|<bool-expr>
<bool-expr> ::= p<idx> > p<idx>|p<idx> < p<idx>
<idx> ::= 0|1|2|3|4|5|6|7|8|9|10|11|12

... then this works for me: python ponyge.py --population_size 1000 --grammar ../grammars/test.bnf --min_init_tree_depth 11 --max_init_tree_depth 15

I am using (11, 15) as the min and max and it is always giving between 5 and 10 ands per individual.

I made the change to the grammar because it's easier to reason about when it's singly recursive. Now, every and adds 1 to depth.

I start thinking that maybe each part of expression counted like <, and, p0

In fact, depth refers to the depth of the derivation tree (please see any literature on grammars or on GE). With the double recursion <rule> and <rule>, a tree of a given depth could have different numbers of ands. With the single recursion, the depth determines the number of ands.

[logindejavu27]

thanks a lot!