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

Inversion
 

The inversion operator, in its mechanism, corresponds basically to the inversion operator firstly described by Holland (1975). In the classification proposed by Larrañaga et al. (1998) it received the more complicated designation of “simple inversion mutation”. In the MGFs context of GEP the inversion operator works as follows: it randomly selects the chromosome, the multigene family to be modified, the inversion points in the MGF, and then inverts the sequence between these points. Each chromosome can only be modified once by this operator.

Consider the chromosome below composed of two multigene families, each containing 13 members:

01234567890120123456789012

bhfgkicmjlaedmdclebfgkjhia

(3.1)

Suppose genes 2 and 6 in MGF2 were chosen as inversion points. Then the sequence between these points is reversed, obtaining:

01234567890120123456789012

bhfgkicmjlaedmdFBELCgkjhia

(3.2)

Note that, with inversion, the whole multigene family can be inverted if the first and last gene were chosen as inversion points. For instance, the inversion of MGF2 in chromosome (3.1) gives:

01234567890120123456789012

bhfgkicmjlaedAIHJKGFBELCDM

(3.3)

Note also that this operator allows small adjustments like, for instance, the permutation of two adjacent genes. For instance, if genes 7 and 8 in FMG1 of chromosome (3.3) were chosen as inversion points, these genes are permuted, obtaining:

01234567890120123456789012

bhfgkicjmlaedAIHJKGFBELCDM

(3.4)

As Figure 1 emphasizes, inversion is the most powerful of the combinatorial-specific genetic operators, causing populations to evolve with great efficiency when used as the only source of genetic diversification. Indeed, this operator alone produces better results than when combined with gene deletion/insertion or permutation.

The high performance obtained by GEP inversion is surprising and deserves a careful inspection. Perhaps for historical reasons, inversion was abandoned by researchers in the early development of GAs (see, e.g., Goldberg 1989 and Mitchell 1996). Decisive for this outcome was, most certainly, Bagley’s (1967) disappointment with inversion while trying to conciliate inversion with homologous recombination (see Goldberg 1989 for a detailed narrative). Obviously, inversion disrupts homology and homologous recombination ceases to work. Unfortunately, Bagley persisted with recombination and did not try inversion alone.

Furthermore, the astounding results obtained for inversion are better appreciated if we compare them with attempts to solve the 19-cities tour TSP by GAs (Haupt and Haupt 1998). These researchers could not find the shortest route using population sizes of 800 for 200 generations. As shown in Figure 1, GEP not only finds the shortest route using inversion but also using gene deletion/insertion or restricted permutation using population sizes eight times smaller than the ones used by the GA. Moreover, if inversion alone is doing the search, GEP finds the shortest route in 96% of the runs.

Home | Contents | Previous | Next