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

Multigene Families and Scheduling Problems
 
As stated previously, the chromosomal organization used to solve combinatorial problems is very simple and consists of multigenic chromosomes composed of one-element genes, where each gene codes for a one-element expression tree (ET) (Ferreira 2001). Furthermore, one-element genes may be organized in multigene families (MGFs), in which a particular class of terminals or tasks is gathered. Such chromosomes composed of MGFs are very useful to evolve solutions to combinatorial problems, as different classes of terminals/items can be included in each MGF. For instance, the different cities in the traveling salesperson problem may be encoded in a multigene family, where each gene codes for a city. Consider the simple chromosome below, composed of one MGF with nine members:

CADEBHFIG

where each element represents a city. In this case, the expression of this chromosome consists of the spatial organization of the one-element ETs, for instance, the following tour for the traveling salesperson problem (the starting and finishing point is in gray):

For optimization problems with N classes of terminals, multigenic chromosomes composed of N multigene families are used. For instance, the chromosome below composed of two MGFs with six members each, was designed to evolve solutions to the simple task assignment problem of section 4.2 (multigene families have different shades):

012345012345
632451EDFCBA

Its expression consists of the orderly interaction of the members of each MGF with one another as shown below:


Home | Contents | Previous | Next