The longer the rule, the more difficult it is to find a good addition. Therefore, it would be a good idea to increase the size of initial population and the number of generations accordingly.
For instance: 20^k or 100*k, where k is the length of the prefix rule.