GEP Book   Home   News   Author   Q&A   Tutorials   Downloads   GEP Biblio   Contacts   Visit Gepsoft

C. FERREIRA In J. M. Santos and A. Zapico, eds., Proceedings of the Argentine Symposium on Artificial Intelligence, pages 160-174, Santa Fe, Argentina, 2002. Combinatorial Optimization by Gene Expression Programming: Inversion Revisited Introduction   Gene expression programming (GEP) is a multigenic genotype/phenotype system encoding expression trees linked by a particular linking interaction (Ferreira 2001). In its simplest representation (head length h = 0 and maximum arity n = 0), GEP is equivalent to the canonical genetic algorithm (GA), in which each gene consists of only one terminal. Such simple chromosomal organization was used to solve the 11-multiplexer problem, where the one-element expression trees encoded in each gene were posttranslationally linked by the Boolean function if (x,y,z) (Ferreira 2001). To solve combinatorial problems, however, another kind of linking interaction is required. For instance, in the traveling salesperson problem (TSP) the linking consists obviously of the distance between the cities represented by two adjacent genes. The TSP represents a classic optimization problem and good, traditional approximation algorithms have been developed to tackle it down (see, e.g., Papadimitriou and Steiglitz 1982 for a review). However, to evolutionary computists, the TSP serves as the simplest case of a variety of combinatorial problems which are of enormous relevance to industrial scheduling problems (Bonachea et al. 2000; Hsu and Hsu 2001; Johnson and McGeoch 1997; Katayama and Narihisa 1999; Merz and Freisleben 1997; Reinelt 1994). Indeed, several evolution inspired algorithms used the TSP as a battleground to develop combinatorial-specific search operators such as: alternating edge crossover (Grefenstette et al. 1985), subtour chunks crossover (Grefenstette et al. 1985), heuristic crossover for adjacency representation (Grefenstette et al. 1985; Jog et al. 1989; Lin 1965; Suh and van Gucht 1987), partially-mapped crossover (Goldberg and Lingle 1985), cycle crossover (Oliver et al. 1987), order crossover (Davis 1985; Oliver et al. 1987), order and position based crossover (Syswerda 1991), heuristic crossover for path representation (Grefenstette 1987; Liepins et al. 1987), genetic edge recombination crossover (Whitley et al. 1989, 1991), maximal preservative crossover (Mühlenbein et al. 1988), voting recombination crossover (Mühlenbein 1989), displacement mutation (Herdy 1991; Michalewicz 1992), exchange mutation (Ambati et al. 1991; Banzhaf 1990; Michalewicz 1992; Oliver et al. 1987; Syswerda 1991), repeated exchange mutation (Ambati et al. 1991; Beyer 1992), insertion mutation (Fogel 1988; Michalewicz 1992; Syswerda 1991), simple inversion mutation (Grefenstette 1987; Holland 1975), inversion mutation (Fogel 1990, 1993), and scramble mutation (Ulder et al. 1990). Note that, in some cases, operators are not named exactly as in the original work, as this nomenclature was recently proposed by Larrañaga et al. (1998) in an attempt to classify the overwhelming number of combinatorial search operators. More recently, other operators such as edge assembly crossover (Nagata and Kobayashi 1997) and inver-over operator (Tao and Michalewicz 1998) were developed. Despite or due to the huge number of combinatorial-specific operators, little work has been done on the comparative performance of the different operators, although different forms of crossover have been compared (Grefenstette et al. 1985; Oliver et al. 1987; Whitley et al. 1989, 1991). In this work, the performance of simple inversion mutation is compared with insertion mutation and exchange mutation on the difficult 19-cities tour TSP, with simple inversion mutation astoundingly outperforming insertion and exchange mutation. Furthermore, poorly performing operators such as displacement mutation or repeated exchange mutation, could only be compared using an easier tour of only 13 cities. Thus, insertion and displacement mutation, two closely related operators in terms of implementation, are compared on the 13-cities tour TSP. Exchange mutation and repeated exchange mutation are also compared using the shorter tour. Moreover, the potentialities of inversion are further demonstrated by solving a simple task assignment problem where a new chromosomal organization based on multigene families is used. Home | Contents | Previous | Next