Search strategies for grammatical optimization problems—alternatives to grammar-guided genetic programming

In this chapter, we have a closer look at search strategies for optimization problems, where the structure of valid solutions is defined through a formal grammar. These problems frequently occur in the genetic programming (GP) literature, especially in the context of grammar-guided genetic programming [18]. Even though a lot of progress has been made to extend and improve GP in the last 25 years and many impressive solutions have been produced by GP, the initial goal of an automated programming machine for generating computer programs is still far away and GP is not yet established as a reliable and general method for solving grammatical optimization problems. Instead, many different GP variants have been described and used for solving specific problems. Today the term GP refers to a large set of related algorithms where the commonality mainly is that an evolutionary algorithm is used to produce solutions which often—but not always—represent code that can be executed by a problem specific virtual machine or an interpreter. This code is most frequently represented either as a tree or as a linear chain of instructions. The term genetic programming thus categorizes algorithms based on their approach to solution manipulation. However, the type of problems that is solved using these algorithms is more general. Especially for practitioners, it is often not relevant how a solution has been produced as only the solution itself is relevant. We argue that even though genetic programming is a powerful approach, it might not always be the optimal approach for solving “genetic programming problems” and instead other algorithms might work better for certain problems. Therefore, in this chapter we take a fresh look at those problems, that we in the following call grammatical optimization problems, and discuss various ways for solving such problems. A severely trimmed down extended abstract for this chapter appeared in [14].