I've been thinking about grammatical evolution problems and how the grammar influences the algorithm performance. It came to my mind the huge impact that the grammar that you're using has in the time that takes an algorithm to reach an optimum solution.

The simplest example would be if your problem doesn't involve trigonometric operations. If you're trying to find f(x) = 3x - 1/2, including sins, tangents or square roots in your grammar will, almost certainly, slowen your algorithm as the population complexity will grow. Other not-so-evident simplifications for a grammar would be trigonometric identities:

tan(x) = sen(x) / cos(x)

Talking about this last example, I don't know how to determine the importance of the impact of including tan(x) between the grammar rules to produce valid solutions. Or in other words, knowing if adding tan(x) will be better in terms of performance than don't doing it and thus, forcing the evolution to combine two or more operators and terminals to being able to use that operation and making the grammar ambiguous.

So this two are the questions:

  1. Is there any way of knowing if a grammar is optimal for finding a solution?
  2. Which evolutionary algorithm or machine learning method (considering that I'm almost profane in this discipline, some explanation is wellcome) would you use for finding optimal or sub-optimal grammars?


  • $\begingroup$ There is virtually no cost to adding extra operators to an operator grammar, provided you use a decent parser generator. $\endgroup$ – rici Jul 5 '20 at 23:15
  • $\begingroup$ I can't understand what you're asking. What problem are you trying to solve? You talk about "the algorithm"; what algorithm are you referring to, and what does it have to do with the grammar? In what way does adding to the grammar make "the algorithm"/"your algorithm" slower? What are the criteria for a grammar to count as "optimal"? I suspect there's some background or context that hasn't been described here. $\endgroup$ – D.W. Jul 6 '20 at 1:07
  • 1
    $\begingroup$ I just would like to let you know that there is also Artificial Intelligence Stack Exchange, where you can ask questions related to all types of evolutionary computation. If you decide to ask this question there, please, delete it from here to avoid cross-posting. Note that this question is on-topic here too, but given that you didn't get an answer, you may want to try another site. $\endgroup$ – nbro Jan 16 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.