In this chapter:
We have already seen that, in its simplest representation, gene expression programming is equivalent to the canonical GA in which each gene consists only of one terminal. Indeed, applying equation
(2.4) for determining tail length and taking
h = 0 and n = 0, we get a gene length g = 1 and genes exclusively composed of terminals. 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
(Ferreira 2001). To solve combinatorial problems,
however, another kind of linking interaction is required. For instance, in the traveling salesperson problem the linking consists obviously of the distance between the cities represented by two adjacent genes.
Furthermore, combinatorial optimization problems require combinatorial-specific search operators so that populations of candidate solutions can evolve efficiently. Indeed, several researchers created modifications to the basic genetic operators of mutation and recombination in order to create high performing combinatorial-specific operators. However, it is not known which operators perform better as no systematic comparisons have been done. In this chapter, a new algorithm that explores a new chromosomal organization based on multigene families will be described. We will see that this new chromosomal organization together with several combinatorial-specific search operators, namely, inversion, gene deletion/insertion, sequence deletion/insertion, restricted permutation, and generalized permutation, allow the algorithm to perform with high efficiency, astoundingly outperforming the canonical genetic algorithm.
|