Paper on combinatorial optimization and inversion

The paper published in the Proceedings of the Argentine Symposium on Artificial Intelligence is now available for download here.

Ferreira, C., Combinatorial Optimization by Gene Expression Programming: Inversion Revisited. In J. M. Santos and A. Zapico, eds., Proceedings of the Argentine Symposium on Artificial Intelligence, pages 160-174, Santa Fe, Argentina, 2002.

ABSTRACT: 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 work, a new algorithm that explores a new chromosomal organization based on multigene families is used. This new organization together with several combinatorial-specific search operators, namely, inversion, gene and sequence deletion/insertion, and restricted and generalized permutation, allow the algorithm to perform with high efficiency. The performance of the new algorithm is empirically compared on the 13- and 19-cities tour traveling salesperson problem, showing that the long abandoned inversion operator is by far the most efficient of the combinatorial operators. The efficiency and potentialities of the new algorithm are further demonstrated by solving a simple task assignment problem.